Содержание к диссертации
Введение
Глава 1. Проблема достоверной передачи информации в системах наземного теле радиовещания – постановка задачи, методы решения 13
1.1. Постановка задачи 13
1.2. Системы связи .15
1.3. Модели каналов связи 18
1.3.1 Двоичный симметричный канал .21
1.3.2 Двоичный симметричный канал со стираниями .22
1.3.3 Канал с аддитивным белым гауссовским шумом .24
1.3.4 Канал с аддитивным белым гауссовским шумом и квантованным выходом 25
1.3.5 Канал с обобщенными Релеевскими замираниями 26
1.4. Математическая формализация задачи построения декодера .26
1.5. Коды с низкой плотностью проверок на четность 28
1.5.1 Представление LDPC кода 28
1.5.2 Графическое представлении LDPC кода .30
1.6. Классические алгоритмы декодирования LDPC кодов 35
1.6.1 Передача сообщений и принципы турбо-декодирования .35
1.6.2 Декодирование LDPC кодов 37
1.6.3 Декодирование кода повторения 40
1.6.4 Декодирование кода проверки на четность 42
1.6.5 Алгоритм сумма-произведение .45
1.6.6 Алгоритмы декодирования для ДСКС .47
1.6.6.1 Итеративный алгоритм заполнения стираний 48
1.6.6.2 Декодер максимального правдоподобия для ДСКС .49
1.6.7 Алгоритмы декодирования для ДСК 53
1.6.7.1 Алгоритмы Галлагера A и Б .54
1.4.7.2 Алгоритм мажоритарного декодирования для ДСК 58
1.4.7.3 Алгоритм с инверсией бита для ДСК 62
1.7. Выводы и рекомендации 64
Глава 2. Разработка и исследование упрощенных алгоритмов декодирования LDPC кодов 66
2.1 Алгоритмы, основанные на алгоритме распространения доверия 66
2.1.1 Алгоритм Ричардсона-Новичкова 67
2.1.2 Алгебра логарифма отношений правдоподобия .70
2.1.3 Алгоритм минимум-сумма с корректировкой .73
2.1.4 Алгоритм минимум-сумма 77
2.1.5 Алгоритм вычисления апостериорных вероятностей. 80
2.2 Алгоритмы, основанные на алгоритме с инверсией бита. 82
2.2.1 Взвешенный алгоритм с инверсией бита .82
2.2.2 Модифицированный взвешенный алгоритм с инверсией бита .84
2.2.3 Усовершенствованный модифицированный взвешенный алгоритм с инверсией бита 86 2.3. Комбинации алгоритмов 88
2.3.1 Алгоритм аппроксимация минимум-сумма .88
2.3.2 Алгоритмы, основанные на алгоритме МС* .90
2.3.3 Обобщенный алгоритм МС* .91
2.3.4 Алгоритм минимальный ОАМС* 92
2.3.5 Выводы и рекомендации 92
Глава 3. Разработка и исследование методов построения составного декодера LDPC кода, минимизирующего средние вычислительные затраты 94
3.1 Математическая формализация и решение задачи оптимизации параметров декодера LDPC кода .94
3.2 Исследование сложности реализации различных алгоритмов декодирования LDPC кодов .96
3.3 Разработка структуры декодера LDPC кодов .103
3.4 Результаты экспериментов .107
3.5 Выводы и рекомендации .116
Глава 4. Разработка среды моделирования и программных средств для проведения экспериментальных исследований и оптимального проектирования декодеров LDPC кодов 118
4.1 Разработка среды моделирования в программной среде GNU Linux 118
4.2 Разработка моделирующей среды для многоядерных процессоров 124
4.3 Разработка методики оптимального проектирования декодеров LDPC кодов 125
4.4 Выводы и рекомендации .131
Заключение .133
Библиографический список
- Двоичный симметричный канал со стираниями
- Алгебра логарифма отношений правдоподобия
- Комбинации алгоритмов
- Разработка методики оптимального проектирования декодеров LDPC кодов
Двоичный симметричный канал со стираниями
В настоящее время общепринятым подходом при построении систем связи является использование помехоустойчивого кодирования. Более того, часто разработка цифровых систем связи начинается именно с подсистемы помехоустойчивого кодирования. И это не удивительно, сложно недооценить улучшение качества связи и скорости передачи информации при введении современных схем помехоустойчивого кодирования. Наличие ошибок, в большей или меньшей степени присуще всем без исключения системам связи. Таким образом, возникает задача устранения нежелательных ошибок.
В настоящее время, как было сказано выше, одним из наиболее эффективных методов устранения ошибок в теории помехоустойчивого кодирования является использование итеративно декодируемых кодов, в том числе и низ-коплотностных. Основными проблемами при разработке систем помехоустойчивого кодирования являются: точки зрения эффективности и вычислительных затрат алгоритмов декодирования.
Несмотря на то, что идея итеративного декодирования была предложена еще в 60-х годах прошлого века [8], она продолжает развиваться и в настоящее время, о чем свидетельствуют большое число публикаций, посвященных данной проблематике в отечественных и зарубежных изданиях. При этом большое внимание уделяется проблеме разработки алгоритмов декодирования итеративно-декодируемых кодов, имеющих приемлемые вычислительные затраты и высокую эффективность. Эта проблема, в первую очередь, актуальна для технических приложений в которых запас энергии на приемной стороне ограничен, например, при организации беспроводной и мобильной связь, цифрового теле-и радиовещание. При этом следует учесть тот факт, что итеративный декодер выполняет различное число итераций в зависимости от ОСШ на входе приемника, а следовательно сложность декодера является переменной величиной. Следовательно для нашего приложения при оценке эффективности работы декодера имеет смысл говорить о средних вычислительных затратах, требуемых на реализацию декодера в диапазоне практически интересных ОСШ.
Как показала практика разработки системы РАВИС, декодер является самым сложным с точки зрения вычислительных затрат элементом приемника. Таким образом, на разрабатываемую систему помехоустойчивого кодирования накладываются жесткие ограничения на использование вычислительные ресурсов. С другой стороны, как было сказано выше, условия использования системы требуют наличия достаточно эффективного декодера, способного качественно отрабатывать негативное воздействие внешней среды.
В связи с чем актуальной становится задача построение такого декодера, который обладал бы заданной эффективностью при минимальных средних вычислительных затратах.
Постановка задачи построения декодера низкоплотностного кода с минимальными вычислительными затратами при заданной эффективности невозможна без рассмотрения системы связи, в которой применяется та или иная система помехоустойчивого кодирования.
Рассмотрим следующий общий случай – информация (речь, аудио, видео, данные и т.д.) передается от источника получателю по каналу связи с шумом (телефонная линия, оптический канал связи, беспроводной канал связи, носитель и т.д.) рисунке 1.1. Получатель заинтересован в надежной передаче, т. е. желает воссоздать передаваемую информацию на приемной стороне с минимально возможными ошибками.
В своей основополагающей работе в 1948 году, Шеннон, помимо введения фундаментальных понятий теории информации, таких, как энтропия, формализовал задачу передачи информации в целом и показал, что эта проблема может быть разделена на две – кодирование источника и кодирование канала [11], рисунок 1.2.
Канал связи Рисунок 1.2 – Система передачи информации с точки зрения теоремы о разделении канала и источника Кодер источника преобразует информацию источника в поток бит. В идеале кодер источника должен удалять всю избыточность из информации, так что полученный битовый поток имеет наименьшее возможное число бит при заданной точности представления источника. Канальный кодер обрабатывает получаемый от кодера источника поток данных и добавляет в него некоторую избыточность. Причем избыточность вносится таким образом, чтобы максимально эффективно бороться с шумом, вносимым каналом. Большинство практически используемых в настоящее время систем связи построены на основании этого принципа.
Основное достоинство такого подхода заключается в том, что линия связи может быть использована для разнообразных источников, то есть хорошая схема канального кодирования может быть использована для любого источника. При этом важно понимать и ограничения принципа разделения источника и канала, так например, схемы, совмещающие кодирования источника и канала, могут быть значительно эффективнее с точки зрения суммарных вычислительных затрат или задержки [12]. Кроме того, разделение на кодер источника и канальный кодер теряет силу при рассмотрении многопользовательских сценариев [13]. Однако, до настоящего времени основной предпосылкой при построении системы связи является разделение кодера источника и канального кодера [14-17]. Не стала исключением и система РАВИС [10].
Данная работа не рассматривает проблему кодирования источника или, что эквивалентно, считается, что она уже решена применяемыми в системе РАВИС кодеками, и на вход канального кодера подается информационная последовательность бит, которые с равной вероятностью могут быть равны 0 или 1.
Теорема Шеннона о канальном кодировании утверждает существование максимальной скорости (бит на используемый канал), с которой информация может быть передана надежно, т.е. со сколь угодно малой вероятностью ошибки в данном канале. Эта максимальная скорость называется пропускной способностью канала связи и обозначается C. Никакой метод кодирования не допускает передачи с большей скоростью при произвольно малой частоте ошибок.
Таким образом, задача передачи цифрового сигнала системы РАВИС множеству пользователей является частным случаем более общей задачи достоверной передачи информации по дискретному каналу с шумами, в условиях ограниченной мощности передатчика.
Следовательно, для построения декодера в условиях ограниченных вычислительных затрат необходимо определиться с каналом связи, для которого будет использоваться синтезируемый декодер. Наилучшим образом это можно сделать, построив модель канала связи, используемого для передачи сигнала системы РАВИС, для этого рассмотрим наиболее распространенные модели каналов связи, используемых для моделирования и анализа эффективности декодеров.
Для дальнейшего рассмотрения введем следующие обозначения. Здесь и далее, если не указано иное, будем полагать, что для передачи по каналу связи кодового слова с=(с1,с2,...,сN) кода сєС длины Ж используется модуляция BPSK. При этом передаваемое кодовое слово с при модуляции отображается в биполярную последовательность:
Алгебра логарифма отношений правдоподобия
Уравнение (1.33) вытекает из того факта, что 0 = сНт =cJ,HTJ, + cJHTJ. Можно
показать, что существует единственное решение этого уравнения тогда и только тогда, когда строки матрицы Н , линейно независимы; в этом случае
стертые элементы могут быть определены методом Гаусса. Поскольку Н , имеет N-K столбцов, ее строки могут быть линейно независимыми, только тогда, когда \J \ N-K, что дает нам необходимое условие для единственности решения задачи (1.33). Кроме того, поскольку любые из drmn-l строк Нг (и, следовательно, И],) линейно независимы, то (1.33) гарантированно имеет единственное решение всегда, когда \J \ dmn. То есть алгоритм может исправить любую комбинацию стираний, число которых не превышает минимального расстояния кода.
Стертые биты могут быть найдены следующим образом. Сначала применяется метод подстановки Гаусса для столбцов матрицы Н с индексами стертых бит / для получения эквивалентной матрицы Н, которую, без потери общности, можно представить в виде Н = [н/Н/,], где подматрица Й/1 будет где Т - это нижняя треугольная матрица размерности / х / с единицами вдоль главной диагонали, а М - случайная бинарная матрица (которая может быть и нулевой). Таким образом, можно найти все стертые биты последовательным решением J проверочных уравнений, представленных верхними строками матрицы H. Принцип работы алгоритма при обнаружении множества остановки приведен на рисунке 1.13.
В обобщенном виде алгоритм можно представить следующим образом: 1 шаг. Инициализация. Для всех узлов / инициализировать значения Lt по (1.32) в зависимости от используемой модели канала связи. Затем для всех / и у, для которых hij=1, устанавливается z . . = Ц. 2 шаг. Обновление проверочных узлов. Для всех проверочных узлов CN вычислить по формуле (1.26) исходящие сообщения L. .:
6 шаг. Проверка условия остановки. Если за последнюю итерацию не было исправлено ни одного стирания, то получить методом Гаусса эквивалентную проверочную матрицу и продолжить вычисления с шага 2. Если все стирания исправлены, то есть V/Д = 1, или число итераций достигло максимума вычисления прекращаются, а v считается результатом декодирования, в противном случае вычисления продолжаются с шага 2.
Галлагер в своей основополагающей работе [8] представил три алгоритма декодирования кодов LDPC в канале ДСК. Эти алгоритмы были названы соответственно: алгоритм Галлагера А (алгоритм ГА или АГА, Gallager А), алгоритм Галлагера В (алгоритм ГБ, или АГБ, Gallager В) и алгоритм с инверсией бита (алгоритм ИБ или АИБ, bit flip - BF). Помимо перечисленных итеративных алгоритмов для декодирования LDPC кодов используется хорошо известный [35] алгоритм мажоритарного декодирования (алгоритм МД, или АМД, one-step majority-logic - OSMLG). Использование модели канала ДСК исключает получение информации достоверности приема того или иного бита. 1.6.7.1 Алгоритмы Галлагера A и Б
Алгоритмы ГА и ГБ, так же, как и АСП, основаны на передаче сообщений, за исключением того, что все передаваемые сообщения - двоичные числа (в контексте принятых обозначений - только знак, достоверность не передается). Поскольку алгоритмы по структуре похожи на АСП, то для краткости изложения будем рассматривать декодирование только для шагов, соответствующих шагам 2 и 3 алгоритма АСП.
Окончательные решения относительно принятых бит выносятся следующим образом. Если степень dc информационного узла нечетна, то значение принятого бита считается равным значению большинства входящих в узел сообщений от проверочных узлов. Если степень информационного узла четна, то к подсчету большинства добавляется канальное сообщение.
Алгоритм ГБ - это уточнение алгоритма ГА, которое затрагивает расчет исходящих сообщений от битовых узлов на шаге 3. В алгоритме ГБ для инвертирования исходящего из информационного узла VNi сообщения достаточно, чтобы всего t входящих в узел сообщений а. . отличалось от or,., рисунок 1.15. Таким образом, правило обновления информационных узлов на третьем шаге алгоритма (1.35) примет вид:
Подсчет исходящего из информационного узла сообщения для алгоритма ГБ: а) число входящих сообщений, не равных aj, равно порогу t, б) число входящих сообщений, не равных aj, меньше порога t
Было показано [36], что алгоритм Б является оптимальным для регулярных LDPC кодов в канале ДСК. 1.6.72 Алгоритм мажоритарного декодирования для ДСК
Рассмотрим регулярный LDPC код, не содержащий циклов порядка 4. Очевидно, что для любых двух 0 і,ї М и ІФГ, множества N(i) и N(i ), в лучшем случае, имеют один общий индекс. Аналогично, множества M(j) и M(j ) при 0 j,j N и j j , также имеют не более одного общего индекса. Так как код регулярный, M(j) = dr для всех 0 j М и N(i) = dc для 0 і N.
Для каждого бита 0 i N определим следующий набор строк матрицы Н: При этом набор строк A(i) имеет следующие свойства: каждая строка A(i) является проверкой кодового бита у,, и любой кодовый бит, отличный от у;, имеет не более одной проверки в А(г ). Это свойство A(i) называют свойством ортогональности набора строк относительно кодового бита уг Очевидно, что для того, чтобы наборы строк A(i) были ортогональны для любого і, достаточно, чтобы код не содержал циклов порядка 4.
Ошибочный бит e.t в /-ой позиции е имеет два возможных значения: 1, если бит искажен: 0, если бит принят правильно. Если е,=1, то оставшиеся ненулевые элементы вектора е могут участвовать не более чем в [_d/2\-1 синдромных суммах, ортогональных Таким образом, по крайней мере (более половины) ортогональных синдромных сумм равны е1:= 1. синдромных суммах, ортогональных относительно et. Таким образом, по крайней мере (половина или более) ортогональных е(. синдромных сумм равны е1, = 0. Учитывая приведенный анализ, может быть выведено простое правило декодирования принятых бит.
Комбинации алгоритмов
Алгоритм ИБ также был предложен Галлагером в [8] и может рассматриваться как модификация алгоритмов ГА и ГБ, однако он имеет много общего и с алгоритмом МД, хотя может быть применен и к кодам, не являющимся мажоритарно декодируемыми (имеется в виду необязательность условия ортогональности, а также необходимость в регулярности кода, хотя бы в плане столбцов). В отличие от алгоритмов ГА и ГБ, в алгоритме ИБ сначала вычисляются все проверочные уравнения в матрице Н, а затем инвертирует те биты в полученном кодовом слове, которые участвует более чем в некотором заданном числе t невыполненных проверок. Этот шаг повторяется с измененным принятым кодовым словом, пока все проверки на четность не будут выполнены или пока не будет достигнуто некоторое максимальное число итераций.
На невыполненные проверочные уравнения указывают элементы синдрома s = yHr, а их число для каждого кодового бита можно найти, используя следующее выражение: f =sH, причем умножения матриц выполняется над целыми числами, а не над двоичными. Вектор f называют профилем достоверности, а его элементы f являются ни чем иным, как достоверностями приема соответствующих бит, причем достоверность тем меньше, чем больше значение fj. При этом диапазон значений f лежит в пределах [0Д], и очевидно, что чем больше вес проверок для каждого из бит, тем более точно можно определить достоверность их приема. Также следует заметить, что вычисление f по сути соответствует выражению (1.41) в рассмотрении МД алгоритма.
Порог t - расчетная величина, которая должна быть выбрана таким образом, чтобы максимизировать эффективность декодирования при минимизации вычислительных затрат, и зависит от вероятности перехода в канале, а также dc и dr. В [8], приводится правило выбора оптимального порога для регулярных LDPC кодов при заданной вероятности перехода в канале. Рассчитывать порог в условиях изменяющихся характеристик канала не всегда оправдано, однако существует удобный, хоть и не оптимальный способ, выбора порога, эффективно адаптирующегося к изменению качества канала. Суть его сводится к тому, что инвертируются те биты, для которых число невыполненных проверок максимально, при этом возможны модификации с инверсией только одного бита или нескольких бит за итерацию. Заметим, что при принятых обозначениях невыполненной проверке соответствует отрицательная достоверность. Следовательно, инвертировать следует биты, имеющие минимальное значение достоверности. шаг. Получение жестких решений. -. 6 шаг. Проверка правильности декодирования. Вычислить синдром Шт. Если Шт = 0 или число итераций достигло максимума, вычисления прекращаются, а v считается результатом декодирования, в противном случае вычисления продолжаются с шага 2.
Представленный выше алгоритм ИБ представляет собой итеративный процесс. Вычисление проверочных сумм представляет собой двоичные операции. Однако, расчеты профилей достоверности и операции сравнения с порогом - это операции с целыми числами. Таким образом, вычислительная сложность АИБ несколько больше, чем АМД.
Вообще АИБ и АМД очень похожи, корень их отличий заключается в выборе порога - для АМД он фиксирован и равен нулю, что позволяет оперировать булевыми числами. Для АИБ - порог жестко не фиксирован и может меняться от итерации к итерации в зависимости от характеристик канала, что вынуждает выполнять операции с целыми числами для получения оценок достоверности бит и сравнения их с порогом t. Следствием этого является тот факт, что АИБ - итеративный алгоритм, а АМД - нет.
Задача построения декодера LDPC кода не является новой и уже Р.Галлагером [8] было предложено несколько вариантов решения этой задачи, однако предложенные им алгоритмы имели либо чрезвычайно высокую сложность (АРД), либо имели низкую эффективность (АГА, АГБ, АИБ) для приложений имеющих практический интерес. Оценки сложности и эффективности можно найти в главе 3 и [40, 41, 42]. Также для декодирования LDPC кодов были адаптирован мажоритарный алгоритм (АМД) и алгоритм заполнения стираний (АЗС) для каналов ДСКС и ДСК соответственно.
Работа Р.Галлагера [8] скорее показывала возможность построения помехоустойчивых кодов, способных по характеристикам приблизится к пропускной способности канала, чем давали четкие указания к их построению и получению декодеров, способных в реальном масштабе времени декодировать принятые кодовые комбинации. А предложенный позже алгоритм АМД, лишь подтверждал сходство предложенных кодов и способов их декодирования с уже существовавшими кодами и алгоритмами их декодирования. АЗС, хоть и является оптимальным (при условии отсутствия множеств остановки), применим только для канала ДСКС, он скорее дает общее представление о принципах декодирования LDPC кодов, на которых основываются и более сложные алгоритмы декодирования – в частности АРД, АГА (Б) и АИБ.
Не удивительно, что в чистом виде эти алгоритмы практически не применяются. Исключение составляет, пожалуй, только алгоритм АИБ, который для некоторых классов кодов показывает эффективность не намного хуже, чем для АРД с кардинально меньшими вычислительными затратами [43].
В этой ситуации вполне естественным стал поиск алгоритмических и структурных решений, позволяющих выполнять декодирование LDPC кодов в приложениях имеющих практический интерес. Актуальной стала задача получения декодера с эффективностью близкой к АРД, но приемлемыми вычислительными затратами. Как следствие, родился ряд решений этой задачи.
Разработка методики оптимального проектирования декодеров LDPC кодов
К настоящему времени опубликовано множество отдельных трудов, отчетов и монографий, посвященных декодированию LDPC кодов, в которых предлагаются всевозможные схемы решения задачи близкого к МАВ декодирования LDPC кодов со сниженными, относительно АРД, вычислительными затратами. В них используются различные подходы к декодированию LDPC кодов, начиная от модификации классических алгоритмов [44–56], переходя к адаптации существующих алгоритмов декодирования [57], использованию вероятностного декодирования [58–61], и даже алгоритмов оптимизации [62–67]. Рассмотрение всех возможных алгоритмов выходит за рамки данной работы, поэтому здесь рассмотрим основные направления развития упрощенных алгоритмов декодирования – модификации классических алгоритмов. Приведем краткий обзор их особенностей, дополнительная информация по эффективности и сложности реализации может быть найдена в [40–42, 68, 69] а также в главе 3.
Как было замечено в первой главе, у алгоритма РД есть один существенный недостаток – его реализация требует существенных вычислительных затрат. В связи с чем появилось множество работ по анализу качества декодирования АРД [24, 70, 71], а также внедрению модификаций в этот алгоритм с целью максимального его упрощения с минимально возможными потерями в качестве декодирования. Здесь рассмотрим ряд упрощенных декодеров, которые порой лишь немного проигрывают оригинальному алгоритму СП в производительности, но заметно выигрывают в требуемых вычислительных затратах. Очевидно, что ключом к снижению затрат является упрощение декодера проверочных узлов, выражение (1.29). При этом величина проигрыша в производительности зависит как от канала, так и от используемого кода.
Реализация функции ф(х) (1.29) табличным способом приемлема для некоторых программных реализаций алгоритма, но при реализации на большинстве аппаратных платформ такой подход не годится. Причина в том, что благодаря широкому динамическому диапазону, рисунок 1.11, эта функция сложна для аппроксимации даже очень большой таблицей. При аппаратной реализации это свойство проявляется в существенном падении эффективности декодирования, особенно в области близкой к “дну”.
Однако, несмотря на эти соображения в [72] описан алгоритм, названный алгоритмом Ричардсона-Новичкова, предлагающий аппроксимацию именно этой функции, дружественную для аппаратной реализации. Выражение для расчета сообщений от проверочных узлов имеет вид: грубая аппроксимация (Д;) Ду «1п(2) , а ф (х) грубая аппроксимация ф (х) для х»ln(2) , логично, что при расчете сообщения от проверочного узла используются корректировочные слагаемые
При аппаратной реализации, часто используется целочисленное представление действительных чисел. Алгоритм Ричардсона-Новичкова, удобно реализовать в целочисленном формате. Для этого достаточно равномерно квантовать сообщения от проверочных узлов Д,. c шагом квантования S = \n(2), тогда Д.,. =Sbrj, где bVj - квантованное значение Д,., тогда
Алгоритм показывает хорошую эффективность для различных кодов, однако его распространение ограничено тем, что алгоритм защищен патентом [72]. Оценку эффективности и сложности АРН можно найти в [40]. 2.1.2 Алгебра логарифма отношений правдоподобия
Обновление проверочных узлов можно представить в несколько ином виде, во многих случаях более удобном для реализации и позволяющем получить достаточно простые, с точки зрения реализации, аппроксимации. Но для этого нам потребуется следующий важный результат [73].
Этот факт может быть непосредственно применен для вычисления исходящего из проверочного узла CN сообщения в случае, если его степень равна двум dc-1=2, поскольку выход проверочного узла CN есть ЛОП суммы двоичных независимых случайных величин. Тогда, выход Lout проверочного узла CN для входящих сообщений Lj и L2 определяется выражением (2.5). Более того, несложно показать, что это выражение эквивалентно (1.26) для двух аргументов:
Если же необходимо найти ЛОП суммы более чем двух независимых двоичных случайных величин (в нашем случае dc 3), тогда ЛОП суммы этих случайных величин может быть вычислено повторным вычислением выражения (2.5). Так ЛОП суммы А3=а1+а2+а3 может быть вычислено как
