Устройство для коррекции двумерного итеративного кода

О П И С А Н И Е 332462ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬОВУ Союз Советоаиз Социалистическив РеспубливЗаявлено 11.И.1969с присоединением заПриоритет иКеиитет по лелатв зобретений и отирцтипри Совете В 1 инистровСССР ДК 681,3,053(088.8. Бюллетень10 публиковано 14.111.1 ата опу бликования писания 25.1 Ч.197 Авторизобретения, Кисл аявитель СТРОИСТВО ДЛЯ КОРРЕКЦИ ИТЕРАТИВНОГО КВУМЕРНОГ пведена на черк управления 1, , блок декодпротеже.Устройство содержит бл чо блок хранения информации Изооретсние относится к области кодипования.Известно, что применение итеративньх кодов представляет собой эффективный способ повышения помехоустойчивости связи, Однако, известные устройства для коррекции двумерного итеративного кода, построенные на основе известных способов декодирования итеративных кодов, не позволяют полностью реализовать корректирующую способность этих кодов, за исключением случая, когда один из используемых кодов (например, код по столбцам) представляет собой код с обнаружением одиночной ошибки. Так, если код по строкам исправляет а; ошибок, а код по столбцам - аошибок, то известные устройства позволяет исправить все ошибки кратности аа, + а + а, или менее и только часть ошибок большой кратности.В предлагаемом устройстве полностью реализуются свойства итеративных кодов по исправлению ошибок - исправляются все ошибки кратности ап = 2 агав + аг+ ав при любых значениях а, и при а,=1, т, е. когда по столбцам используется код Хемминга с исправлением одиночной ошибки.Данное устройство отличается тем, что на выход исправленной строки блока декодирования для кода ло строкам подан вычислитель синдром-матрицы, связанный с выходом номера строки блока хранения пнформац:п,подсоединенный своим параллельным выходом строк синдром-матрицы к матричному перемножителю и различителю типа синдром 5 матрицы, потенциальные выходы которогоподаны на блок управления для задания режима вторичной коррекции, а выход типовыхсиндром-векторов подсоединен к формирователю возможных синдромов, связанному по 10 следовательным выходом синдрома с блокомномеров, параллельным выходом синдрома сматричным перемножителем и выходом характеристики синдрома - с коммутатором.При этом выходы возможных векторов транс 15 формации матричного перемножптеля поданычерез коммутатор на сумматор, связанныйвторым своим входом с блоком декодирования, а выходом - со входом записи блокахранения информации, и на перемножитель,20 подсоединенный другим входом к выходувектора коррекции блока декодирования, асвоим выходом - к определптелю достоверности, связанному с блоком номеров, подключенному к адресному входу блока хране 25 ния информации. Это позволяет уменшитьчисло искаженных сообщений,Блок-схема устройства првания 3, вычислитель синдрома-матрицы 4, различитель типа синдром-матрицы 5, формирозатель возможных синдромов 6, сумматор 7, блок номеров 8, матричный,перемножитель 9, коммутатор 1 О, перемножитель 11, определитель достоверности 12.Устройство работает следующим образом.К моменту 1 о прихода пускового импульса в блок управления 1 все т строк итеративного кода находятся в блоке хранения информации 2, Сигналы управления, поступающие с блока 1 в блок 2, обеспечивают возможность работы блока хранения информации в режимах записи и считывания с последовательной выборкой строк, а также в режимах записи и считывания с произвольной выборкой строк, номера которых подаются на адресный вход блока 2. Кроме того, возможно считывание с перезаписью считываемой строки (регенерация без коррекции) или с записью на ее место сигнала, поступающего на вход записи блока 2 (регенерация с коррекцией). При этом строки нумеруются таким образом, что номер у-ой строки совпадает с синдромом для у-ой позиции кода с исправлением одиночной ошибки, используемого по столбцам.При поступлении в блок 1 пускового импульса начинается первый этап работы корректора, а блок 2 устанавливается в режим считывания с последовательной выборкой при регенерации без коррекции, При этом с выхода информации 13 блока 2 считываются строки В 1, которые поступают в блок декодирования 3. Блок 3 находит вектор ошибок и исправляет ошибку в коде, используемом по строкам с задержкой Тз на выходе исправленной строки 14 блока 3 ,в последовательПном коде формируется вектор В, поступающий в вычислитель синдром-матрицы 4, Одновременно сюда с выхода номера строки 15 блока 2 подается в параллельном коде номер строки 5;. В блоке 4 находится матрица1 РМ; = Я; Х В, которая одновременно складывается по модулю 2 с ранее полученной матрицей. Весь этап состоит из и циклов, в каждом из которых обрабатывается одна из т строк итеративного кода. После считывания с блока 2 последней строки в регистрах блока 4 находится синдром-матрица.На втором этапе анализируется структура синдром-матрица, Для этого синдром-векторы (столбцы синдром-матрицы) последовательно считываются с блока 4;в параллельном коде на различитель типа синдром-матрицы 5, Весь этап состоит из а циклов - по числу синдром-векторов,Блок 5 к концу анализа синдром-матрицы может находиться в одном из четырех состояний Ро, Рь Рь Рз, соответствующих четырем возможным вариантам решений, выносимых в конце второго этапа. В начале анализа блок 5 находится в состоянии Ро, в котором он и остается до конца второго этапа, если60 65 В первом периоде каждого основного 1-го цикла в блоке номеров 8 формируется синдром 5;, который подается в последовательном коде на адресный вход блока 2. Приэтом в результате прохождения строки В 1 с блока 2 в блок 3 на,выходе 17 блока 3 формируетвсе синдром-векторы нулевые, С приходом в блок 5 первого ненулевого синдром-вектора Ъ он переводится в состояние Р а вектор Г, проходит в последовательном коде с бло ка 5 в формирователь возможных синдромов6. Считываемые в последующие циклы с блока 4 ненулевые синдром-,векторы сравниваются с вектором 1, поступающим для этого в каждом цикле с блока 6 в блок 5, Если все 10 последующие ненулевые синдром-векторы совпадают с Ъ то к концу второго этапа блок 5 остается в состоянии Рь Если же появляется такой ненулевой синдром-вектор Ъ, =,Ф= Ъь блок переходит в состояние Р а вектор15 поступает в блок 6, Во время последующихциклов,все ненулевые синдром-векторы с блока 4 сравниваются с синдром-векторамии Р+Р, поступающими в блок 5 сблока 6, Если при этом среди остальных не нулевых синдром-векторов не окажется такого, который отличен одновременно от Р,и У + Р блок 5 остается в состоянии Р до конца второго этапа, в противном случае он переходит в состояние Рз. Дальнейший алго ритм работы корректора определяет состояние блока 5 к концу второго этапа.Как только блок 5 оказывается в состоянии Р, что соответствует обнаружению некорректируемой ошибки, импульс с его выхо да сброса 15 проходит на вход стирания блока хранения информации 2, в результате чего находящаяся в этом блоке комбинация итеративного кода стирается.Сигнал о том, что блок 5 находится в со стоянии Р Р или Р, поступает в блок управления 1,При сигнале Р что соответствует правильному исправлению ошибок в блоке декодирования, устройство переходит на заключи тельный этап работы, При этом в блоке управления 1,вырабатываются сигналы, которые переводят блок 2 в режим регенерации с коррекцией с последовательной выборкой строк, Исправленные строки ппоходят с бло ка декодирования на вход записи блока 2 через сумматор по модулю два 7, на второй вход которого поступают только нули.При наличии сигнала Рчто соответствует неверному исправлению в блоке 3 одной 50 строки или двух строк с одинаковым вектором трансформации, корректор переходит к третьему этапу работы. При этом блок 3 работает в режиме регенерации без коррекции с произвольной выборкой строк, номера кото рых поступают на адресный вход 16 блока 2.Весь этап делится на т основных и один дополнительный цикл, состоящие из двух периодов.60 65 ся вектор коррекции Т,а, С блока б на матричный перемножитель 9 подается вектор Ьг, В блоке 9 находится матричное ароизведение В = Л О Ъ, с суммированием по правилу дизъюнкции. Вектор В с выхода блока 9 проходит через коммутатор 10 на перемножитель 11, на другой вход которого синхронно с Вг подается вектор коррекции Т;,. В определителе достоверности 12 подсчитывается число единиц К; в векторе правдоподобия йа = В,Тги с выхода перемножителя 11.Во втором периоде основного 1-го цикла корректор работает так же, как и в первый, за исключением того, что на адресный вход блока 2 подается номер 5;+ Рг. При этом формируется число У;=У,а -,Ю;где Р, - число единиц в векторе, поступающем с выхода перемножителя 11 во втором периоде.В блоке 12 происходит также сравнение величины Р; с числом 11 гхранящимся в его ,памяти. Если К,) Кгв узел памяти блока 12 записывается число У; и вырабатывается импульс, поступающий на вход управления сменой номера 18 блока 8, в результате чего в узел памяти блока номеров записывается вектор 5;. Если же У;( Ргэти операции не,происходят. Так как к началу третьего этапа узлы памяти блоков 8 и 12 очищаются, то к концу этого этапа в узле памяти блока 8 оказывается записанным номер строки, трансформация которой наиболее вероятна.Отметим, что вариант возможной трансформации одной строки реализуется, когда номер, вырабатываемый в блоке 8 совпадает с синдром-вектором 1 г. При этом во втором периоде в блок 2 поступает нулевой номер, который в блоке хранения информации не используется, а потому сигнал на его выходе 13 отсутствует. При принятом алгоритме перебора возможных вариантов одна и та же пара строк оценивается на достоверность дважды - при выработке в блоке 8 номера 5, (пара 5; и 5; + Ъг) и номера 5; + У, (пара 5, + Рг и 5,). Такое излишнее повторение сделано для упрощения аппаратуры.Четвертый этап состоит из одного цикла с двумя периодами. Блок хранения информации устанавливается в режим регенерации с коррекцией с произвольной выборкой. В первом периоде на блок 2 проходит номер 5 с узла памяти блока 8, во втором периоде 5+ Рг.Вектор трансформации, образуемый так же, как и на третьем этапе, с выхода коммутатора 10 поступает в сумматор по модулю два 7, где складывается с исправленной строкой с блока 3. Результат сложения подается на вход записи блока 2. Таким образом происходит коррекция трансформированных строк, после чего устройство переходит на заключительный этап работы.При наличии в конце второго этапа сигнала Р, что соответствует неверному исправлению в блоке 3 двух строк с разными векторами трансформации, наступает этап работы За. 5 10 15 20 25 30 35 40 45 50 55 Весь этап состоит из трех циклов, включающих в себя четыре периода. Блок хранения информации работает так же, как и на третьем этапе.В первом и втором периодах первого цикла оценивается достоверность возможной трансформации строки с номером 1 г, а во время третьего и четвертого периодов - строки Для этого в первом и втором периодах в блок 2 с блока б через блок 8 поступает номер Г, а в третьем и четвертом - номер Ъ.В блоке б формируется вектор ортогональности Ъо = Ъ Х (гг + 1 г), котоРый одновРе. менно с вектором Гг подается на матричный перемножитель 9. В блоке 9 образуются векторы П=ЛРФ Г, и П,=МФ гХ(Рг+ + которые синхронно в последовательном коде поступают на коммутатор 10. В первом периоде, который предназначен для случая, когда 10 Ф О, на выход коммутатора проходит вектор П. Достоверность трансформации строки с номером Гг определяется с помощью блоков 11 и 12 так же, как и на третьем этапе. При Ъ, Ф О выход блока 10 во втором периоде блокируется импульсом с выхода характеристики синдром-вектора 19 блока 6.Если же Ъо = О, то П = О, и на вход блока 12 в первом периоде поступают только нули. При этом во втором периоде выход блока 10 не блокируется (югпульс на выходе 19 отсутствует), и формируемый в нем вектор В, = П, + П проходит в перемножитель 11.Аналогично работает корректор в третьем и четвертом периодах, Таким же образом определяется достоверность возможной трансформации пар векторов 1, + Ъ, и Гг 1, и Г, + Рг, а наиболее достоверный вариант находится так же, как на третьем этапе. Отличие заключается только в том, что в блоке 8 запоминаются не номера строк, а номер одного из трех возможных вариантов,Все необходимые векторы типа 1 г, Ъг Х (Ъг + 1) и т. п, вырабатываются в трех циклах путем специального циклического преобразования исходных векторов Ъги 1.Этап 4 а состоит из одного, двух илп трех таких же циклов, как на этапе За, Сигнал на выходе блока 10 такой же, как на этапе За. Когда номер цикла совпадает с номером, хранящимся в узле памяти блока 8, блок 2 переводится в режим регенерации с коррекцией с произвольной выборкой. Трансформированные строки корректируются так же, как на этапе 4 апосле чего устройство переходггт на заключительный этап, работы. Предмет изобретения Устройство для коррекции двумерного итеративного кода, содержащее блок хранения информации, блок управления, блок декодирования для исправления ошибок в коде по строкам и сумматор, от,гичающееся тем, что, с целью уменьшения числа искаженных сообЗаказ 1018/12 Изд,358 Тираж 448 ПодписноеЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССРМосква, Ж, Раушская наб., д. 4/5 Типография, пр. Сапунова, 2 гцений, оно содержит вычислитсль синдром- матрицы, матричный перемножитель, различитель типа синдром-матрицы, формирователь возможных синдромов, перемножитель, определитель достоверности блок номеров и коммутатор, выход которого подкл 1 очен к первому входу перемножителя и к первому входу сумматора, один вход - к выходу матричного перемножителя, а другой - к первому выходу формирователя возможных синдромов, выход перемножителя подсоединен ко входу онределителя достоверности, а второй вход - к выходу вектора коррекции блока декодированиявыход исправления строки которого соединен с 1 первым входом вычислителя синдрома-матрицы и со вторым входом сумматора, второй вход вычислителя синдрома-матрицы подключен к выходу номера строки блока хранения информации, адресный вход которого подсоединен к выходу блока номеров, первый вход блока номеров соединен с выходом определителя достоверности, а второй - с выходом синдрома формирователя возможных синдромов, связанного с различителем типа синдром-матрицы, выход 10 вычислителя синдрома-матрицы подключенко входу различителя типа синдром-матрицы, соединенного с блоком управления и с первым входом матричного перемножителя, второй вход которого 1 подсоединен ко второму 15 выходу формирователя возможных синдромов,