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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИК

„„80„„1396283 А 1 сЮ 4 Н 03 М 13/00

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

Н АBTGPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4176891/24-24 (22) 21.11.86 (46) 15.05.88. Бюл. № 18 (72) А.Б.Акулинчев и С.Н.Хлевной (53) 681,3 (088.8) (56) Авторское свидетельство СССР № 1238078, кл.С 06 F 11/08, 1984.

Авторское свидетельство СССР № 862143, кл. Н 03 M 13/00, 1979. (54) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ

ОШИБОК В ДВУХСТУПЕНЧАТОМ МОДУЛЯРНОМ

КОДЕ (57) Изобретение относится к области вычислительной техники и может быть использовано для контроля в вычислительных устройствах, функционирующих в системе остаточных классов, а также для обнаружения ошибок в системах передачи информации, представленной модулярными кодами. Целью изобретения является уменьшение аппаратурных затрат. Поставленная цель достигается тем„ что устройство для обнаружения ошибок в двухступенчатом модулярном коде, содержащее блок 4 памяти, блок 5 вычисления позиционной характеристики, две схемы 8,9 сравнения с константой и элемент

ИЛИ 1 О, содержит демультиплексор 3, . блок 6 вычисления квазиранга числа и схему 7 сравнения с соответствующими связями. 2 з.п. ф-лы, 3 ил.

1396283

В своей работе устройство (фиг.1) использует следующее.

Представим число Х из диапазона совокупностью остатков х .

t ï i

IX I p. по взаимно простым основани1 и ямР;, где i = 1,п+1, а 7„=П Р,.

Таким образом, в рассматриваемом коде основание P „„ является избыточ-. ным. Пусть выбранная система основа— ний упорядочена, т.е.

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

Целью изобретения является уменьшение аппаратурных затрат..

На фиг.1 приведена схема устройства для обнаружения ошибок в двухступенчатом модулярном коде; на фиг.2 — схема блока вычисления позиционной характеристики; на фиг ° 3 схема блока вычисления кваэиранга числа.

Устройство (фиг.1) содержит входы 1 и 2 номера столбца и номера строки устройства, демультиплексор 3, блок 4 памяти, блок 5 вычисления позиционной характеристики, блок 6 вычисления квазиранга числа, схему 7 сравнения, схемы 8 и 9 сравнения с константой, элемент ИЛИ 1 О, информа- 25 ционный вход 11 устройства, первый вход 12 схемы 7 сравнения, выход 13

"Ошибка" устройства, второй вход 14 схемы 7 сравнения, вход 15 блока 5 вычисления позиционной характеристи- 30 ки, вход 16 блока 6 вычисления квазиранга числа, группу входов 17.1-17.К блока 6 вычисления квазиранга числа, выход 18 блока 5 вычисления позиционной характеристики и выход 19 блока

6 вычисления квазиранга числа °

Блок 5 вычисления позиционной характеристики (фиг.2) содержит узел

20 памяти, умножитель 21 по модулю и сумматор 22 по модулю. 40

Блок 6 вычисления квазиранга числа (фиг.3) содержит группу узлов

23.1-23.К памяти, группу умножителей

24.1-24.К по модулю, группу сумматоров 25.1-25.К по модулю и узел 26 45 преобразования модулярного кода в позиционный код.

P cP с... Р„(Р„„

Каждый остаток х;, ь =1,и+1, представим системой остатков и . = х .I+

J по взаимно простым основаниям Р .! где j = 1,k+1. Система оснований второй ступени так же упорядоченная, а основание „+ избыточное, т,е. !З р.=7. иь1 1 к

В результате имеем двухступенчатый модулярный код числа Х, который можно представить в виде матрицы остатков.

Х (м и и1 hktq Иь1.1 Иь1 j И-Ь1 k+1 ...d .... c(Остатки анализируемого числа Х поступают на вход устройства последовательно, по строкам.

Процесс контроля ошибок в принимаемой совокупности остатков

11 состоит из трех этапов. Необходимо определить меньше ли принятый остаток, основания р;. Если да, то

1 процесс контроля можно продолжать дальше, если нет, то делаем вывод о возникновении ошибки. Необходимо проверить принадлежность совокупности остатков ;„,..., o(;„,„ разрешенной кодовой комбинации. Если анализируемое число правильно, то оно принадле-. жит нулевому пространству избыточного модулярного кода (в данном случае I- ) и значение квазиранга к этого чйсла R(x,) лежит в пределах

I0,R (х)) . Если произойдет ошибка, то искаженное число выйдет за пределы указанного диапазона и его квазиранг К(х ) превысит некоторое гранич— ! ное значение К,и(х) . Это свойство функции квазиранг позволяет обнаруживать ошибки в избыточном модуляр ном коде. Значение квазиранга строки определяется как

Кьi

К(х,) = 2

Р КЬ1 где коэффициенты 1. определяются

3 следующим образом для

j = 1, k, 1396283

q! = (1-К,„(х): (у».,— 1) 100% для

1 где m> 1ф1; веса базисных чисел системы основа- 5 ний р второй ступени

) б д !(б!

УК+ для j k+1, 10

Граничное значение

К

Г - m;(p. -1) 1+

R (х)

m

)х! Pj

Необходимо, располагая совокупностью остатков х;, i--lвп+1, проверить принадлежность числа Х к диапазону 1 1,Р, и только в этом случае и

его можно считать правильным. 20

В общем случае контроль указанной совокупности остатков Х; не отличается от описанного процесса контроля совокупности остатков o(;,,..., o(- к+, . Для упрощения технической реализации квазиранг определяется по формуле (Х) В)1 к х.(Х)В, р

М (Р! 1 ) (!в р

1=!

Пб! где х (х) ! х!

35 р f)7(hf.1

m! J»

I базисные числа системы оснований

1-k второй ступени;

45 веса базисных чисел системы оснований

Р;, i=1-и первой ступени; 50 б

1;1= 1Ь,1

L; !,!+!

Râ(X) (P„! 1) 100% для первой ступени;

Процент обнаруживаемых ошибок определяется по формуле 55 второй ступени .

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

Демультиплексор 3 распределяет остатки Ы; входа 11 на К своих выходов в зависимости от значения j на входе

1.

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

Схема 7 сравнения формирует сигнал "1" на своем выходе, когда код на выходе блока 4 больше, чем на входе 11.

Схемы 8 и 9 сравнения выдают сигнал, если их входной код превысит значения R (х) и R (Х) соответственно.

В блоке 5 вычисления позиционной характеристики умножитель 21 и накапливающий сумматор 22 выполнены по модулю 9

В блоке б вычисления квазиранга числа умножители 24.j и накапливающие сумматоры 25.j выполнены по модулю p °

Устройство (фиг.l) работает следующим образом.

B исходном состоянии все сумматоры обнулены, узел 26 преобразования модулярного кода в позиционный готов к преобразованию, на входах l u

2 устройства — "1".

Работа устройства начинается в момент появления на входе 11 кода первого остатка el величина которого сравнивается схемой 7 со значением кода основания р,, установленного на выходе блока 4 памяти, и, если первое значение превьппает второе, на выходе схемы 7 формируется сигнал "1", который проходит через элемент ИЛИ 10 на выход 13 устройства, что означает наличие ошибки в анали зируемом остатке. Далее на вход ll подается код следующего остатка сопровождаемый значением два на входе 1 устройства, что вызывает формирование на выходе блока 4 значе« ния р, которое сравнивается в схе1396283 ме 7 со значением Ы . Последующие остатки анализируются аналогично, в результате чего проверяется выполнение неравенства o(; cу.. J ° 5

Одновременно с этим значения j c входа 1 устройства и соответствующие значения," с входа 11 устройства J поступают на блок 5, который за каждый К+1 тактов вычисляет значение

R(x;),êoòîðîå сравнивается со значением R (х) в схеме 2 сравнения. Ecf11 ли значение R(x.) превышает эначе1 ние R (х),на выходе схемы сравнения формируется сигнал "1", который, пройдя через элемент ИЛИ 10 на выход 13 устройства, сигнализирует о наличии ошибки в i-й строке анализируемой матрицы.

Наряду с указанными процессами происходит выявление ошибки во всем числе путем вычисления R(X) описанным способом.

Для этого демультиплексор 3 преобразует поступающую в него после1

1) довательность Ы . таким образом, что на его j-м выходе последовательно появляются остатки j-ro столбца анализируемой матрицы. После завершения прохождения через демультиплексор З0

Э остатков i-й строки, производится передача остатков (i+1)-й строки матр ицы.

Когда в устройство поступят остатки последней строки матрицы остатков

35 числа, на выходе блока 6 появится результат вычисления R(Х), который сравнится со значением R (Х) в

" схеме 9 сравнения. Если R(X) ) R (X), то на выходе формируется сигнал "1", который поступает через элемент ИЛИ

1 0 на выход 13 "Ошибка" устройства.

Блок 5 вычисления позиционной характеристики (фиг.2) работает следующим образом.

С входа 15 поступает код j, который является адресом j-й ячейки узла 20 памяти, на выходе которого формируется значение ., которое умножаУJ ется на значение Ы; в умножителе 21 по модулю ),„. Результат умножения

50 поступает на накапливающий сумматор

22, где складывается по модулю со значением результатов предшествующих тактов . В итоге за каждые К+1 тактов в сумматоре 22 формируется значение

R(x;) .

Блок 6 вычисления кваэиранга числа (фиг.3) работает следующим образом.

На вход 17. 1 блока 6 поступают остатки j-ro столбца матрицы

11,п+1. На i-M такте вычисления узел 23.j формирует на своем выходе код коэффициента 1;, который умножается на код остатка a ; по модулю в умножителе 24.j, и результат поступает на сумматор 25 ° j, где он складывается по модулю с суммой результатов предыдущих циклов.

Остальные столбцы обрабатываются аналогично и в результате за и+1 циклов на входах узла 26 формируются . значения r (Х), j=1,k.

Узел 26 преобразования модулярного кода числа в позиционный формирует на своем выходе 19 значение квазиранга числа R(X).

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

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

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

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

1396283

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

Редактор Е,Копча Техред Л.Сердюкова Корректор JI Пилипенко

Заказ 2504/57 Тираж 928 .Подписное

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

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

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