Устройство для контроля ошибок в избыточном модулярном коде Советский патент 1987 года по МПК H03M13/03 H03M7/18 

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

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

В модулярном (n,k)-кoдe число X представляется совокупностью неотри цательных вычетов х ,Х2,. .. ,х.,.. ,х„ по группе взаимно простых оснований р, ,PJ, ,..., РК, . .. ,р„ . При этом мощность нулевого пространства кода совпадает с диапазоном (р , где Р

п р;.

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

Можно записать, что X -Х+ДХ, так как X feP, в противном случае X6J-| являлось бы правильным числом.

Пусть 5 ; - величина ошибки i-й разрядной цифры, т.е. Х; |х,-+S;| р; , iel, тогда

- Pk

х Х+Х1т;5-, а -RP

ieJР

где m - находим из сравнения

(I)

га

; Kmodp;), Р

R - некоторое целое число такое.

что Р,: Х 6Р„,

, Р,1, , ,Р2 + 1,..., ..« ,PS -agPg-i +PS-J;

Обозначая Р П Р; и .8--5- - Q, а ,,+Q, ,,, ...,Q -a,Q.,+Q,.,.

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

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

(2)

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

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

X А Y

р; - о

(3)

ное число членов разложения

в цеп-

(3),

I

ную дробь ад,а, ,.. . , которая в по- Так как ., то, используя 5 следующем используется для построеможно записать

ния дроби -5.

При этом процесс вычиА

, Р.-1

- Р:

X

Если -- - действительное положи-

п тельное число и Р и Q - целые

ПОЛО

жительные взаимно простые числа, та-

, X , Р

и

X , Рд

кие, что - ф

р;

м

X

Р

Q:

1

Щ

(4)

р

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

5

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

X

-- может быть разложено.

Сравнивая (З) и (4), замечаем,что

то . PI

™ Р 2ГР:Л7 0. -Р., Q,

Следовательно, процедура контроля 20 ошибок в модулярном коде может быть

X процедурой разложения .- в цепную

. п дробь:

25

Х Г-)

p-, а„ +

1

а,+

а2+...

Используя полученную цепную дробь О последовательно строим

ЗЛр

подходящие дроби -- , а когда окажет еся, что

0.5С -Р ,., 35 следовательно, .

Чс

(5)

40

S 3

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

, Р,1, , ,Р2 + 1,..., . ..« ,PS -agPg-i +PS-J;

Q, а ,,+Q, ,,, ...,Q -a,Q.,+Q,.,.

Q, а ,,+Q, ,,, ...,Q -a,Q.,+Q,.,.

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

Поэтому, так как ,.™ , следеО 1 - 1- /

вательно,

-&- .

(6).

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

X

ное число членов разложения

в цеп-

ния дроби -5.

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

происходить одновременно с разложе

Х Г 1 нием -- в ад,а,...J.

п

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

р,7, ., р, П, р 13, р5 15, р-17, р,19.

Для этой системы, когда р , р

Р

р7 - избыточные основания, Р|,, Р 38798760, а произведение оснований, остатки по которым можно исправить, быть меньрле 1.77. Таким образом, искажение любого одного остатка всегда исправимо, а также ис- правимы искажения в любых двух остатках по основаниям Di р2 Рз а также по основаниям р, , р ; р, , р, ,

Ре;, р, ,pi; PI .р4 рг Pfi рг рб р2

Р PI P Р .

Пусть задано число .1-(0,7,5,4,

1,1,17), в результате искажения которого получилось число х 264588 -(о, 1,7,4,1,1,17):

. 2645881

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

38798760 14 2645881- -1756426, а, 4; 2645881 1.- 1756426+889455, а,, 1 ; 1756426 1 889455+866971, а,1; 889455 1-866971+22484, 866971 38-22484+12579, .д.

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

Р I

Q.7 15

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

1 , ..Й2 Т5

6185 полученное значение не удовлетворяет условию и, следовательно, пере2645881-2586584 59297

ходим к следующему шагу; Р, 2 Рп

25

так как

29

2645881-2645370 5 К616,

3

целым числом, то процесс вычисления

подходящих дробей продолжаем (при

этом также 2645881-267577,6 298995,5);50

Р. 3

Q4 5 следовательно, исходное значение чис

ла X равно 511.

На фиг. 1 прйв.едена функциональная йхема устройства для контроля ошибок в избыточном модулярном коде; на фиг. 2 - пример выполнения блока преобразования числа в цепную дробь;

на фиг. 3 - пример выполнения блока анализа; на фиг. 4 - пример выполнения блока вычисления поправки; на

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

10 2 преобразования числа в цепнз1о дробь, блок 3 вычисления поправки, вычита- тель 4, блок 5 анализа и выходной преобразователь 6 кода. На фиг. 1 обозначены информационные входы 7,

15 гервые 8, вторые 9 и третьи 1C уста- нсвочмые кходы, контролт ньге выходы 1 15 первые 12 и вторг 13 информационные выходь;.

Входной преобразователь i кода

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

25 ющего синхронизации, так и в виде многотактного устройства (необходимые при этом цепи синхронизации на графических материалах не показаны, но их наличие ,Щ1Я этого случая под-

30 разумевается).

Блок 2 преобразования числа в цеп- нута дробь (фиг, 2) выполнс.н на регистре 14 сдвига, состоящем из трех ячеек 14.1-14.3, каждая из котсрых

„j- имеет разрядность не менее З- -Обг.пГэ вычитателе 15, делит еле 16 и перемножителе 17. На фиг. 2 обозначены информационные входы 18, управляющие входы 19 и выходы 20 блока. Входы предварительной записи в ячейку 14,3 не показаны. При появлении импульса на входе 19.1 происходит запись в ячейку 14.3 кода числа с выходов блока 16, при этом содержимое остальных ячеек регистра 14 остается неизменным. При появлении импульса на входе не является 19.2 содержимое регистра 14 передвигается на одну ячейку влево. Блоки 15-17 могут быть выполнены как в комбинационном, так и регистровых вари- cii Tax.

2645881-277 1340 -125459

40

45

55

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

„j-

40

„j-

45

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

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

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

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

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

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

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

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

правильности является выполнение условия X Р.

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

заблокированы, то число X через вы-

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

0 Р|. со входов 9. Если , то на выходах элемента 22 сравнения будет уровень 1, который поступает на выход 11.1 устройства и свидетельствует о том, что нет необходимости

5 в процедуре исправления ошибки. В . этом случае число X может сниматься как с выходов 12 и 13, так и со входов 7. Е сли окажется, что X Р, то устройство приступает к первому так-

Q ту коррекции огоибок.

В первом такте работы устройства в ячейки 14.1, 14.2 и 14.3 регистра 14 записываются коды чисел Р,, X и О соответственно, в ячейки 36.1, 36.2

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

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

РП и

без восстановления остатка, т.е.

0

X величину

И-,

которая блоком 17 ум-5 ножается на X

вычитается из Р

и полученная, величина вычитателем 15. Таким образом с выходов 20 блока 2 разрядная цифра а, цепной дроби а, а, ,.. .2 поступает на входы 33 блока. 0 При этом блок 28 вычисляет знаменатель Q,a, подходящей дроби, а блок 29 ее числитель Р( 1 В этот момент времени на выходах блоков 28 и 29 получим значения а и 1 соответст- 5 венно.

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

значение -0

а

которое вычитается из

числа х вычитателем 4.

Если окажется, что Qt Pj

то на

m

прямом выходе элемента 21 сравнения и соответственно на выходе 11.3 по- g явится уровень 1, означающий, что необходимо отка заться от дальнейшего декодирования ввиду невозможности исправить число X , и работа устройства на-этом прекращается.

il 5- Р

a. I

Если окажется, что Q и Х Jm

22

то на выходе элемента

сравнения и на инверсном выходе элемента 22 сравнения появятся уровни 1,вследствие чего на выходе 11.2

уровень Р

1

-:

Э.|

11 1 i

1

означаю

Исправленное значение числа X в позиционном или модулярном, коде снимается с выходов 1. или 13 соответственно.

Если окажется, что Q,, , а Х то через некоторое время,

13 -р

а,

k

Xll Ir, J

на выходах блока 3 Р - Н.- -тт-,

h

г Qz

1

а

а

2v

а, +Т

При этом,

и

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

Соответственно после этого на выходах блока 2 i-шеем а.

Q-РТ

2 Jm

если Х -Р„ 1 Р г.

то соответственно -Р -- и гене-

У.г

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

Если происходит отказ от дальнейшего декодирования, а если

Q,P.,

и X -Р„ 2. р m 0.2,

, то устройство

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

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

расти медленнее, устройств.

чем для известных

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

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

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

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

входам перемножителя и являются вы-- ходами блока, выходы второй ячейки регистра сдвига подключены к вторым входам делителя и перемножителя, выходы которого соединены с вторыми входами вычитателя, выходы которого подключены к информационным входам третьей ячейки регистра сдвига, ин- Лормаид онные входы первой и второй ячеек регистра сдвига являются соот- ветственно установочными и информа- ДИОНШ-.1МИ входами блока, входы записи и сдвига регистра сдвига являются соответственно первым и вторым управ ляющими входами блока.

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

- ц

10

, в . ий 20

6348410

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

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

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

35 рые входы перемножителя являются информационными входами преобразователя, входы, записи и сдвига регистра сдвига являются соответственно пер- . вым и вторым управляющими входами преобразователя.

25

30

40

ff

II

././

/

/fj

o«/

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

Фа2.2

25

f/.f

12

2/

25

3

n

27 f 272

- //.J

Фи. З

32 33

28

3ff

36

35

.f .2

:тя d

39

Составитель О.Ревинский Редактор Т.Лазоренко Техред Л.Сердюкова

Заказ 6380/54

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, , Раушская наб., д. 4/5

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

(Риг. б

Корректор И.Муска