Алгоритмы повышения эффективности многопороговых декодеров самоортогональных кодов для радиоканалов с высоким уровнем шума тема диссертации и автореферата по ВАК РФ 05.12.04, кандидат наук Као Ван Тоан

• Као Ван Тоан
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Као Ван Тоан

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

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

1.1 Основные принципы работы системы передачи данных

1.2 Помехоустойчивые коды

1.3 Сверточные коды и алгоритмы их декодирования

1.3.1 Декодер Витерби

1.3.2 Последовательные алгоритмы декодирования

1.3.3 Пороговый декодер

1.4 Блоковые коды и алгоритмы их декодирования

1.4.1 Декодирование кодов Хэммига

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

1.4.3 Пороговое декодирование

1.5 Современные методы коррекции ошибок

1.5.1 Турбо коды и их методы их декодирования

1.5.2 Низкоплотностные коды и методы их декодирования

1.5.3 Многопороговое декодирование самоортогональных кодов

1.6 Выводы

2 ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ МНОГОПОРОГОВЫХ АЛГОРИТМОВ ДЕКОДИРОВАНИЯ

2.1 Многопороговое декодирование

2.2 Оценка размножения ошибок

2.3 Оценка погрешности моделирования

2.4 Характеристики МПД в двоичном симметричном канале

2.4.1 Характеристики МПД при разной длине кода

2.4.2 Характеристики МПД при разном кодовом расстоянии

2.4.3 Характеристики МПД при разной кодовой скорости

2.5 Характеристики МПД в канале с аддитивным белым гауссовским шумом

2.6 Характеристики МПД в каналах с замираниями

2.7 Выводы

3 МНОГОУРОВНЕВЫЙ МНОГОПОРОГОВЫЙ ДЕКОДЕР САМООРТОГОНАЛЬНЫХ КОДОВ

3.1 Схема параллельного соединения МПД

3.1.1 Идея построения схемы

3.1.2 Алгоритм работы схемы параллельного соединения МПД

3.1.3 Исследование эффективности схемы параллельного соединения МПД

3.2 Схема последовательно-параллельного соединения МПД

3.2.1 Идея построения схемы

3.2.2 Алгоритм работы схемы последовательно-параллельного соединения МПД

3.2.3 Исследование эффективности схемы последовательно-параллельного соединения МПД

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

3.3.1 Определение информационных битов для внешнего декодера по символу с максимальной надежностью

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

3.4 Устройство многоуровневого многопорогового декодера линейных кодов

3.5 Выводы

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

4.1 Обоснование комбинированного декодера самоортогональных кодов

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

4.3 Эффективность комбинированного декодера в гауссовском канале и

настройка его параметров

4.4 Эффективность комбинированного декодера в каналах с замираниями

4.5 Выводы

ЗАКЛЮЧЕНИЕ

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

СПИСОК ИСПОЛЬЗУЕМЫХ СОКРАЩЕНИЙ

ПРИЛОЖЕНИЯ

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

работе

ПРИЛОЖЕНИЕ 2: Акт внедрения результатов диссертации

Введение диссертации (часть автореферата) на тему «Алгоритмы повышения эффективности многопороговых декодеров самоортогональных кодов для радиоканалов с высоким уровнем шума»

ВВЕДЕНИЕ

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

Степень разработанности темы: Основы помехоустойчивого кодирования информации были заложены в 1948 г. в работе К.Е. Шеннона [1]. В ней К. Шеннон показал, что если скорость передачи информации меньше некоторой величины, называемой пропускной способностью канала связи, то можно подобрать такой помехоустойчивый код и способ его декодирования, при котором может быть обеспечена сколь угодно малая вероятность ошибочного приема информации. Однако он не указал как построить такие помехоустойчивые коды, а лишь доказал их существование. После этой работы в теории помехоустойчивого кодирования начинается бурный этап развития. Много ученых и инженеров во всем мире занялось поиском помехоустойчивых кодов и способов их кодирования и декодирования. Например, в этой области известны работы русских ученых, таких как Б.А. Котельников [2], Л.Е. Назаров [3], В.Д. Колесник [4], Э.Л. Блох [5], С.И. Егоров [6], А.Г. Зюко [7], А.Н. Колмогоров [8], В.Л. Банкет [9], В.В. Зяблов [5,10], В.В. Золотарев [11] и др., а также многих выдающихся зарубежных специалистов: Дж. Месси [12], Дж. Возенкрафт [13], А. Витерби [14], Р. Галлагер [15], У. Питерсон [16], Т. Кассами [17], Р. Блейхут [18] и др.

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

ство кодов и алгоритмов их декодирования, например, блоковые коды Боуза-Чоудхури-Хоквигема [19], коды Рида-Соломона [16, 20], сверточные коды, коды с низкой плотностью проверок на четность (Low-Density Parity-Check, LDPC) [2123], каскадные коды и турбо коды [24-27]. Новое и очень эффективное решение проблемы высокой сложности декодирования при одновременной реализации высоких энергетических характеристик систем кодирования на базе многопороговых декодеров (МПД) самоортогональных кодов (СОК) [28-31] предлагается известными российскими специалистами В.В. Золотарёвым, Ю.Б. Зубаревым, Г.В. Овечкиным.

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

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

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

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

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

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

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

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

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

5. Разработать программные средства для исследования эффективности известных и предложенных алгоритмов декодирования самоортогональных кодов.

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

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

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

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

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

4. Синтезировано устройство многоуровневого многопорогового декодера, реализующее предложенные алгоритмы.

5. Обоснован новый комбинированных декодер самоортогональных кодов, в котором применяются алгоритмы декодирования низкоплотностных кодов и многопороговый декодер.

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

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

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

2. Обоснован комбинированный декодер самоортогональных кодов, позволяющий при двукратном росте сложности получить на 0,5... 1,3 дБ больший энергетический выигрыш кодирования в гауссовском канале по сравнению с многопороговым декодером.

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

Внедрение результатов диссертационной работы произведено в учебный процесс РГРТУ, о чем получен акт внедрения.

Достоверность:

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

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

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

1. XVIII всероссийская научно-техническая конференция студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях - НИТ - 2013», Рязань, РГРТУ, 2013 г.

2. XIX всероссийская научно-техническая конференция студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях - НИТ - 2014», Рязань, РГРТУ, 2014 г.

3. 17-я Международная конференция «Цифровая обработка сигналов и ее применение», г. Москва, 2015 г.

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

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

Публикации:

По материалам диссертационной работы опубликовано 8 научных работ. Из них 2 статьи в ведущих рецензируемых научных журналах из перечня ВАК РФ, 3 статьи в межвузовских сборниках, 3 тезисов докладов Международных и Всероссийских конференций.

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

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

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

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

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

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

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

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

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

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

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

ДЕКОДИРОВАНИЯ

1.1 Основные принципы работы системы передачи данных

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

Дискретный канал

Рисунок 1.1 Структурная схема модели системы связи

Рассмотрим основные принципы работы представленной схемы. Сначала источник сообщений порождает сообщения в виде последовательности некоторых элементов или элементарных сообщений из множества сообщений А = [а\, аг, ...

ЯлЛ. Каждое сообщение из множества Л может быть записано в виде последовательности элементов из конечных множеств элементов В = {Ь\, Ьг, ... ЬмУ-

я; = Ьц,Ь12,...,Ьц.

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

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

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

количественной оценки степени влияния шума n(t) на сигнал S(t) обычно используют символьное отношение сигнал-шум E/Nq, определяемое как отношение мощности сигнала к мощности шума. Рассмотрим наиболее часто встречающиеся математические модели дискретного канала.

Самой простой является модель двоичного симметричного канала (ДСК), представляющегося диаграммой, показанной на рисунке 1.2. Одним из способов его реализации является когерентная система с противоположными сигналами ±s(t) [33]. В этом случае вероятность ошибки, связанная с отношением сигнал-шум E/Nq, вычисляется по формуле:

где ()(х) - функция интеграла ошибок, определяемая по формуле:

= 2 Л. (1.2)

л/2 ж х

Другой способ реализации ДСК является двоичной некогерентной системой с ортогональными сигналами и ^(О» Для которой вероятность ошибки задается формулой:

(1.1)

(1.3)

1-Р

О

о

1-Р

Рисунок 1.2 Двоичный симметричный канал

Отметим, что вероятность ошибки (1.3) для некогерентной двоичной системы с ортогональными сигналами существенно выше вероятности (1.1) для когерентной системы с противоположными сигналами.

Более общая модель дискретного канала характеризуется множеством входных символов, множеством выходных символов и набором переходных вероятностей. В самом простом случае переходные вероятности постоянны во времени и переходы различных символов независимы. Частным случаем является д-ичный симметричный канал (дСК), получающийся при использовании модулятором q ортогональных сигналов и вынесении жесткого решения демодулятором. Вероятность ошибки данного канала вычисляется по формуле [28]:

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

вероятности ошибки от отношения сигнал-шум определяется в соответствии с выражением (1.1).

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

2 йу.

(1.4)

средним и дисперсией <т2 = 1/(2 Еу/Л^). Для данной модели канала зависимость

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

Вероятность ошибки, зависящая от отношения сигнал-шум в релеевском и райсовском канале, вычисляется соответственно по формулам (1.5) и (1.6) [35, 36]:

°° 77 77 1 I 77

Ре = т~ехр(—"7-*)[— - <2(, 2-*-)]Жг;

оАГ0

N.

1

Я" о (х +1)

-ехр

(К + 1) + -^-(х2+1) А^о

А^п

(^ + 1)

(1.5)

N0

■с1х,

(1.6)

1.2 Помехоустойчивые коды

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

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

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

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

Пусть двоичный линейный (л, к) код строится в линейном пространством Г с базисом из £ линейно независимых векторов:

Любое кодовое слово С е F может быть записано как линейная комбинация элементов этого базиса:

где щ е (0, 1}, 0 < г < к.

Из (1.7) и (1.8) кодовое слово С = (сь С2, ..., сп) может быть записано в матричной форме через порождающую матрицу в и вектор сообщении и = (щ, ш, ..., ик):

(1.7)

~хк-(хкЬ хк2, Хы)

С — и^Х] Ч" "" ^к^к '

(1.8)

с = и в

(1.9)

где

с =

г X ^ х9

Х2\' х22

х\п х2п

Хкп )

(1.10)

) Хк2

Обычно кодовые слова представляют в систематической форме. При этом каждая кодовая последовательность начинается с блока к информационных символов и заканчивается блоком из т = п-к проверочных символов С = {и,у\ Такой систематической код имеет проверочную матрицу, записанную в виде:

г\ 0 ••• 0 х,

0 = (1кР) =

41

112

О 1

о о

О X

21

X

22

Х\т х2

1 хк\ Хк2

т

Хкт У

(1.11)

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

¥ = и-Р => =игхи@и2-хъ®---®ик-хи. (1.12)

Это правило обычно используется в процессе декодирования кода следующим образом. Если при передаче по каналу ошибки отсутствуют, то равенство (1.12) должно выполняться. Таким образом, с каждой принятой кодовой последовательностью можно связать систему проверок по числу проверочных символов, которая для кодовой последовательности С, = (мь т, ..., иь уь..., v,,,) может быть описана следующей системой уравнений:

Щ ■ хи ® и2 ■ х21 © • • ■ © ик ■ Хкх © V! = 0 Щ ' х\2 ® и2 ' х22 ® ''' © ик ' хк2 ® у2 ~ 0

, (1.13)

м, • х1ш © и2 ■ х2т е-Фмг хкт © V,,, = 0

Список литературы диссертационного исследования кандидат наук Као Ван Тоан, 2015 год

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

1. Шеннон К.Е. Работы по теории информации и кибернетике // Пер. с англ. под ред. P.JI. Добрушина и О.Б. Лупанова. - М.; 1963. - 829 с.

2. Котельников В.А. Теория потенциальной помехоустойчивости. - M.-JL: Госэнергоиздат, 1956. - 152 с.

3. Назаров JI.E. Анализ и статистическая обработка ансамблей дискретных мультипликативных сигналов для помехоустойчивой передачи информации: дис. на соиск. учен. степ, д-ра физ.-мат. наук. - Москва: 2006.

4. Колесник В.Д., Мирончиков Е.Т. Декодирование циклических кодов. -М.: Связь, 1968.-251 с.

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

6. Егоров С.И. Методы, алгоритмы и устройства коррекции аддитивных и синхронизационных ошибок во внешних запоминающих устройствах ЭВМ: диссертация на соискание ученой степени д.т.н. - Курск: 2009.

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

8. Колмогоров А.Н. Теория информации и теория алгоритмов. - М.: Наука, 1987.-304 с.

9. Банкет В.Л., Дорофеев В.М. Цифровые методы в спутниковой связи. -М.: Радио и связь, 1988. - 240 с.

10. Зяблов В.В. и др. Высокоскоростная передача сообщений в реальных каналах //В.В. Зяблов, Д.Л. Коробков, С.Л. Портной. - М.: Радио и связь, 1991.-228 с.

11. Золотарев В.В. Использование помехоустойчивого кодирования в технике связи //Электросвязь, №7, 1990. С.7-10.

12. Месси Дж. Пороговое декодирование //Пер. с англ. Ю.Л. Сагаловича под ред. Э.Л. Блоха - М.: Мир, 1966. - 208 с.

13. Возенкрафт Дж., Джекобе И. Теоретические основы техники связи //Пер. с англ./Под ред. P.JI. Добрушина. - М.: Мир, 1969. - 640 с.

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

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

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

17. Кассами Т., Токуда И., Ивадари Е. и др. Теория кодирования //Пер. с яп. Под ред. Б.С. Цыбакова и С.Н. Гелфанда. - М.: Мир, 1978.

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

19. Боуз Р.К., Рой-Чоудхури Д.К. Об одном классе двоичных групповых кодов с исправления ошибок // Кибернетический сборник. 1961. - Вып. 2. -С. 83-94.

20. Рид И.С., Соломон Г. Полиномиальные коды над некоторыми конечными полями // Кибернетический сборник. 1983. - Вып. 7. - С. 74 - 79.

21. Gallager R.G. Low Density Parrity Check Codes. - Cambrige: M.I.T. Press, 1963.-p. 90.

22. Mackey D., Neal R. Near Shannon limit performance of low density parity check codes// IEEE Electronics Letters. Aug. 1996. vol. 32. no. 18. pp. 1645 -1646.

23. David J.C. MacKay. Information Theory, Inference, and Learning Algorithms. - Cambridge University Press, 2005. 641 p.

24. Berrou C., Glavieux A., Thitimajshima P. Near Shannon Limit Error Correcting Coding and Decoding: Turbo-Codes // Proceeding of ICC'93, Geneva, Switzerland, May 1993. P. 1064-1070.

25. Berrou С., Glavieux A. Near Optimum Error Correcting Coding and Decoding: Turbo-Codes // IEEE trans. On Comm., Vol. 44, № 10, October 1996. P. 1261-1271.

26. Robertson P., Hoeher P. Optimal end sup-optimal maximum a poteriori algorithms suitable for turbo decoding // European Trans, on Telecommun., vol. 8, №. 2, March-April 1997. P. 19-125.

27. Barbulescu S.A. Interative decoding of turbo codes and other concatenated codes. Ph. D. dissertation, Feb. 1996.

28. Золотарев В. В., Овечкин Г. В. Помехоустойчивое кодирование. Методы и алгоритмы. Справочник. М.: Горячая линия - Телеком, 2004. - 126с.

29. Золотарёв В.В. Теория и алгоритмы многопорогового декодирования // Под редакцией члена-корреспондента РАН Ю.Б. Зубарева. М.: «Радио связи», «Горячая линия - Телеком», 2006. - 276с.

30. Зубарев Ю.Б., Овечкин Г.В. Помехоустойчивое кодирование в цифровых системах передачи данных // Электросвязь. М., 2008. №12. С.2-11.

31. Золотарёв В.В., Зубарев Ю.Б., Овечкин Г.В. Многопороговые декодеры и оптимизационная теория кодирования. - М.: Горячая лииия - Телеком, 2012.-239 с.

32. Деев В.В. Методы модуляции и кодирования в современных системах связи. - СПб.: Наука. 2007. - 267 с.

33. Кларк Дж., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи// Пер. с англ. под ред. Б.С. Цыбакова. М.: Радио и связь, 1987.-391 с.

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

35. Bevan D.D.N., Ermolayev V.T., Flaksman A.G. Coherent multichannel reception of binary modulated signals with independent Rician fading // Proceedings of IEEE Sensor Array and Multichannel Signal Processing Workshop (SAM2000). 2000. Cambridge MA. P. 37-39.

36. Ермолаев В.Т., Флаксман А.Г. Теоретические основы обработки сигналов в системах мобильной радиосвязи. Нижний Новгород, 2010. - 107с.

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

38. Никитин Г.И. Сверточные коды: Учеб. способие/ СПбГУАП. СПб., 2001. -80 с.

39. Королев А.И. Коды и устройства помехоустойчивого кодирования информации. - Мн.: 2002. - 286 с.

40. Consultative committee for Deep Space Data Systems, Telemetry Channel Coding (101.0-B-5 Blue Book), CCSDS: Newport Beach, California. - 2001. - June.

41. European Telecommunications Standards Institute (ETSI), Universal Mobile Telecommunications System (UMTS): Multiplexing and Channel Coding (FDD). 3 GPP TS 125.212 Version 3.4.0 (23 September, 2000).

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

43. Фано Р. Эвристическое обсуждение вероятностного декодирования // Сб. Теория кодирования. М.: Мир, 1964. С. 166 - 198.

44. Хэмминг Р.В. Теория кодирования и теория информации// Пер. с англ. С.И. Гельфанда под ред. Б.С. Цыбакова. М.: Радио и связь, 1983. - 176 с.

45. Сагалович Ю. JI. Введение в алгебраические коды. Учебное пособие. — М.: МФТИ, 2007. — 262 с.

46. Press Release, AHA announces Turbo Product Code Forward Error Correction Technology. 1998.

47. Белоголовый A.B., Крук E.A. Многопороговое декодирование кодов с низкой плотностью проверок на четность// В сб. «Вопросы передачи и защиты информации». СПбГУАП. СПб., 2006. С.25 - 37.

48. Солтанов А.Г. Схемы декодирования и оценка эффективности LDPC-кодов. Применение, преимущества и перспективы развития // Безопасность информационных технологий. М.: 2010, №2, С. 61 - 68.

49. Ardakani М. Efficient Analysis, Design and Decoding of Low-Density Parity-Check Codes // Ph.D. dissertation, University of Toronto. - 2004.

50. Fossorier M.P.C., Mihaljevic M., Imai H. Reduced complexity iterative decoding of low-density parity check codes based on belief propagation// IEEE Transactions on Communications. 47(5). May 1999. P. 673 - 680.

51. Third Generation Partnership Project 2 (3GPP2), Physical Layer Standard for cdma2000 Spread Spectrum Systems, Release C. 3GPP2 C.S0002-C, Version 1.0.-2002.-May 28.

52. Brian Edmonston. Comparison of Turbo-Convolutional Codes and Turbo Product Codes for QPSK-64QAM Channels// IEEE iCODING Technology Incorporated. 18-01-2001.

53. Andersen J.D., "Selection of component codes for turbo coding based on convergence properties", "Annales des Telecommunications", Vol. 54, No 3-4, special issue on turbo codes, march - april 1999.

54. Woodard J.P., Hanzo L. Comparative study of turbo decoding techniques: an overview// IEEE Trans. Veh. Technol. - 2000. - Nov. - Vol. 49. - P.2208-2233.

55. Золотарев В.В. Устройство для декодирования линейных сверточных кодов. Авторское свидетельство на изобратение СССР №92878, Бюллетень изобретений №43, 1975.

56. Золотарев В.В., Овечкин Г.В. Сложность реализации эффективных методов декодирования помехоустойчивых кодов // 6-я межд. конф. и выст. «Цифровая обработка сигналов и ее применение». М.: 2004. Том 1. С. 220-221.

57. Зубарев Ю.Б., Золотарев В.В., Овечкин Г.В. Обзор методов помехоустойчивого кодирования с использованием многопороговых алгоритмов// Цифровая обработка сигналов, 2008, №1, С. 2 - 11.

58. Робинсон Дж. П. Размножение ошибок и прямое декодирование свер-точных кодов // В сб.: Некоторые вопросы теории кодирования. - М.: Мир, 1970.

59. Massey J. L. Catastrophic error propagation in convolution codes // Proc. 11th Midwest Circuit Theory Symp. University Notre Dame. Ind., May, 1968.

60. Massey J. L., Bin R. W. Application of Luapunov's Direct Method to the Error-Propagation Effect in Convolutional Codes // IEEE Trans, on Infrom. Theory, 1964, vol. IT-10, № 4. - P. 248-250.

61. Золотарев B.B. Алгоритмы многопорогового декодирования линейных кодов // Мобильные системы. - М., 2005, № 12. С. 56 - 62.

62. Золотарев В.В. Эффективные многопороговые алгоритмы декодирования // Научный совет по комплексной проблеме «Кибернетика» АН СССР. Препринт. - М., 1981. - 76 с.

63. Као В.Т. Эффективность многопороговых декодеров при разном кодовом расстоянии и длине кода // Новые информационные технологии в научных исследованиях. Материалы 18-й Всероссийской научно-техн. конф. - Рязань: РГРТУ, 2013. С. 82 - 83.

64. Золотарев В. В., Овечкин Г. В. Повышение надежности передачи и хранения данных с использованием многопороговых методов декодирования помехоустойчивых кодов // Цифровая обработка сигналов. 2012. №1. С. 16-21.

65. Золотарев В. В., Овечкин Г. В. Эффективное многопороговое декодирование недвоичных кодов // Радиотехника и электроника. 2010. Т. 55. № 3. С. 324 - 329.

66. Золотарев В. В., Овечкин Г. В. Алгоритмы многопорогового декодирования для гауссовских каналов // Информационные процессы. Т. 8, № 1, 2008. С. 68-83.

67. Као В. Т. Многопороговые декодеры для гауссовских каналов // Новые информационные технологии в научных исследованиях и в образовании.

Материалы 19-й Всероссийской научно-техн. конф. - Рязань: РГРТУ, 2014. С. 121 - 122.

68. Cavers J. К. Mobile Channel Characteristics // Kluwer Akademic Publishers. 2000.

69. David Tse and Pramod Viswanath. Fundamentals of Wireless Communication // Cambridge University Press, 2005.

70. Awad M., Wong К. Т., Li Z. An Integrative Overview of the Open Literature's Empirical Data on the Indor Radiowave Channel's Temporal Properties // IEEE Transactions on Antennas & Propagation. May 2008, Vol. 56, № 5 pp. 1451 - 1468.

71. Barsocchi P. Channel models for terrestrial wireless communication a survey // CNR - ISTI technical report, April 2006.

72. Jakes W. C. Mikrowave Moble Communications // Piscataway, NJ: IEEE Press, 1994.

73. Pop M. F., Beaulieu N. C. Limitations of sum of sinusoids fading channel simulators // IEEE. Trans. Commun., Apr 2001, vol. 49, pp. 699 - 708.

74. Xiao C., Zheng Y. R. A statistic simulation model for mobile radio fading channels // Proc. WCNC, Mar. 2003, vol. 1, pp. 144-149.

75. Stiiber G. L. Principles of Mobile Communication // Kluwer Akademic Publishers. 2001.

76. Yong D. J., Beaulieu N. C. The generation of correlated rayleigh random variares by inverse fourier transform // IEEE Trans. Commun. Jun. 2000, vol. 48, pp. 1114-1127.

77. Шевляков Д. А. Исследование эффективности многопорогового декодера в беспроводных каналах связи // Электронный журнал Cloud of Science. 2014. Т. l.JVb l.C. 106-111.

78. Овечкин Г. В., Као В. Т. Современные методы помехоустойчивого кодирования // Математическое и программное обеспечение вычислительных систем: межвуз. сб. науч. тр. - Рязань: РГРТУ, 2013. С.

79. Золотарев В.В., Овечкин Г.В. Сложность реализации эффективных методов декодирования помехоустойчивых кодов // 6-я межд. конф. и выст. «Цифровая обработка сигналов и ее применение». М.: 2004. Том 1. С. 220-221.

80. Архипкин А. В. Турбо-коды мощные алгоритмы для современных систем связи // М.: Беспроводные технологии, № 1, Т. 2, 2006. С. 63 - 64.

81. Варгаузин В. А., Протопопов JI. П. Турбо-коды и итеративное декодирование: принципы, свойства, применение // ТелеМультиМедиа, 2000, № 4. С. 33-38.

82. Дмитриева Т.А. Разработка многоуровневого многопорогового устройства декодирования. - Вестник РГРТУ. Вып. 22. Рязань, 2007. С. 73-78.

83. Гринченко H.H., Као В.Т., Овечкин Г.В. Эффективность схем соединения нескольких многопороговых декодеров при декодировании самоортогональных кодов / Информационные технологии : межвуз. сб. науч. тр. -Рязань: РГРТУ, 2014. С. 27 - 34.

84. Гринченко H.H., Као В.Т., Овечкин Г.В. Развитие многоуровневого многопорогового декодера / Методы и средства обработки и хранения информации : межвуз. сб. науч. тр. - Рязань: РГРТУ, 2014. С.

85. Као В.Т., Овечкин Г.В. Повышение эффективности многоуровневого многопорогового декодера самоортогональных кодов. - Вестник РГРТУ. № 3 (выпуск 49). Рязань, 2014. С. 10-14.

86. Овечкин Г. В., Овечкин П. В. Эффективность каскадной схемы кодирования на базе многопорогового декодера и кодов Хэмминга // Математическое и программное обеспечение вычислительных систем: Межвуз. сб. науч. тр. Рязань: РГРТА, 2004. С. 79 - 82.

87. Гринченко Н. Н., Овечкин Г. В., Овечкин П. В. Разработка каскадных схем кодирования на основе многопороговых декодеров // 8-я межд. конф. и выст. «цифровая обработка сигналов и ее применение». М.: 2006. Том 1. С. 60-63.

88. Золотарев В. В., Овечкин Г. В. Использование многопоргового декодера в каскадных схемах//Вестник РГРТА. 2003. Вып. 11. С. 112-115.

89. № 73569, кл. И 03 М, 2008 .

90. Овечкин Г. В. Применение min-sum алгоритма для декодирования блоковых самоортогональных кодов // Межвуз. сб. науч. тр. «Математическое и программное обеспечение вычислительных систем». - М.: Горячая линия - Телеком, 2010. С. 99-105.

91. Гринченко Н. Н., Као В. Т., Овечкин Г. В. Повышение эффективности многопорогового декодера // Математическое и программное обеспечение вычислительных систем: межвуз. сб. науч. тр. - Рязань: РГРТУ, 2014. С. 60-64.

92. Chung S., Forney D., Richardson Т., Urbanke R. On the Design of Low-Density Parity-Check Codes within 0.0045 dB of the Shannon Limit // IEEE Comm. Letters. - Feb. 2001. Vol.5. №2. P.58-60.

93. Richardson Т., Shokrollahi M., Urbanke R. Design of capacity-approaching irregular low-density parity-check codes // IEEE Trans. Inform. Theory. - Feb. 2001. V. 47. P. 638-656.

94. Berg V., Dielissen J., Hekstra A. Low cost LDPC decoder for DVB-S2 // Proceedings of the conference on Design, automation and test in Europe: Designers' forum. - 2006.

95. Золотарёв B.B., Овечкин Г.В. Применение многопорогового декодера в схемах с параллельным каскадированием // Труды 59 науч. сессии, поев. Дню радио. - М., 2004, Том 2. С. 121-123.

96. Овечкин Г.В., Овечкин П.В. Построение самоортогональных кодов устойчивых к эффекту размножения ошибок // Мат. 14-й Межд. науч.-техн. конф. «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций». - Рязань: РГРТА, 2005. С. 70-71.

97. Овечкин Г. В., Пылькин А. Н., Шевляков Д. А. Исследование эффективности многопорогового декодера в каналах связи с замираниями // Материалы 6-й Международной научно-технической конференции

«Космонавтика. Радиоэлектроника. Геоинформатика». - Рязань: РГРТУ, 2013. С. 214-215.

98. Vontobel Р. О., Koetter R. Graph-cover decoding and finite-length analysis of message-passing iterative decoding of LDPC codes // IEEE Transactions on Information Theory. - 2005, December. - pp. 67.

99. Kabashima Y., Saad D. Belief propagation vs. TAP for decoding corrupted messages // Europhysics Letters. - 1998, October. - Vol. 44. - No. 5. - pp. 668 - 774.

100. Yedidia J. S., Freeman W. Т., Weiss Y. Understanding belief propagation and its generalizations // Exploring Artificial Intelligence Laboratory. - 2001, August.-pp. 236-239.

101.Richardson Т., Novichkov V. Node processors for use in party check decoders // United State Patent 6,938,196 B2. - 2005, August 30.

102.Гринченко H.H., Kao B.T., Овечкин Г.В. Декодирование самоортогональных помехоустойчивых кодов с помощью многопорогового и min-sum алгоритмов // Современные проблемы науки и образования. - 2015. - № 1; URL: www.science-education.ru/121-17793.

СПИСОК ИСПОЛЬЗУЕМЫХ СОКРАЩЕНИЙ

LDPC - Low Density Perity Check

МПД - Многопороговый декодер

СОК - Самоортогональный код

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

#СК - g-ичный симметричный канал

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

ПД - Пороговый декодер

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

ПЭ - Пороговый элемент

ТК - Турбо коды

RSC - Recursive Systematic Convolutional

SISO - Soft-input soft-output

ТКП - Турбо коды произведения

PO - Размножение ошибок

ПФВ - Производящая функция вероятности

ОД - Оптимальный декодер

BPSK - Binary phase shift keying

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