Проектирование сумматора по модулю пять
Составление таблицы истинности. Замена симметричных переменных с использованием элементарных симметричных функций. Анализ целесообразности совместной реализации системы функций. Раздельная минимизация и декомпозиция системы функций алгебры логики.
Рубрика | Математика |
Вид | контрольная работа |
Язык | русский |
Дата добавления | 01.01.2013 |
Размер файла | 77,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Анализ технического задания
Требуется спроектировать устройство производящее арифметическую операцию сложения по модулю пять двух чисел в двоичном коде. Слагаемые числа обозначим как Х1 и Х2, результат осуществляемой операции - как Y. Работа устройства описывается следующим уравнением:
Y = (X1 * X2) mod 5 = X1 * X2 - [(X1 * X2) / 5] * 5, (1)
где X1,X2,Y < 5. (2)
Максимальное значение переменных X1,X2,Y равно четырем. Для представления этого числа в двоичной системе счисления понадобится число разрядов, равное
N = ]log25[ = 3
Представим входные и выходную переменные, как
X1 = {x1 x2 x3} X2 = {x4 x5 x6} Y = {y1 y2 y3}
Делаем вывод, что проектируемое устройство будет иметь шесть входов и три выхода. При этом устройство должно соответствовать условиям технического задания.
симметричный переменная декомпозиция алгебра
Составление таблицы истинности
На основе уравнения (1) формируем таблицу истинности устройства. Отсортируем входные наборы по убыванию количества неинверсных переменных. Согласно (2) на наборах, где X1 ? 5 или X2 ? 5, значения Y неопределенны, что обозначим, как «*». Соответствие выходных наборов входным приведено в таблице 1.
Таблица 1.
№ набора |
Кол-во неинв. перемен. |
Входные наборы |
Значения |
X1 * X2 |
Оста-ток |
Y |
|||
X1 |
X2 |
X1 |
X2 |
||||||
1 |
6 |
111 |
111 |
7 |
7 |
14 |
4 |
* |
|
2 |
5 |
111 |
110 |
7 |
6 |
13 |
3 |
* |
|
3 |
111 |
101 |
7 |
5 |
12 |
2 |
* |
||
4 |
111 |
011 |
7 |
3 |
10 |
0 |
* |
||
5 |
110 |
111 |
6 |
7 |
13 |
3 |
* |
||
6 |
101 |
111 |
5 |
7 |
12 |
2 |
* |
||
7 |
011 |
111 |
3 |
7 |
10 |
0 |
* |
||
8 |
4 |
111 |
100 |
7 |
4 |
11 |
1 |
* |
|
9 |
111 |
010 |
7 |
2 |
9 |
4 |
* |
||
10 |
111 |
001 |
7 |
1 |
8 |
3 |
* |
||
11 |
110 |
110 |
6 |
6 |
12 |
2 |
* |
||
12 |
110 |
101 |
6 |
5 |
11 |
1 |
* |
||
13 |
110 |
011 |
6 |
3 |
9 |
4 |
* |
||
14 |
101 |
110 |
5 |
6 |
11 |
1 |
* |
||
15 |
101 |
101 |
5 |
5 |
10 |
0 |
* |
||
16 |
101 |
011 |
5 |
3 |
8 |
3 |
* |
||
17 |
100 |
111 |
4 |
7 |
11 |
1 |
* |
||
18 |
011 |
110 |
3 |
6 |
9 |
4 |
* |
||
19 |
011 |
101 |
3 |
5 |
8 |
3 |
* |
||
20 |
011 |
011 |
3 |
3 |
6 |
1 |
001 |
||
21 |
010 |
111 |
2 |
7 |
9 |
4 |
* |
||
22 |
001 |
111 |
1 |
7 |
8 |
3 |
* |
||
23 |
3 |
111 |
000 |
7 |
0 |
7 |
2 |
* |
|
24 |
110 |
100 |
6 |
4 |
10 |
0 |
* |
||
25 |
110 |
010 |
6 |
2 |
8 |
3 |
* |
||
26 |
110 |
001 |
6 |
1 |
7 |
2 |
* |
||
27 |
101 |
100 |
5 |
4 |
9 |
4 |
* |
||
28 |
101 |
010 |
5 |
2 |
7 |
2 |
* |
||
29 |
101 |
001 |
5 |
1 |
6 |
1 |
* |
||
30 |
100 |
110 |
4 |
6 |
10 |
0 |
* |
||
31 |
100 |
101 |
4 |
5 |
9 |
4 |
* |
||
32 |
100 |
011 |
4 |
3 |
7 |
2 |
010 |
||
33 |
011 |
100 |
3 |
4 |
7 |
2 |
010 |
||
34 |
011 |
010 |
3 |
2 |
5 |
0 |
000 |
||
35 |
011 |
001 |
3 |
1 |
4 |
4 |
100 |
||
36 |
010 |
110 |
2 |
6 |
8 |
3 |
* |
||
37 |
010 |
101 |
2 |
5 |
7 |
2 |
* |
||
38 |
010 |
011 |
2 |
3 |
5 |
0 |
000 |
||
39 |
001 |
110 |
1 |
6 |
7 |
2 |
* |
||
40 |
001 |
101 |
1 |
5 |
6 |
1 |
* |
||
41 |
001 |
011 |
1 |
3 |
4 |
4 |
100 |
||
42 |
000 |
111 |
0 |
7 |
7 |
2 |
* |
||
43 |
2 |
110 |
000 |
6 |
0 |
6 |
1 |
* |
|
44 |
101 |
000 |
5 |
0 |
5 |
0 |
* |
||
45 |
100 |
100 |
4 |
4 |
8 |
3 |
011 |
||
46 |
100 |
010 |
4 |
2 |
6 |
1 |
001 |
||
47 |
100 |
001 |
4 |
1 |
5 |
0 |
000 |
||
48 |
011 |
000 |
3 |
0 |
3 |
3 |
011 |
||
49 |
010 |
100 |
2 |
4 |
6 |
1 |
001 |
||
50 |
010 |
010 |
2 |
2 |
4 |
4 |
100 |
||
51 |
010 |
001 |
2 |
1 |
3 |
3 |
011 |
||
52 |
001 |
100 |
1 |
4 |
5 |
0 |
000 |
||
53 |
001 |
010 |
1 |
2 |
3 |
3 |
011 |
||
54 |
001 |
001 |
1 |
1 |
2 |
2 |
010 |
||
55 |
000 |
110 |
0 |
6 |
6 |
1 |
* |
||
56 |
000 |
101 |
0 |
5 |
5 |
0 |
* |
||
57 |
000 |
011 |
0 |
3 |
3 |
3 |
011 |
||
58 |
1 |
100 |
000 |
4 |
0 |
4 |
4 |
100 |
|
59 |
010 |
000 |
2 |
0 |
2 |
2 |
010 |
||
60 |
001 |
000 |
1 |
0 |
1 |
1 |
001 |
||
61 |
000 |
100 |
0 |
4 |
4 |
4 |
100 |
||
62 |
000 |
010 |
0 |
2 |
2 |
2 |
010 |
||
63 |
000 |
001 |
0 |
1 |
1 |
1 |
001 0 |
||
64 |
0 |
000 |
000 |
0 |
0 |
0 |
0 |
000 |
Замена симметричных переменных с использованием элементарных симметричных функций
1. Анализ симметрии переменных.
Согласно переместительному закону при перестановке слагаемых сумма чисел не меняется, следовательно можно сделать вывод о симметрии переменных x1 и x4, x2 и x5, x3 и x6. Подтвердим это утверждение.
Построим карты Карно для выходных функций образом, удобным для рассмотрения симметрии переменных x1 и x4, x2 и x5.
y1 |
||||||||||||||
x1 |
||||||||||||||
x4 |
||||||||||||||
x2 |
0 |
0 |
0 |
0 |
* |
* |
* |
* |
||||||
0 |
1 |
* |
* |
* |
* |
* |
* |
x6 |
||||||
x5 |
0 |
0 |
* |
* |
* |
* |
* |
* |
||||||
1 |
0 |
* |
* |
* |
* |
* |
* |
|||||||
0 |
0 |
* |
* |
* |
* |
* |
0 |
|||||||
0 |
1 |
* |
* |
* |
* |
* |
0 |
x6 |
||||||
0 |
0 |
* |
* |
* |
* |
* |
0 |
|||||||
0 |
0 |
0 |
1 |
0 |
* |
* |
1 |
|||||||
x3 |
x3 |
y1 = 1456 v 2356 v
2356 v 1234 v
2356.
y2 |
||||||||||||||
x1 |
||||||||||||||
x4 |
||||||||||||||
x2 |
1 |
1 |
1 |
0 |
* |
* |
* |
* |
||||||
1 |
0 |
* |
* |
* |
* |
* |
* |
x6 |
||||||
x5 |
0 |
0 |
* |
* |
* |
* |
* |
* |
||||||
0 |
0 |
* |
* |
* |
* |
* |
* |
|||||||
1 |
1 |
* |
* |
* |
* |
* |
0 |
|||||||
1 |
0 |
* |
* |
* |
* |
* |
1 |
x6 |
||||||
0 |
1 |
* |
* |
* |
* |
* |
0 |
|||||||
0 |
0 |
0 |
0 |
1 |
* |
* |
0 |
|||||||
x3 |
x3 |
y2 = 2356 v 2345 v
14 v 1256 v
2356 v 2356.
y3 |
||||||||||||||
x1 |
||||||||||||||
x4 |
||||||||||||||
x2 |
0 |
1 |
0 |
1 |
* |
* |
* |
* |
||||||
1 |
0 |
* |
* |
* |
* |
* |
* |
x6 |
||||||
x5 |
0 |
1 |
* |
* |
* |
* |
* |
* |
||||||
0 |
0 |
* |
* |
* |
* |
* |
* |
|||||||
0 |
1 |
* |
* |
* |
* |
* |
1 |
|||||||
1 |
0 |
* |
* |
* |
* |
* |
0 |
x6 |
||||||
1 |
0 |
* |
* |
* |
* |
* |
0 |
|||||||
0 |
1 |
0 |
0 |
1 |
* |
* |
0 |
|||||||
x3 |
x3 |
y3 = 3456 v 234 v
14 v 1356 v
2356 v 156 v
2346 v 1236.
Сложность реализации устройства в этом представлении составляет
L(Y) = L'(y1) + L'(y2) + L'(y3) + Lинв.,
где L'(yi) - сложность представления функции yi без учета инверсий входных переменных, а Lинв. - количество инверсных переменных, встречающихся в представлении функций y1,2,3. Тогда
L(Y) = 19 + 21 + 27 + 6 = 73 (3)
оператора И, ИЛИ, НЕ.
На картах Карно видно, что переменные x1 и x4, x2 и x5 симметричны при доопределении карт следующим образом:
y2 |
||||||||||||||
x1 |
||||||||||||||
x4 |
||||||||||||||
x2 |
1 |
1 |
1 |
0 |
* |
* |
1 |
0 |
||||||
1 |
0 |
* |
1 |
* |
* |
* |
1 |
x6 |
||||||
x5 |
0 |
0 |
* |
* |
* |
* |
* |
* |
||||||
0 |
0 |
* |
* |
* |
* |
* |
* |
|||||||
1 |
1 |
1 |
0 |
* |
* |
1 |
0 |
|||||||
1 |
0 |
* |
1 |
* |
* |
* |
1 |
x6 |
||||||
0 |
1 |
* |
0 |
* |
* |
* |
0 |
|||||||
0 |
0 |
0 |
0 |
1 |
* |
0 |
0 |
|||||||
x3 |
x3 |
y1 |
||||||||||||||
x1 |
||||||||||||||
x4 |
||||||||||||||
x2 |
0 |
0 |
0 |
0 |
* |
* |
0 |
0 |
||||||
0 |
1 |
* |
0 |
* |
* |
* |
0 |
x6 |
||||||
x5 |
0 |
0 |
* |
* |
* |
* |
* |
* |
||||||
1 |
0 |
* |
* |
* |
* |
* |
* |
|||||||
0 |
0 |
0 |
0 |
* |
* |
0 |
0 |
|||||||
0 |
1 |
* |
0 |
* |
* |
* |
0 |
x6 |
||||||
0 |
0 |
* |
0 |
* |
* |
* |
0 |
|||||||
0 |
0 |
0 |
1 |
0 |
* |
0 |
1 |
|||||||
x3 |
x3 |
y3 |
||||||||||||||
x1 |
||||||||||||||
x4 |
||||||||||||||
x2 |
0 |
1 |
0 |
1 |
* |
* |
0 |
1 |
||||||
1 |
0 |
* |
0 |
* |
* |
* |
0 |
x6 |
||||||
x5 |
0 |
1 |
* |
* |
* |
* |
* |
* |
||||||
0 |
0 |
* |
* |
* |
* |
* |
* |
|||||||
0 |
1 |
0 |
1 |
* |
* |
0 |
1 |
|||||||
1 |
0 |
* |
0 |
* |
* |
* |
0 |
x6 |
||||||
1 |
0 |
* |
0 |
* |
* |
* |
0 |
|||||||
0 |
1 |
0 |
0 |
1 |
* |
0 |
0 |
|||||||
x3 |
x3 |
Перестройка карты Карно для рассмотрения симметрии переменных x3 и x6 также позволяет убедиться в сделанном предположении о симметрии этих переменных (причем дополнительное доопределение не требуется).
2. Замена переменных с использованием элементарных симметричных функций.
Произведем следующую замену переменных
1) z1 = x1 x4;
z4 = x1 * x4.
Таблица 2. Таблица истинности замены
x1 |
x4 |
z1 |
z4 |
|
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
0 |
|
1 |
0 |
1 |
0 |
|
1 |
1 |
0 |
1 |
Запрещенным является состояние z1 = 1, z4 = 1.
2) z2 = x2 x5;
z5 = x2 * x5.
Таблица 3. Таблица истинности замены
x2 |
x5 |
z2 |
z5 |
|
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
0 |
|
1 |
0 |
1 |
0 |
|
1 |
1 |
0 |
1 |
Запрещенным является состояние z2 = 1, z5 = 1.
3) z3 = x3 x6;
z6 = x3 * x6.
Таблица 4. Таблица истинности замены
x3 |
x6 |
z3 |
z6 |
|
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
0 |
|
1 |
0 |
1 |
0 |
|
1 |
1 |
0 |
1 |
Запрещенным является состояние z3 = 1, z6 = 1.
Построим таблицу отображения исходных входных наборов в базис zi и вычеркнем повторяющиеся наборы в z-отображении:
Таблица 5.
X1 |
X2 |
Y |
Z |
||
x1 x2 x3 |
x4 x5 x6 |
y1 y2 y3 |
z1 z2 z3 |
z4 z5 z6 |
|
011 |
011 |
001 |
000 |
011 |
|
100 |
011 |
010 |
111 |
000 |
|
011 |
100 |
010 |
|
|
|
011 |
010 |
000 |
001 |
010 |
|
011 |
001 |
100 |
010 |
001 |
|
010 |
011 |
000 |
|
|
|
001 |
011 |
100 |
|
|
|
100 |
100 |
011 |
000 |
100 |
|
100 |
010 |
001 |
110 |
000 |
|
100 |
001 |
000 |
101 |
000 |
|
011 |
000 |
011 |
011 |
000 |
|
010 |
100 |
001 |
|
|
|
010 |
010 |
100 |
000 |
010 |
|
010 |
001 |
011 |
|
|
|
001 |
100 |
000 |
|
|
|
001 |
010 |
011 |
|
|
|
001 |
001 |
010 |
000 |
001 |
|
000 |
011 |
011 |
|
|
|
100 |
000 |
100 |
100 |
000 |
|
010 |
000 |
010 |
010 |
000 |
|
001 |
000 |
001 |
001 |
000 |
|
000 |
100 |
100 |
|
|
|
000 |
010 |
010 |
|
|
|
000 |
001 |
001 |
|
|
|
000 |
000 |
000 |
000 |
000 |
|
Доопределено: |
|||||
010 |
101 |
010 |
|
|
|
111 |
000 |
010 |
|
|
|
110 |
000 |
001 |
|
|
|
110 |
001 |
010 |
|
|
|
001 |
110 |
010 |
|
|
|
000 |
110 |
001 |
|
|
|
000 |
111 |
010 |
|
|
|
000 |
101 |
000 |
|
|
|
101 |
010 |
010 |
|
|
|
101 |
000 |
000 |
|
|
Построим карты Карно преобразованных функций.
y1 |
||||||||||||||
z1 |
||||||||||||||
z2 |
||||||||||||||
z4 |
0 |
* |
* |
* |
* |
* |
* |
* |
||||||
* |
* |
* |
* |
* |
* |
* |
* |
z6 |
||||||
z5 |
* |
* |
* |
* |
* |
* |
* |
* |
||||||
* |
* |
* |
* |
* |
* |
* |
* |
|||||||
1 |
0 |
* |
* |
* |
* |
* |
* |
|||||||
0 |
* |
* |
* |
* |
* |
* |
* |
z6 |
||||||
0 |
* |
* |
1 |
* |
* |
* |
* |
|||||||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|||||||
z3 |
z3 |
y1 = 26 v 356 v 123
y2 |
||||||||||||||
z1 |
||||||||||||||
z2 |
||||||||||||||
z4 |
1 |
* |
* |
* |
* |
* |
* |
* |
||||||
* |
* |
* |
* |
* |
* |
* |
* |
z6 |
||||||
z5 |
* |
* |
* |
* |
* |
* |
* |
* |
||||||
* |
* |
* |
* |
* |
* |
* |
* |
|||||||
0 |
0 |
* |
* |
* |
* |
* |
* |
|||||||
0 |
* |
* |
* |
* |
* |
* |
* |
z6 |
||||||
1 |
* |
* |
0 |
* |
* |
* |
* |
|||||||
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
|||||||
z3 |
z3 |
y2 = 4 v 23 v 126 v 256
y3 |
||||||||||||||
z1 |
||||||||||||||
z2 |
||||||||||||||
z4 |
1 |
* |
* |
* |
* |
* |
* |
* |
||||||
* |
* |
* |
* |
* |
* |
* |
* |
z6 |
||||||
z5 |
* |
* |
* |
* |
* |
* |
* |
* |
||||||
* |
* |
* |
* |
* |
* |
* |
* |
|||||||
0 |
0 |
* |
* |
* |
* |
* |
* |
|||||||
1 |
* |
* |
* |
* |
* |
* |
* |
z6 |
||||||
0 |
* |
* |
0 |
* |
* |
* |
* |
|||||||
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
|||||||
z3 |
z3 |
y3 = 4 v 56 v 135 v 123
Получили следующую систему функций:
y1 = 26 v 356 v 123
Y = y2 = 4 v 23 v 126 v 256
y3 = 4 v 56 v 135 v 123
Сложность реализации устройства в этом представлении составляет
L(Y) = L”(y1) + L”(y2) + L”(y3) + L(Z) + Lинв.z,
где L”(yi) - сложность представления функции yi без учета сложности реализации
z-функций и их инверсий, L(Z) - суммарная сложность реализации z-функций, а Lинв. - количество инверсий z-функций, встречающихся в представлении y1,2,3. Тогда
L(Y) = 7 + 8 + 8 + 15 + 5 = 43 (4)
оператора И, ИЛИ, НЕ, что на 30 операторов меньше, чем в (3).
Размещено на Allbest.ru
Подобные документы
Основные понятия алгебры логики. Дизъюнктивные и конъюнктивные нормальные формы. Сущность теоремы Шеннона. Булевы функции двух переменных. Последовательное и параллельное соединение двух выключателей. Свойства элементарных функций алгебры логики.
контрольная работа [345,3 K], добавлен 29.11.2010Полнота и замкнутость системы булевых функций. Алгоритм построения таблицы истинности двойственной функции. Класс L линейных функций, сущность полинома Жегалкина. Распознавание монотонной функции по вектору ее значений. Доказательство теоремы Поста.
учебное пособие [1,3 M], добавлен 20.08.2014Основные аксиомы и тождества алгебры логики. Аналитическая форма представления булевых функций. Элементарные функции алгебры логики. Функции алгебры логики одного аргумента и формы ее реализации. Свойства, особенности и виды логических операций.
реферат [63,3 K], добавлен 06.12.2010Основная функционально полная система логических функций. Законы алгебры логики в основной функционально полной системе и их следствия. Переместительный и распределительный законы. Закон инверсии (правило Де Моргана). Системы логических функций.
реферат [40,5 K], добавлен 17.11.2008Понятие алгебры логики, ее сущность и особенности, основные понятия и определения, предмет и методика изучения. Законы алгебры логики и следствия из них, методы построения формул по заданной таблице истинности. Формы представления булевых функций.
учебное пособие [702,6 K], добавлен 29.04.2009Составление таблицы истинности. Получение уравнений функций алгебры логики для заданных выходов. Реализация схемы логического автомата на электромагнитных реле РП-23, на диодной матрице. Реализация структурной схемы логического автомата, на микросхемах.
курсовая работа [862,4 K], добавлен 12.12.2012Изучение булевых функций. Алгоритм представления булевых функций в виде полинома Жегалкина. Система функций множества. Алгебраические преобразования, метод неопределенных коэффициентов. Таблица истинности для определенного количества переменных.
курсовая работа [701,9 K], добавлен 27.04.2011Логика - наука о законах и формах мышления, а основное понятие алгебры логики - высказывание. Основные понятия и тождества булевой алгебры. Изучение методов минимизации булевых функций. Метод Квайна, основанный на применении двух основных соотношений.
контрольная работа [178,2 K], добавлен 20.01.2011Элементы линейной алгебры. Элементы аналитической геометрии и векторной алгебры. Введение в математический анализ. Дифференциальное исчисление функций одной переменной. Дифференциальное исчисление функций нескольких независимых переменных. Интеграл.
методичка [90,5 K], добавлен 02.11.2008Обзор таблицы производных элементарных функций. Понятие промежуточного аргумента. Правила дифференцирования сложных функций. Способ изображения траектории точки в виде изменения ее проекций по осям. Дифференцирование параметрически заданной функции.
контрольная работа [238,1 K], добавлен 11.08.2009