Устройство для обнаружения и исправления ошибок в кодовой последовательности Советский патент 1986 года по МПК G06F11/08 

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

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

Устройство для обнаружения и ИС7 . правления ошибок в кодовой последовательности реализует код условных вычетов (ВУ) - код, использование которого для контроля чисел заключается в следующем. Информационная часть кода числа, представленного в любой системе счисления, в том числе двоич- ной, или любого кода, представленно- гЬ в виде набора двоичных цкфр, сопровождается, как и при известных cnoсобах контроля по модулю, контроль- . ным признаком. В отличие от известных способов расчет контрольного признака и процесс.обнаружения и исправления ошибок заключается в следующем.

Исходный код условно разбивается на определенное число групп разрядов каждая из которых рассматривается как остаток от деления некоторого числа А на набор взаимно простых оснований Р,, Р2,...,Рп. Таким образом, ис- ходный код, например двоичное число А, представляется в виде условного

представляется числа А :

А oi|,oi

г

, ,0бп

представленного в системе остаточных классс в, где ot; - остатки от деления условного числа А , двоичньй код которого соответствует исходному числу А, на набор условных оснований

Р; (i 1,2,...,п).

.Из теории остаточных классов известно, что если имеется остаток от деления числа .А на контрольный модуль q, причем

q 2Р„ Р„., ,

где Р „ и PJ, ., - наибольшие условные основания из их совокупности, то возможно обнаружение и испрдвление ошибок любой кратности в одном из остатков ос; представлен-ия числа А.

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

водится по известным в системе оста точных классов соотношениям, считая условно исходный код А числом в остаточных классах.

Представление исходного кода А совместно с контрольным признйко aJ (j,, вычисленным по правилам системы оста- точных классов в виде условного слова в системе остаточных классов (ВУ- код), позволяет использовать для обнаружения и исправления ошибок тот факт, что любое искажение .исходного кода по одному из условных оснований PJ переводит условное число А из диапазона (О, Р) в диапазон (Р, Р), где Р .Г1Р;. При этом исходное условное число А увеличивается на величину t; , RJ, где Rj Pd,/Pj , т.е. искаженное число (А ) равно: А

л-1

А

«oi.i

(1)

Величина ,j определяется величиной ошибки по основанию Р: , т.е.. величиной

uoi

)

..-« .l Pj

в последнем выражении oi; (oi;) - соответственно неискаженная и искаженная .асти исходного кода, соответствующие условному основанию Р; , а знак

ПричемJ как

(2)

х PV означает вычисление остатка от деления величины X на Р; . следует из выражения (1),

Поскольку условные основания выбираются так, чтобы неискаженное условное число А удовлетворяло условию. А Р , то тогда

А - PjRj 4Р.(3)

Это условие позволяет организовать контроль информации с определением как места, так и величины ошибки. Для этого представим контролируемое число А с помощью ортогональных базисов так, что

1, Т

А 21 В; V ,(4)

L .:.1 Ji((

где R

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

(5)

. t

m - вес 1-го оротогонального базиса, определяемый так, что

.aiv

ставим (4) /С,, n+t

А Г, 1

1 -1 квадратные

виде,.

В,

1. В;

I--R

скобки означают вычисR,

ленив целой части соответствующего выражения. Тогда условие .(3) с учетом (2) может быть записано в виде ht- Г 1 1 Г 1 .g- B;R-R. Л-Д:.с.;В;- ,., , L - -J

Г 1 Т .

RUP

С учетом (5) после образований получим

qZ..z.1

или

ZP-,

- I i

Pi

ii: p

m,

.

L 0 J

Поскольку условие (3) и эквивалентное ему условие (6) справедливы только для того основания, по которому место искажение исходного кода, то они позволяют определить место возникновения ошибки С этой целью необходимо вычислить величину Z (7) и проверить выполнение условия (6) для калздого из п оснований Р; Величина ошибки при этом может быть определена ий следующих соотношений. Так как

Vj fb/j - PJ- A }PJ Г - tPj I

, .K

.ftjRj Pj,

TO

, Де

с учетом A

Т.е.

i j-fRj ..

Из последнего выражения следует, что величина ошибки по i-му условно- |Му основанию Л однозначно определяется величиной Z (R ; и Р; при выб

J i

ранной системе условных оснований являются константами) и может быть определена либо из таблицы соответст- ВИЯ Aoij Z, либо расчетнь м путем. Первый способ является предлочтительным при малой разрядности контроли

с

-

to

15

20

)

25

30

35

40

45

50

55руемых кодов и малом количестве возможных в них искажений, а второй - при больших разрядностях кодов и большой кратности возможных ошибок (например, в ЭВМ,, аппаратуре передачи данных, различного рода накопителях и т.п.),

в устройстве реализован второй способ,

На чертеже представлена схема предлагаемого устройства.

Устройство содержит регистры 1 и 2, группу коммутаторов 3 коммутаторы 4 - 6, группу коммутаторов 7 и 8, коммутатор 9, группу коммутаторов 10, группу блоков памяти 11, блоки памяти 12 - 14, элемент задержки 15, группу элементов задержки 16, элемент задержки 17, регистры 18 и 19, счетчики 20 и 21, дешифраторы 22 и 23, накапливающий сумматор-24, умножитель 25, схему сравнения 26, сзгмматор 27, элементы И 28 и 29, группу элементов И 30., элемент И 31, элемент ИЛИ 32,. триггер 33, элемент НЕ 34, группу узлов свертки 35, группу шифраторов 36.

Коммутатор 4, при наличии на управляющем входе сигнала с выхода элемента И 28 обеспечивает передачу ве- личины Z, образованной на ракаплива- вающем сумматоре 24, на первый вход умножителя 25. Коммутатор 5 при наличии на управляющем входе сигнала с выхода элемента И 31 обеспечивает передачу содержимого группы выходов регистра 18 на регистр 2. Коммутатор 6 при наличии на управляющем входе сигнала с выхода элемента И 31 обеспечивает передачу входного сообщения, кроме его контрольного признака, с регистра 1 на регистр 19. Коммутаторы 7, При наличии на управляющем входе сигнала с выхода соответствую-. щего элемента И 30 группьг, обеспечивает передачу содержимого регистра 18 на один из соответствующих узлов свертки 35. Коммутатор 8, при наличии на управляющем входе сигнала с соответствующего вьгхода дешифратора 23, обеспечивает передачу содержимого соответствующей группы выходов регистра 19 на вход сумматора 27. Коммутатор 9, при наличии на управляющем входе сигнала с выхода элемента И 31, обеспечивает передачу показаний счетчика 21 на вход блока памяти 14. Коммутаторы 10, при наличии на управляющих входах сигнала с соответствующего элемента задержки 16 группы, обеспечивают передачу содержимого сумматора 27 на один из шифраторов группы 36. Регистр 1 предназначен для приема и хранения поступившего сообщения, включая контрольный признак. Регистр 1 .имеет (К+1) групп выходов, содержащих информационную часть сообщения Z,, Zjj..., Z,j к контрольный признак Z, .. Регистр 19 предназначе для хранения выходной информации устройства. Регистр 18 предназначен для хранения произведения, образовавшегося на умножителе .25. Регистр 18 имеет две группы выходов, одна из которых предназначена для хранения целой части произведения jl ДРУ гая - дробной части ZPJ.

Регистр 2 предназначен для хране- ния целой части произведения ZP: .

Группа блоков памяти 11 предназначены для хранения констант вида oij fflj/P: . Блоки 12, 13 и 14 предназначены для хранения констант Р , D, R; соответственно. .

Константы DJ хранятся в обратном коде, а Pj и Kj - в прямом коде, В качестве группы блоков памяти 11 и блоков памяти 12 - 14 могут исполь- зоваться, например, запоминающие устройства, построенные на элементах К 155РУ1 или К 155 РУ2,

Накапливающий сумматор 24 предназначен для суммирования констант, поступающих с первых блоков .памяти 11, и образования величины Z.

Умножитель 25 предназначен, для образования произведений ZPvn zP:jR В качестве умножителя может быть ис- польз.оЪана, , микросхема , входящая в .микропроцессорный комплек серии КР1802 (умножитель 16x16). В целях повьшения быстродействия может использоваться, например, множительное устройство, в котором использова метод ускорения умножения 2-го порядка. .-.

Схема сравнения 26 .предназначена для сравнения двух величин Dj и ZP: с целью проверки вьшолнения условия (7).

В качестве схемы сравнения, может быть использован например, сумматор комбинационного типа. Так как конс- танта D поступает на схему сравне- ния в обратном коде, то по знаку суммы можно судить о выполнении неравен Ьтва (7).

д J

Q

5

S

5

0

Группа узла свертки 35 и группа Шифраторов 36 предназначены для получения свертки по mod Р, , Р ,.,., Р, , величин CzPjlRj и (Zj -iofj) соответственно.

Сумматор 27 предназначен .для образования разности Z -Uoij.

В качестве сумматора 27 можно ис пользовать, например, сумматор комбинационного типа при подаче на его входы величина uc(J в обратном коде с блоков свертки 35.

Элементы задержки 15 и 17 и группа элементов задержки 16 предназначены для задержки выходных сигналов относительно входных на 0,5Т„; 1 j Т|ц (Ту, - период следования тактовых им- пульсов) и на время, необходимое для исправления ошибки образования разности на сумматоре (вычитателе) 27 соответственно.

Устройство работает следующим образом.

В исходном состоянии счетчики 20 и 21, триггер 33 находятся в нулевом состоянии. На регистр 1 поступает принятое сообщение - кодовая последе- вательность (кодограмма).С инверсного выхода триггера 33 поступает сигнал 1 на элемент И 29, разрешающий поступление тактовых импульс.ов на счетный вход счетчика 20. По тактовым импульсам распределитель, состоящий из счетчика 20 и дещифратора 22, последовательно вырабатывает сигналы, поступающие на коммутаторы группы 3. Эти сигналы разрешают передачу информации контролируемых.разрядных групп, на которые условно разбито поступившее сообще.ние: (кодограмма), на соответствующие блоки памяти 11. Содержимое группы разрядов сообщения $. по основанию Dj служит адресом константы в каждом из соответствующих блоков памяти груп- пы 11.

По этим адресам (Zj) в блоках памяти группы 11 осуществляется выборка констант по всем основаниям Р. , PV,...., PJ, , Выбранная очередная константа поступает на накапливающий сумматор 24, н.а котором образуется сумма Z. Образование величины Z осуществляется по тактовым импульсам ТИ, поступающим на сумматор 24 с элемента И 29.

Информация последней (К+1)-и группы передается по сигналу с последнего (К+1)-го выхода дешифратора 22. Этим же сигн шом устанавливаются в О счетчик 20 и в единичное состояние триггер 33.

С инверсного выхода триггера 33 снимается сигнал О на вход элемента И 29, запрещающий поступление тактовых импульсов ТИ на счетный вход счетчика 20.

Сигналами 1 с прямого выхода .триггера 33 и с выхода элемента НЕ 34 разрешается передача тактовых импульсов через элемент И 28 на счетный вход счетчика 21.

Счетчик 21 имеет модуль счета М К (К - количество контролируемых групп разрядов), Показание вто

рого счетчика 21 служит адресом кг-н- стант Dj, Dj и Р хранящихся в блоках памяти 12, 13 и 14 соответственно. Из блоков памяти 12 и 13 выбираются константы Р; и Dj . Константа Р- поступает на умножитель 25, констан- та D; на схему сравнения 26. С поступлением первого тактового Импульса с элемента И 28 на коммута,тор 4 величина Z, образованная на накапливающем сумматоре 24, поступает на первый вход умножителя 25, на второй вход которого поступает константа Р с блока памяти 12. На умножителе 25 образуется произведение ZR , которое с его выхода поступает на регистр 18

Дробная часть величины ZF с груп пы выходов региетра 18 поступает на схему сравнения 26. На схеме сравнения образуется сумма величины Dj, представленной в обратном коде, и дробной части величины ZPj.

При выполнения условия (7), т.е. когда в данной группе разрядов сообще ни,я нет ошибки, с выхода схемь сравнения 26 (со знакового разряда сум- матора) снимается сигнал О. На вы- ходе элемента НЕ 34 сохраняется сигнал 1 разрешающий поступление последующих тактовых импульсов .через элемент И 28 на счетгазй вход счетчика 21 для проверки следующей группы разрядов сообщения.

Проверка последующих групп разрядов кодовой последовательности осуществляется аналогичньм образом. Если опшбка не обнаружится ни в одной из групп разрядов сообщения, то показание счетчика 21 равно К, при этом на последнем (К-м) выходе дешифрато5

0

t5

20

25

0

0

®

5

ра 23 имеется сигнал 1, Этот сигнал через элемент задержки 17 и элем.ент ИЛИ 32 поступает на нулевой вход триггера 33 и устанавливает его в нулевое состояние. С инверсного выхода триггера 33 на элемент И 29 поступает сигнал 1 раарешакщий прохождение через нее тактовых импульсов (ТИ) для проверки следующего сообщения. С прямого выхода триггера 33 на элемент И 28 поступает сигнал О, по которому прекращается подача тактовых импульсов ТИ на: счетный вход счетчика 21. Задержка сигнала, который поступает с выхода дешифратора 23 на триггер 33, осуществляется для того, чтобы на счетчик 21 Ььш подан К+1 тактовый импульс для сброса данного счетчика в ноль. Счетчик 21, таким образок, подготовлен для процесса проверки групп разрядов следующей кодовой последовательности.

Если на выходе схемы сравнения 26 при проверке 1-й группы разрядов сообщения появляется сигнал 1, свидетельствующий о наличии ошибки в данной группе, то тем самым разрешается прохождение тактирующего импульса по сигналу ошибки через элемент И 31 на коммутаторы 5, 6, 9, элементы И 30, ИЛИ 32, элемент задержки 15 и через злемент НЕ 34 подключается прохождение тактовых импульсов через элемент И 28. При этом через коммутатор 9 разрешается передача показания счетчика 21 в блок памяти 14, в котором происходит выборка константы R и передача ее на умножитель 25. Кроме того, через комйутатор 6 с группы выходов регистра 18 на умножитель 25 через регистр 2 поступает целая часть произведения ZPjl. На умножителе 25 образуется произведение fZPiТ Rj, которое за-писывается в регистр 18. Сигнал ошибки, пройдя через элемент задержки 15, сбрасывает счетчик 21 Б ноль. Этот же сигнал поступает через элемент ИЛИ 32 на нулевой вход триггера 33.

Триггер 33 устанавливается в нулевое состояние, и с efo инверсного выхода на элемент И 29 поступает сиг- нал, разрешающий подачу тактовых импульсов ТИ на счетчик 20 для обработки следующей кодовой последовательности,- сообщения.

Сигнал ошибки поступает также на управляющий вход Коммутатора 6, и со-

держимое регистра 1 без контрольного признака поступает на регистр 19.

Информация одной из групп выходов регистра 19 по разрешающему сигналу с выхода дешифратора 23 поступает че- рез соответствующий коммутатор 8 группы на вход сумматора 27. Результат свертки содержимого регистра 18 поступает на другой вход сумматора 27. Разрешающий сигнал с дешифратора 23 через. Ьоответствующий элемент задержки 16 группы поступает на управляющий вход соответствующего коммутатора 10 группы. По этому сигналу образовавшаяся на сумматоре 27 разность поступает на шифраторы 36 групп, осуществляющие свертку по со- соответствующему модулю, -с шифратора группы 36 величина pz ; - пос- тупаёт на соответствующую группу разрядов регистра 19, после чего в регистре 19 хранится исправленная информация.

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

Устройство для обнаружения и исправления ошибок в кодовой последовательности, содержащее Два регистра, схему сравнения, триггер, первый дешифратор, элемент ИЛИ, первый элемент И и элемент НЕ, причем группа выходов первого регистра является группой ин- фррмационньк выходов устройства, о тли ч а ющ е ее я тем, что, с целью расширения функциональных возможностей за счет о беспечения возможности контроля кодовой последовательности, представленной в системе счисле- ния, отличной от остаточных классов, а также снижения избыточности кодовой последовательности, оно содержит накапливающий сумматор, умножитель, сумматор, четыре группы коммутаторов, дварегистра, группу блоков памяти, группу элементов И, группу узлов свертки, группу шифраторов, группу элементов задержки, два счетчика, четыре коммутатора, два элемента за- держки, второй и третий элементы И и второй дешифратор, причем К групп информационных входов устройЬтва соединены с группами информационных входов первого регистра, К групп выходов которого., где К - Число групп сообл1 и1Й, соединены с группами ин- фр-рмаисиоиньрс входов соответствующих К коммутаторов первой группы и инфор

. 0 5 0

5

о 5

5

мационным входом первого коммутатора,, группа выходов контрольного признака первого регистра соединена с группой информационньк входов (К+1)-го коммутатора первой группы, вьрсоды коммутаторов перв-ой группы соедийены с адресными входами соответствугопщх блоков памяти группы, выходы которых соединены с информационными входами накапливающего сумматора,, выходы которого соединены с информационными входами второго коммутатора, выходы которого и вькоды второго.регистра подключены к первой группе информационных входов умножителя, выход которого соединен с.информационным входом третьего регистра, первая и вторая группы выходов которого соединены .с группой информационных.входов третьего коммутатора и .с первой группой информационных схемы сравнения соответственно, а также с группами информационных : входов коммутаторов второй группы, выходы которых соединены с входами соответствующих узлов свертки группы, выходы которых соединены с перво.й группой информационных входов сумматора, выходы которого соединены с информационными входаш коммутаторов третьей группы, .выходы которых через -соответствующие шифра- . торы группы соединены с К-группами информационных входов четвертого регистра, К групп выходов которого соединены с соответствующими группами информационных входов коммутаторов четвертой группы, ()-я группа выходов четвертого регистра является группой информационных выходов устройства, тактовый вход которого соединен с первыми вxoдa ш первого, вто- tporo и третьего элементов И, выход первого элемента И соединен с входом . синхронизации накапливающего сумматора и счетным входом первого счетчика,- разрядные выходы которого соединены с информационными входами первого дешифратора, выходы которого с первого по (К+1)-и соединены с управляющими входами соответствующих коммутаторов первой .группы, а (К+1)-й выход первого дешифратора соединен с вхо- д ом сброса первого счетчика и единичным входом триггера, инверсный и прямой выходы которого соединены с вторыми входами первого и второго элементов И соответственно, выход второго элемента И соединен с управляющим

входом второго коммутатора и счетным входом второго счетчика, разрядные вьбсодЬ которого соединены с адресными входами первого и второго блоков памяти и с информационными входами второго дешифратора и четвертого коммутатора, выходы которого соединены с адресными входами -ретьего блока памяти, выходы которого и выходы пер- вого блока памяти соединены с второй группой информационных входов умножителя, группа выходов третьего блока памяти соединена с второй группой информационных входов схемы сравне- ния, выход которой соединен с вторым входом третьего элемента И и через элемент НЕ с третьим входом второго элемента И, выход третьего элемента И соединен с управляющим входом пер- вого, второго и третьего коммутаторов с первым входом элемента РШИ, с пер-

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

Btrfxod

Изобретение относится к вычислительной технике и может быть испо11ь- эовано в цифровых ЭВМ повышенной ин- |юрмационной надежности. Целью изобретения является расширение функциональных возможностей за счет обеспечения возможности контроля кодовой последовательности, представленной в системе счисления, отличной от остаточных классов, а также снижение избыточности кодовой последовательности. Устройство формирует код условных вычетов. Информационная часть исходного кода числа сопровождается контрольным признаком. Исходный код условно разбивается на группы разрядов и тем самым представляется в виде условного числа. Расчет контрольного признака исходного кода производится по известным соотношениям. Любое искажение исходного кода по одному из условных оснований переводит остаток от деления исходного кода из одного диапазона в другой. Этот факт используется для обнаружения и исправления ошибок. 1 ил. с 9 (Л С вЛ СО 90 О 41 Do

ВНИИПИ Заказ 3293/50 Тираж 671 . Подписное

- - ----- «.«-«1. -щ , „ .„- -и -. - - -г IITT

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