Программно - аппаратная реализация оптимального алгоритма декодирования каскадных кодов на базе кодов Рида - Соломона в адаптивных системах обмена данными тема диссертации и автореферата по ВАК РФ 05.12.13, кандидат наук Тамразян Георгий Михайлович

• Тамразян Георгий Михайлович
• кандидат наук
• 2017

Оглавление диссертации кандидат наук Тамразян Георгий Михайлович

СОДЕРЖАНИЕ

СПИСОК СОКРАЩЕНИЙ

ВВЕДЕНИЕ

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

Степень разработанности темы

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

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

Объект и предмет исследования

Соответствие рассматриваемой специальности

Научная новизна

Практическая ценность работы

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

Обоснованность и достоверность результатов работы

Апробация работы

Реализация результатов работы

Личный вклад автора

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

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

ИНФОКОММУНИКАЦИОННЫХ СИСТЕМАХ

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

1.1.1. Блоковые коды

1.1.2. Непрерывные (сверточные) коды

1.1.3. Укороченные циклические коды

1.1.4. Адаптивные системы передачи данных

1.2. Декодирование кодов Рида - Соломона

1.2.1. Алгоритм Форни

1.2.2. Алгоритм Берлекэмпа - Месси

1.2.3. Алгоритм Евклида

1.2.4. Алгоритм Гурусвами - Судана

1.3. Декодирование сверточных кодов. Алгоритм Витерби

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

1.4.1. Коды Рида - Соломона как внешняя ступень каскадного

кода

1.4.2. Сверточные коды как внутренняя ступень каскадного кода

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

1.5.1. Жесткие методы

1.5.2. Методы стирающего канала связи

1.5.3. Мягкие методы

1.6. Выводы по главе

ГЛАВА 2. ПРОЕКТИРОВАНИЕ КАСКАДНОГО КОДЕКА, ПОСТРОЕНИЕ ЕГО МАТЕМАТИЧЕСКОЙ МОДЕЛИ

2.1. Постановка задачи

2.2. Коды РС в стирающем канале связи

2.3. Двукратная выдача кодового блока

2.4. Произведение кодов РС и БЧХ

2.5. Мягкие подходы к декодированию кодов РС

2.5.1. Формирование мягких решений символов при фазовой модуляции

2.5.2. Формирование мягких решений символов при квадратурной амплитудной модуляции

2.5.3. Использование мягких оценок для определения стираний

2.6. Обобщенный каскадный код на базе кодов РС и сверточных кодов

2.7. Выводы по главе

ГЛАВА 3. ПРОГРАММНО - АППАРАТНАЯ РЕАЛИЗАЦИЯ АДАПТИВНОГО КАСКАДНОГО КОДЕКА, ОПТИМИЗИРОВАННОГО ПОД АРХИТЕКТУРУ ПЛИС

3.1. Аппаратная реализация алгоритма Витерби

3.1.1. Аппаратное описание структуры треллис-диаграммы

3.1.2. Аппаратная реализация блока BMU

3.1.3. Аппаратная реализация блока ACS

3.1.4. Блоки SMS и SPM

3.1.5. Обратный проход решетки. Модуль TBU

3.2. Аппаратная реализация оптимального алгоритма декодирования кода

Рида - Соломона

3.2.1. Оптимальная реализация SC-блока

3.2.2. Оптимальная реализация KES-блока

3.2.3. Оптимальная реализация CSEE-блока

3.2.4. Разработка оптимального АЛУ для реализации арифметических операций в полях Галуа

3.3. Разработка системы адаптации кодека

3.4. Выводы по главе

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

4.1. Выбор элементной базы и технических средств

4.2. Результаты лабораторных испытаний

4.2.1. Описание эксперимента

4.2.2. Результаты испытаний, проводимых при БРБК модуляции

4.2.3. Результаты испытаний, проводимых при РРБК модуляции

4.2.4. Результаты испытаний, проводимых при 8РБК модуляции

4.2.5. Обобщенные результаты испытаний для всей АСК

4.3. Результаты натурных испытаний

4.4. Выводы по главе

ЗАКЛЮЧЕНИЕ

Основные выводы по проделанной работе

Направление дальнейших исследований

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ А. Исходные коды моделей, использованных в работе

ПРИЛОЖЕНИЕ Б. сходные коды программ, использованные при аппаратной реализации кодека РС

ПРИЛОЖЕНИЕ В. Описание изобретения «Мягкий декодер последовательного турбокода»

СПИСОК СОКРАЩЕНИЙ

ACS - модуль сложения, сравнения и выбора метрик путей

BER - вероятность ошибки на бит

BMU - модуль расчета метрик ребер треллиса

BPSK - двоичная фазовая модуляция

CSEE - блок, выполняющий перебор Ченя и расчет значений ошибок

DC - блок расчета невязок

ELU - блок корректировки полинома локаторов ошибок

iBM - безынверсионный алгоритм Берлекэмпа - Месси

KES - блок решения ключевого уравнения

miBM - модифицированный алгоритм iBM

OFDM - мультиплексирование с ортогональным частотным разделением

PSK - фазовая модуляция

QAM - квадратурная амплитудная модуляция

QPSK - четырехпозиционная квадратурная фазовая модуляция

ROM - постоянно запоминающее устройство

SC - блок расчета синдромного многочлена

SMS - регистр хранения метрик узлов

SNR - соотношение сигнал-шум

SPM - регистр хранения траектории выживших путей

TBU - модуль обратного прохода треллиса

АБГШ - аддитивный белый гауссовский шум

АЛУ - арифметико-логическое устройство

АПД - аппаратура передачи данных

АСК - адаптивная система кодирования

АЦП - аналого-цифровой преобразователь

БМА - алгоритм Берлекэмпа - Месси

БЧХ - Боуза - Чоудхури - Хоквингема код

ГСА - алгоритм Гурусвами - Судана

ДСК - двоичный симметричный канал

ДСКС - двоичный симметричный канал со стираниями

ИИА - итеративный интерполяционный алгоритм

МРС - мягкое решение символа

НИР - научно-исследовательская работа

НОД - наибольший общий делитель

ОКР - опытно-конструкторская работа

ПЛИС - программируемая логическая интегральная схема

ПРВ - плотность распределения вероятностей

РС - Рида - Соломона код

СВЧ - сверхвысокочастотный (диапазон)

СПД - система передачи данных

СПК - система помехоустойчивого кодирования

ЦАП - цифро-аналоговый преобразователь

ШПС - шумоподобный сигнал

ЭВК - энергетический выигрыш кодирования

ВВЕДЕНИЕ

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

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

Применение тех или иных методов кодирования способно в значительной степени повысить достоверность принимаемой информации и обеспечить энергетический выигрыш кода (ЭВК) в канале связи до 10 дБ, приблизившись вплотную к порогу Шеннона, например, при использовании турбокодов или кодов с малой плотностью проверок на четность [7, 22, 37, 45, 46, 54]. Недостатком таких мощных кодов является большая избыточность, вносимая в передаваемое сообщение, применение итеративных преобразований, что приводит к существенному увеличению цикла управления на этапе обработки данных [1, 9, 96, 119, 126].

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

Для учета нестабильности передающей среды разрабатываются адаптивные системы кодирования (АСК), способные динамически подстраивать уровень вносимой избыточности в зависимости от текущего состояния канала связи.

Существуют различные подходы к реализации АСК, наиболее простым из которых является предварительная подготовка набора кодеков с динамическим переключением между ними. Такой метод не всегда является оптимальным, так как при переходе с одного кода на другой изменять зачастую необходимо лишь некоторые параметры кода [97]. Гораздо более эффективным методом реализации АСК является динамическая перестройка только тех параметров кода, которые отвечают за его избыточность [120]. В этой связи исследования, направленные на разработку гибких адаптивных алгоритмов применения помехоустойчивых кодов, и их реализация на современной (перспективной) элементной базе, несомненно, являются актуальными.

Степень разработанности темы

Концептуальные принципы развития цифровых систем связи заложены в основополагающих работах В.А. Котельникова, К.Е. Шеннона, Р.М. Фано и П. Элайеса. Значительный вклад в разработку теории повышения спектральной и энергетической эффективности систем обмена данными внесли такие зарубежные авторы как E.R. Berlekamp, R.C. Bose, R.W. Hamming, R.E. Blahut, J. Massey, I.S. Reed, G. Solomon, M. Sudan, G.D. Forney, R.G. Gallager, A.J. Viterbi, а также ряд отечественных ученых: В.И. Коржик, Э.Л. Блох, В.В. Зяблов, К.Ш. Зигангиров, В.В. Золотарев, Г.В. Овечкин, Л.Е. Варакин, в работах которых раскрываются теоретические основы построения различных классов избыточных кодов. Вместе с этим, применение помехоустойчивых кодов в адаптивных системах связи в указанных работах рассматривается в самых общих чертах и основывается на дискретной элементной базе, не отвечающей современным требованиям.

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

Целью работы является разработка и исследование адаптивных алгоритмов мягкого декодирования каскадных кодов на основе кодов Рида - Соломона (РС) и

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

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

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

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

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

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

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

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

Для решения поставленных задач и достижения намеченной цели использованы методы системного анализа, математического моделирования, теории вероятности, теории информационных систем, численные методы, а также методы программирования. Математическое моделирование производилось с использованием пакетов прикладных программ, таких как Mathcad, МАТЬАВ,

Simulink. Разработка и отладка программно-аппаратных средств велась с применением программ Quartus II 13.1 и Modelsim SE

Объект и предмет исследования

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

Соответствие рассматриваемой специальности

Содержание диссертационной работы соответствует следующим пунктам паспорта специальности 05.12.13 - Системы, сети и устройства телекоммуникаций:

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

п.п. 3 - разработка эффективных путей развития и совершенствования архитектуры сетей и систем телекоммуникаций и входящих в них устройств;

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

Научная новизна

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

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

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

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

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

Практическая ценность работы

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

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

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

2. Новый алгоритм вычисления полинома локаторов ошибок на базе модифицированного сдвигового регистра с обратными связями ориентированный

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

3. Метод параметрической адаптации системы обмена данными с каскадным кодированием, основанный на свободном конструктивном выборе числа ступеней промежуточных режимов относительно минимальной скорости кода РС.

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

Обоснованность и достоверность результатов работы

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

Введение диссертации (часть автореферата) на тему «Программно - аппаратная реализация оптимального алгоритма декодирования каскадных кодов на базе кодов Рида - Соломона в адаптивных системах обмена данными»

Апробация работы

Основные результаты диссертационной работы докладывались на Международной конференции «Радиоэлектронные устройства и системы для инфокоммуникационных технологий» REDS, (г. Москва, 2013г., 2015г.), XX Международной научно-технической конференции «Радиолокация. Навигация. Связь», (г. Воронеж, 2014г.), 17-ой Международной конференции «Цифровая обработка сигналов и её применение» DSPA (г. Москва, 2015г.), Международной научно-технической конференции «RLNC» (г. Воронеж, 2015г., 2016г.).

Результаты работы опубликованы в 17 печатных трудах, в числе которых 4 статьи в журналах, входящих в перечень ВАК, 1 патент РФ на изобретение, 12 трудов и тезисов докладов на Международных и Всероссийских научно-технических и научно-практических конференциях.

Реализация результатов работы

Материалы диссертации были использованы:

1. При выполнении ОКР «Каскад 1» (2010-2011 гг.) и НИР «Каскад 2» (2012-2013 гг.). Результаты работы используются в разработках ФНПЦ АО «НПО «Марс» для создания широкополосного помехоустойчивого канала связи в изделиях проекта «Трасса-22350».

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

Личный вклад автора

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

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

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

ГЛАВА 1.

ПРИМЕНЕНИЕ СРЕДСТВ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ В ИНФОКОММУНИКАЦИОННЫХ СИСТЕМАХ

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

Современные методы помехоустойчивого кодирования складываются из трех основных направлений: блоковые коды, непрерывные или сверточные коды, полярные коды, а также их различные комбинации [93, 94, 103, 108]. Рассматриваемая классификация избыточных кодов в соответствии с их конструктивными свойствами представлена на рисунке 1.1.

Рисунок 1.1 - Классификация основных направлений развития систем избыточного

кодирования

1.1.1. Блоковые коды

Блоковые коды - это класс помехоустойчивых кодов, которые можно описать парой чисел (п, к). В процессе кодирования блок из к символов сообщения преобразуется в больший блок из п символов кодового слова, образованного с использованием элементов данного алфавита. Если алфавит состоит только из двух элементов (0 и 1), код является двоичным и включает только двоичные разряды. В таком коде всегда можно указать начало и конец кодовой комбинации [85, 86]. Это свойство полезно в системе с переспросами и

при пороговом декодировании [104, 109, 111]. Данные коды в наибольшей степени приспособлены для адаптивных систем [36].

Наиболее простым способом преобразования к информационных символов в «-мерный кодовый блок является обращение к таблице соответствий, в которой каждому набору информационных слов соответствует единственный набор из п кодовых слов. Однако при построении кодов с длинными блоками, например, кода (127, 92), построение таблицы соответствия становится слишком трудоемкой процедурой, а ее хранение в памяти кодека требует существенных аппаратных затрат. В этом случае, более эффективным методом кодирования является использование так называемой порождающей матрицы О [38].

V, •

О = V 2 = " У 2 я > (1

ук1 _ Ук1 Ук2 •

где V - вектор кодового пространства, Уу - компоненты этого вектора. В матричном виде генерация кодового слова примет вид:

где т - информационный вектор.

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

При декодировании принятого кодового вектора, как правило, используют проверочную матрицу Н. Для каждой порождающей матрицы (к х «) существует матрица Н размером (« - к) х «, такая, что строки матрицы О ортогональны к строкам матрицы Н [115]. Иными словами, ОН = 0. Представим порождающую матрицу в систематическом виде:

где Р - массив четности, входящий в состав порождающей матрицы, 1к -единичная матрица, размерностью (к х к).

и = т ■ О,

(1.2)

(1.3)

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

Н = [1п.к \ Рт]. (1.4)

Поскольку проверочная матрица Н создана так, чтобы удовлетворять условиям ортогональности, она позволяет проверять принятые векторы на предмет их принадлежности заданному набору кодовых слов [115]. и будет кодовым словом, генерируемым матрицей О, тогда и только тогда, когда выполняется равенство:

и • Нт = 0. (1.5)

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

Я = и + е, (1.6)

где е - вектор ошибки, внесенной каналом связи. Тогда синдром принятого сигнала будет определяться следующим образом:

5 = Я • Нт . (1.7)

При отсутствии ошибок в принятом векторе, то есть при е = 0 ^ Я = и, синдром равен нулю. В противном случае, если 5 Ф 0, переданный вектор был искажен в канале связи, а значение синдрома 5 позволит установить характер этого искажения. Зная характер ошибки, декодер пытается ее локализовать и исправить, либо, если его мощности недостаточно для этого, он посылает запрос на перевыдачу этого сообщения [32, 89]. Используя уравнения (1.6) и (1.7), можно представить синдром 5 в следующем виде [24]:

5 = (и + еУ Нт = и • Нт + е • Нт . (1.8)

Согласно выражению (1.5) произведение кодового вектора и проверочной матрицы равно нулю, получим выражение:

5 = г • Нт . (1.9)

Уравнение (1.9) дает взаимно однозначное соответствие между синдромным вектором 5 и вектором ошибки е. Зная значение вектора ошибки е, достаточно вычесть (эквивалентно сложению для двоичных символов) его из принятого вектора Я, таким образом, ошибка будет исправлена [55].

Рассмотренный синдромный подход к декодированию блоковых кодов является обобщенным способом, и для декодирования некоторых кодов описанных действий будет недостаточно [112]. Так при декодировании недвоичных кодов, таких как, например, кодов Рида - Соломона, синдром позволит только локализовать ошибку, а для ее исправления потребуется вовлечение дополнительного математического аппарата [12, 113, 122].

1.1.2. Непрерывные (сверточные) коды

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

Сверточный код образуется множеством всех двоичных последовательностей, порождаемых сверточным кодером. Теоретически эти последовательности бесконечны, однако, на практике, состояние сверточного кодера периодически устанавливается в некоторое заранее известное состояние и, следовательно, порождаемый код приобретает характер блокового кода [110].

Работу кодера можно описать с помощью конечного автомата. Состояния такого автомата, на примере кода (7, 5), показаны на рисунке 1.2.

Рисунок 1.2 - Диаграмма состояний сверточного кодера (7, 5)

Сам кодер представляет собой сдвиговый регистр, входы которого объединены между собой определенным образом. Физические связи кодера определяются выбранными порождающими полиномами. Для рассматриваемого примера эти полиномы равны g0 = 7 ( 1 1 1 ), g1 = 5 ( 1 0 1 ). Схема кодера представлена на рисунке 1.3. В общем случае, сверточный кодер скорости к/п использует к регистров сдвига, по одному на каждый вводимый в кодер информационный символ, и п логических элементов, выполняющих операцию исключающего ИЛИ над содержимым регистров и символами на входе кодера. На практике, обычно рассматриваются только двоичные сверточные коды, то есть коды скоростью 1/п. Их параметры записывают в виде п порождающих полиномов, записанных в восьмеричном виде ( g0 , ... , g1 ).

Рисунок 1.3 - Структурная схема сверточного кодера (7, 5)

Общая длина регистров сдвигов т называется памятью кода. Кодовое ограничение определяется как число информационных символов на входе кодера, которые влияют на кодовые символы на его выходе. Для кодеров скорости 1/2 оно равно К = т + 1.

Сверточный кодер является линейной постоянной во времени системой, импульсной отклик которой задан порождающими полиномами. С помощью этих полиномов можно записать выходную последовательность кодера в следующем виде [56]:

т

*(,)И=£ и[ -1 ]• г, [I] (1.10)

I=0

где 0 <у < п. Выходные последовательности V (/) равны дискретной свертке входной последовательности и с порождающими полиномами g0 , ... , gn-1.

Динамическая структура сверточного кодера позволяет развернуть во времени его диаграмму состояний и построить решетчатую диаграмму (треллис). Треллис строится следующим образом: в соответствии с диаграммой состояний кодера (рисунок 1.2) на каждом временном интервале соединяются ребрами состояния на /-ом и (/+1)-ом тактах. При этом, если на /-ом такте кодеру на вход поступает 1, то такое ребро на треллисе будет показано пунктирной линией, а при поступлении 0 - сплошной. Таким образом, при сверточном кодировании на решетчатой диаграмме формируется некий путь, по которому однозначно определяется кодовая комбинация.

Построение треллис-диаграммы удобнее всего проиллюстрировать на конкретном примере. Положим, что на вход рассматриваемого сверточного кодера (7, 5) поступают символы и = ( 110100 ). Треллис данного кодера представлен на рисунке 1.4. В нижней части рисунка показана входная информационная последовательность, а в верхней - сформированный код. Кодовая комбинация строится в виде непрерывного пути, который выделен на этой диаграмме жирными линиями. Из рисунка видно, что кодер сформировал на решетке выходную последовательность V = ( 111010000111 ). Воспользовавшись

формулой (1.10), нетрудно убедиться, в том, что полученная при помощи этой решетки комбинация верна.

11 10 10 00 01 11

Рисунок 1.4 - Треллис-диаграмма сверточного кодера (7, 5)

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

1.1.3. Укороченные циклические коды

Циклические коды составляют класс кодов, исправляющих ошибки, кодирование и декодирование которых основано на полиноминальном представлении. Простая реализация этих кодов использует регистры сдвига и логические схемы. Их свойства делают их удобными в аппаратной реализации. Одним из распространенных циклических кодов является код РС [42Ошибка! Источник ссылки не найден.].

Обозначим как С некий двоичный циклический код (п, к), и -информационное сообщение, V - соответствующее ему кодовое слово. Представить кодовый вектор V можно в полиноминальном виде:

V = {уо, VI,..., VI 4х) = V) + + ••• + ^плхП~Х • (1.11)

Переменная х служит индикатором относительного положения элемента VI в кодовом слове в виде монома v/X полинома v(x). Линейный код С является циклическим, если циклический сдвиг любого слова из кодового пространства С дает слово из этого же кодового пространства. В полиноминальном виде циклический сдвиг на одну позицию, обозначенный V (1) (х), соответствует умножению на х по модулю (хп - 1),

у(х) е С о V1 (х) — XV(х)шоё(хп - 1)е С. (1.12)

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

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

информационная последовательность и(х) — и0 ^ щх ^... ^ и^ X * преобразуется в

кодовую комбинацию вида:

v(x)— хп-ки(х)+ (хп-ки(х)шоё г(х)), (1.13)

степень которого не превышает п - 8 - 1. Таким образом, укороченный код С является линейным (п - 8, к - 8, ds) кодом с кодовым расстоянием ds > d. В общем случае укороченный код не является циклическим кодом.

Фундаментальное свойство укороченных циклических кодов С состоит в том, что для их обработки могут быть использованы те же самые кодеры и декодеры. Для компьютерного моделирования гораздо проще дополнять слова нулями на старших позициях и использовать те же самые алгоритмы кодирования и декодирования, рассмотренные в этой главе. Этот способ широко используется в аппаратной реализации кодов РС. Очевидно, что нули на старших позициях сообщения не должны включаться в кодовое слово. Кроме того, декодер модифицируется таким образом, что принятое слово г(х) умножается на хп'к+я вместо умножения на хп-к по модулю g(x) в обычном декодере. Укороченные конструкции также прекрасно подходят для реализации адаптивных кодеков.

1.1.4. Адаптивные системы передачи данных

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

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

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

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

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

и е £, (1.14)

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

Если объект таков, что его изменение в процессе адаптации удобно осуществлять с помощью параметров и1 , ... , ип , т. е.

и = ип ), (1.15)

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

U e S с Rq т. е. множество S является континуумом, во втором - U е S = D, где D - дискретное множество значений управления U.

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

U = (W, С) , (1.16)

где W - структурные факторы, с помощью которых можно изменять структуру объекта адаптации, a C = ( c1 , ... , ck) - адаптируемые параметры объекта (параметры (1.15), с помощью которых реализуется параметрическая адаптация).

Целенаправленная вариация структурных факторов дает возможность адаптировать структуру объекта. Такая декомпозиция управления U на структурные W и параметрические C факторы позволяет более эффективно решать задачи адаптации сложных объектов, для которых параметрическая адаптация малоэффективна [102, 120].

Задачу адаптации можно записать в следующем виде:

Q(W, С) ^ min min ^ WС, (1.17)

WeEW CeECW V /

где EW - множество допустимых структур W; ECW - множество допустимых параметров C, соответствующих структуре, определяемой W; W- оптимальная структура; C'w - оптимальные параметры этой структуры. Так как W однозначно

определяет структуру объекта, то W можно условно называть структурой. Очевидно, что:

S = EW • ECW > (1.18)

то есть множество S допустимых управлений при адаптации образуется как произведение множеств допустимых структур EW и параметров ECW этих структур. Блок-схема решения задачи (1.17) показана на рисунке 1.5, из которого хорошо виден иерархический характер адаптации.

Рисунок 1.5 - Двухконтурная схема структурной адаптации

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

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

Рисунок 1.6 - Классификация типов адаптации

Прежде всего, структурную адаптацию удобно подразделить на альтернативную и эволюционную. Альтернативная адаптация отличается тем, что множество допустимых структур ЕЖ невелико и содержит 2-5 альтернативных структур. Эволюционная адаптация моделирует процесс биологической эволюции. Этот алгоритм отличается введением незначительных вариаций структуры дW, моделирующих случайные мутации, которые также незначительно изменяют эффективность Q адаптируемого объекта. «Мутации» структуры дW и правило отбора, позволяющее выявлять ее благоприятные вариации, и образуют механизм эволюции, с помощью которого строится последовательность улучшающихся структур:

Щ ^Щ ^... ^ Wn ^ЩпА ^... , (1.19)

обладающих свойством Щ„ У Щ„_1 (п = 1, 2, ...), где знак предпочтения У имеет смысл:

<2(Щ) < 0(Щп_1). (1.20)

Заметим, что иногда допустимы нарушения соотношения (1.20), например, в случае, когда вариацией структуры Ж не удается получить лучшую, чем Ж , по критерию (1.20). Тогда выбирают лучшую из «мутированных» структур, что нарушает (1.20), но обеспечивает процедуре эволюции глобальные свойства, очень ценные в задачах структурной адаптации.

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

1.2. Декодирование кодов Рида - Соломона

Коды РС были открыты в 1960 году американскими учеными Ридом и Соломоном, как частный случай недвоичных кодов

Боуза - Чоудхури - Хоквингема (БЧХ). В настоящее время коды РС являются

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

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

- вычисления синдрома ошибки (синдромный декодер);

- построения полинома локаторов ошибок, осуществляемого либо посредством высокоэффективного, но сложно реализуемого алгоритма Берлекэмпа - Месси (БМА), либо посредством простого, но медленного алгоритма Евклида;

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

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

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

Схема быстрого декодирования кодов РС приведена на рисунке 1.7. Здесь особого внимания и более детального рассмотрения заслуживают алгоритм по поиску локаторов искажений, а также алгоритм определения характера ошибок, предложенный Форни [23].

Приёмник

С(х) = и(х) + е(х)

1 Искаженные данные

<

Вычисление компонентов синдрома =С(а,-) ] = 1,... ,2Ь

2 t синдром

Рисунок 1.7 - Схема быстрого декодирования кодов Рида - Соломона

1.2.1. Алгоритм Форни

Предположим, что в приемник аппаратуры передачи данных (АПД) поступила кодовая комбинация кода РС с замешанным в нее шумом:

С(х) = и(х)+е(х), (1.21)

где и(х) - переданная передатчиком АПД кодовая комбинация, в которой в процессе передачи по каналу связи произошло V ошибок, отображаемых

многочленом е(х) степени V. Каждый ненулевой компонент е(х) описывается парой элементов: У] - величина ошибок и X} - номер позиции ошибки (локатор ошибки). У] , X - элементы ОЕ(д), при этом элемент X\ = а , а1 е ОЕ(д). Для описания ошибок используются: Многочлен локаторов ошибок:

V

Л(х) = ^(1 -х• х1) = Л • хV + Л^ • х"-1 +... + ^ • X + л0, (1.22)

г=1

имеющий корни X1, * = 1, • • •, V, взаимные к локаторам ошибок, то есть X\ •а = 1. Многочлен значений ошибок П(х):

а.(х ) = 5 (х )• Л(х )-(шо<1 X 2?), (1.23)

где £(х) - синдромный многочлен бесконечной степени, для которого известны только 21 коэффициентов для поступившей комбинации РС-кода. Синдром рассчитывается согласно формуле (1.24):

2? 2? V

5(х) = £ 5 • X7 = £ £ ¥> • XI • х^1 . (1.24)

7=1 7=1 г =1

Здесь 5 = • X/= в(а]) - элемент синдрома, а] - корень порождающего

г=1

многочлена РС-кода. Значения = в(а]) задаются проверками:

5 = С (а7 ) = ы(ау )+ в(ау ) = в(ау ), (1.25)

где т0 < у < т0 + 2? -1 при т0 = 1.

Равенство (1.23) определяет множество из (21 - V) уравнений и называется ключевым уравнением, так как оно представляется «ключом» решения задачи декодирования. Это становится понятным, если учесть, что степень О(х) не превышает (V - 1), и поэтому справедливо:

[л(х )• 5(х)] 2? -1= 0, (1.26)

где [а(х)]т = атХт + ат+1Хт+1 + ... + апХ" .

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

С(х) = и(х) + е(х) [26].

Простейшим путем нахождения корней многочлена Л(х) является метод полного перебора всех возможных значений заданного поля, известный как процедура Ченя. Эта процедура состоит в последовательном вычислении Л(а1 ) для каждого 1 и сравнении полученных значений с нулем. Если величина Л(а-к ) равна нулю, то ак является взаимной к корню многочлена локаторов ошибок, и к-й элемент кодовой комбинации содержит ошибку. Наиболее простым способом вычисления значения Л(х) в точке в является схема Горнера:

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

СПИСОК ЛИТЕРАТУРЫ

1. Ajaz, S. An efficient radix-4 Quasi-cyclic shift network for QC-LDPC decoders / S. Ajaz, H. Lee // IEICE Electronics Express. 2014. - January. - vol. 11. - no. 2. - pp. 1-6.

2. Ashenden, P. J, The Designer's Guide to VHDL / Second Edition, Morgan Kaufmann Publishers. - 2004.

3. Bahl, L.R. Optimal decoding of linear codes for minimizing symbol error rate / L.R. Bahl, J. Cocke, F. Jelinek, J Raviv // IEEE Transactions on Information Theory. -1974. - March. - Vol. IT-20. - pp. 284 - 287.

4. Benedetto, S. Principles of Digital Transmission With Wireless Applications / S. Benedetto, E. Biglieri // New York, USA: Kluwer Academic / Plenum Publisher. -1999.

5. Berlekamp, E. R. Nonbinary BCH Decoding // International Symposium on Information Theory. - 1967.

6. Berlekamp, E. R. The Application of Error Control to Communications / E. R. Berlekamp, R. E. Peile, S. P. Pope // IEEE Communications Magazine. - 1987. - April. - vol. 25. - no. 4. - pp. 44-57.

7. Berrou, C. Near Shannon limit error-correcting coding and decoding: Turbo Codes / C. Berrou, A. Glavieux, P. Thitimajshima // in Proc. IEEE Int. Conf. Communications (ICC'93). - 1993. - May. - pp. 1064-1070.

8. Bhaskar, R. Efficient Galois Field Arithmetic On SIMD Architectures / R. Bhaskar, P. K. Dubey, V. Kumar, A. Rudra // ACM Symp. On Parallel Algorithms and Architectures. - 2003. - pp. 256-257.

9. Blanksby, A. J. A 690-mW 1-Gb/s 1024-b, Rate ^ Low-Density Parity-Check Code Decoder / A. J. Blanksby, C. J. Howland // IEEE J. Solid-State Circuits. - 2002. -March. - vol. 37. - no. 3. - pp. 404-412.

10. Bose, R. C. Further Results on Error Correcting Binary Group Codes / R. C.

Bose, D. K. Ray-Chaudhuri // Information and Control. - 1960. - September. - vol. 3. -pp. 279-290.

11. Burton, H. O. Inversionless decoding of binary BCH codes / IEEE Trans. Inform. Theory. - 1971. - September. - vol. IT-17. - pp. 464-466.

12. Carrasco, R. A. Non-binary error control coding for wireless communication and data storage / R. A. Carrasco, M. Johnston; J. Wiley & Sons, Ltd, - 2008, p.-302.

13. Chang, H.-C. New serial architectures for the Berlekamp-Massey algorithm / H.-C. Chang, C. B. Shung // IEEE Trans. Commun. - 1999. - April. - vol. 47. - pp. 481483.

14. Chen, Y. Small Area Parallel Chien Search Architectures for Long BCH Codes / Yanni Chen, Keshab K. Parhi // IEEE transactions on very large scale integration (VLSI) systems. - 2004. - May. - vol. 12. - no. 5. - pp. 545-549.

15. Chien, R. T. Decoding procedures for Bose-Chaudhuri-Hocquenghem codes / IEEE Trans. - 1964, - IT-10, pp. 357-363.

16. Cho, J. Strength-Reduced Parallel Chien Search Architecture for Strong BCH Codes / J. Cho, W. Sung // IEEE transactions on circuits and systems - II: express briefs. - 2008. - May. - vol. 55. - no. 5. - pp. 427-431.

17. Cho, T. A High-Speed Low-Complexity Modified Radix-25 FFT Processor for High-Rate WPAN Applications / T. Cho, H. Lee // IEEE Transactions on VLSI Systems. - 2013. - January. - vol. 21. - no. 1. - pp. 187-191.

18. Choi, C.-S. High-Throughput Low-Complexity Four-Parallel Reed-Solomon Decoder Architecture for High-Rate WPAN Systems / C.-S. Choi, H.-J. Ahn, H. Lee // IEICE Transactions on Communications. - 2011. - May. - vol. E94-B. - no. 05. - pp. 1332-1338.

19. Clarke, C.K.P. Reed-Solomon error correction / BBC R&D White Paper, WHP 031. - 2002. - July.

20. Clevorn, T. Low-Complexity Belief Propagation Decoding by Approximations with Lookup-Tables / T. Clevorn, P. Vary // in Proc. 5th Int. ITG Conference on Source

and Channel Coding (SCC 2004), Erlangen, Germany. - 2004. - January.

21. Cyclone II Device Family Data Sheet / Altera Inc. - 2005. - July.

22. David Hayes. FPGA implementation of a Flexible LDPC decoder, A thesis submitted in partial fulfilment of the requirements for the degree of Bachelor of Engineering in Telecommunication Engineering at The University of Newcastle, Australia. - 2008. - October 28.

23. Elharoussi, M. VHDL Design and FPGA Implementation of a Parallel ReedSolomon (15, K, D) Encoder/Decoder / M. Elharoussi, A. Hamyani, M. Belkasmi // International Journal of Advanced Computer Science and Applications. - 2013. - vol. 4. - no. 1.

24. Favalli, M. Optimization Of Error Detecting Codes For The Detection Of Crosstalk Originated Errors / M. Favalli, C. Metra // Design Automation and Test in Europe. - 2001. - March. - pp. 290-296.

25. Fettweis, G. The Tactile Internet: Applications and Challenges / IEEE Vehicular Technology Magazine. - 2014. - vol. 9. - no. 1. - pp. 64-70.

26. Forney, G. D. On Decoding BCH Codes, // IEEE Transactions on Information Theory. - 1965. - October. - vol. IT-11. - pp. 549-557.

27. FPGA Designer Quickstart Guide, whitepaper, / Altium Inc. - 2005. - July.

28. Guruswami, V. Improved decoding of Reed-Solomon and algebraic-geometric codes / V. Guruswami, M. Sudan // IEEE Trans. Inf. Theory. 1999. - v.45. - pp.755764.

29. Hagenauer, J. Iterative Decoding of Binary Block and Convolutional Codes / J. Hagenauer, E. Offer, L. Papke // IEEE Trans. Inform. Theory. - 1996. - March. - vol. 42. - no. 2. - pp. 429-445.

30. Han, T. Fast area-efficient VLSI adder / T. Han, D. A. Carlson // in Proc. 8th Symp. on Comp. Arithmetic. - 1978. - May.

31. Hasan, M. A. Algorithms and architectures for a VLSI Reed-Solomon DRAFT /

M. A. Hasan, V. K. Bhargava, T. Le-Ngoc // 2001. - February.

32. Hunt, A. Hyper-codes: High-performance low-complexity error-correcting codes / A. Hunt, S. Crozier, D. Falconer // Proceedings of the 19th Biennial Symposium on Communications. - 1998. - May 31 to June 3. - pp. 263-267.

33. Jeong, B. Low-Complexity Non-Iterative Soft-Decision BCH Decoder Architecture for WBAN Applications / Boseok Jeong, Hanho Lee // Journal of Semiconductor and Science Technology. - 2015. - April 1.

34. Jung K. Low-Complexity Multi-Mode Memory-based FFT Processor for DVB-T2 Applications / K. Jung, H. Lee // IEICE Transactions on Fundamentals of Electronics, Communications, and Computer Sciences, Systems. - 2011. - November. -vol. E94-A. - no. 11. - pp. 2376-2383.

35. Kaur, S. VHDL Implementation of Reed-Solomon code / Thesis, Thapar Institute of Engg. - 2006.

36. Keller, T. A turbo-coded burst-by-burst adaptive wideband speech transceiver / T. Keller, M. Münster, L. Hanzo // IEEE J. Select. Areas Commun. - 2000. - November. -pp. 2363-2372.

37. Kim, S. A Reduced-Complexity Architecture for LDPC Layered Decoding Schemes / S. Kim, G. E. Sobelman, H. Lee // IEEE Transactions on VLSI Systems. -2011. - June. - vol. 19. - no. 6. - pp. 1099-1103.

38. Kung, L.-P. Introduction To Error Correcting Codes / NSDL Scout Report for Math, Engineering, and Technology. - 2003.

39. Kwon, S. An area-efficient VLSI architecture of a Reed-Solomon decoder/encoder for digital VCRs / S. Kwon, H. Shin // IEEE Trans. Consumer Electronics. - 1997. - November. - pp. 1019-1027.

40. Lee, H. High-Speed VLSI Architecture for Parallel Reed-Solomon Decoder / IEEE transactions on very large scale integration (VLSI) systems. - 2003. - April. -vol. 11. - no. 2. - pp. 288-294.

41. Lee, K. A High-Speed Low-Complexity Concatenated BCH Decoder

Architecture for 100Gb/s Optical Communications / K. Lee, H.-G. Kang, J.-I. Park, H. Lee // Journal of Signal Processing Systems. - 2012. - January. - vol. 6. - no. 1. - pp. 43-55.

42. Leven, A. Status and recent advances on forward error correction technologies for lightwave systems / A. Leven and L. Schmalen // J. Lightw. Technol. - 2014. - pp. 2735-2750.

43. Li, J. Realizing unequal error correction for nand flash memory at minimal read latency overhead / J. Li, K. Zhao, J. Ma, T. Zhang // IEEE Trans. Circuits Syst. II, Exp. Briefs. - 2014. - May. - vol. 61. - no. 5. - pp. 354-358.

44. Liu, K. J. R. Algorithm-based low-power and high-performance multimedia signal processing / K. J. R. Liu, A.-Y. Wu, A. Raghupathy, J. Chen. // IEEE. - 1998. -June. - vol. 86. - pp. 1155-1202.

45. MacKay, D. J. C. Near Shannon limit performance of low density parity check codes / D. J. C. MacKay, R. M. Neal // Electron. Lett. - 1997. - vol. 33. - no. 6. - pp. 457-458.

46. Marchand, C. Hign-speed Conflict-free Layered LDPC Decoder for the DVB-S2, -T2 and-C2 Standards / C. Marchand, L. Conde-Canencia, E. Boutillon // IEEE Workshop on Signal Processing Systems. - 2013.

47. Mastrovito, E. D. VLSI Architectures for Computations in Galois Fields / Linkoping University, Sweden. - 1991.

48. McEliece, R. J. Finite Fields for Computer Scientists and Engineers / Boston: Kluwer Academic. - 1987.

49. Morris J. Reconfigurable Computing - FPGA structures, lecture notes, University of Auckland, NZ

50. Nicolaidis, M. Design for Soft-Error Robustness to Rescue Deep Submicron Scaling // White Paper, iRoC Technologies. - 2000.

51. Orlando, G. A Super-Serial Galois Fields Multiplier For FPGAs And Its Application To Public-Key Algorithms / G. Orlando, C. Paar // Proc. of the 7th Annual

IEEE Symposium on Field Programmable Computing Machines, FCCM'99, Napa Valley, California. - 1999. - April. - pp. 232-239.

52. Parhi, K. K. Eliminating the fanout bottleneck in parallel long BCH encoders // IEEE. Trans. Circuits Syst. I. - 2004. - March. - vol. 51. - no. 3. - pp. 512-516.

53. Park, J.-I. Area-Efficient Truncated Berlekamp-Massey Architecture for ReedSolomon Decoders / J.-I. Park, H. Lee // IET Electronics Letters. - 2011. - February. -vol. 47. - no. 4. - pp. 241-243.

54. Park, Y. S. A fully parallel nonbinary LDPC decoder with fine-grained dynamic clock gating / Y. S. Park, Y. Tao, Z. Zhang // IEEE J. Solid-State Circuits. - 2015. -February. - vol. 50. - no. 2. - pp. 464-475.

55. Prange, E. Cyclic Error-Correcting Codes in Two Symbols, Air Force Cambridge Research Center-TN-57-103. - 1957. - September.

56. Purser, M. Introduction to Error Correcting Codes / Artech House. BostonLondon. - 1995.

57. Quartus II Handbook Volume 1: Design and Synthesis. Altera Inc. - 2015. -May.

58. Quartus II Handbook Volume 2: Design Implementation and Optimization. Altera Inc. - 2015. - Juny.

59. Quartus II Handbook Volume 3: Verification. Altera Inc. - 2015. - May.

60. Reed, I. S. Polynomial Codes over Certain Finite Fields / I. S. Reed, G. Solomon // SI AM Journal of Applied Mathematics. - 1960. - vol. 8. - pp. 300-304.

61. Reyhani-Masoleh, A. Low Complexity Bit Parallel Architectures for Polynomial Basis Multiplication over GF(2m) / Arash Reyhani-Masoleh, M. Anwar Hasan // IEEE transactions on computers. - 2004. - August. - vol. 53. - no. 8. - pp. 945-959.

62. Richardson, T. J. Design of Capacity-Approching Irregular Low-Density Parity-Check Codes / T. J. Richardson, M. A. Shokrollahi, R. L. Urbanke // IEEE Trans. Inform. Theory. 2001. - February. - vol. 47. - no. 2. - pp. 619-637.

63. Sarwate, D.V. High-Speed Architectures for Reed-Solomon Decoders / D.V. Sarwate, N.R. Shanbhag // IEEE transactions on VLSI Systems. - 2001.

64. Sauve, P.-P. International Symposium on Turbo Codes, Brest, France / P.-P. Sauve, A. Hunt, S. Crozier, P. Guinand. - 2000. - September. - pp. 121-124.

65. Schmalen, L. Next generation error correcting codes for lightwave systems / L. Schmalen, V. Aref, J. Cho, K. Mahdaviani // ECOC Th.1.3.3. - 2014.

66. Seth, K. Ultra folded high-speed architectures for Reed-Solomon decoders / K. Seth, K. N. Viswajith, S. Srinivasan, V. Kamakoti // in Proc. Int. Conf. VLSI Design. -2006. - January. - pp. 517-520.

67. Shah, S. S. Self-correcting codes conquer noise Part 2: Reed-Solomon codecs / S. S. Shah, S. Yaqub, F. Suleman // Chameleon Logics. - 2001. - Part 1: Viterbi Codecs.

68. Shannon, C. E. A Mathematical Theory Of Communication // Bell System Technology Journal. - 1948. - vol. 27. - pp. 379-423, 623-656.

69. Shao, H. M. A VLSI Design of a Pipeline Reed-Solomon Decoder / H.M. Shao, T.K. Truong, L.J. Deutsch, J. Yuen, I.S. Reed // IEEE Trans. Comput. - 1985. - May. -vol. C-34. - no. 5. - pp. 393-403.

70. Song, L. 10- and 40-Gb/s forward error correction devices for optical communications / L. Song, M. Yu, M. S. Shaffer // IEEE Journal of Solid-State Circuits.

- 2002. - November. - vol. 37. - no. 11.

71. Stratix II Device Handbook / Altera Inc. - 2005. - July. - vol. 1.

72. Sugiyama, Y. A Method for Solving Key Equation for Goppa Codes / Y. Sugiyama, Y. Kasahara, S. Hirasawa, T. Namekawa // Information and Control. - 1975.

- vol. 27. - pp. 87-99.

73. Sylvester, J. Reed Solomon Codes / Elektrobit. - 2001. - January.

74. Truon, T.K. The VLSI Design of a Reed-SoIomon Encoder Using Berlekamp's Bit-Senal Multiplier Algorithm / T.K. Truong, L.J. Deutsch, I.S. Reed, I.S. Hsu, K. Wang, C.S. Yeh // Third Caltech Conf. on VLSI. 1983. - pp. 303-329.

75. VLSI lecture notes, ETF, University of Belgrade.

76. Wai, K. C. C. Field Programmable Gate Array Implementation of Reed-Solomon Code RS (255, 239) / K. C. C. Wai, S. J. Yang // New York. - 2006.

77. Wicker, S. B. Error Control Systems for Digital Communication and Storage / Englewood Cliffs, N.J.: Prentice-Hall. - 1994.

78. Wicker, S. B. Reed-Solomon Codes And Their Applications / S. B. Wicker, V. K. Bhargava // New York, IEEE Press. - 1994.

79. Wilhelm, W. A new scalable VLSI architecture for Reed-Solomon decoders / IEEE J. Solid-State Circuits. - 1999. - March. - vol. 34. - pp. 388-396.

80. Woodard, J. P. Comparative Study of Turbo Decoding Techniques: An Overview / J. P. Woodard, L. Hanzo // IEEE transactions on venicular technology. - 2000. -November. - vol. 49. - no. 6. - pp. 2208-2233.

81. Yeo, E. High Throughput Low-Density Parity-Check Decoders Architectures / E. Yeo, P. Pakzad, B. Nicolic, V. Anantharam // in Proc. IEEE Global Telecommunications Conference, 2001. - 2001. - November. - vol. 5. - pp. 30193024.

82. Yeon, J. Low-Complexity Triple-Error-Correcting Parallel BCH Decoder / J. Yeon, S.-J. Yang, C. Kim, H. Lee // Journal of Semiconductor and Science Technology, - 2013. - October, - vol.13. - no. 5. - pp.465-472.

83. Zhang, J. Optimized design for high-speed parallel BCH encoder / J. Zhang, Z. Wang, Q. Hu, J. Xiao // in Proc. 2005 IEEE Int. Workshop on VLSI Design and Video Technology. - 2005. - May. - pp. 97-100.

84. Zubairi J. A. FPGA: The chip that flip-flops, lecture notes. - 2004. - October.

85. Берлекэмп, Э.Р. Алгебраическая теория кодирования / Э.Р. Берлекэмп; пер.с англ. / под ред. С.Д. Бермана. - М.: Мир, 1971. - 384 с.

86. Берлекэмп, Э.Р. Техника кодирования с исправлением ошибок / Э.Р. Берлекэмп // ТИИЭР. - 1980. - Т. 68, №5, - С. 24-58.

87. Блейхут, Р. Теория и практика кодов, контролирующих ошибки : пер. с англ. / Под ред. Д.К. Зигангирова / Р. Блейхут. - М. : Мир 1986. - 576 с.

88. Блох, Э. Л. Обобщенные каскадные коды / Э.Л. Блох, В.В. Зяблов. - М. : Связь, 1976. - 356 с. : ил.

89. Бородин, Л. Ф. Введение в теорию помехоустойчивого кодирования / Л. Ф. Бородин. - М. : Советское радио, 1968. - 408 с.

90. Бураченко, Д.Л. Геометрические модели сигнально-кодовых конструкций / Д.Л. Бураченко, Н.В. Савищенко. - СПб. : ВАС, 2012. - 388 с.

91. Варакин, Л.Е. Системы связи с шумоподобными сигналами / Л.Е. Варакин. - М.: Радио и связь, 1985. - 384 с.

92. Васильев, К. К. Математическое моделирование систем связи / К. К. Васильев, М. Н. Служивый. - Ульяновск : УлГТУ, 2010. - 128 с.

93. Васильев, К.К. Теория электрической связи / К. К. Васильев, В.А. Глушков, А.В. Дормидонтов, А.Г. Нестеренко. - Ульяновск : УлГТУ, 2008. - 452 с.

94. Вернер, М. Основы кодирования / М. Вернер. - М.: Техносфера, 2004. -288 с.

95. Витерби, А.Д. Принципы цифровой связи и кодирования. Выпуск 18. : пер. с английского под ред. К.Ш. Зигангирова / А.Д. Витерби, Дж. К. Омура. - М.: Радио и связь, 1982. - 536 с.

96. Галлагер, Р. Коды с малой плотностью проверок на четность : пер. с англ. под ред. Р.Л. Добрушшина / Р. Галлагер. - М. : Мир, 1966. - 144 с.

97. Галлагер, Р. Теория информации и надежная связь : пер. с англ, под ред. М. С. Пинскера и Б. С. Цыбакова / Р. Галлагер. - М. : Сов. радио, 1974. - 568 с.

98. Гладких, А. А. Методы эффективного декодирования избыточных кодов и их современные приложения / А.А. Гладких, Р.В. Климов, Н.Ю. Чилихин. -Ульяновск : УлГТУ, 2016. - 258 с.

99. Гладких, А. А. Приемник комбинаций каскадного кода / А. А. Гладких, Г.

А. Гриневич, Н. А. Неудачин, П. Д. Расторгуев // Авторское свидетельство на изобретение № 684762. Бюллетень изобретений, 1979. - № 19.

100. Гладких, А. А. Эффективное декодирование недвоичных кодов с провокацией стертого элемента / Баскакова Е.С., Маслов А.А., Тамразян Г.М // Автоматизация процессов управления. № 2(32) 2013.-С. 87-93.

101. Гладких, А.А. Основы теории мягкого декодирования избыточных кодов в стирающем канале связи. А.А. Гладких - Ульяновск: УлГТУ, 2010. - 379 с.

102. Гладких, А.А. Применение метода гиперкодирования в системах передачи данных / А.А. Гладких // Автоматизация процессов управления. № 2 (24) 2011, -С. 77-81.

103. Золотарев, В. В. Помехоустойчивое кодирование. Методы и алгоритмы. Справочник : под ред. чл.-кор. РАН Зубарева Ю. Б. / В. В. Золотарев, Г. В. Овечкин. - М. : Горячая линия-Телеком, 2004. - 126 с.

104. Золотарев, В.В. Многопороговые декодеры и оптимизационная система кодирования / В.В. Золотарев, Ю.Б. Зубарев, Г.В. Овечкин; под ред. Академика РАН В.К. Левина. - М.: Горячая линия - Телеком. - 2012. - 239 с., ил.

105. Зяблов, В.В. Анализ корректирующих свойств итерированных и каскадных кодов / В.В. Зяблов // Передача цифровой информации по каналам с памятью. -М. : Наука, 1970. - С. 76-85.

106. Касперски, К. Могущество кодов Рида-Соломона или информация, воскресшая из пепла / К. Касперски // Системный администратор. - 2004. - С. 8894.

107. Кларк, Дж. Кодирование с исправлением ошибок в системах цифровой связи / Дж. мл. Кларк, Дж. Кейн; пер.с англ. - М.: Радио и связь, 1987.- 392 с.

108. Мак-Вильямс, Ф. Дж. Теория кодов, исправляющих ошибки / Ф. Дж. Мак-Вильямс, Н. Дж. А. Слоэн. - М. : Связь, 1979. - 354 с.

109. Месси, Дж. Пороговое декодирование / Дж. Месси. - М. : Мир, 1966.- 284 с.

110. Морелос-Сарагоса, Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / Р. Морелос-Сарагоса.- М. : Техносфера, 2005.-320 с.

111. Овечкин, Г.В. Эффективность применения многопорогового декодера в каскадных схемах / Г.В. Овечкин, П.В. Овечкин // Новые информационные технологии в научных исследованиях и в образовании. Материалы 8-й Всероссийской научно-техн. конф. - Рязань: РГРТА. - 2003. -С.131-132.

112. Питерсон, У. Коды, исправляющие ошибки / У. Питерсон, Э. Уэлдон.: пер. с англ.; под ред. Р. Л. Добрушина и С. Н. Самойленко. - М. : Мир, 1976. - 594 с.

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

114. Савищенко, Н.В. Специальные интегральные функции, применяемые в теории связи / Н.В. Савищенко. - СПб. : ВАС, 2012. - 560 с.

115. Скляр, Бернард. Цифровая связь. Теоретические основы и практическое применение : изд. 2-е, испр. пер. с англ / Бернард Скляр. - М. : Издательский дом «Вильямс», 2003. - 1104 с.

116. Тайлеб, Н. Проектирование кодеров и декодеров кода Рида-Соломона на ПЛИС типа БРОЛ / Тайлеб Н., Поляков А.К. // Сборник трудов научного семинара, посвященного памяти д.т.н., профессора З.М. БЕНЕСОНА.- М.: ВЦ РАН, 2008. - С. 26-29.

117. Тайлеб-Мазуз, Н. Параметризованный проект высокоскоростного многоканального декодера кода Рида-Соломона / Н. Тайлеб-Мазуз // Вестник МЭИ. - М.: Издательский дом МЭИ, 2011. № 5. - С. 112-118.

118. Тамразян Г.М. Аппаратная реализация оптимального декодера низкоплотностных кодов / Г.М. Тамразян, А.А. Гладких, Д.В. Ганин // Автоматизация процессов управления. - 2015. - №3 (41). - С.106-113.

119. Тамразян, Г.М. Алгоритм декодирования избыточных кодов с динамически перестраиваемыми параметрами / Г.М. Тамразян // Радиотехника. - 2014. - №11. -С.94-98.

120. Тамразян, Г.М. Современные методы адаптивного помехоустойчивого кодирования / Г.М. Тамразян // Автоматизация процессов управления. - 2016. -№2(44). - С.45-49.

121. Трифонов, П.В. Интерполяция в списочном декодировании кодов Рида-Соломона / П.В. Трифонов // Проблемы передачи информации. 2007. - Т.43. -Вып.3. - С.66-74.

122. Фано, Р. Передача информации, Статистическая теория связи. / Р.Фано. -М. : - Мир, 1965. - 438 с.

123. Финк, Л. М. Теория передачи дискретных сообщений / Л. М. Финк. - М. : Сов. радио, 1970. - 728 с.

124. Форни, Д. Каскадные коды / Д. Форни. - М. : Мир, 1970. - 207 с.

125. Форни, Д. Экспоненциальные границы для ошибок в системах со стиранием, декодированием списком и решающей обратной связью / Д. Форни // Некоторые вопросы теории кодирования. - М. : 1970, - С.166 - 205.

126. Хлынов, А.А. Исследование принципов реализации ЬЭРС кодека на ПЛИС. / А.А. Хлынов // Материалы Международной научно-технической конференции «ШТБКМЛТ1С - 2012». - 2012. - Москва. - ч. 6. - С.150-156.

127. Шувалов, В.П. Прием сигналов с оценкой их качества / В.П. Шувалов. - М. : Связь, 1979. - 240 с.

ПРИЛОЖЕНИЕ А Исходные коды моделей, использованных в работе

В данном приложении приведены исходные коды программ, описывающих работу использованных в работе моделей при аппаратной реализации кодека РС. Представленные модели разработаны в среде MATLAB. Полные тексты программ содержатся на прилагаемом CD-диске в папке \\Source\MODELS.

ПРИЛОЖЕНИЕ Б

Исходные коды программ, использованные при аппаратной реализации

кодека РС

В данном приложении приведены исходные коды программ, используемых при аппаратной реализации кодека РС. Представленные программы разработаны в среде Quartus II и написаны на языке описания аппаратных схем System Verilog. Полные тексты программ содержатся на прилагаемом CD-диске в папке \\Source\CODEC.

ПРИЛОЖЕНИЕ В

Описание изобретения «Мягкий декодер последовательного турбокода»

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

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

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

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

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

На фигуре 1 приведена схема предложенного мягкого декодера последовательного турбокода, содержащая блок приема 1, блок индексов 2, блок статистических решений 3, блок итераций 4, блока внутреннего кода 5, блок приоритетов 6, блок стираний 7, блок локаторов стираний 8, блок производной 9, буфер внешнего кода 10, блок синдромов 11, блок произведений 12, блок исправления стираний 13 и выходной блок 14. Выход блока приема 1 через блок индексов 2 подключен к блоку статистических решений 3, первый выход которого подключен к одному входу блока итераций 4, а второй выход блока статистических решений 3 подключен ко второму входу блока приоритетов 6, при этом выход блока итераций 4 подключен к входу блока внутреннего кода 5, первый выход которого подключен к буферу внешнего кода 10, а второй и третий выходы блока внутреннего кода 5 соответственно подключены к другому входу блока итераций 4 и к первому входу блока приоритетов 6, а выход этого блока 6 подключен к входу блока стираний 7, один выход которого подключен ко второму входу блока синдромов 11, другой выход блока стираний 7 подключен к блоку локаторов стираний 8, а третий выход блока стираний 7 подключен к третьему входу выходного блока 14, при этом первый вход блока синдромов 11 подключен к одному выходу буфера внешнего кода 10, другой выход которого подключен к первому входу выходного блока 14, при этом выход блока синдромов 11 подключен к первому входу блока произведений 12, а его второй вход подключен ко второму выходу блока локаторов стираний 8, первый выход которого через блок производной 9 подключен ко второму входу блока исправления стираний 13, тогда как его первый вход подключен к выходу блока

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

Фигура 1 - Схема мягкого декодера последовательного турбокода

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

"5

РС (7, 3, 5), построенного над полем ОБ(2 ).

Пусть порождающий полином кода РС g(x) определен как

х) = (х -а)(х -а2 )(х -а3 )(х -а4 ).

Используя таблицу сложения элементов в поле ), получают значение

g(x) в явном виде: g(x) = х4 + х3а3 + х2а0 + ха + а3. Пусть с выхода источника

2 6 4

информации на вход кодера поступили символы вида Vinf = a а а . Для кодирования вектора Vinf кодом РС повышают его степень на величину xn-k,

получая Vinf(x) = x4а2 + x5а6 + x6а4. Обычно эта процедура выполняется на

передаче с использованием сдвигового регистра с обратным связями, соответствующими значению g(x), при этом на выходе кодера внешнего кода образуется вектор с q-ми символами Vkc вида:

Vkc(x)q = а2 + xa4 + x 2а5 + x3a5 + x 4а2 + x5a6 + x 6а4

Или в двоичном представлении: Vc(x)2 = (100) + x(110) + x2 (111) + x3 (111) + x4 (100) + x5 (101) + x 6 (110)

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

Vk = (1001)(1100)(1111)(1111)(1001)(1010)(1100) при этом передатчик логические единицы передает с энергией Е, а логические нули с энергией -Е.

После прохождения канала связи блок приема 1 мягкого декодера последовательного турбокода принимает двоичные символы, которые в зависимости от уровня помех в канале связи оказываются в большей или меньшей степени искаженными. Работа блока приема 1 организуется по принципу стирающего канала связи с симметричным интервалом стирания р, где 0 < р < 1 и представляет долю расстояния в системе условных плотностей вероятностей в гауссовском канале связи между математическими ожиданиями - 4E и JE, соответствующих приему информационных нулей и единиц. В целях повышения достоверности МРС параметр р выбирают достаточно большим, например, р = 0,9. Зафиксированный в блоке приема 1 сигнал |z| и соответствующее ему жесткое решение 0 или 1 передаются в блок индексов 2.

Блок индексов 2 предназначен для формирования целочисленных МРС. Если 0,9 < 2 < 3<г (здесь а - среднее квадратическое отклонение), то к жесткому решению добавляется МРС максимального значения, принятого в данном приемнике, например, Лтах = 7. Для всех других значений 0 < 2 < 0,9 целочисленные показатели МРС получают по правилу:

Л =

Л

лтах х г

р4Е

где, символ [•] означает округление значения Л1 до целочисленной величины в сторону уменьшения (расчет на наихудший случай). При известных р, Лтах и Е значения Л (2) представляют легко вычисляемую линейную зависимость. На выходе блока индексов жесткие решения заменяются на значения «минус» для нулей и значения «плюс» для единиц. Таким образом, на выходе этого блока может появиться кортеж данных вида ... -5; + 6; -7; -7;... Эти данные поступают на вход блока статистических решений 3.

Блок статистических решений 3 осуществляет оценку параметров q -х комбинаций внутреннего кода, используя данные из блока индексов 2. Пусть выбраны Лтх = 7, Е = 2 и р = 0,9. Тогда 2 ^ ||_5,5 х 2J. Для получения статистической оценки на длине кодового вектора внутреннего кода определяется среднее значение кортежа МРС М(л ) и оценивается разброс показателей МРС в виде

<г(Л) = (Уп -М(л) - |Л |)2 , где п - длина кодового вектора внутреннего кода.

М (л)-1Л|.х2

I=1

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

Блок итераций 4, получив кодовый вектор внутреннего кода, направляет его на вход блока внутреннего кода 5, где осуществляется декодирование вектора по заданным для этого кода проверочным соотношениям. Если проверочные

соотношения выполняются, то вырабатывается сигнал (+ pc), который через третий выход этого блока поступает на первый вход блока приоритетов 6. Если проверочные соотношения не выполняются, то вырабатывается сигнал (-pc) и осуществляется попытка восстановления кодового вектора за счет итеративных преобразований. Для этого данные о векторе через второй выход блока внутреннего кода 5 направляются на другой вход блока итераций 4. Блок итераций 4 обрабатывает подобные данные по правилу:

L(Лш ) + L(Лр ) * (-1)1-m х sign[L(Лш )]х sign[b(Лр )]х min(L(Л )\\ЦЛр ))

здесь функция sign(•) возвращает знак своего аргумента; L(Лы) - МРС, участвующего в формировании проверочного бита; L(Лр) - мягкое решение

проверочного символа; m - число исключенных из анализа положительных МРС, входящих в корректируемый вектор. После выполнения итеративных преобразований кодовый вектор возвращается в блок внутреннего кода 5. Блок приоритетов 6 работает согласно целевой функции, имеющей вид:

Q{W;M(Л); <г(Л)} ^ sign(w); \M(Л)\; <г(Л),

W pc) max min где W - знак выполнения проверочных соотношений.

В соответствие с Q{^} блок приоритетов 6 на первом шаге обработки комбинации выполняет оценку проверочных соотношений (выполнение четности в четности в рассматриваемом примере), на втором шаге обработки данных оценивает среднее значение принятых МРС и в последнюю очередь определяет степень разброса зафиксированных приемником решений. Максимальное значение |м(Л) соответствует высокой достоверности принятых символов, но

может быть получено множество одинаковых значений МЛ) при различной совокупности оценок, поэтому необходимо дополнительно оценивать параметр <(л) . Если возникает ситуация неопределенности, когда |mi (л) = мj (л) при i ^ j, то приоритетной для последующей обработки данных является комбинация, у которой CJi (л) < <j (л) .

Пример расчета приоритета для первого символа кодовой комбинации кода РС приведен в таблице.

Символы Ул с проверкой четности Представление символов с влиянием помех 2 Я II Ж М (Я) О(Я) Приоритет

а2 ^ 1001 +1,41-0,20 -1,41+0,80 -1,41-0,54 +1,41+0,42 +1,21 -0,61 -1,95 +1,83 6,7=6 3,3=3 2,0=7 1,8=7 + 5,75 3,58 Высокий

Выполнение расчета функции Q{•} для второго символа а4 кода РС

Символы Ул с проверкой четности Представление символов с влиянием помех 2 Я II Ж М (Я) ад Приоритет

а4 ^ 1100 +1,41-0,48 +1,41+0,16 -1,41+1,75 -1,41-0,49 +0,93 +1,57 +0,34 -1,90 5,1=5 1,6=7 1,9=2 1,9=7 - 5,50 3,66 Низкий

Комбинация внутреннего кода в виде последовательности + 5 + 7 + 2 - 7 направляется в блок итераций 4, где выполняются следующие действия: из комбинации удаляется символ + 7, который считается принятым надежно. В этом случае значение т = 1. Оставшиеся символы + 5 + 3 - 7 преобразуются по шагам итераций:

Шаг 1. [+2 +0] + (-7) = -2, поскольку 2<7;

[+5 +0] + (-7) = -5, поскольку 5<7.

Шаг 2. [+2 -5] + (-7) = +3, поскольку 3<7;

[+5 -2] + (-7) = -3, поскольку 3<7.

Шаг 3. [+2 -3] + (-7) = +1, поскольку 1<7;

[+5 +3] + (-7) = -7, поскольку 8>7.

После шага 3 итеративных преобразований возможна коррекция символов исходной последовательности: (+5 +1=+6); (+3-7=-4); -7. После восстановления вычеркнутого символа будет получено +6 +7 -4-7. Следовательно первоначально принятый символ кода РС а5 преобразуется в символ а4. Полученное значение второго символа используется как индикатор правильности восстановления кодового вектора кода РС. Для выполнения последующей

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

Расчет значений Q{•} других значений кодового вектора кода РС

Символы Vtk с проверкой четности Представление символов с влиянием помех z Я N 5 W M (Я) ад Приоритет

а5 ^ 1111 +1,41-2,92 +1,41+1,72 +1,41-0,90 +1,41-0,24 -1,51 +3,31 +0,51 +1,17 1,5=7 3,3=7 2,8=2 6,4=6 - 5,50 5,67 Низкий

а5 ^ 1111 +1,41+0,34 +1,41-0,88 +1,41-1,07 +1,41+0,47 +1,75 +0,53 +0,34 +1,88 1,7=7 2,9=2 1,9=1 1,9=7 + 4,25 10,25 Сомнительный

а2 ^1001 +1,41+1,46 -1,41-0,67 -1,41+0,61 +1,41+1,15 +2,87 -2,08 -0,80 +2,56 2,9=7 2,1=7 2,0=4 2,6=7 + 6,25 2,25 Высокий

а6 ^ 1010 +1,41-0,19 -1,41-0,90 +1,41-0,70 -1,41-0,36 +1,22 -2,31 +0,71 -1,77 6,7=6 2,3=7 3,9=3 1,8=7 + 5,75 3,58 Высокий

а4 ^ 1100 +1,41+0,05 +1,41+0,56 -1,41+1,28 -1,41-1,18 +1,46 +1,97 -0,13 -2,59 1,4=7 2,0=7 0,7=0 2,6=7 + 3,58 12,25 Сомнительный

Данные из блока внутреннего кода 5 в виде символов кода РС накапливаются в буфере внешнего кода 10, а из блока приоритетов 6 поступают в блок стираний 7.

Блок стираний 7 формирует данные, выделяя в отдельные группы символы кода РС с «высоким» и «низким» приоритетом. Символы с «сомнительным» приоритетом могут дополнять группу символов с «низким» приоритетом в зависимости от исправляющей способности кода. Определив число S ненадежных символов кода РС, блок 7 стирает их при условии, что S = йт1п -1.

При йтп = 5 декодер кода РС способен восстановить четыре стирания. Кодовый

вектор кода РС принимает вид а2 S1S2 S3a2a6 S4 и это значение передается в блок синдромов 11.

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

Расстановка символов кодового кода РС вектора по позициям

Номер позиции 0 1 2 3 4 5 6

Символы и стирания кодового вектора а2 £1 £ 2 £ 3 а2 а6 £ 4

На основании этих данных в блоке 11 рассчитываются синдромы для позиций 1; 2; 3; 6. Следует иметь в виду, что независимо от номера стертой позиции значения синдромов стертых позиций (при наличии четырех стираний) вычисляются всегда для у = 0; у = 1; у = 2; у = 3.

Множитель 0 +1 = 1 £у=0 = а2а0 + а2а4 + а6а5 = а2 + а6 + а4 = а5 ;

20 28 6 10 2 3 2 3 Множитель 1 +1 = 2 = = аа +аа +аа =а +а +а = а ;

2 0 2 12 6 15 2 0 0 2 Множитель 2 +1 = 3 =2 = аа +аа +аа =а +а +а = а ;

2 0 2 16 6 20 2 4 5 6 Множитель 3+1=4 £у=3 =а а+аа +аа =а+а+а=а.

Итогом работы блока 11 является полином синдромов

8(х) = а5 + ха3 + х 2а2 + х3а6

Одновременно с этим по известным стертым позициям, полученных из блока стираний 7, в блоке локаторов стираний 8 определяется полином локаторов стираний

Ь( х) = (1 + ха)(1 + ха2 )(1 + ха3 )(1 + хав) = (1 + ха2 + ха + х 2а3 )(1 + хав + ха3 + х 2а9) = = (1 + хаА + х 2а3)(1 + хаА + х 2а2) = 1 + х 2(а2 + а + а3) + х3(аб +а°) + х 4а5 =

= 1 + х 2аб + х ъа2 + х 4а5.

Или в окончательном виде Ь(х) = 1 + х2а6 + х3а2 + х4а5. Данные из блока синдромов 11 и блока локаторов стираний 8 объединяются в блоке произведений 12. При выполнении этой процедуры все значения х со степенями равными и старше величины п - к в расчет не принимаются. Таким образом в блоке 12 образуется последовательность вида:

Б(х) х Ь(х) = (а + хаъ + х 2а2 + х За6 )(\ + х 2а6 + х За2 + х 4а5) = = а5 + ха3 + х 2а2 + х За6 + х 2а4 + х За2 + х За° = а5 + ха3 + х 2а1.

Одновременно с работой блока 12 для реализации алгоритма Форни (решение ключевого уравнения Форни) по данным из блока локаторов стираний 8

в блоке производной 9 определяется производная от значений Ь(х). Будет получен полином вида Ь'(х) = 0 + 2хаб + 3х 2а2 + 4х За5 = х 2а2.

Данные из блока произведений 12 и блока производной 9 объединяются в блоке исправления стираний 13, в котором выполняются действия для каждой стертой позиции с учетом их номера:

5 а3 а1

а +---1----5,2,6 4

У _ а а2 _ а +а +а _ а 4

2 0 1 а ' а а 1

а

5 а3 а1 а +—— +—— 5143 у а +а + а _ а__ 5

*2 = 2 = 5 = 5 = а •

а2 а5 а5

аг

5 а3 а1

а Н--;т Н--т- 5 0 2 3

у _ - а +а +а _ а _ „5

23 2 3 5 а •

а а а

а6

5 а3 а1 у _а + а6 + а12 _ а +а +а _ _ 4

16 = 2 = 4 =4 =а •

а2 а4 а4

а12

В выходном блоке 14 вторая позиция кода РС, полученная с использованием алгоритма Форни сравнивается с позицией, полученной за счет итеративных преобразований и сохранившей свое новое значение в буфере внешнего кода 10. Они совпадают: = а4, что указывает на правильность выполненных действий по восстановлению стираний.

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

Акты внедрения

УТВЕРЖДАЮ Генеральный директор ФНПЦ АО «НПО «Марс», к.т.н.

V^^VAÜV ВА- Маклаев О?. 2016 г

АКТ

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

Научно - техническая комиссия в составе:

Председателя:

первого заместителя генерального директора по науке, начальника КНИО-2, к.т.н. Э.Д. Павлыгина *

Членов комиссии:

заместителя начальника КНИО-1, заместителя генерального конструктора Ю.Л. Корноухова,

главного конструктора изделия «Трасса-22350» A.A. Маслова,

начальника НИО-14 A.B. Новоселова

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

- оптимальный алгоритм поиска полинома локаторов ошибки, применяемый при декодировании кодов Рида - Соломона;

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

- имитационная модель системы обмена данными в условиях применения адаптивных алгоритмов изменения избыточности в каскадных конструкциях кодеков на базе кодов Рида -Соломона;

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

- метод декодирования недвоичных кодов с использованием процедуры провокации стирания, позволяющий наиболее полно использовать введенную в код избыточность, на который предприятием ФНПЦ АО «НПО «Марс» получен патент РФ №2538331;

использованы при выполнении ОКР «Разработка алгоритмов и программ процесса передачи данных по радиоканалу с адаптацией системы помехоустойчивого кодирования, максимизирующего скорость передачи данных при заданной достоверности в условиях помех» - шифр «Каскад», проведенной ФНПЦ АО «НПО «Марс» совместно с Ульяновским государственным техническим университетом. Результаты работы реализованы и внедрены в изделии «Трасса-22350» в составе прибора радиолинии (ПРЛ), что позволило повысить скорость обмена информацией при заданных требованиях к достоверности принимаемых данных при взаимном обмене информацией (ВЗОИ) между автоматизированными комплексами обмена информацией надводных кораблей.

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

Председатель комиссии:

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

Члены комиссии:

V

Э.Д. Павлыгин

Заместитель начальника КНИО-1 -заместитель генерального конструктора

Главный конструктор

Начальник НИО-14

Ю.Л. Корноухов

А.А. Маслов

А.В. Новоселов

ЛсчС^С^

УТВЕРЖДАЮ ^^^^^^^^^^^^^^проректор по научной работе

» сентября 2017 г

АКТ

о внедрении результатов диссертационной работы Тамразян Г.М.

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

Комиссия в составе: декана радиотехнического факультета доцента Кадеева Д.Н., зам. декана РТФ по учебной работе, доцента Новикова Г.А., зав. кафедрой «Телекоммуникации», профессора Васильева К.К. составила настоящий акт в том,/.что научные результаты, полученные Тамразян Г.М. в диссертационной работе, внедрены в учебный процесс по направлению подготовки студентов инфокоммуникационных технологий и систем связи на кафедре «Телекоммуникации» Федерального государственного бюджетного образовательного учреждение высшего профессионального образования «Ульяновский государственный технический университет» в следующем виде:

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

2. На основе результатов диссертационной работы разработаны методические рекомендации по выполнению вариантов курсового проекта по учебной дисциплине «Общая теория связи 2» для студентов, обучающихся по направлению 11.03.02 «Инфокоммуникационные технологии и системы связи».

3. Вопросы мягкого декодирования помехоустойчивых кодов включены в программу практических занятий и лабораторных занятий по курсу «Общей теории связи 2» и «Теории кодирования и защиты информации». Подготовлены и внедрены методические указания в электронной форме по выполнению домашнего контрольного задания и задания по выполнению самостоятельной работы. Эффективность от внедрения состоит в совершенствовании учебного процесса и его учебно-методи^ского обеспечения.

Декан РТФ, к.т.н. доцент

Заместитель декана РТФ по учебной работе, к.ф.-м.н. доцент

Заведующий кафедрой «Телеклммуникации», д.т.н. профессор

«_» сентября 2017 г.

Д.Н. Кадеев

Г.А. Новиков

К.К. Васильев