автореферат диссертации по радиотехнике и связи, 05.12.13, диссертация на тему:Разработка моделей и методов построения декодеров на базе модифицированного алгоритма Витерби

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

АСТАХОВ Николай Владимирович

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

ДЕКОДЕРОВ НА БАЗЕ МОДИФИЦИРОВАН^

ВИТЕРБИ

О АЛГОРИТМА

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

• 3 Ш 2012

Воронеж - 2012

005016739

Работа выполнена в ФГБОУ ВПО «Воронежамй государственный технический университет»

Научный руководитель доктор технических наук, профессор

Муратов Александр Васильевич

Официальные оппоненты: Чопоров Олег Николаевич доктор технических наук, профессор, ФГБОУ ВПО «ВГТУ», заведующий кафедрой;

Перетокин Олег Иванович кандидат технических наук, Воронежский институт правительственной связи (филиал) Академии Федеральной службы охраны Российской Федерации

Ведущая организация Воронежский институт МВД Россий-

ской Федерации

Защита состоится 17 мая 2012 г. в 1400 часов в конференц-зале на заседании диссертационного совета Д212.037.10 ФГБОУ ВПО Воронежский государственный технический университет по адресу: 394026, Воронеж, Московский просп., 14.

С диссертацией можно ознакомиться в научно-технической библиотеке ФГБОУ ВПО «Воронежский государственный технический университет»

Автореферат разослан 16.04.2012 г.

Ученый секретарь диссертационного совета ' Макаров О.Ю.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Хотя в перспективных системах делается упор на использование турбо-кодов и LDPC кодов (код с малой плотностью проверок на чётность, от англ. Low-density parity-check code), тем не менее существует множество телекоммуникационных систем, использующих сверточный код.

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

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

ЧИТЬ максимально правдоподобную (МП) оценку переданного кодового слова. Основным недостатком алгоритма декодирования Витерби является экспоненциальный рост вычислительной сложности при увеличении числа внутренних состояний декодера.

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

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

Работа выполнена в рамках одного из основных научных направлений ФГБОУ ВПО «Воронежский государственный технический университет» «Перспективные радиоэлектронные и лазерные устройства и системы передачи, приема, обработки и защиты информации» и ГБ НИР 2007.17 «Методы исследования и повышения надежности и качества при проектировании радиоэлектронных устройств и систем».

Цель и задачи исследования. Целью диссертационного исследования является разработка моделей и методов построения декодеров на базе модифицированного алгоритма Витерби.

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

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

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

разработать методику реализации помехоустойчивого алгоритма Витерби для протоколов связи У.32 с модулем, реализующим коррекцию ошибок по протоколу У.42;

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

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

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

2

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

Научная новизна результатов исследования. В работе получены следующие результаты, характеризующиеся научной новизной:

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

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

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

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

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

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

Основные положения диссертации внедрены в ОАО «Концерн «Созвездие» и в учебный процесс кафедры КИПР ФГБОУ ВПО "ВГТУ".

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на следующих конференциях, совещаниях и семинарах: Международной конференции «Системные проблемы надежности, качества, информационных и электронных технологий» (Сочи, 2007-2010); Всероссийской научно-технической конференции молодых ученых «Современные проблемы радиоэлектроники» (Красноярск, 2007-2010); ежегодных научно-технических конференциях ГОУ ВПО «Воронежский государственный технический университет» и научно-

3

методических семинарах кафедры конструирования и производства радиоаппаратуры (2007-2010).

Публикации. По теме диссертации опубликовано 10 научных работ, в том числе 3 - в издании, рекомендованном ВАК РФ.

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

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

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

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

Наиболее важным достоинством декодера Витерби является простота реализации по сравнению с другими алгоритмами. Обладает удобством реализации на ПЛИС потому, что легко параллелится на множество независимых операций, что позволяет без роста тактовой частоты резко увеличить пропускную способность. Декодер позволяет легко перейти к «мягким» решениям на входе декодера, что обеспечивает энергетический выигрыш порядка 3...7 дБ без расширения занимаемой полосы частот.

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

Рассмотрены основные свойства алгоритмов, осуществляющих помехоустойчивое декодирование сигнала.

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

На основе проведенного анализа определяются цель и задачи исследования.

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

Предложена схема взаимодействия помехоустойчивого декодера для реализации на ПЛИС (рис. 1), работающего по модифицированному алгоритму Витерби с модулем, реализующим контроль ошибок CRC. Такой подход обеспечивает следующие преимущества:

повышение энергоэффективности, благодаря взаимодействию данного алгоритма с модулем коррекции ошибок;

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

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

Задача помехоустойчивого декодера состоит в формировании оценки с переданной информационной последовательности с по зашумленной последовательности г = х + п . В том случае, если задача декодера состоит в минимизации средней вероятности перепутывания переданной и декодированной информационных последовательностей, декодер должен выбрать решение согласно правилу максимума апостериорной вероятности (MAB). При заданных статистических свойствах информационной последовательности с все кодовые слова являются равновероятными, и правило MAB переходит в правило максимума правдоподобия (МП).

Оценкой переданной информационной последовательности является последовательность с = argmax(P(r | с)), где P(r | С) — функция правдоподобия:

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

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

МП оценкой переданной последовательности данных является последовательность с = argmax(P(r | а)), где P(r | а) — функция правдоподобия:

Р(Г I с) = Р(г | v) = Р(г | х) = ПП-7Г=еХр(~Ь

N л-1 |

|2 /(2а2)) (1)

"ш+т *tn+m

(=1 л»=0

MAB.

2

ЛГ- длина последовательности данных; сг2 дисперсия шума

Последовательность флагов

Кадр протокола у.42

флаг

флаг

адрес

управление

Байт СЖС

«4-

Байт

СЯС

-►

флаг

Байты инфор- Байты контрольной мании последовательности

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

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

Главным недостатком стандартного алгоритма Витерби является необходимость анализа всех возможных последовательностей принятого сигнала, что снижает быстродействие и повышает энергозатраты. В связи с этим предлагается ввести функцию правдоподобия ¿„ благодаря которой на ¡-м шаге декодирования алгоритм поможет выбрать ветвь с ее максимальным значением, т.е. находящуюся на минимальном расстоянии от принятой По-символьной последовательности. При этом функция правдоподобия вычисляется следующим образом (3):

(?)

где

я<=Ц108{-щг

где Р{у) / с*) - вероятность приема из канала символа у } при передачи символа с* ; Р(у*) - вероятность приема символа у* ,В- смещение.

Величину смещения В выберем так, чтобы значение метрики при принятии правильного решения возрастало, а при принятии ошибочного решения — убывало. В нашем случает этому требованию удовлетворяет выбор В=г, где г кодовая скорость.

-В

(4)

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

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

Структурная схема обработки данных, передаваемых согласно стандартам У.32, представлена на рис. 2.

Рис. 2. Структурная схема обработки данных по стандартам передачи данных У.32

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

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

В третьей главе рассматриваются алгоритмы функционирования модифицированного многоуровневого алгоритма Витерби. За основу взят стандарт ШЕЕ-754 для вычислительных устройств на арифметике с плавающей точкой, который в настоящее время является общепринятым.

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

7

с

Старт

Допустимая вероятность ошибки

достигнута

X Не достигнута

декодирование

Последняя итерация декодирования с сохранением метрик всех допустимых путей

Вычисление СЯС принятого блока данных

Сортировка альтернативных путей по возрастанию суммарной метрики

Все пути да Елок данных декодирован правильно

проверены

+

X нет Запрос на повтор блока

Выбор следующего данных

альтернативного пути декодирования ^ Конец

4

Внесение изменений в блок данных согласно альтернативному пути

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

Формирование таблиц номеров ребер

■Г-г/"./= 1.0..-.Н-1

С, = 0,у = 0,1,....ЛГ-1 _1 = 0_

Г

Агатой!. •■= 0

а:=С,+ Д«>

Да а <Ь >> Нет

1 Г

Сг,:-<4„(!):= а Сг, А„(Г):= = ь

бО

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

0 0

Нет

Да

1 г

V^-Wimodi.)

Нет

1 Да г

;= А1ш,(1 modL)

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

(продолжение)

В большинстве случаев первый путь с минимальной суммарной метрикой (вероятность ошибки) будет содержать правильные данные, которые пройдут проверку CRC. Если CRC верно, то поиск альтернативных путей можно прекратить, будет принято решение о правильном декодировании данных, и послан запрос на прием нового блока данных.

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

10

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

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

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

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

При оценке вычислительных затрат существенное значение имеет тип данных, используемый для хранения и обновления информационных путей A,(l) (I = 0,1,... L - 1). Если для Ai(l) в памяти ПЭВМ отводится байт ИЛИ СЛОВО, то при обновлении информационных последовательностей с использованием операции присвоения типа AJ:=Aj(l) для всех значений 1—0,1,... L - 1 требуется L пересылок для данного узла. С другой стороны,

11

можно увидеть, что реализация остальных операций в модуле ССВ требует произвести 8 простых арифметических операций с учетом индексирования. Поскольку глубина декодирования Ь = 5000, то получается, что операция обновления информационной последовательности дает вклад в 4 раза больше, нежели остальные операции.

Для хранения одного информационного символа достаточно использовать один бит. Если для А1(1) в памяти ПЭВМ отводится 1 бит и выбирается Ь=32, то для хранения элементов информационной последовательности требуется два слова для 16-разрядных и одно слово для 32-разрядных ПЭВМ. В этом случае для обновления информационных последовательностей требуется лишь одна и две операции пересылки соответственно. Таким образом при использовании бита для реализации Аг(1) быстродействие модуля ССВ повышается, примерно, в четыре раза в сравнении с ситуацией, при которой информационному символу отводится один байт или слово ПЭВМ.

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

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

Таблица 1

Энергетический выигрыш многовариантного декодера_

Кодовая скорость Число состояний Коэффициент вычислительной сложности Уровень вероятности ошибки Энергетический выигрыш, дБ

1/2 4 2 Ю-5 0,8

Ю-6 1,0

1/2 8 2 Ю-5 0,8

10"6 1,0

1/3 8 2 10"5 0,8

10"6 0,9

2/3 4 4 Ю-5 1,4

10"6 1,8

Таблица 2

Энергетический выигрыш без увеличения вычислительной сложности

Кодовая скорость Число состояний Коэффициент вычислительной сложности Уровень вероятности ошибки Энергетический выигрыш, дБ

1/2 4 2 Ю-5 0,3

Ю-6 0,5

1/2 8 2 Ю-5 0,4

10"6 0,6

1/3 8 2 Ю-5 0,3

1(Гб 0,4

2/3 4 4 Ю-5 0,2

10'6 0,4

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

3. Разработана методика реализации помехоустойчивого алгоритма Витерби для протоколов связи У.32 с модулем коррекции ошибок, работающим по протоколу У.42.

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

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

6. Проведена апробация разработанного модифицированного алгоритма для реализации модифицированного многовариантного алгоритма Ви-терби на ПЛИС. Результаты диссертационной работы внедрены в ОАО «Концерн «Созвездие» и в учебный процесс кафедры КИПР ФГБОУ ВПО «ВГТУ».

Основные результаты диссертации опубликованы в следующих

работах:

Публикации в изданиях, рекомендованных ВАК РФ

1. Астахов Н.В. Математическая реализация модифицированного многовариантного алгоритма Витерби / Н.В. Астахов // Вестник Воронежского государственного технического университета. 2011. Т.7. №2. С. 142 - 143.

2. Астахов Н.В. Реализация на ПЛИС алгоритмов помехоустойчивого кодирования: турбо-декодер и декодер Витерби / Н.В. Астахов, A.A. Пирогов // Вестник Воронежского государственного технического университета. 2011. Т.7. №2. С. 191 - 193.

3. Астахов Н.В. Разработка и применение многовариантного алгоритма в алгоритме Витерби / Н.В. Астахов, С.Ю. Белецкая // Вестник Воронежского государственного технического университета. 2011. Т.7. №3. С. 25-26.

Статьи и материалы конференций

4. Астахов Н.В. Входной и выходной буфер для блока быстрого преобразования Фурье на 256К точек / Н.В. Астахов, A.B. Башкиров И Современные проблемы радиоэлектроники: сб. науч. тр.; ред.: А.И.Громыко, А.В.Сарафанов. М.: «Радио и связь», 2006. С. 425 - 427.

5. Астахов Н.В. Измерение динамических параметров ЦАП / Н.В. Астахов, A.B. Муратов // Системные проблемы надёжности, качества, информационных и электронных технологий в инновационных проектах. М.: Радио и связь, 2006. Ч. 4., Т.1. С. 200-203.

6. Астахов Н.В. Алгоритмизация функционального тестирования СБИС и систем на кристалле / Н.В.Астахов, А.В.Башкиров, Ю.В.Дьячков // Современные проблемы радиоэлектроники: сб. науч. тр.; ред.: А.И.Громыко, А.В.Сарафанов. Красноярск: СФУ, 2007. С. 471-473

7. Астахов Н.В. Исследование алгоритма асинхронного сплошного моделирования МОП-схем на примере комплементарного D-триггера / Н.В.Астахов, К.Н.Сотникова, А.В.Муратов, ДЛО.Ефимцев // Современные

14

проблемы радиоэлектроники: сб. науч. тр.; ред.: А.И.Громыко, А.В.Сарафанов. Красноярск: СФУ, 2007. С. 565-567.

8. Башкиров A.B. Новые критерии достижения высокой степени покрытия верификационным кодом при проектировании систем на кристалле / А.В.Башкиров, Н.В.Астахов // Системные проблемы надёжности, качества, информационных и электронных технологий в инновационных проектах. М.: Энергоатомиздат, 2007. Ч. 2., Т. III. С. 136-141.

9. Астахов Н.В. Проектирование структуры оперативного запоминающего устройства статического типа / Н.В.Астахов, Ю.В.Дьячков, А.В.Муратов // Современные проблемы радиоэлектроники: сб. науч. тр.; ред.: А.И.Громыко, А.В.Сарафанов. Красноярск: ИПК СФУ, 2008. С. 324327.

10. Тенденции развития цифровой техники в условиях применения программируемой логики / В.Б. Авдеев, Н.В. Астахов, A.B. Башкиров, Ю.В. Дьячков, С.Ю. Белецкая // Системы проблемы надёжности, качества, информационных и электронных технологий в инновационных проектах. М.:

Подписано в печать 13.04.2012. Формат 60x84/16. Бумага для множительных аппаратов. Усл. печ. л. 1,0. Тираж 80 экз. Заказ № 50.

ФГБОУ ВПО «Воронежский государственный технический университет» 394026 Воронеж, Московский просп., 14

61 12-5/2396

ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

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

Астахов Николай Владимирович

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

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

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата технических наук

Научный руководитель:

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

Муратов Александр Васильевич

Воронеж-2012

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 4

1. АНАЛИЗ АЛГОРИТМОВ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ, СОВРЕМЕННЫХ МЕТОДОВ КОРРЕКЦИИ ОШИБОК, ЭНЕРГЕТИЧЕСКОЙ ЭФФЕКТИВНОСТИ 11

1.1 Основные принципы помехоустойчивого кодирования 11

1.2 Анализ преимуществ и недостатков кодов в современных системах связи 14

1.3 Аппаратная реализация помехоустойчивого кодирования в

код ерах/декод ерах 19

1.4 Преимущества турбо кодов произведения и их аппаратная реализация. 34

1.5 Аппаратная реализация многопороговых декодеров 42

1.6 Цель и задачи исследования 43

1.7 Выводы первой главы 45

2. РАЗРАБОТКА МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ МОДИФИЦИРОВАННОГО АЛГОРИТМА ВИТЕРБИ 47

2.1 Математическая реализация модифицированного многовариантного алгоритма Витерби 47

2.2 Особенности реализация модифицированного алгоритма Витерби на ПЛИС для протоколов у.42 и у.32 56

2.3 Энергетическая эффективность многовариантного декодера 62

2.4 Разработка и применение многовариантного алгоритма в алгоритме Витерби 64

2.5 Основные выводы второй главы 68

3. РАЗРАБОТКА АЛГОРИТМОВ РЕАЛИЗАЦИИ МОДИФИЦИРОВАННОГО МНОГОУРОВНЕВОГО АЛГОРИТМА ВИТЕРБИ ДЛЯ РЕАЛИЗАЦИИ НА ПЛИС 70

3.1 Особенности функционирования последовательных и параллельных алгоритмов. 70

3.2 Разработка алгоритма реализации многоуровневого алгоритма Витерби для протоколов у.32 и у.42 72

3.3 Алгоритм декодирования Витерби для реализации на ПЛИС 77

3.4 Основные выводы третьей главы 81 4. АППАРАТНАЯ РЕАЛИЗАЦИЯ КОДЕРОВ НА БАЗЕ МОДИФИЦИРОВАННОГО АЛГОРИТМА ВИТЕРБИ НА ПЛИС 82

4.1 Характерные преимущества модифицированного алгоритма Витерби по сравнению с общепринятыми кодами при аппаратной реализации на ПЛИС. 82

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

85

4.3 Синтез аппаратных модулей декодера на ПЛИС, реализующего модифицированный алгоритм Витерби. 90

4.4 Энергетический выигрыш модифицированного алгоритма Витерби с увеличением вычислительной сложности и без увеличения. 92

4.5 Основные выводы четвертой главы 94 ЗАКЛЮЧЕНИЕ 95 Список источников 96 Приложения 110

ВВЕДЕНИЕ

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

помехоустойчивость, а также положительно сказывается на экономическом эффекте.

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

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

Хотя в перспективных системах делается упор на использование турбо-кодов и LDPC кодов (код с малой плотностью проверок на чётность, от англ. Low-density parity-check code), тем не менее существует множество телекоммуникационных систем, использующих сверточный код.

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

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

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

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

Работа выполнена в рамках одного из основных научных направлений ФГБОУ ВПО «Воронежский государственный технический университет» «Перспективные радиоэлектронные и лазерные устройства и системы

передачи, приема, обработки и защиты информации» и ГБ НИР 2007.17 «Методы исследования и повышения надежности и качества при проектировании радиоэлектронных устройств и систем».

Цель и задачи исследования. Целью диссертационного исследования является разработка моделей и методов построения декодеров на базе модифицированного алгоритма Витерби.

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

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

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

разработать методику реализации помехоустойчивого алгоритма Витерби для протоколов связи У.32 с модулем, реализующим коррекцию ошибок по протоколу У.42;

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

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

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

Научная новизна результатов исследования. В работе получены следующие результаты, характеризующиеся научной новизной:

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

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

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

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

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

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

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

сигнала, что позволяет значительно повысить экономические показатели производства.

Основные положения диссертации внедрены в ОАО «Концерн «Созвездие» и в учебный процесс кафедры КИПР ФГБОУ ВПО "ВГТУ".

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на следующих конференциях, совещаниях и семинарах: Международной конференции «Системные проблемы надежности, качества, информационных и электронных технологий» (Сочи, 2007-2010); Всероссийской научно-технической конференции молодых ученых «Современные проблемы радиоэлектроники» (Красноярск, 2007-2010); ежегодных научно-технических конференциях ГОУ ВПО «Воронежский государственный технический университет» и научно-методических семинарах кафедры конструирования и производства радиоаппаратуры (2007-2010).

Публикации. По теме диссертации опубликовано 10 печатных работ, в том числе 3 - в издании, рекомендованном ВАК РФ.

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

В первой главе работы изложены основные принципы помехоустойчивого кодирования с исправлением ошибок. Рассмотрены основные свойства алгоритмов, осуществляющих помехоустойчивое кодирование сигнала. Рассмотрена единая среда проектирования, от системного уровня до уровня регистровых передач и вентильного уровня с поддержкой языков С, С++, 8уБ1етС уровней 1.0 и 2.0 и языков описания аппаратуры Уеп1о§ и УНБЬ.

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

производительности и эффективности для использования в конкретных условиях.

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

На основе проведенного анализа определяются цель и задачи исследования.

Во второй главе рассматривается методы повышения эффективности работы алгоритма Витерби путем применения многовариантного алгоритма декодирования с внедрением модуля коррекции ошибок по протоколу у.42 и у.32.

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

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

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

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

- алгоритмы позволяют повысить помехоустойчивость в системах связи с протоколами коррекции ошибок;

- модели обладают достаточной адекватностью и универсальностью;

- алгоритмы и модели экономически оправданы с точки зрения затрат времени и средств на их реализацию.

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

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

В четвертой главе, на основе ранее предложенных математических моделей и алгоритмов разработана методика реализации модифицированного алгоритма Витерби на ПЛИС.

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

1 АНАЛИЗ АЛГОРИТМОВ ПОМЕХОУСТОЙЧИВОГО

КОДИРОВАНИЯ, СОВРЕМЕННЫХ МЕТОДОВ КОРРЕКЦИИ ОШИБОК, ЭНЕРГЕТИЧЕСКОЙ ЭФФЕКТИВНОСТИ.

1.1 Основные принципы помехоустойчивого кодирования

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

Примем к рассмотрению двоичный канал связи с присутствующими в нем помехами, которые приводят к тому, что в каждом символе независимо появляются ошибки и средняя вероятность появления этой ошибки будет равняться Р=0,01. Если рассматривать произвольный блок состоящий из 10 символов, то будет затруднительно определить символы, являющиеся ошибочными. Если предположить, что данный блок содержит не больше трех ошибок, мы будем некорректны всего в двух случаях из миллиона блоков. Кроме этого, вероятность того, что мы будем правы, увеличивается с ростом длины блока. Если увеличивать длину блока, при этом доля ошибочных символов в блоке будет приближаться к средней частоте ошибок в канале

связи, а также, доля блоков, в которых число ошибок будет существенно отличается от этого среднего значения, стремится к незначительным величинам. Путем несложных вычислений можно сделать выводы о том, насколько верным является это утверждение. Рассмотрим, к примеру, тот же канал и определим вероятность того, что количество ошибочных символов превышает некоторое значение р, построим график этой функции применительно к нескольким значениям длины блока /1,31,33,34,35/.

■101

10

1С

«

10

1Г

1 (

Г И-- 1 1 1 1 1

I ■ 1 * 14111 г ( 1 I 1 I >---~ — ^-N=10

_ - - ^ чо

1 1 »0 у 1 1 1 .............................. I I I Г

0,1

0,3 />

Рис. 1.1- Вероятность превышения значения р долей ошибочных символов в блоке с числом символов 1М, при вероятности появления ошибки Р = 0,01

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