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

,У 141 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИПРИ ГКНТ СССР КАВТОРСКОМУ СВИДТЕЛЬСТ(56) Авторское свидетельство СССРВ 1180917, кл. С 06 Р 15/20, 1983.Авторское свидетельство СССР00561 кл06 Р 15/20 1986 2СТРОЙГ"ВО ДЛЯ КОДИРОВАНИЯ И ДЕ ВАНИЯ ПЕРЕСТАНОВОКобретение относится к автомавычислительной технике и может пользовано при передаче ииФор о каналам данных в сетях ЭВИ, оцессорных вычислительных си и многомашинных комплексах,для генерации кодовых после ьностей в системах контроля и(54) У КВАДРО (57) И тике и быть и мации многопр стемах а такж дователпри решении комбинаторных задач. Цельизобретения - расширение Функциональ ных возможностей за счет преобразования перестановки в однозначно соответствующее ей натуральное число. Устройство содержит группы регистров6, 12, 13, 22, 23, группы ключей 7, ; 21, 28, элементы ИЛИ, элементы 9, 10, 19, 20, 29, 30, 8 задержки, дешифра тор 4 и блок 5 выбора минимального числа, блоки 25 вычитания, множительИзобретение относится к автоматике и вычислительной технике и можетбыть использовано при передаче ин 20 . формации по каналам данных в сетяхЭВМ, при обмене данными в многопро , цессорных вычислительных системах имногомашинных комплексах, а такжедля генерации кодовых последовательностей в системах контроля и при решении комбинаторных задач.Цель изобретения - расширение.функциональных возможностей за счетпреобразования перестановки в одно 30значно соответствующее ей натуральное число,На Фиг. 1 показана функциональнаясхема устройства; на фиг, 2 - функциональная схема блока выбора минимального числа. 35Устройство содержит группы 1 - 3блоков. Группа 1 блоков предназначечейа для Формирования определяющегомножества чисел и выбора из него ми-нимального числа. Группа содержит дешифратор 4, блок 5 выбора минимального числа, регистры 6, ключи 7, элемент 8 задержки и элементы ИЛИ 9 и 10.Группа 2 блоков предназначена дляпреобразования заданного натурального 45числа в однозначно соответствующуюемму перестановку. В состав группы 2входят регистр 11, группы регистров12 и 13, блоки 14 деления, сумматоры15, элементы 16 и 17 задержки, вход 5018 запуска, элементы ИЛИ 19 и 20 иключи 21Группа 3 блоков предназначена для преобразования заданной перестановки в однозначно соответствующее ей натуральное число и содержит группы реги,стров 22 и 23, регистр 24, блоки 25 вычитания, множительно-суммирующие но"суммирующие блоки 26, сумматоры15, блоки 14 деления группы элементов 1, 31, 32 задержки. Устройствореализует как процедуру преобразоватния натурального числа ш (Ош с:.и)в однозначно соответствун 1 щую ему перестановку и элементов, так и обратную процедуру преобразования перестановки и элементов в однозначно соответствующее ей натуральное число.2 ил. блоки 26, вход 27 запуска, ключи 28, элементы ИЛИ 29 и 30 и элементы 31 и 32 задержки,Блок 5 выбора минимального числа обеспечивает выбор минимального числа из априорно неизвестного подмноже-. ства множества известных чисел. Блок 5 содержит элементы ИЛИ 33 и НЕ 34, ключи 35, элементы И Зб. На функциональной схеме блока 5 входы и выход, а также входы элементов ИЛИ и информа- ционные входы ключей изббражены одной линией, как и остальные связи устройства на Фиг, 1, обеспечивающие пере;- дачу кодов чисел, тогда как реальное их число должно обеспечить прием и передачу максимального из возможных чисел параллельным кодом.Устройство работает в двух режи-. мах - кодирования и декодирования, которые основаны на реализации извест ных процедур взаимно однозначных прер образований перестановок исходных, предварительно пронумерованных числа ми 1, 2, Зп, элементов и натуральных чисел ш (О 6 ш ( п,).Сущность процедуры кодированиязаключается в определении величин Р"1, и, численно характеризующихстепень отклонения положения -гоэлемента в кодируемой перестановкех х , л. ,от положениясоответствующего элемента в базовойперестановке, и последующей сверткизначений Р по рекуррентной зависимости в одно натуральное число. Базовая перестановка есть множест.во и первых натуральных чисел1615732 .на З.-м шаге алгоритма (х = 1, 2п) гвыбирается минимальное число г, из х 1, х 433 х Р( и определяется Р, = х, - Г 15Указанные действия осуществляются с подмножеством 1;элементов, а на следующем шаге (1+1) используется под- множество Р - ОР К 5. Р=- О; К+ Р 2,К ш = 28 а - 5 Р)45 х;=Р,+г,(4) Искомое натуральное число ш, соответствующее заданной перестановке х, получается с использованием рекуррент ной зависимости К= К;(и - х + 1) + Р; (2) причем Ко = О, ш = К. 20 Например, при х = (2, 1, 3, 3, 4)г =1; Р =1; 1= 1,3,4,5К =1 ф . 25г 2=1; Ра =0; 1 г= 3 4 5 ек = 4;г - 31 Рг = 21 Е =23, 4)1К = 14 ега 31 Ре 01 Ее 41 Ка 281,г =43 Р =03 1 к =Ф; К=28;ш = 28.Алгоритм декодирования также базируется на определении первоначальных 35 чисел Р и последующем восстановлении по ним исходной перестановки.Значения Р, определяются для последовательности г = и, и - 11. На каждом шаге производятся вычисления 40 Р, геег К; /(и-Ь 1 1 (За) где гезг. - остаток от деления;1 ий - целая часть, причем К 1( =ш.Процедура восстановления х состоит в последовательном ( = 1,2и) вычислении значений х," на основе множества 1; с последующим переходом к 1; в соот 1ветствии с (1).Последовательность восстановлениях в рассматриваемом примере (ш = 28,и = 5) такова: Перед работой устройства в обоихрежимах в регистры 6 вводятся числаисходного определяющего множества11 =, 1, 2и, причем число . Е 1(3заносится в регистр 61. Заданная перестановка параллельным кодом вводится в регистры 22 х = 1, и, а числош - в регистр 11.Работа устройства в режиме коди,рования (используются группы 1 и 3блоков) начинается подачей имп.Кльса навход 27 запуска, При этом импульс поступает на считывающий вход регистра221, один из входов элемента ИЛИ 29,вход элемента 31 задержки и управляющий вход ключа 28Значение х , считанное с регистра223, поступает на вход блока 25 вычи -тания, на другой вход блока 25 с выхода блока 5 выбора минимального числа через ключ 28(замкнутый на времядействия управляющего импульса) поступает значение г . Значение Р = хг вычисляется в блоке 25вычитанияи записывается в регистр 23 . Запускающий импульс, поступив через элементИЛИ 29 на считывающие входы регистров6, вызывает считывание множества 10через замкнутые (по исходному состоянию) ключи 7 на входы блока 5 выбора.минимального числа, что и обусловливаетпоявление значения г на выходеблока 5. Число х пройдя через эле-.менты ИЛИ 30 и 10 с задержкой на элементе 8, поступает на дешифратор 4 ивызывает размыкание ключа 7 с номеромдо конца вычислений. Это равносильио преобразованию множества 1 и 1 согласно (1).Аналогично с использованием блоков 2- 22, 25- 25 вычисляются РТребуемая временная последовательость работы блоков, соответствующаяоследовательности значений , обеспе-.10вается элементами 31 задержки. Притом всякий раз осуществляются обраще-ие к регистрам 6 для выработки г наыходе блока 5 и размыкание одногоиз ключей 7 для преобразования (1).После вычисления Р осуществляетсяоследовательное считйвание Р - Рз регистров 23 на входы множительо-суммирующих блоков 26, функциони-ующих согласно (2). Значение ш = К 20иксируется в регистре 24 и выводитсяа выход устройства под управлениемпульса от элемента 32 задержки.В.режиме декодирования .(используМтся группы 1 и 2 блоков) работа уст 25 ойства начинается подачей импульса а вход 18 запуска. При этом импульсвхода 18 запуска поступает на счибывающий вход регистра 11, вход элемента задержки 16, и синхронизирую Щий вход блока 1 ч, деления. Числоцш с информационного выхода регистра,1: йоступает на вход блока 14деления,Временная последовательйость в ра- боте блоков группы 2 и их взаимодей- ствие с блоками группы 1 строятся йо аналогии с режимом кодирования. При этом блоки 14 деления реализуют ,операции (3), значения Р фиксируются в регистрах 12, на сумматорах 15 осуществляются действия (4), значения х, фиксируются в регистрах 13. Форм и 3 о б р е т е н и 45 я и декожащее уппы клю- о числа, регистр ния сум Устройство для кодированидирования перестановок, содертри группы регистров, две грчей, блок выбора минимальногдешифратор, элемент задержкидва элемента ИЛИ, блоки делематоры, две группы элементов задержки, причем выход -го регистра первой группы соединен с информационным входом 1-го ключа первой группы ( = 1, и, где и - длина перестановок), управляющий вход -го ключа первой группы соединен с д-м выходом дешифрато", ра, вход дешифратора соединен с выхо 55 дом элемента задержки, выход -гоключа первой группы соединен с х-мвходом блока выбора минимального числа, выход блока выбора минимальногочисла соединен с информационными входами ключей второй группы, информационный вход регистра является входомкодирующего числа устройства, выходрегистра соединен с информационнымвходом первого блока деления, выходцелой части результата -го блока деления соединен с информационным входом (д+1)"го блока деления (д =" 1,и), выхоц остатка от деления х-гоблока деления соединен с информационным входом (и+1-)-го регистра второйгруппы, выход х-го регистра второйгруппы и вьгход -го ключа второй груп-,пы соединены с соответствующими вхо-,дами х-го сумматора, выход х-го сум-матора соединен с х-и входом первогоэлемента ИЛИ и с информационным входом -го регистра третьей группы, вы.ходы регистров третьей группы являются выходами элементов перестановкиустройства, вход первого элемента задержки первой группы является входомзапуска устройства и соединен со считывающим входом регистра и входом .синхронизации первого блока деления,выход -го элемента задержки первойгруппы соединен с входом синхронизации 1-го блока деления и входом Я+1)"го элемента задержки первой группы,выход и-го элемента задержки первойгруппы соединен со считывающим входомпервого регистра второй группы, управляющим входом первого ключа второйгруппы, первым входом второго элемента ИЛИ и входом первого элемента задержки второй группы, выход 1-го элемента задержки второй группы соединенсо считывающим входом (1+1)-го регистра второй группы, управляющим входом(1+1)-го ключа второй группы, (1+1)-мвходом второго элемента ИЛИ и входом;;второй группы соединен с входами считывания всех регистров третьей группы, отличающееся тем,что, с целью расширения функциональ-ных возможностей за счет преобразования перестановки в однозначно соответствующее ей натуральное число, оносодержит четвертую и пятую группы регистров, третью группу ключей, блокивычитания, множительно-суммирующиеблоки, дополнительный регистр, третьюи четвертую группы элементов задерж,ки, третий, четвертый, пятый и шестойэлементы ИЛИ, причем информационныевходы регистров четвертой группы являются входами элементов перестановки устройства, выход -го регистра,четвертой группь соединен с х-м входом третьего элемента.ИЛИ и с суммирующим входом 3.-го блока вычитанияинформационные входы всех ключейтретьей группы соединены с выходомблока выбора минимального числа, выход -го ключа, третьей группы соединен с вычитающим входом -го блокавычитания, выход 3.- го блока вычитаниясоединен с информационным входом -горегистра пятой группы, выход 3.-го регистра пятой группы соединен с сумми- щрующим входом .-го множительно-суммирующего блока, выход 1-го мнсхмтельно-суммирующего блока соединен с мно,жительным входом Я+1)-го множительносуммирующего блока, выход и-го множительно-суммирующего блока соединен синформационным входам дополнительногорегистра, выход дополнительного реги,стра являет"я выходом кодирующего чи-.сла устройства, вход первого элемента озадержки третьей группы является дополнительным входом запуска устройства и соединен со считывающим входом первого регистра четвертой группы,управляющим входом первого ключа третьей группы и первым входом четвертого элемента ИЛИ, выход 1-го элементазадержки третьей группы соединен сосчитывающим входом Я+1)-го регистрачетвертой группы, управляющим входом(1+1)-го ключе третьей группы, (1+1)входом четвертого элемента ИЛИ и свходом Ц+1)-го элемента задержки третьей группы, выход и-го элемента задержки третьей группы соединен со считывающим входом первого регистра пятой группы и входом первого элементазадержки четвертой группы, выход 1-гоэлемента задержки Четвертой группысоепинен со считывающим входом (+1)го регистра пятой группы и входом(1+1)-го элемента задержки четвертойгруппы,. выход и-го элемента задержкичетвертой грут.пы соединен со считывающим входом дополнит"=чьного регистра,выходы первого и третьего элементовИЛИ соединены с входами пятого элемента ИЛИ, выход пятого элемента ИЛИсоединен с входом элемента задержки,выходы второго и четвертого элементовИЛИ соединены со входами шестого элемента ИХК, ьыход шестого элемента ИЛИсоединен со считывающими входами всехрегистров первой группы..2 Составитель М. ШелобановаТехред Л.Сердюкова Корректор М, Шароши ктор А. Козори при ГКНТ ССС изводственно-издательский комбинат "Патент", г. Ужгород, ул, Гагар РедаЭаказ 3989ВЙИИПИ Госуда Тираж венного ко 113035, Мо 568 Подписноетета по изобретениям и открыти ва, Ж, Раушская наб., д. 4/