Устройство для кодирования и декодирования перестановок Советский патент 1990 года по МПК G06F15/163 

Изобретение относится к автоматике и вычислительной технике и может быть использовано при передаче ин- формации по каналам данных в сетях ; ЭВМ, при обмене данными в многопро цессорных вычислительных системах и многомащинных комплексах, а также для генерации кодовых последовательностей в системах контроля и при решении комбинаторных задач.

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

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

Устройство содержит группы 1 - 3 блоков. Группа 1 блоков предназначе-: чена для формирования определяющего множества чисел и выбора из н.его ми- нимального числа. Группа содержит де- шифратор 4, блок 5 выбора минимального числа, регистры 6, ключи 7, эле- мет 8 задержки и элементы ИЛИ 9 и 10 2 блоков предназначена для преобразования заданного натурального числа в. однозначно соответствующую ему перестановку. В состав группы 2 входят регистр 11, группы регистров 12 и 13, блоки 14 деления, сумматоры 15, элементы 16 и 17 задержки, вход 18 запуска, элементы ИЛИ 19 и 20 и ключи 21.

Группа 3 блоков предназначена для преобразования заданной перест,ановки в однозначно соответствующее ей натуральное число и содержит группы рёги стров 22 и 23, регистр 24, блоки 25 вычитания, множительно-суммирующи

0

5

0

35

40 45

блоки 26, вход 27 запуска, ключи 28, элементы ИШ 29 и 30 и элементы 31 и 32 задержки,

Блок 5 выбора минимального числа . обеспечивает выбор минимального числа из априорно неизвестного подмноже- - ства множества известных чисел. Блок 5 содержит элементы ИЛИ 33 и НЕ 34, ключи 35, элементы И 36, На функциональной схеме блока 5 входы и вькод, а также входы элементов ИЛИ и информаН ционные входы ютючей изображены одной линией, как и остальные связи устрой-- ства на фиг. 1, обеспечивающие neper- дачу кодов чисел, тогда как реальное их число должно обеспечить прием и передачу максимального из возможных чисел параллельным кодом.

Устройство работает в двух режимах - кодирования и декодирования, которые основаны на реализации извест ных процедур взаимно однозначных преУ образований перестановок исходных, предварительно пронумерованных числа-ми 1, 2, 3,...,,Пэ элементов и нату- ральных чисел m (О тп п/). 1 Сущность процедуры кодирования заключается в определении величин ,, i 1, п, численно характеризующих степень отклонения положения i-ro элемента в кодируемой перестановке

50

X

. 1 ---2.

,«п1

от положения

соответствлтощего элемента в базовой перестановке, и последующей свертки значений Р по рекуррентной зависимо, сти в одно натхуральное число.

Базовая перестановка есть множест„ во п первых натуральных чисел

, 2,...,п1

161

ла i-M шаге алгоритма (i 1, 2,...,n) выбирается минимальное число г, из х, +,, и определяется Р , х, {- I

Указанные действия осуществляются

с подмножеством I, i элементов, а на следующем шаге (i+1) используется подмножество

I; Ц. х;.

26

i 5; Pj 0; Kg. m 28;

i 4; P 0; K 28; i 3; РЗ 2; Кз 14;

i 2; РЗ. 0; Кг 4; i 1; PI 1; К, 1.

,

Изобретение относится к области автоматики и вычислительной техники и может быть использовано при передаче информации по каналам данных в сетях ЭВМ, многопроцессорных вычислительных системах и многомашинных комплексах, а также для генерации кодовых последовательностей в системах контроля и при решении комбинаторных задач. Цель изобретения - расширение функциональных возможностей за счет преобразования перестановки в однозначно соответствующее ей натуральное число. Устройство содержит группы из регистров 6,12,13,22,23, группы ключей 7,21,28, элементы ИЛИ, элементы задержки 9,10,19,20,29,30,8, дешифратор 4 и блок 5 выбора минимального числа, блоки 25 вычитания, множительно-суммирующие блоки 26, сумматоры 15, блоки 14 деления группы элементов задержки 17,31,32. Устройство реализует как процедуру преобразования натурального числа M(0≤M*98N) в однозначно соответствующую ему перестановку N элементов, так и обратную процедуру преобразования перестановки N элементов в однозначно соответствующее ей натуральное число. 2 ил.

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

к; к-, (п - i + 1) + р, (2)

причем KQ О, m К.

Например, при х {2, 1, 5, 3, 4 : имеют

г, 1; Р, 1; 1, 1,3,4,5};

к, 1;

г 1; Pj 0; I2 (з, 4, sj;

Kf 4; г, 3; Р, 2; I, (з,

Кэ 14;

Г4 3; Р Ог.1 -{4JJ К4 28;,

rj 4; Ру 0; 1 0; Kg- 28. m 28.

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

Значения Р определяются для послеовательности i п, п - 11. На

каждом шаге производятся вычисления

P; rest к,-/(п-1+1); (За) K.r K,-/(n-i-H) (36)

где rest - остаток от деления;

lut - целая часть, причем Kj, m. Процедура восстановления х состоит в последовательном (i 1,2,...,п) вычислении значений х, на основе множества I

х; Р; + г.(4)

с последующим переходом к I- в соответствии с (1).

Последовательность восстановления X в рассматриваемом примере (т 28, п 5) такова:

и далее

г, 1;:-:, 2; 1 l,3,4,5J;

г j 1;x,j 1; Ij з, 4, 5};

r 3;Kg 5; (з,

20 r 3; X4 3; I (4J; ГУ 4; x 4; Ij (2

25 Перед работой устройства в обоих режимах в регистры 6 вводятся числа исходного определяющего множества ., IQ {1 2,...,п, причем число i В 1 заносится в-регистр 6. Заданная пе30 рестановка параллельным кодом вводится в регистры 22, i 1, п, а число m - в регистр t1.

Работа устройства в режиме коди- -рования (используются группы 1 и 3 блоков) начинается подачей импульса на вход 27 запуска. При этом импульс поступает на считывающий вход регистра 22,, один из входов элемента ИЛИ 29, вход элемента 31 задержки и управля0 ющий вход ключа 28,.

Значение х.„ считанное с регистра

35

22, поступает на вход блока 25 вычитания, на другой вход блока 25 с выхода блока 5 выбора минимального чис- 5 ла через ключ 28 (замкнутьм на время действия управляющего импульса) поступает значение г. Значение Р

г, вычисляется в блоке 25 вычитания и записывается в регистр 23. Запуска0 ющий импульс, поступив через элемент ИЛИ 29 на считывающие входы регистров 6, вызьшает считывание множества 1 через замкнутые (по исходному состоянию) ключи 7 на входы блока 5 выбора.

5 -минимального числа, что и обусловливает появление значения г. на выходе блока 5. Число х,, пройдя через эле-, менты ИЛИ 30 и 10с задержкой на элементе 8, поступает на дешифратор 4 и

вызывает размыкание ключа 7 с номером XJ. до конца вычислений. Это равносиль- н|о преобразованию множества IQ и 1 с|огласно (1).1

Аналогично с использованием блоков 2«- 22

-п

25

вычисляются Pg I ь.. Требуемая временная последователь- юсть работы блоков, соответствующая ; госледовательности значений i, o6ecnei.jo гивается элементами 31 задержки При ; том всякий раз осуществляются обраще- : пие к регистрам 6 для вьфаботки г на

;}ыходе блока 5 и размыкание одного из ключей 7 для преобразования (1). fs I, После вычисления Р осуп ествляетсЯ: Iпоследовательное считывание P/j - Р 13 регистров 23 на входы множитель - : 1о- суммирующих блоков 26, функциони- :)ующих согласно (2), Значение m К.; 20 фиксируется в регистре 24 и выводится la выход устройства под управлением импульса от элемента 32 задержки

В. режиме декодирования Г (испольау°- )|отся группы 1 и 2 блоков) работа уст, 25 )ойства начинается подачей импульса а вход 18 запуска. При этом импульс j: входа 18 запуска поступает на счи-i гьшаюпщй вход регистра 11, вход эле Мента задержки 16, и синхронизирую- №й вход блока 14,, деления. Число га с информационного выхода регистра Л v Поступает на вход блока 14 деления

Временная последовательность в ра боте блоков группы 2 и их взаимодей ствие с блоками группы 1 строятся По аналогии с режимом кодирования, (При этом блоки 14 деления реализуют .операции (3), значения Р фиксируются в регистрах 12, на сумматорах 15 осуществляются действия (4), значения X фиксируются в регистрах 13, ;

30

35

Формула изобретения

Устройство для кодирования и декодирования перестановок 5 содержащее три группы регистров, две группы клю-j чей, блок выбора минимального числа, , дешифратор, элемент задержки, регистр два элемента ИЛИ, блоки деления, сумматоры, две группы элементов задержки, причем вькод i-ro регистра первой группы соединен с информационным входом i-ro ключа первой группы (i 1, п. где п - длина перестановок), управляющий вход i-ro ключа первой группы соединен с i-м выходом дешифрато- , ра, вход дешифратора соединен с выхо

0

5

0

5

5

0

5

дом элемента задержки, выход i-ro ключа первой группы соединен с i-м входом блока выбора минимального чис ла, выход блока выбора минимального числа соединен с информационными входами ключей второй группы, информаци- онньй вход регистра является входом кодирующего числа устройства, выход регистра соединен с информационным входом первого блока деления, выход целой части результата j-ro блока деления соединен с информационным входом (j+1)ro блока деления (j 1, п-1), выход остатка от деления i-ro блока деления соединен с информацион ным входом (n+1-i)-ro регистра второй группы, выход регистра второй группы и выход i-ro ключа второй грулг- пы соединены с соответствующими вхо- .дами 1-го сумматора, выход i-ro сум- матора соединен с i-м входом первого, элемента ШМ и с информационным вхо- . дом i-ro регистра третьей группы, ходы регистров третьей грзгппы являются выходами элементов перестановки устройства, вход первого элемента задержки первой группы является входом запуска устройства и соединен со счи-f тывающим входом регистра и входом синхронизации первого блока деления у ньжод j-ro элемента задержки первой группы соединен с входом синхронизации j-ro блока деления и входом (j+1) то элемента задержки первой группы, выход п-го элемента задержки первой Группы соединен со считьшающим входом первого регистра второй группы, управляющим входом первого ключа второй группы, первым входом второго элемен- |Та ИЛИ и входом первого элемента за- 1держки второй группы, выход j-ro эле- мента задержки второй группы соединен 1со считывающим входом (j+1)-TO реги стра второй группы, управляющим входом {j + 1)-ro ключа второй группы, (j + 1)-M входом второго элемента ИЛИ и входом : (j-t-1)-ro элемента задержки второй 1группы, выход п-го элемента задерлжи :второй группы соединен с входами считывания всех регистров третьей группы, отличающееся тем, что, с целью расширения: функциональ- ных возможностей за счет преобразования перестановки в однозначно соответствующее ей натуральное число, оно содержит четвертую и пятую группы регистров, третью группу ключей, блоки, .вычитания, множительно-суммирующие

9,

блоки, дополнительньй регистр, третью и четвертую группы элементов задерж- .ки, третий, четвертьй, пятый и шестой элементы ИЛИ, причем информационные входы регистров четвертой группы являются входами элементов перестановки устройства, выход i-ro регистра |четвертой группы соединен с i-м вхо дом третьего элемента .ИЛ и с сумми рующим входом i-ro блока вычитания информационные входы всех ключей третьей группы соединены с выходом блока выбора минимального числа, выход i-ro ключаS третьей группы соединен с вычитающим входом i-ro блока вычитания, выход i-ro блока вычитания соединен с информационным входом 1-го регистра пятой группы, выход 1--го ре- .гистра пятой группы соединен с сумми- ;рующим входом i-ro множнтельно-сумми руищего блока, выход j-ro мнояжтель но-суммирующего блока соединен с мно- .жительным входом (j+1)-ro множительно 1 суммирующего блока, выход п-го множи- .тельно суммирующего блока соединен с информационньи входам дополнительного регистра, выход дополнительного -реги- ;, стра является выходом кодирующего чкела устройства, вхсд первого элемента задерлжи третьей гр-уппы является до- пoлнитeльны:vl входом запуска устройства и соединен со считьшающим входом

0

5

5732

n 5 О

10

первого регистра четвертой группы, управляющим входом первого ключа трё тьей группы и первым входом четвертого элемента ИЛИ, выход j-ro элемента задержки третьей группы соединен со считываюсщм входом (j+1)-ro регистра четвертой группы, управляющим входом (j+1)-ro ключ третьей группы, (j+1)- входом четвертого элемента ИЛИ и с в::одом (j + 1)-ro элемента задержки третьей группы, п-го элемента задержки третьей группы соединен со считывающим входом первого регистра пятой группы и входом первого элемента задержки четвертой группы, выход j-ro элемента задержки четвертой группы соединен со cчитывaюr им входом (j + 1)- го регистра пятой группы и входом (j + 1)-ro .элемента задеряжи четвертой группы,, выход п-го элемента задержки четвертой группы соединен со считывающим входом дополнитеяьного регистра, выходы первого и третьего элементов ИЛИ соединены с входами пятого элемента ИЛИ, выход пятого элемента ИШ соединен с входом элемента задержки, выходы второго и четвертого элементов ИЛИ соединены со входаки шестого элемента ИЛИ, выход шзстс соединен со считьтающиш- регистров первой группы.

элемента ИЛИ входами всех