Разработка и моделирование алгоритмов списочного декодирования блоковых кодов методом вычисления кластера

Актуальность исследования.

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

Большинство современных исследований' в области помехоустойчивого кодирования связывается с мягкой обработкой кодовых векторов приемником^ реализующего эффективные итеративные преобразования символовкомбинаций: В! этой связи становится? актуальной? задача построения моделей формирования индексов достоверности символов (ИДС) на физическом уровне, позволяющих классифицировать принятые символы по градациям их надежности. Решение подобной1 задачи обеспечивает более полное использование приемником1 введенной в код избыточности. Необходимо отметить, что наиболее распространенным с точки зрения формирования ИДС является метод разбиения пространства различаемых сигналов на интервалы, при попадании в которые демодулируемого параметра соответствующему символу присваивается определенная^ градация надежности. Однако подобныйметод не выгоден с точки зрения вычислительных затрат. В свою очередь использование модели логарифмического отношения. правдоподобия для получения ИДС не в полной мере отвечает требованиям практической реализации решающих 5 схем, поскольку получаемые оценки напрямую зависят от характеристик канала связи (в частности от отношения сигнал-шум).

Выполнение процедуры мягкого списочного декодирования помехоустойчивых кодов эффективно с точки зрения простоты реализации декодера, как для блоковых, так и для непрерывных кодов. Однако декодеры именно блоковых кодов в наибольшей степени отвечают современным сетевым технологиям, которые во многом оперируют не с потоком данных неопределенной длины, а с блоками или ячейками информации, к структуре которых блоковые коды приспособлены наилучшим образом. Одновременно с этим, блоковые коды оказываются более гибкими в вопросах построения адаптивных систем обмена данными, особенно в каскадных схемах построения кодеков. В этой связи целесообразность комплексного изучения процессов формирования ИДС и методов декодирования блоковых кодов по спискам не вызывает сомнений.

Учитывая сказанное, актуальной является задача разработки метода получения целочисленных ИДС не зависящего от свойств канала связи и в тоже время пригодного для использования в сочетании со сложными видами модуляции, а также алгоритмов декодирования блоковых кодов на основе анализа номера списка (кластера) и программного обеспечения для моделирования указанных процессов и выявления потенциальных возможностей различных схем построения мягких декодеров.

Цель работы.

Целью работы является повышение помехоустойчивости передачи сообщений в системах обмена данными с использованием процедуры декодирования по спискам в стирающем канале связи с применением целочисленных ИДС, обеспечивающих полное использование введенной в код избыточности.

Для достижения поставленной цели в работе решались следующие задачи:

1. Определение асимптотической границы для энергетического выигрыша группы не максимально декодируемых кодов на основе аналитического моделирования гауссовского канала связи при их обработке по упорядоченным статистикам в целях полного использования введенной в код избыточности.

2. Разработка способа формирования целочисленных ИДС с использованием модифицированных свойств стирающего канала связи оптимального по критерию скорости упорядочения статистик индексов на длине кодового блока.

3. Оценка верхней границы для коэффициента правдоподобия и выявление на этой основе потенциальных возможностей известных методов формирования целочисленных ИДС методом имитационного моделирования работы решающей схемы приемника в гауссовском канале связи.

4. Разработка быстрого алгоритма списочного декодирования комбинаций систематических блоковых кодов, использующих мягкие решения для реализации" процедуры поиска списка, путем разбиения пространства кодовых комбинаций на кластеры.

5. Обоснование адаптивного алгоритма мягкого декодирования комбинаций кода Рида-Соломона (РС) с использованием процедуры преобразований эквивалентных кодов и численных методов обращения порождающих матриц таких кодов в систематической форме.

6. Разработка комплекса программ реализации предложенных алгоритмов, и оценка их эффективности методом* имитационного моделирования.

Методы исследования.

Теоретические исследования, проведенные в диссертации, основаны на применении методов алгебраической теории групп, колец и полей, методов теории вероятностей и теории случайных процессов, теории меры и математической статистики. Экспериментальные исследования проводились с применением методов математического моделирования, в том числе компьютерного, в среде языков программирования высокого уровня.

Научная новизна исследования.

1. Впервые получена сравнительная оценка для известных методов формирования ИДС относительно найденной методом аналитического моделирования верхней границы коэффициента правдоподобия, определены потенциальные возможности таких методов.

2. Предложен способ формирования целочисленных ИДС, не зависящий от параметров канала связи и отвечающий требованиям быстрой сортировки символов в процедуре декодирования кодового вектора, на основе имитационного моделирования различных каналов связи выявлены его свойства относительно достижения граничных оценок.

3. Доказана возможность декодирования кодовых векторов двоичных систематических блоковых кодов с полным использованием введенной в код избыточности, позволяющей получить дополнительный энергетический выигрыш относительно мягкого декодирования.

4. Предложен алгоритм составления списка на основе оценки номера кластера и старших разрядов координат кодового вектора с их дополнительной защитой методом циклических сдвигов и проверок четности.

5. Разработан алгоритм списочного декодирования блоковых кодов на основе процедуры составления списка по признаку кластера. Проведено статистическое испытание модели декодера с составлением списков по кластерам (патент РФ на изобретение № 2 344 556 от 20.01.2009 г.).

Практическая значимость исследования.

Изложенный в работе новый метод обработки систематических кодов способен обеспечить повышение их корректирующих возможностей в системах связи с низким энергетическим потенциалом. Структура разработанных алгоритмов формирования стираний на основе отображения непрерывного канала связи с последующей процедурой образования потока ИДС кодовых комбинаций обеспечивает возможность простой программно-аппаратной реализации цифровых систем обмена данными.

Результаты диссертационной работы приняты для практического использования в разработках ОАО «Ульяновский механический завод», а также в учебном процессе филиала Военной академии связи г. Новочеркасск и в Ульяновском государственном техническом университете.

Достоверность результатов, представленных в диссертации подтверждается корректностью применения математического аппарата, непротиворечивостью фундаментальным положениям теории информации и общей теории связи, определяется близостью теоретических расчетов и экспериментальных данных, нолученных на ЭВМ.

Апробация результатов исследования.

Основные положения диссертационной: работы докладывались и обсуждались: на научных конференциях Ульяновского. ВВИУС (военный институт), 2005;2007 годахна XIII военной научно — технической конференции 29 ИГР МО РФ, г. Ульяновск, 2007 г.- на 40-й научно-технической конференции // «Вузовская наука в современных условиях УлГТУ», 2007 г.- на XIV военной научно — технической конференции 29 ИП МО РФ, г. Ульяновск, 2007 г.- на 29-ой научно — теоретической конференции, Тамбовский ВВАИУРЭ (военный институт), г. Тамбов, 2007 г.- на седьмой международной конференции «Математическое моделирование физических, экономических, технических, социальных систем и процессов», Ульяновск, 2009. на научно-технической конференции // «Интегрированные автоматизированные системы управления» г. Ульяновск, 2011 г., на 66-ой Всероссийской конференции посвященной Дню радио «Научная сессия» г. Москва, 2011 г.

Публикации.

По теме диссертации опубликовано 17 работ, в том числе 16 статей в сборниках научных трудов и материалах конференций, две из которых опубликованы в изданиях, рекомендованном ВАК РФ, и в одном патенте РФ на изобретение.

Структура и объем диссертации

.

Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 116 работ отечественных и зарубежных авторов, содержит 43 рисунка и 12 таблиц. Общий объем диссертации составляет 139 страниц.

3.7. Выводы.

1. Оценка асимптотических возможностей двоичных кодов по исправлению стираний указывает на имеющийся резерв в получении дополнительного энергетического выигрыша при полном использовании введенной в код избыточности. Величина такого выигрыша зависит от скорости кода и составляет от одного до трех децибел относительно мягких методов декодирования. Наибольшее значение выигрыша достигается при скорости кода близкой к 0,5, что соответствует основным принципам теории помехоустойчивого кодирования.

2. Обработка комбинаций любого помехоустойчивого кода в метрике Хэмминга с использованием алгебраических методов декодирования способно обеспечить приближение к асимптотической границе при условии использования свойств эквивалентных кодов. Применение указанной процедуры опирается на систему мягких решений и поиск эквивалентных кодов после упорядочения статистики этих решений по убыванию. Неоднозначность перехода к возможному применению эквивалентного кода из-за не выполнения условий сохранения* нелинейности порождающих матриц обеспечивает значение корректирующего множителя в выражении асимптотической границы в пределах от 0,7 до 0,8, при этом повышается сложность процесса декодирования.

3. Применение метода кластерного анализа к процедуре составления списка позволяет достичь верхней границы для двоичных кодов при условии точного определения номера кластера. Зашита номера кластера может выполняться несколькими способами. Наиболее эффективным следует считать метод выделения группы наиболее надежных символов в кодах с циклической структурой или выделение специальных позиций в кодовой комбинации из числа младших разрядов координат, которые определяются приемником как стирания в канонической структуре кода.

4. Применение способа защиты кластера позволяет снизить сложность процесса декодирования за счет надежного определения номера кластера и перехода к укороченным кодам с выделением корректирующего вектора и вычисления вектора ошибок. Снижение вычислительных затрат обеспечивается за счет понижения порядка определителей в процедуре поиска эквивалентного кода, отвечающей заданной упорядоченной статистики.

5. Использование в системе связи недвоичных кодов позволяет отказаться от оценки эквивалентности кода в силу обязательного выполнения для таких кодов условий максимально декодируемых кодов. Вместе с этим, процедура вычисления обратной матрицы для переставленной матрицы остается актуальной и для таких кодовых конструкций. Применение упорядоченной статистики для кодов РС обеспечивает уменьшение общего числа операций сложения в двоичном поле заданной степени расширения. Это позволяет расширить диапазон вводимой в код избыточности при построении адаптивных систем связи.

ГЛАВА 41 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ РАЗРАБОТАННЫХ АЛГОРИТМОВ И ОЦЕНКА ИХ ЭФФЕКТИВНОСТИ МЕТОДОМ СТАТИСТИЧЕСКОГО МОДЕЛИРОВАНИЯ.

4.1 Принципы и алгоритмы построения модели системы связи.

Машинное моделирование процессовпроисходящих в реальных системах связи, широкие возможности современных программных средств и. средств вычислительной техники по реализации новых алгоритмом функционирования декодеров, позволяют получить надежные результаты для оценки конкретных технических решений, получаемых в ходе модификации известных схем декодирования помехоустойчивых кодов: Именно такие модели в свое время позволили выявить положительные особенности перспективных схем турбокодов и схем многопорогового декодирования [51, 52, 79^ 80, 86, 88, 91, 112].

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

По совокупности классификационных признаков имитационнаямодель может быть охарактеризована как стохастическаяалгебраическая, дискретная, оценочная, динамическая и. многоэтапная. Она соответствует всемосновным принципам моделирования, определяющим построение математических моделей [63, 88]. Особенно важным является модульность построения, которая позволяет использовать накопленный опыт реализации типовых элементов, модулейприразработке сложных моделей систем связи.

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

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

С помощью разработанной имитационной модели" системы связи, включающей элементы подсистемы с помехоустойчивым кодированием, проведено исследование, целью которого являлось получение вероятностных характеристик оценки и" сравнения полученных результатов с известными при следующих исходных параметрах моделирования:

— заданной структуре и алгоритме работы турбокодера-декодера- -источник входного сигнала — случайный источник, Бернулли- -канал АБГШ с постоянными параметрами;

— заданный, набор входных данных, определяемый в виде информационного вектора X = {дс, х2,., д-и}.

В соответствиис задачей моделирования разработан алгоритм работы имитационной модели, представленный на рис. 4.1, который определяет совокупность входных и выходных характеристик системы, правила взаимодействия элементов имитационной модели и механизмы продвижения модельного времени.

Начало 1 г Ввод исходных данных: StopTime, Ts, m, Niter, EbN0, punkt. y г, k, GJGZ. P0.

Выполнение подпрограммы тепи1. ш iter=0- time=0- BERlter=0- d=1/(2*m*r*10A *(EbNo/10)).

Формирование вектора информации: X (Ts, k, P0)=x1, Xj^-.X^- time=time+1.

Формирование Турбокода: X1=X*G1- X2=interliv (X*G2) — X=punktT*MUX (X, X1, X2) 6.

Модуляция и добавление шума: Х=(1−2*Х)Л5ЯП (т) — У=Х+п (с1).

Нормирование Lc=4*r*10A (EbN0/10) — L (uk)=0.

Декодер 1 lter=lter+1- Le1(uk)=ln (Pr (uk=+1)/ /Pr (uk=-1)) — L1k=L (uk)+Lc*yk+Le1(uk).

Декодер 2 L (uk)=interliv (L1k) — Le2(uk)=ln (Pr (uk=+1)/ /Pr (uk=-1)) — L2k=L (uk)+Lc*yk+Le2(uk).

Деперемежение L (uk)=deinterliv (L2k).

Формирование результатов Y*=sign (L (uk));

BER,.er=f (x.Y*);

BER=sum (BER1, ter)/ /iter.

12 —.

Вывод результатов:

Y, BER, alBK.

Нет.

Рис. 4.1. Алгоритм работы имитационной модели системы связи с использованием параллельного турбокода.

Основные возможности и параметры разработанной модели представлены в таблице 4.1. В таблице через ВЕЯ обозначается вероятность ошибки на бит.

ЗАКЛЮЧЕНИЕ

.

В ходе проведенных исследований установлено.

1. Использование средств помехоустойчивого кодирования в перспективных системах связи в условиях динамично развивающихся средств цифровой обработки сигналов неразрывно связывается с методами мягкой обработки кодовых комбинаций, а применение списочного декодирования оправдано в условиях высокого уровня помех. Подобные декодеры обеспечивают минимальную сложность реализации при заданной вероятности ошибки. Большинство методов подобной обработки кодовых комбинаций помехоустойчивых кодов оперирует образцами ошибок, позволяющих выделить подмножество тех кодовых комбинаций, которые с высокой вероятностью включают в себя переданный по каналу с помехами вектор. В отличие от традиционных методов списочного декодирования способ кластерного анализа оперирует с наиболее надежными символами, что позволяет ускорить процесс составления списка за счет определения номера кластера.

2. Большинство способов выработки градаций надежности символов разрабатывались для решения отдельных локальных задач мягкого декодирования блоковых и сверточных кодов, либо являлись развитием алгоритмов обработки избыточных кодов в стирающем канале связи. Для сравнения свойств известных схем образования целочисленных ИДС и разработанного метода предложен коэффициент правдоподобия (отношение вероятности совпадения конкретной оценки с правильными решениями к вероятности ошибочного решения для той же оценки). Методом аналитического моделирования решающей схемы приемника определена верхняя граница коэффициента правдоподобия. Доказано преимущество модифицированной схемы формирования стираний и производство вычислений на этой основе ИДС функционально не зависящих от отношения сигнал-шум в канале связи.

3. Оценка асимптотических возможностей двоичных блоковых кодов по исправлению стираний указывает на имеющийся резерв в получении дополнительного энергетического выигрыша при полном использовании потенциальных возможностей введенной в код избыточности. Доказана способность корректирующего кода обеспечить дополнительный энергетический выигрыш (от 0,5 до 1 дБ в зависимости от параметров кода) относительно системы с мягким декодированием за счет упорядочения статистики ИДС по убыванию. Показано, что наибольший эффект достигается на скоростях кода близких к 0,5, а число неудачных исходов при оценке свойств нелинейности эквивалентных кодов составляет около 30% от общего числа перестановок столбцов порождающей матрицы кода.

4. Применение метода кластерного анализа к процедуре составления списка позволяет достичь верхней границы для двоичных кодов при условии точного определения номера кластера. Защита номера кластера может выполняться несколькими способами. Наиболее эффективными следует считать метод выделения группы наиболее надежных символов в кодах с циклической структурой или выделение специальных позиций в кодовой комбинации из числа младших разрядов координат, которые определяются приемником как детерминированные стирания в канонической структуре кода. Предложен способ защиты номера кластера путем оценки числа циклических сдвигов групп символов, имеющих надежные ИДС в пределах кодового вектора, что обеспечивает по асимптотическим оценкам дополнительный энергетический выигрыш относительно мягкой схемы декодирования от 1 до 3 дБ.

5. На основе комплекса имитационных моделей проведено исследование различных схем списочного декодирования применительно к системам с ортогональным частотным разделением каналов. Показаны преимущества кодов произведений размерности ЗО относительно традиционных схем декодирования как блоковых, так и непрерывных кодов.