Устройство для кодирования 64-разрядных информационных слов в составной корректирующий код с расстоянием шесть Советский патент 1984 года по МПК H03M13/51 

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

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

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

Изобретение .относится к вычислительной технике и технике связи и может быть использовано в .устройствах обработки, хранения и передачи информации для кодирования 64-разрядных двоичных слов в составной корректирутопщй код с расстоя нием шесть. Известно устройство для кодирования 64-разрядных информационных слов в (79,64)-под Боуза-ЧоудхуриХоквинчема (БЧХ), содержащее последовательно соединенные блок умно-жения информационного слова на проверочную матрицу кода БЧХ и блок формирования общей четности информационного слова lj . Недостатком данного устройства является то, что БЧХ не исправляет пакетные ошибки, что снижает надеж яость вычислительных устройств, использующий данное устройство. Наиболее близким к предлагаемому является устройство для кодирования информационных слов в состав кой корректируюгций код, содержащее формирователь кода Рида-Соломона, два входа которого соединены с первой и второй входньми и выходными шинами соответственно, выход формирователя кода Рида-Соломона соединен с третьей выходной шиной, формирователи внешних кодов и последовательно соединенный с ними фор мирователь внутреннего кода 2J , Недостатками данного .устройства являются ИГО низкое быстродействие и надежность. Цель изобретения - повьшение надежности и быстродействие устройства. Цель Достигается тем, что в устройство для кодирования 64-разрядных информационных слов в составной корректирующий код с расстояйием шесть, содержащее формирователь кода Рида-Соломона, два входа которого соединены с первыми и вторыми входными и выходными шинами соответственно, вьгход:. формирователя кода Рида-СЬйомона- соединен с третьей выходной шиной, введены смеситель информационных разрядов ипервый и второй смесители проверочных разрядов, причем первая входная шина соединена с первым входом смесителя информационных разрядов и с первым входом первого смесителя проверочных разрядов, вторая входная шина соединена с вторым входом первого смесителя проверочных разрядов и с первым входом второго смесителя проверочных разрядов, третья входная соединена с вторым входом смесителя информационных разрядов и с вторым входом второго смесителя проверочных разрядов, четвертая входная шина соединена с третьими входами смесителя информационных разрядов и первого и второго смесителей проверочных разрядов, а пятая входная вшна соединена с четвертыми входами первого и второго смесителей проверочных разрядов, при этом четвертая. пятая и шестая выходные шины соединены с выходами смесителя информационных разрядов, первого смесителя проверочных разрядов и второго смесителя проверочных разрядов соответственно. Второй смеситель проверочньгх разрядов содержит формирователь билинейных функций кода Нордстрома-РебинсонаПрепараты, смеситель линейных функций кода Нордстрома-Робинсона-Преиараты с информационными разрядами кода Рида-Соломона, а также сумматор по модулю два, причем первый и

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

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

Г

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

17, выходы которых подключены к входам сумматора 18 по модулю два, выход KOToiJoro соединен с выходом второго смесителя 4. 5 Формирователь 1 кода Рида-Соломона , смеситель 2 информационных разрядов, первый смеситель 3 проверочных разрядов, формирователь

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

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

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

Кроме того, введены следующие

20 обозначения: Код Рида-Соломона. код PC, код Нордстрома-РобинсонаПрепараты - код НРП, а. , ... а. информационное 64-разрядное слово, а , ..., - информационные раз25 ряды кода PC, с, ..., cg - проверочные разряды кода PC, bjj , ..., bg - информационные разряды кода НРП, Ьр - общая проверка на четность кода НРП, b,j, . . ., bj5 - про30 верочные разряды кода НРП, fо, ..., f|5 смешанные разряды, GF() поле Галуа, содержащее 2 элементов , каждый имеет m разрядов, (п, и)-код - код, каждбе слово ко35 торого содержит п разрядов, k из которых являются информационными, Нар - усеченная проверочная матрица кода PC, H - матрица четности для формирования разрядов fg и f,, ,

40 V - ЛОГИЧЕСКОЕ ИЛИ, Ф - сложение по модулю два.

Алгоритм работы устройства состоит в следующем.

64-разрядное информационное сло45 во а , ..., а (табл. 1) разделяется на две части а , ..., и , 5f 64 по 56 и 8 разрядов. Первая часть а , ..., а jg кодируется (16, 14)-кодом PC над полем

50 СР(2Ъ.

Таблица 1 Продолжение табл ...... 15 При этом информационные разряды разбиваются на наборы по четыре, например a. , д а., а , ... , а дадд , ajj , 355 , .каждьй из которых рассматривается как элемент поля GF (2). В результате кодирования кодом PC путем умножения информаци онного слова aj , j.a на транс понированную матрицу (табл. 2 формируются проверочные разряды кода PC образует матрицу, состоящую .из 16 столбцов - элементов пол GF (2) и 4 строк. Информационные разряды а , .. кодируются в слово Ьд, Ь , ., кода НРП, при этом Ь , bg . Однако проверочные разряды bo, Oj , , ..., ном виде не формируются. В принятом алгоритме кодирования сразу формируются смешанные разряды f , i О, ... 15, которые представляют собой сумму по модулю два ра ряда Ъ. кода НРП и четырех разрядов кода PC, расположенных в i-м столбце матрицы слова кода PC. iB результате кодовое слово сос тавного (80, 64)-кода с расстоянием шесть образует матрицу из 16 столбцов и 5 строк, в которой первые 4 строки представляют слов кода PC, а пятая строка - это сме шанные разряды кодов PC и НРП f; (i О, Формирование разрядов с , , fff осуществляется О 1 следующим образом. Разряды а,, ... подаются на первую входную шину 5, с котор поступают на первый вход формирователя 1 кода PC, на первый вход смесителя 2 информационных разрядов и на первый вход первого смес теля 3 проверочных разрядов. Разряды а ; agg поступаю на вторую входную шину 6, с котор поступают на второй вход формирователя 1 кода PC, на второй вход первого смесителя 3 проверочных разрядов и на первый вход второго смесителя 4 проверочных разрядов. Разряд с третьей входной шины 7 поступает на второй вход смесителя 2 информационных разрядов и на второй вход второго смесителя 4 проверочных разрядов. Разряды , ..., с четвертой входной шины 8 поступают на третий вход смесителя 2 информационных разрядов, на третий вход первого смесителя 3 проверочных разрядов и на третий вход второго смесителя 4 проверочных разрядов. Разряд с пятой входной пины 9 поступает на четвертый вход первого смесителя 3 проверочных разрядов и на четвертый вход второго смесителя 4 проверочных раз-, рядов. В формирователе 1 кода PC получаются проверочные разряды , . .., с„ путем умножения информационного вектора (а,, $(, на транспо- нированную усеченную проверочную PC (Н-с (табл. 1). матрицу кода CgO (а,. (с, ..., Умножение вектора на матрицу реализуется с помощью сумматоров по модулю два. Например, разряд с полу- , чается следующим образом: 5 а|) © ®зг « Ф а„ О) а М,, ©а,. ® а,д Ф ajo ф aj а53 ©a55(, (2) т.е. при формировании разряда с; находится сумма по модулю два тех ининформационных разрядов, номера которых соответствуют номерам единичных элементов i-й строки матрицы Н. Сформированные таким образом проверочные разряды с- , i 1, ..., 8 кода PC поступают на третью вьпсодную шину 12. В смесителе 2 информационных разрядов формируются смешанные разряды f, i 2, ..., 8 в соответствии с вь1ражениями О а4(2)+7 , (i2br ® 1 2; где h. - суммы разрядов i-ro Столбца матришг кодового слова PC. Разряды f i 2, 8 поступают на четвертую выходную шину-13. Разряды f- и f формируются в пе первом смесителе 3 проверочных разрядов путем умножения вектора (а,, ..., 5, Ь, ..., by) на транспонированную матрицу Hj (табл. 3). (fo, f, ) (а,, ЧА t (5) , , by) Н Нижняя строка матрицы Н соответствует сумме Ct ® Cg (§9 Су Ср bj f , а верхняя - сумме С2 е с 0:}с4 Эд tg, где о 1 ® . © Ь . Использование матрицы H позволяет формировать разряды fjj и f( одйовременно с формированием разрядов Cj , i 1, ... 8. Разряды fg и fj поступают на пятую выходную пмну 14. Разряды fj формируют 9 (S , ся во втором смесителе 4 проверочных разрядов в соответствии с выра жениями f i h; 0b- , i 9, ..., 15 (6 Проверочные разряды Ъ кода НРП (i 9, ... 15) следующим образом вьфажаются через информационные разряды bj , , .., bg кода НРП: где (f - линейные функции кода НРП Cj - билинейные функции кода НРП. Выражения для СР, имеют вид 9 (ь,,®ь )©а,@ tiXbj© b,)©(bg J7)(b2© © bV, Q, (Ь(5)Ц)(Ь7 by) ® (b b,)(b. + bfi) (bj. + by)(b (f, (bj + b4)(b, + bj) + (by (Э b4 ) (b @ b ) О (b у © b,j) (b Ф Cf,, (b()(b t)(b5©bj(b,@b,), (Ь)() @ (bg © Ь7)(Ь.ФЬ)® (b, ®b4)(b.© b Cf,A (be + Ь-)(Ь,ФЬ. ) (,)(( (,). Cp,y (b, ®Ьб)(Ь4(5Ь,) 0 (b,(± Ь)(Ь5фЬ2) ® (b ©b)(b5 2.8 Величины q, формируются в формирователе 16 билинейных функций кода НРП следующим образом. Сначала формируются суммы в Kpyi льгх скобках из выражений (8) , которые обозначим как Aj, В .и . атем формируются величины путем реализации логических функцийVA-C;VB;C. Cf. A;. В выражении (9) учтено, что АВ © АС 0 ВС ABVACVBC. Линейные функции TjJ- кода НРП имеют вид Vg bg (5 b, (9 b © b ©b,, V{0 bg ©bj C±)b, ©bj ® b , V« bg (i ц c9 b 6 b © b, Vi2 bg ® b4 (Э b,2 (2) b, (J) b , Vi) bg (S)b. ©b фЬбФЬ, ((/,4 b« - -ciyug ( W b, , ©by ® Ьб b2,(10) Линейные функции ф не формируются в явном виде. В смесителе 17 линейных функций кода НРА с информационными разрядами кода PC формируются величины h;0 V; с помощью многовходовых сумматоров по модулю два. В итоге разряды f; , i 9, .. . 15, формируются в сумматоре 18 по модулю два с помощью двухвходовых сумматоров путем формирования сумВ итоге смешанные разряды f- , i 9, ..., 15 поступают на выходную шину 15. Таким образом, на выходных шинах 10-15 формируется кодовое слово составного (80,64)-кода с расстоянием шесть, который позволяет исправлять две независимые ошибки, обнаруживать три независимые ошибки, а также исправлять одиночные фазированные пакеты ошибок длины 5 и обнаруяявать тройные фазированные пакеты длины 5 с нечетным числом ошибок в каждом пакете, что повышает надежность работы устройства. 9,: 1132292 , 1 2- 345 6- 7 8 910 11 12 13 14 1 11000. 100101000 01100010.1 10110 10111001111011 10 о 1100001 01 01 01 001 1000 о 1 о 1 о 001001.101 0011-1 100110111 10011 100010010 10001 23. 24 25 26 27 28 29.30 31 32 33 34 35 36 3 10000110010101 11100011001010 0101 0001 1 01 1 о 1 00001100101011 10100100011101 11110010001110 11011001011111 01001000111010 45 46 47 48 49 5Q 51 52 53 1011.01111 010100110 101000010 011011111 001111110 000101110 100000110 011111101 « .10 Таблица 5 16 17 18 19 20 21 22 10111 00 1 01111 110 . 00011 10 1 001 10111 1 00 1 10. 11 01101111 10010101 01110 01 17 38 39 40 41 42 43 44 11010011 11100001 1 1 1 1 1 00 о 10100111 01011011 10100101 11011010 101 101 10 54 55 56 111 111 011 110 111 011 001 111 12345 678910 11 1 0 ООО 11111 О 01 111 ООООО 1 22 23 242526 2728293031 32 1 О О 11 1 О О00 1 0Г 1О 00 1 111-0 43 44 454647 4849505152 53 0100 1 О 10100 1О 11 010 1011 1213 14 15 16 17 18 19 20 fl fiО О 1 1 1 О 1 1 О 11 1 О О 01001 3334 35 Зб 37 38 39 40 41:42 1 О О 1011011 01 10100100 5455 56 57 58 59 60 61 62 63 1 011111111 0 100000000