УСТРОЙСТВО ДЕКОДИРОВАНИЯ LDPC-КОДОВ
DEVICE FOR DECODING LDPC CODES

Изобретение относится к системам телекоммуникаций и вычислительной техники и может найти применение в устройствах приема информации из канала передачи или воспроизведения информации с высоким уровнем ошибок.
7
Известно устройство декодирования LDPC-кодов (см. патент 7181676 США. МПК H03M 13/45. Layered decoding approach for low density parity check (LDPC) codes / Dale E. Hocevar - заявлено 11.02.2005 №11/056755; опубл. 20.02.2007), содержащее: память с произвольным доступом, сумматоры, блоки обновления проверок, блоки обновления символов, блок прямых перестановок, блок обратных перестановок.
Известное устройство реализует алгоритм итеративного декодирования по слоям, что позволяет улучшить сходимость алгоритма.
Недостаток устройства - относительно высокая вычислительная сложность используемого алгоритма, что ограничивает его применение.
7
Наиболее близким по технической сущности к заявляемому изобретению является выбранное в качестве прототипа устройство декодирования LDPC-кодов (см. патент 2005/0283707 США. МПК H03M 13/00. LDPC decoder for decoding a low-density parity check (LDPC) codewords / Eran Sharon, Simon Litsyn - заявлено 18.02.2005 №11/061232; опубл. 22.12.2005), содержащее: два блока памяти с произвольным доступом, процессоры проверочных нод, схему коммутации, постоянное запоминающее устройство, хранящее структуру графа, блок проверки сходимости.
Устройство-прототип выполняет процедуру последовательного декодирования LDPC-кодов, исправляющую большее число ошибок.
Недостатком прототипа можно считать относительно большую вычислительную сложность алгоритма декодирования.
Технической задачей изобретения является уменьшение вычислительной сложности используемого алгоритма декодирования, обеспечивающее меньшие аппаратные затраты и более высокую пропускную способность декодера.
Поставленная техническая задача решается тем, что в устройство декодирования LDPC-кодов, содержащее первый и второй блоки памяти, согласно изобретению введены третий блок памяти, арифметическое устройство, первый и второй стеки, первый-пятый счетчики, первый регистр-защелка, T-триггер, первый-шестой коммутаторы, схема сравнения кодов, первый и второй элементы И, первый сумматор, причем вторые входы шестого коммутатора являются входами устройства декодирования LDPC-кодов, выходы шестого коммутатора соединены с входами данных первого блока памяти, выходы первого блока памяти соединены с входами данных первого стека, с первыми входами данных арифметического устройства и вторыми входами схемы сравнения кодов, выходы первого стека соединены со вторыми входами данных арифметического устройства, выходы арифметического устройства соединены с первыми входами шестого коммутатора и третьими входами устройства управления, первый выход схемы сравнения кодов соединен с первым входом первого логического элемента И, второй выход схемы сравнения кодов соединен с первым входом второго логического элемента И, выход первого логического элемента И соединен со входом декремента пятого счетчика и T-входом T-триггера, выход второго логического элемента И соединен со входами записи первого и второго стеков и первым входом управления арифметического устройства, выходы пятого счетчика соединены с младшими разрядами первых входов первого коммутатора и первыми входами устройства управления, выход T-триггера соединен со старшим разрядом первых входов первого коммутатора, третьим входом управления арифметического устройства и вторым входом устройства управления, выходы первого коммутатора соединены с входами данных второго блока памяти, младшие разряды выходов второго блока памяти соединены с входами данных пятого счетчика, старший разряд выходов второго блока памяти соединен с входом данных T-триггера, выходы второго стека соединены со вторыми входами второго коммутатора и вторыми входами пятого коммутатора, выходы второго коммутатора соединены с входами данных третьего блока памяти, выходы третьего блока памяти соединены с входами данных первого регистра-защелки, выходы первого регистра-защелки соединены с входами данных второго стека и третьими входами пятого коммутатора, выходы пятого коммутатора соединены с адресными входами первого блока памяти, выходы первого счетчика соединены со вторыми входами третьего коммутатора, выходы второго счетчика соединены с первыми входами третьего коммутатора, выходы третьего счетчика соединены со вторыми входами четвертого коммутатора, выходы четвертого счетчика соединены с третьими входами четвертого коммутатора и вторыми входами первого сумматора, выходы третьего коммутатора соединены с адресными входами второго блока памяти, выходы четвертого коммутатора соединены с адресными входами третьего блока памяти, выходы первого сумматора соединены с входами данных четвертого счетчика, первые выходы устройства управления соединены с первыми входами схемы сравнения кодов, второй выход устройства управления соединен с входами чтения первого и второго стеков и вторым входом управления арифметического устройства, третий выход устройства управления соединен со вторыми входами первого и второго логических элементов И, четвертые выходы устройства управления соединены со вторыми входами первого коммутатора, пятый выход устройства управления соединен с входом управления первого коммутатора, шестой выход устройства управления соединен с входом сброса пятого счетчика, седьмые выходы устройства управления соединены с третьими входами третьего коммутатора, восьмые выходы устройства управления соединены с третьими входами шестого коммутатора, девятые выходы устройства управления соединены с четвертыми входами шестого коммутатора, десятый выход устройства управления соединен с входом сброса первого счетчика, одиннадцатые выходы устройства управления соединены с входами управления шестого коммутатора, двенадцатый выход устройства управления соединен с входом инкремента первого счетчика, тринадцатые выходы устройства управления соединены с входами управления третьего коммутатора, четырнадцатый выход устройства управления соединен с входом сброса второго счетчика, пятнадцатый выход устройства управления соединен с входом записи второго блока памяти, шестнадцатый выход устройства управления соединен с входом инкремента второго счетчика, семнадцатый выход устройства управления соединен с входом записи первого блока памяти, восемнадцатые выходы устройства управления соединены с первыми входами первого сумматора, девятнадцатый выход устройства управления соединен с входом загрузки четвертого счетчика, двадцатый выход устройства управления соединен с входом сброса четвертого счетчика, двадцать первый выход устройства управления соединен с входом инкремента третьего счетчика, двадцать второй выход устройства управления соединен с входом сброса третьего счетчика, двадцать третьи выходы устройства управления соединены с первыми входами четвертого коммутатора, двадцать четвертые выходы устройства управления соединены с входами управления четвертого коммутатора, двадцать пятые выходы устройства управления соединены с входами управления пятого коммутатора, двадцать шестые выходы устройства управления соединены с первыми входами пятого коммутатора, двадцать седьмой выход устройства управления соединен с входом управления второго коммутатора, двадцать восьмые выходы устройства управления соединены с первыми входами второго коммутатора, двадцать девятый выход устройства управления соединен с входом записи третьего блока памяти, тридцатый выход устройства управления соединен с входом загрузки первого регистра-защелки, тридцать первый выход устройства управления соединен с входами загрузок пятого счетчика и T-триггера, тридцать второй выход устройства управления соединен с входом сброса арифметического устройства, старший (знаковый) разряд выходов первого блока памяти является выходом устройства декодирования LDPC-кодов, причем арифметическое устройство содержит третий стек, первый и второй блоки вычисления функции g, шестой счетчик, второй регистр-защелку, первый и второй D-триггера, седьмой-девятый коммутаторы, второй сумматор, дешифратор, первый и второй элементы ИЛИ, третий-шестой элементы И, схему инверсии знака, причем первые входы седьмого коммутатора являются первыми входами данных арифметического устройства, вторые входы седьмого коммутатора соединены со вторыми входами второго сумматора и являются вторыми входами данных арифметического устройства, выходы седьмого коммутатора соединены со вторыми входами первого блока вычисления функции g и вторыми входами восьмого коммутатора, выходы первого блока вычисления функции g соединены с первыми входами восьмого коммутатора, выходы восьмого коммутатора соединены с входами данных второго регистра-защелки, выходы второго регистра-защелки соединены с первыми входами первого блока вычисления функции g, первыми входами второго блока вычисления функции g, первыми входами девятого мультиплексора и входами данных третьего стека, выходы второго блока вычисления функции g соединены со вторыми входами девятого коммутатора, выходы девятого коммутатора соединены с входами схемы инверсии знака, выходы схемы инверсии знака соединены с первыми входами второго сумматора, выходы третьего стека соединены со вторыми входами второго блока вычисления функции g и третьими входами девятого коммутатора, вход управления схемы инверсии знака является третьим входом управления арифметического устройства, вход инкремента шестого счетчика соединен с D-входом второго D-триггера, первым входом второго логического элемента ИЛИ, первым входом третьего логического элемента И и является первым входом управления арифметического устройства, вход декремента шестого счетчика соединен с D-входом первого D-триггера, вторым входом второго логического элемента ИЛИ, первым входом шестого логического элемента И, вторым входом четвертого логического элемента И, вторым входом пятого логического элемента И, входом управления седьмого коммутатора, входом чтения третьего стека и является вторым входом управления арифметического устройства, вход сброса второго регистра-защелки соединен с входом сброса шестого счетчика, входом сброса первого D-триггера, входом сброса второго D-триггера и является входом сброса арифметического устройства, выходы шестого счетчика соединены с входами дешифратора, первый выход дешифратора соединен с вторым входом третьего логического элемента И, второй выход дешифратора соединен с первым входом четвертого логического элемента И, выход третьего логического элемента И соединен с первым входом первого логического элемента ИЛИ, выход первого логического элемента ИЛИ соединен со входом управления восьмого коммутатора, выход второго логического элемента ИЛИ соединен с входом загрузки второго регистра-защелки, выход первого D-триггера соединен со вторым входом шестого логического элемента И, выход второго D-триггера соединен с первым входом пятого логического элемента И, выход пятого логического элемента И соединен со входом записи третьего стека, выход четвертого логического элемента И соединен со первым входом управления девятого коммутатора, выход шестого логического элемента И соединен со вторым входом управления девятого коммутатора и вторым входом первого логического элемента ИЛИ, выходы второго сумматора являются выходами арифметического устройства.
Взаимодействие введенных функциональных блоков обеспечивает последовательное уточнение оценок символов слов LDPC-кода с одновременным упрощением проверочных уравнений.
Сущность изобретения состоит в том, что для уменьшения вычислительной сложности используемого итеративного алгоритма декодирования на каждой его итерации из проверочных уравнений LDPC-кода исключаются символы кодового слова, надежность которых выше заданного порога. Проверочные уравнения в процессе декодирования упрощаются и вырождаются. Вычислительная сложность каждой последующей итерации уменьшается.
На фиг.1 приведена функциональная схема предлагаемого устройства декодирования LDPC-кодов; на фиг.2 - функциональная схема арифметического устройства; на фиг.3 - функциональная схема стека.
В описании устройства и на чертежах используются следующие обозначения:
АУ - арифметическое устройство;
ПУ - проверочное уравнение;
УУ - устройство управления;
Cnt - счетчик;
Mux - коммутатор (мультиплексор);
DC - дешифратор;
LLR - Log likelihood ratio (логарифмическое отношение правдоподобия);
RAM - память с произвольным доступом;
Rg - регистр;
1
7
y-y - управляющие сигналы;
n - количество символов в кодовом слове LDPC-кода;
r - число проверочных уравнений в LDPC-коде.
Устройство декодирования LDPC-кодов (фиг.1) содержит устройство управления 1, первый-третий блоки памяти 2-4; арифметическое устройство 5; первый и второй стеки 6, 7; первый-пятый счетчики 8-10, 11.1, 12; первый регистр-защелку 13; T-триггер 14; первый-шестой коммутаторы 15-20; схему сравнения кодов 21; первый и второй элементы И 22, 23, первый сумматор 11.2.
Вторые входы шестого коммутатора 20 являются входами устройства декодирования LDPC-кодов, на которые подаются входные данные (DIn).
Выходы шестого коммутатора 20 соединены с входами данных первого блока памяти 2. Выходы первого блока памяти 2 соединены с входами данных первого стека 6, с первыми входами данных арифметического устройства 5 и вторыми входами схемы сравнения кодов 21. Выходы первого стека 6 соединены со вторыми входами данных арифметического устройства 5. Выходы арифметического устройства 5 соединены с первыми входами шестого коммутатора 20 и третьими входами устройства управления 1. Первый выход схемы сравнения кодов 21 соединен с первым входом первого логического элемента И 22. Второй выход схемы сравнения кодов 21 соединен с первым входом второго логического элемента И 23. Выход первого логического элемента И 22 соединен со входом декремента пятого счетчика 12 и T-входом T-триггера 14. Выход второго логического элемента И 23 соединен со входами записи первого и второго стеков 6 и 7 и первым входом управления арифметического устройства 5. Выходы пятого счетчика 12 соединены с младшими разрядами первых входов первого коммутатора 15 и первыми входами устройства управления 1. Выход T-триггера 14 соединен со старшим разрядом первых входов первого коммутатора 15, третьим входом управления арифметического устройства 5 и вторым входом устройства управления 1. Выходы первого коммутатора 15 соединены с входами данных второго блока памяти 3. Младшие разряды выходов второго блока памяти 3 соединены с входами данных пятого счетчика 12. Старший разряд выходов второго блока памяти 3 соединен с входом данных T-триггера 14. Выходы второго стека 7 соединены со вторыми входами второго коммутатора 16 и вторыми входами пятого коммутатора 19. Выходы второго коммутатора 16 соединены с входами данных третьего блока памяти 4. Выходы третьего блока памяти 4 соединены с входами данных первого регистра-защелки 13. Выходы первого регистра-защелки 13 соединены с входами данных второго стека 7 и третьими входами пятого коммутатора 19. Выходы пятого коммутатора 19 соединены с адресными входами первого блока памяти 2. Выходы первого счетчика 8 соединены со вторыми входами третьего коммутатора 17. Выходы второго счетчика 9 соединены со первыми входами третьего коммутатора 17. Выходы третьего счетчика 10 соединены со вторыми входами четвертого коммутатора 18. Выходы четвертого счетчика 11.1 соединены с третьими входами четвертого коммутатора 18 и вторыми входами первого сумматора 11.2. Выходы третьего коммутатора 17 соединены с адресными входами второго блока памяти 3. Выходы четвертого коммутатора 18 соединены с адресными входами третьего блока памяти 4. Выходы первого сумматора 11.2 соединены с входами данных четвертого счетчика 11.1.
Первые выходы устройства управления 1 соединены с первыми входами схемы сравнения кодов 21. Второй выход устройства управления 1 соединен с входами чтения первого и второго стеков 6 и 7 и вторым входом управления арифметического устройства 5. Третий выход устройства управления 1 соединен со вторыми входами логических элементов И 22 и 23. Четвертые выходы устройства управления 1 соединены со вторыми входами первого коммутатора 15. Пятый выход устройства управления 1 соединен с входом управления первого коммутатора 15. Шестой выход устройства управления 1 соединен с входом сброса пятого счетчика 12. Седьмые выходы устройства управления 1 соединены с третьими входами третьего коммутатора 17. Восьмые выходы устройства управления 1 соединены с третьими входами шестого коммутатора 20. Девятые выходы устройства управления 1 соединены с четвертыми входами шестого коммутатора 20. Десятый выход устройства управления 1 соединен с входом сброса первого счетчика 8. Одиннадцатые выходы устройства управления 1 соединены с входами управления шестого коммутатора 20. Двенадцатый выход устройства управления 1 соединен с входом инкремента первого счетчика 8. Тринадцатые выходы устройства управления 1 соединены с входами управления третьего коммутатора 17. Четырнадцатый выход устройства управления 1 соединен с входом сброса второго счетчика 9. Пятнадцатый выход устройства управления 1 соединен с входом записи второго блока памяти 3. Шестнадцатый выход устройства управления 1 соединен с входом инкремента второго счетчика 9. Семнадцатый выход устройства управления 1 соединен с входом записи первого блока памяти 2. Восемнадцатые выходы устройства управления 1 соединены с первыми входами первого сумматора 11.2. Девятнадцатый выход устройства управления 1 соединен с входом загрузки четвертого счетчика 11.1. Двадцатый выход устройства управления 1 соединен с входом сброса четвертого счетчика 11.1. Двадцать первый выход устройства управления 1 соединен с входом инкремента третьего счетчика 10. Двадцать второй выход устройства управления 1 соединен с входом сброса третьего счетчика 10. Двадцать третьи выходы устройства управления 1 соединены с первыми входами четвертого коммутатора 18. Двадцать четвертые выходы устройства управления 1 соединены с входами управления четвертого коммутатора 18. Двадцать пятые выходы устройства управления 1 соединены с входами управления пятого коммутатора 19. Двадцать шестые выходы устройства управления 1 соединены с первыми входами пятого коммутатора 19. Двадцать седьмой выход устройства управления 1 соединен с входом управления второго коммутатора 16. Двадцать восьмые выходы устройства управления 1 соединены с первыми входами второго коммутатора 16. Двадцать девятый выход устройства управления 1 соединен с входом записи третьего блока памяти 4. Тридцатый выход устройства управления 1 соединен с входом загрузки первого регистра-защелки 13. Тридцать первый выход устройства управления 1 соединен с входами загрузок пятого счетчика 12 и T-триггера 14. Тридцать второй выход устройства управления 1 соединен с входом сброса арифметического устройства 5.
Старший (знаковый) разряд выходов первого блока памяти 2 является выходом устройства декодирования LDPC-кодов (DOut).
Все триггеры, регистры, счетчики, используемые в устройстве декодирования LDPC-кодов, меняют свое состояние по окончанию тактового интервала в зависимости от управляющих сигналов. Тактовый сигнал на фигурах изобретения не показан, но его наличие подразумевается.
Первый блок памяти 2 имеет емкость в 2n слов, каждое из которых содержит LLR одного символа кодового слова (n - длина кодового слова LDPC-кода).
Второй блок памяти 3 имеет емкость в r слов, каждое из которых содержит описание одного проверочного уравнения по четности LDPC-кода (r - число проверочных уравнений в LDPC-коде). Старший разряд слова описания содержит признак четности, который определяет разновидность проверочного уравнения. Если признак нулевой, осуществляется проверка по четности, если единичный - по нечетности. Остальные разряды слова описания содержат количество членов проверочного уравнения.
Третий блок памяти 4 содержит номера символов кодового слова, входящих в проверочные уравнения. Номера символов одного проверочного уравнения хранятся в соседних словах, количество которых определяется описанием проверочного уравнения. Общее число слов третьего блока памяти 4 равняется суммарному числу единиц в проверочной матрице H LDPC-кода.
При подаче логической единицы на первый вход управления девятого коммутатора 33 на его выходы передается содержимое его третьих входов. При подаче логической единицы на второй вход управления девятого коммутатора 33 на его выходы передается содержимое его первых входов. При подаче логических нулей на входы управления девятого коммутатора 33 на его выходы передается содержимое его вторых входов.
Схема сравнения кодов 21 сравнивает значение LLR символа, подаваемое на его вторые входы, со значением порога Thres, подаваемого на его первые входы. Причем сначала находится модуль LLR. Если этот модуль больше порога или равен ему, на первом выходе схемы формируется логическая единица, в противном случае - логический ноль. На втором выходе схемы формируется сигнал инверсный к сигналу на первом выходе.
Арифметическое устройство (фиг.2) содержит третий стек 24; первый и второй блоки вычисления функции g 25, 26; шестой счетчик 27; второй регистр-защелку 28; первый и второй D-триггера 29. 30; седьмой-девятый коммутаторы 31-33; второй сумматор 34; дешифратор 35; первый и второй элементы ИЛИ 36, 37, третий-шестой элементы И 38-41, схему инверсии знака 42.
Первые входы седьмого коммутатора 31 являются первыми входами данных арифметического устройства 5 (DI1). Вторые входы седьмого коммутатора 31 соединены со вторыми входами второго сумматора 34 и являются вторыми входами данных арифметического устройства 5 (DI2). Выходы седьмого коммутатора 31 соединены со вторыми входами первого блока вычисления функции g 25 и вторыми входами восьмого коммутатора 32. Выходы первого блока вычисления функции g 25 соединены с первыми входами восьмого коммутатора 32. Выходы восьмого коммутатора 32 соединены с входами данных второго регистра-защелки 28. Выходы второго регистра-защелки 28 соединены с первыми входами первого блока вычисления функции g 25, первыми входами второго блока вычисления функции g 26, первыми входами девятого мультиплексора 33 и входами данных третьего стека 24. Выходы второго блока вычисления функции g 26 соединены со вторыми входами девятого коммутатора 33. Выходы девятого коммутатора 33 соединены с входами схемы инверсии знака 42. Выходы схемы инверсии знака 42 соединены с первыми входами второго сумматора 34. Выходы третьего стека 24 соединены со вторыми входами второго блока вычисления функции g 26 и третьими входами девятого коммутатора 33.
Вход управления схемы инверсии знака 42 является третьим входом управления арифметического устройства 5 (Par).
Вход инкремента шестого счетчика 27 соединен с D-входом второго D-триггера 30, первым входом второго логического элемента ИЛИ 37, первым входом третьего логического элемента И 38, и является первым входом управления арифметического устройства 5 (Forward).
Вход декремента шестого счетчика 27 соединен с D-входом первого D-триггера 29, вторым входом второго логического элемента ИЛИ 37, первым входом шестого логического элемента И 41, вторым входом четвертого логического элемента И 39, вторым входом пятого логического элемента И 40, входом управления седьмого коммутатора 31, входом чтения третьего стека 24 и является вторым входом управления арифметического устройства 5 (Backward).
Вход сброса второго регистра-защелки 28 соединен с входом сброса шестого счетчика 27, входом сброса первого D-триггера 29, входом сброса второго D-триггера 30 и является входом сброса арифметического устройства 5 (Reset).
Выходы шестого счетчика 27 соединены с входами дешифратора 35. Первый выход дешифратора 35 соединен с вторым входом третьего логического элемента И 38. Второй выход дешифратора 35 соединен с первым входом четвертого логического элемента И 39. Выход третьего логического элемента И 38 соединен с первым входом первого логического элемента ИЛИ 36. Выход первого логического элемента ИЛИ 36 соединен со входом управления восьмого коммутатора 32. Выход второго логического элемента ИЛИ 37 соединен с входом загрузки второго регистра-защелки 28. Выход первого D-триггера 29 соединен со вторым входом шестого логического элемента И 41. Выход второго D-триггера 30 соединен с первым входом пятого логического элемента И 40. Выход пятого логического элемента И 40 соединен со входом записи третьего стека 24. Выход четвертого логического элемента И 39 соединен со первым входом управления девятого коммутатора 33. Выход шестого логического элемента И 41 соединен со вторым входом управления девятого коммутатора 33 и вторым входом первого логического элемента ИЛИ 36.
Выходы второго сумматора 34 являются выходами арифметического устройства 5 (DO).
Вторые входы пятого и шестого логических элементов И 40 и 41 являются инверсными.
Коммутаторы, используемые в арифметическом устройстве 5, работают следующим образом.
При подаче логической единицы на вход управления седьмого коммутатора 31 на его выходы передается содержимое его вторых входов. При подаче логического нуля на вход управления седьмого коммутатора 31 на его выходы передается содержимое его первых входов.
При подаче логической единицы на вход управления восьмого коммутатора 32 на его выходы передается содержимое его вторых входов. При подаче логического нуля на вход управления восьмого коммутатора 32 на его выходы передается содержимое его первых входов.
При подаче логической единицы на первый вход управления девятого коммутатора 33 на его выходы передается содержимое его третьих входов. При подаче логической единицы на второй вход управления девятого коммутатора 33 на его выходы передается содержимое его первых входов. При подаче логических нулей на входы управления девятого коммутатора 33 на его выходы передается содержимое его вторых входов.
Блоки вычисления функции g 25, 26 (выражение для функции приведено ниже в виде формулы (2)) могут быть реализованы известным способом с использованием таблиц (LUT).
Стек (фиг.3) содержит десятый - (x+9)-ой коммутаторы 43.1-43.x; третий - (x+2)-ой регистры-защелки 44.1-44.x; третий элемент ИЛИ 45, здесь x обозначает глубину стека (максимальное число хранимых в стеке слов).
По схеме, изображенной на фиг.3, реализованы все стеки, используемые в устройстве декодирования LDPC-кодов, (первый стек 6, второй стек 7, третий стек 24). Они отличаются только глубиной (параметр x) и количеством разрядов в запоминаемых словах.
Первые входы десятого коммутатора 43.1 являются входами данных стека (DI).
Выходы десятого коммутатора 43.1 соединены с входами данных третьего регистра-защелки 44.1. Выходы третьего регистра-защелки 44.1 соединены со первыми входами одиннадцатого коммутатора 43.2 и являются выходами стека (DO). Выходы (x+9)-го коммутатора 43.x соединены с входами данных (x+2)-го регистра-защелки 44.x. Выходы (x+2)-го регистра-защелки 44.x соединены со вторыми входами (x+8)-го коммутатора 43.x-1. На вторые входы (x+9)-го коммутатора 43.x подается константа - нулевое слово.
Для значений i (i=2, … x-1): выходы (i+9)-го коммутатора 43.i соединены с входами данных (i+2)-го регистра-защелки 44.i; выходы (i+2)-го регистра-защелки 44.i соединены с первыми входами (i+10)-го коммутатора 43.i+1; и со вторыми входами (i+8)-го коммутатора 43.i-1.
Первый вход логического элемента ИЛИ 45 является входом чтения стека (R). Второй вход логического элемента ИЛИ 45 соединен со входами управления десятого - (x+9)-го коммутаторов 43.1-43.x и является входом записи стека (W). Выход логического элемента ИЛИ 45 соединен со входами загрузок третьего - (x+2)-го регистров-защелок 44.1-44.x.
Стек работает следующим образом.
При подаче на вход записи стека (W) логической единицы на выходы всех коммутаторов 43.1-43.x передаются слова с их первых входов, при этом входы данных каждого следующего регистра-защелки логически подключаются к выходам предыдущих регистров-защелок (образуя сдвиговый регистр на x слов, реализующий сдвиг вниз), на вход регистра-защелки 44.1 подаются записываемые в стек данные (DO). Одновременно с помощью третьего логического элемента ИЛИ 45 на входы загрузок всех регистров-защелок 44.1-44.x подается логическая единица. По окончанию тактового интервала все регистры-защелки 44.1-44.x загружают слова, которые подаются на их входы. Таким образом, осуществляется сдвиг регистра стека в глубину с записью в вершину стека (регистр-защелку 44.1) слова, подаваемого на входы стека.
При подаче на вход чтения стека (R) логической единицы на выходы всех коммутаторов 43.1-43.x передаются слова с их вторых входов, при этом входы данных каждого предыдущего регистра-защелки логически подключаются к выходам следующих регистров-защелок (образуя сдвиговый регистр на x слов, реализующий сдвиг вверх), на вход регистра-защелки 44.x подается слово нулей). Одновременно с помощью третьего логического элемента ИЛИ 45 на входы загрузок всех регистров-защелок 44.1-44.x подается логическая единица. По окончанию тактового интервала все регистры-защелки 44.1-44.x загружают слова, которые подаются на их вход. Таким образом, осуществляется сдвиг регистра стека наверх с записью в вершину стека (регистр-защелку 44.1) ранее записанного в стек слова.
Чаще всего для декодирования LDPC-кодов используют алгоритм декодирования с итеративным распространением доверия (IBP, iterative belief-propagation), известный также как алгоритм sum-product и как алгоритм message-passing (см. Морелос-Сарагоса. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. - М.: Техносфера, 2005. - 320 с.).
В представленном изобретении используется модификация этого алгоритма, предусматривающая обновление значений LLR (Log likelihood ratio - логарифмическое отношение правдоподобия) принятых символов слова LDPC-кода после обработки каждого проверочного уравнения кода.
Данный алгоритм итеративный, он предусматривает выполнение следующих этапов.
1) Счетчик итераций обнуляется.
2) Выбирается первое проверочное уравнение (ПУ) из множества действительных ПУ. Если множество действительных ПУ - пусто, осуществляется переход к п.10.
3) Осуществляется проверка значений LLR символов, входящих в проверочное уравнение. Если модуль значения больше заданного порога или равен ему, оценка символа считается надежной, и она больше не меняется («замораживается»). Соответствующий символ удаляется из проверочного уравнения, при этом проверочное уравнение модифицируется. Если значение замороженного символа соответствует двоичной 1, то четность уравнения меняется.
4) Если в результате модификации в ПУ не остается членов, оно считается вырожденным. Если остается только один член, в качестве оценки LLR символа, адресуемого этим членом, берется значение порога (с учетом знака) и символ «замораживается. Единственный член из уравнения удаляется (уравнение также становится вырожденным).
5) Если уравнение вырождается, оно удаляется из множества действительных ПУ и осуществляется переход к п.8.
6) Осуществляется обновление значений LLR символов, входящих в проверочное уравнение.
7) Модифицированное ПУ заменяет прежнее ПУ в множестве действительных ПУ.
8) Выбирается следующее проверочное уравнение из множества действительных ПУ. Если все ПУ обработаны, осуществляется переход к следующему пункту, в противном случае переход к п.3.
9) Счетчик итераций инкрементируется. Если его величина меньше заданного предельного числа итераций, осуществляется переход к п.2.
10) Осуществляется вывод жестких решений, в качестве которых используется знаковые разряды LLR символов кодового слова. Обновление значений LLR символов, входящих в проверочное уравнение, выполняется на 6 этапе следующим образом:
j
где  - значение LLR символа i кодового слова; g() - функция, используемая для оценки LLR символа на основе проверочного уравнения; p - число членов проверочного уравнения.
7
Функция g() от двух аргументов может быть определена следующим образом (см. патент 1379001 EP. МПК H03M 13/13. Methods and system for decoding low density parity check (LDPC) codes / Mustafa Eroz, Feng-Wen Sun, Lin-Nan Lee - заявлено 02.07.2003 №03254214.4; опубл. 07.01.2004):
g
a
-|a+b|
-|a-b|
где LUT(,b)=ln(1+e)-ln(1+e).
Функция g() от более чем двух аргументов может быть вычислена рекурсивно.
В представленном изобретении арифметическое устройство 5 реализует обновление значений LLR символов последовательно в два прохода.
j
В прямом проходе на первые входы арифметического устройства 5 последовательно поступают , , …, ,  - значения LLR символов, входящих в проверочное уравнение. При этом вычисляется последовательность вспомогательных переменных f:
…
j
При выполнении обратного прохода на вторые входы арифметического устройства 5 последовательно поступают в обратном порядке из первого стека 6 те же самые значения LLR символов, которые подавались в арифметическое устройство 5 во время первого прохода, , , …, , . При этом вычисляется последовательность вспомогательных переменных b:
…
Также во время обратного прохода последовательно вычисляются и выводятся из арифметического устройства 5 новые значения LLR символов:
В процессе обработки устройством декодирования LDPC-кодов принятого кодового слова можно выделить три фазы.
В первой фазе LLR символов последовательно загружаются в первый блок памяти 2 (фиг.1) через шестой коммутатор 20, вторые входы которого являются входами данных устройства. Адреса ячеек первого блока памяти в этом случае формируются устройством управления 1, с двадцать шестых выходов которого они поступают на первые входы пятого коммутатора 19 и подаются далее на адресные входы первого блока памяти 2. Строб записи в память также формируется УУ 1.
Также в первой фазе УУ 1 осуществляет инициализацию второго и третьего блоков памяти 3 и 4. Для этого в них записываются начальные значения параметров проверочных уравнений, определяемые проверочной матрицей H используемого LDPC-кода. Для инициализации используются первый - четвертый коммутаторы 15-18: через первый и второй коммутаторы 15, 16 в блоки памяти 3, 4 записываются параметры, через третий и четвертый 17, 18 передаются адреса соответствующих ячеек памяти.
Во второй фазе осуществляется итеративное декодирование кодового слова. Вторая фаза является основной, она будет подробно рассмотрена ниже.
В третьей фазе исправленное кодовое слово выгружается из первого блока памяти 2, его символы подаются на выход устройства. В качестве символов кодового слова берутся жесткие решения, представляющие собой знаковые разряды LLR. Адреса ячеек первого блока памяти в этом случае формируются устройством управления 1, с двадцать шестых выходов которого они поступают на первые входы пятого коммутатора 19 и подаются далее на адресные входы первого блока памяти 2.
Рассмотрим более подробно работу устройства декодирования LDPC-кодов во второй фазе обработки принятого кодового слова.
В этой фазе устройство декодирования выполняет заданное число итераций.
Количество итераций декодирования подсчитывается устройством управления 1. Декодирование завершается при выполнении декодером заданного числа итераций. Также декодирование завершается при отсутствии действительных проверочных уравнений, которые должны содержаться во втором и третьем блоках памяти 3 и 4. Отсутствие действительных ПУ определяется по нулевому значению поля числа членов ПУ в ячейке второго блока памяти 3, находящейся по нулевому адресу.
В каждой итерации устройство декодирования обрабатывает все действительные проверочные уравнения, параметры которых хранятся во втором и третьем блоках памяти 3 и 4.
Обработка одного действительного проверочного уравнения начинается с чтения описания ГТУ из второго блока памяти 3. Число членов ПУ из описания ПУ заносится в пятый счетчик 5, признак четности помещается в T-триггер 14.
После чего из третьего блока памяти 4 в первый регистр-защелку 13 последовательно считываются номера позиций символов кодового слова, входящих в обрабатываемое уравнение. Эти номера используются как адреса первого блока памяти 2 для чтения последовательности значений LLR символов, входящих в проверочное уравнение. Для этого содержимое первого регистра-защелки 13 подается на третьи входы пятого коммутатора 19 и далее на адресные входы первого блока памяти 2. Последовательность номеров позиций символов кодового слова, входящих в уравнение, также запоминается во втором стеке 7.
Последовательность значений LLR символов, входящих в проверочное уравнение, одновременно подается на вторые входы схемы сравнения кодов 21, первые входы данных арифметического устройства 5 и на входы данных первого стека 6. Помещаются в стек и обрабатываются АУ 5 только не «замороженные» значения LLR, чей модуль не превышает порог Thres. Это соответствует прямому проходу модификации LLR символов, входящих в проверочное уравнение.
Для определения и обработки «замороженных» значений LLR символов используется схема сравнения кодов 21 и первый и второй логические элементы И 22 и 23. Схема сравнения сравнивает коды, поступающие на ее входы. На первые входы подается значение порога, выдаваемого УУ 1, на вторые входы подается последовательность значений LLR символов, считанная из первого блока памяти 2. Если значение LLR по модулю больше или равно значения порога на первом выходе схемы сравнения кодов 21 формируется логическая 1 (признак «замороженности»), на втором выходе схемы сравнения формируется инверсное значение к первому выходу. Единичное значение сигнала на выходе первого логического элемента И 22 уменьшает на единицу число членов ПУ, хранящееся в пятом счетчике 12, и меняет четность ПУ, признак которой хранится в T-триггере. Единичное значение сигнала на выходе второго логического элемента И 23 разрешает запись значений LLR в первый стек бив АУ 5 и соответствующих значениям LLR номеров символов во второй стек 7.
Если после прямого прохода содержимое пятого счетчика 12 обнулилось или стало равно 1, обратный проход не выполняется, параметры вырожденного проверочного уравнения во второй и третий блоки памяти не сохраняется. Если содержимое пятого счетчика 12 стало равно 1, в первый блок памяти 2 в качестве значения LLR записывается значение порога с соответствующим знаком по адресу, равному номеру единственного оставшегося символа.
Если проверочное уравнение не выродилось (содержимое пятого счетчика 12 больше 1), после завершения прямого прохода начинается обратный проход модификации LLR символов, входящих в проверочное уравнение. Во время прохода на вторые входы данных арифметического устройства 5 из первого стека 6 подается последовательность значений LLR символов, входящих в проверочное уравнение, в обратном порядке. Во время обратного прохода на выходах АУ 5 появляются модифицированные значения LLR символов, которые записываются в первый блок памяти 2 по адресам, считанным из второго стека 7. Одновременно адреса, считанные из второго стека 7, являющиеся номерами символов, входящими в ПУ, заносятся в третий блок памяти 4. Модифицированное описание ПУ записывается из T-триггера 14 и пятого счетчика 12 во второй блок памяти 3 по адресу, хранящемуся во втором счетчике 9, который затем инкрементируется. Таким образом, сохраняется модифицированное ПУ.
Первый счетчик 8, хранящий адрес текущего описания ПУ, инкрементируется, и описанный процесс повторяется для следующего и затем для всех действительных проверочных уравнений, описание которых хранится во втором и третьем блоках памяти 3 и 4.
Вычислительная сложность устройства декодирования LDPC-кодов уменьшается по сравнению с прототипом за счет последовательного уменьшения вычислительной сложности итераций алгоритма декодирования с увеличением номера итерации. Это определяется уменьшением числа членов проверочных уравнений (за счет «замораживания» символов кодового слова) и уменьшением числа ПУ (за счет их вырождения).
Арифметическое устройство 5 (фиг.2) во время прямого прохода работает следующим образом.
Значения LLR символов, поступающие на первые входы данных арифметического устройства 5 (DI1), передаются на выходы седьмого коммутатора 31, поскольку второй сигнал управления арифметическим устройством 5 (Backward), поступающий на вход управления коммутатором 31, не активен.
1
Первое значение LLR  через восьмой коммутатор 32, выходы которого на это время подключаются к его вторым входам, загружается во второй регистр-защелку 28, формируя значение f в соответствии с формулой (3). Для управления коммутатором 32 в это время активизируется (принимает значение, равное логической единице) сигнал на выходе логического элемента И 38, поступающий далее через логический элемент ИЛИ 36 на вход управления восьмого коммутатора. Соответствующий временной интервал определяется нулевым состоянием шестого счетчик 27, во время которого на первом выходе дешифратора 35 появляется логическая 1.
j-1
j
j
j
Следующие значения LLR поступают на вторые входы первого блока вычисления функции g 25, на первые входы которого поступают значения f с выходов второго регистра-защелки 28. Результаты вычисления функции g через восьмой коммутатор 32, выходы которого в это время подключены к его первым входам, записываются во второй регистр-защелку 28, формируя тем значения f в соответствии с формулами (4-6). С выходов второго регистра-защелки 28 значения f записываются в третий стек 24. Второй D-триггер 30 необходим для синхронизации сигнала записи в стек с появлением значений f на выходах второго регистра-защелки 28.
Во время обратного прохода арифметическое устройство 5 работает следующим образом.
Значения LLR символов, поступающие на вторые входы данных арифметического устройства 5 (DI2) в обратном порядке, передаются на выходы седьмого коммутатора 31, поскольку второй сигнал управления арифметическим устройством 5 (Backward), поступающий на вход управления коммутатором 31, активен.
p
Первое в обратной последовательности значение LLR  через восьмой коммутатор 32, выходы которого на это время подключаются к его вторым входам, загружается во второй регистр-защелку 28, формируя значение b в соответствии с формулой (7). Для управления коммутатором 32 в это время активизируется (принимает значение, равное логической единице) сигнал на выходе логического элемента И 41, поступающий далее через логический элемент ИЛИ 36 на вход управления восьмого коммутатора. Соответствующий временной интервал определяется с помощью первого D-триггера 29, на D-вход которого подается сигнал управления "Backward".
j+1
j
Следующие значения LLR поступают на вторые входы первого блока вычисления функции g 25, на первые входы которого поступают значения b с выходов второго регистра-защелки 28. Результаты вычисления функции g через восьмой коммутатор 32, выходы которого в это время подключены к его первым входам, записываются во второй регистр-защелку 28, формируя тем значения b в соответствии с формулами (8-10).
Во время обратного прохода на выходе арифметического устройства 5 появляются модифицированные значения LLR символов.
p-1
Первым появляется новое значение  (см. формулу 11), для этого используется второй сумматор 34, на вторые входы которого постоянно подаются значения LLR, поступающие на вторые входы данных арифметического устройства 5, на первые входы сумматора в 34 это время через девятый коммутатор 33 (третьи входы) и схему инверсии знака 42 из стека подается значение f.
j
j+2,
j+2
j
Затем появляются значения LLR, вычисляемые по формуле (12), для этого на первые входы второго сумматора 34 через девятый коммутатор 33 (вторые входы) и схему инверсии знака 42 с выходов второго блока вычисления функции g 26 подается значение g(f,b). При этом на первые входы второго блока вычисления функции g 26 поступают величины b с выходов второго регистра защелки 28, на вторые входы второго блока вычисления функции g поступают величины f с выходов третьего стека 24.
2
Последним на выходах арифметического устройства 5 появляется новое значение  (см. формулу 13), для этого на первые входы второго сумматора 34 через девятый коммутатор 33 (первые входы) и схему инверсии знака 42 с выходов второго регистра-защелки 28 подается значение b. Соответствующий этому временной интервал определяется нахождением шестого счетчика 27 в состоянии «1», при этом на втором выходе дешифратора 35 появляется логическая 1, которая пропускается во время обратного прохода четвертым логическим элементом И 39 на первый вход управления девятого коммутатора 33.
Если на третьем входе управления арифметического устройства 5 (Par) присутствует логическая 1, схема инверсии знака меняет знак величины изменения LLR, это необходимо делать для проверочных уравнений, сумма символов которых должна быть нечетной.
Предлагаемое устройство состоит из простых по своему функциональному назначению элементов и поэтому легко может быть реализовано на ПЛИС или специализированной БИС.
Предлагаемое устройство декодирования LDPC-кодов по сравнению с прототипом обладает преимуществом, заключающемся в меньшей вычислительной сложности. Это в свою очередь определяет меньшую аппаратную сложность или (и) более высокую пропускную способность устройства.