Изобретение относится к вычислительной технике и может быть использовано для контроля и исправления ошибок 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. входы
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.
Любое натуральное число N в п-разряд- ном 2-коде Фибоначчи представляется в виде
о о ю о
О О
N
Z ai № (0.
I 1
гдеа| Ј{0,1};
0 при П 0; 1 при (1)
902(1 - 1) + рг( - 3) при п 0.
Минимальная форма (М-норма) представления числа в 2-коде Фибоначчи имеет не менее двух О между единичными разрядами, т.е. для каждой 1 М-формы можно выделить группу 100, Если сложить исходный и сдвинутый вправо на один разряд коды М-формы (что соответствует умножению на полином 1 + х ), получают следующее преобразование выделенных групп: 100-НЮ. В полученном коде каждая 1 исходного кода М-формы представлена двумя 1, поэтому его можно назвать 2- кодом Фибоначчи с дублированием 1 (2 - ФОБ). Код 2 - ФОЕ можно записать в виде полинома, полученного в результате умножения полинома М (х) М-формы на образующий полином 1 + х :
Т(х) 21(ai + ai+i)x j BiX1.
I 0
i o
Ki + 5 ail-1;
i i
Ki + 2, 32i
i 1
Sri.
(2)
а Bi -Вы; i 2,n: ai Bi.
(3)
Каждому виду синдрома соответствует свой тип ошибки, которые сведены в таблицуИсходя из таблицы, определяют корректирующую функцию для каждого разряда при четном и нечетном i (i 1n-1): I четное:
Ci(Bi+2 §i+i Bi + Bi+2 61+1 Bi) -SiS2 + + (BiBi-iJ3i-2+ B| Bi-i 81-2) -SiS2 + + Bi+i Bi Bi-i -SiS2 +
+ Bi-2 BM bi bi+i Bi+2;(4)
i нечетное:
25
Cj ( Bi + Bi+i bi)jSi 82 + +{bi bi-1 bi-2 Bj-2) -SiS2 + +81+1 bi bi+1 Si 82 + Ьь-2 bi bi+i bi+2, ( 5)
название | год | авторы | номер документа |
---|---|---|---|
Устройство для свертки кода Фибоначчи | 1988 |
|
SU1585901A1 |
Устройство для контроля 3-кода Фибоначчи | 1987 |
|
SU1439596A1 |
Устройство для контроля принимаемой информации | 1991 |
|
SU1820384A1 |
Устройство для контроля 3-кода Фибоначчи | 1987 |
|
SU1478217A1 |
Преобразователь прямого 1-кода Фибоначчи в обратный 1-код Фибоначчи | 1988 |
|
SU1580560A1 |
Устройство для контроля Р-кодов Фибоначчи | 1988 |
|
SU1533007A1 |
Преобразователь прямого кода в обратный | 1982 |
|
SU1032448A1 |
Устройство для приведения 1-кода Фибоначчи к минимальной форме | 1989 |
|
SU1665515A1 |
Устройство для контроля р-кодовфибОНАччи | 1979 |
|
SU817718A1 |
Устройство для исправления двух ошибок в кодовой комбинации с самоконтролем в системах контроля и передачи информации | 1984 |
|
SU1239721A1 |
Изобретение относится к вычислительной технике и может быть использовано в специализированных ЭВМ для контроля и исправления ошибок в системах передачи данных, использующих коды Фибоначчи. Цель изобретения - расширение области применения за счет возможности исправления одиночных ошибок в 2-коде Фибоначчи с дублированием единиц. Устройство содержит группу триггеров 1, первую группу элементов И 2, вторую группу элементов И 3, третью группу элементов И 4 и четвертую группу элементов И 5, два блока 6.1 и 6.2 свертки по модулю два, дешифратор 7, блок 8 коррекции ошибок, группу элементов ИЛИ 9, элемент ИЛИ 13 с соответствующими связями. Обнаруживаются все одиночные и двойные ошибки и исправляются все одиночные ошибки. 1 з.п. ф-лы, 2 ил.
где Bi ai + ai+i.
При единичной ошибке в коде 2 - ФОЕ могут возникнуть следующие ситуации: 010 - пропадание или появление 1, 111 - появление 1 и ситуация 11111 - появление 1 в среднем разряде, которую можно сразу исправить, преинвестировав средний единичный разряд. Умножение на полином 1 + позволяет обнаружить и локализовать ошибку до группы из трех разрядов. Чтобы локализовать ошибку в группе, необходимо дополнительно выполнить контроль по четности, выделяя два контрольных разряда Ki и Кг. Они несут информацию о четности, выделяя два контрольных разряда, соответственно в нечетных и четных разрядах первоначального кодового слова минимальной формы.
-S.
321- 1:
i 1
К2 Ј a2i; .
i 1
При возникновении ошибки один из этих разрядов нарушен, что приведет к ненулевому синдрому. Синдром определяется по формуле
0
Если одна из корректирующих функций С| имеет единичное значение, что свиде- п тельствует о наличии ошибки, то сложение его с соответствующим значением разряда Bi по модулю два позволяет исправить эту ошибку. В этом заключается суть процедуры исправления ошибок.
с Триггеры 1.1-1.7 предназначены для записи исходного кода.
Элементы И 2.1-2.5 предназначены для получения минимальной формы.
Шесть элементов И группы 3.1-3.6 позволяет выделить из кодового слова группы типа 010, свидетельствующих о наличии ошибки.
Элементы И 4.1-4.4 группы предназначены для выделения трехразрядной кодовой ц группы 111, а элементы 5.1 и 5.2 позволяют выделить пятиразрядную группу 11111.
Блоки 6.1 и 6.2 свертки по модулю два позволяют определить значение синдрома Si 82 согласно (2).
Блок 8 коррекции ошибок и группа элементов ИЛИ 9.1-9.6 предназначены для получения контрольных значений каждого информационного разряда согласно формулам (4) и (5).
Элемент ИЛИ-13 предназначен для вы0
5
деления ненулевого значения одного из контрольных разрядов. Единичный сигнал на его выходе означает наличие ошибки в контролируемом коде.
На входы 10,8 и 10.9 подаются значения контрольных разрядов Ki и «2.
Вход 11 сброса необходим для установки в нулевое состояние триггеров 1.1-1.7.
Устройство (фиг.1) работает следующим образом.
Пусть на информационный вход устройства поступает комбинация 1100110 (соответствующая коду 1001000 М-формы) с ошибкой в четвертом разряде. На входы 10.8 и 10.9 поступают единичные контрольные разряды Ki и Ка. Тогда на выходах элементов И 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 Г 100, соответствующей коду 1001000 М-формы, с ошибкой в пятом разряде, на выходах элементов И 2.1-2.5 устанавливается комбинация 11110.
Выходы элементов И 4.1-4.4 группы будут единичные, кроме первого. Сигнал 1 устанавливается на выходе элемента И 5.2 группы и на выходе элемента ИЛИ 9.4 группы. Этот единичный сигнал с выхода элемента ИЛИ 9.4 группы, поступая на счетный вход триггера 1,5, устанавливает его в правильное нулевое состояние.
Пусть на информационный вход устройства поступает кодовая комбинация 1101110 с ошибкой во втором разряде(соот- ветствующая правильному коду М-формы будет 1001000), поэтому контрольные разряды Ki и Ка, поступающие на входы ТО.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 и устанавливает его в нулевое
5 состояние.
Возникновение ошибки в одном из контрольных разрядов не сказывается на изменении информационных разрядов, поскольку все входы, кроме 16.1. 16.2 или
0 16.3, и все выходы блока 8 коррекции ошибок и элементов И 5.1 и 5.2 группы будут нулевыми. А следовательно, выходы элементов ИЛИ 9.1-9.6 тоже устанавливаются нулевыми, что не меняет состояния тригге5 ров 1.2-1.7.
Таким образом, устройство позволяет исправлять все одиночные ошибки в 2-коде Фибоначчи при сохранении возможности коррекции одиночных ошибок для Р 2
0 (при этом четвертая группа элементов И вырабатывает сигналы обнаружения многократных неисправимых ошибок и в коррекции не участвует).
5 Формула изобретения
0 группу элементов ИЛИ и элемент ИЛИ, причем прямые выходы триггеров группы являются выходами соответствующих разрядов информационного выхода устройства, контрольный выход которого соединен
5 с выходом элемента ИЛИ, прямой выход (i+2)-ro (i 1-n-2, n - разрядность кода) триггера группы соединен с первым входом 1-го элемента И первой группы, вход сброса устройства соединен с входами установки в
0 О триггеров регистра, отличающее- с я тем, что, с целью расширения области применения за счет возможности исправления одиночных ошибок в 2-коде Фибоначчи с дублированием единиц, оно
5 содержит четвертую группу элементов И, дешифратор и блок коррекции ошибок, причем прямой выход (i-H)-ro триггера группы соединен с вторым входом i-ro элемента И первой группы,входы информаци0 онных разрядов устройства соединены с входами установки в 1 соответствующих триггеров группы, входы разрешения записи которых соединены с тактовым входом устройства, с первого по третий входы
5 К-го (К 1-п-1) элемента И второй группы соединены соответственно с инверсным выходом К-го, с прямым выходом (К+1)-го и с инверсным выходом (Кь2)-го триггеров группы, первый и второй входы М-го (М 1-п-3)элемента И третьей группы соедийены соответственно с выходами М-ro и (М+1}-го элементов И первой группы, первый и второй входы 1-го (I 1 -п-5) элемента И четвертой группы соединены соответственно с выходами 1-го, (1+2)-го элементов И третьей группы, выходы нечетных и четных элементов И первой группы соединены соответственно с младшими входами первого и второго блоков свертки по модулю два, старшие входы которых соединены соответственно с входами нечетного и четного контрольных разрядов устройства, выходы первого и второго блоков свертки по модулю два соединены соответственно с входами дешифратора, выходы которого соединены с входами соответствующих разрядов управляющего входа блока коррекции ошибок, входы разрядов первого и второго информационных входов которого соединены соответственно с выходами элементов И третьей и второй групп, К-й выход блока коррекции ошибок соединен с первым входом К-го элемента ИЛИ группы, второй вход i-ro элемента ИЛИ группы соединен с (п-1+21)-м выходом блока коррекции ошибок, (Зп-б)-й выход которого соединен с вторым входом (п-1)-го элемента ИЛИ группы, третий вход 1-го, кроме первого, элемента ИЛИ группы, соединен с (п+2) ()-2)-м выходом блока коррекции ошибок, выход 1-го элемента И четвертой группы соединен с четвертым входом (1+2)-го элемента ИЛИ группы, прямой выход первого триггера группы и выходы элементов ИЛИ группы соединены соответственно со счетными входами триггеров группы, выходы
элементов ИЛИ соединены с соответствующими входами элемента ИЛИ.
ИЛИ группы, входы разрядов второго информационного входа блока коррекции ошибок соединены с первыми входами соответствующих элементов И первой группы, выходы которых и выходы элементов И
второй группы соединены соответственно с выходами блока коррекции ошибок, вход первого разряда управляющего входа которого соединен с вторыми входами элементов И первой группы, вход второго
разряда управляющего входа блока коррекции ошибок соединен с первыми входами (2j-1)-ro и 2j-ro элементов И второй группы (j-четное), вход третьего разряда управляющего входаi блока коррекции
ошибок соединен с первыми входами (2Р- 1)-го и 2Р-го (Р-нечетное) элементов И второй группы, выход М-го элемента ИЛИ группы соединен с вторыми входами 2М-го и (2М + 1)-го элементов И второй группы,
первые входы первого и (п-1)-го элементов И первой группы соединены соответственно с вторыми входами первого и (2п-4)-го элементов И второй группы, второй вход М-го элемента ИЛИ группы соединен с первым входом (М41)-го элемента И первой группы.
Устройство для исправления однократных ошибок р-кодов Фибоначчи | 1985 |
|
SU1361554A1 |
Переносная печь для варки пищи и отопления в окопах, походных помещениях и т.п. | 1921 |
|
SU3A1 |
Устройство для обнаружения и исправления ошибок | 1987 |
|
SU1578811A1 |
Переносная печь для варки пищи и отопления в окопах, походных помещениях и т.п. | 1921 |
|
SU3A1 |
Авторы
Даты
1991-07-07—Публикация
1988-07-05—Подача