Устройство для кодирования 64-разрядных информационных слов в составной корректирующий код с расстоянием шесть

 

1. УСТРОЙСТВО ДЛЯ КОДИРОВАНИЯ 64-РАЗРЯДНЫХ ИНФОРМАЦИОННЫХ СЛОЕВ В СОСТАВНОЙ КОРРЕКТИРУЮЩИЙ КОД С РАССТОЯНИЕМ ШЕСТЬ, содержащее формирователь кода Рида-Соломона, два входа которого соединены с первыми и вторыми входньми и выходными шинами соответственно, выход формирователя кода Рида-Соломона соединен с третьей выходной шиной, о тличающееся тем, что, с целью повьшения надежности и быстродействия устройства, в него введены смеситель информащюнных разрядов и первый и второй смесители проверочных разрядов, причем первая входная шина соединена с первым входом смесителя информационных разрядов и с первым входом первого смесителя проверочных разрядов, вторая входная шина соединена с вторым входом первого смесителя про-верочных разрядов и с первым входом второго смесителя проверочных разрядов , третья входная шина соединена с вторым входом смесителя информационных разрядов и с вторым входом второго смесителя проверочных разрядов, четвертая входная шина соединена с третьими входами смесителя информационных разрядов и первого и второго смесителей проверочных разрядов., а пятая входная шина соединена с четвертыми входами первого и второго смеЬителей проверочных разрядов, при этом четвер-, тая, пятая и шестая выходные пшны соединены с выходами смесителя информационных разрядов, первого смесителя проверочных разрядов и второго смесителя проверочных разрядов V соответственно. 2. Устройство по п. 1, от Л ичающееся тем, что второй смеситель проверочных разрядов содержит формирователь билинейных функций кода Нордстрома-РобинсонаПрепараты , смеситель линейных функций кода Нордстрома-РобинсонаПрепараты с информационными разря э дами кода Рида-Спломона и сумматор э по модулю два, причем первый и второй входы формирователя билинейных N3 функций кода Нордстрома-Робинсона:о Препараты и смесителя линейных о функций кода Нордстрома-РобинсонаПрепараты с информационными разрядами кода Рида-Соломона соединены с третьим и четвертым входами второго смесителя проверочных разрядов соответственно, а третий и четвер , тый входы смесителя линейных функций кода Нордстрома-Робинсона-Препараты с информационными разрядами кода Рида-Соломона подключены к первому и второму входам второго сме

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

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

РЕСПУБЛИК

09) (И) з(5g G 06 F 11/12

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

Н ABTOPCHOMV СВИДЕТЕЛЬСТБУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3532125/24-21 (22) 28.12.82 (46) 30.12.84. Бюл. № 48 (72) А.В. Анохин, И.М. Бояринов, А.А. Давыдов, Ю.Г. Дадаев, В.А. Мельников, Ю.И. Митропольский, В.П. Салакатов. Ю.F.. Улыбин и P.М. Воробьев (53) 62 1.282(088.8) (56),1. Патент США № 4030067, кл. С 06 F 11/12., 12.06.75.

2. Блок Э.Л., Зяблов В.В. Обобщенные каскадные коды. — "Вопросы кибернетики", вып. 29. М., 1977, с. 3 — 28 (прототип). (54) (57) 1. УСТРОЙСТВО ДЛЯ КОДИРОВАНИЯ 64-РАЗРЯДНЫХ ИНФОРМАЦИОННЫХ

СЛОЕВ В СОСТАВНОЙ КОРРЕКТИРУЮЩИЙ

КОД С РАССТОЯНИЕМ ШЕСТЬ, содержащее формирователь кода Рида-Соломона, два входа которого соединены с первыми и вторыми входными и выходными шинами соответственно, выход формирователя кода Рида-Соломона соединен с третьей выходной шиной, о тл и ч а ю щ е е с я .тем, что, с целью повышения надежности и быстродействия устройства, в него введены смеситель информационных разрядов и первый и второй смесители проверочных разрядов, причем первая входная шина соединена с первым входом смесителя информационных разрядов и с первым входом первого смесителя проверочных разрядов, вторая входная шина соединена с вторым входом первого смесителя проверочных разрядов и с первым входом второго смесителя проверочных разрядов, третья входная шина соединена с вторым входом смесителя информационных разрядов и с вторым входом второго смесителя проверочных разрядов, четвертая входная шина соединена с третьими входами смесителя информационных разрядов и первого и второго смесителей проверочных разрядов, а пятая входная шина соединена с четвертыми входами первого и второго смесителей проверочных разрядов, при этом четвер-, тая, пятая и шестая выходные шины соединены с выходами смесителя информационных разрядов, первого смесителя проверочных разрядов и второго смесителя проверочных разрядов соответственно.

2. Устройство по п. 1, о т;л ич а ю щ е е с я тем, что второй смеситель проверочных разрядов содержит формирователь билинейных функций кода Нордстрома-РобинсонаПрепараты, смееитель линейных функций кода Нордстрома-РобинсонаПрепараты с информационными разрядами кода Рида-Соломона и сумматор по модулю два, причем первый и второй входы формирователя билинейных функций кода Нордстрома-РобинсонаПрепараты и смесителя линейных функций кода Нордстрома-РобинсонаПрепараты с информационными разрядами кода Рида-Соломона соединены с третьим и четвертым входами второго смесителя проверочных разрядов соответственно, а третий и четвер. тый входы смесителя линейных функций кода Нордстрома-Робинсона-Препараты с информационньии разрядами кода Рида-Соломона подключены к первому и второму входам второго смесителя проверочных разрядов соответственно, при этом выходы формирователя билинейнь!х функций кода

Нордстрома-Робинсона-Препараты и смесителя линейных функций кода

Нордстрома-Робинсона-Препараты с

I 1,32292 информационными разрядами кода Рида-Соломона соединены соответственно с первым и вторым входами сумматора по модулю два, выход которого соединен с выходом второго смесителя проверочных разрядов.

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

64-разрядных двоичных слов в составной корректирующий код с расстоя нием шесть.

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

Наиболее близким к предлагаемому является устройство для кодирования информационньж слов в состав иой корректирующий код, содержащее формирователь кода Рида-Соломона, два входа которого соединены с первой и второи входными и выходными шинами соответственно„ выход ЗО формирователя кода Рида-Соломона соединен с третьей выходной шиной, формирователи внешних кодов и последовательно соединенный с ними формирователь внутреннего кода )2) .

Недостатками данного .устройства являются его низкое быстродействие и надежность.

Цель изобретения — повышение надежности и быстродействие устройст4О

Вае

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

Второй смеситель проверочных разрядов содержит формирователь билинейных функций кода Нордстрома-РебинсонаПрепараты, смеситель линейных функций кода Нордстрома-Робинсона-Препараты с информационными разрядами кода Рида-Соломона, а также сумматор по модулю два, причем первый и

3 1132292,4 второй входы формирователя бйлинейных функций кода Нордстрома-Робинсона-Препараты и смесителя линейных функций кода Нордстрома-Робинсона †Препара с информационными разрядами кода Рида-Соломона соединены с третьим и четвертым входами второго смесителя проверочных разрядов соответственно, третий и четвертый входы смесителя линейных функций кода Нордстрома-РобинсонаПрепараты с информационными разрядами кода Рида-Соломона подключены к первому и второму входам второго смесителя проверочных разрядов соответственно, при этом выходы формирователя билинейных функций кода Нордстрома-Робинсона-Препараты и смесителя линейных функций кода Нордстрома-Робинсона-Препараты с информационными разрядами кода Рида-Соломона соединены соответственно с первым и вторым входами сумматора по модулю два, выход которого соединен с выходом второго смесителя проверочных разI рядов.

На фиг. 1 приведена блок-схема устройства для кодирования, на фиг. 2 — блок-схема второго смесителя проверочных разрядов.

Устройство содержит формирователь 1 кода Рида-Соломона, смеситель 2 информационных разрядов, первый смеситель 3 проверочных разрядов, второй смеситель 4 проверочных разрядов, первую-пятую входные шины (входы) 5-9 соответственно, а также первую-шестую выходные шины (выходы) 10-15 соответственно, а второй смеситель 4 проверочных разрядов состоит из формирователя 16 билинейных функций кода Нордстрома-Робинсона-Препараты, смесителя 17 линейных функций кода Нордстрома-Робинсона-Препараты с информационными разрядами кода Рида-Соломона и сумматора 18 по модулю два. Входные шины 5 — 9 соединены с соответствующими входами формирователя 1 кода Рида-Соломона и смесителей 2. 3 и 4, причем выходы формирователя 1 и смесителей

2. 3 и 4 подключены к выходным шинам 12-15 соответственно, при этом входы второго смесителя 4 проверочных разрядов соединены с входами формирователя 16 и смесителя

»5

Та бли ца 1 (0 1 2 3 ° . . . ° . 15J

17, выходы которых подключены к входам сумматора 18 по модулю два, выход которого соединен с выходом второго смесителя 4.

Формирователь t кода Рида-Соломона, смеситель 2 информационных разрядов, первый смеситель 3 проверочных разрядов, формирователь

16 билинейных функций кода Нордстрома-Робинсона-Препараты и смеситель

17 линейных функций кода НордстромаРобинсона-Препараты с информационными разрядами кода Рида-Соломона выполнены на сумматорах по модулю два. Формирователь 16 билинейных функций кода Нордстрома-РобинсонаПрепараты выполнены на логических схемах И-ИЛИ-НЕ.

Кроме того, введены следующие обозначения: Код Рида-Соломона— код РС, код Нордстрома-РобинсонаПрепараты — код НРП, a», а64 информационное 64-разрядное слово, а, ..., а5 — информационные разряды кода РС, с, ..., св — проверочные разряды кода PC Ь», Ьк — информационные разряды кода

НРП, Ьр — общая проверка на четность кода НРП, Ь,, ..., Ь»5 — проверочные разряды кода НРП, fq, и — смешанные разряды СР(2 )

Й) поле Галуа, содержащее 2 элементов, каждый имеет m разрядов, (и, k)-код — код, каждбе слово которого содержит,п разрядов, Е из которых являются информационными, Н с — усеченная проверочная матрица кода РС, Н» — матрица четности для формирования разрядов f и f, U — ЛОГИЧЕСКОЕ ИЛИ, 9 — сложение по модулю два. .Алгоритм работы устройства состоит в следующем.

64-разрядное информационное слово а», .. °, а 4 (табл. 1) разделяется на две части а», ..., а54 и, а5f, ..., а6,» по 56 и 8 разрядов.

Первая часть а», .. °, а кодируется (16, 14)-кодом PC над полем

GF(2 ) .

f132292 а

Продолжение табл.l

О 1 2 3

При этом информационные разряды раз биваются н а наборы по четыре, например а а ay а4 ° ° ° a а 4 aug у а 5g .каждыи из которых рассматривается как элемент поля

СР (2). В результате кодирования кодом PC путем умножения информационного слова а, ..., а на транспонированную матрицу Н, (табл. 2) формируются проверочные разряды с, с, и с с, Слово кода PC образует матрицу, состоящую из 16 столбцов — элементов поля

GF (2 ) и 4 строк.

Информационные разряды а а кодируются в слово Ь„, Ь, 64

Ъ кода HPII, при этом Ь = а,, Ю ..., b8 -а . Однако проверочные разряды bp, b>, b@, ..., Ъ| в явном виде не формируются. В принятом алгоритме кодирования сразу формируются смешанные разряды f1, = О, ..., 15, которые представляют собой сумму по модулю два раз ряда Ь кода НРП и четырех раэря1 дов кода PC расположенных в i столбце матрицы слова кода РС, ЗО

В результате кодовое слово составного (80, 64)-кода с расстоянием шесть образует матрицу из

16 столбцов и 5 строк, в которой первые 4 строки представляют слово кода РС, а пятая строка — это смешанные разряды кодов PC и НРП f (i = О, ...,.15).

Формирование разрядов с, ... с и

f>g осуществляется следующим образом.

Разряды aij ... ) а28 подаются ЬО на первую входную шину 5, с которой. поступают на первый вход формирователя 1 кода PC на первый вход с смесителя 2 информационных разря-. дов и на первый вход первого смесителя 3 проверочных разрядов.

Разряды а,, ...; а @ поступают на вторую входную шину 6, с которой

Е4 = h; Q a (3) 4 -И11 H 4 (<-2)42

4(j "2)t3 а4(1-1)<4

i 2, ..., 8 (4) ! поступают на второй вход формирователя 1 кода PC на второй вход первого смесителя 3 проверочных разрядов и на первый вход второго смесителя 4 проверочных разрядов. Разряд а64 с третьей входной шины 7 поступает на второй вход смесителя

2 информационных разрядов и на второй вход второго смесителя 4 проверочных Разрядов ° Разряды а<8 ..., a63 с четвертой входной шины

8 поступают на третий вход смесителя 2 информационных разрядов, на третий вход первого смесителя 3 проверочных разрядов и на третий вход второго смесителя 4 проверочных разрядов. Разряд а с пятой входной шины 9 поступает на четвертый вход первого смесителя 3 проверочных разрядов и на четвертый вход второго смесителя 4 проверочных раз-, рядов .

В .формирователе 1 кода PC получаются проверочные разряды с, с путем умножения информационного вектора (а, ..., a><) на транспорт нированную усеченную проверочную матрицу кода РС (Н (табл. 1) . (с<, ..., С ) = (а4, ..., а ©)» х Н ",. ° (1)

Умножение вектора на матрицу реализуется с помощью сумматоров по модулю два. Например, разряд с полу-, .чается следующим образом: С4 = а1 О+ а20+ аб 04 а9 (Ран + a,,(Q+

9 а„ О. а Q а,, +7а ©+a2 (3

®аМ ® a2q ® а 2(Ва14 ® а 6Ж

О+aÄ e+ aÄ a+a„„О+а4, Ва„О+ +) а4 Q+ a47 О+ а4Ц ® 50 ® a 4 О+

О+ а 52 С+) а,З О+ а 4 Я 5 О+ a 6 (2) т.е. при формировании разряда с находится сумма по модулю два тех ининформационных разрядов, номера которых соответствуют номерам единичньи элементов i-й строки матрицы

Н . Сформированные таким образом проверочные разряды с;, i = 1, 8 кода PC поступают на третью выходную шину 12.

В смесителе 2 информационных разрядов формируются смешанные разряды й;, i = 2, ..., 8 в соответствии с выражениями

1132292 (9) (f1= A В ЧА„ С;ЧВ С;

20 ((. + гг °

7 ! ) где h, — суммы разрядов i-го Столбца матрицу кодового слова PC.

Разряды й;, i = 2, ..., 8 поступают на четвертую выходную шину. 13.

Разряды f и f» формируются в пер- 5 первом смесителе 3 проверочных разрядов путем умножения вектора (а а 6, b», ..., Ь ) на транспонированную матрицу Н4 (табл. 3) .

10 (fc, f» ) (» ..., „, Ь ..., Ь,) Н, (5)

Нижняя строка матрицы Н4 соответствует сумме с (+) сб 8) с О

О+ с (+) b» = Е», а верхняя — сумме с» (+> с С+) с> О+ e4 Q+ Ъо = Е,з, где

Ь = b» Я ... 9 ЬЬ7. Использование матрицы Н4 позволяет формировать разряды Й», и f » одй овр еменн о с формированием разрядов с:, i = 1, 8.

Разряды fÎ и f» поступают на пятую выходную шину 14.

Разряды f(7, ° ° °, f »9 формируют ся во втором смесителе 4 провероч ных разрядов в соответствии с выра- 25 жениями

f; =. h Qb„, i = 9, ..., 15 (6)

Проверочные разряды Ь; кода НРП (i = 9,;, 15) следующим образом 30 выражаются через информационные разряды Ь, ..., ЬВ кода НРП:

Ь, = ; Q+) q,« (7) где »1>; — линейные функции кода НРП, Щ; — билинейные функции кода

НРП.

Выражения для О> имеют вид (ь, ® ь,) (Ь, О+ Ь,) О+ (b4 О+

О+ Ь )(b20+ Ь4) О+ (Ъ ® ЪУ)(b2++3 40

Q+) Ь,), СУ»0 = (Ь О+Ь»)(Ъ7Й) Ь ) (+) (Ь» О+ (3 Ь)(Ь +Ьь)+ (Ь +Ь)(Ь +

О b,).

» »1 - (Ь, + Ь,)(Ь, + Ь,) + (Ь, Я

0+ Ь )(Ь СРЬ )P+ (bÄ Sb,)(Ь С+7

Я b ), су„- (b6 & b )(ь G) b ) Q+ (bb o+

P+ b! ) (Ьг<+> Ьг) <Ь! (Ь5Ю Ь, ) (Ь b> Ьг ), гг!г (ьг!гьг)(ьг Ю ьг) & <ьг И sa

О+ ь ) (ь э ьг) а> (ь! э ьг)(ь o+ ьг), <г<, b5 ьъ)(ь юьг) +

O+ <ь,йь,><ь а ь„ > Ю <ь, (г>ь,>

<ь Оь >. гг !г- (ь (b> b, ) (b, Û b, ) O+ (ь, (ь>

O+ ьг) (ь г Й ьг ) 6I (ь <г) ь>(ь г Q

Величины (», формируются в формирователе 16 билинейных функций кода НРП следующим образом.

Сначала формируются суммы в кругг лых скобках из выражений (8), которые обозначим как А,, В .и С, .

1 ,3атем формируются величины < ; путем реализации логических функций

В выражении (9) учтено, что

АВ О+ AC (+) ВС = ABVACVBC

Линейные функции <»>; кода НРП имеют вид

1 (l>q ba У Ь» О Ь1 G+ Ь Я Ь3

<1>1<> Ь ЯЬ Яb» (+) Ь5 Q+ Ь4

V«= ЬВ ®Ъ ®Ь4 +Ь CBbq. >1г = Ь O+ b4 Я Ь (.> Ь1 ®Ь, <1>1»- Ь О+ Ь О+ b7 Q) Ь CP b4, М<4= Ьв О+Ъ (+7 Ь > + Ь4 О+ Ь1 э

<>>»»= Ь 0+ b> Q+3 Ь6 Q+ b1 Я Ь>,(10) Линейные функции (»>, не формиру-. ются в явном виде. В смесителе 17 линейных функций кода HPA с информационными разрядами кода РС форми- руются величины

Е ь; O Ч; с помощью многовходовых сумматоров по модулю два.

В итоге разряды f i = 9, 15, формируются в сумматоре 18 по модулю два с помощью двухвходовых сумматоров путем формирования суммы

В итоге смешаннь»е разряды f»1 у

i = 9, ..., 15 поступают на выходную шину 15.

Таким образом, на выходных шинах

10-15 формируется кодовое слово составного (80,64) — кода с расстоянием шесть, который позволяет исправлять две независимые ошибки, обнаруживать три независимые ошибки, а также исправлять одиночные фазированные пакеты ошибок длины 5 и обнаруживать тройные фазированные пакеты длины 5 с нечетным числом ошибок в каждом пакете, что повышает надежность работы устройства., 1132292

Та блица 2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

1.1 О О О. 1 О О 1 О 1 О О О 1 О 1 1 1 О О 1

О 1 I О О О 1 О. 1 1 О 1

1 О 1 1 1 0 О 1 1 1 1 О

О О 1 1 О О О О 1 О 1 0 1 О О 1 1 О 1 1 1

О 1 О О 1 I О О О О 1 О 1 О 1 О О 1 1 0 1

О О 1 О О 1. 1 О 1 О О 1 1 1 О 1 1 О 1 1 1 1

1 0 О 1 1 О 1 1 1 1 О О 1 1 1 О 0 1 О 1 О 1

0.1 О 1 1 1 О О 1 1

35 36 37 38 39 40 41 42 43 44

1 О О 1 О

О О О

23 24 25 26 27 28 29 30 31

1 О О О О 1 1 О О 1 О 1 О 1 1 1 О 1 О О 1 1

О О О 1

1 1 1 О О О 1 1 О 0 1 О 1 О 1 1 1 О

О 1 О 1 О 0 0.1 1 0 1 1 О 1 1 1 1 1

1 О О О

1 1 1 О 1 8 О 1 1 1

О 1 О 1 0 1 1 О 1 1

1 1 I 1 О О 1 О О О I 1 1 О 1 О 1 О О 1 О 1

1 1 О 1 1 О О 1 О I 1 1 1 1 1 i О 1 1 О 1 О

О 1 О О 1 О О О 1 1 .1 О 1 О 1 О 1 1 О 1 1 О

45 46 47 48 49 5g 51 52 53 54 55 56

1 О 1 1 О 1 1 1 1 1 1 1

О 1 О 1 О О I 1 О I 1 1

I О 1 О О О 0 1 О О 1 1

О 1 1 О 1 1 1 1 1 1 1 О

О О 1 1 1 1 1 1 О 1 1 1

О О 0 1 О 1 1 1 О О 1 1

I О О О О 0 I 1 0 О 0 1

О 1 1 1 1 1 1 О 1 1 1 1

О О О О 1 1 0 О 1

О 1 О 0.1 О О О

1 О О

32 33 34

О 1 О !

1 1 1

1 О

1 1

О 1 1 1 1 1 1 0

О 0 О 1 1 1 0 1

)2

1132292

Таблица 3

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Л

1 О 0 О О 1 1 1 1 1 0 0 О 0 1 1 1 О 1 1 0

0 1 1 1 1 О 0 О 0 0 1 1 1 1 О О 0 1 О 0 1

22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 4!;42

1 О О 1 1 1 О О О О 1 1 0 О 1 О 1 1 О 1 1

О 1 1 0 О" О 1 1 1 1 О .О 1 1 О 1 0 0 1 0 О . 43 44 45 46 47 48 49 50 51 52 53 50 55 56 57 58 59 6061 62 63

О 1 0 0 1 О 1 0 1 0 О 1 0 I 1 1 1 1 1 1

1 О 1 1 О 1 О 1 О 1 1 О 1 0 0 0 О О 0 О О

Puz.7

1132292

Ап. 2

Редактор Л. Апексеенко

Заказ 9793/41 Тираж 698

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

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

Подписное

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4 б

Составитель Б. Мельников

Техред О.Ващишина Корректор А. Ильин