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

 

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

СОЮЗ COBETCHHX

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

РЕСПУБЛИН

2 А1 (S))S Н 03 М 13/02

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

H АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

Г10 ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГННТ СССР

1 (21) 4419948/24-24 (22) 03.05.88 (46) 15.07.90. Бюл. 9 26 (72) А.В. Маркарян (53) 681.325.63(088.8) (56) Хетагуров Я.А. и др. Повышение надежности цифровмх устройств методами избыточного кодирования. М.:

Энергия, 1974, с. 51-56.

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

У 720757, кл. Н 03 М 13/02, 1980.

Патент США h" 3755779, кл. G 06 F 11/12. (54) УСТРОЙСТВО ЛЛЯ ИСПРАВЛЕНИЯ ПАКЕТА ОШИБОК ДЛИНЫ ДВА.

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

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

1 иле

157881 2 а„, а»,) длины и, где а — двоичньп» (п1 символ кода а(.при j = (1-nI, совпаает с одним из значений столбцов матрицы Н, а синдром ошибки в соседних разрядах кода а(— с одним из эначе(н нйй столбцов матрицы С.

В этом случае, например, код Хэминга (32, 26) преобразуется в код (24, 18), исправляющий пакеты ошибок и H = (О(4, (г (; a <, где а1 az За4 абаба7а8 a a a a„

9 1Он

001 0

001 1

1111

01 00

001 1

1 1 1 1

01 0.0

001 1

0011

001 1

001 0

001 1

1111

0100 ааайа ча»

И 8 I9 20

azIazzа23 я

001 1

001 1

1 t 11

01 00

0 1 1 О

001 1

1 1 1 1

01.00

01 1 0

001 1

0010

001 1

001 0

001 1

1 1 1 1

1 = 6; (= Г4 1 1,с = (0 5) (1 =0 — 0+4=4, i 9=2= (4+4) шос(6, i< = 2-1 =

=1, 1 =1+4=5, (.6=3= (5-4)mod6); каждому столбцу этих подматриц и(" соответствует один из символов а и = 24-разрядного кода а = (а, a ...à ... à ащ) (г9)

Ц Я при j = 1 — 24). Для упроцейия схемы кодирования, также как и в случае кода Хэмминга, целесообразно в качестве контрольных символов выбрать значения

9 а»3 а»7 и аг соответству ющие первым столбцам этих подматриц (у (К г Р Р ; P3((бра зуется из следующих подматриц P с:

d» d< d> d < d d dzd»» . с(9 с(ю и а4

01 00

0001

1.1 00

01 01

01 01

0 1 1 1

01 01

0001

1100

0001

1 1 0 0

01 01

0111

01 01

d<>d»»»di9dzo с(гас(гз

И;4 15»6

0 1 1

0 1 0

1 1 0

101

1 1 0 0

101 0

01 01

0111

01 01

0001

01 01

0001

1 1 0 0

1 0 1 0

01 01

0111

Каждый )-й столбец в подматрицах

8 "обозначен символом с(; с(= Б, +

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

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

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

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

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

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

r = и-m контрольных символов исходного кода Хэмминга (2, 2 -r), где

Р-1 и = 2 ;,матрица Н представлена в ви» -Г де H = О(," ...; g " .I> (, rpe O(. — 35 б, подматрица размером гх и/к;

=j1 r); 1» = 0 1 =1»,,+ (mod,r)

Ф. (ф coast подматрицы о(, < были бы сос» тавлены путем (1 -i» )mоd r цикл»»чeс--, 40 . ких перестановок строк подматрицы п, а значение столбцов в подматрице Ы

< и значение были бы выбраны так, чтобы матрица С,столбцы которой Аорми руются в результате суммирования всех 4с соседних столбцов матрицы Н, содержа ла бы различимые коды, столбцов,четного веса с аналогичной структурой

С =))P ., P . P "It гдеP " подматрица, являющаяся результатом последовательного суммирования значе и ний соседних столбцов подматрицы К,", i Ê9 1 включая первый столбец подматрицы»с ".

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

5 15788 .+ S>q (шос12); S1 — синдром одиночной ошибки, соответствующий j-му столбцу матрицы Н. Например, если в коде a(" ошибка произошла по разрядам а и а6, то ) = 5, S = llu00010!!, S6= II10001Й, а с1 = Sg + S (шос12) = ll00001jl где

Т вЂ” знак транспонирования матрицы.

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

Первым этапом декодирования вычисляется значение r-разрядного синдрома 1т

S по известному выражению: S = ai"1 х Н.

Если в коде а1" отсутствуют ошибки, то

S = О (нулевой синдром). В случае одиночной ошибки по. разряду а получается S ф 0 (ненулевой синдром) нечетного веса, совпадающий с j ûì столбцом матрицы Н. При возникновении пакета опп бок длины два по разрядам 20 а и а +1 — S = dj четного веса. Если

+1 значение S ф О.и не совпадает ни с одним из значений столбцов матриц Н и

С, значит имеет место неисправная ошибка (произвольная четная или нечет- 25 ная ошибка).

Вторым этапом декодирования производится дешифрация S результатом ко торой являются коды е = (е<е>... е е4 составленние из симнолов е = (О; 1 соответственно с нечетными j и четными j+1 индексами.

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

Н и G, выполняется условие: е > = е и =

= О. При S ф О нечетного веса только одно значение е в кодах е и и еИ может равняться единице. Если ошибка происходит по нечетному разряду а кода а, то е.ц. = О, ен P О c e> = 1; М а в случае ошибки по четному разряду а,— еи = О, еп О с е1,<= 1. Например, если ошибка происходит по разряду а кода а, то е ц = (000000000000), e>=(001000000000) с е =1; при ошибке по разряду а6 - еи = (000000000000), e;> = (001000000000) с е 6 = 1.

В случае S P 0 четного веса с учетом с1 = S> + S><>(но<12) сначала про изводится преобразование S = d в S> с нечетным индексом, j и вычисление

S14< с четным. индексом j41 на.основе;

S = S ) + d>(mod?), а затем аналогично случаю S ф О нечетного веса

S5 генерируются значение еи Р О и еи Р О

no S> и Б 4, соответственно. Указанное преобразование S = d2 в S производит1

- ся путем выбора S) по значению d из

12 б таблицы преобразования, где каждому

1 значению d матрицы G поставлено в соответствйе значение S с нечетным

1 индексом j.

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

Если в коде а происходит ошибка но разрядам а5 и а6, то для 1 = 5, d = ji100001II согласно приведенной таблице должно быть выбрано значение

Б = II 000010II вычислено S6 — — d< +

Т.

+ Б (mod2) = II100011IIT. После дешифрации H6

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

a<" + еи + ец(mod2). Например, если е — (l0001000000000010000) то после вычисления значения синдрома по S

141 Т а «Н и дешифрации S получаем

eu«се,=1ие ФОсе6=1, а в коде а 41 проинвертированы разряды 5 и б, обозначенные знаком + . Откоррек/241 тированньп код а имеет следующий вид: а = (100001000000000100010000), которьп1 удовлетворяет соотношению °

S = а 21 Н = О.

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

С входов 10.1, 10,2,...,10.(п 1)

10.п и-разрядньп код а " = (а а а,, a ) в параллельной форме поступает на входы соответствуюцих сумматоров

7.1, 7.?,....7.(п — 1), 7.п и на входы генератрра 1. Б соответствии с первым этапом декодирования генератор 1 по матрице Н на своих выходах вырабатывает r-разрядный синдром $, который поступает на входы генератора 2 и преобразователя 8, на первые входы селекторов 3 и 4 и блока 9.

В случае возникновения в коде а1 одиночной ошибки вырабатывается S 0 нечетного веса, по которому генератор

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

В селекторах 3 и 4 открываются каналы, пропускаюпие на виход информацию с первых входов, а значение S c выходов

1578812

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

I (!. j 8 . ) d j Б.

1 1 1

О 1 О

1 1 1

001

1 0 1

1 1 0

1 1 0

101

0.1 0

001

1 1 0000

31011

310111

5 00001

5 00001

7 1 1 1 1 1

7 1 1 1 1 1

9 001 00

9 001 00

1111101

1111101

13 01000

0 13

1 14

1 15

0 1б

0 17

0 !8

0 19

0 20

0 21

1 22

1 23

10101

000 t 01

110011

1 10000

001 1 1 1

0000 1 1 l 11010

01 0001

1 0 1 1

2 0 1 О

3 001

5 100

6 0 1 1

7 101

8 О 1 1

9 000

10 1 1 0

12.0 О 1

13 01

15 1 1

15. 1 1

17 00

17 00

19 01

19 01

21 00

21 00

23 1 1

23 1 1

0 1 1 1

0 1 1 1

ОО01

0001

1111

1 1 1

1101

1 1 0

Составитель С. Левнчев

Te>PeÀ М.Моргентал Корректор Л. Патай

Редактор С. Лисина

Тираж 660 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Заказ 1922

Производственно-издательский комбинат "Патент", r.Óæãoðîä, ул. Гагарина, 101 устройство для исправления пакета ошибок длины два, содержащее первый и второй дешифраторы, генератор синдрома, в входов, которого (где и — раз-, рядность входного кода) объединены с первыми входами первого блока суммматоров по модулю два и являются инфор- l0 мационными входами устройства, гене ратор сигналов ошибок, первый, второй, и третий выходы которого являются со- . ответствующими выходами сигналов ошибок устройства, выходы сумматоров по модулю два являются информационными выходами устройства, о т л и ч а ю— щ е е с я тем, что, с целью првышения достоверности исправляемой информации, в пего введены преобразователь > кода, второй блок сумматоров по модулю два, первый и второй селекторы, первые входы которых объединены с одноименными входами преобразователя кодов, первыми входами второго блока сумматоров по модулю два, входами ге- нератора сигналов ошибок и подключены к выходам генератора синдрома,вторые входы второго блока сумматоров по модулю два и первого селектора объединены и подключены к соответствующим выходам преобразователя кодов, третьи входы первого н второго селекторов объединены и соединены с вторым. выходом сигнала ошибок устройства, выходы первого и второго селекторов соединены соответСтвенно с первыми входами первого и второго дешифраторов, вторые входы которых объединены и подключены к третьему выходу сигнала ошибок устройства, выходы первого и второго дешифраторов подключены соответственно к вторым входам четных и нечетных сумматоров по модулю два первого блока, вторые входы второго сепектора соединены с выходами второго сумматора по модулю два.