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

 

О П И С А Н И Е 332462

ИЗОБРЕТЕНИЯ

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

Союз Советова

Социалистическив

Республив

Зависимое от авт. свидетельства М

Заявлено 11.Х1!.1969 (И 1347148/18-24) с присоединением заявки №

Приоритет

Опубликовано 14.111.1972. Бюллетень № 10

Дата опубликования списания 25.IV.1972

М. Кл. G 06f 11/00

Н 031с 36,. 24

Кеиитет по лелатв изобретений и открытиИ при Совете Министров

CCCP

УДК 681.3.053(088.8) Автор изобретения

Л. Д. Кислюк

Заявитель

УСТРОИСТВО ДЛЯ КОРРЕКЦИИ ДВУМЕРНОГО

ИТЕРАТИВНОГО КОДА

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

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

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

Хемминга с исправлением одиночной ошибки.

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

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

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

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

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

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

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

При поступлении в блок 1 пускового импульса начинается первый этап работы корректора, а блок 2 устанавливается в режим считывания с последовательной выборкой при регенерации без коррекции. При этом с выхода информации 18 блока 2 считываются строки В1, которые поступают в блок декодирования 8. Блок 8 находит вектор ошибок и исправляет ошибку в коде, используемом по строкам с задержкой Тз на выходе исправленной строки 14 блока 8 в последовательП ном коде формируется вектор В, поступающий в вычислитель синдром-матрицы 4. Одновременно сюда с выхода номера строки 15 блока 2 подается в параллельном коде номер строки S . В блоке 4 находится матрица

ll

М; = $; Х В, которая одновременно складывается по модулю 2 с ранее полученной матрицей. Весь этап состоит из т циклов, в каждом из которых обрабатывается одна из т строк итеративного кода. После считывания с блока 2 последней строки в регистрах блока 4 находится синдром-матрица.

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

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

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

2 в блок 3 на,выходе 17 блока 8 формируетвсе синдром-векторы нулевые. С приходом в блок 5 первого ненулевого синдром-вектора он переводится в состояние Р,, а вектор

V> проходит в последовательном коде с блока 5 в формирователь возможных синдромов

6. Считываемые в последующие циклы с блока 4 ненулевые синдром-,векторы сравниваются с вектором V> поступающим для этого в каждом цикле с блока б в блок 5. Если все

N последующие ненулевые синдром-векторы совпадают с V>, то к концу второго этапа блок

5 остается в состоянии Р>. Если же появляется такой ненулевой синдром-вектор V W V>, блок переходит в состояние Р>, а вектор V

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

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

Сигнал о том, что блок 5 находится в со35 стоянии Рр, Р> или Р>, поступает в блок управления 1, При сигнале Ро, что соответствует правильному ис правлению ошибок в блоке декодирования, устройство переходит на заключи40 тельный этап работы. При этом в блоке управления 1,вырабатываются сигналы, которые переводят блок 2 в режим регенерации с коррекцией с последовательной выборкой строк, Иоправленные строки ппоходят с бло45 ка декодирования на вход записи блока 2 через сумматор по модулю два 7, на второй вход которого поступают только нули.

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

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

Весь этап делится на т основных и один дополнительный цикл, состоящие из двух IIIp.риодов.

332462

65 ся вектор коррекции Т;i. С блока б на матричный перемножитель 9 подается вектор V .

В блоке 9 находится матричное ароизведение

В = Л 0 U> с суммированием по правилу дизъюнкции. Вектор В с выхода блока 9 проходит через коммутатор 10 на перемножитель 11, на другой вход которого синхронно с Вг подается вектор коррекции Т;,. В определителе достоверности 12 подсчитывается число единиц W; в векторе правдоподобия

1 а = В Ти с выхода перемножителя 11.

Во втором периоде основного j-го цикла корректор работает так же, как и в первый, за исключением того, что на адресный вход блока 2 подается номер S + V>. При этом формируется число W>- — — У,i — W;z,,где W,z— число единиц в векторе, поступающем с выхода перемножителя 11 во втором периоде.

В блоке 12 происходит также сравнение величины W; с числом Кг„хранящимся в его ,памяти. Если W ) Wn, в узел памяти блока

12 записывается число W. и вырабатывается импульс, поступающий на вход управления сменой номера 18 блока 8, в результате чего в узел памяти блока номеров записывается вектор S;. Если же W; (W<, эти операции не,происходят. Так как к началу третьего этапа узлы памяти блоков 8 и 12 очищаются, то к концу этого этапа в узле памяти блока

8 оказывается записанным номер строки, трансформация которой наиболее вероятна.

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

18 отсутствует. При принятом алгоритме перебора возможных вариантов одна и та же пара строк оценивается на достоверность дважды — при выработке в блоке 8 номера

S, (пара $; и 8;+ V>) и номера S;+ V> (пара S + V> и S ). Такое излишнее повторение сделано для упрощения аппаратуры.

Четвертый этап состоит из одного цикла с двумя периодами. Блок хранения информации устанавливается в режим регенерации с коррекцией с произвольной выборкой. В первом периоде на блок 2 проходит номер S c узла памяти блока 8, во втором периоде

S+ V(.

Вектор трансформации, образуемый так же, как и на третьем эта пе, с выхода коммутатора 10 поступает в сумматор ino модулю два 7, где складывается с исправленной строкой с блока 8. Результат сложения подается на вход записи блока 2. Таким образом происходит коррекция трансформированных строк, после чего устройство переходит на заключительный этап работы.

При наличии в конце второго этапа сигнала Р>, что соответствует неверному исправлению в блоке 8 двух строк с разными векторами трансформации, наступает этап работы За.

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

В первом и втором периодах первого цикла оценивается достоверность .возможной трансформации строки с номером 1 >, а во время третьего и четвертого периодов — строки

Для этого в первом и втором псриодах в блок 2 с блока б через блок 8 поступает номер V), а в третьем и четвертом — номер Vz.

В блоке б формируется вектор ортогональности Vo — — V Х (Vг+ V ), который одновременно с вектором VI подается на матричный перемножитель 9. В блоке 9 образуются векторы П,— М Ф V и Ïz — — М Ф (V, х (г г+

+ Vz)), которые синхронно в последовательном коде поступают на коммутатор 10. В первом периоде, который предназначен для случая, когда V< Ф О, на выход коммутатора проходит вектор П>. Достоверность трансформации строки с номером V определяется с помощью блоков 11 и 12 так же, как и на третьем этапе. При V< Ф О выход блока 10 во втором периоде блокируется импульсом с выхода характеристики синдром-вектора 19 блока б.

Если же Vo = О, то П = О, и на вход блока 12 в первом периоде поступают только нули. При этом во втором периоде выход блока 10 не блокируется (им пульс на выходе 19 отсутствует), и формируемый в нем вектор

В, = Пг+ П проходит в перемножитель 11.

Аналогично работает корректор в третьем и четвертом периодах, Таким же образом определяется достоверность возможной трансформации пар векторов Vz — Vг и V Vz u

Vz+ V<, а наиболее достоверный вариант находится так же, как на третьем этапе. Отличие заключается только в том, что в блоке 8 запоминаются не номера строк, а номер одного из трех возможных вариантов, Все необходимые .векторы типа V>, V> Х (V> + Vz) и т. п. вырабатываются в трех циклах путем специального циклического преобразования исходных векторов ги Vz.

Этап 4а состоит из одного, двух илп трех таких же циклов, как на этапе За. Сигнал на выходе блока 10 такой же, как на этапе 3а.

Когда номер цикла совпадает с номером,хранящимся в узле памяти блока 8, блок 2 переводится в режим регенерации с коррекцией с произвольной выборкой. Трансформированные строки корректируются так же, как на этапе 4a,,после чего устройство переходит на заключительный этап, работы.

Предмет изобретения

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

Составитель В. Богатырев

Редактор Б, Федотов Техред А. Камышникова Корректор Е. Михеева

Заказ 1018/12 Изд. № 358 Тираж 448 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

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

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