Разработка и моделирование алгоритмов декодирования полярных кодов в системе информационно-управляющих комплексов тема диссертации и автореферата по ВАК РФ 05.12.13, кандидат наук Чилихин, Николай Юрьевич

• Чилихин, Николай Юрьевич
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Чилихин, Николай Юрьевич

СОДЕРЖАНИЕ

Введение

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

КОДИРОВАНИЯ СОВРЕМЕННЫХ СИСТЕМ ОБМЕНА ДАННЫМИ

1.1. Пути конвергенции современных телекоммуникационных технологий

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

1.3. Принципы построения полярных кодов

1.4. Принципы построения кодов Рида-Маллера

1.5. Выводы по главе и постановка задач на исследование

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

2.1. Свойства каналов связи в процедуре обмена данными на основе радиоинтерфейса

2.2. Принцип формирования индексов мягких решений в модифицированном стирающем канале

2.3. Особенности декодирования полярных кодов

2.4. Особенность формирования кодового вектора в схеме полярного кодирования и эквивалентность кодам Рида-Маллера

2.4.1. Принципы фиксации ненадежных каналов на основе параметра Бхаттачария в схеме полярного кодирования

2.4.2. Эквивалентность кодов Рида-Маллера и полярных кодов

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

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

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

3.2. Свойство эквивалентности линейных блоковых кодов

3.3. Лексикографический метод в процедуре списочного декодирования блоковых кодов

3.3.1. Обоснование метода

3.3.2. Классификация методов защиты номера кластера

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

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

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

ГЛАВА 4. ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ СИСТЕМ ОБМЕНА ДАННЫМИ С ИСПОЛЬЗОВАНИЕМ РАЗРАБОТАННЫХ

АЛГОРИТМОВ

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

4.2. Моделирование процедуры защиты номера кластера

4.2.1. Принцип моделирования непрерывного канала связи

4.2.2. Методика оценки параметров гауссовского канала связи

4.2.3. Оценка вероятности ошибки на комбинацию

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

Приложение А. Защита номера кластера путем циклических отчетов

Приложение Б. Алгоритм декодирования ПК с итеративной процедурой

проверки номера кластера

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

ВВЕДЕНИЕ

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

Объективно возрастающие требования к оперативности управления современных и перспективных информационно-управляющих комплексов (ИУК) диктуют необходимость применения коротких циклов управления (ЦУ). Поэтому для защиты информации от ошибок в прямых и обратных каналах связи системы управления (СУ) целесообразно использовать короткие помехоустойчивые коды. Уменьшение длины кодовых последовательностей при заданных требованиях по достоверности приводит к необходимости гибкого синтеза кодовых и алгоритмических способов коррекции ошибок на основе применения в них мягких методов декодирования в сочетании с итеративными преобразованиями данных. В определенной мере этому требованию отвечают сравнительно новые конструкции на основе полярных кодов (ПК). Применение концепции ПК обусловлено рядом положительных свойств данного класса блоковых кодов: достижением асимптотически возможной пропускной способности двоичного канала без памяти и возможностью свободного выбора требуемого кодового расстояния в рамках метрики Хэмминга.

В настоящее время над проблемой совершенствования систем связи с ПК активно работает ряд научных коллективов. Среди них следует выделить Белькентский университет, Турция (Е. Arikan - автор первоначальной концепции ПК), Калифорнийский университет, Сан Диего (I. Tal, A. Vardy и др.), Калифорнийский университет, Беркли (Е. Sasoglu), Швейцарский федеральный технологический институт, Лозанна (S. Korada, R. Urbanke и др.), Токийский институт технологий (R. Mori, Т. Tanaka и др.), Босфорский университет, Стамбул (A. Pusane), среди отечественных организаций - Санкт-Петербургский государственный политехнический университет (П.В. Трифонов, П.К. Семенов).

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

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

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

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

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

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

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

3. Классификация и исследование методов защиты номера кластера при его передаче по каналам с помехами.

4. Оценка на основе математического моделирования потенциальных возможностей предложенных алгоритмов декодирования ПК с использованием целочисленных ИМР в условиях применения каналов связи с независимым потоком ошибок.

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

1. С использованием расстояния Бхаттачария выявлены новые особенности формирования «замороженных» каналов ПК и раскрыто их влияние на структуру

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

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

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

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

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

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

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

сигналов в стохастических каналах связи, теории оценивания, алгебраической теории групп, колец и полей.

Аналитическое и имитационное моделирование проводилось с использованием языков программирования высокого уровня лицензионных версий МаШсас! и МАТЬЛВ.

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

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

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

3. Потенциальные возможности предложенных алгоритмов по обеспечению энергетического выигрыша СОД с ПК в рамках предложенной концепции.

Апробация результатов исследования

Основные положения и результаты работы докладывались на следующих конференциях: Научная сессия РНТОРЭС им. Попова, посвященная Дню Радио, г. Москва (2013, 2014); Международная конференция «Цифровая обработка сигналов и ее применение» - ББРА, г. Москва (2014, 2015); Международная научно-техническая конференция «Радиолокация, навигация, связь» - ЯЬЫС, г. Воронеж (2013, 2014); XV Международная научно-техническая конференция «Проблемы техники и технологий телекоммуникаций» - ПТиТТ, г. Казань (2014); Всероссийская научно-практическая конференция «Современные проблемы создания и эксплуатации радиотехнических систем», г. Ульяновск (2014).

Результаты работы опубликованы в 13 печатных трудах (5 из которых опубликованы в журналах, входящих в перечень ВАК, 8 тезисов и текстов докладов на международных и всероссийской конференциях).

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

Результаты исследования внедрены в организации ФНПЦ ОАО «НПО «Марс» - г. Ульяновск при выполнении НИР «Каскад-2», что подтверждается соответствующим актом.

Структура, объем и содержание работы

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

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

1.1. Пути конвергенции современных телекоммуникационных технологий

Модернизация СОД - объективный и непрерывный процесс, в основе которого заложены фундаментальные принципы пакетной передачи и технологии, ассоциированные с ней. Предоставление телекоммуникационных услуг по одним и тем же правилам стало гарантом повышения уровня качества обслуживания, на который не оказывают влияния способы транспортировки данных и используемое оборудование. Подобная концепция создает условия гибкого и эффективного построения глобального информационного общества. Значительным шагом в этом направлении являются сети следующего поколения (Next Generation Network - NGN), которые предполагают управление сервисами и непрерывное управление транспортной сетью [5, 32, 71, 72, 74]. Успехи современных сетевых технологий непосредственно отражаются на совершенствовании принципов взаимодействия элементов интегрированных ИУК. Например, в последние годы большое внимание уделяется созданию систем передачи и обработки информации многопозиционных мобильных радиолокационных станций, систем создания воздушной обстановки близкой к реальной в масштабе 3D, систем оценки координат автономных мобильных объектов и т.п. [66].

Современные ИУК в защищенных мультисервисных сетях развиваются в направлении повышения оперативности и достоверности ЦУ, который своевременно реагирует на внешние воздействия и элементы сети, носящие деструктивный характер. Указанный подход, прежде всего, обусловлен необходимостью создания высокоорганизованной синхронизации в современных СОД на всех уровнях модели OSI. Существующие технологии, такие как: IP/ATM (Asynchronous Transfer Mode - асинхронный способ передачи данных), IP/MPLS (Multiprotocol Label Switching - многопротокольная коммутация по меткам), IP/Gigabit Ethernet, лежащие в основе построения данного класса сетей, удовлетворяют подобным требованиям и поэтому находят отражения в

специализированных СОД ИУК [5, 11, 33, 71, 72]. Однако для обеспечения требуемой оперативности ЦУ необходимо создание высокоскоростных каналов связи. Подобная задача решается за счет применения волоконно-оптических линий связи и совершенствования технологий радиоинтерфейса обработки цифровых сигналов. В любом случае характер мешающих воздействий на сигнал и особенности реальных каналов связи позволяют говорить о необходимости применения схем помехоустойчивого кодирования. Подобная потребность возникает по причине возрастающих требований к достоверности информации, обрабатываемой конечным пользователем в ИУК [33, 42, 74].

На данный момент преимущественно используется сочетание технологий ATM и MPLS, при этом на основе ATM происходит построение сетей доступа, а MPLS является основой ядра транспортной сети. Использование MPLS в качестве ядра обусловлено высокой степенью масштабирования, поскольку в данной технологии имеется возможность функционального наращивания системы путем добавления новых элементов или замены устаревших на более совершенную элементную базу, при этом данные действия не влекут за собой изменения архитектуры. Эта особенность наиболее актуальна для транспортной сети [5, 72, 74]. Свойство масштабируемости наиболее отчетливо выражается в низовых звеньях иерархических ИУК, для которых характерны не только высокая динамика решаемых задач, но и возможные изменения топологии СОД из-за влияния мешающих факторов.

Это предопределило преимущественное применение в таких звеньях беспроводных технологий СОД. Развитие беспроводных технологий, таких как: UMTS (Universal Mobile Telecommunications System - универсальная мобильная телекоммуникационная система), WIMAX (Worldwide Interoperability for Microwave Access - стандарт беспроводного микроволнового доступа), LTE (Long-Term Evolution - стандарт мобильной связи) и т.д. расширило функциональные возможности конечного мобильного пользователя [5, 21, 29, 32, 33, 72, 74, 79]. При проектировании СОД ИУК реального времени формируется обмен информацией между управляющим объектом и объектами управления

через информационную систему (систему связи и сетевые ресурсы) [11, 32, 33, 72, 79]. Таким образом, современные телекоммуникационные технологии играют решающую роль в способах организации и структуре построения существующих и проектируемых мобильных ИУК или специализированных СУ. Подобные системы призваны осуществлять сбор заданного набора сведений об управляемых объектах и, в соответствии с целевой функцией Р{}У,и,Т), выполнять управление этими объектами. В СУ множество объектов \У считается заданным, в то время как множество условий функционирования и может изменяться и оказывать влияние на достижение в требуемые интервалы времени Т.

Временные параметры СУ определяются длительностью ЦУ Т15у, выполнение которого является показателем эффективности достижения В условиях

действия интенсивных мешающих факторов снижение параметра может быть

достигнуто только за счет применения интегрированных СУ и ИУК на основе материального носителя в виде системы связи, способной передавать не только короткие сигналы управления, но и большие объемы мультимедийных данных [5, 29, 33].

Наличие прямого и обратного каналов связи в классической СУ требует выполнения обязательного условия кп-(Тпк+Ток)«Т11у, где кп - коэффициент,

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

Тсс=кп-(Тпс+Ток), в СУ тратится на обработку данных и принятие решения как в управляемом объекте, так и в управляющем объекте, при этом А ^ 0. Повсеместное внедрение беспроводных технологий, увеличение объемов обрабатываемой посредством них информации, повышение требований к скорости обмена данными и их достоверности позволяют говорить о необходимости совершенствования СУ современных мобильных комплексов с использованием радиоканалов [5, 11, 29, 32, 72, 74].

Мультимедийность трафика, относительная неопределенность размерности и точности исходных данных, используемых в СУ, приводят к необходимости создания эффективной модели управления сетевыми элементами и ресурсами. Действительно, в ЦУ могут быть использованы данные объемом от нескольких десятков бит до нескольких мегабайтов. Известна модель сети управления электросвязью (Telecommunications Management Network - TMN), которая учитывает интеллектуализацию управления указанными параметрами. Структура взаимодействия задач управления в рамках указанной модели носит иерархический характер [72, 74]. При использовании нестационарных каналов связи, подверженных помехам естественного и антропогенного характера, для эффективной передачи мультимедийного трафика целесообразно использование адаптивных СОД с масштабируемой избыточностью и применением мягких методов обработки данных [73, 131, 136].

В силу многообразия сетевых служб, задействованных в доставке информации, возникают требования к сети, одним из которых является качество доставки, реализованное в виде временных критериев и уровня ошибок в переданных данных [5, 11, 29, 32, 33, 64, 65, 71, 72]. В реальных каналах действуют искажения сигналов, замирания, шумы, различные помехи, которые в дискретном канале проявляются в виде ошибок, определяющих верность правильного приема информации. Одним из наиболее часто используемых показателей, которым принято характеризовать качество цифровых систем передачи, является вероятность ошибок на бит (Bit Error Rate - BER). В пакетных сетях в качестве показателя, характеризующего качество передачи пакетов, принято использовать вероятность искажения пакета (Frame Error Rate - FER) [5, 11, 14, 15, 21, 29, 46, 64, 65 71]. Природа указанных ошибок во многом определяется техническими устройствами, физической средой и рядом других факторов, в том числе и антропогенного характера. К временным критериям качества доставки данных принято относить два показателя: время задержки и джитгер задержки. По рекомендациям Международного союза электросвязи (МСЭ) Y.1541 с учетом особенностей NGN выделены шесть классов

облуживания, число которых может увеличиваться. К ним, в первую очередь, следует отнести: интерактивный, интерактивный при использовании спутниковой линии связи, сигнальный, потоковый и трафик передачи данных. Параметры основных служб по указанным показателям приведены в таблице 1.1. В этой таблице PPLR — вероятность потери пакета (Packet Loss Rate - PLR) и PPIR -вероятность доставки пакета не по адресу (Packet Insertion Rate - PIR) [5, 74].

Таблица 1.1- Параметры основных служб

Служба PBER PpLR РPIR Задержка, мс

Телефония ю-7 10~3 10"3 25/400

Передача данных 10"7 10"6 10"6 1000 (50)

ТУ 10"6 10"8 ю-8 1000

Звуковые сигналы с высокой точностью воспроизведения 10~5 ю-7 ю-7 1000

Управление обработкой в распределенных базах данных 10"5 10~3 ю-3 1000

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

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

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

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

Возрастающие требования к управлению элементами интегрированных ИУК диктуют необходимость применения разнородных по организации протоколов обмена и длительности ЦУ. Одним из существующих и активно применяющихся механизмов подстройки к условиям функционирования СУ является использование средств избыточного кодирования. На практике помехоустойчивое кодирование наталкивается на ряд ограничивающих факторов, важнейшим из которых является экспоненциальный рост сложности декодера при увеличении краткости исправляемых избыточным кодом ошибок [4, 6, 18, 22, 39, 41, 60, 64, 71, 79]. На данный момент способы комбинирования и модификаций существующих схем помехоустойчивого кодирования являются приоритетными направлениями решения указанной задачи. В работе [76] были введены каскадные коды в качестве метода практической реализации кода с очень большой длиной блока и весьма высокой корректирующей способностью. Аналогичный подход рассматривался в работе [7], в которой были предложены обобщенные каскадные коды (ОКК). Это семейство кодов способно исправлять не только случайные ошибки, но и случайные пакеты ошибок. Конструкция ОКК является комбинацией принципов прямой суммы кодов (разложения по смежным классам) и каскадного конструирования кодов [64]. Наиболее важной характеристикой линейного блокового (ТУ, К, с?) кода С в рамках концепции ОКК является возможность разложения на линейные блоковые г/,) подкоды С,-,

0<1<МС— 1, где Мс — уровень разложения на вложенные подкоды. Для осуществления разложения указанной структуры необходимо выполнение ряда условий [64]:

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

М-1

С=^Сг О-1)

1=0

2. Для любого кодового слова V, на выходе результирующего кодера, где

V, е С,, существует взаимно-однозначное соответствие

м-1

2] у| =0^У0=У1=... = Ул/_1=0. (1.2)

1=0

3. Необходимо ввести линейный блоковый (п1, кп) код Си такой, что символы на входе кодеров

М-1

21 м,=о->1/,=о, (1.3)

/=о

где / - число ступеней кодирования (в классической каскадной схеме I = 2).

Таким образом, введя минимальное расстояние Хемминга 5,- прямой суммы кодов СИ + С1М+...+С1М _х и перейдя в область линейного блокового

(«о, £0/, ¿/0/) кода С01, над трансформированным полем GF(#fc), где к = кп,

получим весовое расстояние Хемминга с1 кода С, ограниченное снизу соответствующей границей [64]

й^гшпб^-. (1.4)

Тогда сумма каскадных кодов дает линейный блоковый («0«7, к, с1) код, размерность которого соответственно равна

*=2>/А)/> 0-5)

1=0

при этом минимальное расстояние описывается выражением (1.4) [64].

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

счет использования подкомпонентных кодов при больших / и Мс, что приводит только к линейному росту сложности декодера в зависимости от кратности исправляемых ошибок [37, 40, 41, 64, 71, 75, 77], но в условиях реального времени большие / и Мс малопригодны.

До появления турбокодов (ТК) и практической реализации кодов с низкой плотностью проверок (Low-Density Parity-Check codes - LDPC) каскадная структура в виде внешнего кода Рида-Соломона (PC) и внутреннего сверточного кода являлась наиболее распространенной кодовой конструкцией [17, 64, 68, 71, 106, 135]. При этом коды PC до сих пор находят широкое применение [6, 29, 50, 64, 67, 71, 103, 121]. Как известно, коды PC можно определить как множество кодовых слов, компоненты которых равны значениям некоторых определенных многочленов. Таким образом, речь идет о полиномиальных кодах, в основе которых лежит информационный полином P^nf(jc) = a1 +a2-х + ...+аЛ-х*-1 с

коэффициентами aieGF(2w), где т — степень расширения двоичного поля

Галуа, а a - примитивный элемент этого поля. В отличие от кодов Боуза-Чоудхоури-Хоквенгема (БЧХ) коды PC строятся над трансформированным полем

GF(2m). В частности нулями кода PC, исправляющего td ошибок, являются 2 -td последовательных степеней примитивного элемента поля Галуа. Все делители порождающего код многочлена i^nf(x) являются линейными, тогда

порождающий полином имеет вид [6, 50, 64]

b+2-tj-l

g(x)= П (х-а1), (1.6)

j=b

где b - целое число, обычно принимает значение «0» или «1».

Из выражения (1.6) следует, что минимальное расстояние (п, к, d) PC кода

над трансформированным полем GF{2m) удовлетворяет неравенству d>n-k +1 [64]. С учетом границы Синглтона [6, 60, 64, 67, 68] можно сделать вывод, что d = n — k +1, и коды PC — это коды с максимально достижимыми расстояниями

[128]. Известно, что кодам PC присущ изоморфизм между полем GF(2m) и

l m

множеством {0,1} . При этом если элементы GF(2m) рассматривать как векторы из т бит [3], то из кода PC получаем двоичный линейный код длины п-т- (2т -1) и размерности к = т-(2т -l-2-td). Минимальное расстояние такого кода не меньше 2 -td [6, 29, 64, 71]. Таким образом, код PC способен исправлять не только до td случайных ошибок, но и многократные случайные пакеты ошибок, что актуально для передачи информации реального времени в системе радиоинтерфейса. Это объясняет широкое распространение подобного вида кодов в реальных системах связи.

Существенное отличие в процедуре декодирования кодов PC от кодов БЧХ заключается в вычислении вектора ошибок , где 1<х<(п — к)/2, через

двухступенчатую процедуру определения локаторов ошибок и их последующего исправления. В общем случае это делается через алгоритм Форни. Для кодов с произвольным множеством 2-td последовательных нулей {аь,аь+х,....,аь+5}, где d = 2 ■ td +1, значение ошибок определено как

л 0'(а~л) 7

где 0'(а~л) - производная от локаторов ошибок, а A(a~Jt) - многочлен значений ошибок [29, 64, 71].

Наиболее распространенными алгоритмами декодирования кодов PC являются алгоритм Берлекэмпа-Месси (БМА) [62] и Евклидов алгоритм (ЕА) [29, 64]. В отличие от БМА ЕА использует все синдромы уже на первом шаге процедуры. Однако по числу операций в конечном поле БМА эффективнее ЕА [64]. ЕА имеет однообразную структуру, что значительно упрощает аппаратную реализацию.

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

[11, 29, 38, 39, 40, 46, 48, 64, 71]. В концепции итеративного декодирования важным понятием является логарифмическое отношение правдоподобия (Log Likelihood Ratio - LLR) для информационного символа [29, 37, 47, 48, 64, 71, 90]

"^•=+1137)"

LLR(u.t\y) = ]n

(1.8)

Р{гЧ=-\\у)

где м,=±1 - возможные значения бита, у - принятая приемником последовательность бит. Следует отметить, что LLR для информационного символа является аддитивной величиной, определяемой как [64]

ЫЯ(щ) = ЫЖсН + ЬЬЯа{щ) + 1Ше , (1.9)

где — LLR канала, — априорное значение LLR информационного

символа, а ЬЬЯе — LLR, накладываемое другими информационными символами. Среди всего многообразия итеративно декодируемых кодов целесообразно выделить ТК и LDPC. ТК можно рассматривать как параллельный составной код,

порождающая матрица которого может быть приведена к виду [47, 64, 91, 92]

(1Л0)

где Р[ =

0

, а Р7 =

0

- есть матрица проверочных

2 J

символов.

Между матрицами Р]| и Р2 есть матрица перестановок В, ассоциированная с перемежителем (интерливером). Итеративное декодирование ТК условно можно разделить на две составляющие. На первом этапе декодер производит вычисление апостериорных LLR, при этом считается, что любой символ носит равновероятностный характер LLRa(Uj) = 0. Далее происходит вычисление LLRe[ на основе проверочных символов первого компонентного кода, и полученная информация передается второму декодеру. В качестве декодера рассматривается SISO (Soft-Input Soil-Output) декодер. На втором этапе перемеженные элементы внешней информации от первого декодера рассматриваются как априорные LLR,

Список литературы диссертационного исследования кандидат наук Чилихин, Николай Юрьевич, 2015 год

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Агафонов, И.В. Коды Рида-Маллера: примеры исправления ошибок / И.В. Агафонов // Семинар по дискретному гармоническому анализу и геометрическому моделированию «DHA & CAGD». - 2012. - С. 1-16.

2. Акимов, O.E. Дискретная математика: логика, группы, графы, фракталы / O.E. Акимов. - М.: издатель АКИМОВА, 2005. - 656 с.

3. Арнольд, В.И. Динамика, статистика и проективная геометрия полей Галуа / И.В. Арнольд. - М.: МЦНМО, 2005. - 72 с.

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

5. Битнер, В.И. Сети нового поколения NGN: учеб. пособие для вузов / В.И. Битнер, Ц.Ц. Михайлова. - М.: Горячая линия - Телеком, 2011. - 225 с.

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

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

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

9. Ван Трис, Г. Теория обнаружения, оценок и модуляции. Том первый / Г. Ван Трис. - М.: Советское радио, 1977. - 534 с.

10. Ван Трис, Г. Теория обнаружения, оценок и модуляции. Том третий / Г. Ван Трис. - М.: Советское радио, 1977. - 662 с.

11. Варгаузин, В.А. Методы повышения энергетической и спектральной эффективности цифровой радиосвязи: учебное пособие / В.А. Варгаузин, В.А. Цикин. - СПб.: БХВ-Петербург, 2013.-352 с.

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

13. Васильев, К.К. Методы обработки сигналов: учебное пособие / К.К. Васильев. - Ульяновск: УлГТУ, 2001. - 78 с.

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

15. Вентцель, Е.С. Теория вероятностей и ее инженерные приложения: учеб. пособие для вузов / Е.С. Вентцель, Л.А. Овчаров. - 2-е изд., стер. — М.: Высш. шк., - 2000. - 480 с.

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

288 с.

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

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

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

20. Возенкрафт, Дж. Теоретические основы техники связи / Дж. Возенкрафт, И. Джекобе. - М.: Мир, 1969. - 640 с.

21. Волков, Л.Н. Основы цифровой радиосвязи: базовые методы и характеристики: учебное пособие / Л.Н. Волков, М.С. Немировский, Ю.С. Шинаков. - М.: Эхо Тредз, 2005. - 392 с.

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

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

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

25. Гладких, A.A. Асимптотическая оценка процедуры неалгебраического декодирования избыточных кодов / A.A. Гладких, Р.Ш. Шакуров,

К.Ю. Украинцев // Периодический научно-технический и информационно-аналитический журнал «Инфокоммуникационные технологии». - 2009. - Том 6, № 3. - С. 30-34.

26. Гладких, A.A. Декодирование полярных кодов в декодере Арикана на базе индексов мягких решений / A.A. Гладких, НЛО. Чилихин // Периодический научно-технический и информационно-аналитический журнал «Инфокоммуникационные технологии». - 2014. - Том 12, № 3. - С. 11-17.

27. Гладких, A.A. Моделирование алгоритмов совместной обработки полярных кодов в системе произведения кодов / A.A. Гладких, НЛО. Чилихин // Периодический научно-технический и информационно-аналитический журнал «Радиотехника». - 2014. - № 7. - С. 111-115.

28. Гладких, A.A. Мягкое декодирование произведений кодов произвольной размерности на базе кодов с единственной проверкой четности / A.A. Гладких, H.IO. Чилихин // Периодический научно-технический журнал «Известия Самарского научного центра Российской академии наук». - 2013. -Том 15, № 4-3. - С. 668-674.

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

30. Гладких, A.A. Формирование мягких решений в системе широкополосного канала связи с QPSK-QAM / A.A. Гладких, НЛО. Чилихин // Автоматизация процессов управления. - 2013. - № 3 (33). - С. 8-18.

31. Гладких, A.A. Численное моделирование обобщенной процедуры формирования индексов мягких решений / A.A. Гладких, Р.В. Климов // Периодический научно-технический и информационно-аналитический журнал «Инфокоммуникационные технологии». - 2013. - Том 12, № 2. — С. 22-28.

32. Голдсмит, А. Беспроводные коммуникации / А. Голдсмит; пер. с англ. под ред. В.А. Березовского. - М.: Техносфера, 2011. - 904 с.

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

34. Евстигнеев, В.А. Теория графов: алгоритмы обработки деревьев / В.А. Евстигнеев, В.Н. Касьянов. — Новосибирск: Наука, 1994. - 361 с.

35. Зигангиров, Д.К. Декодирование низкоплотностных кодов с проверочными матрицами, составленными из перестановочных матриц, при передаче по каналу со стираниями / Д.К. Зигангиров, К.Ш. Зигангиров // Проблемы передачи информации. - 2006. - Т. 42, В. 2. - С. 44-52.

36. Зигангиров, К.Ш. К теории списочного декодирования сверточных кодов / К.Ш. Зигангиров, Р. Йоханнессон // Проблемы передачи информации. -1996. - Т.32, №1. - С. 122-130.

37. Злотник, Б.М. Помехоустойчивые коды в системах связи: статистическая теория связи / Б.М. Злотник. - Вып. 31. - М.: Радио и связь, 1989. -232 с.

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

39. Золотарев, В.В. Теория и алгоритмы многопорогового декодирования / В.В. Золотарев. - М.: Радио и связь, Горячая линия-Телеком, 2006. - 276 с.

40. Зубарев, Ю.Б. Обзор методов помехоустойчивого кодирования с использованием многопороговых алгоритмов / Ю.Б. Зубарев, В.В. Золотарев,

B.Г. Овечкин // Цифровая обработка сигналов. - 2008. - №1. -

C. 2-11.

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

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

43. Зяблов, В.В. Метод обнаружения ошибочного декодирования с использованием списков / В.В. Зяблов, М.А. Цветков // Информационные процессы. -2004. - Т.4. - С. 188-201.

44. Зяблов, B.B. Об оптимальном выборе порога в системе множественного доступа, основанной на перестроении ортогональных частот / В.В. Зяблов, Д.С. Осипов // Проблемы передачи информации. - 2008. - Т.44, № 2. -С. 23-31.

45. Зяблов, В.В. Оценка сложности исправления ошибок низкоплотностными кодами Галлагера / В.В. Зяблов, М.С. Пинскер // Пробл. передачи информации. - 1975. -Т. 11, №1. - С. 23-36.

46. Карташевский, В.Г. Обработка пространственно-временных сигналов в каналах с памятью / В.Г. Карташевский. - М.: Радио и связь, 2000. - 271 с.

47. Карташевский, В.Г. Итерационное декодирование турбо-кодов в канале с памятью / В.Г. Карташевский, Д.В. Мишин // 3-я Международная конференция и выставка «Цифровая обработка сигналов и ее применение». - 2000. - С. 65-68.

48. Карташевский, В.Г. Прием кодированных сигналов в каналах с памятью / В.Г. Карташевский, Д.В. Мишин. - М.: Радио и связь, 2004.- 239 с.

49. Карташевский, В.Г. Помехоустойчивость приема сигналов ФМ-4 в канале с памятью / В.Г. Карташевский // Радиотехника. - 2012. - № 9. -С. 103-111.

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

51.Кловский, Д.Д. Передача дискретных сообщений по радиоканалам / Д.Д. Кловский. - М.: Связь, 1969. - 375 с.

52. Конопелько, В.К. Теория норм синдромов и перестановочное декодирование помехоустойчивых кодов / В.К. Конопелько, В. А. Липницкий. - 3-е изд. - М.: Едиториал УРСС, 2012.-176 с.

53. Коржик, В.И. Помехоустойчивое кодирование дискретных сообщений в каналах со случайной структурой / В.И. Коржик, Л.М. Финк. - М.: Связь, 1975. -272 с.

54. Коржик, В.И. Расчет помехоустойчивости систем передачи дискретных сообщений: справочник / В.И. Коржик, Л.М. Финк, К.Н. Щелкунов. -М.: Радио и связь, 1981. - 232 с.

55. Кофман, А. Введение в прикладная комбинаторику / А. Кофман; пер. с франц. под ред. Б.А. Севастьянова. - М.: Изд-во «Наука», 1975. - 480 с.

56. Лайонс, Р. Цифровая обработка сигналов / Р. Лайонс; пер. с англ. под ред. A.A. Бритова- 2-е издание. - М.: ООО Бином-Пресс, 2006. - 656 с.

57. Липницкий, В.А. Нормированное декодирование помехоустойчивых кодов и алгебраические уравнения / В.А. Липницкий, В.К. Конопелько. - Минск, 2007.-293с.

58. Лычагин, Н.И. Неалгебраическое декодирование групповых кодов в стирающем канале связи / Н.И. Лычагин, С.А. Агеев, A.A. Гладких, A.B. Васильев // Системы и средства связи телевидения и радиовещания. - 2006. -№ 1,2.-С. 49-55.

59. Мак-Вильямс, Ф.Дж. Перестановочное декодирование систематических кодов / Ф.Дж. Мак-Вильямс // Кибернетический сборник. Новая серия. -1965.-Вып. 1.-С. 35-37.

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

61. Математика. Большой энциклопедический словарь / гл. ред. Ю.В. Прохоров. - 3-е изд. - М.: Большая Российская энциклопедия, 1998. — 848 с.

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

284 с.

63. Мишин, Д.В. Методы повышения эффективности обработки сигналов в каналах с памятью: дис. на соискание докт. техн. наук: 05.12.13 / Мишин Дмитрий Викторович. — Самара, 2004. - 368 с.

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

65. Овечкин, Г.В. Помехоустойчивое кодирование в цифровых системах передачи данных / Г.В. Овечкин, Ю.Б. Зубарев. // ISSN 0013-2771, «Электросвязь». - 2008. - №12. - С. 58-61.

66. Павлыгин, Э.Д. Программный комплекс для имитации целей и обработки сигналов в многопозиционной PJ1C / Э.Д. Павлыгин, К.К. Васильев,

A.C. Гуторов, С.М. Наместников // Тезисы VIII Всероссийской научно-технической конференции «Радиолокация и радиосвязь». - Москва, 2014. - 24-26 ноября. - С. 286-289.

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

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

69. Семенов, П.К., Декодирование обобщенных каскадных кодов с внутренними полярными кодами / П.К. Семенов // Информационно-управляющие системы. - 2012. - Выпуск №5. - С. 44-50.

70. Сергиенко, А.Б. Цифровая обработка сигналов / А.Б. Сергиенко. -М.: Питер, 2002. - 348 с.

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

72. Столингс, В. Беспроводные линии связи и сети. Пер. с англ. /

B. Столингс - М.: Издательский дом «Вильяме», 2003. - 640 с.

73. Уидроу, Б. Адаптивная обработка сигналов / Б. Уидроу, С. Стирнз; пер с англ. под ред. В.В. Шахгильдяна. - М.: Радио и связь, 1988. - 440 с.

74. Федеральный справочник. Связь и массовые коммуникации в России. -М.: Центр стратегического партнерства, 2009. - 305 с.

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

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

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

78. Шеннон, К.Е. Математическая теория связи. Работы по теории информации и кибернетики / К.Е. Шеннон. - М.: Иностранная литература, 1963. — 476 с.

79. Шлома, A.M. Новые алгоритмы формирования и обработки сигналов в системах подвижной связи / A.M. Шлома, М.Г. Бакулин, В.Б. Крейнделин, А.П. Шумов. - М.: Горячая линия - Телеком, 2008. - 344 с.

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

81.Элайес, П. Сети гауссовских каналов и их применение к системам с обратной связью / П. Элайес // Некоторые вопросы теории кодирования. -1970. -С.205-229.

82. Alamdar-Yazdi, A. A simplified successive cancellation decoder for polar codes / A. Alamdar-Yazdi, F.R. Kschischang // IEEE Communications Letters. - 2011. - December. - Vol. 15, no. 12.-P. 1378-1380.

83. Alon, N. Linear Time Erasure Codes with Nearly Optimal Recovery / N. Alon, J. Edmonds, M. Luby // IEEE Symposium on Foundations of Computer Science, Proc. IEEE. - 1995. - Vol. 3. - P. 512-519.

84. Arikan, E. A performance Comparison of Polar codes and Reed-Muller Codes / E. Arikan // IEEE Comm. Letters. - 2008. - Vol.12, no.6. - P.447-^49.

85. Arikan, E. Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels / E. Arikan // IEEE Transactions on Information Theory. - 2009. -N 7(55). - P. 3051-3073.

86. Arikan, E. On the rate of channel polarization / E. Arikan, E. Telatar // Proc. IEEE Int'l Symp. Inform. Theory (ISIT'2009), Seoul, South Korea. - 2009. -P.1493-1495.

87. Arikan, E. Systematic polar coding / E. Arikan // IEEE Commmun. Lett. -2011.-Vol. 15.-P. 860-862.

88. 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. - P. 284-287.

89. Bakshi, M. Concatenated polar codes / M. Bakshi, S. Jaggi, M. Effros // Proceedings of the IEEE International Symposium on Information Theory (ISIT'10), Pasadena, CA, USA. Piscataway, NJ, USA: IEEE. - 2010. -Jun 13-18.-P. 918-922.

90. Barg, A. Random codes: Minimum Distances and Error Exponents / A. Barg, G.D. Forney // IEEE Transactions on Information Theory. - 2006. - Vol. 48, no. 9. -P. 2568-2573.

91.Berrou, C. A low complexity soft-output Viterbi decoder architecture / C. Berrou, P. Adde, E. Angui, S. Faudeil // in Proc. of the Intern. Conf. on Commun. -1993.-May.-P. 737-740.

92. Berrou, C. Near Shannon limit error-correcting coding and decoding: Turbocodes / C. Berrou, A. Glavieux, P. Thitimajshima // ICC 93, Geneva. - 1993. - May. -Vol. 2.-P. 1064-1070.

93. Carrasco Rolando Antonio, Non-binary error control coding for wireless communication and data storage / Rolando Antonio Carrasco, M. Johnston. — John Wiley & Sons, Ltd., 2008. - 302 p.

94. Chase, D. A Class of Algorithms for Decoding Block Codes With Channel Measurement Information / D. Chase // IEEE Trans. On Information Theory. - 1972. -Vol. IT-18. -№1.

95. Chen, L. A. Efficient list decoder for algebraic-geometric codes / L. Chen, R. Carrasco; Presented at 9th International Symposium on Communication Theory and Application (ISCTA'07). - Ambleside, Lake district, UK, 2007.

96. Chung, S. On the Design of Low-Density Parity-Check Codes within 0,0045dB of the Shannon Limit / S. Chung, D. Forney, T. Richardson, R. Urbanke // IEEE Trans. Letters. - 2001. - Feb. - V.5. - № 2. - P. 58-60.

97. Djurdjevic, I. A class of low-density parity-check codes constructed based on Reed-Solomon codes with two information symbols / I. Djurdjevic, J. Xu, K. Abdel-Ghaffar, S. Lin // IEEE Commun. Lett. - 2003. -Vol. 7.-P. 317-319.

98. Dumer, I. Soft-decision decoding of Reed-Muller codes: recursive lists / I. Dumer, K. Shabunov // IEEE Trans. Inform. Theory. - 2006. - Vol. 52. -P.1260-1266.

99. Elshahawy, A. An overview on channel polarization and polar codes / A. Elshahawy, B. Honary // ISBN: 978-1-902560-26-7 ©. - 2012.

100. Eslami, A. A practical approach to polar codes / A. Eslami, A. Pishro-Nik // IEEE International Symposium on Information Theory Proceedings. - 2011. -P. 16-20.

101. Fossorier, M. Soft-decision decoding of linear block codes based on ordered statistics / M. Fossorier, S. Lin // IEEE Transactions on Information Theory. - 1995. -N5.-P. 1379-1396.

102. Gallager, R. The Random Coding Bound is Tight for the Average Code / R. Gallager // IEEE Transactions on Information Theory. - 1973. - Vol. 19, no. 2. -P. 244-246.

103. Guruswami, V. Improved Decoding of Reed-Solomon and Algebraic-Geometry Codes / V. Guruswami, M. Sudan // IEEE Transactions on Information Theory. - 1999. - Sept. - P. 1757-1767.

104. Goela, N. On LP decoding of polar codes / N. Goela, S.B. Korada, M. Gastpar // IEEE Inf. Theory Workshop (ITW). - 2011. - P. 1-5.

105. Hagenauer, J. A Viterbi Algorithm with Soft-Decision Outputs and Its Applications / J. Hagenauer, P. Hoher // IEEE Global Telecommunications Conference (GLOBECOM'89). - 1989. - P. 47.1.1-47.1.7.

106. Hagenauer, J. Iterative decoding of binary block and convolutional codes / J. Hagenauer, E. Offer, L. Papke // IEEE Transactions on Information Theory. - 1996. -March. - Vol. 42. - P. 429-445.

107. Hassani, S.H. On the scaling of polar codes: I. The behavior of polarized channels / S.H. Hassani, R. Urbanke // IEEE Int. Symp. on Inf. Theory (ISIT). - 2010. - June. - P. 874-878.

108. Hof, E. Polar coding for reliable communications over parallel channels / E. Hof, I. Sason, S. Shamai // IEEE Information Theory Workshop. - 2010. - P. 1-18.

109. Hussami, H. Performance of polar codes for channel and source coding / H. Hussami, R. Urbanke, S. Korada // IEEE ISIT 2009. - 2009. -Jun. — P. 1488-1492.

110. Kahraman, S. Code based efficient maximum-likelihood decoding of short polar codes / S. Kahraman, M.E. Celebi // IEEE Int. Symp. on Inf. Theory (ISIT). -2012.-P. 1967-1971.

111. Kasami, T. Some Results on the Weight Structure of Reed-Muller-Codes / T. Kasami // Доклад на II Международном симпозиуме по теории информации, сент. 1971, Цахкадзор. Тезисы докладов. - 1971. - С. 351-353.

112. Koetter, R. Algebraic Soft-Decision Decoding of Reed-Solomon Codes / R. Koetter, A. Vardy // Proc. 2000 IEEE Int. Symp. Info. Theory (ISIT), Sorrento, Italy. - 2000. - June 25-30. - P. 61.

113. Korada, S.B. An empirical scaling law for polar codes / S.B. Korada, A. Montanari, I.E. Telatar, R. Urbanke // IEEE Int. Symp. on Inf. Theory (ISIT). -2010.-June.-P. 884-888.

114. Korada, S.B. Polar Codes are Optimal for Lossy Source Coding / S.B. Korada, R.L. Urbanke // IEEE Trans, on Inform. Theory. - 2010. - Apr . - Vol. 56, no. 4.-P. 1751-1768.

115. Korada, S.B. Polar Codes for Channel and Source Coding / S.B. Korada. -PhD thesis, Ecole Polytechnique Federale de Lausanne (EPFL), 2009. -181 p.

116. Korada, S.B. Polar Codes: Characterization of Exponent, Bounds, and Constructions / S.B. Korada, E. Sasoglu, R. Urbanke // IEEE Trans, on Information Theory. - 2010. - Vol. 56, no. 12. - P. 6253-6264.

117. Leroux, С. Hardware architectures for successive cancellation decoding of polar codes / C. Leroux, I. Tal, A. Vardy, W.J. Gross // Proc. IEEE Int Acoustics, Speech and Signal Processing (ICASSP) Conf. - 2011. - P. 16651668.

118. Luby, M.G. Efficient Erasure Correcting Codes / M.G. Luby, Mitzenmacher, M.A. Shokrollahi, D.A. Spielman // IEEE Transactions on Information Theory. - 2011. - Vol. 47, no. 2. - P. 569-584.

119. Mahdavifar, H. Achieving the Secrecy Capacity of Wiretap Channels Using Polar Codes / H. Mahdavifar, A. Vardy // IEEE Trans, on Information Theory. — 2011. — Oct. - Vol. 57, no. 10. - P. 6428-6443.

120. Mori, R. Performance and construction of polar codes on symmetric binary-input memoryless channels / R. Mori, T. Tanaka // Proceedings of the IEEE International Symposium on Information Theory (ISIT'09), Jun 28—Jul 3, 2009, Seoul, Republic of Korea. Piscataway, NJ, USA: IEEE. - 2009. -P. 1496-1500.

121. Mori, R. Non-binary polar codes using Reed-Solomon codes and algebraic geometry codes / R. Mori, T. Tanaka // Proc. IEEE Information Theory Workshop (ITW). — 2010. — P. 1-5.

122. Mori, R. Performance of polar codes with the construction using density evolution / R. Mori, T. Tanaka // IEEE Commun. Letters. - 2009. - Jul. - Vol. 13, no. 7. -P. 519-521.

123. Natalin, A.B. The Method of Theoretic Estimation of BER of ML Receiver for Binary Coded Systems with Square QAM / A.B. Natalin, A.B. Sergienko // Proc. IEEE Int. Conf. on Communications (ICC2006), Istanbul. - 2006. -11-15 June.-Vol.3.-P. 1206-1211.

124. Pamuk, A. An FPGA implementation architecture for decoding of polar codes / A. Pamuk // 8th International Symposium on Wireless Communication Systems (ISWCS). - 2011. - Nov. - P. 437-441.

125. Peng, X.H. Erasure-control Coding for Distributed Networks / X.H. Peng // IEE Proceedings on Communications. - 2005. - Vol. 152. - P. 1075-1080.

126. Sarkis, G. Systematic encoding of polar codes for list decoding / G. Sarkis, W.J. Gross // private communication. - 2011.

127. Sasoglu, E. Polarization for arbitrary discrete memoryless channels / E. Sasoglu, E. Telatar, E. Arikan // Proc. IEEE Information Theory Workshop ITW. -2009. P. 144-148.

128. Sudan, M. Decoding of Reed-Solomon Codes Beyong the Error-Correction Bound / M. Sudan // J. Complexity. - 1997. - Dec. - Vol. 12. - P. 180-193.

129. Tal, I. List decoding of polar codes /1. Tal, A. Vardy // IEEE Int. Symp. Inf. Theory (ISIT). - 2011. - August.

130. Tal, I. How to construct polar codes /1. Tal, A. Vardy // IEEE Trans. Inform. Theory. - 2013. - October. - Vol. 59, no. 10. - P. 6562-6582.

131.Taghavi, M.H. Adaptive methods for linear programming decoding / M.H. Taghavi, P.H. Siegel // IEEE Trans. Inform. Theory. - 2008. - December. - Vol. 54, no. 12.-P. 5396-5410.

132. Tanner, M. A Recursive Approach to Low Complexity Codes/ M. Tanner // IEEE Trans. Inform. Theory. - 1981. - V. 27. № 5. - P. 533-547.

133. Trifonov, P. Efficient design and decoding of polar codes / P. Trifonov // IEEE Transactions on Communications. - 2012. - November. - Vol. 60, no. 11. - P. 3221-3227.

134. Ungerboeck, G. Channel coding with multilevel-phase signals / G. Ungerboeck // IEEE Transactions on Information Theory. - 1982. - Jan. - Vol. IT-28, no. l.-P. 55-67.

135. Viterbi, J. Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm / J. Viterbi // IEEE Trans. Information Theory. - 1967. -Apr. - V. IT - 13. - P.260-269.

136. Zhang, X. Adaptive cut generation algorithm for improved linear programming decoding of binary linear codes / X. Zhang, P.H. Siegel // IEEE Trans. Inform. Theory. - 2012. - October. - Vol. 58, no. 10. - P. 6581-6594.

Приложение А Защита номера кластера путем циклических отчетов

Двоичный циклический (п,к) - код обычно представляется порождающим полиномом вида

£(*) = К_к • х"~к + Ъп_к_х • х"-к~1 +...+¿о, где Ь,- - коэффициенты из GF(2). Весовой спектр IV такого кода симметричен относительно участка спектра комбинаций с максимальным весом для прямого кода и минимальным весом для дуального кода. Прямой код образуется с использованием полинома g(x), а комбинации дуального кода формируются с использованием проверочного полинома И(х). Если известно число комбинаций веса / для прямого кода, то число комбинаций дуального кода веса у = л — / оказывается аналогичным, т.е. С учетом нулевого и

единичного элементов мультипликативной группы спектр IV может быть представлен как

..........И^)».»}

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

Преобразуя двоичную форму кодового вектора У2 = 00101... в виде чисел в восьмеричной системе счисления У8= 125..., получают наглядную линейку представителей весов и их циклических сдвигов. На рисунке А.1 показан пример распределения характерных чисел для кода БЧХ (15,5,7). В таком коде всего четыре образца комбинаций

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

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

различным числом шагов. Кластер О

000000000000000

2524136537 640 0 1

524 136537 64 0 0 1 2

' 11I5 2 5 3 6 4 1 240 1 3

Кластер 1

0 13 77 5 2 5 3 6 шниини 4 124

24136537640 0125

5 3 7 640 0 12 5 2 4 13 6

7 6 5 2 5 3 641240137

Кластер 2

1 3 7 7 6 5 2 5

3 6 5 3 7 64 0 0 12 5 2 4 1

4 1 3 6 5 3 716 4 010 1 2 5 2

64 1240 13 Щб|5 2 511

Кластер 3

1 2 4 0 1 3 7 7 6 5 2 5 3,64

37 6400125241365

40 01252413653 7|б

6 52 5 36412401377

Кластер 4

12524136537

3 7 76

52 5

4 0 1 3 7 7Ь 65 3 71640

64 0

0

3 6412401 364 1 2

5 2 5

0 12 5 2 4 13

Кластер 5

13 6 5 3 7 64 0 0 12 5 24

3 64 э и ч 124 7 7 Л 5 2 5

4 1 24 01 3 7 7 б|5 2 5 3 6

|б 4 0 012541366537

Кластер 6

012524136537

240 1 3,776 ^364124013

01252413653

64 0

Кластер 7

0]0 1 2 5 2 4 1 3 6 5 3 7[бТ 25]3 6 4 12 4 0 13 7 7б]Т 5 2 5|3 6 4 12 4 0 13 7 7 6 777777777777777

Рисунок А. 1 - Характерные числа прямого (светлый фон) и дуального (серый фон) кодов для

кода БЧХ (15,5,7)

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

Рисунок А.2 - Алгоритм декодирования ПК с циклическими перестановками в процедуре

проверки номера кластера