Устройство для исправления пакета ошибок длины два Советский патент 1990 года по МПК H03M13/02 

(21)4419948/24-24

(22)03.05.88 .

(46) 15.07.90. Бил. № 26 (72) А.В. Маркарян

(53)681.325.63(088.8)

(56) Хетагуров #.А. и др. Повышение надежности цифровпх устройств методами избыточного кодирования. М.: Энергия, 1974, с. 51-56.

Авторское свидетельство СССР № 720757, кд. Н 03 М 13/02, 1980.

Патент США № 3755779, кл. G 06 F 11/12.

(54)УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ ПАКЕТА ОШИБОК ДЛИНЫ ДВА,

(57) Изобретение относится к вычислительной технике, а именно к передачам информации, и может быть использовано для контроля оперативных и постоянных запоминающих устройств. Целью изобретения является повышение достоверности исправляемой информации. Устройство содержит генератор 1 синдрома, генератор 2 сигналов оиибок, селекторы 3,4, дешифраторы 5,6, первый блок 7 суммматоров по модулю два, преобразователь 8 кода, второй блок 9 сумматоров по модулю два, информационные входы 10, выходы 11, 12, 13 сигналов ошибок, информационные выходы 14. 1 ил.

Изобретение относится к вычислительной технике, а именно к передачам информации, и может быть использовано для контроля оперативных и постоянных запоминающих устройств. Целью изобретения является повышение достоверности исправляемой информации. Устройство содержит генератор 1 синдрома, генератор 2 сигналов ошибок, селекторы 3, 4, дешифраторы 5, 6, первый блок 7 сумматоров по модулю два, преобразователь 8 кода, второй блок 9сумматоров по модулю два, информационные входы 10, выходы 11, 12, 13 сигналов ошибок, информационные выходы 14. 1 ил.

14.2

СД

оо ро

to

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

Цель изобретения - повышение достоверности исправляемой информации путем исправления максимального числа п-1 пакетов ошибок длины два

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

Устройство содержит генератор 1 синдрома, генератор 2 сигналов ошибок, селекторы 3 и 4, дешифраторы 5 и 6, первый блок 7 сумматоров по модулю два, преобразователь 8 кода,второй блок 9 сумматоров по модулю два, информационные входы 10, выходы 11- 13 сигналов ошибок и информационные выходы 14.

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

Код образуется путем сокращения числа m информационных символов модифицированного кода Хэмминга с обнаружением двойных ошибок на основе матрицы Н, содержащей п различимых кодов столбцов нечетного веса, таким образом, чтобы число п было кратно числу г n-m контрольных символов исходно-

го кода Хэмминга (2 , 2 -г), где и 2 ; .матрш Н представлена в виде Н 11 ct1 -...1; ot ;...; оС Ч , rfleodifc- подматрица размером rx n/r; k |l i, 0; .,+ Ј (mod r); /

Ј const1 подматрицы об к были бы составлены путем (IK, )mod г цикличест ких перестановок строк подматрицы oi. 1, а значение столбцов в подматрице о64 и значение f были бы выбраны так, чтобы матрица G,столбцы которой формируются в результате суммирования всех соседних столбцов матрицы Н, содержала бы различимые коды, столбцов ч четного веса с аналогичной структурой

с-|1Г;---1Г ;---р |1 г«еР1К - подматрица, являющаяся результатом

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

((

i ап «а.

аи а.) длины п где а, - двоичный (п -Т 7

символ кода а( при j , совпадает с одним из значений столбцов матрицы II, а синдром ошибки в соседних разрядах кода а - с одним из значений столбцов матрицы G.

В этом случае, например, код Хэмминга (32, 26) преобразуется в код

(24, 18), исправляющий пакеты ошибок длины два, с матрицей Н ||ot° jo(4;rtz o ;

где

г 6; Ј (4; 1J; i к f 0-5} ( i2 , i,2(4+4)mod6, i4 2-1 1, ig., (5-4)mod6); каждому столбцу этих подматриц ОС1 соответствует один из символов а . п 24-разрядного кода а 24 (а, а2о. .a j. о. агзам- при j J1 - 24J. Для упрощения схемы кодирования, также как и в случае кода Хэмминга, целесообразно в качестве контрольных символов выбрать значения а,, а, ае) а,3, а,7 и а, соответствующие первым столбцам этих подматриц «.

Матрица G ||p°: :fi2: fb | f) j/i H.образуется из следующих подматриц

d,d2djd4 dj-djdrdg d9d,od,,d,Ј

, Каждый j-й столбец в подматрицах В кобозначен символом dj ; dj S +

+ S , + , (mod2); Sj - синдром одиночной ошибки, соответствующий j-му столбцу матрицы Н. Например, если в коде а п ошибка произошла по разрядам а5 и а$ , то j 5, S5 ||000010llT, S6 Ц100011Н a ds S + Sg (mod2) || 00001)1r, где Т - знак транспонирования матрицы.

Декодирование предлагаемого кода в устройстве производится в три этапа.

Первым этапом декодирования вычисляется значение r-разрядного синдрома S по известному выражению: S . Если в коде а 1 отсутствуют ошибки, то (нулевой синдром). В случае одиночной ошибки по разряду a j получа ется (ненулевой синдром) нечетного веса, совпадающий с j-ым столбцом матрицы Н. При возникновении пакета ошибок длины два по разрядам

1

и

aj4,- S dj

четного веса. Если

хретьим этапом производится коррекция кода а путем вычисления по

t О

с е с 1 ЛИГ

и е,

0 с е6

ч „ чзначениям j поразрядной суммы:

значение S t 0 и не совпадает ни с од- а(п + ец + е (mod2). Например, если ним из значений столбцов матриц Н и e(L О 000 100000000001 0000) , то после G, значит имеет место неисправная вычисления значения синдрома по S ошибка (произвольная четная или нечет-25 „ дешифрации S получаем нал ошибка).

Вторым этапом декодирования производится дешифрация S, результатом ко торой являются коды e - (ete... е:. еп-|) и еп (егс4...е j+,...eft), составленные из символов ej ГО; 1 j соответственно с нечетными j и четными j+1 индексами.

При S 0 и S Ј О, не совпадающим ни с одним из значений столбцов матриц

в коде а4 проинвертированы разряды 5 и 6, обозначенные знаком , Откорректированный код а 1 1 имеет следующий 30 вид: ас (100001000000000100010000), который удовотетворяет соотношению «

35

S а 24)ТхН 0.

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

С входов 10.1; 10.2,...,10.(п-1), 10.п n-разрядный код я(п| (... аи, а) в параллельной форме поступает на иходы соответствующих сумматоров 7„1, 7.2,....7.(п-1), 7.п и на входы генератора 1. В соответствии с первым этапом декодирования генератор 1 по матрице Н на своих выходах .вырабатывает r-разрядный синдром S, который поступает на входы генератора 2 и преобН и G, выполняется условие: ен ец

35

0. При нечетного веса только одно значение ej в кодах ен и еи может равняться единице. Если ошибка

кода ,ото BU. 0, ew 0 с ej 1;

происходит по нечетному разряду а

L(| тл п.. - П 0

тг Р,. О Р., Ј

а в случае ошибки по четному разряду aj+, - ен 0, еи 0 с ej.ft 1. Например, если ошибка происходит по разря,(«)

40

С входов 10.1; 10.2,...,10.(п-1), 10.п n-разрядный код я(п| (... аи, а) в параллельной форме поступает на иходы соответствующих сумматоров 7„1, 7.2,....7.(п-1), 7.п и на входы генератора 1. В соответствии с первым этапом декодирования генератор 1 по матрице Н на своих выходах .вырабатывает r-разрядный синдром S, который поступает на входы генератора 2 и преобду а 5 кода а(. , то еи (000000000000} д§ раз0вателя 8, на первые входы селектоен(001000000000) се 1; при ошибке по разряду ag - е« (000000000000), еу (001000000000) с еб 1.

В случае S ф- 0 четного веса с учетом d: Sj + S;+i(raod2) сначала производится преобразование S d j в S. с нечетным индексом j и вычисление с четным индексом j + 1 на основе Sj4 Sj + dj(mod2), а затем аналогично случаю S jЈ 0 нечетного веса генерируются значение еи / 0 и е,,0

по

4

и

С

I

W

:м

м+

соответственно. Указанное

преобразование S dy в S1 производится путем выбора Si по значению d; из J У

ров 3 и 4 и блока 9.

1iff В случае возникновения в коде а

одиночной ошибки вырабатывается S Ј О JQ нечетного веса, по которому генератор

2на своем первом выходе вырабатывает сигнал одиночной ошибки, поступающий на выход 12 устройства. При этом сигналы двойной и неисправимой ошибок на

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

значение S: с нечетным

5

таблицы преобразования, где каждому значению dj матрицы G поставлено в соответствие индексом j.

Например, для кода (24, 18) в соот ветствии с указанными примерами матриц Н и G получается таблица пре- - образования (см. ниже).

(24| Если в коде а происходит ошибка

но разрядам а5 и а6, то для j 5, dr |Ю0001||Т согласно приведенной таблице должно быть выбрано значение S5 |l 000010| т,- вычислено Stf df + + Sy(mod2) f|l0001lllT. После дешифрации Sj и S g получаются коды е н 0 с 1 и еи Ј 0 с

20

хретьим этапом производится коррекция кода а путем вычисления по

t О

с е с 1 ЛИГ

и е,

0 с е6

а(п + ец + е (mod2). Например, если e(L О 000 100000000001 0000) , то после вычисления значения синдрома по S 25 „ дешифрации S получаем

в коде а4 проинвертированы разряды 5 и 6, обозначенные знаком , Откорректированный код а 1 1 имеет следующий 30 вид: ас (100001000000000100010000), который удовотетворяет соотношению «

35

40

S а 24)ТхН 0.

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

С входов 10.1; 10.2,...,10.(п-1), 10.п n-разрядный код я(п| (... аи, а) в параллельной форме поступает на иходы соответствующих сумматоров 7„1, 7.2,....7.(п-1), 7.п и на входы генератора 1. В соответствии с первым этапом декодирования генератор 1 по матрице Н на своих выходах .вырабатывает r-разрядный синдром S, который поступает на входы генератора 2 и преобд§ раз0вателя 8, на первые входы селекторов 3 и 4 и блока 9.

1iff В случае возникновения в коде а

одиночной ошибки вырабатывается S Ј О нечетного веса, по которому генератор

2на своем первом выходе вырабатывает сигнал одиночной ошибки, поступающий на выход 12 устройства. При этом сигналы двойной и неисправимой ошибок на

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

15

селекторов 3 и 4 поступает на входы соогветствугоину дешифраторов 5 и 6, предназначенный для генерации; кодов е,„ и ец соответственно. Если ошибка происходит по одному из нечетных раз-рядов а, 5 a-JS, аЈ..„ кода а , то в соответствии с вторым этапом декодь рования дешифратором б вырабатывается код е„ - Оа а дешифратором 5 - код е и Ј 0 с сигналом е , - I коррекции на соо гветствугацем гшходе дашифрато-- ра 5. Сигнал е: 1 поступает на дру 1 ой вход соответствующего сумматора

7,1 или 7о35 или 7 о 5 т , а. г нечетным номером В результате,, сумматора ми Л 7„3; , в поочветс чвии

с третьим этапом де соп ооьштя i ене- 1 ai сулим э1 с . (tr.c 1 лвер. t pyo c;i п ксроируетсг резулыа э1 1 с ,(tr.od2)

си г/a not i е, ,,- , ,.. , рекгьрусгся о 1лбо ПЕы ; и С-тный j-й разряд а кода а Оч ьсрректпрованнь 7 разряд а% вместе с остг1къ и.М разря дани копа ч , которые с i/чех ом си О бе ч изменения генерируются на въгхоп.ах суямагоров 7, t j 7 „ 2 c u , (n -1) , / ,n , в пзраллсльноп форье rroc i ла соотве-гствугогще зыходы i4,i; и„2„ , s iAj(n-O 14.1 устройства Если иткб- ча происходит то опяс jT-ч четных

ра .олцов ае.

кода а

-и

го

е|; 0и процедура коррекции одиночной ошибки осуществляется ana- логично леивифраторок 6 ч сум атораггл

7 & 7,Ь

чегнЈ1№-т иомерамь

(И

В случае воонпкноьег- я Ј коде а па)сета ошибок длины два вырабатывает ся S - d { нечетного з са , по котором генератор 2 ка свое , jj opof выходе вьфабатывает сягьап двойног ошибки При этом сигналы одьноччой леясггт г вммой ошибок не оырабаг1Ы0з;о1ся„ Сигнал двойной отгибки поступает па управляющие входы селекторов 3 и k и ч ЯМУ од 11 ycfpoftcTiJei, В електора;с Э и 4 открываются кан- ы лро з Счтлонгие на вькод инфоркату ао с -д одьп: входов Далее вьз олняеточ э Јя ггкодл роъания кода а 1 С выхого | ре орра- зователя 89 ппеднячиачсилопо для выработки S с нечотньп1 iirvi&Tcc 1 по габли,е лреобразовак я, на J с.ые входы селектора 3 поступает счпдрсм S а на ы 1Оры 2 входы ce-neirrjos 4 с выхода блока 9 j синдром И;},с четным индексом j-ui« Значение 51 , - II -5- S: (raod2) вырабатывав. ся блоком У путем поразряд Ю о суг мирования ьо два значений S i S;, посту™

О

0

5

,

4rt

S5

J

пающих на первые и вторые входы блока 9 с выходов генератора 1 и преобразователя 8 соответственно. С выходов селекторов 3 и 4 значения S, и S соответственно поступают на входы дешифраторов 5 и 6, Дальнейшая процедура коррекции пакета ошибок длины два Б соответствии с третьим этапом декодирования аналогична случаю оди- но«ной ошибки,, Исправление ошибок в нечетном и четном разрядах кода а( производится одновременно. По е 0 дешифратором 5 и сумматорами 7.1; 7„3; 7,5,,,, с нечетными номерами исправляется ошибочный нечетный разряд л- , а по еи Ј 0 дешифратором 6 и сук- заторами 7.2; 7,1ч 7.6,.., с четными номерами - ошибочный четный разряд

П|

я;-|( кода а .

В случае отсутствия ошибок вырабатывается S 0„ При этом генератор 2 на своих выходах не вырабатывает сигналы одиночной, двойной и неисправимой ошибок„и Значение 8 0 через первые входы селекторов 3 и 4 поступает на входы соответствующих дешифраторов 5 и 6 и, посколысу в этом случае еи - ец 0, корректный код с входов 10,1 10„2,..., 10„(), 10.п /етройства без изменения через входы сумматоров 7.1, , „.„,7.(п-1),7.п выдается на выходы 14„1; 14.2,..., 14.( 14cii устройства,

3 случае 5 когда S 0 и не совпадает ни с одним из значений столбцов ь матрицах Н и G, на третьем выходе генератора 2 вырабатывается сигнал неисправимой ошибки, который поступает на выход I3 устройства и на управляющие входы дешифраторов 5 и 6. При GToi i блокируется работа дешифраторов 5 и 6 (генерируются коды ен ец О и ошибочный код с входов 10.1; Ю,2ЭОС о,10„(т)-1), ЮоП устройства без .изменения через входы сумматоров /olj, 7с.2э«,„„э 7„(), 7«п вьщаются на выходы 1. ц 14.2,..., 14. (п-1) , б.п устройстваg

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

10

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

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

,

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