книги из ГПНТБ / Цифровые многозначные элементы и структуры учеб. пособие

* = П 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*).

разователи, если

k = k1 - k2... km. Например, при

k = 6 (kt = 2,

/?2 =

3) преобразователь 6 -> 2 , 3 легко получить из

преобразовате­

ля 9

3, то есть

способы построения таких преобразователей очень

n = [lo g * (V ]~ -£ f

(4.62)

Л (х) Л (У) V Л М Л (У) = J a (ХУ) Л (х V У).

3, V

(4.63)

_____С р

(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

Я (*. У)

Р (*.

у)

р = 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 ) ,

то справедливы

тождественные соотношения

1 (V -М р )) =

Мр),

(4-75)

ft (х) fi (У) V ft (х) ft (У) =

fa (Ху) fb (х V У),

(4.76)

где а = 17; b =

i \] /; I, /

=

1 ,

2 ,

ft — 1 .

В справедливости их легко убедиться путем непосредственной

проверки. С учетом (4.75)

и (4.76) получим при нечетном ft

0.5(*—1)

Р =»

У

ft (ху) fk-i (X V у)

и при четном ft

1

0.5(*-2)

V

Р

= /о ,5ft (* Р )

(V

ft (ХУ) fk-i (X V Р ).

щ х\ = f1

ПРИ

* < [0,5ft] — 1,

(0

при х > [0,5ft] — 1

позволяет записать выражение для р в виде

Р = h 0,5*] (ху) V

/[0,5*j (х V У) и (Я)-

Используя это

выражение,

а

также

выражения

(4.71) — (4.74),

можно построить

сумматор из

2 ^ + 3 одновходовых

и 2k +

6 дву­

входовых элементов (k > 3).

(2.30) — (2.32). В [1]

пока­

Рассмотрим теперь систему операций

зано, что для реализации функции х +

у (mod k) требуется 2k — 2

Р =

W -')(*'“')( V (У1 4 ) (у'4

) ) ,

i=1

\i=k-t

J

s = qz1 V qxz,

r = z(q2) (q2),

c = p \ J r,

требуется еще 3

одновходовых и 5ft — 1 двувходовых элементов.

Система,

включающая

операции х + у (mod ft)

и (2.30), а также

константы 0,

1,

....

ft — 1, функционально полна (§ 2.4). Поскольку

где х 2 — хх, то для построения

сумматора при k > 3 необходимо

иметь 7k — 5 двувходовых элементов.

В модулярной системе операций при простом k схемы Р и R можно

строить по выражениям

Р =

/ \ у—о

1=1 \ /=о

г = гft-., (q).

В этом случае для построения

сумматора при k > 3 требуется

2k одновходовых и 2k + 2 двувходовых элементов.

Включение в рассматриваемую систему операций

xt = j 1 при х = t,

[О при х ф 1 ,

(i = 1 , 2 ,

. . . , k —. 1)

дает возможность представить функции р и г

как

р = хук (х +

у),

непустое (например, к (х) — 2х + 2.

При k = 5 и k = 7 всегда

можно найти такие функции / (х), <р (х)

и ф (х), для которых

/х (х) =

J1 при хф О ,

[О при х = О,

ф(х) =

2

при х£

{0 , 2 },

О при х£

{0 , 2 },

ф (х) =

х + 1 (mod k).

В общем случае при любом k справедливо выражение

P = fi(U (х) U(y) + F(x + у) fx (U (х) + U (у))),

где, например,

1

при х >

[0,5/е],

О

при х <

[0,5/г],

F(x) = 1

при х < [0,5^] — 1,

О

при х>[0,5&] — 1 .

ного сумматора требуется минимум оборудования

[11].

Сложность

n-разрядного сумматора может быть оценена по

числу L (k, п)

логических элементов, необходимых для его построения

L (к, п) = пЬ (к, 1) = [log, N] L(k, 1)

L (к,

1).

М М ) = - ^ - .

(4.77)

нельзя построить из элементов, число

которых

меньше п (Ak +

В),

где А и В постоянные данного базиса. Так как величина А «

7

9,

то при реализации сумматора в таких

базисах

оптимальное

k — 2 .

Заметим,

что

применение

симметричного

кодирования цифр

{— t, — t +

1 , ...,

—1 , 0 , 1 , ...,

t — 1 , t), где

k = 2t + 1 , или дру­

В многотактной схеме

(рис. 67)

каждый разряд одного из сомножите­

Сумма частичных произведений

лей X и Y < N, где N — некоторое

большое число,

поочередно управляет

Рис. 67. Структура

многотактной

параллельной обработкой всех

п раз­

множительной схемы.

рядов другого

сомножителя.

Умно-

П

П

жение X =* ^

на Y =

V уft1- 1 выполняется за п тактов. Здесь

i= 1

2, ...,

(=i

X

и Y.

xt, У{ £ Ek, (i = 1 ,

п) — количество разрядов чисел

Однотактная множительная схема осуществляет параллельную

обработку всех разрядов обоих сомножителей (рис. 68, п =

3).

но блоками

U и W. На рис.

69 пока­

заны

связи

между блоками U,

W,

Q,

Р, S,

R

и С внутри узлов

А

и

В

(рис.

67

и

68), первый из

которых

j (лл а (« при x = s,

а ф О,

и — Ji (х) у V V Ji (х) ( s V

(i х S) Js (y) j ,

ixs^to

'

= V Jt (x)

(

V

(i. s) Л (уЛ .

,=!

l-[4]

J

q =

xJ0(y) \f J0(x) у \J

\j J( (x) (

V

(t + s)

(г/)

i= l

I

s= l,

\H ^ 0

P = 1 (V J i (X) (sV; Л (</))) ,

где t X s =

i

X s (mod ft), i +

s = (mod /г). Блоки S,

R

и С строят

согласно выражениям (4.70) — (4.72). В этом случае для

построения

многотактной

и однотактной множительных

схем требуется соответ­

что

система

уравнений

ху = Ь,

х У у — с,

где

b =

is;

с =

i

\J

s; i,

s £

Ek,

при любых i

и s имеет только два

решения

(t,

s)

и

(s,

t),

то

справедливо тождественное соотношение

j i

(х) Jt (У) У J, (X) Ji (у) — JЬ(ху) Jc(x V

У)-

С учетом этого соотношения выражения для и и w имеют вид

и =

Ji(x) у У xJx (у) У У

Л (х У у) ( У

(i X s) Js (ху)

1=2

\s= 2

ft-1

/

i

ч

w = У Ji(x У у)

V

wО, s) Js(**)) ,

<=р

- [ 4 ]

/

где p =

[J^ft].

Остальные

функции

реализуются

по выражениям

(4.68) — (4.72).

Для

построения многотактной и однотактной множи­

тельных схем при ft >• 3

требуется соответственно не более п (4,5ft2 +

+ 7,5ft + у — а — р —

0,5а2 + 21) — 1,25ft2 — 4,75ft — 0,5у + а —

— 10 и п2 (4,5ft2+ 7,5ft + у — а — р — 0,5а2+ 21) — п (2,5ft2 +

9,5ft -f-

+ у — 2а +

20) +

3 элементов, где у = [0,5 (ft — 1)].

Введение

избыточности

включением в полную систему всех одно­

местных

операций

(§ 2.9)

позволяет значительно упростить

схемы

в такой

системе.

и =

к—1

w =

к—\

Ji (х) w (г, у),

(4.78)

V Ji (х) 11 ('. У),

V

i= l

(=2

к—1

-М*) (А */) V

(«/),

Р =

к—\

q = V

V J Л х) р (А г/),

4=1

/=1

s = qJ0(z) V Ji(z)s (q,

1).

Р — fl (/[0.5А] (х) f [0,5ft] (у) V

\J h { x \ J

у) f l (A0,5*] ( X )

V Ao.s/e] («/))). (4'79)

ft (x)

[1

при x > t ,

1.0

при x < i,

(i= 1, [0.5Л]),

h {x) = j 1

при x <

[0,5£] — 1,

0

при x > [0,5/e] —. 1,

удобно строить блоки U n W совместно (рис. 70),

Рис. 70. Структура управ­

причем и образуется сложением х самого с со­

бой у раз, а сумма всех переносов, возникаю­

ляющей схемы.

щих при этом,

равна до.

Управляющая схема реализует k ■ 1 функций

dt = x fi

(у)),

(i =

1 , 2 ,

...,

k — 1).

Блок R строят согласно выражению (4.71). Для построения много­

тактной

и однотактной множительных схем

соответственно

надо

13kn — 14 и

13&п2 — 28 п +

3 элементов.

В модулярной системе со всеми одноместными операциями для

блоков U, Q, S, С требуется

по одному элементу, а блоки R,

W и Р

строят согласно (4.71),

(4.78)

и (4.79). Следовательно, для многотакт-

9

896

129