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

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

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

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

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

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

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

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

А 0/,, Of «г ,. . . , 0

п

в системе остаточных классов, где

U; - остатки от деления условного ,|

Обнаружение ошибок осуществляет путем введения контроля по модулю в каждой из 1-х групп (,п) и в дением остатка ъ1Пц по контрольно

числа А1, двоичный код которого соот- основанию q, который используется

ветствует исходному числу А, на набор условных оснований Р( (,п).

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

q 7/рм,

где Рп - наибольшее условное основание из их совокупности, то возможно исправление ошибок любой кратности в одном из остатков представления числа А при условии, что известно, по какому из оснований Pj(,n) произошло искажение.

Исправление может осуществляться по формуле

«1исп { i - , (1)

де

ы„d

вычисление остатка от деления х на Р; ; остаток по основанию Р ( теп

л. исправленный;

$ i - остаток по основанию Р, в котором произошло искажение;

ДоЧ - величина ошибки.

В свою очередь из выражения:

йс/( определяется

№-Ч;(и,1р( «

где Р - диапазон представления чисел в системе остаточных классов с заданными основаниями Р. (,п)

П

1-1

Р . q

Z

муле

- величина, определяемая по фор

, П-

-К. VI(3)

где к - вычисление дробной части

величины х; W; - остаток по основанию

Pi (i-1.n);

пь - весовой коэффициент основания Р( вычисляется по формуле

m

. l-N

(4)

Обнаружение ошибок осуществляется путем введения контроля по модулю 1 в каждой из 1-х групп (,п) и введением остатка ъ1Пц по контрольному

основанию q, который используется

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

Представление исходного кода А совместно с контрольным признаком С(л /ПлД , вычисленным по ВУ-коду, позволяет использовать для обнаружения ошибок тот факт, что любое искажение исходного кода по одному из условных оснований PJ переводит условное число А из диапазона ( 0, Ј) в диапазон () где (Р и Р - величины рабочего и полного диапазонов представления чисел в системе остаточных классов соответственно, т.е. если будет выполняться неравенство.

AS 9,

то

И

(5)

А1 искажено. Из теории системы остаточных классов известно, что

п-н

4

А « IZoLiB; i --

гн

Ґх,в,

р, (6)

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

Ш;Р

В;

Ргде Р - диапазон представления чисел

в СОК.

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

2 7 - (7)

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

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

г 1оё,1 ,

где 3YL вычисление ближайшего

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

Of r,n

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

i

logoal

+ 1

1633497

5

0

5

0

5

0

5

0

мы

дробная часть которой

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

входы величине к; . Пирамидальный сумматор 9 выполняет вычисление сум- п« . ЈЦ -L™-i (-.4 Р;

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

Блок 23 памяти предназначен для выбора величины Р по номеру i, поступившему на его адресный вход. Умножитель 25 перемножается на величину Р; с числом Z,сформированным на выходе пирамидального сумматора 9 и подает результат на вход блока 26 памяти.

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

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

В устройстве производится и контроль с использованием ВУ-кода. Для этого информация с выходов регистров группы 7 подается на адресные входы группы 8 блоков памяти. По этим адресам из группы 8 блоков памяти выби(У i m (

раются величины ----, которые складываются на пирамидальном сумматоре 9 и

дробная часть полученной суммы подается на блок 15 сравнения, где она сравнивается с пороговой константой /q, выбираемой из блока 14 памяти, При отсутствии ошибок на выходе блока 5 сравнения будет логический ноль Инвертируясь на логическом элементе НЕ 16, этот сигнал подается на вход логического элемента И 17, на второй вход которого подана логическая единица с первого выхода блока 6 памяти. На выходе логического элемента И 17 формируется единичный сигнал, который проходит через логический элемент ИЛИ 19 и подается на первый вход коммутаторов группы 10. Этот сигнал подключает выходы всех регистров группы 7 ко всем информационным выходам устройства 28 и информация выдается потребителю.

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

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

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

На входы блока 12 элементов ИЛИ поступает искаженная группа, а на входы блока 13 элементов ИЛИ поступает ее номер i.Номер группы i, пройдя через блок 13 элементов ИЛИ, поступает на адресный вход блока 23 памяти, из которого выбирается величина условного основания Р;, поступающая на дешифратор 24, возбуждая соответствующий вход, а также на адресные входы блока 26 памяти, где является частью адреса. Тем,временем на выходе пирамидального сумматор,- 9

v

уже формируется величина Z

-If:

J i-.-t L

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

5

адреса. Заключительной частью адреса блока 26 памяти является код искаженного остатка, который попадает на адресный вход этого блока памяти, приходя через блок 12 элементов ИЛИ. Таким образом, формируется адрес блока 26 памяти, из которого на основании формулы (1) выбирается неправильная группа И, через коммутатор 27,

0 открытый при отсутствии сигнала с выхода логического элемента ИЛИ 21, подается на входы всех регистров группы 7. Но запись происходит только в i-й регистр, так как сигнал логической единицы появляется на i-м выходе дешифратора 24 и, проходя через элемент ИЛИ блока 5, разрешает запись только в этот i-й регистр группы 7.

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

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

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

В случае, когда обнаруживающие способности кода по модулю недостаточны для обнаружения ошибки, но ошибка обнаруживается при контроле ВУ-кодов, устройство работает аналогично. В этой ситуации на выходе блока 5 сравнения будет сигнал логической единицы, который в блоке 6 памяти возбудит первый выход. Оба этих сигнала подаются на вход элемента И 20, единичный сигнал с выхода которого поступает на вход логического элемен- та ИЛИ 21 и с его выхода на вход коммутатора 27 и сигнальный выход 29 устройства.

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

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

0

5

5 о 0

0

5

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

Изобретение относится к вычислительной технике и МОЖРТ быть использовано в цифровых ЭВМ повышенной информационной надежности. Целью изобретения является расширение функциональных возможностей за счет контроля по модулю в каждом из остатков по рабочим основаниям, упрощения структуры и повышения быстродействия устройства. Устройство содержит входы 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