СПОСОБ ДЕКОДИРОВАНИЯ ЦИКЛИЧЕСКОГО ПОМЕХОУСТОЙЧИВОГО КОДА Российский патент 2004 года по МПК H03M13/00 H03M13/15 G06F11/14 

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

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

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

Предлагаемый способ направлен на решение актуальной задачи повышения помехоустойчивости приема циклического кода при работе в каналах с высоким уровнем помех.

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

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

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

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

Наиболее близким к предлагаемому способу является способ (прототип) декодирования циклического помехоустойчивого кода, заключающийся в том, что на передающей стороне формируют выходную последовательность, представляющую собой сумму по модулю два циклического помехоустойчивого кода и синхронизирующей последовательности. На приемной стороне принятую последовательность сначала умножают на проверочный полином помехоустойчивого кода и в результате вычисляют синхронизирующую последовательность. Далее осуществляют обнаружение определенной комбинации синхронизирующей последовательности с учетом ошибок, наложенных на принятую последовательность в канале связи. При обнаружении синхронизирующей последовательности принимают решение о наличии цикловой синхронизации и выделяют помехоустойчивый код. Затем определяют комбинацию ошибок и осуществляют исправление ошибок в информационной части помехоустойчивого кода [3].

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

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

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

Рассмотрим осуществление предлагаемого способа декодирования циклического помехоустойчивого кода.

На передающей стороне формируют выходную последовательность. Для этого исходное сообщение объемом k символов вначале кодируют циклическим помехоустойчивым кодом. В результате кодирования информации получают слово циклического кода C(n,k)=a₀,a₁,...,а_n-1, информационная длина которого составляет k символов, а блоковая - n символов. Поскольку код является циклическим, существует рекуррентное соотношение, с помощью которого можно получить все контрольные символы кода

Далее слово циклического кода C(n,k) рекуррентно продолжают с помощью того же соотношения до длины n₁ ≥ n и при этом в силу цикличности помехоустойчивого кода получают последовательность, состоящую из тех же символов кода

K(n₁,k)=a₀,a₁,...,a_n-1,a₀,a₁,...,a_n-1,...,a₀,a₁,...,a_n-1,

т.е. получают код с повторением. Свойством такого кода, в отличие от обычного кода с повторением, будет то, что любая комбинация символов в скользящем окне длины n символов будет словом помехоустойчивого кода C(n,k).

Далее формируют постоянную циклическую синхронизирующую последовательность длины n символов. Такой последовательностью может быть любая последовательность подходящей длины с хорошими синхронизирующими свойствами, например последовательность максимальной длины (код Рида-Маллера 1-го порядка). Эту последовательность рекуррентно продолжают до длины n₁ символов

D(n₁)=d₀, d₁,..., d_n-1, d₀, d₁,..., d_n-1,..., d₀, d₁,..., d_n-1.

Символы выходной последовательности на передающей стороне

В(n₁)=b₀, b₁,...,b_n-1, b₀, b₁,...,b_n-1,..., b₀, b₁,...,b_n-1

получают сложением по модулю два символов циклического кода с символами синхронизирующей последовательности:

b_i=c_i ⊕ d_i i=0...n-1.

На приемной стороне принятая последовательность, из-за ошибок в канале связи, в общем случае отличается от передаваемой последовательности B(n₁) и может быть записана в виде:

B^l(n₁)=b10

,b11,...,b1n-1,b20,b21,...,b2n-1,...,bj0,bj1,...,bjn-1.

После приема последнего символа bjn-1

из канала связи декодируют последнее принятое кодовое слово bj0, bj1,...,bjn-1, а также формируют и декодируют циклические продолжения принятой последовательности.

В предлагаемом способе под циклическим продолжением принятой последовательности будем понимать кодовое слово, составленное из последних i(i=n-1...1) символов принятой последовательности, дополненных до длины n символов ранее принятыми символами, так что совокупность нижних индексов всех символов циклического продолжения составляет циклическую последовательность.

Например, принятая последовательность

B¹(n₁)=bl0

,b11,...,b1n-1,b20,b21,...,b2n-1,...,bj0,bj1,...,bjn-1

вместе с возможными циклическими продолжениями запишется в виде

bl0

,b11,...,b1n-1,b20,b21,...,b2n-1,...,bj0,bj1,...,bjn-1,bj-10,bj-11,...,bj-1n-2;

bl0

,b11,...,b1n-1,b20,b21,...,b2n-1,...,bj0,bj1,...,bjn-1,bj-20,bj-21,...,bj-2n-2;

bl0

,b11,...,b1n-1,b20,b21,...,b2n-1,...,bj0,bj1,...,bjn-1,b10,b11,...,b1n-2;

а сами циклические продолжения будут представлены следующими кодовыми словами

bj1

,...,bjn-1,bj-10; bj2...,bjn-1,bj-10,bj-11; bj3,...,bjn-1,bj-10,bj-11,bj-12; ...

bj1

,...,bjn-1,bj-20; bj2,...,bjn-1,bj-20,bj-21; bj3,...,bjn-1,bj-20,bj-21,bj-22; ...

bj1

,...,bjn-1,b10; bj2,...,bjn-1,b10,b11; bj3,...,bjn-1,b10,b11,b12;…

Всего может быть сформировано (j-1)x(n-1) циклических продолжений: для каждого из j-1 повторений кодового слова в принятой последовательности можно записать n-1 циклических продолжений.

Помимо декодирования последнего принятого кодового слова осуществляют также декодирование циклических продолжений.

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

При декодировании безошибочного кодового слова синдром кода равен нулю и в результате вычисления синдрома будет получена n-k разрядная двоичная комбинация d₀, соответствующая преобразованной синхронизирующей последовательности.

При поступлении на вход последовательности с ошибками будет вычислена комбинация из некоторого множества {d_i}, i≠0, соответствующая сумме ненулевого синдрома кода s_i и преобразованной синхронизирующей последовательности: d_i=s_i ⊕ d₀.

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

Обнаружение синхронизирующей последовательности в комбинации d₀, либо в комбинации из множества {d_i}, позволяет осуществить цикловую синхронизацию помехоустойчивого кода, т.е. определить начало помехоустойчивого кода.

Далее синхронизирующую последовательность вычитают из входной последовательности, и в результате получают слово помехоустойчивого кода.

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

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

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

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

bj1

,...,bjn-1,b10; bj2,...,bjn-1,b10,b11; bj3,...,bjn-1,b10,b11,b12; ...

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

В качестве примера отметим, что при использовании предлагаемого способа для декодирования двоичного циклического кода БЧХ(63,32), рекуррентно продолженного до длины 126 бит, вероятность неприема сообщения будет равна 0.03 на гауссовском канале, средняя вероятность ошибок в котором составляет 0.01. Декодирование кода выполняют только с обнаружением ошибок. Для сравнения, аналогичная вероятность неприема на том же канале для алгоритма декодирования без использования циклических продолжений равна 0.13. Для получения той же вероятности неприема, равной 0.03, для алгоритма декодирования без использования циклических продолжений помехоустойчивый код следует рекуррентно продолжить до длины 188 бит, т.е. дополнительно передавать 62 бита по сравнению с предлагаемым способом.

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

Источники информации

1. Лосев В.В., Бродская Е.Б., Коржик В.И. Поиск и декодирование сложных дискретных сигналов / Под ред. В.И.Коржика. - М.: Радио и связь, 1988, стр.136.

2. Болховитин Л.М., Журкин С.П., Квашенников В.В., Сосин П.А. Передача формализованных сообщений самосинхронизирующимся кодом с переменными параметрами. Техника средств связи, сер. ТПС, вып. 8, 1990, стр.39.

3. Бек Г.В., Богданович В.Н., Киреев О.П. Метод синхронизации сообщений. Сб.: Построение и анализ систем передачи информации. М.: Наука, 1980, стр.84.

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

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