Устройство для кодирования и декодирования перестановок

Устройство для кодирования и декодирования перестановок

Иллюстрации

Показать все

Реферат

 

Изобретение относится к области автоматики и вычислительной техники и может быть использовано при передаче информации по каналам данных в сетях ЭВМ, многопроцессорных вычислительных системах и многомашинных комплексах, а также для генерации кодовых последовательностей в системах контроля и при решении комбинаторных задач. Цель изобретения - расширение функциональных возможностей за счет преобразования перестановки в однозначно соответствующее ей натуральное число. Устройство содержит группы из регистров 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 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН (g1)g G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4629402/24-24 (22) 02.01.89 (46) 23.12.90. Бюл. Р 47 (72) О. Г. Алексеев, А. А. Бабаев и Н. И. Ячкула (53) 681.3(088.8) (56) Авторское свидетельство СССР И 1180917, кл. С 06 Р 15/20, 1983.

Авторское свидетельство СССР ,У 14 10056, кл. G 06 F 15/20, 1986.

„.ЯК 1615732 А1

2 (54) УСТРОЙСТВО ДЛЯ КОДИРОВАНИЯ И ДЕ, КЩЩРОВАНИЯ ПЕРЕСТАНОВОК (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано при передаче инфор мации по каналам данных в сетях ЭВИ, многопроцессорных вычислительных сн» стемах и многомашинных комплексах, а также для генерации кодовых после, довательностей в системах контроля H !

1615732 }

= (1, г,...,n„ при решении комбинаторных задач. Цель изобретения — расширение функциональ ных возможностей за счет преобразования перестановки в однозначно соответствующее ей натуральное число.

Устройство содержит группы регистров

6, 12, 13, 22, 23, группы ключей 7, ; 21, 28, элементы ИЛИ, элементы 9, 10, 19, 20, 29, 30, 8 задержки, дешифра- 10 тор 4 и блок 5 выбора минимального числа, блоки 25 вычитания, множительИзобретение относится к автоматике и вычислительной технике и может

1 быть использовано при передаче ин20 . формации по каналам данных в сетях, ЭВМ, при обмене данными в многопро

: цессорных вычислительных системах и

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

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

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

Устройство содержит группы 1 - 3 блоков. Группа 1 блоков предназначечейа для формирования определяющего множества чисел и выбора из него ми- нимального числа. Группа содержит де- 40 шифратор 4, блок 5 выбора минимального числа, регистры 6, ключи 7, элемент 8 задержки и элементы ИЛИ 9и 10.

Группа 2 блоков предназначена для преобразования заданного натурального 45 числа в однозначно соответствующую емму перестановку. В состав группы 2 входят регистр 11, группы регистров

12 и 13, блоки 14 деления, сумматоры

15, элементы 16 и 17 задержки, вход 50

18 запуска, элементы ИЛИ 19 и 20 и ключи 21.

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

15, блоки 14 деления группы элементов 1?, 31, 32 задержки. Устройство реализует как процедуру преобразоват.. ния натурального числа m (О ш :. n.!) в однозначно соответствующую ему перестановку и элементов, так и обратную процедуру преобразования перестановки Q элементов в однозначно соответствующее ей натуральное число.

2 ил. блоки 26, вход 27 запуска, ключи 28„ элементы ИЛИ 29 и 30 и элементы 31 и

32 задержки, Блок 5 выбора минимального числа обеспечивает выбор минимального числа из априорно неизвестного подмноже-. ства множества известных чисел. Блок

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

Устройство работает в двух режи-. мах - кодирования и декодирования, которые основаны на реализации извест ных процедур взаимно однозначных пре; образований перестановок исходных, предварительно пронумерованных числа-ми 1, 2, 3...,,п, элементов и натуральных чисел m (О 6

Сущность процедуры кодирования заключается в определении величин Р"„

1, п, численно характеризующих степень отклонения положения i-го элемента в кодируемой перестановке х = (х,, х,,...,х„ от положения соответствующего элемента в базовой перестановке, и последующей свертки значений Р„ по рек ррентной зависимо сти в одно натуральное число.

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

1615732 .на i-м шаге алгоритма (i = 1, 2,...,n) пвыбирается минимальное число r, из х1, х, f f) хд и определяется P = х, —

Г1е

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

Р— О р К5.

Р„=- О; К+

P> = 2; К>

m = 28;

1 = 5р

= 4;

28;

i -= -3;

14;

i = 2 р

Pz = 0> К

P = 1; Kq

i 1 ° (1) II = I„ х, ° и далее — 1,3,4;5

3, 4, 5 ЕЗ = (3, 4)1

Ее = 44)1

2 р

1е Х2 1

= 5 р

3; х>

3; х<

= 3 р

= 4;

4у х5

x I yI +r( (4) Искомое натуральное число m соответствующее заданной перестановке х, получается с использованием рекуррент ной зависимости

K> = К3-! (n — i + 1) + Р; (2) причем Ко = О, m = К„. 20

Например, при х = (2, 1, 3, 3, 43,имеют г =1; Р(=1; I< = 1,3,4,5 — 25

r<=1; Р =0; I = 3, 4, 5 к =4; гЗ 3; Ре = 2; Е =ЕЗ, 4)1

К = 14; еа = 3; Р+ = 01 ЕЕ = Е4)1 Ка = 28; г — 43 Р = 03 ?5 = )Р К = 28.

m = 28.

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

Значения P, определяются для последовательности i = n n — 1,...,1. На каждом шаге производятся вычисления

P, = rest (К; /(и-i+1)); (За}

К = let (К /(и-(+1)J (3á) !

-! 1 У

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

lut - целая часть, причем К)/! =ш.

Процедура восстановления х состоит в последовательном (i = 1,2,...,n) вычислении значений х," на основе мно1 жества с последующим переходом к 1; в соот1 ветствии с (1).

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

Перед работой устройства в обоих режимах в регистры 6 вводятся числа исходного определяющего множества 3

I = 1, 2,...,n), причем число i E I о заносится в регистр 61. Заданная перестановка параллельным кодом вводится в регистры 22,, i = 1, и, а число

m — в регистр 11.

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

22, один из входов элемента ИЛИ 29, вход элемента 31 задержки и управляющий вход ключа 28,.

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

222, поступает на вход блока 25 вычи— тания, на другой вход блока 25 с выхода блока 5 выбора минимального числа через ключ 28 4 (замкнутый на время действия управляющего импульса) поступает значение r . Значение P = х 1 ( г< вычисляется в блоке 25 1 вычитания и записывается в регистр 23 <. Запускающий импульс, поступив через элемент

ИЛИ 29 на считывающие входы регистров

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

1615732 вызывает размыкание ключа 7 с номером до конца вычислений. Это равносиль,I ио преобразованию множества I и I<

corëàñío (1).

Аналогично с использованием блоков 2 - 22, 25 — 25 вычисляются Р

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

ыходе блока 5 и размыкание одного из ключей 7 для преобразования (1).

После вычисления Р осуществляется. оследовательное считйвание P — Р

Н з регистров -23 на входы множитель о-суммирующих блоков 26, функциони- ующих согласно (2). Значение m = K,,2O иксируется в регистре 24 и выводится а выход устройства под управлением пульса от элемента 32 задержки .

В.режиме декодирования .(используются группы 1 и 2 блоков) работа уст 25 ойства начинается подачей импульса а вход 18 запуска. При этом импульс входа 18 запуска поступает на счи- бывающий вход регистра 11, вход элемента задержки 16,„ и синхронизирую- 30 щий вход блока 14 деления. Число m с информационного выхода регистра,1: йоступает на вход блока 14„ деления.

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

Irro аналогии с режимом кодирования.

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

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

Устройство для кодирования и декодирования перестановок, содержащее трй группы регистров, две группы клю- чей, блок выбора минимального числа, дешифратор, элемент задержки, регистр два элемента ИЛИ, блоки деления, сум маторы, две группы элементов задержки, причем выход i-го регистра первой группы соединен с информационным входом i-ro ключа первой группы (i = 1, и, где n — длина перестановок), управляющий вход i-ro ключа первой группы соединен с i-м выходом дешифрато", ра, вход дешифратора соединен с выходом элемента задержки, выход i-го ключа первой группы соединен с i-м входом блока выбора минимального числа, выход блока выбора минимального числа соединен с информационными входами ключей второй группы, информационный вход регистра является входом кодирующего числа устройства,„ выход регистра соединен с информационным входом первого блока деления, выход целой части результата j-го блока деления соединен с информационным Вхо дом (д+1)"го блока деления (j =" 1, п-1), выхоц остатка от деления i-го блока деления соединен с информацион ным входом (п+1-i)-го регистра второй группы, выход i-го регистра второй группы и выход i-ro ключа второй груп-,. пы соединены с соответствующими вхо-,,цами i-го сумматора, выход i-ro сум- матора соединен с i — м входом первого. элемента ИЛИ и с информационным вхо- . дом i-ro регистра третьей группы, вы; ходы регистров третьей группы являются выходами элементов перестановки устройства, вход первого элемента задержки первой группы является входом запуска устройства и соединен со счи тывающим входом регистра и входом . синхронизации первого блока деления, выход j-ro элемента задержки первой группы соединен с входом синхронизации j-ro блока деления и входом (j+1)"го элемента задержки первой группы, выход n-ro элемента задержки первой ! группы соединен со считывающим входом первого регистра второй группы, управляющим входом первого ключа второй группы, первым входом второго элемен* та ИЛИ и входом первого элемента за держки второй группы, выход j-го эле мента задержки второй группы соединен

)co считывающим входом ()+1)-го регистра второй группы, управляющим входом (j+1)-го ключа второй группы, (j+1)-м входом второго элемента ИЛИ и входом:

I(j+1)-ro элемента задержки второй группы, выход и-го элемента задержки

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

1615732 блоки, дополнительный регистр, третью и четвертую группы элементов задерж.ки, третий, четвертый, пятый и шестой элементы ИЛИ, причем информационные входы регистров четвертой группы являются входами элементов перестановки устройства, выход i-го регистра, четвертой группь соединен с i-м вхо дом третьего элемента.ИЛИ и с суммирующим входом i-ro блока вычитания„ информационные входы всех ключей третьей группы соединены с выходом блока выбора минимального числа, выход i-го ключа, третьей группы соединен с вычитающим входом i-го блока вычитания, выход 1- го блока вычитания соединен с информационным входом i-го регистра пятой группы, выход i-го ре-. гистра пятой группы соединен с сумми- щ рующим входом -го мнсжнтельно-суммирующего блока, выход j-го мнсхмтель.— но-суммирующего блока соединен с мно,жительным входом (j+1)-го множительно суммирующего блока, выход и-ro множи- 25 тельно-суммирующего блока соединен с информационным входам дополнительного регистра, выход дополнительного -реги.стра являет"я выходом кодирующего чи=сла устройства, вход первого элемента >0 задержки третьей группы является дополнительным входом запуска устройства и соединен со считывающим входом первого регистра четвертой группы, управляющим входом первого ключа тре тьей группы и первым входом четвертого элемента ИЛИ, выход j ro элемента задержки третьей группы соединен со считывающим входом (j+1)-ro регистра четвертой группы, управляющим входом (j+1)-го ключ" третьей группы, (j+1)входом четвертого элемента ИЛИ и с входом (j+l)-го элемента зацержки третьей группы, выход и-го элемента задержки третьей группы соединен со считывающим входом первого регистра пятой группы и входом первого элемента задержки четвертой группы, выход j-ro элемента задержки Четвертой группы соепинен со считывающим входом (j+1)го регистра пятой группы и входом (j+1)-ro элемента задержки четвертой группы,. выход и-ro элемента задержки четвертой гру .пы соединен со считывающим входом дополнит"=чьного регистра, выходы первого и третьего элементов

ИЛИ соединены с входами пятого элемента ИЛИ, выход пятого элемента ИЛИ соединен с входом элемента задержки, выходы второго и четвертого элементов

ИЛИ соединены со входами шестого элемента ИХК, ьыход шестого элемента ИЛИ соединен со считывающими входами всех регистров перв"й группы.

1615732

Составитель М. Шелобанова

Редактор А. Козориз Техред Л.Сердюкова Корректор М, лароши

Э аказ 3989 Тираж 568 Подписное

ВЙИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101