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

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

 

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

Под помехоустойчивым кодированием понимается кодирование символов цифрового сигнала данных, характеризующееся использованием кодовых комбинаций, позволяющих обнаруживать и (или) исправлять ошибки в этом сигнале (ГОСТ 17657-79. Передача данных. Термины и определения. - с.9).

Под помехоустойчивым декодированием понимается операция обратная кодированию символов цифрового сигнала данных (ГОСТ 17657-79. Передача данных. Термины и определения. - с.9).

Под кодом проверки на четность с низкой плотностью понимается такой код, проверочная матрица которого имеет большинство элементов, равных нулю, и меньшинство - равных единице (R. G. Gallager. Low-Density Parity-Check Codec. - 1963, p.7).

Под параллельным каскадным кодом понимается схема кодирования, состоящая из двух параллельно соединенных через перемежитель кодов (Р.Морелос-Сарагоса. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. - Москва: Техносфера, 2005, с.238).

Известен способ декодирования низкоплотностного кода - алгоритм распространения доверия (Р.Морелос-Сарагоса. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. - Москва: Техносфера, 2005, сс. 262-263). Принцип алгоритма заключается в том, что каждый узел итеративно обменивается данными с соседними узлами через соединяющие их ребра. Начальными данными для алгоритма являются мягкие решения демодулятора, а именно логарифмическое отношение правдоподобия (LLR) для каждого бита кодового слова:

$$L^{\left(0\right)}\left(c_i\right)=\log \frac{P\left(c_i=0|y_i\right)}{P\left(c_i=1|y_i\right)}$$ ,

где:

L⁽⁰⁾(c_i) - логарифмическое отношение правдоподобия i-го элемента кодового слова, нулевой итерации;

Р(c_i=0|y_i) - условная вероятность того, что передавался 0, при условии, что приняли y_i;

Р(c_i=1|y_i) - условная вероятность того, что передавался 1, при условии, что приняли y_i.

В конце каждой итерации формируется вектор LLR:

$${\overline{L}}^{(l+1)}={\overline{L}}^{(0)}+\alpha {\overline{L}}_{ext}^{(l)}$$ ,

где

$${\overline{L}}^{(l+1)}$$ - вектор логарифмического отношения правдоподобия на (l+1)-й итерации;

$${\overline{L}}^{(0)}$$ - мягкие решения демодулятора;

$${\overline{L}}_{ext}^{(l)}$$ - сторонняя информация на l-й итерации.

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

На выходе алгоритма после выполнения l итераций формируется вектор LLR:

$${\overline{L}}^{(l)}=\left[L^{(l)}(c_1),L^{(l)}(c_2),\dots ,L^{(l)}(c_n)\right]$$ .

На основе данного вектора принимается жесткое решение - вектор V.

Синдром S кодового слова V рассчитывается по формуле:

S=V·H^T,

где вектор S состоит из (n-k) компонент (n - полная длина кодового слова, k - информационная длина кодового слова) и рассчитывается по (n-k) проверочным уравнениям, H^T - транспонированная проверочная матрица кода. В случае если вектор V является кодовым словом, все (n-k) компонент равны 0, т.е. все (n-k) проверочных уравнений равны 0.

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

Неразрешенный короткий цикл - цикл длиной шесть ребер, битовые узлы которого декодируются неоднозначно.

Также известен способ и устройство для декодирования канала в системе связи с использованием кода проверки на четность с низкой плотностью (Патент РФ №2446585, МПК Н04Н 60/88).

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

Наиболее близким по технической сущности к заявляемому изобретению (прототипом) является способ декодирования канала с использованием параллельного каскадного кода проверки на четность с низкой плотностью (Патент РФ №2461964, МПК Н03М 13/11), заключающийся в том, что после декодирования кода проверки на четность с низкой плотностью осуществляют процедуру выявления и устранения коротких неразрешенных циклов в графе Таннера, а именно по пороговому значению определяют множество индексов недостоверных бит, по полученному множеству строят вектор частот встречаемости G, определяют индексы, имеющие максимальную частоту появления в векторе G, изменяют в них знак на противоположный в кодовом слове, которое поступало на декодер, и снова выполняют декодирование полученного слова.

Наиболее близким по технической сущности к заявляемому изобретению (прототипом) является устройство LDPC-декодирования (Патент РФ №2392737, МПК Н03М 13/00), содержащее входной буфер, формирователь логарифмического отношения правдоподобия бит, итеративный декодер LDPC, выходной буфер и устройство управления, выход входного буфера соединен со входом формирователя логарифмического отношения правдоподобия бит, выход которого соединен с итеративным декодером LDPC, а выход последнего - со входом выходного буфера.

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

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

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

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

Дополнительный вектор оценок W(w₀, w₁,…, w_n) имеет размерность, равную длине кодового слова, и показывает степень недостоверности мягкого решения бита. Вектор оценок формируется следующим образом. В случае, если i-й бит после j-й итерации $$\left(j=\overline{\mathrm{0..9}}\right)$$ принимает значение меньше нуля, то i-е значение индекса вектора оценок увеличивается на единицу. Таким образом, после каждой десятой итерации элементы вектора оценок принимают значения от 0 до 9. Если i-й элемент равен 0, то данный элемент десять раз декодировался как положительное значение (т.е. в жестком виде 0), а если элемент равен 9, то данный элемент десять раз декодировался как отрицательное значение (т.е. в жестком виде 1). Коррекция мягких решений демодулятора L⁽⁰⁾(c_i) осуществляется следующим образом. Если W[i]=0 и L⁽⁰⁾[i]<0, то L⁽⁰⁾[i]=0, а если W[i]=9 и L⁽⁰⁾[i]>0, то L⁽⁰⁾[i]=-1. После чего элементы вектора W(w₀, w₁,…) обнуляются и за следующие десять итераций формируются заново. Также вектор дополнительных оценок участвует в процедуре определения и разрешения коротких циклов в графе Таннера, а именно с его помощью определяют индексы недостоверных бит. Недостоверные биты - это биты, которые можно с одинаковой вероятностью декодировать как «0», так и «1». В прототипе (Патент РФ №2461964, МПК Н03М 13/11) недостоверные биты определяются по абсолютному пороговому значению. При наиболее оптимальном пороге, установленном экспериментально, вероятность, рассчитанная по формуле P=n/N, где N - число индексов, биты которых имеют абсолютное значение меньше порогового, a n - число индексов из N, которые декодировались неверно, составляет «0.25», т.е. из ста отобранных индексов только 25 декодировалось неверно. В случае использования вектора достоверности мягких решений демодулятора W(w₀, w₁,…, w_n) для определения недостоверных бит, где недостоверными решениями являются те, которые имеют в векторе W значение, равное «4» или «5», вероятность, рассчитанная по выше написанной формуле, равна «0.491». Таким образом, при использовании вектора достоверности мягких решений демодулятора формируется наиболее полное множество недостоверных бит. На фигуре 4 показана зависимость вероятности ложного декодирования бит от значений вектора достоверности мягких решений демодулятора.

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

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

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

Следовательно, заявленное изобретение соответствует условию патентоспособности «изобретательский уровень».

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

Заявленный способ поясняется чертежами, на которых показаны:

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

1 - операция декодирования десяти итераций (0-9);

2 - процедура коррекции мягких решений демодулятора после десятой итерации;

3 - операция декодирования десяти итераций (10-19);

4 - процедура коррекции мягких решений демодулятора после двадцатой итерации;

5 - операция декодирования десяти итераций (20-29);

6 - процедура коррекции мягких решений демодулятора после тридцатой итерации;

7 - операция декодирования десяти итераций (с 10·(k-1) по 10·k);

8 - процедура коррекции мягких решений демодулятора после 10·k итерации;

9 - процедура расчета синдрома кодового слова;

10 - процедура обнаружения и устранения коротких циклов в графе Таннера;

L - кодовое слово, принятое из канала связи;

L_n - кодовое слово после n-й операции декодирования;

$$L_n^{correct}$$ - скорректированное кодовое слово после n-й операции декодирования;

L_cycle - кодовое слово с неразрешенными короткими циклами в графе Таннера;

L_{with out cycle} - кодовое слово с разрешенными короткими циклами в графе Таннера;

L^correct - декодированное кодовое слово;

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

А1 - инициализация алгоритма декодирования;

А2 - проверка условия: равен номер текущей итерации предельному числу итераций или нет;

A3 - инициализация (обнуление) вектора достоверности мягких решений демодулятора;

А4 - увеличение номера текущей итерации;

А5 - проверка условия: равен нулю номер текущей итерации по модулю 10 или нет;

А6 - выполнение одной итерации декодирования алгоритма распространения доверия;

A7, A8, A9 - формирование вектора достоверности мягких решений демодулятора;

А10, А11, А12, А13, А14, А15 - коррекция мягких решений демодулятора;

А16 - расчет синдрома кодового слова;

А17 - проверка условия: равен синдром кодового слова нулю или нет;

фигура 3 - схема устройства, реализующая алгоритм декодирования кода проверки на четность с низкой плотностью:

В1 - модуль накопления и хранения входных значений до прихода следующего кодового слова;

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

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

B4 - модуль накопления и хранения декодированных бит;

B5 - декодер низкоплотностного кода;

B6 - счетчик итераций низкоплотностного кодирования;

B7 - устройство контроля и формирования сигналов управления;

фигура 4 - зависимость вероятности ложного декодирования бит от значений вектора достоверности мягких решений демодулятора.

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

Над принятым из канала связи кодовым словом L в блоке 1 выполняются первые десять итераций декодирования алгоритмом распространения доверия и формируется вектор достоверности мягких решений демодулятора W(w₀,w₁,…,w_n), элементы которого принимают значения от «0» до «9». Если W[i]=9, то i-e мягкое решение декодировалось 9 раз как отрицательное значение, если W[i]=0, то i-е мягкое решение декодировалось 9 раз как положительное значение. В блоке 2 на основе значений вектора W производится коррекция мягких решений демодулятора $$L_n^{correct}$$ , вектор достоверности W обнуляется и в блоках 3, 4, 5, 6, 7, 8 процесс повторяется. В блоке 9 после 10·k итераций выполняется расчет синдрома кодового слова. В случае если синдром равен 0, кодовое слово поступает на выход (L^correct), в противном случае - на процедуру обнаружения и устранения коротких циклов в графе Таннера (L_cycle). Данная процедура выполняется, как и в прототипе, за исключением того, что множество недостоверных бит определяется не по пороговому значению, а по значениям вектора достоверности мягких решений демодулятора, а именно недостоверные биты - биты, имеющие значения вектора W, равные «4» или «5». После устранения коротких циклов кодовое слово L_{with out cycle} вновь поступает на блок 1 и заново повторяется весь цикл обработки.

Общий алгоритм способа декодирования сигналов с использованием кода проверки на четность с низкой плотностью представлен на фигуре 2. На начальном этапе декодирования сигнала текущее число итераций ставится равным нулю и инициализируется вектор достоверности мягких решений демодулятора: $$\text{n}=\text{0}\text{, W[m]}=\text{0}\text{, m}=\overline{\text{0}\text{,}\dots \text{,N-1}}$$ (блок А1). Далее проверяется условие: не превышает ли номер текущей итерации предельное число итераций декодирования (блок А2). В случае превышения кодовое слово поступает на выход, в противном случае - снова происходит инициализация вектора достоверности мягких решений демодулятора (блок A3) и текущий номер итерации декодирования увеличивается на один (блок А4). Затем проверяется условие: равен ли нулю по модулю десять номер текущей итерации (блок А5). Если не равен, то продолжается формирование вектора недостоверности мягких решений демодулятора (блок А7, А8, А9). В противном случае - вектор достоверности мягких решений демодулятора сформирован и выполняется коррекция мягких решений демодулятора - от начала до конца кодового слова в цикле (блок А10) перебираются значения вектора достоверности. Если элемент вектора принимает крайние значения - «0» или «9» (блок A11), то проверяется условие: если для конкретного мягкого решения бита значение вектора достоверности равно «0» (данный бит десять раз декодировался как положительное значение), а мягкое решение демодулятора -отрицательное значение (блок А 12), то мягкому решению демодулятора присваивается значение «0» (блок А13). Если для конкретного мягкого решения бита значение вектора достоверности равно «9» (данный бит десять раз декодировался как отрицательное значение), а мягкое решение демодулятора - положительное значение (блок А14), то мягкому решению демодулятора присваивается значение «-1» (блок А15). После коррекции мягких решений демодулятора рассчитываем синдром декодированного кодового слова (блок 17), если он равен «0», то кодовое слово поступает на выход. В противном случае данное кодовое слово снова поступает на вход блока 1, и весь цикл обработки повторяется заново.

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

Декодируемое кодовое слово поступает во входной буфер В1, предназначенный для накопления входных данных во время декодирования и предотвращения потери входных данных. Из входного буфера считывается декодируемое кодовое слово, и в блоке В2 формируется мягкое решение демодулятора, которое в процессе декодирования может изменяться после десяти итераций с помощью модуля коррекции логарифмического отношения правдоподобия бит ВЗ. Исправление ошибок в принятом кодовом слове достигается за счет итеративного декодера LDPC B5. Процесс декодирования контролируется счетчиком промежуточных итераций В6, который формирует сигнал переполнения при достижении значения «10». В этот момент происходит коррекция логарифмических отношений правдоподобия входных бит (мягкого решения демодулятора) В3. Результат декодирования записывается в выходной буфер В4, предназначенный для согласования скорости считывания декодированных бит и тактовой частоты декодера. Все вышеперечисленные блоки формируют сигналы индикации работы на устройство управления В7, которое в зависимости от режима работы формирует различные управляющие воздействия.

Для реализации описанной выше схемы была использована программируемая логическая интегральная схема (ПЛИС) XC6VSX240T-FF1156-1 фирмы Xilinx семейства Virtex-6. В таблице представлены ресурсы ПЛИС, необходимые для реализации предлагаемого способа помехоустойчивого декодирования.

Таблица 1
Ресурсоемкость предлагаемого способа помехоустойчивого декодирования
Ресурсоемкость Slice Logic	используется	всего	проценты
Количество Slice Registers	36391	58880	61%
Количество Slice LUTs	45765	58880	77%
Количество используемых как логика	45600	58880	77%
Количество используемых как память	165	24320	0%
Ресурсоемкость специализированных блоков
Количество Block RAM/FIFO	153	244	62%
Количество BUFG/BUFGCTRLs	6	32	18%
Количество DSP48Es	180	640	28%
Количество PLL ADVs	1	6	16%

Для оценки эффективности предлагаемого способа помехоустойчивого декодирования по сравнению с существующим способом, описанном в прототипе, была разработана программная модель декодера в среде Microsoft Visual Studio 2008, в которой реализуется алгоритм предлагаемого способа помехоустойчивого декодирования для сигналов стандарта DVB-S2, где код проверки на четность с низкой плотностью входит в состав каскадной конструкции, а также для параллельной схемы турбо-кодирования, где код проверки на четность с низкой плотностью является компонентным кодом. Эксперимент показал, что при использовании модуляции QPSK для стандарта DVB-S2 для всех скоростей кодирования энергетический выигрыш составил 0.2-0.3 дБ. При использовании параллельной схемы турбо кодирования - 0.5 дБ.

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

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