Устройство для контроля р-кода фибоначчи

(57) Изобретение оттельной технике. Целрасширение функционза счет обнаруженияи исправления одинор-коде Фибонначчи прсодержит регистры 1коррекции, элементытриггеры 11-3, тричик 16 по модулю ссвязями. 1 з.п. ф-ль КОНТРОЛЯ р-КОДА Р 35ное конструкторбюро "Модуль"ческого институтический институтА. Лужецкий тельство СССР М 13/00, 1985. ельство СССР М 13/00,20/8 19 ОСУДАРСТВЕННЫЙ КОМИТЕТО ИЗОБРЕТЕНИЯМ И ОЧНРЫТИЯРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕ У СВИДЕТЕЛЬСТВУ(71) Специализироваско-технологическоеВинницкого политехнии Винницкий политех(56) Авторское свидР 1361554, кл. Н 03Авторское свидетУ 1439596, кл. Н 0307.05.87. осится к вычислиь изобретения - альных возможносте двойных ошибок чных ошибок в и р ) 1, Устройство 3 сдвига, блок 4 И 5-10, счетные геры 14, 5, счетоответствующими3 1510100Изобретение относится к вычислительной технике и может быть испольэовано для контроля и исправленияошибок р-кода Фибоначчи,Цель изобретения - расширение функ. 5циональных возможностей за счет обнаружения двойных ошибок и исправления одиночных ошибок в р-коде Фибоначчи при р1.10На фиг. 1 представлена схема устройства для контроля р-кода Фибоначчи; на фиг. 2 - схема блока коррекции; на фиг. 3 - временная диаграмма,поясняющая работу предлагаемого устройства,Устройство (фиг. 1) содержит спервого по третий регистры 1-3 сдвига, блок 4 коррекции, с первого пошестой элементы И 5-10, второй счетчный триггер 11, третий счетный триггер 12, первый счетный триггер 13,первый и второй триггеры 14 и 15,счетчик 16 по модулю, информационныйвход 17 устройства, входы 18 и 19 пер.25вого и второго контрольных разрядовустройства соответственно, вход 20начальной установки устройства, тактовый вход 21 устройства, третий,первый, второй,.шестой, седьмой, четвертый и пятый входы 22-28 блока 4коррекции соответственно, информационный выход 29 устройства, выход30 ошибки в информационных разрядахустройства, выход 31 ошибки в конт 35рольных разрядах устройства, вы.ход 32 неисправимой ошибки устройства.Счетчик 16 работает по модулю(п+5), и - разрядность входного кода, 40без учета контрольных разрядов.Блок 4 коррекции (фиг. 2) содержит,первый, второй и третий элементыИ 33-35, первый, второй и третийэлементы ИЛИ 36-38, элемент 39 запрета, дешифратор 40, сумматор 41по модулю два.В фибоначчиевой р-системе счисления существует единственная, такназываемая минимальная форма (Мформа) представления. натуральногочисла, в которой между соседнимиединичными разрядами следует не ме"нее р нулей. Нарушение этого свойстваМ-формы и.позволяет обнаруживать ошибки в р-коде Фибонначчи с точностьюдо группы разрядов. При этом не об наруживаются ошибки типа 1 ч О, таккак они не нарушают минимальность 4формы кода. Следовательно, для обнаружения ошибок типа 1- 0 минимальный вес кодовой комбинации должен быть не менее двух. Таким образом, для обнаружения всех однократных ошибок в р-коде Фибоначчи необходимо обеспечить минимальный вес кодовой комбинации, равный двум. Самый простой способ получения таких комбинаций - это умножение исходного кода М-формы на код порождающего полинома (1+Х). При этом каждая единица М-формы будет представлена двумя единицами, т,е. такие коды можно назвать кодами Фибоначчи с дублированием единиц (ФДЕ).Для исправления одиночных ошибок необходимо сохранить свойство М-формы локализации группы с ошибочным разрядоми ввести дополнительные проверки для выявления этого ошибочного разряда. Локализация кодовых групп, содержащих один неисправный разряд, возможна для р-кодов ФДЕ при р1, так как в этом случае структура кода будет представлять пары единичных разрядов, разделенных не менее (р)- нулями.Например; (М-форма без младших нулевых "охранных" разрядов):. М-форма р=2 100100012-ФДЕ 110110011М-форма р=3 10001000013-ФДЕ 11001100011Локализация ошибки происходит с точностью до трех разрядов. Ошибочными считаются группы 111 (означает ошибку 0- 1) и 010 (за исключением кода 2-ФДЕ, в котором возможна ошибочная группа 11111, которая однозначно указывает на ошибку в среднем разряде), Локализация неисправного разряда в обнаруженной ошибочной группе осуществляется с помощью введения двух контрольных разрядов К н и Кч, дополняющих до четности значения разрядов в исходном коде М-формы, стоящих соответственно на нечетных и четных позициях. Это объясняется тем, что появление (исчезновение) единицы в р-коде ФДЕ приводит к появлению (исчезновению) соответствующей единицы в. М-форме при декодировании. Алгоритм кодирования и декодирования кодов ФДЕ описывается следующими выражениями: Й = ш+ ш=о 151010 0 6ние ошибки типа 0 - 1 при ошибочнойгруппе 010. При обнаружении кодовойгруппы 11111 она преобразуется вгруппу 11011.Первый регистр 1 сдвига разрядностью пять предназначен для записипентад входного р-кода ФДЕ. Во второйрегистр 2 сдвига заносятся разрядыдекодированного кода М-формы, а втретий регистр 3 сдвига - ошибочныекодовые группы 010,С помощью элемента И 8 выдепяетсякомбинация согласно (1), а с помощьюэлемента И 7 - комбинация 010. Элементы И 5, 8 и 6 определяют наличиев первом регистре 1 сдвига комбинации11111 и вырабатывают на выходе элемента И 6 единичный сигнал разрешениязаписи константы 11011 в первый регистр 1 сдвига, Второйи третий регистры 2 и 3 сдвига имеют разрядность и.С помощью второго и третьего счетных триггеров 11 и 12 определяетсярезультат свертки по модулю два соответственно нечетных и четных разрядовполучаемого с выхода элемента И 8 кода М-формы с соответствующими контрольными разрядами входного кода.Триггеры 14 и 15 служат для записии хранения кода синдрома ошибки. Счетчик 16 по модулю служит для выработкис выхода переполнения. сигнала разрешения записи в триггеры 14 и 15. Первый счетный триггер 13 разбиваетвходные тактовые импульсы устройствана четные (с инверсного выхода) инечетные (с прямого выхода) для управления работой соответственно третьего и второго счетных триггеров 12,11 и блока 4 коррекции.Блок 4 коррекции осуществляет дешифрацию кода синдрома, исправлениеошибок и выдачу контрольных сигналовв зависимости от анализа типа ошибкипо содержимому второго и третьегорегистров 2 и 3 сдвига - "ошибка" и"Неисправимая ошибка".Реализуемые функции блоком 4коррекции имеют следующие виды,где ш, - значение 1-го разряда Мформы;а - значение х-го разряда кодаФЛЕ.Код ФЛЕ с возможностью исправления единичных ошибок будет иметь следующую структуру: 10 50 функция коррекции ф: фк= н 8Я (РГЗ + РГ 2 РГ 2 , )где й, Сч - соответственно моментпоступления неч тного и четного синхроимпульса Сущность метода контроля и исправления ошибок в коде ФДЕ заключается в следующем. Выявление места и вида ошибочной группы - при преобразовании из кода ФДЕ в М-форму и локализации неисправного разряда - с помощью свертки по модулю два четных и нечетных позиций полученной М-формы с соответствующими контрольными разрядами К., Кц кода ФДЕ. При появлении в коде ФДЕ ошибочной группы 111 при декодировании согласно (1) в коде М-формы образуется соответствующая группа 1, свидетельствующая о наличии ошибки типа О - 1. После анализа количества единиц на четных и нечетных позициях в полученной М-форме и сравнения с входными контрольными разрядами Ки К ц (т.е. анализа синдрома Б= К н + Кя, 8 ц = = К ц + К, где К и К - полученные контрольные разряды при де.;одировании), делается вывод о появлении единицы в четной или нечетной позиции М-формы.При появлении в коде ФДЕ ошибочной группы 010 аналогично происходит анализ синдрома ошибки, Однако при этом возможны два случая. Первый - ошибка типа 1 О. Тогда она приведет к исчезновению единицы в декодированной форме, четность или нечетность позиции которой укажет код синдрома ошибки, а позиция единичного разряда в ошибочной группе - на позицию ошибочного разряда в М-форме. Второй случай - когда произошпа ошибка типа 0 - 1. И тогда код синдрома укажет на отсутствие ошибки в полученной М-форме. Следовательно, такая ошибка не приводит к нарушению М- формы, Ситуация, когда обнаруживает 55 ся ошибочная группа при нулевом коде синдрома, означает наличие ошибки кратности два или более или появле 1510100относительно начала преобразованияЯр, Б ч - значения соответственнонечетного и четного раз 5рядов кода синдрома; РГЗ РГ 2- выходы -х разрядовтретьего и второго регистров 3 и 2 сдвига.Функция сигнала "Ошибка": Фф= РГЗ+ РГ 2 РГ 2 , + Бн Я ч + Бн 8 ч(3) Функция сигнала "Неисправимаяошибка":158 н 8 чф (4)Функция сигнала "Ошибка в контрольных разрядах":Ф= (РГЗ+ РГ 2;,РГ 2,) Бн 8 ч (5) 20Выражение (2) реализуется с помощью элементов И 33-35, ИЛИ 36 и 37и дешифратора 40, Сумматор 41 по модулю два служит для инвертированиявыхода регистра 2 сдвига по единичному значению сигнала коррекции ФВыражение (3) реализовано на элементах И 33, ИЛИ 36 и 38 и дешифраторе 40.Сигнал (4) снимается с четвертоговыхода дешифратора 40, Выражение (5)реализуется с помощью сигнала (3),сигнала с первого выхода дешифрато-ра 40 и элемента 39 запрета,Устроиство (фиг. 1) работает следующим образом,Пусть на информационный вход 17устройства подается, например, 2-кодФДЕ "010011111" (слева старший разряд) с контрольными разрядами К ц = 40,р "охранных" нулей не учитываются)и содержащий неисправный третий идевятый разряды (правильная кодоваякомбинация "110011011"). Предвари"тельно подачей сигнала с входа 20установки в начальное значение контрольные разряды К и К ч заносятсяс входов 18 и 19 соответственно вовторой и третий счетные триггеры 11и 12.Информационные разряды входногокода заносятся в первый регистрсдвига под управлением синхросигналов с тактового входа 21 устройства,По приходу пятого синхроимпульсав первом регистре 1 сдвига устанавливается комбинация "11111". На вьмодах элементов И 5, 8 и 6 устанавливается единичное значение и в регистр 1 сдвига заносится константа 1 1111011 , что соответствует исправлению ошибочного третьего разряда. Единичное значение с выхода элемента И 8 через открытый элемент И 9 переключает второй счетный триггер11 в единичное состояние, а по приходу шестого синхроимпульса заносится во второй регистр 2 сдвига.По приходу восьмого синхроимпульса в регистре 1 сдвига устанавливается комбинация "11001" и на выходе элемента И 8 снова появляется единичный сигнал, который через открытый элемент И 10 переключает в нулевое состояние третий счетный триггер 12, а по приходу девятого синхроимпульса эанесется во второй регистр 2 сдвига.По приходу 11-го синхроимпульса в регистре 1 сдвига устанавливается комбинация "01000" и на выходе элемента И 7 устанавливается единичное значение, которое по приходу 12-го синхроимпульса заносит в третий регистр 3 сдвига.По приходу 14-го синхроимпульса под управлением сигнала переполнения счетчика 16 в триггеры 14 и 15 заносится код "10" синдрома ошибки с выходов счетных триггеров .11 и 12.По приходу 15-го синхроимпульса одновременно с режимом коррекции можно производить анализ следующего входного кода.Блок 4 коррекции (фиг. 2) работает следующим образом.Код синдрома "10" с входов 27 и 28 блока 4 коррекции поступает на выходы дешифратора 40, на втором выходе которого появляется единичный сигнал. По приходу 21-го импульса устанавливается на выходе элемента ИЛИ 37 единичное значение сигнала коррекции Ф согласно (2)поскольку в это время с выхода третьего регистра 3 сдвига на третий вход 22 блока 4 коррекции поступает единичный сигнал, открывающий элемент И 34. Так как в это время на выходе второго регистра 2 сдвига нулевой сигнал, поступающий на первый вход 23 блока 4 коррекции, то на вьмоде сумматора 41 по модулю два устанавливается единичное значение,ч 1510100 10Таким образом, на выходе устройства поступает код "10010001", соответствующий требуемому коду М-формы е 510 15 40 45 50 55 Аналогичным образом устройствоработает при исправлении одиночнойошибки в группе "111". При этом сигнал о наличии ошибки при декодировании поступает с выходов второго регистра 2 сдвига.Единичные значения контрольныхсигналов устанавливаются при появлении условий согласно выражений (3)(5).Устройство обнаруживает все однократные и двухкратные ошибки и большой процент ошибок высшей кратности,а также позволяет исправлять одиночные и некоторые двойные ошибки, зафисключением двуххратных ошибок, приводящих к разрешенной комбинации винформационных разрядах входного кода.Время задержки на устройстве равно(2 Ь+5)0 ч, где Гц - длительность синхроимпульса. Однако при преобразовании потока входных слов задержкауменьшается до 5 Г за счет совмещечния коррекции -го слова и декодирования (+1)-го слова,Формула изобретения 1. Устройство для контроля р-кода Фибоначчи, содержащее три регистра сдвига, блок коррекции и четыре элемента И, причем информационный вход устройства соединен с информационным входом первого регистра сдвига, выходы первого и второго разрядов которого соединены соответственно с первым и вторым входами первого элемента И, тактовый вход устройства соединен с тактовым входом первого регистра сдвига, первый вход второго элемента И соединен с выходом четвертого элемента И, первый вход которого соединен с выходом четвертого разряда первого регистра сдвига, выходы двух старших разрядов второго регистра сдвига соединены соответственно с первым и вторым входами блока коррекции, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет обнаружения двойных ошибок и исправления одиночных ошибок в р-коде Фибоначчи при р1, оно содержит пятый и шестой 20 25 30 35 элементы И, первый, второй и третийсчетные триггеры, первый и второйтриггеры, счетчик по модулю, причемпрямой выход третьего разряда первогорегистра сдвига соединен с третьимвходом первого элемента И, выход которого соединен с вторым входом второго элемента И, инверсный выход третьего разряда, выход четвертого разряда и инверсный выход пятого разряда первого регистра сдвига соединенысоответственно с входами третьегоэлемента И, выход которого соединенс информационным входом третьегорегистра сдвига, выход которого соединен с третьим входом блока коррекции, прямой выход пятого разрядапервого регистра сдвига соединен свторым входом четвертого элементаИ, выход которого соединен с информационным входом второго регистра и спервыми входами пятого и шестогоэлементов И, тактовый вход устройства соединен с тактовыми входами второго и третьего регистров сдвига,с входом первого счетного триггера,со счетным входом счетчика по модулю,выход переполнения которого соединенс входами разрешения записи первогои второго триггеров, выходы которыхподключены соответственно к четвертому и пятому входам блока коррекции,шестой вход которого соединен с прямым выходом первого счетного триггера и с вторым входом пятого элемента И, выход которого подключен ксчетному входу второго счетного триггера, выход которого соединен с информационным входом первого триггера,информационный вход второго триггерасоединен с выходом третьего счетноготриггера, счетный вход которого сое- . динен с выходом шестого элемента И,второй вход которого подключен к инверсному выходу первого счетного триг.гера и к седьмому входу блока коррекции, с первого по четвертый выходыкоторого являются соответственно информационным выходом, выходом ошибкив информационных разрядах, выходомошибки в контрольных разрядах и выходом неисправимой ошибки устройства,входы первого и второго контрольныхразрядов которого соединены соответственно с информационными входамивторого и третьего счетных триггеров,входы разрешения записи которых объединены и соединены с входом началь.151010 ной установки устройства, выход второго элемента И соединен;", с входом разрешения записи первого регистра сдвига, входы первого, второго, четвертого и пятого разрядов которого соединены с входом логической единицы устройства, вход логического нуля которого соединен с входом третьего разряда первого регистра сдвига. 2, Устройство по и. 1, о т л и - ч а ю щ е е с я тем, что блок коррекции содержит три элемента И, три элемента ИЛИ, элемент запрета, де. шифратор и сумматор по модулю два, причем первый и второй входы блока коррекции соединены соответственно с первым и вторым входами первого элемента И, выход которого соединен с первым входом первого элемента ИЛИ, входы дешифратора соединены соответственно с четвертым и пятым входами блока коррекции, третий вход которого соединен с вторым входом первого эле мента ИЛИ, выход которого соединен с первым входом третьего элемента ИЛИ, с первыми входами второго и третьего1 0 12элементов И и с управляющим входом элемента запрета, информационный вход которого соединен с первым выходом дешифратора, второй выход которого подключен к второму входу третьего элемента ИЛИ и к второму входу второго элемента И, выход которого соединен с первым входом второго элемента ИЛИ, второй вход которого подключен к выходу третьего элемента М, второй вход которого соединен с третьим входом третьего элемента ИЛИ и с третьим выходом дешифратора, четвертый выход которого соединен с четвертым выходом блока коррекции, первый выход которого подключен к вьиоду сумматора по модулю два, первый и второй входы которого соединены соответственно с выходом второго элемента ИЛИ и первым входом блока коррекции, шестой и седьмой входы которого соединены с третьими входами соответственно. второго и третьего элементов И, выход элемента запрета является третьим выходом блока коррекции, второй выход которого соеди-.нен с выходом третьего элемента ИЛИ.1510100 Составитель М. ЕелобатоваТехред Л.Олийнык Редактор Е. КоРРектоР С,Черни Папп Заказ 5830/57 Тираж 884 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб д. 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, улГагарина, 101