Способ декодирования ldpc-кодов и устройство для его осуществления

Изобретение относится к системам телекоммуникаций и эфирным видеоинформационным системам вещания и может найти применение в декодерах устройств приема дискретной информации. Технический результат – снижение средней вычислительной сложности декодирования с сохранением качества декодирования принятого сигнала. Способ декодирования LDPC-кодов заключается в том, что для принятого кодового слова сигнала определяется отношение сигнал-шум, затем происходит переключение на оптимальный для данного значения отношения сигнал-шум алгоритм декодирования, после декодирования кодового слова происходит запись декодированного сигнала в общий массив декодированного сигнала. Алгоритм «распространения доверия» при значениях отношения сигнал-шум меньше 1,25 дБ, алгоритм «аппроксимация минимум-сумма» при значениях сигнал-шум в диапазоне [1,25, 1,8) дБ, алгоритм «минимум-сумма» при значениях сигнал-шум в диапазоне [1,8, 4,95) дБ, алгоритм «апостериорных вероятностей» при значениях отношения сигнал-шум в диапазоне [4,95, 11,5] дБ, алгоритм с инверсией бита - при значениях отношения сигнал-шум больше 11,5 дБ. 2 н. и 1 з.п. ф-лы, 1 ил.

 

Изобретение относится к системам телекоммуникаций и эфирным видеоинформационным системам вещания и может найти применение в декодерах устройств приема дискретной информации.

Известен способ для декодирования канала с использованием кода LDPC, включающий этапы, на которых демодулируют принятый сигнал, определяют позицию сокращенных информационных битов, декодируют демодулированный сигнал, принимая во внимание определенную позицию сокращенных информационных битов, причем позиция определяется исходя из числа информационных битов, которые должны быть сокращены, а также определяют число групп битов, которые должны быть сокращены на основе определенного числа информационных битов, которые должны быть сокращены, и получают предварительно определенный порядок групп битов (патент RU 2543553, МПК Н03М 11/00, опубл. 10.03.2015 г.).

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

Наиболее близким к предлагаемому способу является способ декодирования LDPC-кодов, включающий вычисление логарифмических отношений правдоподобия через вычисление отношения сигнал-шум (ОСШ) или оценки их вероятностей, причем определение соотношения сигнал-шум осуществляют для каждого принятого кодового слова сигнала, декодирование принятых кодовых слов сигнала производят на основе одного алгоритма, в том числе с применением алгоритма «распространения доверия» (АРД) или алгоритма «минимум-сумма» (АМС) с возможностью переключения между обработчиками проверочных узлов или информационных узлов в декодере (патент US 7484158, МПК G06F 11/00; Н03М 13/00, опубл. 15.09.2005 г. - прототип).

В известном способе предлагается использовать декодирование на основе алгоритма "распространения доверия" или алгоритма "минимум-сумма". Одновременное применение указанных алгоритмов в процессе декодирования не предусмотрено. Недостаток данного способа декодирования заключается в недостаточной вычислительной эффективности при изменении ОСШ.

Известно устройство декодирования LDPC-кодов, включающее блок декодирования на основе алгоритма "распространения доверия" (АРД) и блок декодирования на основе алгоритма "минимум-сумма" (АМС), выполненные с возможностью последовательного декодирования каждого кодового слова сигнала (патент US 8006161, МПК Н03М 13/00, опубл. 23.08.2011 г.).

В известном устройстве сначала производится обработка алгоритмом "распространения доверия", затем алгоритмом "минимум-сумма". Переключение между алгоритмами в зависимости от ОСШ не предусмотрено. Недостаток данного способа декодирования заключается в недостаточной вычислительной эффективности при изменении ОСШ.

Известно устройство декодирования LDPC-кодов, включающее блок вычисления логарифмического отношения правдоподобия через вычисление отношения сигнал-шум (ОСШ), соединенный выходом с блоком переключателя (коммутатором) для переключения обработчиков проверочных узлов или информационных узлов в декодере, блок вычисления алгоритма «распространения доверия» или блок вычисления алгоритма «минимум-сумма», обобщенный блок обработки узлов, объединяющий блок обновления информационных узлов и блок обновления проверочных узлов (патент US 7484158, МПК G06F 11/00; Н03М 13/00, опубл. 15.09.2005 г.).

В известном устройстве переключение между указанными алгоритмами декодирования не предусмотрено. Недостаток данного способа декодирования заключается в недостаточной вычислительной эффективности при изменении ОСШ.

Наиболее близким к предлагаемому устройству является устройство декодирования LDPC-кодов, включающее блок определения отношения сигнал-шум, соединенный выходом с коммутатором, блок вычисления алгоритма «распространения доверия», блок вычисления алгоритма «минимум-сумма», блок вычисления алгоритма «апостериорных вероятностей» и блок объединения результатов декодирования сигналов по разным алгоритмам, первый, второй и третий выходы коммутатора соединены соответственно с входами блока вычисления алгоритма «распространения доверия», блока вычисления алгоритма «минимум-сумма» и блока вычисления алгоритма «апостериорных вероятностей», выходы которых соединены соответственно с первым, вторым и третьим входами блока объединения результатов декодирования сигналов по разным алгоритмам, выход которого является выходом устройства, входом которого является вход блока определения отношения сигнал-шум, выполненного с возможностью задания диапазона значений отношения сигнал-шум соответственно для каждого блока вычисления алгоритма декодирования, причем алгоритм «распространения доверия» применяют при значениях отношения сигнал-шум меньше 1,8 дБ, алгоритм «минимум-сумма» - при значениях сигнал-шум в диапазоне от 1,8 до 4,95 дБ, алгоритм «апостериорных вероятностей» - при значениях отношения сигнал-шум больше 4,95 дБ (патент на полезную модель РФ №168191, МПК Н03М 13/11, опубл. 23.01.2017 г. - прототип).

В известном устройстве предусмотрено переключение только между тремя алгоритмами декодирования. Недостаток данного устройства декодирования заключается в недостаточной вычислительной эффективности при изменении ОСШ.

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

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

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

Предпочтительно алгоритм «распространения доверия» применить при значениях отношения сигнал-шум меньше 1,25 дБ, алгоритм «аппроксимация минимум-сумма» - при значениях сигнал-шум в диапазоне [1,25, 1,8) дБ, алгоритм «минимум-сумма» - при значениях сигнал-шум в диапазоне [1,8, 4,95) дБ, алгоритм «апостериорных вероятностей» - при значениях отношения сигнал-шум в диапазоне [4,95, 11,5] дБ, алгоритм с инверсией бита - при значениях отношения сигнал-шум больше 11,5 дБ.

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

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

Целесообразно алгоритм «распространения доверия» применить при значениях отношения сигнал-шум меньше 1,25 дБ, алгоритм «аппроксимация минимум-сумма» - при значениях сигнал-шум в диапазоне [1,25, 1,8) дБ, алгоритм «минимум-сумма» - при значениях сигнал-шум в диапазоне [1,8, 4,95) дБ, алгоритм «апостериорных вероятностей» - при значениях отношения сигнал-шум в диапазоне [4,95, 11,5] дБ, алгоритм с инверсией бита - при значениях отношения сигнал-шум больше 11,5 дБ.

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

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

На фиг. 1 изображена блок-схема предлагаемого устройства декодирования LDPC-кодов.

На фиг. 1 приняты следующие обозначения:

1 - блок определения отношения сигнал-шум;

2 - коммутатор;

3 - блок вычисления алгоритма «распространения доверия»;

4 - блок вычисления алгоритма «минимум-сумма»;

5 - блок вычисления алгоритма «апостериорных вероятностей»;

6 - блок вычисления алгоритма «аппроксимация минимум-сумма»;

7 - блок вычисления алгоритма с инверсией бита;

8 - блок объединения результатов декодирования сигналов по разным алгоритмам.

Устройство декодирования LDPC-кодов включает блок 1 определения отношения сигнал-шум, соединенный выходом с коммутатором 2, блок 3 вычисления алгоритма «распространения доверия», блок 4 вычисления алгоритма «минимум-сумма», блок 5 вычисления алгоритма «апостериорных вероятностей», блок 6 вычисления алгоритма «аппроксимация минимум-сумма», блок 7 вычисления алгоритма с инверсией бита и блок 8 объединения результатов декодирования сигналов по разным алгоритмам, причем первый, второй, третий, четвертый и пятый выходы коммутатора 2 соединены соответственно с входами блока 3 вычисления алгоритма «распространения доверия», блока 4 вычисления алгоритма «минимум-сумма», блока 5 вычисления алгоритма «апостериорных вероятностей», блока 6 вычисления алгоритма «аппроксимация минимум-сумма», блока 7 вычисления алгоритма с инверсией бита, выходы которых соединены соответственно с первым, вторым, третьим, четвертым и пятым входами блока 8 объединения результатов декодирования сигналов по разным алгоритмам, выход которого является выходом устройства, входом которого является вход блока 1 определения отношения сигнал-шум. Предпочтительно блок 1 определения отношения сигнал-шум выполнить с возможностью задания диапазона значений отношения сигнал-шум соответственно для каждого блока вычисления алгоритма декодирования. Блок 1 определения отношения сигнал-шум может быть реализован на основе различных алгоритмов определения отношения сигнал-шум на миникомпьютере Hardkernel Odroid XU4 с процессором ARM, 8 ядер. Язык реализации C/C++.

Целесообразно алгоритм «распространения доверия» применить при значениях отношения сигнал-шум меньше 1,25 дБ, алгоритм «аппроксимация минимум-сумма» - при значениях сигнал-шум в диапазоне [1,25, 1,8) дБ, алгоритм «минимум-сумма» - при значениях сигнал-шум в диапазоне [1,8, 4,95) дБ, алгоритм «апостериорных вероятностей» - при значениях отношения сигнал-шум в диапазоне [4,95, 11,5] дБ, алгоритм с инверсией бита - при значениях отношения сигнал-шум больше 11,5 дБ.

Предлагаемый способ применяют следующим образом. Для принятого кодового слова сигнала принимают информацию о значении отношения сигнал-шум. Далее в зависимости от полученного для принятого кодового слова значения ОСШ происходит переключение на оптимальный для данного значения отношения сигнал-шум алгоритм декодирования. Если значение ОСШ меньше 1,25 дБ, то обработка принятого кодового слова сигнала для декодирования LDPC-кода осуществляется алгоритмом «распространения доверия». В случае если значение ОСШ находится в диапазоне [1,25, 1,8) дБ, то обработка принятого кодового слова сигнала для декодирования LDPC-кода осуществляется алгоритмом «аппроксимация минимум-сумма». Если значение ОСШ находится в диапазоне [1,8, 4,95) дБ, то обработка принятого кодового слова сигнала для декодирования LDPC-кода осуществляется алгоритмом «минимум-сумма». В случае, если значение ОСШ находится в диапазоне [4,95, 11,5] дБ, то обработка принятого кодового слова сигнала для декодирования LDPC-кода осуществляется алгоритмом «апостериорных вероятностей». Если значение ОСШ больше 11,5 дБ, то обработка принятого кодового слова сигнала для декодирования LDPC-кода осуществляется алгоритмом с инверсией бита. После декодирования объединяют декодированные сигналы и добавляют их в общий массив декодированного сигнала.

Первым алгоритмом, используемым в предлагаемом способе декодирования LDPC-кода, является алгоритм "распространения доверия" (АРД) также известный под более общим названием - алгоритм "сумма-произведение" (АСП). В его основе лежит критерий максимума апостериорной вероятности, задачей которого является вычисление апостериорной вероятности того, что конкретный бит х_i в переданном кодовом слове х=[х₀,х₁,…x_N-1] равен единице, при принятом кодовом слове y=[y₀,y₁,…y_N-1].

,

тогда отношение правдоподобия (ОП, likelihood ratio, LR) для этого бита равно

,

или же в форме логарифмического отношения правдоподобия - ЛОП (log likelihood ratio)

.

Декодер инициализируется установкой всех исходящих из узла VNi сообщений L_i→j равными канальным ЛОП

для всех i и j, для которых h_ij=1. Здесь y_i обозначает принятое из канала значение для символа i.

Условие прекращения декодирования - равенство нулю синдрома

,

где кодовое слово - предположительный результат декодирования.

Таким образом, алгоритм АРД можно представить в виде следующих шагов:

1. Инициализация. В зависимости от используемой модели канала связи для всех узлов i инициализируют значения L_i по следующей формуле:

Затем для всех i и j, для которых h_ij=1, устанавливают L_i→j=L_i.

2. Обновление проверочных узлов. Для всех проверочных узлов CN вычисляют исходящие сообщения L_j→i

и передают их соответствующим информационным узлам VN.

3. Обновление битовых узлов. Вычисляют сообщения L_i→j, исходящие от информационных узлов VN

и передают их соответствующим проверочным узлам.

4. Вычисление апостериорных ЛОП. Для всех j=0, 1…,N-1 вычисляют

5. Получение жестких решений. Для всех i=0, 1…,N-1 находят жесткие решения

6. Проверка условия остановки. Вычисляют синдром . Если или число итераций достигло максимума, вычисления прекращаются, а считается результатом декодирования, в противном случае вычисления продолжаются с шага 2.

Данный алгоритм (АРД) очень хорошо справляется с декодированием сигналов даже при очень низком уровне отношения сигнал-шум (ОСШ). Однако имеет ряд недостатков. Самым существенным недостатком предложенного Галлагером алгоритма является высокая сложность его реализации.

Еще одним алгоритмом, используемым в предлагаемом способе декодирования LDPC-кода, является алгоритм "минимум-сумма" (АМС).

Обобщенная форма записи алгоритма минимальной суммы имеет вид:

1. Инициализация. Для всех узлов i инициализируют значения L_i по (1) в зависимости от используемой модели канала связи. Затем для всех i и j, для которых h_ij=1, устанавливают L_i→j=L_i.

2. Обновление проверочных узлов. Для всех проверочных узлов CN вычисляют исходящие сообщения L_j→i:

и передают их соответствующим информационным узлам VN.

3. Обновление битовых узлов. Вычисляют сообщения L_i→j, исходящие от информационных узлов VN

,

и передают их соответствующим проверочным узлам.

4. Вычисление апостериорных ЛОП. Для всех j=0, 1…,N-1 вычисляют

5. Получение жестких решений. Для всех i=0, 1…,N-1 находят жесткие решения

6. Проверка условия остановки. Вычисляют синдром . Если или число итераций достигло максимума, вычисления прекращаются, а считается результатом декодирования, в противном случае вычисления продолжаются с шага 2.

Достоинством алгоритма АМС является то, что значение исходящего сообщения для каждого информационного узла может быть вычислено нахождением всего двух минимальных значений достоверностей, входящих в проверку (что требует всего 1-log₂d_r-3 операций [Fossorier М., Mihaljevich М., Imai Н. Reduced complexity iterative decoding of low density parity check codes based on belief propagation, IEEE Transactions on Communications. - 1999, May. - Vol. 47. - №5. - pp. 673-680]), плюс вычисление его знака:

Второе несомненное достоинство заключается в том, что при использовании модели канала с АБГШ инициализация может осуществляться не канальными ЛОП, а принятыми из канала амплитудами соответствующих бит.

К недостаткам алгоритма (АМС) можно отнести низкую производительность при ОСШ меньше 1,5 дБ относительно алгоритма АРД, а также вычислительную неэффективность при ОСШ больше 5 дБ относительно алгоритма вычисления апостериорных вероятностей.

Еще одним алгоритмом, используемым в предлагаемом способе декодирования LDPC-кода, является алгоритм "аппроксимация минимум-сумма" (АМС*).

Алгоритм, называемый «аппроксимация минимум-сумма» (АМС*, approximate min* - a-min*) [T. Tian, C. Jones, J. Villasenor, R. Wesel. Construction of irregular LDPC codes with low error floors // 2003 IEEE International Conference on Communications. - 2003, May. - pp. 3125-3129], является комбинацией алгоритмов АРД и АМС, модификация касается алгоритма подсчета сообщений в проверочном узле. В общем виде для АРД эта операция имеет вид

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

Алгоритм АМС* использует ту же идеологию - в каждом проверочном узле рассчитывается всего два сообщения - одно для информационного узла, приславшего сообщение с минимальным весом, второе для всех остальных информационных узлов. Отличие заключается лишь в том, что вместо обычного минимума из двух аргументов используется оператор , в котором помимо операции поиска минимума используется еще и функция корректировки g(L₁, L₂).

В обобщенном виде этот алгоритм выглядит следующим образом.

1. Инициализация. Для всех узлов i инициализировать значения L_i по (8) в зависимости от используемой модели канала связи. Затем для всех i и j, для которых h_ij=1, устанавливается L_i→j=L_i.

2. Обновление проверочных узлов. Для всех проверочных узлов CN вычислить по формуле

исходящие сообщения:

• для узла с минимальной достоверностью

• для всех остальных

и передать их соответствующим информационным узлам VN.

3. Обновление битовых узлов. Вычислить сообщения L_i→j, исходящие от информационных узлов VN

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

4. Вычисление апостериорных ЛОП. Для всех j=0, 1 …, N-1 вычислить

.

5. Получение жестких решений. Для всех i=0, 1 …, N-1 найти жесткие решения

.

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

Подобная модификация позволяет снизить вычислительные затраты на вычисление сообщений из проверочного узла для АРД-подобных алгоритмов с 3(d_c-1) до (d_c-1) операции . По эффективности этот алгоритм занимает промежуточное место между АРД-подобными алгоритмами и алгоритмом АМС.

В алгоритме используется оператор , а значит, при реализации может быть использована любая его интерпретация. Видно, что алгоритм сводится к поиску всего двух отсылаемых сообщений вместо d_c. Вычисление этих двух сообщений займет всего d_c-1 арифметических операций. Правомерность применения такого упрощения можно пояснить, рассмотрев работу алгоритмов АРД и АМС. Если при декодировании проверочного узла два или более входящих в проверочный узел сообщений недостоверны, то недостоверными будут все сообщения, исходящие из этого узла. Это свойство сохраняется и при введении рассматриваемой модификации. Если всего одно входящее в проверочный узел сообщение не верно, то исходящее сообщение для недостоверного информационного узла будет достоверным для всех трех декодеров. Как видно из описания рассматриваемого упрощения, в обоих рассмотренных случаях сообщение, отправляемое к самому ненадежному информационному узлу, всегда будет в точности таким же, как и для алгоритма АРД.

Еще одним алгоритмом, используемым в предлагаемом способе декодирования LDPC-кода, является алгоритм вычисления апостериорных вероятностей (ААВ).

Алгоритм вычисления апостериорных вероятностей (алгоритм АВ, ААВ, aposteriory probability, АРР) получил свое название благодаря шагу обновления битовых узлов - если в других АРД-подобных алгоритмах на этом шаге вычислялось сообщение (сумма ЛОП - за исключением ЛОП исходящего из рассматриваемого узла), то в этом алгоритме сразу осуществляется расчет апостериорных вероятностей, именно они используются для дальнейших расчетов. Алгоритм АВ можно рассматривать как дальнейшее упрощение алгоритма АМС. Этот алгоритм отличается от алгоритма АМС шагом обновления битовых узлов. Здесь вычисляется только одно исходящее сообщение от битового узла i, вместо d_c (L_i вместо L_i→j), как это было во всех алгоритмах, основанных на алгоритме АСП. Выражение для подсчета исходящих из информационного узла сообщений имеет вид

Обобщенная форма записи алгоритма имеет вид:

1. Инициализация. В зависимости от используемой модели канала связи для всех узлов i инициализируют значения L_i по формуле

Затем для всех i и j, для которых h_ij=1, устанавливают L_i→j=L_i.

2. Обновление проверочных узлов. Для всех проверочных узлов CN вычисляют исходящие сообщения L_j→i

и передают их соответствующим информационным узлам VN.

3. Обновление битовых узлов. Вычисляют сообщения L_i→j, исходящие от информационных узлов VN:

и передают их соответствующим проверочным узлам.

4. Получение жестких решений. Для всех i=0, 1…,N-1 находят жесткие решения

.

5. Проверка условия остановки. Вычисляют синдром . Если или число итераций достигло максимума, вычисления прекращаются, а считается результатом декодирования, в противном случае вычисления продолжаются с шага 2.

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

Еще одним алгоритмом, используемым в предлагаемом способе декодирования LDPC-кода, является алгоритм с инверсией бита (АИБ).

Алгоритм с инверсией бита (алгоритм ИБ, АИБ) был предложен Галлагером в [Gallager R.G. Low-density parity-check codes // Cambridge, MA: M.I.T. Press. - 1963]. В АИБ сначала вычисляются все проверочные уравнения в матрице Н, а затем инвертируются те биты в полученном кодовом слове, которые участвуют более чем в некотором заданном числе t невыполненных проверок. Этот шаг повторяется с измененным принятым кодовым словом, пока все проверки на четность не будут выполнены или пока не будет достигнуто некоторое максимальное число итераций.

На невыполненные проверочные уравнения указывают элементы синдрома s=yH^T, а их число для каждого кодового бита можно найти, используя следующее выражение:

f=sH,

причем умножения матриц выполняется над целыми числами, а не над двоичными. Вектор f называют профилем достоверности, а его элементы ƒ_j являются ни чем иным, как достоверностями приема соответствующих бит, причем достоверность тем меньше, чем больше значение ƒ_j. При этом диапазон значений ƒ_j лежит в пределах [0,d_c], и очевидно, что чем больше вес проверок для каждого из бит, тем более точно можно определить достоверность их приема.

Порог t - расчетная величина, которая должна быть выбрана таким образом, чтобы максимизировать эффективность декодирования при минимизации вычислительных затрат, и зависит от вероятности перехода в канале, а также d_c и d_r. В [Gallager R.G. Low-density parity-check codes // Cambridge, MA: M.I.T. Press. - 1963], приводится правило выбора оптимального порога для регулярных LDPC кодов при заданной вероятности перехода в канале. Рассчитывать порог в условиях изменяющихся характеристик канала не всегда оправдано, однако существует удобный, хотя и не оптимальный способ выбора порога, эффективно адаптирующегося к изменению качества канала. Суть его сводится к тому, что инвертируются те биты, для которых число невыполненных проверок максимально, при этом возможны модификации с инверсией только одного бита или нескольких бит за итерацию. Заметим, что при принятых обозначениях невыполненной проверке соответствует отрицательная достоверность. Следовательно, инвертировать следует биты, имеющие минимальное значение достоверности.

Алгоритм ИБ можно представить в обобщенном виде следующим образом:

1. Инициализация. Для всех узлов i инициализировать значения α_i жесткими оценками принятых бит.

2. Обновление проверочных узлов. Для всех проверочных узлов CN вычислить исходящие сообщения L_j→i

и передать их соответствующим информационным узлам VN.

3. Обновление битовых узлов. Вычислить сообщения L_i→j, исходящие от информационных узлов VN

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

4. Получение окончательных решений. Для всех i=0, 1 …, N-1 найти жесткие решения

5. Проверка правильности декодирования. Вычислить синдром . Если или число итераций достигло максимума, вычисления прекращаются, а считается результатом декодирования, в противном случае вычисления продолжаются с шага 2.

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

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

Для принятого кодового слова сигнала в блоке 1 определения отношения сигнал-шум принимается информация о значении отношения сигнал-шум (ОСШ). Далее в зависимости от полученного для принятого кодового слова значения ОСШ происходит переключение на оптимальный для данного значения отношения сигнал-шум алгоритм декодирования. Если значение ОСШ меньше 1,25 дБ, то обработка принятого кодового слова сигнала для декодирования LDPC-кода осуществляется блоком 3 вычисления алгоритма «распространения доверия». В случае, если значение ОСШ находится в диапазоне [1,25, 1,8) дБ, то обработка принятого кодового слова сигнала для декодирования LDPC-кода осуществляется блоком 6 вычисления алгоритма «аппроксимация минимум-сумма». Если значение ОСШ находится в диапазоне [1,8, 4,95) дБ, то обработка принятого кодового слова сигнала для декодирования LDPC-кода осуществляется блоком 4 вычисления алгоритма «минимум-сумма». В случае если значение ОСШ находится в диапазоне [4,95, 11,5] дБ, то обработка принятого кодового слова сигнала для декодирования LDPC-кода осуществляется блоком 5 вычисления алгоритма «апостериорных вероятностей». Если значение ОСШ больше 11,5 дБ, то обработка принятого кодового слова сигнала для декодирования LDPC-кода осуществляется блоком 7 вычисления алгоритма с инверсией бита. После декодирования блок 8 объединения декодированного сигнала принимает информацию с задействованного блока декодирования сигнала и добавляет ее в общий массив декодированного сигнала.

Устройство просто и может быть реализовано на миникомпьютере Hardkernel Odroid XU4 с процессором ARM, 8 ядер. Язык реализации C/C++, возможно использование технологии openCL.

Предлагаемый способ оперативен, точен и позволяет снизить затраты на декодирование в 4,13-7,93 раза в зависимости от используемой структуры декодера по сравнению с использованием только алгоритма АРД и в 2,61 раз по сравнению с использованием только алгоритма АМС. По сравнению с прототипом предлагаемое устройство позволяет снизить затраты на декодирование в 1,2-1,6 раза в зависимости от применяемого кода.

1. Способ декодирования LDPC-кодов, включающий определение отношения сигнал-шум для каждого принятого кодового слова сигнала и декодирование принятых кодовых слов сигнала на основе алгоритма «распространения доверия» и «на основе алгоритма «минимум-сумма», отличающийся тем, что введено декодирование на основе алгоритма «апостериорных вероятностей», а также на основе алгоритма «аппроксимация минимум-сумма» и алгоритма с инверсией бита, для каждого алгоритма устанавливают диапазон значений сигнал-шум, причем осуществляют переключение алгоритмов в зависимости от значения отношения сигнал-шум для каждого слова с последующим последовательным объединением результатов декодирования сигналов по разным алгоритмам, при этом алгоритм «распространения доверия» применяют при значениях отношения сигнал-шум меньше 1,25 дБ, алгоритм «аппроксимация минимум-сумма» при значениях сигнал-шум в диапазоне [1,25, 1,8) дБ, алгоритм «минимум-сумма» при значениях сигнал-шум в диапазоне [1,8, 4,95) дБ, алгоритм «апостериорных вероятностей» при значениях отношения сигнал-шум в диапазоне [4,95, 11,5] дБ, алгоритм с инверсией бита - при значениях отношения сигнал-шум больше 11,5 дБ.

2. Устройство декодирования LDPC-кодов, включающее блок определения отношения сигнал-шум, соединенный выходом с коммутатором, блок вычисления алгоритма «распространения доверия», блок вычисления алгоритма «минимум-сумма», блок вычисления алгоритма «апостериорных вероятностей» и блок объединения результатов декодирования сигналов по разным алгоритмам, первый, второй и третий выходы коммутатора соединены соответственно с входами блока вычисления алгоритма «распространения доверия», блока вычисления алгоритма «минимум-сумма» и блока вычисления алгоритма «апостериорных вероятностей», выходы которых соединены соответственно с первым, вторым и третьим входами блока объединения результатов декодирования сигналов по разным алгоритмам, выход которого является выходом устройства, входом которого является вход блока определения отношения сигнал-шум, отличающееся тем, что введены блок вычисления алгоритма «аппроксимация минимум-сумма» и блок вычисления алгоритма с инверсией бита, причем четвертый и пятый выходы коммутатора соединены соответственно с входами блока вычисления алгоритма «аппроксимация минимум-сумма» и блока вычисления алгоритма с инверсией бита, выходы которых соединены соответственно с четвертым и пятым входами блока объединения результатов декодирования сигналов по разным алгоритмам, при этом алгоритм «распространения доверия» применяют при значениях отношения сигнал-шум меньше 1,25 дБ, алгоритм «аппроксимация минимум-сумма» при значениях сигнал-шум в диапазоне [1,25, 1,8) дБ, алгоритм «минимум-сумма» при значениях сигнал-шум в диапазоне [1,8, 4,95) дБ, алгоритм «апостериорных вероятностей» при значениях отношения сигнал-шум в диапазоне [4,95, 11,5] дБ, алгоритм с инверсией бита - при значениях отношения сигнал-шум больше 11,5 дБ.

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