Файл: Цифровые многозначные элементы и структуры учеб. пособие.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 10.07.2024
Просмотров: 143
Скачиваний: 0
целое |
число. |
Каноническое представление |
выходной функции |
х = |
|||||
«= ф (у) |
в системе Россера — Тьюкетта имеет вид |
|
|||||||
|
|
|
х =■ |
V |
^ Ф (<*)/«, Ы Ja2(у2) • • . Jam(у'), |
(4.59) |
|||
|
|
|
|
по всем а |
|
|
|
|
|
где а |
= |
(alt |
а 2, |
..., ат ), |
а, £ £*,. |
|
|
|
|
В системе теоретико-множественных операций получим |
|
||||||||
|
|
|
X ~ |
V |
(l/la l)0 (^а*)® |
• • • |
(Утат)° = |
|
|
|
|
|
|
по |
всем a |
|
|
|
|
|
|
|
= |
V |
-* ((yi<*l)6 (У.<*2)6 |
■ ■ ■ |
(Уп&т)6)а> |
(4.60) |
по всем a
где а = ср (alt a 2, a„,), а б £ Ek выбирают произвольно.
О , __ 1 _ _ 2
3
У)
. Ж Е
„ Ш — У З
|
т а |
• Iга |
|
|
|
Рис. 65. |
Схема |
преобразователя типа |
kx -*■ k при k = |
9 и |
|
= 3. |
|
|
|
|
|
Необходимо отметить, что функция х на каждом из наборов аргу |
|||||
ментов уи уг, |
у„\ принимает различные значения. Это |
приводит |
|||
к использованию в схеме преобразователя, |
построенного |
в |
соответст ■ |
вин с (4.59) или (4.60), /г^значного m-входового дешифратора. Дешиф ратор можно построить любым из известных способов.
119
С другой стороны, можно показать, что в системе теоретико-множе ственных операций рассматриваемый преобразователь может быть построен по более простой схеме согласно выражению
* = П M vv‘<ao) v (^•i)VVi(",) V ••• f o ( * i - l) ) v?i<e‘ “1)), (4.61) |
|
/=1 |
х при yt = у, |
где у, (ау) £ Ek — значения, которые принимает |
|
то есть у( (a.j) — это все буквы выходного алфавита, |
соответствующие |
при заданном кодирующем отображении всем входным словам, имею
щим на t-м месте букву у. |
|
= 3. Построим, согласно |
Рассмотрим пример. Пусть k = 9, |
||
(4.61), преобразователь типа kx |
k, обратный рассмотренному в пре |
|
дыдущем примере: |
|
|
* - «»,0)ov,v! V (9,1 )SV4VS V (9,2 ),V7V*) X |
||
X (<9,0)ov3v6 V <»,1>,V ‘ V7 |
V (9,2 )!vsv*). |
Схема этого преобразователя изображена на рис. 65.
Описанную методику построения алфавитных преобразователей легко распространить на случай избыточного кодирования, то есть
для k < kT. При этом можно несколько упростить их схемы. С другой стороны, очевидно, могут быть более простыми неизбыточные преоб
разователи, если |
k = k1 - k2... km. Например, при |
k = 6 (kt = 2, |
|
/?2 = |
3) преобразователь 6 -> 2 , 3 легко получить из |
преобразовате |
|
ля 9 |
3, то есть |
способы построения таких преобразователей очень |
мало стличаются от описанных.
§ 4.9. Синтез многозначных комбинационных сумматоров
Комбинационным сумматором называют схему, которая осущест вляет арифметическое сложение двух чисел X и Y -< N, где N — неко торое большое число. Такую схему можно построить как
n = [lo g * (V ]~ -£ f |
(4.62) |
однотипных параллельно соединенных блоков, структура которых показана на рис. 66. Здесь и далее будем пользоваться следующими обозначениями:
х и y £ E k —.поразрядные значения чисел X и Y\
z £ £ а = (0 , 1 }-^ перенос из младшего разряда сумматора;
с £ £ 2 —.перенос в старший разряд сумматора;
q = х + у (mod k), s = q -f- z (mod k), p и r £ £ 2
переносы, возникающие при сложении х с у и q с z. Функционирование отдельных схем Q, P ,R ,S и С одноразрядного сумматора описывает
120
ся таблицами 24—28, где k = 5. Прочерк в табл. 28 функции с (р, г) означает, что на соответствующем наборе эта функция может прини мать произвольные значения. Рассмотрим, как реализовать функции <7, р, s, г и с в некоторых функционально полных системах.
Пусть ху, х V у и Js (х) — операции системы Россера — Тьюкетта. Вопросы минимизации функций в этой системе рассмотрены в § 2.7. Однако функцию q (х, у) в классе дизъюнктивных нормальных форм существенно упростить нельзя [19]. Значительно лучшие результаты дает использование тождественных соотношений, спреведливость которых легко доказать на основе изложен xsf
ного в § 4.3:
Л (х) Л (У) V Л М Л (У) = J a (ХУ) Л (х V У). |
3, V |
|
|
(4.63) |
_____С р |
Л(х) у V xJ0 (у) = Л (ху) (х V у)> (4-64)
Л- 1 {х) у V xJк- 1 (у) = (ху) Л - 1 (х V У)>
|
|
|
|
|
|
|
|
|
|
(4.65) |
5 5 У $ |
1 ^ г~Л |
|||
|
|
|
|
|
|
|
|
|
|
|
Г |
||||
|
|
Jo(x V y ) J 0(xy) = |
J0(x \/у), |
(4.66) |
|
||||||||||
|
|
Л - 1 (х V У) Л -i (ху) = Л - 1 (ху), |
(4.67) |
Рис. 66. Блок-схема комбина |
|||||||||||
|
|
ционного сумматора. |
|||||||||||||
где |
а = is; |
b = |
i \J |
s\ |
i, |
s £ |
с с учетом соотношений (4.63) |
(4.07) |
|||||||
|
Выражения для |
q, |
p, |
r, |
s, |
||||||||||
имеют вид |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
q — (х \/ |
у) Jo (ху) |
V |
V Л (* V */) ( V (i + s) Л (ху)) у |
|
|||||||||
|
|
|
|
|
|
|
|
/ = |
1 |
\ S— 1 |
|
|
|
|
|
|
|
V |
(к — 2) Л -1 |
(ху) |
v Л -1 (X V У) (V ( '— 1) Л (ху)), |
(4.68) |
|||||||||
|
|
|
|
|
|
Таблица 24 |
|
|
|
|
Таблица 25 |
||||
|
|
|
|
У |
|
|
|
|
|
|
|
У |
|
|
|
|
|
0 |
1 |
2 |
|
3 |
|
4 |
0 |
1 |
2 |
|
3 |
4 |
|
|
0 |
0 |
1 |
2 |
|
3 |
|
|
4 |
0 |
0 |
|
0 |
0 |
0 |
|
1 |
1 |
2 |
3 |
|
4 |
|
|
0 |
0 |
0 |
|
0 |
0 |
1 |
к |
2 |
2 |
3 |
4 |
|
0 |
|
|
1 |
0 |
0 |
|
0 |
1 |
1 |
|
3 |
3 |
4 |
0 |
|
1 |
|
|
2 |
0 |
0 |
|
1 |
1 |
1 |
|
4 |
4 |
0 |
1 |
|
2 |
|
|
3 |
0 |
1 |
|
1 |
1 |
1 |
|
|
|
Я (*. У) |
|
|
|
|
|
|
Р (*. |
у) |
|
|
121
|
Таблица 26 |
Таблица 27 |
||
|
г |
|
Z |
|
I |
О |
1 |
0 |
1 |
0 |
1 |
|
|
|
0 |
0 |
0 |
||
1 |
1 |
2 |
0 |
0 |
<*\2 |
2 |
3 |
0 |
0 |
3 |
3 |
4 |
0 |
0 |
. 4 |
4 |
0 |
0 |
1 |
|
s (а, г) |
|
г (Ч. г) |
|
Таблица 28
г
О1
01
1—
с(Р, г)
|
р = if V J t (ху) V ( * р ) (* V р) V |
|
|
|||||||
|
|
|
\ /=[0,5*J |
|
|
|
|
|
|
|
|
|
V |
[0,5ft]—1 |
/ |
ft—2 |
|
\ \ |
|
(4.69) |
|
|
|
V Л (ху) ( |
V |
-J, (* V Р))). |
|
|||||
|
|
|
i=2 |
|
\s = f t- i |
|
) J |
|
|
|
S = Л (<7*) (9 V 2) V Л (?2) f V |
(*' + |
1) Ji (<7 V z) V ^ft- 2 (9 V *)) , |
(4.70) |
|||||||
|
|
|
|
r = /*_,(<7) 2, |
|
|
(4.71) |
|||
|
|
|
|
|
c = p \J r. |
|
|
(4.72) |
||
Для построения сумматора, согласно выражениям |
(4.68) — |
|||||||||
(4.72), требуется при к = 4 |
или |
k — нечетном З/г одновходовых и |
||||||||
[0,5 (2&2 + |
5/г) ] |
двувходовых элементов. При четном k >- 6 требуется |
||||||||
3k одновходовых и [0,5 (2k2 + 5&)] —- 1 двувходовых элементов. |
||||||||||
Включение в систему Россера — Тьюкетта операции х + |
1 (mod k) |
|||||||||
позволяет значительно упростить выражения для q и s |
|
|
||||||||
|
|
|
q =, |
\7 |
Ji (х V У) (ху + |
0. |
|
(4-73) |
||
|
|
|
s = |
?70 (z) V (q + |
1)-Mz). |
|
(4.74) |
|||
Чтобы построить сумматор по выражениям |
(4.69) и (4.71) — (4.74), |
|||||||||
требуется 3k одновходовых и 4& |
(при |
нечетном к >- 5) или |
4& — 1 |
|||||||
/при четном k ;> 6) двувходовых элементов. |
операцией |
|||||||||
Если в |
систему |
Россера — Тьюкетта, |
дополненную |
|||||||
х + 1 (mod k), |
включить операции |
|
|
|
|
|||||
|
|
1 |
при X > |
t, |
|
|
|
|
|
|
ft (х) |
= 0 |
при х С |
i, |
(/= 1 , 2 , ... , f t ^ l ) , |
|
|
122