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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 5)5 Н 03 М 13/00 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТПРИ ГКНТ СССР ИСАНИЕ ИЗОБРЕТЕНИЯ О УУ СВИДЕТЕЛЬСТВУ ВТО(71) Специальноегическое бюро "литехнического и 1"ч. 25 конструктМодуль" В ститута сколо нницкого по(72) А,П.Стахов, Ви Т,И,Сегнет(54) УСТРОЙСТВФИБОНАЧЧИ ЛЯ КОН ЛЯ 2 роистдляп= блока 1 ч = а( уа (1) 1= Изобретение относится к вычислительной технике и может быть использовано для контроля и исправления ошибок 2-кода Фибоначчи.Целью изобретения является расширение области применения за счет возможности исправления одиночных ошибок в 2-коде Фибоначчи с дублированием единиц.На фиг,1 представлена схема уст ва для контроля 2-кода Фибоначчи ( =7); на фиг,2 - функциональная схема коррекции ошибок,Устройство (фиг,1) содержит группу триггеров 1.1 - 1,7, первую группу элементов И 2.1 - 2.5, вторую группу элементов И 3,1- 3.6, третью группу элементов И 4,1 - 4,4, четвертую группу элементов И 5.1 и 5.2, первый 6.1 и второй 6.2 блоки свертки по модулю два, дешифратор 7, блок 8 коррекции ошибок, группу элементов ИЛИ 9.1 - 9,6. входы 501662009 А 1(57) Изобретение относится к вычислительной технике и может быть использовано в специализированных ЭВМ для контроля и исправления ошибок в системах передачи данных, использующих коды Фибоначчи. Цель изобретения - расширение области применения за счет воэможности исправления одиночных ошибок в 2-коде Фибоначчи с дублированием единиц. Устройство содержит группу триггеров, первую группу элементов И, вторую группу элементов И, третью группу элементов И и четвертую группу элементов И, два блока свертки по модулю два, дешифратор, блок коррекции ошибок, группу элементов ИЛИ, элемент ИЛИ с соответствующими связями. Обнаруживаются все одиночные и двойные ошибки и исправляются все одиночные ошибки. 1 з.п, ф-лы, 2 ил., 1 табл,10,1 - 10,7 информационных разрядов устройства, входы нечетного 10.8 и четного 10,9 контрольных разрядов устройства, вход 11 сброса устройства, тактовый вход 12 устройства, элемент ИЛИ 13, входы 14.1 - 14.4 разрядов первого информационного входа блока 8 коррекции ошибок, входы 15,1 - 15,6 разрядов второго информационного входа блока 8 коррекции ошибок, входы 16,1 - 16,3 разрядов управляющих входа блока 8 коррекции ошибок.Блок 8 коррекции ошибок (фиг.2) содержит первую группу элементов И 17.1 - 17.6, вторую группу элементов И 18.1 - 18.10, группу элементов ИЛИ 19.1 - 19,4,Любое натуральное число И в и-разрядном 2-коде Фибоначчи представляется в ви- деи =- (и/2). О при п 0;1 при п=О; (1) о 2( - 1+р 2( - 3) при и О. Минимальная форма (М-норма) представления числа в 2-коде Фибоначчи имеет не менее двух "0" между единичными разрядами, т;е. для каждой "1" М-формы можно выделить группу 100, Если сложить исходный и сдвинутый вправо на один разряд коды М-формы (что соответствует умножению на полинам.1+ х ), получают следующее преобразование выделенных групп;100-ф.110, В полученном коде каждая "1" исходного кода М-формы представлена двумя "1", поэтому его можно назвать 2- кодом Фибоначчи с дублированием "1" (2 - ФОЕ). Код 2 - ФОЕ можно записать в виде полинома, полученного в результате умножения полинома М (х) М-формы на образующий полином 1+ х п - 1 и - 1 Т(х) =,"), (а+ а+1)Х = ВХ,=О =ОПри единичной ошибке в коде 2 - ФОЕ могут возникнуть следующие ситуации: 010 - пропадание или появление "1", 111 - появление "1" и ситуация 11111 - появление "1" в среднем разряде, которую можно сразу исправить, проинвертировав средний единичный разряд. Умножение на полином 1 + х позволяет обнаружить и локализовать ошибку до группы из трех разрядов, Чтобы локализовать ошибку в группе, необходимо дополнительно выполнить контроль по четности, выделяя два контрольных разряда К 1 и К 2. Они несут информацию о четности, выделяя два контрольных разряда, соответственно в нечетных и четных разрядах первоначального кодового слова минимальной формы,При возникновении ошибки один из этих разрядов нарушен, что приведет к ненулевому синдрому. Синдром оп ределяется по формуле а = В В;=2.п: а 1= 81. (3) гКаждому виду синдрома соответствует свой тип ошибки, которые сведены в таблицуИсходя из таблицы, определяют корректирующую функцию для каждого разряда при четном и нечетном( = 1 п - 1);четное: С = (8+2 8+1 В + В+2 В+1 В) 3152++8+1 Ь Ь+151%+ Ь 2 Ь Ь+1 Ь+2,( 5) Если одна из корректирующих функцийС имеет единичное значение, что свидетельствует о наличии ошибки, то сложениеего с соответствующим значением разрядаВ по модулю два позволяет исправить этуошибку, В этом заключается суть процедурыисправления ошибок,Триггеры 1,1-1,7 предназначены для записи исходного кода.Элементы И 2,1 - 2.5 предназначены дляполучения минимальной формы,Шесть элементов И группы 3.1-3.6 по 40 зволяет выделить из кодового слова группытипа 010, свидетельствующих о наличииошибки.Элементы И 4,1-4.4 группы предназначены для выделения трехразрядной кодовой45 группы 111, а элементы 5.1 и 5.2 позволяютвыделить пятиразрядную группу 11111,Блоки 6,1 и 6,2 свертки по модулю двапозволяют определить значение синдрома51 52 согласно (2),Блок 8 коррекции ошибок и группа элементов ИЛИ 9.1 - 9.6 предназначены дляполучения контрольных значений каждогоинформационного разряда согласно формулам (4) и (5).Элемент ИЛИ 13 предназначен для выделения ненулевого значения одного изконтрольных разрядов. Единичный сигнална его выходе означает наличие ошибки вконтролируемом коде, 16620095 10 15 20 25 30 35 40 45 50 55 На входы 10,8 и 10,9 подаются значения контрольных разрядов К 1 и К 2.Вход 11 сброса необходим для установки в нулевое состояние триггеров 1,1 - 1,7,Устройство (фиг.1) работает следующим образом.Пусть на информационный вход устройства поступает комбинация 1100110 (соответствующая коду 1001000 М-формы) с ошибкой в четвертом разряде. На входы 10,8, и 10.9 поступают единичные контрольные разряды К 1 и К 2, Тогда на выходах элементов И 2.1 - 2,5 получают комбинацию 10000 (два младших "охранных" нулевых разряда М-формы не формируются).Значение синдрома на выходах блоков 6,1 и 6.2 свертки будет 01, Выходы всех элементов И 4.1 - 4,4, 5.1 - 5.2, 3.1 - 3,6, кроме 3.3, будут нулевые. На выходе дешифратора 7 присутствует код 010. На выходы 15,3 и 16,2 блока 8 коррекции ошибок поступают единичные сигналы. Сигнал "1" будет на выходе элементов ИЛИ 19.1, И 18.3, на третьем выходе блока 8 коррекции ошибок и на выходе элемента ИЛИ 9.3, Этот единичный сигнал, поступая на счетный вход триггера 1.4, устанавливает его в единичное состояние, тем самым исправляя ошибку,При поступлении на информационный вход устройства кодовой комбинации 11 11100, соответствующейкоду 1001000 М-формы, с ошибкой в пятом разряде, на выходах элементов И 2,1 - 2,5 устанавливается комбинация 11110,Выходы элементов И 4.1 - 4,4 группы будут единичные, кроме первого, Сигнал "1" устанавливается на выходе элемента И 5,2 группы и на выходе элемента ИЛИ 9,4 группы. Этот единичный сигнал с выхода элемента ИЛИ 9,4 группы, поступая на счетный вход триггера 1,5, устанавливает его в правильное нулевое состояние.Пусть на информационный входустройства поступает кодовая комбинация 1101110 с ошибкой во втором разряде(соответствующая правильному коду М-формы будет 1001000), поэтому контрольные разряды К 1 и К 2, поступающие на входы 10.8 и 10.9 я вля ются еди н ич н ы ми. Н а выходах элементов И 2.1 - 2.5 присутствует комбинация 10011, При этом значение синдрома на выходах блоков 6,1 и 6,2 свертки по модулю два будет 10. Все выходы элементов И 3.1 - 3,6, 4.1 - 4.4, 5.1, 5.2, кроме 4.1, нулевые, На выходе дешифратора 7 имеется код 100. На входы 14.1 и 16,3 блока 8 . коррекции ошибок поступают единичные сигналы. Сигнал "1" устанавливается на выходах элементов ИЛИ 19.1 и И 18,2 (на восьмом выходе блока 8 коррекции ошибок) и на выходе элемента ИЛИ 9,1, Этот единичный сигнал поступает на счетный вход триггера 1.2 и устанавливает его в нулевое состояние,Возникновение ошибки в одном из контрольных разрядов не сказывается на изменении информационных разрядов, поскольку все входы, кроме 16,1, 16,2 или 16,3, и все выходы блока 8 коррекции ошибок и элементов И 5.1 и 5,2 группы будут нулевыми. А следовательно, выходы элементов ИЛИ 9,1 - 9.6 тоже устанавливаются нулевыми, что не меняет состояния триггеров 1,2-1.7,Таким образом, устройство позволяет исправлять все одиночные ошибки в 2-коде Фибоначчи при сохранении возможности коррекции одиночных ошибок для Р2 (при этом четвертая группа элементов И вырабатывает сигналы обнаружения многократных неисправимых ошибок и в коррекции не участвует),Формула изобретения 1, Устройство для контроля 2-кода Фибоначчи, содержащее группу триггеров, с первой по третью группы элементов И, первый и второй блоки свертки по модулю два, группу элементов ИЛИ и элемент ИЛИ, причем прямые выходы триггеров группы являются выходами соответствующих разрядов информационного выхода устройства, контрольный выход которого соединен с выходом элемента ИЛИ, прямой выход (+2)-го ( = 1 - и - 2, и - разрядность кода) триггера группы соединен с первым входом 1-го элемента И первой группы, вход сброса устройства соединен с входами установки в "0" триггеров регистра, о т л и ч а ю щ е е - с я тем, что, с целью расширения области применения за счет возможности исправления одиночных ошибок в 2-коде Фибоначчи с дублированием единиц, оно содержит четвертую группу элементов И, дешифратор и блок коррекции ошибок, причем прямой выход (+1)-го триггера группы соединен с вторым входом -го элемента И первой группы, входы информационных разрядов устройства соединены с входами установки в "1" соответствующих триггеров группы, входы разрешения записи которых соединены с тактовым входом устройства, с первого по третий входы К-го (К = 1-и - 1) элемента И второй группы соединены соответственно с инверсным выходом К-го, с прямым выходом (К+1)-го ис инверсным выходом (К+2)-го триггеровгруппы, первый и второй входы М-го (М = =1 - и - 3) элемента И третьей группы соеди 1662009нены соответственно с выходами М-го и (М+1)-го элементов И первой группы, первый и второй входы 1-го ( = 1-и) элемента И четвертой группы соединены соответственно с выходами 1-го, (1+2)-го элементов И третьей группы, выходы нечетных и четных элементов И первой группы соединены соответственно с младшими входами первого и второго блоков свертки по модулю два, старшие входы которых соединены соответственно с входами нечетного и четного контрольных разрядов устройства, выходы первого и второго блоков свертки по моду,лю два соединены соответственно с входами де шифратора, выходы которого соединены с входами соответствующих разрядов управляющего входа блока коррекции ошибок, входы разрядов первого и второго информационных входов которого соединены соответственно с выходами элементов И третьей и второй групп, К-й выход блока коррекции ошибок соединен с первым входом К-го элемента ИЛИ группы, второй вход -го элемента ИЛИ группы соединен с (и - 1+21)-м выходом блока коррекции ошибок, (Зп - 6)-й выход которого соединен с вторым входом (и - 1)-го элемента ИЛИ группы, третий вход 1-го, кроме первого, элемента ИЛИ группы соединен с (и+2) (1 - 2)-м выходом блока коррекции ошибок, выход 1-го элемента И четвертой группы соединен с четвертым входом (+2)-го элемента ИЛИ группы, прямой выход первого триггера группы и выходы элементов ИЛИ группы соединены соответственно со счетными входами триггеров группы, выходы элементов ИЛИ соединены с соответствующими входами элемента ИЛИ,2. Устройство по п,1, от л и ч а ю ще ес я тем, что блок коррекции ошибок содер 5 жит первуюи вторую группы элементов И игруппу элементов ИЛИ, причем входы разрядов первого информационного блокакоррекции ошибок соединены с первымивходами соответствующих элементов10 ИЛИ группы, входы разрядов второго информационного входа блока коррекцииошибок соединены с первыми входами соответствующих элементов И первой группы, выходы которых и выходы элементов И15 второй группы соединены соответственнос выходами блока коррекции ошибок, входпервого разряда управляющего входа которого соединен с вторыми входами элементов И первой группы, вход второго20 разряда управляющего входа блока коррекции ошибок соединен с первыми входами (2)-1)-го и 2)-го элементов И второйгруппы -четное), вход третьего разрядауправляющего входа блока коррекции25 ошибок соединен с первыми входами (2 Р -1)-го и 2 Р-го (Р-нечетное) элементов И второй группы, выход М-го элемента ИЛИгруппы соединен с вторыми входами 2 М-гои (2 М + 1)-го элементов И второй группы,ЗО первые входы первого и (и - 1)-го элементовИ первой группы соединены соответственно с вторыми входами первого и (2 п - 4)-гоэлементов И второй группы, второй входМ-го элемента ИЛИ группы соединен с пер 35 вым входом (М+1)-го элемента И первойгруппы.1662009Составитель А. Клюев Редактор Н, Рогулич Техред М,Моргентал Корректор М. Кучерява каз 2137 Тираж 461 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СС113035, Москва, Ж, Раушскаянаб., 4/5Производственно-издательский комбинат "Патент". г Ужгооод, чл.Гагарина, 10