Файл: Цифровые многозначные элементы и структуры учеб. пособие.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 10.07.2024
Просмотров: 154
Скачиваний: 0
Тогда |
при гп = |
г„_1 = |
zx = а, |
|
а |
(4.47) |
|||
Я = zt |
при z„ = |
zn—1 =. |
Z(+l — О, z,. =£ Й. |
Рассмотрим процесс синтеза функций (4.46) и (4.47) в функциональ но полной системе, включающей все константы, ft одноместных опе
раций |
\а при х =; /, |
|
|
|
|
|
|
! |
|
|
|
|
|
||
* _ |
(0 при х ф } , |
(/ = |
0 , |
1 , . . . . |
Л — 1 ) |
|
|
и две двухместные операции ху и х V |
|
удовлетворяющие условиям |
|||||
(2.42). С учетом введенных ранее обозначений получим |
|
||||||
Я = Пг? y b U |
V |
|
П |
г/ ) , |
(4.48) |
||
где |
/=1• ‘ |
' |
/=1 |
|
/= П—/+1 |
|
|
|
|
|
|
|
|
|
|
|
Zi = |
V х{у[\/ |
ь [ у |
x'ii |
V г/f )) • |
(4.49) |
|
|
|
/=о |
\/= 1 |
\р=0 |
|
|
|
Для реализации схемы сравнения многозначных кодов по этим
выражениям при ft > |
3 требуется 2n (ft + |
1) |
и п (5ft —- 1) — 1 дву |
|
входовых логических |
элементов. |
|
|
операции |
Введение вместо k одноместных операций х>двухместной |
||||
|
\а при х = у, |
|
|
|
|
[О при х ф у , |
|
|
|
позволяет несколько упростить выражение |
(4.49) |
|
||
|
Z; = хЬ V Ъ(V х{ (V |
|
. |
(4.50) |
Для построения схемы сравнения по выражениям (4.48) и (4.50)
при ft > 3 требуется п (5ft + 1) — |
1 двувходовых элементов. Во мно |
гих конкретных полных системах |
возможно дальнейшее упрощение |
выражений для Н и zc. Рассмотрим некоторые из них. |
(2.30) и (2.31). |
|
Пусть операции ху |
и х V у являются операциями |
|
Тогда |
V ь ((*?)" (х{ V У,)у‘ V У% |
|
Z, = |
(4.51) |
|
В этом случае для построения схемы сравнения по выражениям
(4.48) и (4.51) надо 15п — 1 двувходовых |
элементов. |
|
|
Если ху — шах (х, у), а = |
ft — 1, то |
|
|
z( = |
V b ((xt V у |
О- |
(4.52) |
Реализация схемы сравнения многозначных кодов в |
соответствии |
||
с выражениями (4.48) и (4.52)требует при f t> 3 10п — 1 двувходовых элементов.
114
Следует отметить, что существуют полные системы, в которых схе му сравнения многозначных кодов нельзя значительно упростить (например, модулярная система). В этом случае для упрощения схем необходимо вводить избыточность в полную систему. Один из способов введения избыточности состоит во включении в полную систему всех одноместных операций. Рассмотрим такую избыточную полную си стему, где х V у = х + у (mod 6), ху = х х у (mod 6), а = 1. В такой системе функцию zt можно представить в виде [13]
= xb v Мл ), |
(4-53) |
|||||
где |
(а при Р1ф 0 , |
|
||||
|
|
|||||
^ |
[0 |
при Pi = 0. |
|
|||
Pi = u (*,) и ifi) у |
F(xt \/ fi) (U (Xi) V u (fi)), |
|
||||
11 при |
x > |
[0,56], |
|
|||
U(x) = {О при |
x < |
[0,56], |
|
|||
f t ~ k — 1 — yh |
|
|||||
1 |
при |
x C |
[0,56] — 1, |
|
||
F(x) = 0 |
при |
x > |
10,56] — 1. |
|
||
Здесь [0,56] — ближайшее к 0,56 большее целое число. Для |
пост |
|||||
роения схемы сравнения в соответствии с выражениями (4.48) и (4.53)
при 6 > |
3 требуется 5га одновходовых и 12га — 1 двувходовых эле |
||||||
ментов. |
|
|
|
|
|
|
|
|
Сравним сложность (то есть число одновходовых и двувходовых |
||||||
элементов) L (6 , га) реализации схем сравнения многозначных кодов |
|||||||
при различных |
6 : |
|
|
|
|
||
|
|
|
L (6 , га) = raLj (6) + L2 (га), |
|
|||
где |
(6) — сложность |
схемы, |
реализующей функцию |
г{ (хг, у{), |
|||
L2 (га) — сложность схемы, реализующей функцию Я (zlt |
z2, ..., z„). |
||||||
Если X и К < |
IV, где N — некоторое большое число, то |
|
|||||
|
|
|
М * . . ) - ё г М * > |
+ 1 . (•!? •)• |
|
||
|
При |
этом предполагается, что сложность логических |
элементов |
||||
не зависит от 6 . Так как L2 (га) является линейной функцией от га, |
|||||||
то |
L (6 , га) можно представить |
как |
|
|
|||
|
|
Ц 6 , ra) = ^ f |
(Ak + B) + C ^ ^ L ( A k + B ) . |
|
|||
|
Если |
для реализации |
функций zt |
используют выражения (4.49) |
|||
и (4.50), |
то В » |
0. Поэтому, при й > |
3 и постоянном N, L (6 , га) уве |
||||
личивается с ростом 6 (табл. 23). Если же функции zt реализуются согласно выражениям (4.41) — (4.53), то А = 0, следовательно, в
115
этом случае сложность схемы сравнения уменьшается с увеличением k и может быть проще соответствующей схемы, работающей в двоич ном структурном алфавите (табл. 23).
Таблица 23
Формулы |
|
|
|
L (к, п )/1 п |
к |
|
|
|
|
|
|
к |
|
|
|
|
|
ДЛЯ |
|
|
|
|
|
|
|
|
*< |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
4.49 |
20 |
21 |
22,5 |
24 |
25,7 |
27,5 |
29,3 |
31 |
4.50 |
14,5 |
15,2 |
16,1 |
17,3 |
18,6 |
19,7 |
21 |
22,2 |
4.51 |
13,6 |
10,9 |
9,3 |
8,4 |
7,7 |
7,2 |
6,8 |
6,5 |
4.52 |
9.1 |
7.2 |
6,2 |
5,6 |
5,2 |
4,8 |
4,5 |
4,3 |
4.53 |
15,5 |
12,3 |
10,5 |
9,5 |
8,8 |
8,2 |
7,8 |
7,4 |
Ьа
'/0-Н рЕКЯ
f c s -
I I
1
I
у л Ч
ш
I
I
I
1I
у»0*-! -
!---------------------------------------- |
J |
а * |
Рис. 63. |
Схема сравнения при п = |
3. |
ш -
№
Пример построения схемы сравнения по выражениям (4.48) и (4.52) при п = 3 представлен на рис. 63. Здесь символы \J, со и • обозначают элементы, реализующие соответственно операции х \J у,
Xй и ху.
116
§ 4.8. Преобразователи Л-значных кодов
При построении устройств для обработки информации иногда необходимо информацию, заданную в /г-значном алфавите, представить в /г^значном алфавите. Для этого используют так называемые алфа витные преобразователи, осуществляющие взаимно однозначные кодиру ющие отображения. Одним из примеров таких преобразователей явля ются устройства, позволяющие производить обмен информацией между регистрами на многоустойчивых элементах и запоминающими устройствами на элементах сдвумя устойчивыми состояниями. Приме нение преобразователей необходимо, когда оптимальное число k устой чивых состояний многоустойчивых элементов не совпадает с оптималь ным числом k0 букв структурного алфавита комбинационной схемы
(§ 4.1).
Задача синтеза алфавитных преобразователей формулируется сле дующим образом: построить схему, в которой любому сигналу на ее входе, соответствующему определенному элементу из множества Ек, ставится в соответствие конечная совокупность выходных сигналов. Каждый из этих сигналов однозначно соответствует определенному элементу из множества Ekt = {0, 1, ..., k±— 1}, Ekt cz Ek.
Необходимо отметить, что алфавитный преобразователь реализует
многозначные функции f (х) |
£ Е^, в то |
время |
как |
аргументы этих |
функций хъ х2, •••, хп £ Eh. |
Поскольку |
Е с: |
Ек, |
такие функции |
можно считать определенными не на всех наборах своих аргументов и синтезировать их известными методами.
Рассмотрим преобразователи типа k -> kv
Пусть k = k™, то есть рассматривается преобразователь fe-знач- ного алфавита в /г^значный, осуществляющий неизбыточное кодиро
вание. |
Каждой букве х £ Ек соответствует упорядоченная последова |
||
тельность т букв уъ у2, .... ут £ £*,. |
|
||
Предс авим yt как ^-значные функции yt (х). |
форма функции |
||
В |
системе |
Россера — Тьюкетта каноническая |
|
Hi (х), |
(i = 1 , |
2 , .... т) имеет вид |
|
|
|
yi(x)= V yi(s)Js(x). |
(4.54) |
|
|
s=0 |
|
В системе теоретико-множественных операций эта же функция |
|||
может |
быть представлена как |
|
|
|
|
УсМ = V (sxp{s\ |
(4.55) |
|
|
s=0 |
|
Объединяя в каждом выражении члены с одинаковым значением
117
yt (s) |
= |
|
ft в группы по «1 |
членов, |
можно представить |
выражения |
|||||||||
(4.54) |
и (4.55) |
соответственно в виде |
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
yi{x) = |
V |
(ft V |
Л(л,(,о W ), |
|
|
|
(4.55) |
||
|
|
|
|
|
|
|
h= 1 |
\ |
<=1 |
/ |
|
|
|
|
|
|
|
|
|
|
|
№(*)— |
*i-l / |
г |
|
\Л |
|
|
|
(4.57) |
|
|
|
|
|
|
|
V |
V S(^. |
0*1. |
|
|
|
||||
|
|
|
|
|
|
|
Л=0 \<=1 |
|
/ |
|
|
|
|
||
где s (ft, |
/, |
0 |
определяют из уравнений ft = yi(s(h, |
t, i)), |
a r = |
~r~. |
|||||||||
|
|
|
1 |
|
|
|
|
|
|
|
При построении |
«1 |
|||
|
|
|
|
|
|
|
|
|
|
преоб- |
|||||
|
|
|
|
|
V п£<?*| V Г- ! |
|
|
|
разователей, согласно вы |
||||||
|
С |
|
|
|
|
|
|
|
|
ражению |
(4.56), |
требуется |
|||
|
|
|
|
-@Г |
|
|
|
меньше элементов, чем при |
|||||||
X |
|
- |
l |
b |
|
|
|
|
использовании |
выражения |
|||||
|
|
|
-ф |
V |
|
|
(4.57), так как при этом вы |
||||||||
|
|
-------- > |
|
|
|
|
|
падает участок схемы, свя |
|||||||
-------------------------- |
|
|
|
|
занный |
с ft = |
0. |
Однако |
|||||||
-> -н — I |
|
|
|
|
|
|
|
выражение (4.57) |
допуска |
||||||
|
|
|
|
|
|
|
ет дальнейшее упрощение и |
||||||||
|
|
- L J p |
|
|
|
|
УгЩ2} |
может быть |
приведено к |
||||||
|
|
|
|
|
|
|
|
|
|
|
виду |
У‘ {х) = |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
= V l * ( V s(ft. t. |
0 |
|||
f e r n f |
^ Г 7 | |
|
|
|
|
|
|
Л=0 \ |
\/= 1 |
|
|
(4.58) |
|||
|
|
|
|
|
|
|
|
|
|
||||||
|
|
Схема преобразователя типа k -*■ |
|
|
|
|
|
||||||||
Рис. 64. |
при |
Пример построения пре |
|||||||||||||
k = 9 и |
|
= |
3. |
|
|
|
|
|
|
образователя |
при |
ft = 9, |
|||
веден на рис. 64. |
Каждую цифру i |
|
|
3, согласно (4.58) .при |
|||||||||||
£ £ 9 преобразователь представляет |
|||||||||||||||
в троичной системе счисления |
|
|
|
|
|
|
|
|
|||||||
|
УЛх) = (* (0 |
V 3 V 6))° V (*0 |
V 4 V 7))1 V (*(2 V 5 V 8))2, |
||||||||||||
|
у»(х) = (х(0 V 1 V 2))° v (JC(3 V 4 V 5))1 v (*(6 V 7 V 8))2. |
||||||||||||||
Рассмотрим преобразователи типа ftx -> ft, предназначенные для |
|||||||||||||||
преобразования |
нескольких |
ftj-значных |
функций |
уъ у2, |
.... ут на |
||||||||||
входе в одну ft-значную выходную функцию. Таким образом, преобра зователи типа ftx -> ft осуществляют кодирующее отображение, обрат
ное рассмотренному выше. По-прежнему считаем ft = ft” ,, где т —
118