УСТРОЙСТВО для КОРРЕКЦИИ ДВУМЕРНОГО ИТЕРАТИВНОГО КОДА Советский патент 1972 года по МПК H03M13/51 G06F11/08 

Изобретение относится к области кодирования.

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

В предлагаемом устройстве полностью реализуются свойства итеративных кодов по исправлению ошибок - исправляются все ошибки кратности «п 2агав + аг+ссв при любых значениях Кг и при , т. е. когда по столбцам используется код Хемминга с исправлением одиночной ошибки.

Данное устройство отличается тем, что на выход исправленной строки блока декодирования для кода по строкам подан вычислитель синдром-матрицы, связанный с выходом

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

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

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

вания 3, вычислитель -синдрома-матрицы 4, разлнчитель типа синдром-матрицы 5, формирователь возможных синдромов 6, сумматор 7, блок номеров 8, матричный -перемножитель 9, коммутатор 10, перемножитель 11, определитель достоверности 12.

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

К моменту /о прихода пускового импульса в блок управления 1 все m строк итеративного кода находятся в блоке хранения информации 2. Сигналы управления, поступающие с блока 1 в блок 2, обеспечивают возможность работы блока хранения информации в режимах записи и считывания с последовательной выборкой строк, а также в режимах записи и считывания -с произвольной выборкой строк, номера которых подаются на адресный вход блока 2. Кроме того, возможно считывание с перезаписью считываемой строки (регенерация без коррекции) или с записью на ее место сигнала, поступающего на вход записи блока 2 (регенерация с коррекцией). При этом строки нумеруются таким образом, что номер /-ой строки совпадает с синдромом для /-ОЙ позиции кода с исправлением одиночной ошибки, используемого по столбцам.

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

строки ВJ , которые поступают в блок декодирования 3. Блок 3 находит вектор ошибок и исправляет ошибку в коде, используемом по строкам с задержкой Гз на выходе исправленной строки 14 блока 3 в последовательном коде формируется вектор Bj , поступающий в вычислитель синдром-матрицы 4. Одновременно сюда с выхода номера строки 15 блока 2 подается в параллельном коде номер строки Sj. В блоке 4 находится матрица

Mj Sj X BJ , которая одновременно складывается по модулю 2 с ранее полученной матрицей. Весь этап состоит из т циклов, в каждом из которых обрабатывается одна из т строк итеративного кода. После считывания с блока 2 последней строки в регистрах блока 4 находится синдром-матрица.

На втором этапе анализируется структура синдром-матрица. Для этого синдром-векторы (столбцы синдром-матрицы) последовательно считываются с блока 4 в параллельном коде «а различитель типа синдром-матрицы 5. Весь этап состоит из п циклов - по числу синдром-векторов.

Блок 5 к концу анализа синдром-матрицы может находиться в одном из четырех состояний РО, PI, PZ, Р&, соответствующих четырем возможным вариантам решений, выносимых в конце второго этапа. В начале анализа блок 5 находится в состоянии РО, в котором он и остается до конца второго этапа, если

все синдром-векторы нулевые. С приходом в блок 5 первого ненулевого синдром-вектора У он переводится в состояние Р, а вектор У проходит в последовательном коде с блока 5 в формирователь возможных синдромов 6. Считываемые в последующие циклы с блока 4 ненулевые синдром-векторы сравниваются с вектором FI, поступающим для этого в каждом дикле с блока 6 в блок 5. Если все

последующие ненулевые синдром-векторы совцадают с Vi, то к концу второго этапа блок 5 остается в состоянии Р. Если же появляется такой ненулевой синдром-вектор V ф V, блок переходит в состояние Р, а вектор Vz

поступает в блок 6. Во время последующих циклов все ненулевые синдром-векторы с блока 4 сравниваются с синдром-векторами V, УЗ и , поступающими в блок 5 с блока 6. Если при этом среди остальных ненулевых синдром-векторов не окажется такого, который отличен одновременно от Vi, V и У| + Vz, блок 5 остается в состоянии 2 До конца второго этапа, в противном случае он переходит в состояние РЗ. Дальнейший алгоритм работы корректора определяет состояние блока 5 к концу второго этапа.

Как только блок 5 оказывается в состоянии РЗ, что соответствует обнаружению некорректируемой ошибки, импульс с его выхода сброса 15 проходит на вход стирания блока хранения информации 2, в результате чего находящаяся в этом блоке комбинация итеративного кода стирается.

Сигнал о том, что блок 5 находится в состоянии РО, Р или PZ, поступает в блок управления .

При сигнале PQ, что соответствует правильному исправлению ошибок в блоке декодирования, устройство переходит на заключительный этап работы. При этом в блоке управления / вырабатываются сигналы, которые переводят блок 2 в режим регенерации с коррекцией с последовательной выборкой строк. Исправленные строки проходят с блока декодирования на вход записи блока 2 через сумматор по модулю два 7, на второй вход которого поступают только нули.

При наличии сигнала Р, что соответствует неверному исправлению в блоке 3 одной

строки или двух строк с одинаковым вектором трансформации, корректор переходит к третьему этапу работы. При этом блок 3 работает в режиме регенерации без коррекции с произвольной выборкой строк, номера которых поступают на адресный вход 16 блока 2. Весь этап делится на т основных и один дополнительный цикл, состоящие из двух периодов.

В первом периоде каждого основного /-го цикла в блоке номеров 8 формируется синдром Sj который подается в последовательном коде на адресный вход блока 2. При этом ся вектор коррекции Гд. С блока 6 на матричный перемножитель 9 подается вектор Vi. В блоке 9 находится матричное ироизведение B M@Vi с суммированием по правилу дизъюнкции. Вектор В с выхода блока 9 проходит через коммутатор 10 на перемножитель 11, на другой вход которого синхронно с Bi подается вектор коррекции Г. В определителе достоверности 12 подсчитывается число единиц Wji в векторе правдоподобия Dji с выхода перемножителя //. Во втором периоде основного /-го цикла корректор работает так же, как и в первый, за исключением того, что на адресный вход блока 2 подается номер Sj + V. При этом формируется число + Wj2, где Wjz- число единид в векторе, поступающем с выхода леремножителя 11 во втором периоде. В блоке 12 происходит также сравнение величины Wj с числом Wji, хранящимся в его памяти. Если Wj Wh, в узел памяти блока 12 записывается число Wj и вырабатывается импульс, поступающий на вход управления сменой номера 18 блока 8, в результате чего в узел памяти блока номеров записывается вектор Sj. Если же , эти операции не происходят. Так как к началу третьего этапа узлы памяти блоков 8 и 12 очищаются, то к концу этого этапа в узле памяти блока 8 оказывается записанным номер строки, трансформация которой наиболее вероятна. Отметим, что вариант возможной трансформации одной строки реализуется, когда номер, вырабатываемый в блоке 8 совпадает с синдром-вектором УЬ При этом во втором оериоде в блок 2 поступает нулевой номер, который в блоке хранения информации не используется, а потому сигнал на его выходе 13 отсутствует. При принятом алгоритме перебора возможных вариантов одна и та же пара строк оценивается на достоверность дважды - при выработке в блоке 8 номера Sj (пара Sj и Sj-f У) и номера Sj + У (пара Sj + У и Sj). Такое излищнее повторение сделано для упрощения аппаратуры. Четвертый этап состоит из одного цикла с двумя периодами. Блок хранения информации устанавливается в режим регенерации с коррекцией с -произвольной выборкой. В первом периоде на блок 2 проходит номер S с блока 8, во втором периоде узла памяти s+y.. Вектор трансформации, образуемый так же, как и на третьем этапе, с выхода коммутатора 10 поступает в сумматор по модулю два 7, где складывается с исправленной строкой с блока 3. Результат сложения подается на вход записи блока 2. Таким образом происходит коррекция трансформированных строк, после чего устройство переходит на заключительный этап .работы. Весь этап состоит из трех циклов, включающих в себя четыре периода. Блок хранения информации |работает так же, как и на третьем этапе. В первом и втором периодах первого цикла оценивается достоверность возможной трансформации строки с номером У, а во время третьего и четвертого периодов - строки Vz. Для этого в первом и втором периодах в блок 2 с блока 6 через блок 8 поступает номер УЬ а в третьем и четвертом - номер УаВ блоке 6 формируется вектор ортогональности УО Vi X (Vi + 2), который одновременно с вектором У подается на матричный перемножитель 9. В блоке 9 образуются векторы Я1 Л1тф У и Я2 У1Х(1+ + 2), которые синхронно в последовательном коде поступают на коммутатор 10. В первом периоде, который предназначен для случая, когда УО 7 О, на выход коммутатора проходит вектор П. Достоверность трансформации строки с номером У определяется с помощью блоков // и 12 так же, как и на третьем этапе. При УО т О выход блока 10 во втором периоде блокируется импульсом с выхода характеристики синдром-вектора 19 блока 6. Если же УО О, то //2 0, и на вход блока 12 в первом периоде поступают только нули. При этом во втором периоде выход блока 10 не блокируется (импульс на выходе 19 отсутствует), и формируемый в нем вектор 5т Я + Яа проходит в перемнол итель 11. Аналогично работает корректор в третьем и четвертом периодах. Таким же образом определяется достоверность возможной трансформации пар векторов У и У1У2 и У2 -f У, а наиболее достоверный вариант находится так же, как на третьем этапе. Отличие заключается только в том, что в блоке 8 запоминаются не номера строк, а номер одного из трех возможных вариантов. Все необходимые векторы типа УЬ У2, У X (У + У2) и т. п. вырабатываются в трех циклах путем специального циклического преобразования исходных векторов У1иУ2. Этан 4а состоит из одного, двух или трех таких же циклов, как на этапе За. Сигнал на выходе блока 10 такой же, как на этапе За. Когда номер цикла совпадает с номером, хранящимся в узле памяти блока 8, блок 2 переводится в режим регенерации с коррекцией с произвольной выборкой. Трансформированные строки корректируются так же, как на этапе 4а, после чего устройство переходит на заключительный этап работы, Предмет изобретения Устройство для коррекции двумерного итеративного кода, содержащее блок хранения информации, блок управления, блок декодирования для исправления ощибок в коде по строкам и сумматор, отличающееся тем, что.

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

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

вычислителя синдрома-матрицы подключен ко входу различителя типа синдром-матрицы, соединенного с блоком управления и с первым входом матричного перемножителя, второй вход которого подсоединен ко второму

выходу формирователя возможных синдромов.