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

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

Цель изобретения - упрощение устройства.

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

Устройство для обнаружения ошибок в модулярном коде содержит первый и второй входные регистры 1 и 2, блок 3 памяти, сумматоры 4, преобразователь 5 кода, счетчик 6, блок 7 управления, блоки 8 перавпозначности, блок 9 сравнения, элемент ИЛИ 10 и элемент И 11, имеет первый и второй информационные входы 12 и 13, контрольные входы 14, вход 15 пуск, тактовьд вход 16 и выход 17,

Входной регистр 1 представляет собой регистр сдвига, в который заX

п

писываются остатки х,, х, . числа X по основаниям р, , р, ..., р . Причем один тактовый импульс сдвигает последовательность остатков та- КИМ образом, что на выходах регистра 1 появляется код следующего остатка.

Входной регистр 2 представляет собой статический параллельный регистр, в который записываются остатки х., , ,.., , где m - число избыточных оснований, по контрольным основаниям PJ,, , ...,РК,„ .

Шины предварительной установки регистров 1 и 2 не- показаны,, так как предполагается, что к моменту начала работы устройства остатки х,, ,,., х, к , t.., Кт занесены в регистры 1 и 2.

Сумматоры 4 с первого по т-й являются сумматорами по модулям 0) соответственно и представляют собой сумматоры накапливающего типа с возможностью предварительной записи исходного значения.

Блок 7 управления (фиг. 2) содер- жкт элемент 18 задержки, триггер 19, элемент И 20, распределитель 2 импульсов, счетчик 22 импульсов и поро- говьй блок 23, имеет первый и второй входы 24 и 25 и первый - четвертый выходы 26-29.

-Блок 9 сравнения выдает сигнал, если код па его первых входах боль- ..ше, чем на вторых.

95528 ;2

Пороговьш блок 23 (фиг. 2) выдает сигнал, если его входной код не меньше 2п-1 .

В своей работе устройство для обнаружения ошибок в модулярном коде используют следующее.

Для диапазона Р определим число Xel l,,.. , которое представлено совоХо Хь

fo

15

20

Ipn купностьго остатков х,, л, ...,

по взаимно простым основаниям р,, рг ,

1 П

..., р„ , Очевидно, что Р.,П п- обра- ) 1 1 г

з ует нулевое пространство кода.

Для такого непозиционного представления числа X может быть определена позиционная характеристика Нормированный ранг числа

-MX)r(X)-i: (I) i- - J 1 J

где г(Х) - функция Ранг числа ;

Ш JL fl , у 1 л

- - l(mod Р; ) - базисные числа.

В;Р г(Х) может, быть найдено из

X

,р ZlxjB--r(X)P(2)

п i-1

Из уравнений (1) и (2) выражают (Х) следующим образом:

35

:)(х) (

;т- Гх;тЛ-. |х|р„ ,,.

-рГ . L-pyj

Вводят избыточное основание р , по которого преобразз от вырах|р; -

К

1

)

Если имеется несколько избыточных оснований, pit;, , .. ,, ри , то,

т ™

представляя Ру.- П р , как р., , из вы- 1-1 I

ражения (5) находят (X), учитывая.

50

что в этом случае m x;L ,

(6)

5

где L - базисные числа для системы

оснований РК, )

Подставляя выражение (6) и (5), имеют. - |:(,.p.|,

(Х)

X к L;

(7)

3 1295528 Вычислять (X) с помощью выражения (7) сложноi поэтому, воспользовавшись тем, что Р составное, вычиснови

ляют т.е.

Чх)

Чх)

4x);t(X) ; j l,m

Р«1 ,

V- f g. jiiHJ-1 fc P L РИ,

) +

+ X

PK;

10

}

Для сравнения (X) с ,, учитывая выражение (11), достаточно сравнить ЧХ) между собой и одно из них с величиной I 1 1- Если (Х) не равны между собой,

J ) р; ( ° 5 „ всегда. (Х)„. Совокупность (Х), .../(Х) ) равны, одно из них

Выражение (9) справедливо, так как

;1L 0, ,

следовательно

больше , то и тогда (Х)- Т1есть не что иное, как остатки от деления т)(Х) по модулям р , ...,р.

Известно

max

. VI

Следовательно, для упорядоченной системы оснований справедливо

.- (Ю 25

J20

Ркг 3..

Пусть Х,241 4- (1,3,,3) - пра- . число. Если происходит ошибка в двух вильное число, тогда - 55 остатках, например,

(Х) И 1+8+4-1-7 8 Кз 1;

(Х){ 4+3+2+3-31,7

1,

Таким образом, вычислив (X) и ) (X), заключают, что X, - правильное;

тогда

Х,(1,5,10,7 4),

54x)ln+4+4+7-8l, 10; (Х) | 4+10+2+4-31 7 11.

528

Если происходит любая ошибка кратности m и меньше, то всегда неправильное X находится вне диапазона Р,

Можно показать, что при реализа- 5 ции алгоритма (9) для ()Р„ чисел, не принадлежащих Гр (Х) т.е. эти неправильные числа выrti

являются вычислением (9).

10

„ всегда. (Х)„. ) равны, одно из них

больше , то и тогда (Х)- Т1Таким образом пред.поженный алгоритм позволяет из числа неправильных

чисел опознать подавляющее их количество за число тактов не больше (п+1) для любого числа избыточных оснований.

Пример

число. Если происходит ошибка в остатках, например,

тогда

Х,(1,5,10,7 4),

54x)ln+4+4+7-8l, 10; (Х) | 4+10+2+4-31 7 11.

Вследствие этого заключают, что Х - неправильное число.

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

В исходном состоянии в регистр I занесены остатки х,, х, .,., к.

В регистр 2 занесены остатки к , х , ... . На выходах преобразователя 5 кода сформированы значения кодов Ix,f,jJ, , ..., |х,р/ соответственно.

На вход 16 поступают тактовые импульсы, триггер 19 установлен в нулеIpvcm

Прибавлены значения кодов 0р

г,К последнему такту на вход счетчи ка 22 поступает 2п-2 тактовых импуль 5 са,, и по приходу (2п-1)-го тактового импульса на В 1ходе порогового блока 23 появляется логическая единица, .которая устанавливает триггер 19 в ° нулевое состояние, запрещая тем са- fO мым дальнейшее поступление тактовых импульсов.

На этом такте содержимое сумматоров 4 соответствует Ai(X), ...)

Если ЧХ) (Х) ..,) (Х)

вое состояние, и, соответственно, на f5 „,8 то на выходах блоков 8 и 9 ловыходах распределителя 21 нет импульсов.

Импульс Пуск, поступивший на вход 15, устанавливает счетчик 6 в исходное нулевое состояние и, пройдя через блок 7 управления на выход 28, записывает в сумматоры 4 с первого

х,, fi

гические нули не изменяют значение логического уровня на выходе элемента ИЛИ 10 и соответственно элемента И П, Тем самым констатирует- 20 ся правильность числа X,

Если же (Х)5 --3-ЧХ), i,j6 i,n, или (X)v 5 то логическая единица на выходе элемента ИЛИ 10 приводит к появлению логической единицы на также устанавливает в исходное состо- выходе элемента И П , так как на его

по т-и значение кодов 11

. fpk,

I.4.I -1 ( I ГК5 Xi- ft n соответственно, a

I Km P I pKm

яние распределитель 21 импульсов и счетчик-22. Через время, определяемое окончанием переходных процессов в сумматорах 4 и блоке 3 памяти, через элемент 18 задержки триггер 19 устанавливается в единичное состоя- . ние. Поступивший на вход 16 тактовый импульс приводит к появлению импульса на выходе 27.

К этому времени на выходах блока 35 числа предлагаемое устрой-, 3 памяти сформированы коды Ор, (х,), тво более просто в выполнении, чем .... 0p|j (х ) , которые при появлении импульса на выходе 27 прибавляют значения этих кодов к содержимому сумматоров 4 с первого по т-й соответст- 40 венно.

Следующий тактовый импульс на входе 25 приводит к появленшо импульса на выходе блока 7 управления, вследствие чего содержш-гае К сдвигается 45 рого подключены к ссответствующим вправо и на входы блока 3 памяти посту- входам преобразователя кодов, выхо- .пает код остатка Xj,. Содержимое счетчика № которого соединены с первыми вхо

втором входе присутствует логическая единица с выхода порогового блока 23.

Таким образом, единица на выходе 30 элемента И 1 свидетельствует о том, что число X неправ шьноеJ т.-е. искаженное (ошибка достигает кратности т)

Благодаря использоЕтнию функции

известное-;

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

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

6 увеличивается на единицу. На выходах блока 3 памяти формируются кодл

дами соответствующих сумматоров, блок сравнения и элемент И, входы

9р (х ), ...,0р (х), которые при 50 первого и второго входных регистров

Tf CJli ГТПГГ ГТ Г г/ Г /.ГЧПтгэ/: Т Г грти1ГТГ Т11-ГТЛЛТЛ TjrTJr r4-nT;A TTT;r

поступлении следующего тактового импульса прибавляются к содержимому сумматоров 4 с первого по т-й соответственно.

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

Подобным образом работа устройства продолжается до тех пор, пока к содержимому сумматоров 4 не будут

Прибавлены значения кодов 0р

г,К последнему такту на вход счетчика 22 поступает 2п-2 тактовых импуль- са,, и по приходу (2п-1)-го тактового импульса на В 1ходе порогового блока 23 появляется логическая единица, .которая устанавливает триггер 19 в ° нулевое состояние, запрещая тем са- мым дальнейшее поступление тактовых импульсов.

На этом такте содержимое сумматоров 4 соответствует Ai(X), ...).

Если ЧХ) (Х) ..,) (Х)

втором входе присутствует логическая единица с выхода порогового блока 23.

Таким образом, единица на выходе элемента И 1 свидетельствует о том, что число X неправ шьноеJ т.-е. искаженное (ошибка достигает кратности т).

Благодаря использоЕтнию функции

числа предлагаемое устрой-, тво более просто в выполнении, чем

рого подключены к ссответствующим входам преобразователя кодов, выхо- № которого соединены с первыми вхо

известное-;

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

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

рого подключены к ссответствующим входам преобразователя кодов, выхо № которого соединены с первыми вх

дами соответствующих сумматоров, блок сравнения и элемент И, входы

50 первого и второго входных регистров

CJli ГТПГГ ГТ Г г/ Г /.ГЧПтгэ/: Т Г грти1ГТГ Т11-ГТЛЛТЛ TjrTJr r4-nT;A TTT;r

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

импульсов и управляющему входу первого входного регистра, выходы которого соединены с соответствующими информационными входами блока памяти, выходы счетчика подключены к соот- ветствующим адресным входам блока памяти, первые - т-е выходы которого соедине с вторыми входами соответствующих сумматоров, где m - число избыточных оснований, вьрсоды перво- го сумматора подключены к. соответствующим перйым входам первого блока неравнозначности, выходы i-ro сумматора, is L2}m-lj подключены к соответствующим первым входам i-ro и вто- рым входам (i-l)-ro блоков неравнозначности, выходы т-го сумматора подключены к соответств.ующим вторым входам (ni-l)-ro блока неравнозначности и nepBFjiM входам блока сравне- ния, выходы блоков неравнозначности и блока сравнения соединены с соот- ветствуюпщми входами элемента ИЛИ, выход которого подключен к первому входу элемента И, второй и третий выходы блока управления- соединены с соответствующими третьими и четвертыми входами сумматоров, четвертый выход блока управления подключей к второму входу элемента И, первьш и вто- рой входы блока управления являются

25

Составитель о. Ревинский Редактор О..Юрковецкая Техред-Л,Сердюкова Корректор О, Луговая

Заказ 628/62Тираж 902Подписное

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

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

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

соответственно входом Пуск и тактовым входом устройства, вторые входы блока сравнения являются контрольными входами устройства.

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

выходу блока управлений, второй вход элемента И является вторым входом блока управления, выход .порогового элемента подключен к четвертому выходу блока управления.

Изобретение относится к. вычислительной технике. Его использование в системах обработки и передачи информации в модулярном коде(коде в остатках) позволяет упростить устройство, которое содержит входные регистры 1, 2, блок 3 памяти, сумматоры 4, преобразователь 5 кодов, блок 9 сравнения и элемент И 11. Введение счетчика 6 импульсов, блоков 8 неравнозначности, элемента ИЛИ 10 и блока 7 управления обеспечивает возможность обнаружения ошибки с помощью функции Ранг числа, благодаря чему упрощается вьшолнение устройства. 1 з.п. ф-лы, 2 ил. i (Л