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

 

Изобретение относится к вычислительной технике и МОЖРТ быть использовано в цифровых ЭВМ повышенной информационной надежности. Целью изобретения является расширение функциональных возможностей за счет контроля по модулю в каждом из остатков по рабочим основаниям, упрощения структуры и повышения быстродействия устройства . Устройство содержит входы 1 и 2 информационных и контрольных разрядов, блок 3 элементов ИЛИ, блок 4 элемен U тов сравнения, блок 5 элементов ИЛИ, блок 6 памяти, группу 7 регистров, , I группу 8 блоков памяти, пирамидальный сумматор 9, группу 10 коммутаторов , группу 11 блоков памяти, блоки 12 и 13 элементов ИЛИ, блок 14 памяти, блок 15 сравнения, элемент НЕ 16, элемент И 17, элемент 18 задержки, эпемент ИЛИ 19, элемент И 20, элемент ИЛИ 21, блок 22 модульной свертки, блок 23 памяти, дешифратор 24, умножитель 25, блок 26 памяти, коммутатор 27, информационные и сигнальный выходы 28 и 29. Устройство обнаружения позволяет определить количество возникших ошибок. Если в пакете информации имеется ошибка такой кратности, что превышается возможность устройства по исправлению, то исправление не производится, если кратность ошибки не больше допустимой, то она исправляется , и скорректированная информация выдается параллельным кодом. Таким образом, на выход устройства поступает только неискаженная информация . 1 ил. с Ј (Л о 00 оо Јь СО 1

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

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

РЕСПУБЛИК,80„1633497

А1 (51)5 Н 03 М 13 00

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

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

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫ7ИЯМ

ПРИ ГКНТ СССР (21) 4683210/24 (22) 27.04,89 (46) 07.03.91. Бюл. N 9 (72) В. С. Василенко, А. Б. Надыкто и В.А.Вересенко (53) 681.325(088.8) (56) Авторское свидетельство СССР

II} 960823, кл. G 06 F 11/08, 1980.

Авторское свидетельство СССР

11} 1238078, кл. G 06 F ll/08, 1984. (54) УСТРОЙСТВО ДЛЯ ОБНАРУ111ЕНИЯ И

ИСПРАВЛЕНИЯ ОПИВОК В КОДОВОЙ ПОСЛЕДОВАТЕЛЬНОСТИ (57) Изобретение относится к вычислительной технике и может быть использовано в цифровых 3ВМ повышенной информационной надежности. Целью изобретения является расширение функциональных возможностей за счет контроля по модулю в каждом из остатков по рабочим основаниям, упрощения структуры и повышения быстродействия устройства. Устройство содержит входы 1 и 2 информационных и контрольных разрядов, блок 3 элементов ИЛИ, блок 4 элемен2 тов сравнения, блок 5 элементов ИЛИ, блок 6 памяти, группу 7 регистров, группу 8 блоков памяти, пирамидальный сумматор 9, группу IO коммутаторов, группу ll блоков памяти, блоки 12 и 13 элементов ИЛИ, блок 14 памяти, блок 15 сравнения, элемент HF. 16, элемент И 17, элемент IS задержки, элемент ИЛИ 19, элемент И 20, элемент

ИЛИ 21, блок 22 модульной свертки, блок 23 памяти, дешифратор 24, умножитель 25, блок 26 памяти, коммутатор 27, информационные и сигнальный выходы 28 и 29. Устройство обнаружения позволяет определить количество возникших ошибок, Если в пакете ичформации имеется ошибка такой кратности, что превышается возможность устройс1ва по исправлению, то исправление не производится, если кратность ошибки не больше допустимой, то она исправляется, и скорректированная информация выдается параллельным кодом. Таким образом, на выход устройства поступает только неискаженная информация; 1 ил.

1633497

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

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

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

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

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

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

I некоторого числа А на набор взаимно простых оснований Р!,Р,...,Pn Таким образом, исходный код, например исходное числФ А, представляется в ! виде условного числа А !

А = 0 !, 0,. ° °, Ы!!, в системе остаточных классов, где

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

I числа А при условии, что известно, по какому иэ оснований Р,(i=1,п) произошло искажение.

Исправление может осуществляться по формуле л (i исп = 1; — 60(!" PL где xI — вычисление остатка от де Р; ления х на Р;; д;!! !! — остаток по основанию Р;— исправленный; остаток по основанию Р в котором произошло искажение;

5df — величина ошибки.

В свою очередь Q o(. определяется из выражения:

6м; ((z v;j) (— - > (2) ! где P — диапазон представления чисел в системе остаточных классов с заданными основаниями P. (i=1,п) п !

Р= 1

1=!

P, q

Z — величина, определяемая по формуле п

2 =) — - (, 1=! (3) где 1 х(— вычисление дробной части величины х;

Ы;—

; — остаток по основанию

Р,,(i=1,п);

m — весовой коэффициент основания,Р! вычисляется по формуле —

Р (4)

Р 1 Pi

Обнаружение ошибок осуществляется путем введения контроля по модулю 1 в каждой из i-x групп (i=1 n) и введением остатка О(„,1 по контрольному основанию q который используется ветствует исходному числ А на набор условных оснований Р (1=1,n).

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

16334 как при обнаружении, так и при исправлении ошибок °

Представление исходного кода А совместно с контрольным признаком ф(< =

= 4 п, вычисленным по BY-коду, позволяет испольэовать для обнаружения ошибок тот факт, что любое искажение исходного кода по одному иэ условных оснований Р; переводит условное чис<1 10 ло А из диапазона (0,9 ) в диапазон (У Р) где 9 и Р— величины рабочего и полного диапазонов представления чисел в системе остаточных классов соответственно, т.е. если будет выполняться неравенство.

А ) (5) то А искажено.

Из теории системы остаточных классов известно, что 20

«i<

Х с(В; <;в;—

<- 4

А P, (б)

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

m;P

В ° р Э

I где P — - диапазон представления чисел в СОК.

После несложных преобразований, с учетом (4) и (3) неравенство (5) примет вид

Z 7 ——

30 (7) Это условие реализуется в предлагаемом устройстве для обнаружения ошибок с использованием BY-кода. 40

Для увеличения вероятности обнаружения ошибок и для определения номера искаженной группы i(i = 1,n), в которой произошло искажение, вводится контроль по модулю 1 в каждой из 45 групп представления. Обозначим через

r — разрядность 1, тогда

r = )log 1, где J Y(— вычисление ближайшего

50 большего целого Y.

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

О r.n

7 где п — число контролируемых групп, а общая избыточность ч - Q<+ E1og

97 6

Группа 8 блоков памяти предназначена для табличного вычисления вели«<,; m; чин -- --- по приходящей на адресные

< < входы величине Ы; . Пирамидальный сумматор 9 выполняет вычисление сум— «(; m; мь< - †---, дробная часть которой

<=< Р; подается на блок 15 сравнения, предназначенный для сравнении ее с числом 1/q, которое постоянно хранится в блоке 14 памяти, и выдачи сигнала ошибки, выявленной контролем с испопьзованием BY-кода.

Блок 23 памяти предназначен для выбора величины Р, по номеру i поступившему на его адресный вход. Умножитель 25 перемножается на величину Р; с числом Z,ñôîðìèðîâàííûì на выходе пирамидального сумматора 9 и подает результат на вход блока 26 памяти.

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

В исходном состоянии на выходах группы 11 блоков памяти номера групп отсутствуют, поэт му возбуждается ну-, левая шина дешифратора 24 и этот сигнал разрешает запись информации с входа 1 через блок 3 элементов ИЛИ в регистры группы 7 ° Поступающая информация может быть верной, может иметь одну или более ошибок. Рассмотрим по порядку все возможные варианты.

Рассмотрим работу устройства, когда полученная информация не искажена.

Кроме регистров группы 7, входная информация по К-разрядной шине со входов 1 поступает на блок 22 модульной свертки, где вычисляются ее свертки по модулю 1, которые в блоке 4 элементов сравнения сравниваются с исходными свертками, полученными по

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

При этом возбуждается первый выход блока 6 памяти, сигнал с выхода которого имеет единичный уровень и подается на входы элементов И !7 и 20.

В устройстве производится и конт55, роль с использованием BY-кода. Для этого информация с выходов регистров группы 7 подается на адресные входы группы 8 блоков памяти. По этим адресам из группы 8 блоков памяти выби1633497 (g m раются величины ----- которые складыр %

1 ваются на пирамидальном сумматоре 9 и дробная часть полученной суммы пода5 ется на блок 15 сравнения, где она сравнивается с пороговой константой

1/q, выбираемой иэ блока 14 памяти, При отсутствии ошибок на выходе блока 15 сравнения будет логический ноль.10

Иннертируясь на логическом элементе

НЕ 16, этот сигнал подается на вход логического элемента И 17, на второй вход которого подана логическая единица с первого выхода блока 6 памяти.

На выходе логического элемента И 17 формируется единичный сигнал, который проходит через логический элемент

ИЛИ 19 и подается на первый вход коммутаторов группы 10. Этот сигнал подключает выходы всех регистров группы 7 ко всем информационным выходам устройства 28 и информация выдается потребителю.

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

Сигнал единичного уровня, поступающий на второй вход коммутатора группы 10, разрешает подключение выхода соответствующего регистра группы 7 к входам блока 12 элементов ИПИ, обеспечивает выборку номера искаженной группы i из группы 11 блоков памяти и, попадая на адресный вход блока 6 памяти, возбуждает его второй выход. С второго выхода блока 6 40 памяти сигнал логической единицы поступает на элемент 18 задержки, где задерживается на время, необходимое для исправления ошибки и записи исправленного остатка в соотнет- 45 ствующий регистр группы 7.

Исправление происходит следующим образом.

На входы блока 12 элементов ИЛИ поступает искаженная гРуппа, а на входы блока 13 элементов ИЛИ поступает ее номер i.Íîìåð группы i, пройдя через блок 13 элементов ИЛИ, поступает на адресный вход блока 23 памяти, из которого выбирается величи55

На условного основания Р;, поступающая на дешифратор 24, возбуждая соот; нетстнующий вход, а так p на адресные входы блока 26 памяти, где является частью адреса. Тем,временем на выходе пирамидального сумматор,; 9 йе1 (, I уже формируется величина Z = р. л которая, поступая на вход умножителя 25, перемножается с величиной Р; и целая часть этого произведения поступает на адресные входы блока 26 памяти, где также составляет часть адреса. Заключительной частью адреса блока 26 памяти является код искаженного остатка, который попадает на адресный вход этого блока памяти, приходя через блок 12 элементов ИЛИ, Таким образом, формируется адрес блока 26 памяти, из которого на основании формулы (1) выбирается неправильная группа И, через коммутатор 27, открытый при отсутствии сигнала с выхода логического элемента ИЛИ 21, подается на входы всех регистров группы 7. Но запись происходит только в i-й регистр, так как сигнал логическ и единицы появляется на 1-м выходе дешифратора 24 и, проходя через элемент ИЛИ блока 5, разрешает запись только в этот i-й регистр группы 7 °

После записи исправленного остатка н i-й регистр группы 7 на выходе элемен,а 18 задержки появляется сигнал, который, проходя через элемент

ИЛИ 19, подается на вход коммутаторон группы 10. Коммутаторы группы 10 обеспечивают подключение выходов регистров группы 7 к информационным выходам 28 устройства. Таким образом, исправленная информация выдается потребителю.

Если при контроле по модулю 1 в блоке 22 модульной свертки обнару и1 ваются дне и более ошибок, то возбуж0 дается третий выход блока 6 памяти.

Сигнал единичного уровня на его выходе проходит через логический элемент ИЛИ 21 и подается на сигнальный выход 29 устройства. Уровень логической единицы на этом выходе свидетельствует о невозможности исправления устройством принятой информации. В этой ситуации на выходе блока 26 памяти возникает случайная информация, которая может, при записи ее в регистры группы 7, вызвать дополнительные искажения принятого сообщения. Для исключения подобной ситуации уровень логической единицы подается на управляющий вход коммутатора 27 и запреща!

633497

IO ет передач> информации через пего на входы блока элементов ИЛИ 3.

В случае„ когда обнаруживающие способности кода по модулю недоста5 точны для обнаружения ошибки, но ошибка обнаруживается при контроле

BY-кодов, устройство работает аналогично. В этой ситуации на ньгходе блока !5 сравнения будет сигнал логичес- !О кой единицы, который в блоке 6 памяти возбудит первый выход. Оба этих сигнала подаются на вход элемента И 20, единичный сигнал с выхода которого поступает на вход логического элемен- !

5 та ИЛИ 21 и с его выхода на вход коммутатора 27 и сигнальный выход 29 устройства.

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

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

ИЛИ, отличающее с я тем, что, с целью расширения функциональных

40 воэможностей за счет контроля по модулю в каждом иэ остатков по рабочим основаниям, упрощения структуры и повышения быстродействия устройства, в него введенЬ1 первый-четвертый блоки

45 элементов ИЛИ, второй элемент ИЛИ, пирамидальный сумматор, вторая группа блоков памяти, четвертый блок памяти и блок элементов сравнения, первые входы которых являются входами контрольных разрядов устройства, первые входы первого блока эле1яентон ИЛИ объединены с входами блока модульной свертки и являются входами информационных разрядов устройства, выходы блока модульп 7й свертк1. подключены соответственно к вторым входам элементов сравнения блока, выходы которых подключены к вторым входам коммутаторов группы, входам блокон памяти второй группы и входам четвертого блока памяти, первый выход которого подключен к вторым входам первого и второго элементов И, ныхо ды которых подключены состнететненH(7 к первым н х Ол ам Опно11ме11HL lх эле— ментов ИЛ1 ., второй выход четвертого

6лс ка памят11 через -лемент задержки подключс и к EE сорому вход . н торо гс7 зле ме11та И II I ныхОд кОто17О1 О !1Одклю чен к тре TE им нходам ко1мутаторон группы, первые и вторые выходы которых 11одключены соответственно к нходам второго блока элементов ИЛИ и являются информационными выходами устроиства, выходы блокс; памя-.и втор7й группы подключены к входам третьего блока элементов ИЛИ, выходы которого подключены к входам второго блока памяти, первым входам третьего блока памяти и входам дешифрато-тОРа, НУЛЕНОй НЫХ»Ц кот РОГО ПОДКЛЮчен к первым входа; ° яементов ИЛИ четвертого блока, .стал,ные выходы дешифратора подключены к вторым входам соответствующих элементов ИЛI1 четвертого блока, выходы которых подключены к первым входам соответствующих регистров группы, входы и выходы блоков памяти первой группы подключены соответственно к выходам регистров группы и входам пирамидального сумматора, выходы которого подключены к вторым входам блока сравнения и умножителя, выходы которого и выходы второго блока элементов ИЛ1! подключены соответственно к вторым и третьим входам третьего блока памяти, выходы которого соединены с информац1гонными входами коммутатора, третий выход четвертого блока памяти подключен к второму входу первого элемента ИЛИ, выход которого является сигнальным выходом устройства и подключен к управляющему входу коммутатора, выход которого подключен к вторым входам элементов ИЛИ первого блока, ныходы которых подключены к вторым входам регистров группы.