Устройство для контроля ошибок в избыточном модулярном коде

 

Изобретение относится к вычислительной технике, может быть использовано в системах связи и обработки информации, оперирующих с модулярными кодами (кодами в системе остаточных классов), позволяет расширить 1 II-I-T. функ1щональные возможности устройства за счет обеспечения исправления ошибок любой заданной кратности. Устройство содержит входной преобразователь 1 кода (из модулярного в позиционный ), блок 3 вычисления поправок и блок 5 анализа. Введение блока 2 преобразования числа в цепную дробь, вычитателя 4 и выходного преобразователя 6 кода (из позиционного в модулярный ) обеспечивает при соответствующей избыточности исходного кода обнаружение и исправление ошибок.Все вычисления производятся в позиционном коде, чем достигается еще и некоторое упрощение устройства. 4 з.п. флы, 5 ил. СО СС О) со 4 СХ) : 3 :ta гз фие

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

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

РЕСПУБЛИК

1511 4 Н 03 М 13/00, 7/18

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

H АBTOPCHOMV СВИДЕТЕЛЬСТВУ

У о

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4095119/24-24 (22) 26.05.86 (46) 30.12.87. Бюл. № 48 (72) С.H.Õëåâíoé (53) 681.326.7(088.8) (56) Авторское свидетельство СССР

¹ 744583, кл. G 06 F 11/08, 1977.

Авторское свидетельство СССР № 377780, кл. G 06 F 11/10, 1970. (54) УСТРОЙСТВО ДЛЯ КОНТРОЛЯ ОШИБОК . В ИЗБЫТОЧНОМ МОДУЛЯРНОМ КОДЕ (57) Изобретение относится к вычис.лительной технике, может быть использовано в системах связи и обработки информации, оперирующих с модулярными кодами (кодами в системе остаточных классов), позволяет расширить

ÄÄSUÄÄ 1363484 А1 функциональные воэможности устройства за счет обеспечения исправления ошибок любой заданной кратности. Устройство содержит входной преобразователь 1 кода (из модулярного в позиционный), блок 3 вычисления поправок и блок 5 анализа. Введение блока 2 преобразования числа в цепную дробь, вычитателя 4 и выходного преобразователя 6 кода (из позиционного в модулярный) обеспечивает при соответствующей избыточности исходного кода обнаружение и исправление ошибок.Все вычисления производятся в позиционном коде, чем достигается еще и некоторое упрощение устройства. 4 з.п. злы, 5 ил.

1363484

x x+Qm; 8; .,) где m — находим из сравнения

m; - - = 1(modp;), Р, (R — некоторое целое число такое, что Р Х Р„. с — P

Обозначая Р = 1 (с и A= m g -„ Д 1 о

1ЕЭ Г

-RP, перепишем (1) в ином виде

»

Х =Х+Р (2) 1

Таким образом, для исправления ошибок необходимо определить величиА

Ну p- e

Преобразуем (2) к виду

Х

", (3)

3 максfX)=Р„,, то, используя записать

Так как (3), можно

А Є— 1 (Р F„

Рп

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

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

В модулярном (п,Е)-коде число Х представляется совокупностью неотрицательных вычетов х,,х,...,х„...,х„ по группе взаимно простых оснований

При этом мощность нулевого пространства кода совпадает с диапазоном I 1 Р, где Р„ =

=И ;

При искажении группы остатков х.;(ЕХ)» .где I — множество, образованное из номеров искаженных разрядных цифр, число Х трансформируется в число Х

I !

Можно записать, что Х =X+AX так (+ как Х ьР, в противном случае Х 6(! к» к являлось бы правильным числом.

Пусть о ; — величина ошибки 1-й разрядной цифры, т. е. х . = 1х;+ 8; Р;

16I тогда х

Если -- — действительное положиР„ тельное число и Рэ и Цэ — целые положительные взаимно простые числа, таХ Ps кие, что -- ф - и

Р„

Х Р 1 с (4)

Q5 9

Ps то -- является подходящей дробью

Ь

S-го порядка цепной дроби, в которую

Х

1г — может быть разложено. и

Сравнивая (3) и (4), замечаем,что если Р (-- — "--- =Р, то — = - Следовательно, процедура контроля

20 ошибок в модулярном коде может быть

Х процедурой разложения . — в цепную и дробь:

Х Г 1» 1

25 — =(а 8, ° ° э Ь +

p »» °

Q, +

Ь +е ° °

Используя полученную цепную дробь .(а,а,,...j, последовательно строим подходящие дроби —, а когда окажет S ся что

О Х (5)

»

Pq А

35 следовательно, 5

Всегда а, =0, а Р и Я могут быть вычислены как

-5 - S S6- Р6-, »

» 6 6-(+ 5 2 Р„1

Известно,что Я всегда больше 2

Поэтому, так как P с -- —, следо2(Р -11 к вательно, $ ax(s11og — -- . (6)

Р, 50

Выражение (6) определяет максималь

Х ное число членов разложения — в цепР„ ную дробь (а,а, ...,, которая в по55 следующем используется для построеР ния дроби - . При этом процесс вычиЯ

Рэ сления подходящей дроби - - может

1 363484 происходить одновременно с разложеX вием = в (а,а,...).

11

Пример. Основаниями модуляр-ного кода выберем числа

, =7,, =8,, =11, P4=-13р PAL=15«

16 17«17 19

Для этОЙ системы когда р 4 p5 6 )Q

P — избыточные основания, Р =6!6, Р„=38798760, а произведение оснований, остатки по которым можно исправить, должно быть меньше 177. Таким образом, искажение любого одного остатка всегда исправимо, а также ис— правимы искажения в любых двух остатках по основаниям p,, p, р.« « à -,ÿêже по Основаниям f), $4 « p, p j p, >

16«1> «pt«1а «J4« >««t$« ь«|16«pz «2О

Р « f3 «Р4«Р «(5

Пусть задано число X=511-(0«7,5,4, 1,1,17), в результате искажения которого получйлось число Х =2645881-(О, !,7,4,1,1,17).

2645881

Раскладываем число †††-- в цеп38798760 ную дробь

38798760=14 2645881+1756426, а,=141

2645881=1:1756426+889455, а =1;

1756426=1 889455+866971, а:,=1;

889455=1.866971+22484„ а,=l;

866971=38 22484+12579, а =38 и т.д.

Соответственно для цепной дроби (О« 14, 1, 1, 1, 38,...J

Р, 1 ц 14

2645881-27/1340=-125459<

«О, так как получилось отрицательное число, то продолжаем вычислять подходящие дроби; .Б

264588!-2586584=59297>

r618, полученное значение не удовлетворяет условию и, следовательно, переходим к следующему шагу; 45

Р, 2 Р«1 — так как — не является

29 29 целым числом, то процесс вычисления подходящих дробей продолжаем (при этом также 2645881-267577«6=298995,5);50

-4- = gg, 2645881-2645370=511<616« 4 следовательно, исходное значение числа Х равно 511, На фиг. 1 приведена функциональная схема устройства для контроля

Ошибок в избыточном модулярном коде; на фиг. 2 - пример выполнения блока преобразования числа в цепную дробь; на фиг. 3 -- пример выполнения блока анализа; на фиг. 4 — пример выполнения блока вычисления поправки; на фиг. 5 — пример выполнения блока преобразования цепной дроби.

Устройство для контроля ошибок в избыточном модулярном коде содержит входной преобразователь 1 кода> блок

2 преобразования числа в цепп N дробь, блок 3 вь;числения поправки, вычитатель 4, блок 5 анализа и выходной преобразователь 6 кода. На фиг. 1 обозна .ены информациолые входы 7,,.ервые 8, вторые 9 и третьи 1С установочные гходы, контрол>ьн>, е ьыходы

11, первые 12 и вто;и з 13 информационные выходы.

Входной преобразователь кода обеспечивает преобразования кода г.

f остатках,модулярного кода ) в позиционный кс,-., например, двоичный.

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

Блок 2 преобразования числа в цепí..I0 дробь (фиг. 2) выпалнеH на регистре 14 сдвига, состоящем из трех ячеек 14.1-14.3, каждая из котсрых имеет разрядность не менее J."îð Г .> n . .« вычитателе 15«делителе 16 и перемножителе 17. На фиг. 2 обозначены информационные входы 18, управляющие входь. 19 и выходы 20 блока. Ьхоцы предварительной записи в ячейку 14.3 не показаны. При появлении импульса на входе 19.1 происходит запись в ячейку 14.3 кода числа с выходов бло-ка 16, при этом содержимое остальных ячеек регистра 14 остается неизменным. При появлении импульса »а входе

19.2 содержимое регистра 14 передвигается на одну ячейку влево. Блоки

15-!7 могут быть выполнены -как в комбинационном, так и регистровых вариа.. тах.

Блок 5 анализа (фиг. 3) выполнен на первом ?l и втором 2? Элементах сравнения, генераторе 23 импульсов и элементе И 24. На фиг. 3 обозначены первые 25 и вторые 26 информационные входы и управляющие выходы 27 блока.

Если код на входах 26 меньше кода на входах 9, то на выходе элемента 22

3484

5 136 сравнения будет уровень "1", запирающий генератор 23 импульсов. Если код на входах 25 меньше кода Р> на входах 10, то на прямом выходе элемента 21 будет уровень "0". Генератор 23 генерирует двухфазную последовательность импульсов на выходах

27.1 и 27.2.

Блок 3 вычисления поправок (фиг. 4) выполнен на первом 28 и втором 29 преобразователях кода, делителе 30 и перемножителе 31. На фиг. 4 обозначены информационные входы 32, управляющие входы 33, первые 34 и вторые 35 выходы блока. Делитель 30 и перемножитель 31 могут быть выполнены известным способом, при этом перемножитель 31 имеет шину блокировку (не показана), посредством которой на его выходе можно обеспечить появление кода числа 0 независимо от значений переменных на его ьходах.

Преобразователи 28 и 29 .кода выполнены каждый (фиг. 5) на регистре

Зб сдвига, аналогичном регистру 14 блока 2, перемножителе 37 и сумматоре 38. На фиг. 5 обозначены информационные входы 39 и выходы 40 преобразователя.

Выходной преобразователь 6 кода служит для преобразования позиционного кода (например, двоичного), в котором функционируют блоки 2-5, в исправленный модулярный код, аналогичный входному коду. Этот преобразователь, как и входной преобразователь

1, может быть выполнен в комбинационном или регистровом виде.

Устройство для контроля ошибок в избыточном модулярном коде работает следующим образом.

В исходном состоянии на входах 7 установлены коды остатков х,...,х (1 соответственно, которые определяют число Х . Число Х =Х, если ни один ! ( ( из остатков не искажен, либо Х 1 Х, если искажен один или несколько остатков н представлении числа Х . За( дачей работы устройства является коррекция искаженных остатков с целью преобразования Х в Х. Через время, I определяемое переходными процессами в преобразователе 1, íà его выходах установится значение числа Х в позиционном (дноичном) коде.

Далее необходимо проверить пра( вильность числа Х . Критерием его

40 правильности является выполнение ус( ловия Х «Р„.

Так как в исходный момент времени перемножитель 31 и генератор 23

I заблокированы, то число Х через вычитатель 4 в неизменном виде поступает на нходы элемента 22 сравнения, который сравнивает его с кодом числа

Р со входов 9. Если Х «Р„, то на вйходах элемента 22 сравнения будет уровень "1", который поступает на выход 11.1 устройства и свидетельствует о том, что нет необходимости в процедуре исправления ошибки. В этом случае число Х может сниматься как с выходов 12 и 13, так и со входов 7. Если окажется, что Х ) Р„, то устройство приступает к первому такту коррекции ошибок.

В первом такте работы устройства в ячейки 14.1, 14.2 и 14.3 регистра

14 записываются коды чисел Р„, Х и

0 соответственно, в ячейки 36.1, 36.2 и 36.3 регистра 36 блока 28 — значения О, 1 и 0 соответственно, а в ячейки 36.1, 36.2 и 36.3 регистра Зб блока 29 значения 1, 0 и 0 соответственно. При этом снимается блокировка с блоков 23 и 31.

Делитель 16 вычисляет отношение

Р(, беэ восстановления остатка, т.е.

Х

Р„ величину -а, которая блоком 17 ум1 ножается на Х и полученная, величина вычитается из Р вычитателем 15. Таким образом с выходов 20 блока 2 разрядная цифра а, цепной дроби (а, а,,...j поступает на входы 33 блока.

При этом блок 28 вычисляет знаменатель Ц,<†- а, подходящей дроби, а блок

29 ее числитель P< =l. Р этот момент времени на выходах блоков 28 и 29 получим значения а и l соответстt венно.

На выходах блока 3 вычисления по. правок после окончания переходных процессов н блоках 30 и 31 имеем

Р. значение -"-, которое вычитается из а, числа Х вычитателем 4.

Если окажется, что Ц, Р,, то на прямом выходе элемента 2! сравнения и соответственно на выходе 11.3 появится уровень "1", означающий, что необходимо отказаться от дальнейшего декодирования вниду невозможности

I исправить число Х, и работа устройства на этом прекращается.

1363484

Если окажется, что Q, P> и Х—

Р

Р, то на выходе элемента 22 а к сравнения и на инверсном выходе эле-. мента 22 сравнения появятся уровни

-"l" âñëåäñòâèå чего на выходе 11.2 также появится уровень "1", означаю(Р щий что Х=Х вЂ” — . Исправленное знаФ а, чение числа Х в позиционном или модулярном коде снимается с выходов 1? или 13 соответственно.

Если окажется, что Ц, Р, à X 3m — Р, то через некоторое время, а, которое необходимо для окончания nepBxopHblx poUe c. BbIpK: помянутых блоках, на выходе 27,1 генератора 23 появится импульс, под действием которого в ячейки 14.3 и 36.3 будут запи1 саны коды чисел г, =Р„-а,Х, а, 1 соответственно (заметим, что ячеек

36.3 две: одна в блоке 28, вторая в блоке 29). А через некоторое время, когда закончатся переходные процессы в регистрах !4 и 36, появится импульс на выходе 27.2, при этом содержимое регистров 14 и 36 сдвинется на одну ячейку влево.

Соответственно после этого на

ГХ 1 выходах блока 2 имеем a. = =) --, а

Рг А на выходах блока 3 P — =Р— — - —, С ча а,+l

Р

При этом, если Х -Р -- «P и Q P и Р к 2 3щэ

P то соответственно Х=Х -P - и генеТ) Ц ратор 23 блокируется уровнем "1" с выхода элемента 23 сравнения, а на выходе 11.2 появляется уровень "1", означающий окончание процесса коррекции.

Если Q P, то происходит отказ

TYl от дальнейшего декодирования, а если

Р2.

Ц «Р и Х -Р— Р, то устройство и Π— к>

2 продолжит свою работу вышеописанным образом.

Таким образом, предлагаемое устройство позволяет контролировать ошибки любой кратности (при соответствующей величине избыточности). Кроме того, отсутствует ПЗУ и все операции выполняются в двоичном коде, соответственно аппаратурная сложность устройства пропорциональна log Р„ и при росте мощности кода она будет расти медленнее, чем для известных устройств.

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

45 ные входы блока анализа являются соответственно вторыми и третьими установочными входами у стройства, выхо" ды выходного преобразователя кода яв" ляются вторыми информационными выхо50,".„ами устройства.

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

1. Устройство для контроля ошибок в избыточном модулярнэм коде, содержащее входной преобразователь кода, t0 входы которого являются соответствующими информационными входами устройства, блок вычисления поправок, первые выходы которого подключены к первым информационным входам блока анализа, контрольные выходы которого являются контрольными выходами устройства, отличающееся тем, что, с целью расширения функциональных возможностей за счет обеспечения исправления ошибок любой заданной кратности, в устройство введены блок преобразования числа в цепную дробь, вычитатель и выходнои преобразователь кода, выходы входного преобразователя кода подключены к соответствующим первым входам вычитателя и информационным входам блока преоб.разования числа в цепную дробь, выхо-,, ды которого соединены с информационными входами блока вычисления поправок, выходы которого соединены с вторыми входами вычитателя, вь.:ходы кото"рого подключены к соответствующим вторым информационным входам блока анализа, входам выходного преобразова. теля кода и являются первыми информационными выходами устройства, управляющие выходы блока анализа соединены с соответствующими управляющими входам:.блока вычисления поправок и блока преобразования числа в цепную дробь, установочные входы которых соответственно объединены и являются первыми установочными входами устройства, первые и вторые установоч1363484 входам перемножителя и являются выходами блока, выходы второй ячейки регистра сдвига подключены к вторым входам делителя и перемножителя вы5 ходы которого соединены с вторыми входами вычитателя, выходы которого подключены к информационным входам третьей ячейки регистра сдвига, информационные входы первой и второй )p ячеек регистра сдвига являются соответственно установочными и информационными входами блока, входы записи и сдвига регистра сдвига являются соответственно первым и вторым управ- 1 ляющими входами блока.

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

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

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

1363484

Фиг. 2

Фиг. д

1363484

Составитель О.Ревинский

Редактор Т.Пазоренко Техред J1.Сердюкова Корректор И,Муска

Тираж 900 Подписное

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

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

Заказ 6380/54

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4