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

Таганрогский государственный радиотехнический университет

На правах рукописи

Бабенко Денис Викторович

ИССЛЕДОВАНИЕ И РАЗРАБОТКА СПОСОБОВ ПОВЫШЕНИЯ ПРОИЗВОДИТЕЛЬНОСТИ ПОСЛЕДОВАТЕЛЬНОГО ДЕКОДИРОВАНИЯ СВЕРТОЧНЫХ КОДОВ НА ПРИМЕРЕ АЛГОРИТМА ФАНО

л

05.13.13 — Телекоммуникационные системы и компьютерные сети 05.12.13 - Системы, сети и устройства телекоммуникаций

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Таганрог - 2003

Работа выполнена на кафедре безопасности информационных технологий (БИТ) Государственного образовательного учреждения высшего профессионального образования «Таганрогский государственный радиотехнический университет» (ТРТУ).

НАУЧНЫЙ РУКОВОДИТЕЛЬ: доктор технических наук,

ВЕДУЩАЯ ОРГАНИЗАЦИЯ: Федеральное Государственное унитарное предприятие

Ростовский научно-исследовательский институт радиосвязи (ФГУП РНИИРС)

V

Защита состоится «19» декабря 2003 г. в 1430

на заседании диссертационного совета Д212.259.05 при Таганрогском государственном радиотехническом университете

по адресу: 347928, г. Таганрог, ул. Чехова, 2, корп. «И», комн. 347. С диссертацией можно ознакомиться в библиотеке ТРТУ.

Просим Вас прислать отзыв, заверенный печатью учреждения по адресу:

347928, г. Таганрог, Ростовская область, ГСП-17А, пер. Некрасовский, 44,

Таганрогский государственный радиотехнический университет

Ученому секретарю диссертационного совета Д212.259.05 Кухаренко А.П.

Автореферат разослан « »_2003 г.

Ученый секретарь диссертационного совета кандидат технических наук,

профессор

Макаревич Олег Борисович

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ:

доктор технических наук, профессор

Макаров Анатолий Михайлович (Пятигорский государственный технологический университет) кандидат технических наук, доцент

Букатов Александр Алексеевич (Вычислительный центр ростовского государственного университета)

доцент

А.П.Кухаренко

ОП1ЦЛЯ ХАРАКТЕРИСТИКА РАВОГЫ

Актуальность проблемы 11а современном этапе развития средств телекоммуникаций пробзема повышения производительности систем передачи данных, включающая в себя проблемы повышения скорости и качества передачи данных является актуальной Эти два основных нараме|ра споем передачи обратно пропорциональны друг другу С увеличением скорости передачи данных терне1ся качество передаваемой информации и наоборот Это связано с присутствием во всех телекоммуникационных системах различного рода шумов Существует общий для всех каналов передач шум - аддитивный шум, возникающий внутри устройств передачи и приема данных Для выделения сигнала из канала с шумом существует широкое множество решений Во-первых, это повышение качества передающей и принимающей аппаратуры, аналоговое подавление помех, увеличение моншосш сигнала и тд Во-вторых, это разнообразные способы кодирования информации для обнаружения ипн исправления случайных искажений сигнала на приемном конце, называемые помехоустойчивым кодированием Помехи существуют во всех используемых каналах передачи информации, поэтому актуальность проблемы исправления ошибок, возникших под влиянием помех, является очевидной

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

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

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

В результате развития средств вычислительной техники, появилась высокоскоростная, экономичная, компактная и надежная элементная база, предназначенная для конструирования различных средств вычислительной техники - ПЛИС (Программируемые логические интегральные схемы), сопровождаемые удобными и производительными средствами автоматизированного проектирования (САПР) В связи с эгим, проблема реализации лаш ofo-fUH4i|>nTMa п его модификаций в устройствах

РОС НАЦИОНАЛЬНАЯ БИБЛИОТЕКА

помехоустойчивой передачи данных на сильно зашумленных каналах передач данных предсивляется весьма актуальной

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

Основные задачи, решенные в работе для достижения данной цели.

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

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

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

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

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

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

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

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

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

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

алгоритма, аппаратной реализации и элементной базы устройства Основные положения и результаты, выносимые на защиту

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

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

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

- - *» W-

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

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

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

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

Реализация научно-технических результатов работы Разработанные алгоритмы, результаты исследования математической модели, рекомендации по повышению производительности декодера внедрены в Ростовском НИИ радиосвязи в совместной работе "Разработка модуля ПУ-декодировання систематических сверточных кодов" - х/д 16103. Результатом работы является опытный образец устройства последовательного декодирования систематических сверточных кодов использующий модифицированный алгоритм Фано Данное устройство обладает следующими техническими характеристиками по быстродействию4 и качеству декодирования В качестве элементной базы использовались ПЛИС фирмы Xilinx XC4036HQ240EX, работающие на тактовой частоте 40 МГц Устройство способно производить декодирование информационного потока, с кодовыми скоростями 1/2, 3/4 и ,7/8, на скоростях информационного потока 2, 2 и 1 Мбит/с, при соотношении сигнал/шум в канале 3 4, 4 0, 5 0 дБ соответственно Устройство оснащено вспомогательными интерфейсными модулями, позволяющими организовывать его работу как в составе системы приема данных на базе VME интерфейса, так и в составе персонального компьютера IBM через шину ISA Разработанный пакет профаммною обеспечения, предназначенного для проведения типовых операций инициализации и контроля, делает устройство настраиваемым и диагностируемым в процессе загрузки и работы Разработанный пакет программ и тестовых имитационных последовательностей, предназначенных для диагностики внутренних режимов работы устройства будет необходим при модификации устройства, переходе на новую элементную баз; или другие скорости сверточного кода

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

Апробация работы Результаты исследований, приведенные в работе, докладывались на 46-й студенческой научной конференции (Таганрог, 1999 г.) [2]; б-й международной конференции студентов и аспирантов (Москва, 2000 г.) [1], V Всероссийской научной конференции студентов и аспирантов (Таганрог, 2000 г.) [3], изложены в сборнике трудов научно-практической конференции «Информационная безопасность» (Таганрог, 2001 г) [4]; межрегиональном семинаре с международным участием "Информационная безопасность" (Таганрог, 2002 г.) [5], изложены в специальном выпуске журнала «Известия ТРТУ» в разделе «Материалы XLVII научно-практической конференции» (Таганрог 2002 № 1(24)) [6], разработанный способ и программы зарегистрированы Свидетельствами об официальной регистрации программ для ЭВМ № 2003611331 [8], № 2003611332 [9], №2003611333 [10], № 2003610910 [11] (Роспатент, 2003 г.)

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

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

СОДЕРЖАНИЕ РАБОТЫ

В первой главе приводится сравнительная характеристика существующих способов помехоустойчивого декодирования относительно декодирования сверточных кодов Исследуются линейные блоковые колы, (Хэмминга, циклические коды и др) с целью определения границ своей применимости Показана необходимость применения сверточных кодов в телекоммуникационных системах, использующих спутниковые каналы передачи данных

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

Исследования основных методов помехоустойчивого декодирования сверточных кодов алгоритм Витерби, коды Рида-Соломона, Стековый алгоритм и алгоритм Фано позволили оценить и\ основные характеристики

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

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

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

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

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

Рис. 1. Алгоритм итерации Фано В последнем параграфе первой главы дана общая оценка производительности алгоритмов, исходя из рассматриваемых условий высокого уровня шума (порядка 2,5 - 3 дБ) с вероятностью ошибки на бит >103, кодового ограничения, превышающего 20 бит. В этих условиях алгоритм последовательного декодирования Фано способен производить декодирование кодовой последовательности, обеспечивая предельно низкое количество ошибок на выходе ^Ю"4) Эти характеристики алгоритма Фано делают его применимым в различных системах спутниковой передачи данных, с наличием'высокого уровня шумов Это дальняя космическая связь, системы передачи данных в сильно зашумленных каналах связи, некоторые виды систем факсимильной передачи данных и др

Алгоритм Фано успешно применяется в различных системах передачи данных Его качество по вероятности ошибки сравнимо с декодированием по алгоритму Витерби Однако, несмотря на сравнительно большую задержку алгоритма Фано, он требует меньше памяти и, следовательно, является незаменимым инструментом для декодирования сверточных кодов с большим кодовым ограничением Основным его преимуществом над кодами Рида-Соломона является возможность исправления пакета ошибок, глубина которого по результатам программного и аппаратного моделирования может достигать 4 подряд идущих инвертированных бит.

Данный алгоритм обладает наилучшими показателями по производительности и исправляющей способности в описанных ситуациях Однако его быстродействие напрямую зависит от скорости кода, так как он ориентирован на последовательное декодирование, те. на обработку всех ветвей текущего узла кодового дерева (те. текущего символа канала) К примеру, для скоростей кода 1/2, 3/4 и 7/8 на каждом шаге алгоритм должен обрабатывать 2, 8 и 128 ветвей соответственно для выбора единственного

оптимального пути По примерным оценкам для скорости кода 7/8 декодирование будет давать значительную задержку каллою символа С другой стороны ал гори im должен, учитывая весь спектр мягкого решения, формировав метрику, полностью определяющую принятый символ канала Учитывая, что данные предположительно передаются по каналу с ненулевой вероятностью ошибки на бит, соот ветс i ву юшие значения метрик для безошибочной информации будут меньше максимальных, следовательно, возможно наличие задержек процесса декодирования

Анализ приведенных ситуаций, показал на необходимость нахождения путем повышения проншо.штелыюстн данного алгоритма в этих случаях. Проведенные исследования алгоритма в данных ситуациях на лршраммной модели указали на такие возможности путем изменения самого алгоритм н модификации таблицы метрик. Модификация алгоритма основано на отказе от полного перебора исследуемых ветвей на "чистых" отрезках кодовой последовательности для больших скоростей кода Это приведет к увеличению быстродействия алгоритма на таких отрезках по приблизительным оценкам от 20 до 60% и, учитывая относительно небольшое предполагаемое количество ошибок в канале передачи данных, составляющее примерно 101 вероятности ошибки на бит для скоростей кода порядка 7/8, привезет к общему повышению его производительности Модификация метрик ветвей основана на присвоении всем метрикам безошибочных данных (данное определяется алгоритмом как ошибочное по несовнадешно принятого и вычисленного контрольных разрядов) максимального значения, что сушеывенио сократит общее количество итераций алгоритма и так же приведет к повышению его производительности Рассмотрены возможности реализации способов повышения производительности в алгоритмах последовательного декодирования Стек-алгоритм и алгоритме Фано Алгоритм Фано взят за основх для дальнейших разработок, по результатам сравнительного анализа приведенных последовательных алгоритмов

Вторая глава включает в себя исследование алгоритма последовательного декодирования систематических сверточных кодов Фано и разработки путей повышения его производительности Разработано два способа повышения производительности алгоритма первый основан на модификации самого алгоритма для скорости кода 7/8, второй - на модификации таблицы метрик Для обоснования целесообразности внесения изменений в таблицу метрик, проведено изучение влияния аддитивною шума на поток кодированных данных и описан характер возникающих вследствие данного воздействия ошибок

Описанные особенности последовательного алгоритма Фано и особенности его реализации выявили возможность повышения его производительности Рассматривая работу алгоритма на кодовом потоке, представленном мягким решением, отмечено, что при продвижении вперед метрика пути (сумма метрик ветвей), увеличивается на величину тем большую, чем меньше уровень шума в канале и, соответственно, чем выше метрика ветвей, те принимаемых символов канала При исправлении ошибки, декодер, в соответствие с базовым алгоритмом Фано, должен вернуться к моменту предыдущего увеличения порота, те вернуться назад на количество шагов, соответствующее количеству принятых символов канала Соответственно, чем ниже общая метрика ветвей этого пути, тем на большее количество шагов алгоритму необходимо вернуться и тем большее время он затратит иа исправление возникшей ошибки Обойти приведенную ситуацию можно путем модификации таблицы метрик Изменения, вносимые в эту таблицу, должны быть направлены на увеличение значений метрик, соответствующих приему безошибочных данных, до максимального значения Это повлечет сокращение общего количества шераипй последовательного алюритма Фано на промежутках между моментами наращения порога метрик, а так же при откате назад по кодовому дереву в процессе исправления ошибок Некоторое уменьшение исправляющей способности компенсируется уменьшением среднего времени декодирования одного символа канала при использовании ограниченного объема буферной памяти устройства Данная модификация дает сокращение общего количества итераций алгоритма, затрачиваемых на исправление ошибки, которое по предварительным расчетам составило от 5 до 20 %

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

На рис 2 расположены графики изменения метрики пути М в процессе исправления ошибки Горизонтальная ось соответствует количеству итераций алгоритма Отрезки «Предл» и «стандарт» соответств\ют режимам работы алгоритма в предлагаемом и известном режимах работы Величины Di, Dj, Di - соответствуют дискретным значениям порога декодирования, различающиеся на uiai изменения порога - d„

На обоих графиках сначала декодирование идет без ошибок При этом метрика модифицированного варианта (см рис 2а) увеличивается быстрее обычного (см рис 2 6) После возникновения ошибки, декодер переходит в режим классического декодирования в соответствие с алгоршмом Фано, с

сохранением предложенной модификации метрик. Возникшая вследствие появления ошибки отрицательная метрика заставляет декодер путем последовательных шагов назад вернуться к момент) предыдущего повышения порога, чтобы понижением порога скомпенсировать возникшую отрицательную метрику. Метрика начинает уменьшаться до момента предыдущего увеличения порога Когда порог уменьшается на величину своего приращения с1>, появились условия для нормального декодирования и продвижения декодера вперед Повторно дойдя до ошибки при пони/кенном пороге, декодер начинает перебирать возможные варианты, стремясь путем перебора отыскать метрику, соответствующую исправленной ошибке Здесь возникает очередь из последовательных шагов вперед и назад декодера, количество которых для скорости кода 7/8 может варьироваться от 1 до 127. После того как декодер нашел нужную ветвь и исправил ошибку - отрицательная метрика ветви, соответствующей исправленной ошибке уменьшает общую метрику пути, которая начинает постепенно возрастать, и после превышения текущего уровня порога декодирования активируется предложенный режим и декодер возвращается к производительному декодированию последовательности

Величина <1ц соответствует выигрышу во времени, полученному от использования предложенного варианта модифицированных метрик.

При данном кодовом ограничении, в расчете контрольного разряда одновременно принимают участие 91 информационных и 13 контрольных бит. Учитывая, что принятая вероятность ошибки в последовательности - 0,001, среднее количество шагов на исправление одиночной ошибки - 25 (данные нрог раммнои модели) и дополнительное количество шагов до момента входа алгоритма в «быстрый» режим составляет в среднем 130-140 итераций Накопленная за время исправления ошибки информация во входном буфере (БСК), составляет примерно 25/8 * 3, тк. символы канала принимаются с демодулятора последовательно, а декодер формирует параллельный код Таким образом, области полного перебора всех ве1вей (исправление ошибки) занимает 10-15% всей кодовой последовательности Очевидно, что этот показатель является достаточно приемлемым для дальнейшей аппаратной реализации алгоритма

а )

стандарт

Рис 2 Последовательность, операций декодера в процессе исправления ошибок а) известным алгоритмом Фано б) алгоритмом Фано, использующим предложенный способ

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

Рассматривая работу помехоустойчивого алгоритма декодирования систематических сверточных кодов Фано, обрабатывающего данные, представленные мягким решением, отмечено, что, выполняя обработку потока со скоростью кода г=7/8, тратит большое время на полный перебор ветвей (вариантов комбинаций входного потока) при поиске ветви с максимальной метрикой (вероятностью правильного сочетания бит) Это существенно сказывается на быстродействии устройства, тк основной задачей ал| оритма является именно нахождение ветви с максимальной метрикой На скорости кода 7 8 алгоритм

работает тогда, когда вероятность ошибки в канале передачи данных заведомо мала (порядка КГ1, 10"'), на основе этой особенности применения алгоритма был разработан первый метод повышения его производительности

Исследования алгоритма на программной модели и математические расчеты, показали, что на скорости кода 7/8, где количество ветвей полного перебора составляет N=27=128, а предполагаемая вероятность ошибки - Р=0,001, можно отказаться от полного перебора ветвей на «чистых» отрезках информационного потока (ошибки распределены равномерно в потоке), обрабатывая только одну ветвь, соответствуют) ю текущему символу канала, до тех пор, пока ее метрика не станет отрицательной (что индиинрует появление ошибки в потоке), затем осуществляется переход к полному перебору ветвей в каждом последующем узле, до полного исправления ошибки, о чем будет сигнализировать повышение порога метрики пути (метрики всей правильно декодированной последовательности) В данной модели был исследован сверточный код 7/8, с кодовым ограничением 91.

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

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

Таким образом, предложенные модификации таблицы метрик, основанные на особенностях воздействия АБГШ на информационную последовательность и модификация алгоритма последовательного декодирования Фано, дают сокращение общего количества итераций алгоритма в процессе исправления ошибок, а, следовательно, общее повышение производительности декодера, основанного на алгоритме Фано, составит от 15 до 80*/«.

Результаты исследований основных характеристик каналов передач, применительно к условиям передачи данных показали, что оптимальными по показателям избыточности и исправляющей способности являются кодовые скорости 1/2, 3/4 и 7/8. Эти же скорости кода являются и наиболее популярными в современных системах сверточного кодирования. Скорость кода 3/4 является оптимальной по основным параметрам для аппаратной реализации числа ветвей (2,=8) и обеспечивает достаточную скорость информационного потока (3/4=0,75)

Для определения поведения метрик ветвей и общей метрики пути было проведено детальное итерационное моделирование алгоритма на канале с АБГШ. Исследования процесса влияния метрик на работу алгоритма в данных условиях выявили ею основные особенности Был тщательно и исследован сам процесс исправления случайной ошибки для скоростей кода 1/2, 3/4, и 7/8 и его зависимость от заданного набора метрик В результате обнаружен ряд неоптимальных итераций алгоритма на этапах продвижения вперед по зашумленной информационной последовательности ("чистые" отрезки последовательности) и ряд возвратов назад по последовательности (этапы исправления возникших ошибок) Выяснено, что при наличии шума, но отсутствии ошибок в канале, наращивание метрики пути на каждой итерации происходит па величину, значительно меньшую, чем на аналогичном канале без шума Следовательно, на исправление случайной ошибки уходит гораздо большее количество возвратов, производимых до момента предыду uici о наращения величины порога, так как сама величина приращения порога - постоянная Если модифицировать таблицу стандартных метрик таким образом, чтобы в случае отсутствия ошибки, т е при наличии положительной метрики ее величина всегда была бы максимальной, то декодер будет затрачивать на исправление одной ошибки минимальное количество возвратов, а следовательно общее время исправления ошибки станет значительно меньше. После проведенной модификации стандартной таблицы метрик устранены потери производительности работы алгоритма на этапах обнаружения и исправления случайной ошибки в кодовой последовательности Оценки производительности алгоритма, использующего модифицированную таблицу метрик на математической модели, показали значительное возрастание ею производительности и устойчивости Небольшая потеря исправляющей способности компспсирусия уменьшением среднего времени обработки одного символа канала

В приведенном алгоритме за счет разработанных модификаций достигается чвелнчение производительности алгоритма на "чистых" отрезках кодовой последовательности, которые по результатам проведенных исследований составляют большую часть принимаемой последовательности для больших скоростей кода, порядка 7/8 Это позволяет создать высокоскоростное устройство декодирования сперточных кодов с кодовой скоростью 7/8 на элементной базе декодеров для скорости кода I '2 и 3/4 без дополнительных модификации аппаратной части.

Рис 3. Модифицированный алгоритм Фано

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

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

После проверки соответствия модели модифицированному алгоритму был проведен этап сравнительной оценки производительности стандартной и модифицированной моделей Основным показателем разницы в производительности служило количество итераций, пройденных моделями при скорости кода 7/8 Подсчитывалось общее количество итераций для стандартного алгоритма и количество обычных и «быстрых» итераций - для модифицированного алгоритма Выигрыш в производительности на данном этапе оценивался, во-первых, в соотношении общего количества итераций стандартного алгоритма к сумме стандартных и «быстрых» итераций модифицированногои, во-вторых, в отношении количества «быстрых» итераций к общему их количеству модифицированного алгоритма Еще одним важным параметром быстродействия является среднее количество итераций, затраченное обоими алюритмамн на исправление одной ошибки Суммарная оценка всех перечисленных показателей демонстрирует сравнительные характеристики производительности процесса декодирования кодового потока

Сравнительные оценки увеличения быстродействия конкретного устройства на данном этапе могут быть получены только приблизительно, но, следуя логике работы алгоритма, они оценивались следующим образом Для скорости 7/8 последовательность основных операций работы устройства на одном шаге декодирования можно выразить так чтение символа канала из БСК, подготовка декодера к перебору 128 ветвей текмпею узла кодового дерева Затем выполняется шаг вперед или назад, в соответствии с алгоритмом, где выбранная ветвь или записывается в БИП и происходит переход вперед, либо происходит шаг назад Таким образом, видно, что наибольшей частью алгоритма является именно обработка перечня 128 ветвей кодового дерева на каждом шаге без режима «быстрого» декодирования По примерным оценкам разница во времени выполнения «быстрого» и стандартного шага вперед алгоритма составляет от 60 до 80°'о времени, что может служить значительным выигрышем в производительности алгоритма, реализованного в конкретном устройстве

Сравнительная оценка сведена в табл I

Результаты

таботы программной модели

ТАБЛИЦА I

R 1/2 3/4 7/8

[■ 0,01 | 0,01 | 0,001 0,02 | 0,01 | 0,001 0,01 | 0,005 | 0,001

QStcp Мод метр Кол-во итераций в режиме Qstep

IX IL есть 6435 7791 8150 2134 2352 2689 1235 993 1119

СсТЬ нет 6224 7799 8203 2074 2275 2694 1134 944 1195

НС 1 есть 11800 8394 8368 4521 3409 2732 2430 1599 1344

НСГ нет 11930 8465 8404 4615 3466 2736 2547 1682 1417

QStcp Мод метр Кол-во итераций в обычном режиме

есть CCI L есть 5932 763 83 2289 1074 71 1345 691 80

нет 6175 833 86 2364 1151 74 1451 762 81

нет нет есть 0 0 0 0 0 0 0 0 0

нет 0 0 0 0 0 0 0 0 0

QStcp Мод метр Общее количество итераций

ее ri. есть 12367 8554 8233 4423 3426 2760 2580 1684 1199

есть нет 12399 8632 8289 4438 3426 2768 2585 1706 1276

HCt есть 11800 8394 8368 4521 3409 2732 2430 1599 1344

ист нет 11930 8465 8404 4615 3466 2736 2547 1682 1417

OSlep Мод метр Отношение общего количества итераций к итерациям Qstep

есть есть 0,52 0,91 0,99 0,48 0,69 0,97 0,48 0,59 0,93

есть нет 0,50 0,90 099 0,47 0,66 0,97 0,44 0,55 0,94

QStcp есть Мод метр Увеличение производительности

есть 1,02 1,09 1,13 1,15 1,17 1,23 1,38 1,55 2,69

есть пег нет 1.01 1,08 1,13 1.15 1,17 1,23 1.34 1.48 2,53

есть 1 01 1 01 1,00 1,02 1,02 1,00 1,05 1,05 1,05

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

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

Скорость кода 3/4 характеризует большее, по сравнению с 1/2, количество операции, затрачиваемых устройством на обработку одного символа канала Те время итерации в режиме QStep, и в стандартном режиме отличаются уже на 0,8 (на основании данных аппаратной реализации устройства) По причине большего числа бит в символе канала, модификация таблицы метрик становится более приемлемой для данной скорости кода Отсюда имеем существенное увеличение общей производительности устройства при использовании режима QStep и модифицированной таблицы метрик Производительность так же возрастает при уменьшении уровня шума в канале передачи данных

Использование данных режимов является основной целью для скорости кода 7/8 Данная скорость кода отличается от остальных значительными затратами времени обработки одного символа канала, что связано с необходимостью обработки всего перечня ветвей узла кодового дерева Для этой скорости кода все разработанные модификации являются оптимальными в плане выигрыша времени от использования итераций в режиме QStep и уменьшения количества итераций от использования модифицированной таблицы метрик По данным аппаратной реализации относительное время выполнения одной итерации QStep для шагов декодера вперед и назад при данной скорости кода составляет менее 0,4 Это является основным фактором увеличения производительности работы устройства декодирования Второй фактор -применимость сверточных кодов со скоростью 7/8 на каналах передачи данных с достаточно низким уровнем шумов (вероятность ошибки порядка 0,001) Это обеспечивает преобладание количества итераций QStep над обычными Отсюда максимальное увеличение производительности устройства при низком уровне шумов

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

Четвертая глава посвящена разработке методик отладки и тестирования телекоммуникационной системы при реализации разработанного алгоритма помехоустойчивого декодирования систематических сверточных кодов

Показано, что на основании особенностей внутренней организации, основных принципов работы и применение ПЛИС (FPGA) в качестве элементной базы, проектируемого устройства, является оптимальным по параметрам производительности, себестоимости, аппаратных затрат, затрат на проектирование и гибкости в применении в различных телекоммуникационных системах

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

Основная структура декодера представлена на рис. 4.

ДМ — демодулятор, БСК — буфер символов канала; УУ — устройство управления, Д — декодер, К" — кодер, БИП — буфер выходной информационной последовательности

Aiiaiofoiwii Днсърстнын Cnu.onu Демдчро.акн.» Выходи»,

поток „.,„,, канала

поток последователь- посчсдоватсль*

данных данныч HOCTV ность

ПС

дм

во

Пршиакм in Команды для

| бЛОКО»| | ÖIOKOBj.

номер ветви I

кд

про*

разряд

т. /т

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

ТАБЛИЦА 2

Скорость кода Скорость входного потока (МГц)

Для классического варианта Для модифицированного

1/2 11.4 20 v

3/4 42 8

7/8 03 4,7

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

Однако, предлагаемая модификация алгоритма для скорости кода 7/8, позволяет на безошибочных входных потоках достигать скорости сравнимой со скоростью декодера на 1/2.

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

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

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

С помощью разработанных программных средств произведена общая опенка производительности декодера и его исправляющая способность

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

С помощью разработанных программных средств произведена обшая оценка производительности декодера и его исправляющая способность.

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

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

Данная программа позволила определить основные характеристики декодера (см табл. 3).

ТАБЛИЦА 3

Скорость кода Вероятность ошибки на бит Скорость выходного потока (Мбиг/с)

на входе на выходе

1/2 0,01 <ю-" 1,7

3/4 0,004 <10* 2

7/8 0,001 <10* 1,2

Все полученные показатели с допустимой точностью соответствуют теоретическим, что

свидетельствует о работе устройства в полном соответствии с общим алгоритмом.

• В заключении сформулированы основные результаты работы.

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

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

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

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

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

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

дЛС Q

Р ШЭ 51 7

ПУБЛИКАЦИИ ПО ТЕМЕ ДЙССЕ^ТМЩИ

1. ДВБабенко, ОА.Усенко Помехоустойчивое декодирование систематических сверточных кодов / Тезисы докладов 6-я международная конференция студентов и аспирантов, 1-2 марта 2000 г. МЭИ, Москва, тезисы докл , том 1, с. 113-114

2. Д В Бабснко Методы помехоустойчивого декодирования систематических сверточных кодов / V Всероссийская научная конференция студентов и аспирантов, тезисы докл. 12-13 октября 2000 г. ТРТУ, г.Таганрог. - с. 354-355

3. Д В Бабснко, О Б Макаревич, Л К.Бабенко. Способы повышения производительности устройств помехоустойчивого декодирования систематических сверточных кодов. / Сборник трудов научно-практической конференции "Информационная безопасность", Таганрог, 2001. с. 179-181.

4 ДВБабенко, О.БМакаревич. Обзор элементной базы устройств связи и технологии ПЛИС для устройств помехоустойчивого декодирования. / Сборник трудов научно-практической конференции "Информационная безопасность", Таганрог, 2002 г., с.56-58.

5. Л К Бабенко, Д В Бабенко, А В Иванченко Проблемы синхронизации в декодерах систематических сверточных кодов / Известия ТРТУ. Специальный выпуск «Материалы XLVII научно-практической конференции»,Таганрог,ТРТУ,2002№ 1(24) -с. 144-146.

6 ОБ Макаревич, Д В Бабенко Перспективы помехоустойчивого декодирования по алгоритму Фано / Известия ТРТУ. Специальный выпуск «Материалы XLVII научно-практической конференции», Таганрог, ТРТУ, 2002 №1(24) с. 147-148

7. ОБ Макаревич, Д В Бабенко Программа поиска сверточного кода и режимов демодулятора в информационной последовательности. Свидетельство К» 2003611333 от 16.04.2003 г., Роспатент, Москва, 2003 г. *

8 ОБ Макаревич, Д В Бабенко Программа создания таблицы метрик для последовательного декодера сверточных кодов Свидетельство № 2003611332 от 16 04.2003 г., Роспатент, Москва, 2003 г.

9. ОБ Макаревич, Д В Бабенко. Программа имитации режимов демодулятора с квантованием по уровню сигнала на зашумленном канале передачи данных. Свидетельство № 2003611331 от 16 04.2003 г., Роспатент, Москва, 2003 г.

10 ОБ Макаревич, Д В Бабенко Программная модель устройства последовательного декодирования систематических сверточных кодов по алгоритму Фано. Свидетельство № 2003610910 от 25.04 2003 г, Роспатент, Москва, 2003 г «

Отпечатано в типографии ООО "Оригинал - КВ"

тираж 100 экз заказ № 604а от 17,11,2003г Таганрог, ул Александровская, 108, тел 66-46-24

СОДЕРЖАНИЕ.

ВВЕДЕНИЕ.

1. ИССЛЕДОВАНИЕ СУЩЕСТВУЮЩИХ МЕТОДОВ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ И ОСНОВНЫХ ХАРАКТЕРИСТИК КАНАЛОВ ТЕЛЕКОММУНИКАЦИИ.

1.1 Анализ линейных блоковых кодов для каналов с аддитивным шумом.

1.1.1 Исследование основных свойств линейных кодов.

1.1.2 Коды Рида-Соломона.!.

1.2 Исследование сверточных кодов, в качестве аппарата помехоустойчивой связи ВЫСОКОЙ ПРОИЗВОДИТЕЛЬНОСТИ.

1.3 популярные алгоритмы декодирования сверточных кодов.

1.3. J Алгоритм Виттерби.

1.3.2 Алгоритм декодирования с обратной связью.

1.4 Методы последовательного декодирования сверточных кодов.

1.4.1 Исследование основных принципов последовательного декодирования систематических сверточных кодов.

1.4.2 Стек-алгоритм.

1.4.3 Алгоритм Фано.

1.5 Исследование особенностей процесс а вычисления метрик.

1.6 Сравнительный анализ рассмотренных алгоритмов помехоустойчивого декодирования.

2 РАЗРАБОТКА СПОСОБОВ ПОВЫШЕНИЯ ПРОИЗВОДИТЕЛЬНОСТИ АЛГОРИТМОВ ПОМЕХОУСТОЙЧИВОГО ДЕКОДИРОВАНИЯ.

2.1 Исследование алгоритма Фано помехоустойчивого декодирования систематических сверточных кодов.

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

2.2.1 Процесс вычисления метрик для телекоммуникационной системы с мягким решением.

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

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

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

3 ИССЛЕДОВАНИЕ И РАЗРАБОТКА ПРОГРАММНОЙ МОДЕЛИ

МОДИФИЦИРОВАННОГО АЛГОРИТМА ФАНО.

3.1 Разработка модифицированной программной модели и оценка результатов ее работы

3.2 Оценка и исследование на программной модели модифицированного алгоритма Фано

4 РАЗРАБОТКА МЕТОДИК ОТЛАДКИ И ТЕСТИРОВАНИЯ УСТРОЙСТВА ПОМЕХОУСТОЙЧИВОГО ДЕКОДИРОВАНИЯ И ИССЛЕДОВАНИЕ ЕГО ТЕХНИЧЕСКИХ ХАРАКТЕРИСТИК.

4.1 Исследование основных особенностей реализации алгоритма декодирования в 1елекоммуникационной системе.

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

На современном этапе развития средств телекоммуникаций является актуальной проблема повышения производительности систем связи, включающая в себя проблемы ^ повышения скорости и качества передачи данных. Эти характеристики систем связи обратно пропорциональны друг другу. С увеличением скорости передачи данных теряется качество передаваемой информации и наоборот. Это связано с присутствием во всех каналах передачи данных различного рода шумов, оказывающих определенное влияние на целостность передаваемой информации [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. Программно аппаратные средства и методики отладки и тестирования устройства помехоустойчивого декодирования сверточных кодов, разработанного на основе модифицированного алгоритма Фано позволяют упростить процесс проектирования, тестирования и отладки устройства.

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

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

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

Реализация научно-технических результатов работы. Разработанные алгоритмы, результаты исследования математической модели, рекомендации по повышению производительности декодера внедрены в Ростовском НИИ радиосвязи в совместной работе "Разработка модуля ПУ-декодирования систематических сверточных кодов" - х/д 16103. Результатом работы является опытный образец устройства последовательного декодирования систематических сверточных кодов использующий модифицированный алгоритм Фано. Данное устройство обладает следующими техническими характеристиками по быстродействию и качеству декодирования. В качестве элементной базы использовались ПЛИС фирмы Xilinx XC4036HQ240EX, работающие на тактовой частоте 40 МГц. Устройство способно производить декодирование информационного потока, с кодовыми скоростями 1/2, 3/4 и 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)) [ ]; разработанный способ и программы зарегистрированы Свидетельствами об официальной регистрации программ для ЭВМ № 2003611331 [41], № 200361 1332 [40], №2003611333 [39], № 2003610910 [42] (Роспатент. 2003 г.).

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

1. Прокис Джон. Цифровая связь. Пер. с англ./Под ред. Д.Д.Кловского. М.:Радио и связь. 2000. -800с.:ил.

2. Т.Касами, Н.Токура, Е.Иварди, Я.Инагаки. Теория кодирования. Пер. с япон. А.В.Кузнецова. Под ред. Б.С. Цыбакова, С.И.Гельфанда. М.:Мир. 1978. -570с.

3. У.Питерсон, Э.Уэлдон. Коды, исправляющие ошибки. -М.:МИР. 1976.

4. Витерби А. Границы ошибок для сверточных кодов и асимптотически оптимальный алгоритм декодирования. В сб. Некоторые вопросы теории кодирования. М.:Мир. 1970, стр. 142-165.

5. J.H.Sttoll. The DVB terrestrial (DVB-T) specification and its implementation in a practical modem. Документы International Broadcasting Convention, 12-16 September 1996, Conference Publication №428, p.255-260

6. Возенкрафт Дж., Рейффен Б. Последовательное декодирование. ИЛ, 1963

7. И.И.Гроднев, А.Г.Мурадян, Р.М.Шарафутдинов и др. Волоконно-оптические системы передачи и кабели: Справочник М.: Радио и связь, 1993. - 264 е.: ил.

8. Радиорелейные и спутниковые системы передачи: Учебник для вузов / А.С.Немировский, О.С.Данилович, Ю.И.Маримонт и др. Под ред.

9. A.С.Немировского. М.: Радио и связь, 1986. - 392 е.: ил.

10. Прагер Э., Шимек Б., Дмитриев В.П. Цифровая техника в связи / Под ред.

11. B.В.Маркова. М.: Радио и связь; Прага, SNTL,1981. - 280 е., ил.

12. П.П.Мальцев, Н.С.Долидзе и др. Цифровые интегральные микросхемы.: Справочник. М.: Радио и связь, 1994. -240 е.: ил.

13. Л. Невдяев. CDMA: кодирование и перемежение. Журнал "Сети", №12,: Открытые Системы, 2000.

14. XILINX. The Programmable Logic Data Book 1998. XDOCS E-mail Document Server: xdocs@xiIinx.com

15. Зюко А.Г., Фалько А.И., Панфилов И.П., Банкет В.Л., Иващенко П.В., Помехоустойчивость и эффективность систем передачи информации, М., Радио и связь, 1985, 272с.

16. Гроднев И.И., Верник С.М. Линии связи: Учебник для вузов. 5-е изд., перераб. и доп. - М.: Радио и связь, 1988. - 544 е.: ил.

17. В.Л.Банкет. Спутниковые системы связи. М.: Радио и связь. 1987.

18. Радиорелейные и спутниковые системы передачи: Учебник для вузов / А.С.Немировский, О.С.Данилович, Ю.И.Маримонт и др. Под ред. А.С.Немировского. М.: Радио и связь, 1986. - 392 е.: ил.

19. А.В. Ермаков. Потенциальная помехоустойчивость сети доступа к данным по стандарту DOCSIS в системе КТВ. :Журнал TeleMultiMedia N 1(5). Интерактивные сети кабельного ТВ. 2001. (адрес в интернете: www.telemultimedia.ru)

20. J1.A. Севальнев. Эфирное вещание цифровых ТВ-программ со сжатием данных. Журнал Теле-Спутник №10(36). Научно-технические разработки. Октябрь 1998. (адрес в интернете: www.telesputnik.ru')

21. Месси Д. Пороговое декодирование. М.: Мир, 1966, - 207 с.

22. Сагалович Ю.Л. Алгебра, коды, диагностика. М.:Мир, - 1993. - 196 с.

23. Макаров В.А. Моделирование кодирующих и декодирующих устройств на ПЭВМ: Учеб. пособие / В. А. Макаров, Ю. А. Курочкин; С.-Петерб. гос. техн. ун-т. СПб.: СПбГТУ. - 1996.-54 е.: ил.

24. Лазарева Е.Е. Учебное пособие по курсу Системы передачи информации. Циклические и сверточные коды / Ред. Л. В. Когновицкий; М.: МЭИ. 1986. - 51, е.: ил.

25. Rao T.R.N. Error-control coding for computer systems / Fuliwara E. Englewood Cliffs (NJ): Prentice Hall. - 1989. - XIII,524 с

26. Adamek J. Foundations of coding: Theory and applications of error-correcting codes with an introduction to cryptography and information theory. Chichester etc: Wiley-Interscience. - 1991. - XIII,336 с

27. M. Riley, I. Richardson Reed-Solomon Codes. An introduction to Reed-Solomon codes: principles, architecture and implementation. 4i2i Communications Ltd -1998. (адрес в интернете: www.4i2i.com)

28. Д.В.Бабенко, О.А.Усенко. Помехоустойчивое декодирование систематических сверточных кодов / 6-я международная конференция студентов и аспирантов, 1-2 марта 2000 г. МЭИ, Москва, тезисы докл., том 1, с. 113-114

29. Д.В.Бабенко. Устройство ПУ-декодирования систематических сверточных кодов. / 46-я студенческая научная конференция, тезисы докл., 18 марта 1999 г. ТРТУ, Таганрог. с. 78

30. Д.В.Бабенко. Методы помехоустойчивого декодирования систематических сверточных кодов. / V Всероссийская научная конференция студентов и аспирантов, тезисы докл. 12-13 октября 2000 г. ТРТУ, г.Таганрог. с. 354-355.

31. Д.В.Бабенко. Основные перспективы применения алгоритма Фано (тезисы докл.)/ Сборник трудов научно-практической конференции "Информационная безопасность", Таганрог, 2001 г.

32. Д.В.Бабенко. Способы повышения производительности устройств помехоустойчивого декодирования систематических сверточных кодов. / Сборник трудов научно-практической конференции "Информационная безопасность", Таганрог, 2001 г. с. 179-181.

33. Д.В.Бабенко, О.Б.Макаревич. Анализ популярных алгоритмов помехоустойчивого декодирования систематических сверточных кодов / журнала "РИУ" Запорожский национальный технический университет (ЗНТУ).

34. Д.В.Бабенко. Обзор элементной базы устройств связи и технологии ПЛИС для устройств помехоустойчивого декодирования. / Сборник трудов научно-практической конференции "Информационная безопасность", Таганрог, 2002 г., с.56-58.

35. О.Б.Макаревич, Д.В.Бабенко. Учебно-методическое пособие по теме помехоустойчивого декодирования систематических сверточных кодов. ТРТУ, г. Таганрог 2002 г. (в печати)

36. Heller J.A. Feedback decoding of convolutional codes. In Advances in Communication System, vol. 4, A.J.Viterbi (ed.) Academic, NewYork.

37. О.Б.Макаревич, Д.В.Бабенко. Программа поиска сверточного кода и режимов демодулятора в информационной последовательности. Свидетельство № 2003611333 от 16.04.2003 г., Роспатент, Москва, 2003 г.

38. О.Б.Макаревич, Д.В.Бабенко. Программа создания таблицы метрик для последовательного декодера сверточных кодов .Свидетельство № 2003611332 от 16.04.2003 г., Роспатент, Москва, 2003 г.

39. О.Б.Макаревич, Д.В.Бабенко. Программа имитации режимов демодулятора с квантованием по уровню сигнала на зашумленном канале передачи данных. Свидетельство № 2003611331 от 16.04.2003 г., Роспатент, Москва, 2003 г.

40. О.Б.Макаревич, Д.В.Бабенко. Программная модель устройства последовательного декодирования систематических сверточных кодов по алгоритму Фано. Свидетельство № 2003610910 от 25.04.2003 г., Роспатент, Москва, 2003 г.

41. О.Б.Макаревич, Д.В.Бабенко. Способ последовательного декодирования систематических сверточных кодов на основе алгоритма Фано. Заявка № 2003114853, от 27.05.2003 Роспатент, Москва, 2003 г.