<< Предыдущая

стр. 3
(из 5 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

бора:
2) {&, ? };
3) {?, ? }.
Русский математик Жегалкин показал, что любая булева функция
может быть представлена с использованием операций конъюнкции
(&) сложения по модулю 2 (?) и константы 1. Покажем, как извест-
ные функции набора 1) представить в виде декомпозиции функций
Жегалкина: ? A = A ? 1; A ? B = ? (? A? B) = (A ? 1)(B ? 1) ? 1 =
= AB ? A ? B ? 1 ? 1 = AB ? A ? B.
Поэтому следующим функционально полным (базисным) набором
будет набор функций Жегалкина:
4) {&, ? , 1 }.
Аналогично можно показать, что набор
5) {?, ? , 1} – базисный набор.
Выше было показано, что мажоритарная функция M(X, Y, Z) =
= XY ? XZ ? YZ. Если на один из входов, например Z, подать константу
1, то получим M(X, Y, 1) = XY ? X ? Y = X ? Y , а если на этот же вход Z
подать константу 0, то получим M(X, Y, 0) = XY. Поэтому получаем еще
два базисных набора:
6) {M, ?, 1};
7) {M, ?, 0}.
Когда говорят о “мажоритарном базисе” , то имеют в виду эти два
набора (или их объединение: {M, ?, 1, 0}), предполагая, что 1 и 0 реали-
зуются “без затрат”, а инверсия аргументов всегда присутствует, если
комбинационная схема подключается к триггерным устройствам (эле-
ментарным автоматам), которые имеют как прямой, так и инверсные
выходы.
На практике, как правило, используются базисные наборы, состоя-
щие только из одной функции (“штрих Шеффера” или “стрелка Пирса”):
8) {/};
9) {v}.
Набор 8) реализует функцию ? (XY) = XY . Инверсия аргумента мо-
жет быть получена так: ? X = ? (XX). Конъюнкция XY = ? (? (XY) =
= X Y = X Y X Y . Дизъюнкция может быть реализована так: X ? Y =

= ? (? X?Y) = X Y = X X Y Y .
15
Набор 9) реализует функцию ? (X ? Y) = X ? Y . Инверсия аргумента
может быть получена так: ? (X ? X). Дизъюнкция может быть полу-
чена так: X ? Y = ? (? (X ? Y)). Конъюнкция может быть получена так:
XY = (? X?? Y).
П р и м е р . Перевести в базис Шеффера и Пирса функцию, задан-
ную в дизъюнктивной форме:
F = A B ? A CD ? B D.
В базисе Шеффера функция будет иметь вид

F = A B AC D B D
В базисе Пирса функция будет иметь вид

F = A? B ? A? C ? D ? B ? D
Примеры для самостоятельной работы.
Представить в базисах Шеффера и Пирса следующие функции (при
необходимости предварительно упростить):
а) ABC ? BD ? AC ? ACD ;
=

б) XZ ? ZY ? ZP = .
1.9. Примеры реализации комбинационных схем
Редко задание на проектирование комбинационных схем формулиру-
ется в виде перечисления входных и соответствующих им выходных
наборов (таблиц истинности). Часто оно задается в виде описания ра-
боты.
П р и м е р 1. Построить однотактное устройство, реализующее сле-
дующий алгоритм работы.
На вход устройства подается 5-разрядный двоичный код (x1, x2, x3,
x4, x5).
На выходе вырабатывается 0, если число единиц в коде равно 0
или 1, и вырабатывается 1, если число единиц равно 4 или 5. Осталь-
ные случаи не предусмотрены (на остальных наборах можно про-
ставить “–”).
Построим диаграмму Вейча по данному описанию.


16
x3
x2
x1
– – 1 – – – – 0
– 1 1 1 – 1 – –
x5
– – 1 – – – – 0
x4
0 – – – 0 – 0 0

Выпишем решение при очевидном способе доопределения и пред-
ставим его в базисе Шеффера и Пирса:

F = x2 x3 ? x4 x5 = x2 x3 x4 x5 = x2 ? x3 ? x4 ? x5 .
Комбинационные схемы на несколько выходов строятся аналогич-
ным образом. Однако предпринимаются попытки провести совместную
минимизацию схем, реализующих отдельные выходные сигналы. При-
мерами таких схем могут служить различные преобразователи кодов.
П р и м е р 2. Построить однотактное устройство, преобразующее
двоичный код в код Грэя.
Выпишем таблицу истинности четырех разрядов кода Грэя.
x4 x3 x2 x1 y4 y3 y2 y1
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 1
0 0 1 1 0 0 1 0
0 1 0 0 0 1 1 0
0 1 0 1 0 1 1 1
0 1 1 0 0 1 0 1
0 1 1 1 0 1 0 0
1 0 0 0 1 1 0 0
1 0 0 1 1 1 0 1
1 0 1 0 1 1 1 1
1 0 1 1 1 1 1 0
1 1 0 0 1 0 1 0
1 1 0 1 1 0 1 1
1 1 1 0 1 0 0 1
1 1 1 1 1 0 0 0
17
Число диаграмм Вейча равно четырем, причем для y4 она триви-
альная (y4 = x4), а для остальных имеет следующий вид.
Для y1
x4
x3
y1 = x1 x2 ? x1 x2 = x1 ? x2 .
1 1 1 1


x2
1 1 1 1
x1


Для y2
x4
x3
y2 = x2 x3 x2 ? x3 = x2 ? x3 .
1 1
1 1
x2
1 1
x1
1 1

Для y3
x4
x3
y3 = x3 x4 ? x3 x4 = x3 ? x4.
1 1
1 1
x2
1 1
x1
1 1



1.10. Изображение комбинационных элементов
на функциональных схемах
Для изображения комбинационных элементов в различных базисах
используются следующие обозначения.

18
Изображение элемента “И”
&


Изображение элемента “ИЛИ”
1


Изображение элемента “И-НЕ” (Шеффера)
&


Изображение элемента “ИЛИ-НЕ” (Пирса)
1


Изображение элемента “НЕ”



Изображение элемента “?” (сумма по модулю 2)

?



Упражнение. Нарисуйте функциональные схемы двух устройств в
различных базисах, которые были синтезированы в подразд. 1.9.




19
2. БУЛЕВЫ ПРЕОБРАЗОВАНИЯ
ДВОИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

2.1. Постановка задачи
Пусть имеются две двоичные последовательности A(a1, a2, …, an) и
B(b1, b2, …, bn). При этом ai, bi ? {0, 1}, i = 1, 2, 3, …, n. Элементы
последовательности B будем получать булевым преобразованием пос-
ледовательности A, при этом bi будет результатом булевого преобразо-
вания, зависящего от ai и некоторых элементов из окружения ai. Мак-
симальное число аргументов булевой преобразующей функции F равно
N = 2n – 1. Так, для n = 3 N = 5; для n = 4 N = 7; для n = 5 N = 9.
Рассмотрим методы нахождения функций F.
2.2. Теорема о преобразованиях
двоичных последовательностей
Сформулируем теорему, на основании которой можно строить буле-
вы функции, преобразующиe одну последовательность в другую. Эта
теорема являeтся аналогом теоремы, доказанной в литературе1.
Теорема. Для того чтобы существовала булева функция F, преобра-
зующая произвольную последовательность А в произвольную последо-
вательность В, необходимо и достаточно, чтобы А была ненулевой пос-
ледовательностью. Число аргументов F не превышает 2n – 1.
Необходимость следует из того, что при нулевой последовательнос-
ти А все элементы последовательности В будут либо нулями, либо еди-
ницами, и в этом случае В не может быть произвольной последователь-
ностью.
Для доказательства достаточности построим часть таблицы истин-
ности функции F, в которой функция определена:

1
A?io E. E., Eaiaouaa I. A., Iineaeaa Y. N. Aaaioeaiua nenoaiu oi?aaea-
iey i?iiuoeaiiuie ?iaioaie: O?aa. iiniaea aey aoocia / EEAI. E., 1985. 144 n.
20
a1 a2 … an b1
a1 a2 … an b2
a1 a2 … an b3
……………………………………………
a1 a2 … an+1 bn

Если хотя бы один элемент последовательности А не равен 0, то все
наборы, на которых функция определена, будут различными, поэтому не
существует ни одной одинаковой пары наборов, на которой функция дол-
жна принимать одновременно значение 0 и 1.
П р и м е р . Пусть A (101), B (011). Функция F будет зависеть от
аргументов (ai – 2 , ai – 1, ai , ai + 1, ai + 2). Таблица истинности этой
функции (точнее, только та ее часть, на которой функция определена)
будет иметь вид

ai – 2 ai – 1 ai ai B
ai
+1 +2

1 0 1 0
1 0 1 1
1 0 1 1

Функция пяти аргументов задается на 32 наборах. Однако эта функ-
ция задана в примере всего на 3 наборах. На остальных 29 наборах
функция не определена и ее можно доопределить 229 способами. Диаг-
рамма Вейча этой функции будет иметь вид
ai – 2
ai – 1
ai

– – – – – – 0 –
– – – – – – – –
ai + 2
– – – – 1 – – –
ai + 1
– 1 – – – – – –


Доопределить и минимизировать данную функцию достаточно про-
сто: F = ai + 2 . Действительно, применив булево преобразование F к A,
получим B.
21
При длинах векторов A и B, равных n, булева функция будет зада-
ваться на n наборах, а на 2(2n-1) – n наборах функция будет не определе-
на. Доопределение и минимизация булевой функции не однозначны.
Определение. Два набора Ai и Aj длины n будем называть связан-
ными сдвигом, если при некотором сдвиге одного набора относительно

<< Предыдущая

стр. 3
(из 5 стр.)

ОГЛАВЛЕНИЕ

Следующая >>