Устройство для генерации троичного кода с постоянным количеством «нулей»

 

О Il И С "А" Н" И"Е

ИЗОБРЕТЕНИЯ

Савв Советских

Социалистических

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Зависимое от авт, свидетельства ¹

Заяьлено 14Х.1968 (№ 1241085/18-24) с присоединением заявки №

Приоритет

Опубликовано 10.IX.1969. Бюллетень № 28

Дата опубликования описания 4Х.1970

Кл, 42m>, 7I00

21ат, 36/24

МПК G 06f

Н ОЗК

УДК 681.326.35(088.8) Комитет по делам изобретений и открытий при Совете Министров

СССР

Автор изобретения

А. А. Давыдов

Заявитель

УСТРОЙСТВО ДЛЯ ГЕНЕРАЦИИ ТРОИЧНОГО КОДА

С ПОСТОЯННЫМ КОЛИЧЕСТВОМ «НУЛЕЙ»

Устройство относится к области вычислительной техники и телемеханики.

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

Однако известные устройства сложны и не позволяют генерировать троичный код постоянного веса.

Предложенное устройство отличается тем, что оно содержит блок переписи массива ненулевых символов и переключатель управления записью первого символа «два», причем первая группа выходов блока выделения граничного разряда преобразуемой части комбинации соединена с первой группой входов блока переписи массива ненулевых символов, вторая группа входов блока переписи массива ненулевых символов соединена с выходами ненулевых символов троичного регистра, выходы блока переписи массива ненулевых символов подключены ко входам записи троичного регистра со сдвигом, вторая группа выходов блока выделения граничного разряда преобразуемой части комбинации соединена с первыми входами вентилей перестановки, вторые входы вентилей перестановки подключены к выходам троичпого регистра, выходы вентилей перестановки соединены со входами троичного регистра, выходы ненулевых символов троичного регистра со сдвигом соединены через вентили стирания массива ненулевых

5 символов и вентили записи сдвинутого массива ненулевых символов со входами троичного регистра, выходы переключателя управления записью первого символа «два» соединены со входами записи символа «два» троичного ре10 гистра, выходы троичного регистра со сдвигом непосредственно и через переключатель длины кода подсоединены к одной группе входов блока определения конца сдвига, вторая группа входов блока определения конца сдви15 га соединена с выходами троичного регистра, входы одной группы элементов «И» через элементы «НЕ» соединены с выходами символа

«нуль» i-10 разряда троичного регистра (i + 1) -го разряда троичного регистра со

20 сдвигом, входы другой группы элементов «И» соединены с выходами символа «два» i-го разряда троичного регистра и (i+ 1)-го разряда троичного регистра со сдвигом, выходы всех групп элементов «И» соединены со вхо25 дами соответствующих элементов «ИЛИ».

Это позволяет упростить устройство и расширить его функциональные возможности.

На фиг. 1 показана блок-схема предложенного устройства; на фиг. 2 — функциональные

30 схемы и связи блоков 1 — б и 10.

251931

60

Устройство содержит троичный регистр 1 для запоминания кодовой комбинации, выходы которого являются выходами устройства, троичный регистр со сдвигом 2, предназначенный для сдвига массива ненулевых символов или массива символов «2», блок 8 выделения граничного разряда преобразуемой части комбинации для разделения комбинации на две части, одна из которых преобразуется при переходе к следующей комбинации, а другая не преобразуется, блок 4 переписи массива ненулевых символов для переписи массива ненулевых символов или массива символов

«2» из регистра 1 в регистр со сдвигом 2, блок 5 определения конца сдвига для фиксации момента, когда сдвиг массива ненулевых символов или массива символов «2» закончен, вентили перестановки б, предназначенные для перестановки значений в разрядах К и (К + 1) регистра 1 (в том случае, когда К-й разряд является граничным разрядом преобразуемой части комбинации), вентили 7 стирания массива ненулевых символов для записи символов «О» вместо массива ненулевых символов и для записи символов «1» вместо массива символов «2», вентили 8 записи сдвинутого массива ненулевых символов для переписи сдвинутого массива из регистра сдвига 2 в регистр:1, схему управления 9 для выработки управляющих и тактирующих импульсов, переключатель 10 длины кода для задания длины генерируемого кода и переключатель 11 управления записи первого символа «2», предназначенный для записи символа «2» в разряд (n — т+ 1) регистра 1, (где т — длина генерируемого кода).

Троичный регистр 1 имеет ячейки 12) — 12„, а троичный регистр 2 — ячейки 18 — 18„ (каждая ячейка регистров,l и 2 имеет выходы символов «О», «1», «2» и входы записи символов «О», «1», «2») .

Если в ячейке регистра 1 или 2 записан символ i, то на выходе символа «единица», а на остальных выходах — «нуль».

В разряды 14 — 14„q блока 8 выделения граничного разряда преобразуемой части комбинации входят соответственно схемы сравнения 15i — 15 и логические схемы

1б — !ба †1

Логические схемы lб имеют первые 17 —

17,, вторые 18) — 18n I и третьи 19,—

19„> выходы. (На выходах 17„18, и 19 реализуются соответственно логические функции + а

fi = fn р %+

i+I 1

f1s = f13 (pi Ai+I о g+y

gi Xi+ iVfis (%+, о

Где — Хс ь Xi i — значения сигнала на выходе символов «О» («1») ячейки 12i >, нр, — значение сигнала на выходе схемы

45 сравнения (5,, причем равенство — — 1 оь начает, что число, записанное в ячейке 1= „ больше числа, записанного в ячейке !2 i).

Блок 4 переписи массива ненулевых символов содержит р аз ряды 20 — 20„.

Блок 5 определения конца сдвига содержит схемы «ИЛИ» 21, 22, 28, первую группу логических схем «И» 24, — 24„ i и вторую группу логических схем «И» 25, — 25„ i.

Устройство содержит также логические схемы «НЕ» 2б — 2б„и 27) — 27„, двоичный триггер 2I8 с раздельными входами и вентили

29 — 29„, 80 — 80m 1, 81 — 81, ь 82g—

32„, осуществляющие перестановку.

Перед началом работы устройства переключателем 10 длины кода выход символа «О» ячейки 18„m, > через схему «НЕ» 27, + подсоединяется ко входу логической схемы

«И» 24О (n — длина генерируемого кода), Затем переключателем 11 записи первого символа «2» выход 88 схемы управления 9 подсоединяется ко входу записи символа «2» ячейки

12,+ . После этого в регистр 1 записывается комбинация О ... О 1 ... 1 О ... О, где

n — т m — f

1 — число символов «О» в генерируемом коде.

Регистр 2 и триггер 28 обнуляются. Затем на вход 84 схемы управления 9 поступает входной сигнал, и устройство начинает генерировать кодовые комбинации в порядке, указанном в таблице на примере пятиразрядного троичного кода, каждая комбинация которого содержит 1 = 2 символа «О».

Таким образом, и-разрядный троичный код, каждая комбинация которого содержит 1 символов «О», генерируется группами. Число этих групп равно n — 1+ 1. При этом группа представляет собой троичный код постоянного веса, т. е. код, каждой комбинации которого соответствует один и тот же вектор веса (е, d, где е — число символов «1» в комбинации, а d — число символов «2»). Вес комбинации первой группы (и — t, О), второй группы— (и — t — 1,1),, (и — t + 1) -й группы (О, и — t). Группы генерируются подгруппами из С» комбинаций с одинаковым взаимным расположением ненулевых символов.

Подгруппы генерируются в порядке убывания чисел, соответствующих взаимному расположению ненулевых символов для каждой подгруп пы. Комбинации в под группах также генерируются в порядке убывания соответствующих им чисел, для чего каждая комбинация разделяется на две части, правую (разряды К вЂ” n), которая преобразуется при переходе к следующей комбинации данной подгруппы, и левую (разряды 1 — (К вЂ” 1), которая не преобразуется при этом переходе. Такое разделение сделано в таблице для подгрупп (1 и 2)..

Граничным разрядом преобразуемой части комбинации при генерации всех комбинаций одной подгруппы является разряд К, удовлетворяющий условиям

О

Р:1, о х к

v 2

Ю хх о

Ф х х х <фо»

М х р IL о

Р х

М в

1о о а о

И

I_#_ х х

Ю

k( о

z к

v 2

Ill

IIl х х х

Ю

Х CU х х сО 1 с0 х

Ф о

Р. х й

CJ о р о

М х » сч х

1 о О х

v х аО х

Ю о о х х

О х М

»о йз v хо

v + р» III охЦ оо о,Ш ( х wv

>аI-о о в к < II» V

2 о - х ххох

Ръ o (»

> v

Ill х х о

1» оЕ

О х х

1 х х х х

О) \о о

» х х »

Q (» о ъ, а

Г» о о х2

А1 1

А11

А1" з

А1 1

360

111 100

1110 10

11 1001

1101 10

354

352

336

1111 (40) 111100

111100

ООШ1

603

5.97

595

2111 (67) 579

577

571

525

523

517

499

201

199

193

175

067

002111

211100

441

121100

1211 (49) 2.2

А2 2

А2.3

049

1 21100

001211

112100

387

1121 (43) 2.3

А2.3

А2.4

043

11 2100

001121

111200

379

1112 (41) 2.4

А2. 4

А3.1

211100 шг00

001112

684

221100

2211 (76) А"

2 21100

076

002 211 (4,0) 1. 1 (3 1) 21

А1 1

А 2.1

А2.1

А2 1 з

А2 "

4 д2.1

А21 б

А2 1

A2 1 в

А2 1

А2,1

А2.1

А2 1

2.1

А1з

2.1

А14

2.1

А15

А2 2

КОДОВАЯ

К ОМ ВИН AU)4 Я

211 100

2110 10

21 1001

2101 10

210 101

2 10011

2011 10

201 101

20 1011

200111

0211 10

021 101

02 1011

0 20111

Таблица

АЭ.2

630

212100 (2.2) 3.2

2121 (70) АЭ. 2

AЭ. Э

070

1 21 2100

002121

612

211200

А3.3

А3.4

1 гпг (68) 068

002112

122100

211200

3.3

468

А3.4

АЭ 5

1221 (52) 052

001221

1г 2100

3.4

450

121200

А3,5

АЭ. 6

050

001212

1 1 21200

1212 (50)

1222 (44) 3.5

396

112200

А3.6

А4Л

00пгг

112200

1 221100

222100

711

2221 (79) 4.1

А4 1

А4,2

002221

221200

079

1 22 2100

693

2212 (77) 1.3 4.2

А4.2

A4 Ý

002212

212200

077

1 2 21200

639

2122 (71) 0

002122

122200

071

А4.3

А4 4

212200

1222 (53) 4.4

001222

053

1 122200

А4. 4

А5.1

1 222100

222200

720

2222 (80) 5.1

002222

080

222200

5.1

1 222200 а) Х,=О; 0 б) Х,+1= 1; в) среди разрядов (К+ 2) и нет ни одной пары разрядов, удовлетворяющих условиям а) и б).

В разрядах К+2 —:n,ïðåooðàçóåìîé части комбинаций либо записаны символы «0» (A1, A1 ), либо есть ненулевые символы, 1.1 2.1 расположенные массивом в конце комбинации (Аэ, А1о ).

Преобразование правой части комбинации (разряды К вЂ”:n) при генерации всех комбинаций одной подгруппы заключается в перестановке значений в разрядах К и К+ 1 и сдвиге влево массива ненулевых символов (если он существует) вплотную к разряду К+ 1, при

5 этом первый символ массива занимает разряд К+2. При сдвиге освободившиеся справа разряды заполняются символами «0». Для этого на выходе M схемы управления 9 вырабатывается импульс опроса, поступающий

10 на вход разряда 14, 1 блока 8 выделения граничного разряда преобразуемой части комбинации. Импульс опроса распространяется по цепям переноса этого блока, появляясь пооче251931

9 редно на выходах 17 -ъ 17л — 2 и 17m — 1 до тех пор, пока не дойдет до двух ячеек 12» и 12, i, в первой из которых записан ненулевой символ, а во второй — нулевой символ.

После этого на выходе 19„появляется импульс, а перенос дальше не распространяется.

Импульс с выхода 19„поступает на вход вентилей 80„, 81„29„+ > и 82„+ . Вентили 80к и 81„открыты сигналом с выхода 8á схемы управления 9. В ячейку 12,+> записывается содержимое ячейки 12»; а в ячейку,12, — содержимое ячейки 12,+>, что соответствует перестановке значений в разрядах К и К+ 1.

Импульсы переноса с выходов 17» i, 17 г, °, 17„+ и импульс с выхода 85 схемы управления 9 поступают в блок 4, связанный с выходами регистра 1. Массив ненулевых символов в конце комбинации (если он существует) переписывается из регистра 1 в регистр 2.

Затем на выходе 87 схемы управления 9 появляется импульс, который через вентили 7 стирания массива ненулевых символов, управляемые выходами регистра 2, записывает символы «О» в ячейки регистра 1::. При этом ячейка 12, обнуляется, если в ячейке 18; записан ненулевой символ, что соответствует записи в регистр 1 символов «О» вместо массива ненулевых символов. Если массив ненулевых символов существует, то на выходе 88 блока 5 определения конца сдвига (выход схемы «ИЛИ»

28) сигнал равен «1», Этот сигнал поступает на вход 89 схемы управления 9,,на выходе 40 которой появляются импульсы, поступающие через вход 41 регистра 2,на шину сдвига.

Начинается сдвиг массива ненулевых символов влево. Как только левый разряд массива ненулевых символов будет записан в ячейку

18,+д, срабатывает схема «И» 24« (так как в ячейке 12 после перестановки значений в разрядах К и К+ 1 записан ненулевой символ.

На выходе схемы «ИЛИ» 21 (выход 42 блока определения конца сдвига) появляется сигнал «1», который поступает на вход 48 схемы управления 9 и прекращает подачу импульсов сдвига.

Затем на выходе 44 схемы управления 9 появляется импульс, который через вентили 8 записи сдвинутого массива ненулевых символов переписывает сдвинутый массив ненулевых символов из регистра 2 в регистр 1. Очередная комбинация образована. Регистр сдвига 2 обнуляется, и устройство готово к приходу следующего входного сигнала.

Устройство продолжает работать аналогично до тех пор, пока не будет образована пось1 2.1 х.у ледняя комбинация подгруппы (Ад, Аи, Ац), которая имеет вид 0... 0 0...0 2... 1 ... 2

n— - m m-t и не содержит ни одной пары символов, удовлетворяющих условиям а) и б) .

Граничного разряда преобразуемой части комбинацыии не существует, и импульс опроса

Зо

45 с выхода 85 схемы управления 9, распространяясь по цепям переноса блока 8 выделения граничного разряда преобразуемой части комбинации, доходит до разряда 14» На выходе

17I появляется импульс, который поступает на вход 45 схемы управления 9 и устанавливает в состояние «1» триггер 28. Массив ненулевых символов при распространении переноса переписывается в регистр 2, а соответствующие ячейки регистра 1 обнуляются, Импульсы с выхода 40 схемы управления 9 сдвигают массив ненулевых символов до тех пор, пока левый символ массива не займет ячейку 18„+> выход символа «О», который переключателем

10 длины кода подсоединен через схему «НЕ»

27„m g ко входу схемы «И» 24р, Схема «И»

24р срабатывает, и на выходе 42 блока 5 определения конца сдвига появляется импульс, Сдвиг прекращается, сдвинутый массив ненулевых символов переписывается в регистр 1.

Снова образована первая комбинация генерируемой подгруппы, имеющая вид 0... 0 и-я

2...1...2 0...0, таи иаи сигнал с выхода !

17> поступает на вход 45 схемы управления 9.

Эта комбинация на выход не подается (см. таблицу), При этом содержимое обнуленных ячеек

12„t- i —: 12„не меняется. Комбинация, записанная в ячейках 12„m+> —. 12, t разделяется на две части: правую (разряды S —:и— — t), которая преобразуется при образовании первой комбинации очередной подгруппы, н левую (разряды n — т+ 1 —: S — 1), которая не преобразуется при этом; (такое разделение сделано в таблице). Граничным разрядом преобразуемой части комбинации при образовании первой комбинации очередной подгруппы является разряд S, удовлетворяющий условиям:

a,) Х, = 1, б ) Х, „, = 1, в ) среди разрядов (S + 2 †: и — t) нет ни одной пары разрядов, удовлетворяющей условиям а ) и б ).

В разрядах 5 + 2 - - и — t преобразуемой части комбинации либо записаны символы

«1» (первая промежуточная комб инация

А,5 A ), либо есть символы «2», расположенные массивом в конце преобразуемой части (первая промежуточная комбинация

А, А 3) . .Преобразование правой части (разряды S —: и — t) при образовании первой комбинации очередной подгруппы заключается в перестановке значений в разрядах

5 и S + 1 и сдвиге влево массива символов

«2» (если он существует) вплотную к разряду S + 1, т. е. первый символ массива занимает разряд S+ 2. Освободившиеся при сдвиге массива символов «2» разряды заполняются символами «1». Ячейка 12, фиксируется после того, как с выхода 4б схемы управления

9 в разряд 14 > поступает импульс опроса.

Этот сигнал аналогично импульсу с выхода 85

10

25 схемы управления 9, появляясь поочередно на выходах 18, 1, 18, р,..., 18»1, доходит до ячейки 12,. После этого на выходе 19, появляется импульс, а перенос дальше не распространяется. Импульс с выхода 19 поступает на вентили перестановки б, осуществляя запись содержимого ячейки 12, в ячейку

12,.1, и наоборот. При этом вентили 80, и

81, открыты сигналом с выхода 86 схемы управления 9. Импулысы переноса с выходов

18n — I, 18n 2,..., 18,+1 и импульсы опроса с выхода 46 схемы управления 9 поступают в блок 4 переписи массива ненулевых символов. Массив символов «2» (если он существует) переписывается в регистр 2. Затем на выходе 47 схемы управления 9 появляется импульс, который через вентили 7 стирания массива ненулевых символов записывает символы «1» в ячейки регистра 1. При этом в ячейку 121 записывается символ «1», если в ячейке 181 записан символ «2». Сдвиг массива символов осуществляется аналогично сдвигу массива ненулевых символов и заканчивается, когда левый символ «2» массива будет записан в ячейку 18» . Срабатывает схема

«И» 25 +1, так как в ячейке 12,41 после перестановки значений в разрядах 5 и S + 1 записан символ «2». На выходе схемы «ИЛИ»

22 (выход 48 блока 5 определения конца сдвига) появляется сигнал «1», поступающий на вход 49 схемы управления 9 и прекращающий подачу импульсов сдвига. Затем импульсом с выхода 44 схемы управления 9 сдвинутый массив символов «2» переписывается в регистр 1.

Первая комбинация очередной подгруппы образована. После этого аналогично описанному генерируются все комбинациями этой подгруппы, затем образуется первая комбинация новой подгруппы и т, д. до тех пор, пока не будет прогенерирована последняя подгруппа данной группы, подгруппы 4.4, 3.6, 2.4 (см. таблицу). Первая промежуточная комбинация (А4.4 А3.6 А .4 ) при

О... 0 1...1 2...2 0...0 и не содержит ни и-m 1 d t одной пары символов, удовлетворяющих условиям а1) б1). Импульс опроса с выхода 46 схемы управления 9 доходит до разряда 141, на выходе 181 которого появляется импульс, устанавливающий в состояние «1» триггер 28.

Сдвиг массива символов «2» происходит до тех пор, пока левый символ массива не займет ячейку 18„41. После этого срабатывает схема «И» 24О, и сдвиг прекращается. Массив символов «2» переписывается в регистр 1.

В результате вновь образована первая комбинация первой подгруппы прогенерированной группы, имеющая вид О .. О 2... 2 1... 10...О.

n — m d 1

Но так как .импульс с выхода 181 поступает на вход 50 схемы управления 9, эта комбинация на выход не подается. При этом сигнал на выходе 86 схемы управления 9 равен

«О» и вентили 80 — 80, 1, 811 — 82, 1, закрыты, На выходе 46 схемы управления 9 поЗО

65 является импульс, вызывающий, в свою очередь, появление импульса на выходе 19,. Импульс с выхода 19, записывает содержимое ячейки 12, (символ «2») в ячейку 12,„1, но содержимое ячейки 12s+1 (символ «1») в ячейку 12, не переписывается, так как вентили 80, и 81, закрыты. В результате число символов «2» в комбинации увеличивается на едини цу, а число символов «1» уменьшается, и ооразуется первая комбинация первой подгруппы очередной группы, имеющая вид О... О 2... 2

n — и

1...1 0....0.

1 1

1.1

В случае, когда d=0 (Ай), запись первого символа «2» осуществляется импульсом с выхода 88 схемы управления 9 через переключатель 11 управления записью первого символа «2».

В случае, когда l=0 (Ад), при образо5.1 ванин второй промежуточной комбинации выдается сигнал об окончании процесса генерации.

Предмет изобретения

Устройство для генерации троичного кода с постоянным количеством «нулей», содержащее троичный регистр, троичный регистр со сдвигом, блок определения конца сдвига, выполненный на элементах «И», «ИЛИ», «НЕ», блок выделения граничного разряда преобразуемой части комбинации, входы которого соединены с выходами троичного регистра, переключатель длины кода, вентили перестановки, вентили стирания массива ненулевых символов, вентили записи сдвинутого массива ненулевых символов и схему управления, отличпюи4ееся тем, что, с целью расширения функциональных возможностей устройства и его упрощения, оно содержит блок переписи массива ненулевых символов и переключатель управления записью первого символа «два», причем первая группа выходов блока выделения граничного разряда преобразуемой части комбинации соединена с первой группой входов блока переписи массива ненулевых символов, вторая группа входов блока переписи массива ненулевых символов соединена с выходами ненулевых символов троичного регистра, выходы блока переписи массива ненулевых символов подключены ко входам записи троичного регистра со сдвигом, вторая группа выходов блока выделения граничного разряда преобразуемой части комбинации соединена с первыми входами вентилей перестановки, вторые входы вентилей перестановки подключены к выходам троичного регистра, выходы вентилей перестановки соединены со входами троичного регистра, выходы ненулевых символов троичного регистра со сдвигом соединены через вентили стирания массива ненулевых символов и вентили записи сдвинутого массива ненулевых символов со входами троичного регистра, выходы переключателя

251931

14

13 управления записью первого символа «два» соединены со входами записи символа «два» троичного регистра, выходы троичного регистра со сдвигом непосредственно и через переключатель длины кода подсоединены к одной группе входов блока определения конца сдвига, вторая группа входов блока определения конца сдвига соединена с выходами троичного регистра, входы одной группы элементов

«И» через элементы «НЕ» соединены с выходами символа «нуль» i-ro разряда троичного регистра и (i+ 1)-го разряда троичного регистра со сдвигом, входы другой группы элемен5 тов «И» соединены с выходами символа «два» -го разряда троичного регистра и (i + 1) -ro разряда троичного регистра со сдвигом, выходы всех групп элементов «И» соединены со входами соответствующих элементов «ИЛИ», 251931

Фиг. 2

Составитель А. Д. Ходырев

Редактор Л. А. Утехина Техред А. А. Камышникова Корректор 3. И. Тарасова

Заказ 1172/6 Тираж 480 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

Москва Ж-35, Раушская наб., д. 4i5

Типография, пр. Сапунова, 2