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

 

Изобретение относится к вычислительной технике и может быть использовано в специализированных ЭВМ для контроля и исправления ошибок в системах передачи данных, использующих коды Фибоначчи. Цель изобретения - расширение области применения за счет возможности исправления одиночных ошибок в 2-коде Фибоначчи с дублированием единиц. Устройство содержит группу триггеров 1, первую группу элементов И 2, вторую группу элементов И 3, третью группу элементов И 4 и четвертую группу элементов И 5, два блока 6.1 и 6.2 свертки по модулю два, дешифратор 7, блок 8 коррекции ошибок, группу элементов ИЛИ 9, элемент ИЛИ 13 с соответствующими связями. Обнаруживаются все одиночные и двойные ошибки и исправляются все одиночные ошибки. 1 з.п. ф-лы, 2 ил.

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

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

РЕСПУБЛИК (5!)5 Н 03 М 13/00

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

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

ПРИ ГКНТ СССР

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

К ABTOPCKOMY СВИДЕТЕЛЬСТВУ и и =,>, ai pz(i), (21) 4454546/24 (22) 05.07.88 (46) 07,07.91, Бюл. ¹ 25 (71) Специальное конструкторско-технологическое бюро "Модуль" Винницкого политехнического института (72) А,П.Стахов, В.А.Лужецкий, П.В.Коэлюк и Т.И.Сегнет (53) 681,3 (088.8) (56) Авторское свидетельство СССР

¹ 1361554, кл. Н 03 M 13/00, 1985, Авторское свидетельство СССР

N 1578811, кл, Н 03 М 13/00, 25.09,87 (прототипи) (54) УСТРОЙСТВО ДЛЯ КОНТРОЛЯ 2-КОДА

ФИБОНАЧЧИ

Изобретение относится к вычислительной технике и может быть использовано для контроля и исправления ошибок 2-кода Фибоначчи.

Целью изобретения является расширение области применения за счет возможности исправления одиночных ошибок в 2-коде Фибоначчи с дублированием единиц.

На фиг.1 представлена схема устройства для контроля 2-кода Фибоначчи (для и =

=7); на фиг,2 — функциональная схема блока коррекции ошибок, Устройство (фиг,1) содержит группу триггеров 1.1 — 1,7, первую группу элементов

И 2.1 — 2.5, вторую группу элементов И 3 13.6, третью группу элементов И 4.1 — 4,4, четвертую группу элементов И 5.1 и 5.2, первый

6.1 и второй 6.2 блоки свертки по модулю два, дешифратор 7, блок 8 коррекции ошибок, группу элементов ИЛИ 9.1 — 9,6. входы

„„5U„„1662009 А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 — l7.6, вторую груп и у эл ем е нто в И 18.1 — 18. 10, группу элементов ИЛИ 19.1 — 19.4, Любое натуральное число N в и-разрядном 2-коде Фибоначчи представляется в виде

1662009 где а! (0,1);

$1 =К1+ аг|-1;

| =1

Б1 =Ki + g ai (2) (4) где В| = а! + а|+1.

К1= аг|-1:

I=1

K2 = а2|, i =1

m =- Сп/2).

0 при п<0; (i)= 1 при и=0; (1) (i — 1)+ (i — 3) при и >О.

Минимальная форма (М-норма) представления числа в 2-коде Фибоначчи имеет не менее двух "0" между единичными разрядами, т.е. для каждой "1" М-формы можно выделить группу 100, Если сложить исходный и сдвинутый вправо на один разряд коды M-формы (что соответствует умножению на полинам.1+ х ), получают следующее преобразование выделенных групп;

100-".110. В полученном коде каждая "1" исходного кода M-формы представлена двумя "1", поэтому его можно назвать 2кодом Фибоначчи с дублированием "1" (2—

ФОЕ). Код 2 — ФОЕ можно записать в виде полинома, полученного в результате умножения полинома M (x) M-формы на образующий полином 1 + х

-1, п — 1 n — 1

T(x) =,"), (а!+ а|+1)Х =, >, В|Х, |=о |=о

При единичной ошибке в коде 2 — ФОЕ могут возникнуть следующие ситуации: 010— пропадание или появление "1", 111 — появление "1" и ситуация 11111 — появление "1" в среднем разряде, которую можно сразу исправить, проинвертировав средний единичный разряд. Умножение на полином

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

При возникновении ошибки один из этих разрядов нарушен, что приведет к ненулевому синдрому. Синдром on ределяется по формуле а! = В! В|-1;! =2.п: а1= 81. (3) Каждому виду синдрома соответствует свой тип ошибки, которые сведены в таблицу

Исходя из таблицы, определяют корректирующую функцию для каждого разряда при четном и нечетном i (1 = 1„...п — 1); I четное:

С! =(8|+2 Bi+1 В|+ В|+2 Bi+1 В|) S1S2+

+ (В! Bi-1 Bl — 2+ Bl Bi — 1 Bl — 2) S1S2+

+ BI+1 Bl Bl 1 $1$2+

+ Bl г Bl 1 Ь! Ь!+1 Bi+2

i нечетное:

С| = (6|+2 Bi+1 Bi + bi+2 Bi+1 Ь!) $1 S2 +

+(Ь! Ь! — 1 Ь! — 2+ В| Ь! — 1 Bi — 2) S1S2+

+8!+1 Ь! bi+1 S1 S2 + Ь -г Ь! bi+1 bi+2, (5) Если одна из корректирующих функций

Ci имеет единичное значение, что свидетельствует о наличии ошибки, то сложение его с соответствующим значением разряда

Bi no модулю два позволяет исправить эту ошибку, В этом заключается суть процедуры исправления ошибок, Триггеры 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 свертки по модулю два позволяют определить значение синдрома

S1 S2 согласно (2), Блок 8 коррекции ошибок и группа элементов ИЛИ 9.1 — 9.6 предназначены для получения контрольных значений каждого информационного разряда согласно формулам (4) и (5).

Элемент ИЛИ 13 предназначен для выделения ненулевого значения одного из контрольных разрядов. Единичный сигнал на его выходе означает наличие ошибки в контролируемом коде.

1662009

55

На входы 10,8 и 10,9 подаются значения контрольных разрядов К1 и К2.

Вход 11 сброса необходим для установки в нулевое состояние триггеров 1,1 — 1,7, Устройство (фиг.1) работает следующим образом.

Пусть на информационный вход устройства поступает комбинация 1100110 (соответствующая коду 1001000 М-формы) с ошибкой в четвертом разряде. На входы

10.8, и 10.9 поступают единичные контрольные разряды К1 и Kz. Тогда на выходах элементов И 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, устанавливает его в единичное состояние, тем самым исправляя ошибку, При поступлении на информационный вход устройства кодовой комбинации

1111100, соответствующей коду 1001000

М-формы, с ошибкой в пятом разряде, на выходах элементов И 2.1 — 2,5 устанавливается комбинация 11110, Выходы элементов И 4.1 — 4.4 группы будут единичные, кроме первого, Сигнал "1" устанавливается на выходе элемента И 5.2 группы и на выходе элемента ИЛИ 9.4 группы. Этот единичный сигнал с выхода элемента ИЛИ 9,4 группы, поступая на счетный вход триггера 1,5, устанавливает его в правильное нулевое состояние.

Пусть на информационный входустройства поступает кодовая комбинация

1101110 с ошибкой во втором разряде (соответствующая правильному коду М-формы будет 1001000), поэтому контрольные разряды К1 и Kz, поступающие на входы 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-коде

Фибоначчи при сохранении возможности коррекции одиночных ошибок для P > 2 (при этом четвертая группа элементов И вырабатывает сигналы обнаружения многократных неисправимых ошибок и в коррекции не участвует).

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

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

i-ro элемента И первой группы, вход сброса устройства соединен с входами установки в

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

К-го (К = 1-и — 1) элемента И второй группы соединены соответственно с инверсным выходом К-ro, с прямым выходом (K+1)-го и с инверсным выходом (К+2)-го триггеров группы, первый и второй входы 5, i-го (M =

=1 — n — 3) элемента И третьей группы соеди1662009 нены соответственно с выходами M-ro u (М+1)-го элементов И первой группы, первый и второй входы I-ro (I = 1-и-5) элемента

И четвертой группы соединены соответственно с выходами I-ro, (1+2)-го элементов И третьей группы, выходы нечетных и четных элементов И первой группы соединены соответственно с младшими входами первого и второго блоков свертки по модулю два, старшие входы которых соединены соответственно с входами нечетного и четного контрольных разрядов устройства, выходы первого и второго блоков свертки по моду,лю два соединены соответственно с входами де шифратора, выходы которого соединены с входами соответствующих разрядов управляющего входа блока коррекции ошибок, входы разрядов первого и второго информационных входов которого соединены соответственно с выходами элементов И третьей и второй групп, К-й выход блока коррекции ошибок соединен с первым входом К-го элемента ИЛИ группы, второй вход i-го элемента ИЛИ группы соединен с (n — 1+21)-м выходом блока коррекции ошибок, (3n — 6)-й выход которого соединен с вторым входом (п — 1)-ro элемента

ИЛИ группы, третий вход I-го, кроме первого, элемента ИЛИ группы соединен с (и+2) (I — 2)-м выходом блока коррекции ошибок, выход I-ro элемента И четвертой группы соединен с четвертым входом (I+2)-го элемента ИЛИ группы, прямой выход первого триггера группы и выходы элементов ИЛИ группы соединены соответственно со счетными входами триггеров группы, выходы элементов ИЛИ соединены с соответствующими входами элемента ИЛИ, 2. Устройство по п.1, о.т л и ч а ю щ е ес я тем, что блок коррекции ошибок содер5 жит первую и вторую группы элементов И и группу элементов ИЛИ, причем входы разрядов первого информационного блока коррекции ошибок соединены с первыми входами соответствующих элементов

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

15 второй группы соединены соответственно с выходами блока коррекции ошибок, вход первого разряда управляющего входа которого соединен с вторыми входами элементов И первой группы, вход второго

20 разряда управляющего входа блока коррекции ошибок соединен с первыми входами (2j 1)-го и 2J-го элементов И второй группы (j-четное), вход третьего разряда управляющего входа блока коррекции

25 ошибок соединен с первыми входами (2P—

1)-го и 2Р-го (P-нечетное) элементов И второй группы, выход М-го элемента ИЛИ группы соединен с вторыми входами 2М-го и (2М + 1)-ro элементов И второй группы, 30 первые входы первого и (п — 1)-ro элементов

И первой группы соединены соответственно с вторыми входами первого и (2п — 4)-го элементов И второй группы, второй вход

М-ro элемента ИЛИ группы соединен с пер35 вым входом (М+1)-ro элемента И первой группы.

1662009

1662009

Составитель А. Клюев

Техред М,Моргентал

Корректор М. Кучерявая

Редактор Н, Рогулич

Производственно-издательский комбинат "Патент". г. Ужгооод. vn.Ãàãàðèíà, 101

Заказ 2137 Тираж 461 Подписное

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

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