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

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

Суэтинов Игорь Вячеславович/ Л С -

V

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

Специальность 05.13.01 «Системный анализ, управление и обработка информации»

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

Москва - 2003 г.

Работа выполнена на кафедре Микроэлектронных Радиотехнических Устройств и Систем Московского Государственного Института Электронной Техники (технического университета)

Научный руководитель: к.т.н., профессор Незлин Д.В.

Официальные оппоненты:

д.т.н., профессор Савченко Ю.В.

к.т.н., с.н.с. Слезкин Ю. А.

Ведущая организация: ФГУП НИИМА «Прогресс»

Защита состоится «_»_2003 г. в_часов

на заседании диссертационного совета Д 212.134.02 в Московском государственном институте электронной технике (техническом университете) по адресу 124498, Москва, МИЭТ

С диссертацией можно ознакомиться в библиотеке МИЭТ.

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

« »

2003 г.

Ученый секретарь диссертационного с^эета к.т.н., профессор

Воробьев Н.В.

^^ О^щая характеристика работы

Аннотация

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

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

На базе ПЛИС ХСУ600Е-6НС)240С были реализованы оба варианта архитектур мягкого декодера квадратично-вычетного кода (48, 24, 12) - одного из самых эффективных коротких блочных кодов. Декодеры оформлены в виде библиотечных элементов для их использования как в виде отдельной микросхемы ПЛИС, так и в составе произвольных устройств цифровой обработки, реализованных на ПЛИС. Для испытания реализованных на ПЛИС декодеров был разработан испытательный стенд кодеков (кодер-декодеров). В результате экспериментального исследования декодера кода (48, 24, 12) на

РОС. НАЦИОНАЛЬНАЯ { БИБЛИОТЕКА | СПстсфру -7 I 09 \

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

Актуальность работы

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

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

ступеней при каскадировании кодов, в частности при разработке турбо-кодеков на основе блочных кодов.

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

Цели диссертационной работы.

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

2. Создание методики, позволяющей аппаратно реализовать и оптимизировать мягкий декодер произвольного короткого блочного кода.

3. Разработка и экспериментальное испытание мягкого декодера квадратично-вычетного кода (48, 24, 12). Научная новизна работы.

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

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

3. При аппаратном декодировании в реальном времени коротких линейных блочных кодов впервые достигнуты характеристики, сопоставимые с характеристиками декодирования по методу максимального правдоподобия. В частности в декодере кода (48, 24, 12) вероятность ошибки на бит 10~6 достигнута при отношении сигнал/шум 5 дБ, а вероятность ошибки на бит 10'9 - при отношении сигнал/шум 6.4 дБ.

4. Быстродействие разработанного декодера инвариантно к отношению сигнал/шум в широком диапазоне. Отсутствует необходимость в адаптивных подстройках и итеративных процедурах в декодере при изменении отношения сигнал/шум.

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

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

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

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

Внедрение результатов.

Диссертационная работа выполнялась в соответствии с планом научно-технических исследований кафедры «МРТУС» Московского государственного института электронной техники и

являлась составной частью мероприятий проектно-конструкторской деятельности ООО «Кедах Электронике Инжиниринг» по созданию аппаратного канального кодека. На базе ПЛИС были реализованы два варианта мягкого декодера квадратично-вычетного кода (48, 24, 12). Разработан испытательный стенда аппаратных кодеков, позволяющий осуществлять экспериментальное исследование декодеров. В результате замены жесткого декодера кода (48, 24, 12) разработанным мягким декодером в цифровом радиомодеме системы Link Rider RD 3.5/8 был получен энергетический выигрыш в 2 дБ динамического диапазона сигнала, что позволило увеличить дальность пролета радиорелейной линии системы в 1.26 раз. О вышеприведенных результатах свидетельствует соответствующий акт о внедрении. Личный вклад автора.

Основные результаты, полученные автором.

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

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

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

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

5. Разработан испытательный стенд кодеков, реализованных на ПЛИС.

На защиту выносятся.

1. Универсальная архитектура мягких декодеров коротких линейных блочных кодов. Мягкое декодирование линейного блочного кода с параметрами (п, к) «быстродействующим» вариантом декодера

осуществляется за 2п + 4(п - к) + ¡£>| +1 + ууЛШ ,К,т

аппаратных тактов, где - объем множества тестовых векторов ошибок (например, для кода (48, 24) оптимальным признано ¡£>|=250), а АРс,ш - число перестановок стобцов проверочной матрицы кода (для кода (48, 24) ЛГал%„и=8). 2. Методика синтеза аппаратных декодеров, позволяющая реализовать мягкий декодер произвольных коротких (для эффективной реализации на ПЛИС длина блока не больше 64) линейных блочных кодов. 5. Реализованный на микросхемах ПЛИС мягкий декодер квадратично-вычетного кода (48, 24, 12). Для вероятности ошибки на блок в диапазоне 10"' - КГ5 при декодировании обеспечивается близость к нижней границе Шеннона не хуже, чем 0.5 дБ; вероятность ошибки на бит 10"6 достигнута при отношении сигнал/шум 5 дБ, а вероятность ошибки на бит 10'9 - при отношении сигнал/шум 6.4 дБ. Это сопоставимо с результатами декодирования по методу максимального правдоподобия. Для аппаратных декодеров коротких кодов такой результат получен впервые. Апробация работы.

Основные научные положения и практические результаты диссертационной работы докладывались и обсуждались на заседаниях кафедры «МРТУС», на научно-технических совещаниях фирмы КЕЕ, а также научно-технических конференциях всероссийского и международного значения. Публикации.

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

Структура и объем работы.

Диссертация изложена на 150 страницах основного текста, состоит из введения, 4 глав, заключения, списка литературы из 63 наименований, содержит 39 рисунков и 2 таблицы. Работа сопровождается 2 приложениями. Содержание работы

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

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

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

Возможным приложением является гибридная система кодово-временного разделения каналов TD-CDMA. Это направление поддерживается в Европе комиссией ACTS (Advanced Communication technologies and Services) в проекте FMA2, в Америке комитетом TR4.5 ассоциации производителей -ТА! (Telecommunications Industry Association), а также другими развитыми странами. Большое внимание в развитии третьего поколения UMTS уделяется системам TD-CDMA с временным разделением дуплекса - TDD (Time Division Duplex). Актуальность применения коротких кодов в этих системах возрастает. Известно, что распределение задержек передачи данных на местных цифровых сетях в интересах глобальных

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

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

На (рис. 1) показано, что наилучшие блочные коды (коды Хэмминга, Голея, квадратично-вычетные и БЧХ коды) находятся в пределах 0.5 дБ от нижней границы Шеннона (sphere-packing bound - SPB).

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

Отметим основные недостатки этих алгоритмов:

1. Приближение к ML декодированию происходит только на больших отношениях сигнал/шум (алгоритм Чейза, алгоритм GMD (generalized minimal distance), обобщенный алгоритм Дейкстры - алгоритм А ).

Вероятность ошибки на слово

1Е+0

1Е-1

1Е-2

1Е-3

1Е-4

1Е-5

'в,4'„, случайный ~

ниж. гр Шеннона ;

(•.4)

Хэимшга

(24,12)

' случайный

(46,24)

квадратично-

ВЫЧСТ9ЫЙ

(24,12)

ниж гр Шеннона

(«,24)

случайный

1Е-6

(48.24) |

ни ж гр Шеннона

1 Е-7

0.5

1.5 2

2.5

3.5

4.5

ЕЬ/ЫО, дБ

Рис. 1. Характеристики коротких кодов в сравнении с нижней границей Шеннона и случайными кодами.

2. Используется арифметическое декодирование, зависящее от типа кода (алгоритм Чейза, алгоритм йМО). Данное обстоятельство не позволяет разработать универсальную архитектуру для декодирования различных кодов.

3. Высокая сложность декодирования для низких отношений сигнал/шум (алгоритм Чейза, алгоритм А ) приводит к неравномерной

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

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

Избежать указанные недостатков позволяет декодирование с помощью упорядочивания принятых бит в соответствии с информацией об их надежности и построения нового базиса на основании надежных символов с последующим генерированием множества тестовых кодовых слов, из которого выбирается результирующее. Объем множества тестовых слов определяет сложность алгоритма. На таком принципе построены алгоритм 08Э (декодирование на основе порядковой статистики) и алгоритм мягкого перестановочного декодирования Дмитриева. Решающим аргументом в пользу выбора алгоритма Дмитриева для аппаратной реализации явился меньший объем его множества тестовых слов, что обуславливает высшую производительность алгоритма Дмитриева при сопоставимых с алгоритмом ОБО характеристиках. Для достижения характеристик МЬ декодирования объем тестового множества алгоритма Дмитриева повышается линейно с ростом длины блока, в то время как для алгоритма ОБО этот объем растет почти экспоненциально.

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

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

отдельные модули, на основе которых построена структурная схема декодера.

Введем следующие условные обозначения.

С\п, к, с1)- передаваемый код с параметрами п, к, д.,

С - образующая матрица кода,

Н - проверочная матрица кода,

/,.- единичная матрица, размерности г = п-к ,

с - двоичный кодовый вектор с е С,

^-двоичный вектор, принятый от демодулятора,

е- двоичный вектор ошибок, е = у®с

(размерность 1 х п),

и - тестовый вектор ошибок (размерность 1 х к), й - множество всех тестовых ошибок - множество О, Л- множество всех тестовых кодовых векторов, обрабатываемых при декодировании одного принятого вектора,

Н = Н>

ф - вектор метрики надежности решений демодулятора о символах у ,

| | - абсолютное значение, при употреблении с вещественным числом, количество элементов при использовании с множеством,

| - операция конкатенации. © - операция сложения по модулю два. Кодовый вектор с кода С имеет следующую структуру с = (сп,С|,...,С(_|,С1,с,+|,...,£„_,) = (с,. | ск), где

с, = (с„, с, ,...,£:,_,)- проверочные символы,

с\ = (с, ,с1+) ,...,с„_,) - информационные. В алгоритме используется проверочная матрица следующего формата: Н = [/, где /,. - единичная матрица размерности г,

определяющая границы левой части матрицы, Я1 г матрица

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

Задача декодирования состоит в нахождении переданного кодового слова - вектора с, для которого функция

л-1

(2(с) = ф]~е' (1 -ф,)"' , Ус е А (А - множество кодовых

/=0

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

передано кодовое слово с (т. е. с = С), максимальна. Данная функция реализует функцию максимального правдоподобия в области ограниченных значений с,\/с е А .

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

Осуществляет перегруппировку принятых кодовых векторов в соответствии с их надежностью:

ф , < л\ф;\ < | ф) |(о </,/<«-1)

Модуль матричных операций.

Производит перестановку столбцов матрицы Н: Н' = А(#) формирование нового базиса Я* линейного пространства кодовых слов С*: Н'—-—>Н , отображение вектора у в линейное пространство кодовых слов С* с новым базисом Н*:

ф* =Л\ф,),Х =Л\Л),у =Л\у).

Модуль формирования гипотез.

Генерирует множество тестовых кодовых слов и осуществляет поиск максимального <2 для всех кодовых слов

множества: ск = ь>, Ф у*к,

с,=ск-К,,' с = (с,|с4), е = сфу\

/=о

Модуль обратной перестановки.

Производит восстановление искомого вектора - наиболее вероятной гипотезы переданного кодового слова.

= л*"'(с).

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

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

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

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

адресуемая запись столбца матрицы,

чтение по адресу строки и/или столбца матрицы,

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

«два» с т. н. «строкой-киллером»,

взаимная перестановка двух строк,

циклический сдвиг к столбцов.

Приведение проверочной матрицы кода (п, к) к ступенчато-приведенному виду в «быстродействующем» варианте модуля производится за 4(п-к) + NАШ ,«.„„ аппаратных тактов. В приведенном примере для кода (48, 24) оптимальное значение данного параметра составило N1Ш ,тш =8.

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

{){с) = (1 _ ф'')'' ■ В результате модификации алгоритма

1=0

при вычислении ^(с) удалось перейти от вычисления произведения к вычислению суммы. Перебор всех вариантов гипотез кодовых слов занимает в «быстродействующем» варианте модуля |£)| + 1 аппаратный такт, где - количество

элементов множества тестовых ошибок О. Разработан «компактный» вариант архитектуры модуля формирования гипотез, занимающий в 2.5 раза меньший объем аппаратных ресурсов, чем «быстродействующий» вариант, что составляет 20% эквивалентных логических вентилей от объема всей

архитектуры декодера. Работа «компактного» варианта производится за 3|£| + 1 аппаратных такта.

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

исходному базису си>1 = X ' (с). Обратная перестановка

кодового вектора размерности п выполняется за п аппаратных тактов. В зависимости от выбранной степени параллелизма архитектуры декодера, модуль обратных перестановок занимает о г 10% до 18% объема аппаратных ресурсов декодера.

В итоге «быстродействующий» вариант архитектуры декодера производи г декодирование блока кода (п. к) за 2 п + 4 (п - к) + + 1 + /УЛШ ,К,т аппаратных тактов.

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

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

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

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

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

Согласно изложенной методике реализованы оба варианта разработанной архитектуры кодека квадратично-вычетного кода (48, 24, 12) на базе ПЛИС ХСУ600Е-6НО240С. «Быстродействующий» и «компактный» варианты занимают соответственно 71% и 30% ресурсов программируемой логики микросхемы, емкость которой составляет 600 ООО эквивалентных логических вентилей.

Декодирование кодового блока для данного кода производится «быстродействующим» и «компактным» вариантами максимум за 547 и 1534 такта соответственно. Разводка схемы оптимизировалась для тактовой частоты 40.96 МГц («быстродействующий») и 30.72 МГц («компактный»). Достигнутая пропускная способность декодеров составляет для «быстродействующего» 2700000 бит/с (1350000 бит/с чисто информационного потока для данной скорости кода) и для «компактного» 1280000 бит/с (640000 бит/с чисто информационного потока).

Разработан испытательный стенд (рис. 2) декодеров, с помощью которого проведено экспериментальное исследование характеристик аппаратного декодера. При этом вероятность ошибки на бит 10'6 достигается при отношении сигнал/шум 5 дБ, а вероятность ошибки на бит 10'9 - при отношении сигнал/шум

Workstation

г1

| ! compact _RCI_ .

контроллер PCI

\ v

локальна| шина ,

КОДЕК (FPGA Xilinx)

flash

арбитр локальной

шины (CPLD Xilinx)

"I/

DSP

buffer

ПЛАТА КОДЕКА

Clock driver 40.96 MHz

buffer

' контрольная индикация

Рис. 2. Испытательный стенд кодеков

6.4 дБ, что соответствует результатам декодирования по методу максимального правдоподобия. Сравнение результатов компьютерного программного декодирования с экспериментальным аппаратным декодированием (рис. 3) выявляет совпадение представленных характеристик с точностью до 0.1 дБ. Данное обстоятельство позволяет сделать заключение о соответствии аппаратной реализации используемого алгоритма декодирования его математической модели.

Рис. 3. Экспериментальные зависимости вероятностей ошибок аппаратного декодирования кода (48,24) на бит (BER) и на блок (WER) по сравнению с рассчитанной нижней границей Шеннона для вероятности ошибки на блок (Shennon bound WER).

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

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

робастность алгоритма по отношению к величине отношения сигнал/шум в канале, инвариантность алгоритма к структуре блочного кода,

сравнительно небольшой требуемый объем множества тестовых векторов (обеспечивает приемлемое быстродействие аппаратного декодера).

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

сформулированы исходные данные для разработки архитектуры декодера.

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

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

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

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

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

Согласно изложенной методике были реализованы на ПЛИС ХСУ600Е-6НО240С оба варианта архитектуры декодера квадратично-вычетного кода (48, 24, 12) - одного из самых эффективных коротких блочных кодов. С помощью разработанного испытательного стенда было проведено экспериментальное исследование характеристик аппаратных декодеров. При этом достигнуты вероятностные характеристики,

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

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

Мягкий декодер кода (48, 24, 12) был применен в цифровом радиомодеме системы Link Rider RD 3.5/8.0 вместо используемого жесткого декодера. В результате был получен энергетический выигрыш в 2 дБ отношения сигнал/шум, что позволило увеличить дальность пролета радиорелейной линии системы в 1.26 раз.

Представляются перспективными дальнейшие

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

Публикации.

1. Суэтинов И. В. Анализ и выбор оптимального для

аппаратной реализации метода мягкого декодирования блочных кодов // Аспирант и соискатель, Москва, 2003 -№4 - с224-229.

2. Дмитриев О. Ф., Суэтинов И. В. Оценка вероятностных параметров в робастном алгоритме декодирования Дмитриева // Известия Вузов. Электроника, Москва, 2003 - № 6.

3. Суэтинов И. В. Аппаратная реализация устройств цифровой обработки на кристаллах программируемой логики FPGA для систем связи W-CDMA стандарта // Тез. докл. VII всерос. конф. «Микроэлектроника и информатика», Москва: МИЭТ, 2000 - el98.

4. Суэтинов И. В. Аппаратная реализация устройства сортировки данных на кристаллах программируемой логики FPGA для задач помехоустойчивого декодирования // Тез. докл. VIII всерос. конф. «Микроэлектроника и информатика», Москва: МИЭТ, 2001 -с252.

5. Дмитриев О. Ф., Суэтинов И. В. Аппаратная реализация мягкого декодера квадратично-вычетного кода (48, 24, 12) //Докл. VII междунар. науч.-техн. конф. «Радиолокация, навигация, связь», Воронеж: ВГУ, 2001, том 2 - el 1861191.

6. Суэтинов И. В. Обмен быстродействия на аппаратные затраты при переходе от многоканального декодера к малоканальному // Тез. докл. IX всерос. конф. «Микроэлектроника и информатика», Москва: МИЭТ, 2002-с212.

7. Суэтинов И. В. Варианты архитектур построения аппаратных декодеров мягких решений квадратично-вычетного кода // Докл. VIII междунар. науч.-техн. конф. «Радиолокация, навигация, связь», Воронеж: ВГУ, 2002, том 1 -с471-476.

Суэтинов И. В. Схемотехническая реализация устройства дешифрации номера позиции двоичного символа // Тез. докл. X всерос. конф. «Микроэлектроника и информатика», Москва: МИЭТ, 2003 - с305.

Суэтинов И. В. Оценка числа перестановок столбцов в декодере линейных блочных кодов // Докл. IX междунар. науч.-техн. конф. «Радиолокация, навигация, связь», Воронеж: ВГУ, 2003, том 2 - с1056-1061.

Дмитриев О. Ф., Суэтинов И. В. Оценка корректирующей способности линейных блочных кодов в каналах со стиранием // Материалы 58-й науч.-техн. конф. Санкт-Петербургского научно-технического общества им. А. С. Попова, Санкт-Петербург:СПбГЭТУ «ЛЭТИ», 2003 - с56-58.

Подписано в печать:

Заказ №253Тираж/^экз. Уч.-изд.л./^Формат 60x84 1/16. Отпечатано в типографии МИЭТ(ТУ). 124498, Москва, МИЭТ(ТУ).

Л

(

»

ч *

I

t

<

I i

17 557 * 17 5 5 7

Введение.

Глава 1. Анализ существующих декодеров и алгоритмов декодирования. Выбор оптимального для аппаратной реализации алгоритма декодирования.

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

§1.2 Основные классы кодов.

1.2.1 Линейные блочные коды.

1.2.2 Циклические коды.

1.2.3 Свёрточные коды.

1.2.4 Каскадные коды.

1.2.5 Турбо - коды.

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

1.3.1 GMD алгоритм.

1.3.2 Алгоритм Чейза.

1.3.3 Алгоритм Витерби для блочных кодов (алгоритм Вольфа)

1.3.4 Обобщенный алгоритм Дейкстры (алгоритм А*).

1.3.5 Декодирование на основе порядковой статистики.

1.3.6 Алгоритм перестановочного декодирования Дмитриева.

§ 1.4 Постановка задачи и выбор алгоритма декодирования для аппаратной реализации.

Выводы.

Глава 2. Декомпозиция алгоритма декодирования. Формирование структуры декодера.

§ 2.1 Введение в алгоритм Дмитриева.

2.1.1 Условные обозначения.

2.1.2 Особенности алгоритма Дмитриева.

§ 2.2 Предварительная декомпозиция алгоритма мягкого перестановочного декодирования Дмитриева.

2.2.1 Этапы алгоритма.

2.2.2 Дополнительные возможности алгоритма.

§ 2.3 Формирование структурных модулей декодера.

2.3.1 Возможности обмена быстродействия декодирования на щ объем аппаратных ресурсов.

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

§ 2.4 Переложение алгоритма декодирования для структурных модулей декодера.

2.4.1 Модуль сортировки.

2.4.2 Модуль матричных операций.

2.4.3 Модуль формирования гипотез.

2.4.4 Модуль обратной перестановки.

§ 2.5 Оценка числа перестановок столбцов в модуле матричных операций.

Выводы.

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

§ 3.1 Разработка модулей сортировки.

3.1.1 Задача сортировки. Выбор метода сортировки.

3.1.2 Сортировка методом простых вставок.

3.1.3 «Быстродействующий» модуль сортировки.

3.1.4 «Компактный» модуль сортировки.

§ 3.2 Разработка модулей матричных операций.

3.2.1 Вычислительное ядро модуля матричных операций.

3.2.2 Структура модуля матричных операций.

§ 3.3 Разработка модуля формирования гипотез.

3.3.1 «Быстродействующий» модуль формирования гипотез.

3.3.2 «Компактный» модуль формирования гипотез.

§ 3.4 Разработка модуля обратной перестановки.

Выводы.

Глава 4. Методика синтеза декодеров блочных кодов. Аппаратная реализация кодека (48, 24, 12) и его экспериментальное исследование.

§ 4.1 Изложение методики синтеза декодеров блочных кодов.

4.1.1 Исходные данные для построения декодера.

4.1.2 Подготовка данных ПЗУ декодера.

4.1.3 Расчет максимального числа перестановок столбцов.

4.1.4 Синтез модуля сортировки.

4.1.5 Синтез модуля матричных операций.

4.1.6 Синтез модуля формирования гипотез.

4.1.7 Синтез модуля обратных перестановок.

§ 4.2 Аппаратная реализация на ПЛИС кодека квадратично-вычетного кода (48, 24, 12).

4.2.1 Введение в ПЛИС.

4.2.2 Технологический процесс разработки устройств на ПЛИС

4.2.3 Расчетный этап построения декодера кода (48, 24, 12)

4.2.4 Структура кодека.

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

4.3.1 Назначение и состав испытательного стенда.

4.3.2 Взаимодействие компонентов испытательного стенда.

§ 4.4 Экспериментальное исследование характеристик аппаратного декодера.

4.4.1 Вероятностные характеристики декодера в канале с независимыми ошибками.

4.4.2 Вероятностные характеристики декодера в канале с пакетами ошибок.

Выводы.

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

На базе ПЛИС (программируемой логической интегральной схемы) были реализованы оба варианта архитектур мягкого декодера квадратично-вычетного кода (48, 24, 12) - одного из самых эффективных коротких блочных кодов. Декодеры оформлены в виде библиотечных элементов для их использования как в виде отдельной микросхемы ПЛИС, так и в составе произвольных устройств цифровой обработки, реализованных на ПЛИС. Для испытания аппаратных декодеров был разработан испытательный стенд кодека (кодер-декодера). В результате экспериментального исследования декодера кода (48, 24, 12) на стенде были получены вероятностные характеристики декодера для различных параметров канала и различных параметров декодирования.

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

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

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

Целью диссертационной работы является:

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

2. Создание методики, позволяющей аппаратно реализовать и оптимизировать мягкий декодер произвольного короткого блочного кода.

3. Разработка и экспериментальное испытание мягкого декодера квадратично-вычетного кода (48, 24, 12).

Научную новизну работы составляют:

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

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

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

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

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

Диссертационная работа выполнялась в соответствии с планом научно-технических исследований кафедры «МРТУС» Московского Государственного Института Электронной Техники и являлась составной частью мероприятий проектно-конструкторской деятельности ООО «Кедах Электронике Инжиниринг» по созданию аппаратного кодека.

Основными из полученных автором результатов, являются:

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

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

3. Разработка и аппаратная реализация на микросхемах ПЛИС двух вариантов мягких декодеров квадратично-вычетного кода

48,24,12).

4. Разработка испытательного стенда кодеков и экспериментальное исследование на нем кодеков (48, 24, 12). Положения, выносимые на защиту:

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

2. Методика проектирования и аппаратной реализации декодеров позволяет построить мягкий декодер произвольных коротких (для эффективной реализации на ПЛИС длина блока не больше 64) линейных блочных кодов.

3. Реализованный на микросхемах ПЛИС мягкий декодер квадратично-вычетного кода (48, 24, 12) для вероятности ошибки на блок в диапазоне 10"1 - 10"5 обеспечивает близость к нижней границе Шеннона не хуже, чем 0.5 дБ. При этом вероятность ошибки на бит 10"6 достигается при отношении сигнал/шум 5 дБ, а вероятность ошибки на бит 10"9 - при отношении сигнал/шум 6.4 дБ, что соответствует результатам декодирования по методу максимального правдоподобия. Для аппаратных декодеров коротких кодов такой результат получен впервые.

Основные научные положения и практические результаты диссертационной работы докладывались и обсуждались на заседаниях кафедры «МРТУС», на научно-технических совещаниях фирмы КЕЕ, а также научно-технических конференциях всероссийского и международного значения. Материалы, отражающие основное содержание работы, опубликованы в двух научных статьях и восьми трудах российских и международных научно-технических конференций.

Аннотация глав

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

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

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

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

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

Диссертация изложена на 150 страницах основного текста, состоит из введения, 4 глав, заключения, списка литературы из 63 наименований, содержит 39 рисунков и 2 таблицы. Работа сопровождается 2 приложениями. В приложениях предлагаются акт о внедрении результатов настоящей работы и принципиальные схемы разработанного декодера квадратично-вычетного кода (48, 24, 12).

Выводы

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

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

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

Согласно изложенной методике реализованы оба варианта разработанной архитектуры кодека квадратично-вычетного кода (48, 24, 12) на базе ПЛИС XCV600E-6HQ240C. «Быстродействующий» и «компактный» варианты занимают соответственно 71% и 30% ресурсов программируемой логики микросхемы, емкость которой составляет 600 ООО эквивалентных логических вентилей.

Декодирование кодового блока для данного кода производится «быстродействующим» и «компактным» вариантами максимум за 547 и 1534 такта соответственно. Разводка схемы оптимизировалась для тактовой частоты 40.96 МГц («быстродействующий») и 30.72 МГц («компактный»). Достигнутая пропускная способность декодеров составляет для «быстродействующего» 2700000 бит/с (1350000 бит/с чисто информационного потока для данной скорости кода) и для «компактного» 1280000 бит/с (640000 бит/с чисто информационного потока).

Разработан испытательный стенд декодеров, с помощью которого проведено экспериментальное исследование характеристик аппаратного декодера. При этом вероятность ошибки на бит 10"6 достигается при отношении сигнал/шум 5 дБ, а вероятность ошибки на бит 10"9 - при отношении сигнал/шум 6.4 дБ, что соответствует результатам декодирования по методу максимального правдоподобия. Сравнение результатов компьютерного программного декодирования с экспериментальным аппаратным декодированием выявляет совпадение представленных характеристик с точностью до 0.1 дБ. Данное обстоятельство позволяет сделать заключение о соответствии аппаратной реализации используемого алгоритма декодирования его математической модели.

Заключение

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

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

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

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

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

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

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

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

Согласно изложенной методике были реализованы на ПЛИС XCV600E-6HQ240C оба варианта архитектуры декодера квадратично-вычетного кода (48, 24, 12) - одного из самых эффективных коротких блочных кодов. «Быстродействующий» и «компактный» варианты декодера занимают соответственно 71% и 30% ресурсов программируемой логики микросхемы, емкость которой составляет 600 ООО эквивалентных логических вентилей.

Декодирование кодового блока для данного кода производится «быстродействующим» и «компактным» вариантами максимум за 547 и 1534 такта соответственно. Разводка схемы оптимизировалась для тактовой частоты 40.96 МГц («быстродействующий») и 30.72 МГц («компактный»). Достигнутая пропускная способность декодеров составляет для «быстродействующего» 2700000 бит/с (1350000 бит/с чисто информационного потока для данной скорости кода) и для «компактного» 1280000 бит/с (640000 бит/с чисто информационного потока).

С помощью разработанного испытательного стенда было проведено экспериментальное исследование характеристик аппаратных декодеров. При этом вероятность ошибки на бит 10"6 достигнута при отношении сигнал/шум 5 дБ, а вероятность ошибки на бит 10"9 — при отношении сигнал/шум 6.4 дБ, что соответствует результатам декодирования по методу максимального правдоподобия. Сравнение результатов компьютерного программного декодирования с экспериментальным аппаратным декодированием выявило совпадение представленных характеристик с точностью до 0.1 дБ. Данное обстоятельство позволяет сделать заключение о соответствии аппаратной реализации используемого алгоритма декодирования его математической модели.

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

Диссертационная работа выполнялась в соответствии с планом научно-технических исследований кафедры «МРТУС» Московского Государственного Института Электронной Техники и являлась составной частью мероприятий проектно-конструкторской деятельности ООО «Кедах Электронике Инжиниринг» по созданию аппаратного канального кодека. В результате работы разработан аппаратный декодер и испытательный стенд микросхемы кодека, о чем свидетельствует соответствующий акт о внедрении.

Мягкий декодер кода (48, 24, 12) был применен в цифровом радиомодеме системы Link Rider RD 3.5/8.0 вместо используемого жесткого декодера. В результате был получен энергетический выигрыш в 2 дБ динамического диапазона сигнала, что позволило увеличить дальность пролета радиорелейной линии системы в 1.26 раз.

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

1. Дмитриев О. Ф., Реализация возможности исправлять циклическим кодом (п, к) одиночные пакеты стираний длиной n-k, «Труды ученых институтов связи», М:Связь, 1963.

2. Блох Э. JL, Постов О. В., Исправление пакетов стираний с помощью блочных кодов, «Проблемы передачи информации», М:АН СССР вып. 14, 1963.

3. Питерсон У., Коды, исправляющие ошибки. М: Мир, 1964.

4. О. Ф. Дмитриев, Класс составных циклических кодов с простой реализацией, «Радиотехника», М:Связь, т. 19, N 4, 1964.

5. R. G. Gallager, "Low-density parity-check codes," IRE Transactions on Information Theory, vol. IT-8, pp. 21-28, Jan. 1962.

6. G. D. Forney, Jr., Concatenated Codes, Cambridge, Massachusetts: Massachusetts Institute of Technology, 1966.

7. G. D. Forney, Jr., Generalized Minimum Distance Decoding IEEE Trans. Inform. Theory, pp. 125-131, April 1966.

8. О. Ф. Дмитриев, Об одном алгоритме исправления независимых ошибок циклическими кодами, «Проблемы передачи информации», М:АН СССР т. 3, вып. 12, 1967 .

9. D. Chase, A Class of Algorithms for Decoding Block Codes with Channel Measurement Information IEEE Trans. Inform. Theory, pp. 170(181, January 1972.

10. Г. Т. Артамонов, Анализ производительности ЦВМ методами теории массового обслуживания. М:Энергия, 1972.11 .Д. А. Поспелов, Введение в теорию вычислительных систем. М:Советское радио, 1972.

11. J. К. Wolf, Efficient Maximum Likelihood Decoding of Linear Block Codes Using a Trellis IEEE Trans. Inform. Theory, pp. 7680, January 1978.13.3ахарченко H.B., Пудельман П.Я., Канонович В.Г. Основы передачи дискретных сообщений. М: Радио и связь, 1990.

12. D. J. Taipale and М. В. Pursley, An Improvement to Generalized-Minimum-Distance Decoding IEEE Trans. Inform. Theory, pp. 167-172, January 1991.

13. William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery, Numerical Recipes In С -The Art Of Scientific Computing, Cambridge University Press, Second Edition 1992.

14. C. Berrou, A. Glavieux, and P. Thitimajshima, "Near Shannon limit error-correcting coding and decoding: Turbo-codes," in ICC'93, Geneva, Switzerland, May 1993, pp. 1064-1070.

15. Y. S. Han, C. R. P. Hartmann, and C.-C. Chen, Efficient Priority-First Search Maximum-Likelihood Soft-Decision Decoding of Linear Block Codes IEEE Trans. Inform. Theory, pp. 1514-1523, September 1993.

16. Y. S. Han, C. R. P. Hartmann, and C.-C. Chen, Efficient Priority-First Search Maximum-Likelihood Soft-Decision Decoding of Linear Block Codes IEEE Trans. Inform. Theory, pp. 1514-1523, September 1993.

17. Evans, Merran, Hastings, Nicholas and Peacock, Brian, "Statistical Distributions, Second Edition", Wiley 1993 pp. 147-148.

18. Y. S. Han, Efficient Soft-Decision Decoding Algorithms for Linear Block Codes Using Algorithm A*, PhD thesis, School of Computerand Information Science, Syracuse University, Syracuse, NY 13244,1993.

19. Т. Kaneko, T. Nishijima, H. Inazumi, and S. Hirasawa, An Efficient Maximum-Likelihood Decoding Algorithm for Linear Block Codes with Algebraic Decoder IEEE Trans. Inform. Theory, pp. 320-327, March 1994.

20. Webb W.T., Hanzo L. Modern quadrature amplitude modulation -Pentech Press, London, 1994.

21. С. H. Papadimitriou, Computation Complexity, Addison-Wesley, Reading MA, 1994.

22. R. Pyndiah, A. Picart, and A. Glavieux "Performance of block turbo coded 16-QAM and 64-QAM modulations," Proceedings of GLOBECOM'95, pp. 1039-1043.

23. Proakis J.G. Digital communication. McGraw-Hill, New York, 1995.

24. R.Motowani and P. Raghavan, Randomized Algorithms, Cambridge Univ. Press, 1995.

25. M. P. C. Fossorier and S. Lin, Soft-Decision Decoding of LinearBlock Codes Based on Ordered Statistics IEEE Trans. Inform. Theory, pp. 1379-1396, September 1995.

26. S. Sivaprakasam, K.S. Shanmugan, An equivalent Markov model for burst errors in digital channels, IEEE Transactions on Communications ,vol.43,no.2/3/4,pp.l347-1355, 1995.

27. L. Ekroot and S. Dolinar, A* Decoding of Block Codes IEEE Trans on Communications, pp. 1052-1056, September 1996.

28. M. P. C. Fossorier and S. Lin, Computationally Efficient Soft-Decision Decoding of Linear Block Codes Based on Ordered Statistics IEEE Trans. Inform. Theory, pp. 738-751, May 1996.

29. S. Benedetto, G. Montorsi, D. Divsalar and F. Pollara, "Serial concatenation of interleaved codes: Performance Analysis, Design, and Iterative Decoding", JPL TDA Progress Report 42-126, August 15, 1996.

30. J Hagenauer, E. Offer and L. Papke, "Iterative decoding of binary block and convolutional codes", IEEE Transactions on Information Theory, vol. 42, pp.429-445, March 1996.

31. P. Jung, "Comparison of turbo-code decoders applied to short frame transmission systems," IEEE J. Select. Areas Commun., vol. 14, no. 3, pp. 530-537, 1996.

32. Т. Kaneko, T. Nishijima, and S. Hirasawa, An Improvement of Soft-Decision Maximum-Likelihood Decoding Algorithm Using Hard-Decision Bounded-Distance Decoding IEEE Trans. Inform. Theory, pp. 1314-1319, July 1997.

33. R. Pyndiah, "Iterative Decoding of Product Codes" in Proc. Int Symp. on Turbo Codes andRelated Topics, (Brest, France), pp. 7179, Sept. 1997.

34. Samuel J. MacMullan, Oliver M. Collins, "A Comparison of Known Codes, Random Codes, and the Best Codes", IEEE transactions on information theory, vol. 44, no. 7, November 1998.

35. S. Dolinar, D. Divsalar, F. Pollara, "Code Performance as a Function of Block Size", TMO Progress Report 42-133, May 15, 1998.

36. W.Turin, R.Nobelen, Hidden Markov modeling of flat fading channels,"IEEE Journal on Selected Areas in Communications, vol.16, no.9, pp. 1809-1817, December 1998.

37. Связь России в XXI веке. М.: MAC, 1999. - 737 с.

38. Архипкин В.Я., Дмитриев О.Ф., Нестратов М.В., Соколов А.Г., «Коррекция ошибок короткими блочными кодами в WLLсистемах», «Радиолокация, навигация, связь», Воронеж, 2000, том 2, стр. 943-948.

39. Суэтинов И. В. Аппаратная реализация устройств цифровой обработки на кристаллах программируемой логики FPGA для систем связи W-CDMA стандарта // Тез. докл. VII всерос. конф. «Микроэлектроника и информатика», Москва: МИЭТ, 2000-с198.

40. Дональд Э. Кнут, Искусство программирования, Основные алгоритмы, Вильяме Москва, 2000.

41. Дональд Э. Кнут, Искусство программирования, Сортировка и поиск, Вильяме Москва, 2000.

42. D. Agrawal and A. Vardy, Generalized Minimum Distance Decoding in Euclidean Space: Performance Analysis IEEE Trans. Inform. Theory, pp. 60-83, January 2000.

43. Anwer A.Khan, Iterative Decoding and Channel Estimation overHidden Markov Fading Channels, Blacksb rg,Virginia, May, 2000.

44. Суэтинов И. В. Аппаратная реализация устройства сортировки данных на кристаллах программируемой логики FPGA для задач помехоустойчивого декодирования // Тез. докл. VIII всерос. конф. «Микроэлектроника и информатика», Москва: МИЭТ, 2001 -с252.

45. Б.Я. Советов, С.А. Яковлев, Моделирование систем, М. Высш. шк., 2001.

46. Дмитриев О. Ф., Суэтинов И. В. Аппаратная реализация мягкого декодера квадратично-вычетного кода (48, 24, 12) // Докл. VII междунар. науч.-техн. конф. «Радиолокация, навигация, связь», Воронеж: ВГУ, 2001, том 2 -cl 186-1191.

47. Нестратов М.В., Дмитриев О.Ф. Коррекция пакетных ошибок квадратично-вычетным расширенным кодом (48,24,12) «Информатика и электроника», всероссийская конференция, Москва, 2001 -с237.

48. Нестратов М.В. Построение программной среды для разработки помехоустойчивых кодов, Докл. VIII междунар. науч.-техн. конф. «Радиолокация, навигация, связь», Воронеж: ВГУ, 2002, том 2 с930-936.

49. Суэтинов И. В. Обмен быстродействия на аппаратные затраты при переходе от многоканального декодера к малоканальному // Тез. докл. IX всерос. конф. «Микроэлектроника и информатика», Москва: МИЭТ, 2002 с212.

50. Нестратов М.В., Дмитриев О.Ф. Программная модель модифицированного алгоритма мягкого декодирования разделимых и неразделимых блочных кодов, Докл. IV междунар. науч.-техн. конф. "Цифровая обработка сигналов и ее применение", Москва, 2002 с26-28.

51. Суэтинов И. В. Варианты архитектур построения аппаратных декодеров мягких решений квадратично-вычетного кода // Докл. VIII междунар. науч.-техн. конф. «Радиолокация, навигация, связь», Воронеж: ВГУ, 2002, том 1 с471-476.

52. Б.Б. Самсонов, Е.М. Плохов, А.И. Филоненков, Т.В. Кречет, Теория информации и кодирование, Феникс, Ростов-на-Дону, 2002.

53. Нестратов М.В. Аспекты построения объектно-ориентированной программной системы моделирования помехоустойчивых кодов, Тез. докл. всерос. конф. «Информатика и электроника», Москва: МИЭТ, 2002 с158.

54. Дж. Хопкрофт Введение в теорию автоматов, языков и вычислений, М:Вильямс, 2002.

55. Карпов Ю. Г. Теория автоматов, СПб:Питер, 2002.

56. Нестратов М.В. Автоматизированная разработка в специализированной программной среде помехоустойчивых кодеков для передачи данных, Известия Вузов. Электроника, Москва, 2002 № 6 - с60-65.

57. Суэтинов И. В. Схемотехническая реализация устройства дешифрации номера позиции двоичного символа // Тез. докл. X всерос. конф. «Микроэлектроника и информатика», Москва: МИЭТ, 2003 -с305.

58. Суэтинов И. В. Оценка числа перестановок столбцов в декодере линейных блочных кодов // Докл. IX междунар. науч.-техн. конф. «Радиолокация, навигация, связь», Воронеж: ВГУ, 2003, том 2 -cl056-1061.

59. Суэтинов И. В. Анализ и выбор оптимального для аппаратной реализации метода мягкого декодирования блочных кодов // Аспирант и соискатель, Москва, 2003 №4 - с224-229.

60. Тел: +7 (095) 530-0102 Факс: +7 (095) 534-8654 www.kedah. ru kedahgkecLah. ru kedah@ma±l. canpnet. ru

61. Building 445, 124498, Zelenograd., Moscow, Russian Federation

62. Тел: +7 (095) 530-0102 Факс: +7 (095) 534-8654 www.kedah. ru kedab@kedali.ru kedahgmaiJ. compnet. ru1. ИНН 7735101696г. Москва, ЗАО "Международный Московский Банк" Р/с № 40702810300010161879, БИК 044525545, к/с 301018103000000005451. АКТ

63. Аппаратная реализация на ПЛИС и экспериментальное испытание двух вариантов мягкого декодера квадратично-вычетного кода (48, 24,12).

64. Разработка испытательного стенда кодеков, позволившего получать экспериментальные характеристики декодеров, построенных на базе ПЛИС XCV600E-6HQ240C в соответствии с разработанными архитектурой и методикой.

65. Председатель комиссии д.т.н., с.н.с. В.М. Смольянинов ""1. Члены комиссии:к.т.н., C.H.C. О.Ф. Дмшриевк.т.н. А.Р. Корниловк.т.н. П.В. Иванов