СПОСОБ СИНДРОМНОГО ДЕКОДИРОВАНИЯ ДЛЯ СВЕРТОЧНЫХ КОДОВ Российский патент 2006 года по МПК H03M13/23 

Изобретение относится к радиотехнике и может быть использовано в системах радиосвязи для исправления многократных ошибок в канале связи.

Известен способ синдромного декодирования сверточных кодов путем табличного поиска с обратной связью, формирование в которой корректирующих символов по символам синдрома осуществляется путем поиска в таблице, которая реализуется на основе постоянной памяти (ПЗУ). Набор решений для всевозможных синдромов находится путем перебора. Недостатком данного способа является то, что из-за наличия обратной связи в декодере возникновение ошибки декодирования может вызвать неограниченное распространение ошибок. Вторым недостатком способа является сложность процедур декодирования при применении его для исправления большого числа ошибок [Кларк Дж.-мл., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи/ Пер. с англ. - М.: Радио и связь, 1987, стр.213, 249-265].

Целью предлагаемого изобретения является упрощение способа формирования кодовой комбинации и декодирующего устройства для гарантированного исправления многократных ошибок. Поставленная цель достигается путем применения несистематического сверточного кодера с сумматорами по модулю двумя представленными порождающими многочленами g_i(x)(i=1,2...m) такими, чтобы условие накопления катастрофических ошибок не выполнялось; при декодировании применяется принцип синдромного декодирования блочных кодов для гарантированного исправления многократных ошибок, а также устраняется эффект распространения ошибок, вызванный наличием обратной связи.

На фиг.1 представлена схема кодирующего устройства для реализации предложенного способа. Устройство содержит кодер для несистематического сверточного кода, состоящий из регистра 1 сдвига, блока 2 сумматоров по модулю два, коммутатора 3.

На фиг.2 представлена схема декодирующего устройства в виде декодера для синдромного декодирования блочных кодов, состоящего из регистра 4 сдвига, двух блоков 5 и 7 сумматоров по модулю два, логического 6 блока.

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

Для придания сверточным кодам блочной структуры к концу входной информационной последовательности А добавляется число нулевых символов, на единицу меньшее числа ячеек памяти, одновременно служащих для очистки регистра от бит данных [Скляр Бернард. Цифровая связь. Теоретические основы и практическое применение, 2-е издание/ Пер. с англ. - М.: Издательский дом «Вильяме», 2003, стр.408-409].

С помощью коммутатора 3 осуществляется поочередная подача в канал 8 сформированных на сумматорах кодовых символов выходной последовательности Х.

Принятая кодовая последовательность Х', искаженная помехами в канале 8 связи, поступает на декодирующее устройство, изображенное на фиг.2, где осуществляется вычисление синдрома и исправление ошибок. В основе вычисления синдрома кода лежит проверочная матрица Н, составленная из уравнений проверок по информационным символам. Искаженные символы последовательности подаются на регистр 4 сдвига, с выходов которого они одновременно подаются на r сумматоров по модулю два блока 5 для вычисления синдрома кода S, где r - число проверочных символов в кодовой последовательности, и на n сумматоров по модулю два блока 7 для посимвольного суммирования с построенным вектором ошибок Е, где n - общее число символов в кодовой комбинации. Построение вектора Е осуществляется в логическом 6 блоке на основе сравнения полученного синдрома с эталонными синдромами, однозначно определяющими положение ошибок и преобразования последнего в комбинацию ошибок. При этом эффект распространения ошибок отсутствует. Причем при совпадении полученного синдрома с эталонным имеем возможность как обнаружить, так и исправить ошибочные комбинации, в противном случае исправить ошибочные комбинации не удается. Для того чтобы можно было проводить сравнение синдромов логический 6 блок должен содержать устройство для хранения данных об эталонных синдромах (ПЗУ).

Пример. В качестве примера рассмотрим код со скоростью R=1/2, тремя ячейками памяти и видами связи между ячейками, определяемые порождающими полиномами g₁(x)=1+x² и g₂(x)=1+x+x² [Куликов В.В., Баркетов С.В., Солчатов М.Э., Карпов Д.К. Использование синдромного декодирования для сверточных кодов. - Физика волновых процессов и радиотехнические системы. Самара, 2003, №3, с.43-46]. Будем считать число информационных символов k=3. Для очистки регистра, а также, чтобы корректирующая способность кода не зависела от положения информационного символа (т.е. чтобы число проверок для каждого символа было одинаково) добавим во входную информационную последовательность два нулевых символа. Последовательность информационных символов на входе кодирующего устройства имеет следующий вид:

A=[a₁ а₂ a₃ 0 0].

Выходная последовательность состоит из 10 символов

X=[x₁ x₂ x₃ x₄ x₅ x₆ x₇ x₈ x₉ x₁₀],

каждый из которых связан с информационными символами уравнениями кодирования:

x₁=x₂=a₁; x₃=x₇=a₂;

x₄=a₁+a₂; x₅=a₁+a₃;

x₆=a₁+a₂+a₃; x₈=a₂+a₃;

x₉=x₁₀=a₃.

Можно описать кодер через его импульсную характеристику. Последовательность на выходе при единице на входе называется откликом кодера на импульсное возмущение. Порождающая матрица рассматриваемого кода (10,3), определенная импульсной характеристикой кодера, имеет вид:

Для построения проверочной матрицы Н^T, удовлетворяющей условию ортогональности G×H^T=0, можно воспользоваться вариантами связей символов кодовой последовательности (т.е. уравнениями проверки по информационным символам) и выбрать из полученных уравнений 7 линейно независимых, которые и составят проверочную матрицу. Один из вариантов проверочной матрицы может иметь вид:

Для обнаружения и исправления ошибок в принятой кодовой комбинации X' необходимо определить синдром

S=X'×H^T=(X+E)×H^T=[s₁ s₂ s₃ s₄ s₅ s₆ s₇],

где Е=[е₁ е₂ е₃ е₄ е₅ е₆ е₇ е₈ е₉ e₁₀] - ошибочная комбинация.

Максимальное число ненулевых синдромов составляет для этого кода 2⁷-1=127 (от 1 до 127). Положение синдрома в матрице Н^T (номер строки) отображает место одного пораженного символа в кодовой комбинации. Соответствующие однократным ошибкам синдромы, переведенные в десятичное число, примут значения

S⁽¹⁾=15; S⁽²⁾=1; S⁽³⁾=54; S⁽⁴⁾=2; S⁽⁵⁾=8; S⁽⁶⁾=4;

S⁽⁷⁾=16; S⁽⁸⁾=32; S⁽⁹⁾=108; S⁽¹⁰⁾=64.

При возникновении двукратных ошибок синдром определяется как сумма по модулю два соответствующих синдромов однократных ошибок

S^(i,j)=S⁽ⁱ⁾+S^(j).

Для проведения сравнения полученных синдромов с эталонными необходимо заранее при разработке сверточных кодов произвести расчет всех синдромов соответствующих различным ошибочным комбинациям, имеющим место для проектируемого кода согласно выражению:

S=E×H^T.

В приведенном примере проведены расчеты всех синдромов, однозначно определяющих как однократные (10 шт.), так и двукратные (45 шт.) ошибки, а также для трехкратных ошибок, не встречавшихся ранее синдромов однозначно определяющих такие ошибки (39 шт. из 120 возможных). Всего для кода (10,3) потребуется запись в логическом блоке 94-х эталонных синдромов, однозначно определяющих положение ошибок. Также рассматриваемый код гарантирует обнаружение четырехкратных ошибок.

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

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