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

На современном этапе развития средств телекоммуникаций является актуальной проблема повышения производительности систем связи, включающая в себя проблемы ^ повышения скорости и качества передачи данных. Эти характеристики систем связи обратно пропорциональны друг другу. С увеличением скорости передачи данных теряется качество передаваемой информации и наоборот. Это связано с присутствием во всех каналах передачи данных различного рода шумов, оказывающих определенное влияние на целостность передаваемой информации [14]. Существует общий для всех каналов передач шум — аддитивный шум [1−19], возникающий уже внутри устройств приема данных. Не менее важной характеристикой канала связи является доступная ширина полосы частот канала, обусловленная физическими ограничениями среды и параметров электрических компонентов системы. Для выделения сигнала из канала с шумом существует широкое множество решений. Во-первых, это повышение качества передающей и принимающей аппаратуры, аналоговое подавление помех, увеличение мощности сигнала и т. д. Во-вторых, это разнообразные способы кодирования * информации на выходе для обнаружения или исправления случайных искажений сигнала на приемном конце, называемые помехоустойчивым кодированием. Помехи существуют во всех используемых каналах связи [1−13]. Проводные каналы (коаксиальный кабель, витая пара и т. д.) подвержены искажению фаз и амплитуд и ограничены довольно низкой полосой пропускания — порядка десятков МГц. Волоконно-оптические каналы [7] - менее всего подвержены влиянию помех, которые в основном связаны с затуханием светового сигнала на больших расстояниях. Оптоволоконные каналы имеют полосу пропускания на несколько порядков больше, чем проводные каналы связи. Акустические каналы связи — наименее распространены, причина этого — сильная подверженность искажениям и шумам, низкая скорость распространения и ограниченная полоса пропускания. Особое внимание заслуживают беспроводные или радио каналы связи, где характеристики передачи данных напрямую зависят от рабочего диапазона частот. В системах беспроводной связи (радиосвязи) электромагнитная энергия передается в среду распространения излучающей антенной, j, чьи формы и размеры определяются в зависимости от диапазона передаваемых частот.

Частотным диапазоном определяются также и свойства канала передачи.

Наиболее производительными в области передачи информации являются системы спутниковой связи [8], получившие за последние годы широкое применение за счет стремительного развития космической индустрии (появление большого количества коммерческих спутников и как результат — снижение общей стоимости использования спутниковых средств связи). Подобные системы, предназначенные для высокоскоростной связи, сталкиваются с проблемой качества принятой информации, т.к. очевидно, что на сигнал, транслируемый через спутник влияют множество шумовых факторов. Это аддитивный шум, гашение сигнала в облачную погоду, прохождение его через ионосферу, влияние посторонних источников излучений и т. д. Вместе с тем спутниковый канал не должен допускать повторную передачу информационного пакета в случае обнаружения ошибки, как это реализовано в проводных и оптоволоконных системах связи, иначе это пагубно скажется на производительности, себестоимости и общих характеристиках такой системы. Следовательно для спутниковых систем необходимо использование высокопроизводительных средств обеспечения помехоустойчивости. Самым оптимальным решением для таких систем на сегодняшний день является использование сверточных кодов [1−402,2−222], обладающих высокой корректирующей способностью и сравнительной простотой функциональной и аппаратной реализации. Существует целый ряд способов декодирования сверточных кодов: оптимальное декодирование (алгоритм Витерби) [1−413], коды Рида-Соломона, и т. д. Однако, если уровень шума, а следовательно количество ошибок в принимаемой последовательности высоко (>10″), — кодовое ограничение для таких каналов так же должно быть большим — в данной ситуации наиболее подходящим методом является последовательное декодирование, работающее с кодами любой длины и большим количеством ошибок на входе.

Среди различных алгоритмов последовательного декодирования сверточных кодов (стек-алгоритм, алгоритм декодирования с обратной связью) выделяется алгоритм Фано [1−428,2−305]. Данный алгоритм не требует громоздких операций, — как переупорядочивание стека для стек-алгоритма — и не требует большого объема памяти, как для алгоритма декодирования с обратной связью. Все операции, реализуемые этим алгоритмом просты, и приемлем объем памяти, требуемый для его эффективной работы.

В свете развития высокопроизводительных средств вычислительной техники [10], появления высокоскоростной, экономичной, компактной и надежной элементной базы, предназначенной для конструирования различных средств вычислительной техники — ПЛИС (Программируемых логических интегральных схем), сопровождаемых удобными и производительными САПР, проблема реализации данного алгоритма в устройствах помехоустойчивой связи на сильно зашумленных каналах передач данных представляется наиболее актуальной.

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

1. Исследованы способы помехоустойчивого декодирования и проведен анализ их основных характеристик, применительно к кодированным информационным потокам с величиной вероятности ошибки на бит, принятой от 0,001 до 0,01 и кодовым ограничением от 58 до 128 кодовых символов. Исследованы известные алгоритмы последовательного декодирования сверточных кодов, что позволило разработать способы повышения их производительности.

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

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

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

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

6. Разработаны методики тестирования и технические требования к аппаратуре отладки устройства декодирования в системе помехозащищенной передачи данных.

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

Основные положения и результаты, выносимые на защиту.

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

2. Способ повышения производительности алгоритма Фано, основанный на модификации таблицы метрик, путем установки значений достоверного приема данных равными максимуму позволяет сократить количество итераций алгоритма при исправлении ошибки.

3. Результаты исследования имитационной модели алгоритма декодирования и сравнительный анализ полученных результатов дают возможность получить количественную оценку увеличения производительности алгоритма.

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

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

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

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

Реализация научно-технических результатов работы. Разработанные алгоритмы, результаты исследования математической модели, рекомендации по повышению производительности декодера внедрены в Ростовском НИИ радиосвязи в совместной работе «Разработка модуля ПУ-декодирования систематических сверточных кодов» — х/д 16 103. Результатом работы является опытный образец устройства последовательного декодирования систематических сверточных кодов использующий модифицированный алгоритм Фано. Данное устройство обладает следующими техническими характеристиками по быстродействию и качеству декодирования. В качестве элементной базы использовались ПЛИС фирмы Xilinx XC4036HQ240EX, работающие на тактовой частоте 40 МГц. Устройство способно производить декодирование информационного потока, с кодовыми скоростями ½, ¾ и 7/8, на скоростях информационного потока 2, 2 и 1 Мбит/с, при соотношении сигнал/шум в канале 3.4, 4.0, 5.0 дБ соответственно. Устройство оснащено вспомогательными интерфейсными модулями, позволяющими организовывать его работу как в составе системы приема данных на базе VME интерфейса, так и в составе персонального компьютера IBM через шину ISA. Разработанный пакет программного обеспечения, предназначенного для проведения типовых операций инициализации и контроля, делает устройство настраиваемым и диагностируемым в процессе загрузки и работы. Разработанный пакет программ и тестовых имитационных последовательностей, предназначенных для диагностики внутренних режимов работы устройства будет необходим при модификации устройства, переходе на новую элементную базу или другие скорости сверточного кода.

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

Апробация работы. Результаты исследований, приведенные в работе, докладывались на 46-й студенческой научной конференции (Таганрог, 1999 г.) [30]- 6-й международной конференции студентов и аспирантов (Москва, 2000 г.) [29]- V Всероссийской научной конференции студентов и аспирантов (Таганрог, 2000 г.) [31]- изложены в сборнике трудов научно-практической конференции «Информационная безопасность» (Таганрог, 2001 г.) [33]- межрегиональном семинаре с международным участием «Информационная безопасность'' (Таганрог, 2002 г.) [35]- изложены в специальном выпуске журнала «Известия ТРТУ» в разделе «Материалы XLVII научно-практической конференции» (Таганрог 2002 № 1(24)) [ ]- разработанный способ и программы зарегистрированы Свидетельствами об официальной регистрации программ для ЭВМ № 2 003 611 331 [41], № 200 361 1332 [40], № 2 003 611 333 [39], № 2 003 610 910 [42] (Роспатент. 2003 г.).

Публикации. По основным результатам опубликовано 11 работ.

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

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

Разработана имитационная модель устройства декодирования, позволившая получить Сравнительные оценки производительности стандартного и модифицированного алгоритма Фано. Результаты моделирования показали повышение скорости обработки кодовой последовательности модифицированным алгоритмом и метриками от 10% до 100%, позволяющее декодировать сверточный код с максимальной кодовой скоростью 7/8, без потерь общей производительности устройства.

Результаты проведенных исследований позволили провести сопровождение разработки, комплексной наладки устройства помехоустойчивого декодирования систематических сверточных кодов — ОКР для ростовского НИИ радиосвязи.