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

 

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

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

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

РЕСПУБЛИК

А1 (19) (11) (51) 4

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

К ABTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTKPbITHA (2 1) 3808769/24-24 (22) 29. 10.84 (46) 15.06.86. Бюл. ¹ 22 . (72) В.С. Василенко, С.Е. Карловский и Ю.В. Василенко, (53) 683.1{088.8) (56) Авторское свидетельство СССР № 840912, кл. С 06 F 11/08, 1979.

Авторское свидетельство СССР № 1111169, кл. С 06 Р 11/08, 1982. (54) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ И

ИСПРАВЛЕНИЯ ОШИБОК В КОДОВОЙ ПОСЛЕДОВАТЕЛЬНОСТИ (57) Изобретение относится к вычислительной технике и может быть использовано в цифровых ЭВМ повышенной информационной надежности. Целью изобретения является расширение функцио1 нальных возможностей за счет обеспечения возможности контроля кодовой последовательности, представленной в системе счисления, отличной от остаточных классов, а также снижение из быточности кодовой последовательности. Устройство формирует код условных вычетов. Информационная часть исходного кода числа сопровождается контрольным признаком. Исходный код условно разбивается на группы разрядов и тем самым представляется в виде условного числа. Расчет контрольного признака исходного кода производится по известным соотношениям.

Любое искажение исходного кода по од.ному из условных оснований переводит остаток от деления исходного кода из одного диапазона s другой. Этот факт ислольяуеуся Лля обнаруяання и ис- а правления ошибок. I ил.

1238078

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

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

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

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

А на набор взаимно простых основа-! ний P Р,,...,Pn. Таким образом, исходный код, например двоичное число

А, представляется в виде условного ( числа А

А 0 у 0 у ° ° ° у 06 и представленного в системе остаточных 4 классов, где Ф, — остатки от деления условного числа A, двоичный код которого соответствует исходному числу А, на набор условных оснований

Р, (i = 1,2,...,n). .Из теории остаточных классов известно, что если имеется остаток от деления числа .А на контрольный модуль q причем

50 q где Р„ и Рд, — наибольшие условные основания из их совокупности, то возможно обнаружение и исправление ошибок любой кратности в одном из остат- 55

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

Представление исходного кода А совместно с контрольным признакоМ М, вычисленным по правилам системы оста точных классов в виде условного слова в системе остаточных классов (ВУкод), позволяет использовать для обнаружения и исправления ошибок тот факт, что любое искажение исходного кода по одному из условных оснований

P переводит условное число А из дйапаэона (О, P) в диапазон (P, Р ), где Р= .Е Р;. При этом исходное услов1 ное число A увеличивается на величину 1, К, где Rj= P /P, т.е. иска1 женное число (А ) равно:

1 4

A=A+PR ,) (1)

Величина определяется величиной ошибки по основанию P, т.е.. величиной ьо = a,— a; Р

В последнем выражении М (t6 ) — соот-! ветственно неискаженная и искаженная части исходного кода, соответствующие условному основанию P,,а знак (xj P означает вычисление остатка от деления величины Х на Р . Причем, как следует из выражения (1), к =" . = з

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

А — 11 R

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

А = 0(, В (4) где В=Р,;

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

В, = Р, (5)

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

;=I ) г,, 1238078

Представим (4) в виде !!Ф

В д К ю ! =! . где квадратные скобки означают вычисление целой части соответствующего выражения. Тогда условие .(3) с учетом (2) может быть записано в виде! Ф! 1 л+1 1 !! !! ; В ° - — !! ; В; R-К вЂ” 2. к,  —

Кг =

KgpВ R P

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

<(2 — — (Р2) !

I (б) р

ЕР— (ZP ) (20 где

«j -. («„- «Д p,"- =(А г - (А — (г ) р. =

-(«,— (e;!!;3 г,, то 40

ЬЫ = jt; RÄ) Р;, „де с учетом (2) е! -() = (г!,), т.е.!

«;= («; ZP,)!!P .

Из последнего выражения следует, что величина ошибки по i-му условно- 50 му основанию .h k> однозначно опреде- ляется величиной Z (R и P при выб1 ранкой системе условных оснований являются константами) и может быть определена либо из таблицы соответст- Ы вия ЬЫ > Е, либо расчетным путем.

Первый способ является предпочтительным при малой разрядности контролиПоскольку условие (3) и эквива-. лентное ему условие (6) справедливы только для того основания, по которому имеет место искажение исходного кода, то они позволяют определить место возникновения ошибки. С этой ЗО целью необходимо вычислить величину .

Z (7) и проверить выполнение условия (б) для каждого из n:îñíoBàíèé Р .

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

Так как

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

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

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

Устройство содержит регистры 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 при наличии на управляющем входе сигнала с выхода элемента И 3 1 обеспечивает передачу содержимого группы выходов регистра 18 на регистр 2. Коммутатор 6 при наличии на управляющем входе сигнала с выхода элемента И 31 обеспечивает передачу входного сообщения, кроме его контрольного признака, с регистра 1 на регистр 19. Коммутаторы 7, при наличии на управляющем входе сигнала -с выхода соответствую-. щего элемента И 30 группьг, обеспечивает передачу содержимого регистра

18 на один из соответствующих узлов свертки 35 ° Коммутатор 8, при наличии на управляющем входе сигнала с соответствующего выхода дешифратора

23, обеспечивает передачу содержимого соответствующей. группы выходов регистра 19 на вход сумматора 27. Коммутатор 9, при наличии на управляющем входе сигнала с. выхода элемента И 31, обеспечивает передачу показаний счетчика 21 на вход блока памяти 14. Коммутаторы 10, при наличии на управляющих входах сигнала с соответствующе1238078

ro элемента задержки 16 группы, обеспечивают передачу содержимого сумматора 27 на один из шифраторов группы 36. Регистр 1 предназначен для

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

Регистр 1 .имеет (К+1) групп выходов, содержащих информационную часть сообщения Z,, Z,..., Е и контрольный признак Z +„..Регистр 19 предназначен для хранения выходной информации устройства. Регистр 18 предназначен для хранения произведения, образовавшегося на умно* теле 25 Регистр 18 15 имеет две группы выходов, одна из которых предназначена для хранения целой части произведения (ЕРД, а дру-. гая — дробной части ZP .

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

Группа блоков памяти 11 предназначены для хранения констант вида

g m !Ð . Блоки памяти 12, 13 и 14 пРедйазначены для хранения констант

P D, К соответственно.

Койстайты D. хранятся в обратном коде, а Р и К. — в прямом коде. В качестве группы блоков памяти 11 и блоков памяти 12 — 14 могут исполь30 зоваться, например, запоминающие устройства, построенные на элементах

К .155РУ1 или К 155 РУ2.

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

Умножитель. 25 предназначен. для образования произведений ZP и(ЕРДК .

B качестве умножителя может быть использоЪана, напрнмер, микросхема, 40 входящая в Микропроцессорный комплект серии КР1802,(умножитель 16х16). В целях повышения быстродействия может использоваться, например, множительное устройство, в котором использован 15 метод ускорения умножения 2-ro порядка.

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

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

Группа узла свертки 35 и группа

«нифраторов 36 предназначены для получения свертки по mod P,, Р,..., Р„, величин ГЕР;) К и (Е„ -ЬЮ, ) соответственно.

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

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

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

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

В исходном состоянии счетчики 20 и 21, триггер 33 находятся в нулевом состоянии. На регистр 1 поступает принятое сообщение — кодовая последовательность (кодограмма). С инверсного выхода триггера 33 поступает сигнал "1" на элемент И 29, разрешающий поступление тактовых импульсов на счетный вход счетчика 2О. По тактовым импульсам распределитель, состоящий из счетчика 20 и дешифратора 22, последовательно вырабатывает сигналы, поступающие на коммутаторы группы 3.

Эти сигналы разрешают передачу инфор" мации контролируемых, разрядных групп, на которые условно "разбито" поступившее сообщение (кодограмма), на соответствующие блоки памяти группы 11.

Содержимое группы разрядов сообщения по основанию D служит адресом константы р ш /Р в каждом из соответствующйх блоков памяти группы 11.

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

Информация последней (К+1)-й группы передается по сигналу с последне1238078 го (К+1)-го выхода дешифратора 22.

Этим же сиги лом устанавливаются в

В1 И

0 счетчик 20 и в единичное состояние триггер 33.

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

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

Счетчик- 21 имеет модуль счета

М = К (К вЂ” количество контролируе Ч, мых групп разрядов). Показание второго счетчика 21 служит адресом к н20 стант В, D и Р, хранящихся в бло- ках памяти 12, 13 и 14 соответственно. Из блоков памяти 12 и 13 выбираются константы P u D . Константа Р.

3 5 поступает на умножитель 25, константа В. на схему сравнения 26. С поступлением первого тактового импульса с элемента И 28 на коммутатор 4 величина Е, образованная на наканливающем сумматоре 24, поступает на первыи вход умножителя 25, на второй

ЗО вход которого поступает константа P с блока памяти 12. На умножителе 25 образуется произведение ZP>, которое с его выхода поступает на регистр 18.

Дробная часть величины ZP e груп-З5

4 пы выходов регистра 18 поступает на схему сравнения 26. На схеме сравнения образуется сумма величины В, Э представленной в обратном коде, и дробной части величины ZP

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

Проверка последующих групп разрядов кодовой последовательности осуществляется аналогичным образом. Если ошибка не обнаружится ни в одной из групп разрядов сообщения, то показание счетчика 21 равно К, при этом на последнем (К-м) выходе дешифратора 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, в котором происходит выборка константы К1 и передача ее на умножитель 25. Кроме того, через коммутатор 6 с группы выходов регистра 18 на умножитель 25 через регистр 2 поступает целая часть произведения jZP1). На умножителе 25 образуется произведение (ЕРД R которое записывается в регистр 18.

Сигнал ошибки, пройдя через элемент задержки 15, сбрасывает счетчик 2 1 и ноль. Этот же сигнал поступает через элемент ИЛИ 32 на нулевой вход триггера 33.

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

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

25 изобретения

Фар мула

Устройство для обнаружения и исправления. ошибок в кодовой последовательности, содержащее два регистра, 30 схему сравнения, триггер, первый дешифратор, элемент ИЛИ, первый элемент

И..и элемент НЕ, причем группа выходов

1 первого регистра является группой инФормационных выходов устройства ,л и ч а ю щ .е е. с я тем, что, с целью расширения фуйкциональных возможностей за счет обеспечения возможности контроля кодовой последовательности, представленной в системе счисде40 ния, отличной от остаточных классов, а также снижения избыточности кодовой последовательности, оно содеряйт накапливающий сумматор, умножитель, сумматор, четыре группы коммутаторов, два регистра, группу блоков памяти, 45 группу элементов И, группу узлав свертки, группу шифраторов, группу элементов задержки, два счетчика, четыре коммутатора, два элемента за» держки, второй и третий элементы И и второй дешифратор, причем К групп информационных входов устройства соединены с группами информационных входов первого регистра, К групп выходов которого,, где К вЂ” число групп 55 сообщений, соединены с группами информационньцс входов соответствующих

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

Информация одной из групп выходов регистра 19 по разрешающему сигналу с выхода дешифратора 23 поступает через соответствующий коммутатор 8 группы на вход сумматора 27. Результат свертки содержимого регистра 18 поступает на другой вход сумматора 10

27. Разрешающий сигнал с дешифратора

23 через. соответствующий элемент задержки 16 группы поступает на управляющий вход соответствующего коммутатора 10 группы. По этому сигналу образовавшаяся на сумматоре 27 раз- ность поступает на шифраторы 36 групп, осуществляющие свертку по сосоответствующему молулю, с шифратора группы 36 величина. (Š— ь0 1Р пос- 20

) 3> тупает на соответствующую группу разрядов регистра 19, после чего в регистре 19 хранится исправленная информация. мационным входом первого коммутатора,. группа выходов контрольного признака первого регистра соединена с группой информационных входов (К+1)-го коммутатора первой группы, выходы коммутаторов первой группы соединены с адресными входами соответствующих блоков памяти группы, выходы которых соединены с информационными входами

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

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

1238078

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

Произв.-полигр. пр-тие, г. Ужгород, ул. Проектная, 4 входом второго коммутатора и счетным входом второ,".:"о счетчика, разрядные выходй которого соединены с адресными входами первого и второго блоков

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

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