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

2СодержаниеВведение ................................................................................................................................ 5Общая характеристика работы ......................................................................................... 5ГЛАВА 1. Анализ алгоритмов декодирования LDPC кодов........................................

101.1 Основные понятия..................................................................................................... 101.2 Постановка задачи декодирования сигнала L1C..................................................... 111.3 Известные алгоритмы декодирования......................................................................

131.3.1 Алгоритм с инверсией бита «Bit flip»............................................................... 141.3.2 Алгоритм с распространением доверия «Belief propagation» по вероятностям... 161.3.3 Алгоритм с распространением доверия «Belief propagation» по надежностям....

191.3.4 Семейство алгоритмов минимума суммы «Min-sum» ..................................... 231.3.4.1 Алгоритм минимума суммы «Min-sum» ................................................... 241.3.4.2 Алгоритм минимума суммы «Min-sum normalized»................................. 241.3.4.3 Алгоритм минимума суммы «Min-sum offset» ......................................... 251.3.5 Семейство алгоритмов мажоритарного декодирования «UMP BP»................

261.3.5.1 Мажоритарное декодирование «UMP BP» ............................................... 261.3.5.2 Мажоритарное декодирование «UMP BP normalized» ............................. 281.3.5.3 Мажоритарное декодирование «UMP BP offset»...................................... 281.3.6 Мажоритарное декодирование с варьируемым порогом .................................

291.3.7 Реализация декодирования кусочной аппроксимацией ................................... 301.4 Выводы по главе........................................................................................................ 31ГЛАВА 2. Оценка вычислительной сложности декодирования ................................. 322.1 Методика оценки сложности декодирования .......................................................... 322.2 Оценка сложности алгоритмов декодирования ....................................................... 332.2.1 Алгоритм минимума суммы «Min-sum»...........................................................

332.2.2 Алгоритм минимума суммы «Min-sum normalized» ........................................ 362.2.3 Алгоритм минимума суммы «Min-sum offset» ................................................. 382.2.4 Мажоритарное декодирование «UMP BP» ....................................................... 402.2.5 Мажоритарное декодирование «UMP BP normalized».....................................

432.2.6 Мажоритарное декодирование «UMP BP offset» ............................................. 452.2.7 Мажоритарное декодирование с варьируемым порогом ................................. 472.2.8 Мажоритарное декодирование с варьируемым порогом и нормировкой ....... 492.2.9 Мажоритарное декодирование с варьируемым порогом и сдвигом................ 502.3 Оценка сложности алгоритма «Belief propagation» с линейной аппроксимацией..

5232.4 Сравнительный анализ сложности алгоритмов декодирования.............................. 562.5 Повышение вычислительной эффективности декодирования ................................ 592.5.1 Повышение вычислительной эффективности алгоритма «Min-sum» ............. 592.5.2 Повышение вычислительной эффективности алгоритма «UMP BP» ............. 652.5.3 Сравнительный анализ сложности модифицированных алгоритмов..............

682.6 Выводы по главе........................................................................................................ 69ГЛАВА 3. Исследование характеристик декодирования LDPC кодов наимитационной модели .......................................................................................................

703.1 Планирование экспериментов с имитационными моделями .................................. 703.2 Представление низкоплотностной матрицы проверки на четность........................ 713.3 Описание имитационной модели.............................................................................. 733.4 Результаты имитационного моделирования ............................................................

763.4.1 Подбор весового коэффициента для алгоритма «Min-sum normalized».......... 763.4.2 Подбор корректирующей константы для алгоритма «Min- sum offset» .......... 773.4.3 Влияние порога на декодирование по мажоритарному алгоритму ................. 783.4.4 Сравнение характеристик декодирования субоптимальных алгоритмов ....... 813.4.5 Варианты кусочной аппроксимации гиперболических функций .................... 843.5 Выводы по главе........................................................................................................ 90ГЛАВА 4.

Исследование характеристик декодирования БЧХ и LDPC кодов приобработке сигнала L1C...................................................................................................... 914.1 Пример применения методики выбора алгоритма декодирования LDPC .............. 914.2 Исходные данные для декодирования......................................................................

924.3 Исследование БЧХ кодека ........................................................................................ 934.4 Результаты декодирования выборки сигнала L1C................................................... 954.5 Идентификация инверсии битового потока сигнала L1C........................................ 994.5.1 Идентификация инверсии по ограниченному числу итераций...................... 1014.5.2 Идентификация инверсии по сходимости синдрома ..................................... 1024.5.3 Сравнение способов идентификации инверсии ............................................. 1074.6 Выводы по главе...................................................................................................... 110ГЛАВА 5.

Сравнение LDPC кодов и турбо кодов........................................................ 1115.1 Классификация турбо кодов ................................................................................... 1115.2 Турбо кодек ............................................................................................................. 1115.3 Сравнение характеристик декодирования.............................................................. 1155.4 Сравнение вычислительной сложности декодирования........................................ 11745.5 Выводы по главе...................................................................................................... 120Основные результаты и выводы по работе..................................................................

121Список используемой литературы ................................................................................ 1225ВведениеОбщая характеристика работыРабота относится к теории и технике помехоустойчивого кодирования. Рассматриваютсяпути повышения эффективности практической реализации декодеров кодов с малойплотностью проверок на четность (LDPC от англ. Low-density parity-check). Разрабатываются иисследуются варианты реализации LDPC декодеров, обеспечивающих наилучшие показателипокритериюпомехоустойчивость-сложностьтехническойреализации.Результатыисследований апробируются на примере спутниковой телекоммуникационной подсистемыпередачи эфемеридной и служебной информации наземным потребителям с использованиемсигнала L1C.Актуальность диссертационной работыВ современных телекоммуникационных системах большое внимание уделяетсяпомехозащищенности передаваемой информации.

Помехозащищенность обеспечивается засчет применения помехоустойчивого кодирования информации. Примерно с начала 90-ыхгодов задачу помехоустойчивого кодирования решали с помощью турбо кодов. Однако сростом объемов трафика и скоростей передачи информации возрос интерес к болееэффективной технике помехоустойчивого кодирования – кодированию с помощью кодов смалой плотностью проверок на четность.Коды с малой плотностью проверок на четность обладают эффективными алгоритмамидекодирования, позволяющими быстро и надежно корректировать поврежденную при передачев результате шумов информацию.

Данные коды позволяют осуществлять работу цифровойлинии связи при отношениях сигнал/шум, близких к границе Шеннона, опережая поэффективности коррекции ошибок турбо коды на относительно больших длинах кодовых слов.Коды с малой плотностью проверок на четность рекомендованы для коррекции ошибок всовременных стандартах связи DVB-S2, DVB-C2, Wi-Fi 802.11n, WiMAX 802.16е.Степень разработанности темы диссертацииНа данный момент можно выделить два направления исследований в области кодов смалой плотностью проверок на четность. Первое из них относится к синтезу конструкций LDPCкодов.

В этом направлении следует отметить труды Афанасьева В.Б., Воробьева К.А.,Зигангирова Д.К., Зигангирова К.Ш., Зяблова В.В., Иванова Ф.И., Крука Е.А., ОвчинниковаА.А., Пацей Н.В., Потапова В.Г., Трухачева Д.В., Costello D., Johnson S.J., Kou Y., Luby M.G.,Richardson J., Weller S.R.6Второе направление исследует алгоритмическую составляющую LDPC кодеков. В этомнаправлении следует отметить труды Башкирова А.В., Белоголового А.В., Витязева В.В.,Владимирова С.М., Климова А.И., Козлова А.В., Кравченко А.Н., Лихобабина Е.А., МуратоваА.В., Овечкина Г.В., Проскурина А.А., Солтанова А.Г., Chen J., Fossorier M., Kim N., UrbankeR.L.Общий вклад в развитие теории внесли труды Акулинина А.С., Золотарева В.В.,Зубарева Ю.Б., Колесника В.Д., Eckford A.W., MacKay D., Tanner M.Последние достижения в области кодирования кодами с малой плотностью проверок начетность позволили практически вплотную приблизиться к границе Шеннона.

Как следствие,актуальной задачей на сегодня является не увеличение исправляющей способности, аразработка методики выбора алгоритма декодирования, обеспечивающего наилучшийкомпромисс по определенным критериям качества в рамках рассматриваемой системы связи, имодификация существующих алгоритмов с целью повышения вычислительной эффективностидекодирования и экономии используемых ресурсов памяти.Цель диссертационной работы и решаемые задачиЦелью работы является разработка и исследование алгоритмов декодирования LDPCкодов.

Для достижения поставленной цели решаются следующие задачи:1. Анализ существующих алгоритмов декодирования LDPC кодов.2. Оценка вычислительной сложности декодирования LDPC кодов.3. Оценка статистических характеристик декодирования (BER, число итераций,сходимость синдрома) LDPC кодов.4. Разработка модификаций и методов, позволяющих повысить вычислительнуюэффективность декодирования и сэкономить используемые при декодировании ресурсыпамяти.Методы исследованияВ работе использовался аппарат теории вероятностей, теории электрической связи,дискретной математики и математического анализа.Для проведения моделирования использовалась среда имитационного моделированияMATLAB с пакетом Simulink и среда разработки программных продуктов Microsoft VisualStudio 2010.7Научная новизна1.