Диссертация (Декодирование кодов с малой плотностью проверок на четность), страница 5

В противном случае следуетвернуться к шагу 1.Алгоритмы«UMPBP»и«Min-sum»идентичныповсемхарактеристикамдекодирования, но обеспечивают результат разным набором элементарных операций,выполняемых в процессе декодирования.1.3.5.2 Мажоритарное декодирование «UMP BP normalized»По аналогии с модификацией алгоритма минимума суммы «Min-sum», алгоритмвзвешенного мажоритарного декодирования «UMP BP» может быть модернизирован весовымвзятием сообщений от проверочных узлов графа. Для этого вместо формулы (1.28) следуетиспользовать: 1   min Lqm,l '  , если  m ,l  0 L(rm,l )   l'ξ(m)\l.1  min Lqm ,l '  , если  m ,l  1  l'ξ(m)\l(1.31)Значение коэффициента  и характеристики на выходе декодера не претерпелиизменений по сравнению с алгоритмом «Min-sum normalized». Результаты моделированияданного алгоритма аналогичны результатам моделирования алгоритма «Min-sum normalized»,приведенным в третьей главе.1.3.5.3 Мажоритарное декодирование «UMP BP offset»Декодирование по этому алгоритму обуславливает необходимость использования вместоформулы (1.28) формулу:Lqm,l '   c ,0 , если  m,l  0  max   l'minξ(m)\l L(rm,l )  . max   min Lqm ,l '   c ,0 , если  m ,l  1   l'ξ(m)\l(1.32)Значение константы с и характеристики на выходе декодера не претерпели изменений посравнению с алгоритмом «Min-sum offset».

Результаты моделирования данного алгоритмааналогичны результатам моделирования алгоритма «Min-sum offset», приведенным в третьейглаве.291.3.6 Мажоритарное декодирование с варьируемым порогомАлгоритм взвешенного мажоритарного декодирования с варьируемым порогом, будучимодификацией классического мажоритарного алгоритма «UMP BP», рассматривался ранее в[28,38]. Алгоритм имеет два отличия от классического «UMP BP».Первоеотличиекасаетсяформирования«жестких»символовxm ,l .Согласноклассическому алгоритму «UMP BP» решение о формировании того или иного «жесткого»символа xm ,l принимается по средствам сравнения сообщений от символьных узлов графаТаннера Lq m,l  с нулем (1.26).

В этом случае нуль являлся порогом на всех итерацияхдекодирования. Идея мажоритарного декодирования с варьируемым порогом состоит вустановлении ненулевого порога TIter  0 , который бы изменялся от итерации к итерации(рисунок 1.12).На начальных итерациях сообщения Lq m,l  от символьных узлов графа сформированына основе ненадежной информации L(rm,l ) от проверочных узлов графа. Зачастую это приводитк ошибочному формированию величины xm ,l , что сказывается на ошибочном формированиизнака поправки к априорной надежности принятого символа.

Как следствие, надежностьошибочно принятого символа может возрасти, а правильно принятого символа уменьшиться.Если на начальных итерациях порог опустить ниже нуля, негативный эффект от действияненадежных сообщений L(rm,l ) на сообщения Lq m,l  , и, как следствие, на xm ,l , можно смягчитьили вообще нивелировать.Рисунок 1.12 – Изменение порога30Второеотличиезаключаетсявформировании«зонынеопределенности»протяженностью от 0 до порогового значения TIter . Все сообщения L(qm ,l ) , попавшие в эту зонув результате расчета по (1.25), устанавливаются в 0. В алгоритм необходимо добавить условие,определяющее попадание сообщения L(qm ,l ) в «зону неопределенности». Условие выглядитследующим образом:0, L(qm, l )  TIter  & L(qm ,l )  0L(qm, l )  , L(qm ,l ), в остальных случаях (1.33)а формула (1.26) примет вид:x ml xlc , если L(q m ,l )  TIter  c. xl  1, если L(q m,l )  TIter (1.34)Под шириной сходимости порога (x) (рисунок 1.12) понимается число итераций, накоторых значение порога отлично от нуля.

Под глубиной сходимости порога (y) понимаетсязначение порога на первой итерации декодирования. Очевидно, что варьируя пару значений(x,y) можно прийти к различным результатам декодирования.В [28,38] отмечается, что энергетический выигрыш от применения мажоритарногодекодирования с варьируемым порогом по сравнению со стандартным мажоритарнымалгоритмом «UMP BP» составляет 0.1 – 0.4 дБ. Следует отметить, что этот алгоритм можномодифицировать нормировкой сообщений от проверочных узлов графа Таннера иливычитанием корректирующей константы из их абсолютного значения.В главе 3 приводится методика изменения порогового значения и результатымоделирования данного алгоритма декодирования при разных порогах, а также исследованиевлияния глубины порога на сходимость синдрома и среднее число итераций декодирования.1.3.7 Реализация декодирования кусочной аппроксимациейПомимо использования субоптимальных алгоритмов декодирования существуют другиепути упрощения процесса декодирования, позволяющие избежать аналитического расчетагиперболических функций.

Одним из таких путей является аппроксимация функций tanh( x) иatanh(x) . Линейная аппроксимация этих функций рассматривалась ранее в [63,79], аквадратичная в [70]. В [45,65,83] представлены варианты аппроксимации экспоненциальной31функции, используемой для расчета гиперболических функций. В главе 3 предлагаютсяразличные варианты аппроксимаций гиперболических функцийtanh( x)иatanh(x)иисследуется влияние ошибки аппроксимации на характеристики декодирования.1.4 Выводы по главе1.

Анализ существующих алгоритмов декодирования показал их тесную взаимосвязьдруг с другом в рамках отдельных семейств, а также принципиальные отличия семейств друг отдруга.2. Исследование работы алгоритмов декодирования позволило выявить их характерныеособенностив частирасчета поправок, модификациявычислительную эффективность декодирования.которых позволяетповысить32ГЛАВА 2.

Оценка вычислительной сложности декодированияВ данной главе проведена оценка сложности декодирования LDPC кодов. Полученысоотношения для оценки вычислительной сложности для случая регулярных и нерегулярныхматриц для различных алгоритмов декодирования. На основе анализа работы алгоритмовдекодирования разработаны две модификации, позволяющие использовать меньшее числоэлементарных операций без потери в качестве декодирования при незначительном увеличениитребований к памяти для хранения внутренних переменных декодера.Основные результаты, полученные в рамках данной главы, опубликованы автором в[12,15].2.1 Методика оценки сложности декодированияВ качестве критерия сложности алгоритмов декодирования низкоплотностных кодовчасто используют количество элементарных операций различного типа, выполняемыхдекодером за одну итерацию декодирования. Существующие методики оценки сложностиалгоритмов декодирования по данному критерию обладают двумя недостатками.Первый из них связан с отсутствием возможности дать количественную оценкусложности алгоритмов декодирования для случая нерегулярных матриц проверки на четность.Существующие формулы для оценки сложности предназначены для регулярных структуркодов.

В случае нерегулярности проверочной матрицы низкоплотностного кода количество «1»в строках и столбцах усредняется. Такой подход позволяет дать лишь приближенную оценкувычислительной сложности декодирования.Второй недостаток это отсутствие унификации. Под этим понимается различие вподходах к оценке сложности, при которых, например в [38], происходит оценка сложности сучетом всей итерации декодирования, а в [50,90] оценивается лишь сложность расчетасообщений от символьных и проверочных узлов графа Таннера. В [74] опускаются операции,связанные с арифметикой по модулю 2. Все это затрудняет сравнение алгоритмовдекодирования низкоплотностных кодов по критерию сложности между собой.В данной главе приводится обобщение формул расчета сложности на случайнерегулярности проверочной матрицы для различных алгоритмов декодирования и унификацияподхода к оценке сложности декодирования.Для оценки сложности алгоритмов декодирования в качестве базовой используетсяметодика, предложенная в [38].

Данная методика в полной мере учитывает операции сложения( N  ), умножения ( N  ), сравнения ( N / ), взятия модуля числа ( N a ) и сложения по модулю 233( N  ) на одну итерацию декодирования. Операция вычитания приравнивается к операциисложения. Число операций различного типа будет зависеть от «весов» строк (k) и столбцов (j)проверочной матрицы, а также от длины кодового слова (l), количества уравнений в матрицепроверки на четность (m) и алгоритма декодирования.Работу любого алгоритма декодирования кодов с малой плотностью проверок начетность можно разделить на несколько этапов, представленных на рисунке 2.1.

Подсчетэлементарных операций будет вестись для этапов 1-4, выполняемых итеративно.Рисунок 2.1 – Этапы декодирования LDPC кодов2.2 Оценка сложности алгоритмов декодированияДалее будет проведена оценка сложности для большинства вариантов декодированиякодов с малой плотностью проверок на четность.Вычислительная сложность «жесткого» декодирования «Bit Flip» не рассматривается вданной работе. Оценки вычислительной сложности данного алгоритма и его различныхмодификаций проведены в [32,80].2.2.1 Алгоритм минимума суммы «Min-sum»Шаг 1.