Декодер ldpc и способ его функционирования
Владельцы патента RU 2634193:
Акционерное общество Научно-производственный центр "Электронные вычислительно-информационные системы" (АО НПЦ "ЭЛВИС") (RU)
Группа изобретений относится к области цифровой обработки информации, а именно к декодерам LDPC (кодов с малой плотностью проверок на четность) и способам их функционирования. Техническим результатом является уменьшение аппаратных ресурсов. Сущность заявленных изобретений заключается в оптимизации схемы декодера и способа его функционирования, а именно использования для каждой проверочной вершины одного узла поиска минимумов (509) и элементов памяти (503) для всех ребер, исходящих из этой проверочной вершины (502) к символьным (501) согласно графу. Для каждой символьной вершины используют один общий сумматор (516) всех сообщений (520 и 515) от проверочных вершин согласно графу Таннера и элемент памяти (524) вне зависимости от ребер, исходящих из этой символьной вершины. 2 н.п. ф-лы, 5 ил.
Изобретение относится к области цифровой обработки информации, а именно к декодерам LDPC (Low density parity check - кодов с малой плотностью проверок на четность) и способам их функционирования, и может быть использовано для декодирования информации, закодированной кодом LDPC, в различных системах передачи/приема данных.
Коды LDPC относятся к блочному кодированию и широко используют в системах передачи информации. Данные коды позволяют исправлять множественные ошибки в блоках данных от нескольких бит до сотен килобайт (увеличение блока данных приводит к аппаратным сложностям).
В настоящее время данные коды LDPC массово используют в нескольких стандартах передачи данных. Последние достижения в технологии производства микроэлектроники позволяют аппаратно реализовать системы кодирования (декодирования) на основе кодов LDPC, что позволяет крайне близко подойти к границе Шеннона по пропускной способности.
Как у любого блочного кода, основой декодирования является проверочная матрица. При больших длинах данных (десятки-сотни килобит) данная матрица имеет огромные размеры, однако суть кодов LDPC заключается в том, что количество единиц в строках и столбцах всегда не более определенного числа, гораздо меньшего размерности матрицы. Как правило, декодирование осуществляют при помощи графа Таннера, построенного согласно проверочной матрице. Существует несколько способов декодирования по надежностям, полученным при демодуляции принятых данных из зашумленного канала. Наиболее адаптированным способом для аппаратной реализации с минимальной потерей в корректирующей способности является алгоритм min-sum (минимум-сумма). В зависимости от применения существуют параллельный, последовательный и последовательно-параллельный способы реализации данного алгоритма. Наибольшей пропускной способностью является алгоритм, реализованный параллельным способом, то есть обменом вероятностью между символьными и проверочными вершинами графа Таннера. Данная реализация требует наибольшие аппаратные ресурсы.
Известен декодер LDPC, описанный в заявке US 2011/0239086 A1, в котором реализован алгоритм min-sum. Однако, в нем по каждому ребру от проверочной вершины к символьной вычисляют свое сообщение, что требует больших аппаратных ресурсов декодера. Аналогично, от символьной вершины к проверочным вычисляют сообщение, уникальное для каждой вершины, что также требует больших аппаратных ресурсов декодера, поэтому увеличивает его стоимость.
В патенте RU 2382493 описан способ декодирования кодов LDPC, в котором узел проверочной вершины оптимизирован подобно заявленному изобретению в части вычисления двух минимумов, однако отсутствует элемент корректировки сообщения от символьной вершины к проверочной. Это значит, что в символьной вершине также вычисляют уникальные сообщения по каждому ребру, исходящему из вершины, что требует больших аппаратных ресурсов декодера, поэтому увеличивает его стоимость.
Наиболее близкими к заявленному изобретению являются декодер LDPC и способ его функционирования, описанные в патенте CN 101188426 и выбранные в качестве прототипов заявленного изобретения, которые аналогичны способу, описанному в патенте RU 2382493, в части сохранения двух минимумов, однако в них значения хранят в буферах FIFO, что свидетельствует о последовательном режиме работы, и также отсутствует элемент корректировки сообщения от символьной вершины к проверочной, это свидетельствует о затрате большие аппаратных ресурсов декодера со стороны символьных вершин и, соответственно, об увеличении стоимости декодера.
Задачей заявленного изобретения является создание декодера LDPC (Low density parity check - кодов с малой плотностью проверок на четность) и способа его функционирования с меньшими аппаратными ресурсами и, соответственно, с меньшей стоимостью, за счет оптимизации параллельного алгоритма min-sum, а именно за счет одного подсчета надежностей от проверочной вершины для символьных вершин с разницей только в коммутации этих значений для символьной вершины, а также за счет одного общего сумматора в каждой символьной вершине. Алгоритм min-sum является итеративным, в нем при каждой итерации пересчитывают надежности, первоначально принятые от демодулятора. От каждой проверочной вершины исходит надежность, подсчитанная по правилу для символьной вершины согласно графу Таннера (Фиг. 1). И, соответственно, наоборот, от каждой символьной вершины исходит надежность, подсчитанная по правилу для проверочной вершины.
Поставленная задача решена путем создания декодера LDPC (Фиг. 5), содержащего по меньшей мере два общих сумматора (516) с элементами памяти и по меньшей мере два блока (509) поиска двух минимумов, вход которых соединен с выходом сумматора (528) текущей символьной вершины (501) и по меньшей мере еще один вход соединен с по меньшей мере еще одним сумматором (539) другой символьной вершины (541), а выходы соединены с входами элементов памяти (503), выходы которых соединены с нулевым и первым входами мультиплексора (532), вход выбора которого соединен с выходом элемента памяти (534), хранящего значение сигнала выбора (510), причем выход этого же элемента памяти (534) также соединен со входом мультиплексора (533) знака, нулевой и первый входы которого соединены с выходами элементов памяти (503), выполненных с возможностью хранения знака второго и первого (507, 506) минимального значения выхода блока (509) поиска двух минимумов, а выход мультиплексора (533) знака соединен с входом сумматора (523) по модулю два, второй вход которого соединен с выходом элемента памяти (503), выполненного с возможностью хранения общего знака (508) сообщений, а выход соединен с входом инвертора (527), выход которого соединен с входом выбора мультиплексора (531) константы, выход которого соединен с первым входом умножителя (530), второй вход которого соединен с выходом мультиплексора (532) значения, при этом выход умножителя (530) соединен с первым входом сумматора (528), выход которого соединен с входом блока поиска минимумов (509) и с первым входом компаратора (511), второй вход которого соединен с выходом умножителя (512), на второй вход которого поступает модуль первого минимума (504) с выхода блока поиска минимумов (509), а на первый вход поступает сигнал с выхода мультиплексора (513) константы, на нулевой вход которого поступает константное значение 1, а на первый вход константное значение -1, на вход выбора этого мультиплексора (513) поступает значение знака первого минимума (506), при этом выход компаратора (511) соединен с входом элемента памяти (534), с входом выбора мультиплексора (521) значения и входом выбора мультиплексора (535) знака, на нулевой и первый вход которого поступают знаки второго (507) и первого (506) минимумов с выхода блока поиска минимумов (509), при этом выход мультиплексора (535) знака соединен с первым входом сумматора (536) по модулю два, на второй вход которого поступает значение (508) общего знака с выхода блока (509) поиска минимумов, а выход сумматора (536) по модулю два соединен с входом выбора мультиплексора (522) константы, на нулевой вход которого поступает константное значение 1, а на первый вход константное значение -1, при этом выход мультиплексора константы (522) соединен с первым входом умножителя (529), второй вход которого соединен с выходом мультиплексора (521) значения, на нулевой и первый входы которого поступают первый (504) и второй (505) минимумы с выходов блока поиска минимумов (509), при этом выход (515) умножителя (529) соединен с входом общего сумматора (516), вход которого соединен с входом декодера, а по меньшей мере еще один вход соединен с выходом умножителя (529) текущей проверочной вершины (502), а выход общего сумматора (516) соединен с входом элемента памяти (524), выход которого является выходом декодера и соединен со вторым входом сумматора (528).
Поставленная задача решена также путем создания способа функционирования декодера LDPC (Фиг. 5), в котором на первом этапе в каждой проверочной вершине (502) определяют два минимальных по модулю значения из всех приходящих сообщений (518 и 519) от символьных вершин (501) независимо от того, для какой символьной вершины они предназначаются, причем абсолютные значения минимумов (504, 505), а также знаки (506, 507) этих значений, сохраняют в элементах памяти (503), при раздаче сообщения обратно к символьным, учитывают текущее сообщение от символьной вершины (518): если оно совпадает с одним из выбранных минимумов с учетом знака, то для этой вершины выбирают другой из двух минимумов для каждой из вершин, при каждой итерации сохраняют в элементах памяти (503) оба минимума по модулю (504, 505), оба знака этих минимумов (506, 507), а также общий знак всех сообщений (508), приходящих в проверочную вершину (502), сигнал отрицательного сообщения сохраняют в следующем виде:
тогда общий сигнал отрицательности (508) всех входящих сообщений вычисляют следующим образом:
где операция 
- сложение по модулю 2,
сигнал выбора (510) одного из минимумов для сообщения от проверочной вершины к символьной формируют на выходе первого компаратора (511), исходя из найденных узлом MINIMUM (509) значений:
где 
- значение с выхода первого мультиплексора знака (513), (9)
таким образом, модуль сообщения (514) от проверочной вершины к символьной формируют на выходе второго мультиплексора (521) следующим образом:
а так как знак формируют из общего знака всех сообщений, исключая сообщения от символьной вершины, для которой формируют сообщение на выходе второго компаратора (522), исключив из общего знака, знак отброшенного согласно (10) минимума:
где 
- сигнал отрицательности, сформированный на выходе сумматора по модулю 2 (523), сформированные сообщения 
(520) от каждой проверочной вершины (502) согласно графу Таннера посылают на входы общего сумматора (516) символьной вершины (501), так что на его выходе формируют значение согласно (4): 
которое при каждой итерации сохраняют в элемент памяти (524), выход которого является выходом декодера (525);
на втором этапе оптимизации корректируют полную сумму для каждой из проверочных вершин от рассматриваемой символьной, при этом вычитают из полной суммы после элемента памяти (524) сообщение от этой вершины, запомненное на предыдущем шаге, все операции с сохраненными в элементах памяти (503) значениями минимумов и знаков выполняют (min 1_, min 2_, neg1_, neg2_, neg_) аналогично выражениям (8-11), знак отрицательности (526) из выражения (12) формируют с помощью инвертора (527) с точностью до наоборот:
у сообщения меняют знак и складывают с полной суммой, при этом получают на выходе сумматора (528) скорректированное сообщение от символьной вершины.
Для лучшего понимания заявленного изобретения далее приводится его подробное описание с соответствующими чертежами.
Фиг. 1 - пример графа Таннера.
Фиг. 2 - схема сообщений от символьной вершины к проверочным после инициализации, выполненная согласно изобретению.
Фиг. 3 - схема сообщений от проверочной вершины С2 к символьным D0 (а) и D3 (б), выполненная согласно изобретению.
Фиг. 4 - схема сообщений от символьной вершины D1 к проверочным С0 (а) и С1 (б), выполненная согласно изобретению.
Фиг. 5 - функциональная схема декодера (с коммутацией сообщений между проверочными и символьными вершинами), выполненная согласно изобретению.
Рассмотрим кратко принцип работы заявленного изобретения (Фиг. 2-4). Декодирование по алгоритму min-sum начинают с инициализации элементов памяти символьных вершин значениями априорного отношения правдоподобий (201), поступающих от демодулятора (Фиг. 2):
где Un - априорное отношение правдоподобий принятого символа n от демодулятора,
N - длина кодового слова,
deg(n) - степень вершины - количество исходящих ребер от символьной вершины,
- сообщение для конкретной проверочной вершины ki (203) от текущей символьной вершины n (202).
Далее обновляют информацию, исходящую от проверочных вершин (303), по следующему правилу (Фиг. 3):
где функция g(…) - определяет минимальное по модулю значение с общим знаком из всех аргументов, так что:
где 
Стоит заметить, что среди аргументов функции поиска минимального значения для конкретной символьной вершины (302) отсутствует собственно сообщение от этой символьной вершины. Таким образом, от одной проверочной вершины к символьным исходят разные сообщения о минимуме, поэтому облако комбинационной логики (305) получается разным для каждого исходящего ребра (306) (Фиг. 3).
Далее обновляют все символьные вершины (402) с учетом полученных сообщений от всех проверочных вершин (403), вычисленных согласно выражению (2):
В следующей итерации сообщения (404) от символьных вершин к проверочным вычисляют в зависимости от того, к какой проверочной вершине они следуют:
Аналогично сообщениям от проверочных вершин, сообщения (404) от символьных вершин для конкретной проверочной вершины в своей сумме не содержат сообщения собственно от этой проверочной вершины. Таким образом, от одной символьной вершины к проверочным исходят разные сообщения о сумме, поэтому облако комбинационной логики (405) получается разным для каждого исходящего ребра (406) (Фиг. 4).
Рассмотрим более подробно вариант выполнения заявленного декодера, показанный на Фиг. 5 и способ его функционирования.
Ввиду того, что для каждого ребра из каждой проверочной вершины согласно графу Таннера необходима своя функция нахождения минимума, аппаратные ресурсы будут крайне велики. В заявленном изобретении оптимизирован данный алгоритм с целью уменьшения аппаратных ресурсов.
Если рассматривать путь сообщений от проверочных вершин (303) к символьным (302), то согласно выражению (2) для символьной вершины ni (302) необходимо найти минимум из всех приходящих в проверочную вершину k сообщений от символьных вершин кроме ni. И так далее, для ni+1 участвуют все сообщения кроме сообщения от ni+1 (Фиг. 3 а, б).
Первый этап оптимизации заключается в определении двух минимальных (по модулю) значений из всех приходящих сообщений (518 и 519) от символьных вершин независимо о того, для какой символьной вершины они предназначаются, при этом существенном снижении аппаратных ресурсов. Абсолютные значения минимумов (504, 505), а также знаки (506, 507) этих значений сохраняют в элементах памяти (503). При раздаче сообщения обратно к символьным, учитывают текущее сообщение от символьной вершины (518): если оно совпадает с одним из выбранных минимумов с учетом знака, то для этой вершины выбирают другой из двух минимумов для каждой из вершин. При каждой итерации сохраняют в элементах памяти (503) оба минимума по модулю (504, 505), оба знака этих минимумов (506, 507), а также общий знак всех сообщений (508), приходящих в проверочную вершину (502). Сигнал отрицательного сообщения сохраняют в следующем виде:
тогда общий сигнал отрицательности (508) всех входящих сообщений вычисляют следующим образом:
где операция 
- сложение по модулю 2.
Сигнал выбора (510) одного их минимумов для сообщения от проверочной вершины к символьной формируют на выходе первого компаратора (511), исходя из найденных узлом MINIMUM (509) значений:
где 
- значение с выхода первого мультиплексора знака (513). (9)
Таким образом, модуль сообщения (514) от проверочной вершины к символьной формируют на выходе второго мультиплексора (521) следующим образом:
а так как знак формируют из общего знака всех сообщений, исключая сообщения от символьной вершины, для которой формируют сообщение на выходе второго компаратора (522), исключив из общего знака, знак отброшенного согласно (10) минимума:
где 
- сигнал отрицательности, сформированный на выходе сумматора по модулю 2 (523).
Сформированные таким образом сообщения 
(520) от каждой проверочной вершины (502) согласно графу Таннера посылают на входы общего сумматора (516) символьной вершины (501), так что на его выходе формируют значение согласно (4):
, которое после нескольких итераций сохраняют в элемент памяти (524), выход которого является выходом декодера (525).
Второй этап оптимизации состоит в том, что в каждой символьной вершине (501) хранится полная сумма всех сообщений (520), согласно графу, от проверочных вершин, вне зависимости для какой из проверочных вершин она предназначена. Однако согласно выражению (5) для проверочной вершины (502) предназначена сумма сообщений от проверочных вершин, кроме этой проверочной вершины (502). В схеме на Фиг. 5 предусмотрена корректировка полной суммы для каждой из проверочных вершин от рассматриваемой символьной. Вычитают из полной суммы после элемента памяти (524) сообщение от этой вершины, запомненное на предыдущем шаге. Все операции с сохраненными в элементах памяти (503) значениями минимумов и знаков выполняют (min1_, min2_, neg1_, neg2_, neg_) аналогично выражениям (8-11). Нижнее подчеркивание перед индексом означает, что это значение после элемента памяти (503). Знак отрицательности (526) из выражения (12) формируют с помощью инвертора (527) с точностью до наоборот:
Так как от общей суммы необходимо вычесть сообщение от данной вершины, поэтому у сообщения меняют знак и складывают с полной суммой, при этом получают на выходе сумматора (528) скорректированное сообщение.
Сущность заявленного изобретения заключается в оптимизации схемы декодера и способа его функционирования, а именно использования для каждой проверочной вершины одного узла (данный узел выделен пунктиром на Фиг. 5) поиска минимумов (509) и элементов памяти (503) для всех ребер, исходящих из этой проверочной вершины (502) к символьным (501) согласно графу. И для каждой символьной вершины используют один общий сумматор (516) всех сообщений (520 и 515) от проверочных вершин согласно графу Таннера и элемент памяти (524) (узел выделен сплошной линией) вне зависимости от ребер, исходящих из этой символьной вершины. По каждому ребру необходима схема коммутации сообщений, однако данная схема проста в реализации (выделено жирным штрихпунктирном).
Хотя описанный выше вариант выполнения изобретения был изложен с целью иллюстрации настоящего изобретения, специалистам ясно, что возможны разные модификации, добавления и замены, не выходящие из объема и смысла настоящего изобретения, раскрытого в прилагаемой формуле изобретения.
1. Декодер LDPC, содержащий по меньшей мере два общих сумматора (516) с элементами памяти и по меньшей мере два блока (509) поиска двух минимумов, вход которых соединен с выходом сумматора (528) текущей символьной вершины (501) и по меньшей мере еще один вход соединен с по меньшей мере еще одним сумматором (539) другой символьной вершины (541), а выходы соединены с входами элементов памяти (503), выходы которых соединены с нулевым и первым входами мультиплексора (532), вход выбора которого соединен с выходом элемента памяти (534), хранящего значение сигнала выбора (510), причем выход этого же элемента памяти (534) также соединен со входом мультиплексора (533) знака, нулевой и первый входы которого соединены с выходами элементов памяти (503), выполненных с возможностью хранения знака второго и первого (507, 506) минимального значения выхода блока (509) поиска двух минимумов, а выход мультиплексора (533) знака соединен с входом сумматора (523) по модулю два, второй вход которого соединен с выходом элемента памяти (503), выполненного с возможностью хранения общего знака (508) сообщений, а выход соединен с входом инвертора (527), выход которого соединен с входом выбора мультиплексора (531) константы, выход которого соединен с первым входом умножителя (530), второй вход которого соединен с выходом мультиплексора (532) значения, при этом выход умножителя (530) соединен с первым входом сумматора (528), выход которого соединен со входом блока поиска минимумов (509) и с первым входом компаратора (511), второй вход которого соединен с выходом умножителя (512), на второй вход которого поступает модуль первого минимума (504) с выхода блока поиска минимумов (509), а на первый вход поступает сигнал с выхода мультиплексора (513) константы, на нулевой вход которого поступает константное значение 1, а на первый вход константное значение -1, на вход выбора этого мультиплексора (513) поступает значение знака первого минимума (506), при этом выход компаратора (511) соединен с входом элемента памяти (534), с входом выбора мультиплексора (521) значения и входом выбора мультиплексора (535) знака, на нулевой и первый вход которого поступают знаки второго (507) и первого (506) минимумов с выхода блока поиска минимумов (509), при этом выход мультиплексора (535) знака соединен с первым входом сумматора (536) по модулю два, на второй вход которого поступает значение (508) общего знака с выхода блока (509) поиска минимумов, а выход сумматора (536) по модулю два соединен с входом выбора мультиплексора (522) константы, на нулевой вход которого поступает константное значение 1, а на первый вход константное значение -1, при этом выход мультиплексора константы (522) соединен с первым входом умножителя (529), второй вход которого соединен с выходом мультиплексора (521) значения, на нулевой и первый входы которого поступают первый (504) и второй (505) минимумы с выходов блока поиска минимумов (509), при этом выход (515) умножителя (529) соединен с входом общего сумматора (516), вход которого соединен с входом декодера, а по меньшей мере еще один вход соединен с выходом умножителя (529) текущей проверочной вершины (502), а выход общего сумматора (516) соединен с входом элемента памяти (524), выход которого является выходом декодера и соединен со вторым входом сумматора (528).
2. Способ функционирования декодера LDPC, в котором на первом этапе в каждой проверочной вершине (502) определяют два минимальных по модулю значения из всех приходящих сообщений (518 и 519) от символьных вершин (501) независимо от того, для какой символьной вершины они предназначаются, причем абсолютные значения минимумов (504, 505), а также знаки (506, 507) этих значений сохраняют в элементах памяти (503), при раздаче сообщения обратно к символьным, учитывают текущее сообщение от символьной вершины (518): если оно совпадает с одним из выбранных минимумов с учетом знака, то для этой вершины выбирают другой из двух минимумов для каждой из вершин, при каждой итерации сохраняют в элементах памяти (503) оба минимума по модулю (504, 505), оба знака этих минимумов (506, 507), а также общий знак всех сообщений (508), приходящих в проверочную вершину (502), сигнал отрицательного сообщения сохраняют в следующем виде:
тогда общий сигнал отрицательности (508) всех входящих сообщений вычисляют следующим образом:
где операция ⊕ - сложение по модулю 2,
сигнал выбора (510) одного из минимумов для сообщения от проверочной вершины к символьной формируют на выходе первого компаратора (511), исходя из найденных узлом MINIMUM (509) значений:
где
- значение с выхода первого мультиплексора знака (513) (9)
таким образом, модуль сообщения (514) от проверочной вершины к символьной формируют на выходе второго мультиплексора (521) следующим образом:
а так как знак формируют из общего знака всех сообщений, исключая сообщения от символьной вершины, для которой формируют сообщение на выходе второго компаратора (522), исключив из общего знака, знак отброшенного согласно (10) минимума:
где
- сигнал отрицательности, сформированный на выходе сумматора по модулю 2 (523),
сформированные сообщения 
(520) от каждой проверочной вершины (502) согласно графу Таннера посылают на входы общего сумматора (516) символьной вершины (501), так что на его выходе формируют значение согласно (4):
, которое при каждой итерации сохраняют в элемент памяти (524), выход которого является выходом декодера (525);
на втором этапе оптимизации корректируют полную сумму для каждой из проверочных вершин от рассматриваемой символьной, при этом вычитают из полной суммы после элемента памяти (524) сообщение от этой вершины, запомненное на предыдущем шаге, все операции с сохраненными в элементах памяти (503) значениями минимумов и знаков выполняют (min 1_, min2_, neg1_, neg2_, neg_) аналогично выражениям (8-11), знак отрицательности (526) из выражения (12) формируют с помощью инвертора (527) с точностью до наоборот:
у сообщения меняют знак и складывают с полной суммой, при этом получают на выходе сумматора (528) скорректированное сообщение от символьной вершины.
