Други алгоритми за декодиране
В този раздел представяме редица важни алгоритми за предаване на съобщения, които по същество са приближения на алгоритъма за сума-продукт. Тук не е показан пълен списък на такива алгоритми, но повечето от алгоритмите, които ще бъдат използвани в следващите глави на тази работа, са обхванати тук.
В алгоритъма за минимална сума, методът за коригиране в променливия възел е същият като в алгоритъма за сума-продукт (2.9), но методът за коригиране в контролния възел е опростен
Обърнете внимание, че резултатът се апроксимира като минимума на абсолютната стойност на получения знак. Това приближение става по-точно с увеличаване на размера на съобщението. По този начин, в следващите итерации, когато размерът на съобщението обикновено е голям, вероятността от погрешно декодиране на този алгоритъм е почти същата като тази на алгоритъма за сума-продукт.
Алгоритъм за декодиране на Gallager A:
В този алгоритъм, въведен от Gallagher [11], съобщението принадлежи към азбуката. С други думи, използва се непрограмна информация.
Правило за корекция на контролния възел:
където ⨁ представлява сумата по модул две на двоичните съобщения.
В променлив възел изходящото съобщение е същото като вътрешното съобщение, ако всички външни съобщения не са съгласни с вътрешното съобщение. В този случай изходящото съобщение е същото като външните съобщения. С други думи
където е вътрешното двоично съобщение и е допълнение към двоичната стойност.
В останалата част от тази работа се позоваваме на алгоритъма за декодиране на Gallagher A. Алгоритъмът се представя по-лошо от софтуерните методи за декодиране, представени по-горе, но е много по-малко сложен от изчислителна гледна точка.
Алгоритъм за декодиране на Gallager B:
Този алгоритъм също се дължи на Gallagher и, подобно на алгоритъм A, всички съобщения имат двоична стойност. Единствената разлика между този алгоритъм и алгоритъм А е методът за коригиране на променливия възел. На променлив възел, изходящо съобщение
където е цяло число в диапазона. Тук изходящото съобщение на променливия възел е същото като вътрешното съобщение, с изключение на външните съобщения, които си противоречат. Стойността може да се променя от една итерация на следваща. Оптималната стойност за единен LDPC код се изчислява от Gallagher [11] и най-малкото число, за което
където и са съответно вероятностите за преход на канала (стойност на вътрешна грешка в съобщението) и стойност на външна грешка в съобщението. Отсега нататък ще наричаме Алгоритъм B на Gallagher като Алгоритъм B.
Ще докажем в глава 3, че алгоритъм B е най-добрият възможен алгоритъм за предаване на двоични съобщения за еднообразни LDPC кодове. За нееднородни LDPC кодове ще покажем също, че алгоритъм B е най-оптималният от всички алгоритми за предаване на двоични съобщения, когато възлите във факторната графика на кода нямат информация за степените на възлите в тяхната локална област.
И в двата алгоритма A и B съобщенията не носят програмна информация. Следователно не е изненадващо, че вероятността от погрешно декодиране на тези два алгоритъма, в сравнение с алгоритъма за сума-продукт, е с ниско качество. Но, разбира се, те са много по-евтини от изчислителна гледна точка. Тъй като декодиращата програма (напр. декодиращата сума-продукт) се движи в посоката на конвергенция, размерът на съобщението става много голям, така че програмната информация става по-малко полезна. Използваме тази функция в Глава 7, за да ускорим процеса на декодиране, като позволим на декодера да избере свой собствен метод на декодиране при всяка итерация и ниеще видим, че декодерът има тенденция да превключва към хардуерни алгоритми за декодиране в следващите итерации.
LDPC кодове: анализ
Преди да изучаваме методите за анализ на LDPC кодове, ще обсъдим принципа на итеративно декодиране, така че целта на такъв анализ да стане ясна.
Ориз. 2.4. Принципът на итеративното декодиране.
Итеративният декодер при всяка итерация използва два източника на предадена информация за кодовата дума: информация от канала (вътрешна информация) и информация от предишната итерация (външна информация). От тези два източника на информация алгоритъмът за декодиране се опитва да получи по-добра информация за предадената кодова дума, използвайки тези данни като външна информация за следващата итерация (виж Фиг. 2.4). При успешно декодиране външната информация става все по-добра и по-добра, докато декодерът итерира. Така във всички методи за анализ на итеративен декодер се изследва статистиката на външните съобщения при всяка итерация.
Изследването на еволюцията на функциите на PDF от външни съобщения, итериране на всяка итерация на свой ред, е най-пълният анализ (известен като гъстота на еволюцията). Въпреки това, като приблизителен анализ, може да се проследи еволюцията на представителите на тази плътност.
LDPC анализ на кодовете на Галахър
В оригиналната работа на Gallagher LDPC кодовете се считат за унифицирани и декодирането включва използването на двоични съобщения (алгоритми A и B). Gallagher анализира декодера в такива ситуации [11]. Основната идея на неговия анализ е да характеризира големината на грешките в съобщенията във всяка итерация от гледна точка на ситуацията в канала и големината на грешката в съобщенията в предишната итерация. С други думи, в анализа на Gallagher, развитието на големината на грешката всъобщенията се изучават, то също е еквивалентно на плътността на еволюцията, тъй като PMF функцията на двоичните съобщения е едномерна, т.е. може да бъде описана с един параметър.
Ориз. 2.5. Дървото за декодиране на дълбочина е едно за унифицирания (3, 6) LDPC код.
Анализът на Gallagher се основава на предположението, че входящите съобщения към променлив (проверяващ) възел са независими. Въпреки че това предположение е вярно само ако графиката е без цикли, това е доказано в [12], където очакваната вероятност за погрешно декодиране на код намалява до случая без цикли с увеличаване на дължината на кодовия блок.
Дърво на декодиране
Помислете за коригирано съобщение от възел с променлива мощност, за да потвърдите възела в декодера. Това съобщение се изчислява от входящите съобщения и съобщението на канала до Тези входящи съобщения всъщност са изходящи съобщения от някои възли за проверка, които са коригирани по-рано. Помислете за едно от тези съобщения заедно с неговия възел за проверка на степента. Изходящото съобщение на този контролен възел се изчислява от входящите съобщения до . Можете да повторите тази процедура за всички контролни възли, свързани с, за да формирате декодиращо дърво със същата дълбочина. Пример за такова декодиращо дърво за унифициран (3, 6) LDPC код е показано на фиг. 2.5. Продължавайки по същия начин, може да се получи декодиращо дърво с всякаква дълбочина. На фиг. 2.6 показва пример на дърво за декодиране на дълбочина две за нееднороден LDPC код. Очевидно е, че за нееднородни кодове декодирането на вкоренени дървета в различни променливи възли е различно.
Ориз. 2.6. Дърво на декодиране на дълбочина две за нееднороден LDPC код.
Обърнете внимание, че когато коефициентната графика е дърво, съобщенията в дървото за декодиране с всякаква дълбочина са независими.Ако факторната графика има цикли и нейният обхват, тогава до дълбочината на съобщенията в дървото за декодиране са независими. По този начин независимото предположение е вярно до итерации и е приблизително за следващи итерации.