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

 

Изобретение относится к вычислительной технике. Цель изобретения - расширение функциональных возможностей за счет обнаружения двойных ошибок и исправления одиночных ошибок в р-коде Фибоначчи при P *981. Устройство содержит регистры 1-3 сдвига, блок 4 коррекции, элементы И 5-10, счетные триггеры 11-13, триггеры 14,15, счетчик 16 по модулю с соответствующими связями. 1 з.п. ф-лы, 3 ил.

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

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

РЕСПУБЛИК (51)4 Н 03 М 13 00

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

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

20/8 19

Фиг./ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И OTHPbITHRM

ПРИ ГКНТ СССР

1 (21) 4357494/24-24 (22) 04.01.88 (46) 23.09.89. Бюл. Р 35 (71) Специализированное конструкторско-технологическое бюро "Модуль"

Винницкого политехнического института и Винницкий политехнический институт (72) А.П. Стахов, В.А. Лужецкий и П.В. Козлюк (53) 681.3(088.8) (56) Авторское свидетельство СССР

Р 1361554, кл. Н 03 M 13/00, 1985.

Авторское свидетельство СССР

У 1439596, кл. Н 03 М 13/00, 07.05.87.

„„SU, 1510100 А1

2 (54) УСТРОЙСТВО ДЛЯ КОНТРОЛЯ р-КОДА

ФИБОНАЧЧИ (57) Изобретение относится к вычислительной технике. Цель изобретения— расширение функциональных возможностей за счет обнаружения двойных ошибок и исправления одиночных ошибок в

; р-коде Фибонначчи при р > 1. Устройство содержит регистры 1-3 сдвига, блок 4 коррекции, элементы И 5-10, счетные триггеры 11-13, триггеры 14, 15 счетчик 16 по модулю с соответствуюцими связями. 1 з.п. ф-лы, 3 ил. з 1510100

Изобретение относится к вычислительной технике и может быть испольэовано для контроля и исправления ошибок р-кода Фибоначчи, Цель изобретения — расширение функ. 5 циональных возможностей за счет обнаружения двойных ошибок и исправления одиночных ошибок в р-коде Фибоначчи при р > 1.

На фиг. 1 представлена схема устройства для контроля р-кода Фибоначчи; на фиг. 2 — схема блока коррекции; на фиг. 3 — временная диаграмма, поясняющая работу предлагаемого устройства.

Устройство (фиг. 1) содержит с первого по третий регистры 1-3 сдвига, блок 4 коррекции, с первого по шестой элементы И 5-10, второй счет- 20 чный триггер 11, третий счетный триггер 12, первый счетный триггер 13, первый и второй триггеры 14 и 15, счетчик 16 по модулю, информационный вход 17 устройства, входы 18 и 19 пер-25 вого и второго контрольных разрядов устройства соответственно, вход 20 начальной установки устройства, тактовый вход 21 устройства, третий, первый, второй,.шестой, седьмой, чет- 30 вертый и пятый входы 22-28 блока 4 коррекции соответственно, информа-. ционный выход 29 устройства, выход

30 ошибки в информационных разрядах устройства, выход 31 ошибки в конт35 рольных разрядах устройства, вы.ход 32 неисправимой ошибки устройства.

Счетчик 16 работает по модулю (п+5), n — разрядность входного кода, 40 без учета контрольных разрядов.

Блок 4 коррекции (фиг. 2) содержит, первый, второй и третий элементы

И 33-35, первый, второй и третий элементы ИЛИ 36-38, элемент 39 за- 4 прета, дешифратор 40, сумматор 41 по модулю два.

В фибоначчиевой р-системе счисления существует единственная, так называемая минимальная форма (Мформа) представления. натурального числа, в которой между соседними единичными разрядами следует не менее р нулей. Нарушение этого свойства

М-формы и.позволяет обнаруживать ошибки в р-коде Фибонначчи с точностью до группы разрядов. При этом не об наруживаются ошибки типа 1ч О, так как они не нарушают минимальность

4 формы кода. Следовательно, для обнаружения ошибок типа 1 0 минимальный вес кодовой комбинации должен быть не менее двух. Таким образом, для обнаружения всех однократных ошибок в р-коде Фибоначчи необходимо обеспечить минимальный вес кодовой комбинации, равный двум. Самый простой способ получения таких комбинаций— это умножение исходного кода И-формы на код порождающего полинома (1+Х).

При этом каждая единица М-формы будет представлена двумя единицами, т,е. такие коды можно назвать кодами Фибоначчи с дублированием единиц (ФДЕ).

Для исправления одиночных ошибок необходимо сохранить свойство M-формы локализации группы с ошибочным разрядом и ввести дополнительные проверки для выявления этого ошибочного разряда. Локализация кодовых групп, содержащих один неисправный разряд, возможна для р-кодов ФДЕ при р > 1, так как в этом случае структура кода будет представлять пары единичных разрядов, разделенных не менее (р-1)— нулями.

Например; (M-форма без младших нулевых "охранных" разрядов): . M-форма p=2 10010001

2-ФДЕ 110110011

M-форма р=3 1000100001

3-ФДЕ 11001100011

Локализация ошибки происходит с точностью до трех разрядов. Ошибочными считаются группы 111 (означает ошибку 0 1) и 010 (за исключением кода 2-ФДЕ, в котором возможна ошибочная группа 11111, которая однозначно указывает на ошибку в среднем разряде). Локализация неисправного разряда в обнаруженной ошибочной группе осуществляется с помощью введения двух контрольных разрядов К н и Кч, дополняющих до четности значения разрядов в исходном коде М-формы, стоящих соответственно на, нечетных и четных позициях. Это объясняется тем, что появление (исчезновение) единицы в р-коде ФДЕ приводит к появлению (исчезновению) соответствующей единицы в. М-форме при декодировании.

Алгоритм кодирования и декодирования кодов ФДЕ описывается следующими выражениями:

151010

50

5 п

K> = (g шг) mod2;

1 л/z

K „(;» m .„) mod 2, !

=о где m,. — значение i ãî разряда Мформы;

d - значение i-го разряда кода

ФДЕ.

Код ФДЕ с возможностью исправления единичных ошибок будет иметь следующую структуру: к„, к„, а„, а „,, ..., а, Сущность метода контроля и исправления ошибок в коде ФДЕ заключается в следующем. Выявление места и вида ошибочной группы — при преобразовании из кода ФДЕ в М-форму и локализации неисправного разряда — с помощью свертки по модулю два четных и нечетных позиций полученной М-формы с соответствующими контрольными разрядами К.„, Кц кода ФДЕ. При появлении в коде ФДЕ ошибочной группы 111 при декодировании согласно (1) в коде M-формы образуется соответствующая группа 1, свидетельствующая о наличии ошибки типа 0 -1. После анализа количества единиц на четных и нечетных позициях в полученной

М-форме и сравнения с входными контрольными разрядами K „ и К ц (т.е. анализа синдрома S„ = К н + Kí, S÷ =

= К ц + К„, где К „и К„- полученные контрольные разряды при де.;одировании), делается вывод о появлении единицы в четной или нечетной позиции M-формы.

При появлении в коде ФДЕ ошибочной группы 010 аналогично происходит анализ синдрома ошибки. Однако при этом возможны два случая. Первый— ошибка типа 1 О. Тогда она приведет к исчезновению единицы в декодированной форме, четность или нечетность позиции которой укажет код синдрома ошибки, а позиция единичного разряда в ошибочной группе — на позицию ошибочного разряда в M-форме. Второй случай — когда произошпа ошибка типа 0 » I И тогда код синдрома укажет на отсутствие ошибки в полученной М-форме. Следовательно, такая ошибка не приводит к нарушению Mформы. Ситуация, когда обнаруживает55 ся ошибочная группа при нулевом коде синдрома, означает наличие ошибки кратности два или более или появле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 кода M-формы с соответствующими контрольными разрядами входного кода.

Триггеры 14 и 15 служат для записи и хранения кода синдрома ошибки. Счетчик 16 по модулю служит для выработки с выхода переполнения. сигнала разрешения записи в триггеры 14 и 15. Первый счетный триггер 13 разбивает входные тактовые импульсы устройства на четные (с инверсного выхода) и нечетные (с прямого выхода) для управления работой соответственно третьего и.второго счетных триггеров 12, 11 и блока 4 коррекции.

Блок 4 коррекции осуществляет дешифрацию кода синдрома, исправление ошибок и выдачу контрольных сигналов в зависимости от анализа типа ошибки по содержимому второго и третьего регистров 2 и 3 сдвига — "ошибка" и

"Неисправимая ошибка".

Реализуемые функции блоком 4 коррекции имеют следующие виды.

Функция коррекции Ф„:

Фк= "н8 Я,.(РГЗ „+ РГ2„РГ2 „, ) +

+ t S„S (РГ3 „+ РГ2„РГ2„, ), (2) где и „ t ч — соответственно момент поступления неч тного и четного синхроимпульса

1510100

oTYoñèòåëüHî начала преобразования;

8„, S ч — значения соответственно нечетного и четного раз5 рядов кода синдрома;

РГЗ,, РГ2 — выходы i-х разрядов третьего и второго регистров 3 и 2 сдвига.

Функция сигнала "Ошибка":

Фо= РГЗ„+ РГ2„РГ2„, + S„S Ä + Бн 8ц(3) Функция сигнала "Неисправимая ошибка":

8н8 ч (4)

Функция сигнала "Ошибка в контрольных разрядах":

Ф „= (РГЗ„+ РГ2;,РГ2 „, ) Бн 8ч . (5) 20

Выражение (2) реализуется с помощью элементов И 33-35, ИЛИ 36 и 3? и дешифратора 40, Сумматор 41 по модулю два служит для инвертирования выхода регистра 2 сдвига по единичному значению сигнала коррекции Ф

Выражение (3) реализовано на элементах И 33, ИЛИ 36 и 38 и дешифраторе 40.

Сигнал (4) снимается с четвертого выхода дешифратора 40. Выражение (5) реализуется с помощью сигнала (3), сигнала с первого выхода дешифрато- ра 40 и элемента 39 запрета.

Устроиство (фиг. 1) работает следующим образом, Пусть на информационный вход 17 устройства подается, например, 2-код ФДЕ "010011111" (слева старший разряд) с контрольными разрядами К ц = 40

= О, Кр = 1 согласно кода "10001001", соответствующий М-форме (младшие ,р "охранных" нулей не учитываются)

1 и содержащий неисправный третий и девятый разряды (правильная кодовая комбинация "110011011"). Предварительно подачей сигнала с входа 20 установки в начальное значение контрольные разряды К „и К заносятся с входов 18 и 19 соответственно во второй и третий счетные триггеры 11 и 12.

Информационные разряды входного кода заносятся в первый регистр сдвига под управлением синхросигналов с тактового входа 21 устройства.

По приходу пятого синхроимпульса в первом регистре 1 сдвига устанав.ливается комбинация "11111". На выходах элементов И 5, 8 и 6 устанавливается единичное значение и в регистр 1 сдвига заносится константа

tl CT

11011, что соответствует исправлению ошибочного третьего разряда.

Единичное значение с выхода элемента И 8 через открытый элемент И 9 переключает второй счетный триггер

1i в единичное состояние, а по приходу шестого синхроимпульса заносится во второй регистр 2 сдвига.

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

По приходу 11-ro синхроимпульса в регистре 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", соответствующий требуемому коду М-формы °

10

40

Аналогичным образом устройство работает при исправлении одиночной ошибки в группе "111". При этом сигнал о наличии ошибки при декодировании поступает с выходов второго регистра 2 сдвига.

Единичные значения контрольных сигналов устанавливаются при появлении условий согласно выражений (3)(5).

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

Время задержки на устройстве равно (2h+5)-„. где Гц — длительность синхроимпульса. Однако при преобразовании потока входных слов задержка уменьшается до 5 2 за счет совмещеч ния коррекции i-го слова и декодирования (i+1) -го слова.

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

1. Устройство для контроля р-кода

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

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

И, выход которого соединен с информационным входом второго регистра и с первыми входами пятого и шестого элементов И, тактовый вход устройства соединен с тактовыми входами второго и третьего регистров сдвига, с входом первого счетного триггера, со счетным входом счетчика по модулю, выход переполнения которого соединен с входами разрешения записи первого и второго триггеров, выходы которых подключены соответственно к четвертому и пятому входам блока коррекции, шестой вход которого соединен с прямым выходом первого счетного триггера и с вторым входом пятого элемента И, выход которого подключен к счетному входу второго счетного триггера, выход которого соединен с информационным входом первого триггера, информационный вход второго триггера соединен с выходом третьего счетного триггера, счетный вход которого сое- . динен с выходом шестого элемента И, второй вход которого подключен к инверсному выходу первого счетного триг. гера и к седьмому входу блока коррекции, с первого по четвертый выходы которого являются соответственно информационным выходом, выходом ошибки в информационных разрядах, выходом ошибки в контрольных разрядах и выходом неисправимой ошибки устройства, входы первого и второго контрольных разрядов которого соединены соответственно с информационными входами второго и третьего счетных триггеров, входы разрешения записи которых объединены и соединены с входом началь.151010 ной установки устройства, выход второго элемента И соединен;", с входом разрешения записи первого регистра сдвига, входы первого, второго, четвертого и пятого разрядов которого соединены с входом логической единицы устройства, вход логического нуля которого соединен с входом третьего разряда первого регистра сдвига.

2, Устроиств о no rr ° 1, ч а ю щ е е с.я тем, что блок коррекции содержит три элемента И, три элемента ИЛИ, элемент запрета, де. шифратор и сумматор по модулю два, причем первый и второй входы блока коррекции соединены соответственно с первым и вторым входами первого элемента И, выход которого соединен с первым входом первого. элемента ИЛИ, входы дешифратора соединены соответственно с четвертым и пятым входами блока коррекции, третий вход которого соединен с вторым входом первого эле- 2 мента ИЛИ, выход которого соединен с первым. входом третьего элемента ИЛИ, с первыми входами второго и третьего

0 12 элементов И и с управляющим входом элемента запрета, информационный вход которого соединен с первым выходом дешифратора, второй выход которого подключен к второму входу третьего элемента ИЛИ и к второму входу второго элемента И, выход которого соединен с первым входом второго элемента ИЛИ, второй вход которого подключен к выходу третьего элемента

М, второй вход которого соединен с третьим входом третьего элемента

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

Риа. 2

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

Техред Л.Олийнык

Редактор Е.

Корректор C.вверни

Папп

Заказ 5830/57 Тираж 884 Подписное

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

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

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