Исследование сигнально-кодовых конструкций на основе обобщенных кодов с локализацией ошибок тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Кобозева, Ирина Геннадьевна

• Кобозева, Ирина Геннадьевна
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Кобозева, Ирина Геннадьевна

Оглавление

Введение

Обзор литературы

Глава 1. Обобщенные коды с локализацией ошибок. Оценка кодового расстояния для ОЛО-2 кодов

1.1. Введение

1.2. Кодирование и декодирование JlO-кодами

1.3. Кодирование ОЛО-2 кодами

1.4 Декодирование ОЛО-2 кодами

1.5 Нижняя оценка кодового расстояния

1.6 Выбор параметров кода, обеспечивающих максимальное кодовое расстояние

1.7 Теоретические оценки для вероятности неправильного декодирования для ОЛО-2 кодов

1.8 Задача выбор оптимальных параметров для ОЛО-2 кода

1.9 Оценка количества шагов для ОЛО-2 кодов

1.10 Выводы

Глава 2. Анализ вероятностных характеристик ОЛО-2 кодов

2.1. Введение

2.2. Используемые каналы передачи

2.3. Результаты моделирования для ОЛО-2 кодов

2.4. Передача закодированной ОЛО-2 кодами информации по гауссовскому каналу

2.5. Передача закодированной ОЛО-2 кодами информации по частотно-позиционному каналу

2.6. Передача закодированной ОЛО-2 кодами информации по каналу с модуляцией С^АМ

2.7. Выводы

Глава 3. Трехмерные обощенные коды с локализацией ошибок. Оценка кодового расстояния для ОЛО-3 кодов

3.1. Структура ОЛО-3 кодов

3.2. Кодирование ЛО-3 кодами

3.3. Декодирование ЛО-3 кодов

3.4. Алгоритм кодирования ОЛО-3 кодами

3.5. Алгоритм декодирования ОЛО-3 кодов

3.6. Выбор параметров кода, обеспечивающих максимальное кодовое

расстояние

3.7 Теоретическая оценки для вероятности неверного декодирования для ОЛО-3 кодов. Выбор параметров кода

3.8. Задача выбора оптимальных параметров для ОЛО-3 кодов

3.8. Оценка сложности вычислений

3.9. Выводы

Глава 4. Анализ вероятностных характеристик ОЛО-3 кодов

4.1. Результаты моделирования для ОЛО-3 кодов

4.2. Передача закодированной ОЛО-3 кодами информации по гауссовскому каналу

4.3. Передача закодированной ОЛО-3 кодами информации по частотно-позиционному каналу

4.4. Передача закодированной OJIO-3 кодами информации по каналу с модуляцией QAM

4.5. Выводы

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

Список литературы

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

Введение

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

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

1 9

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

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

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

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

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

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

• разработка алгоритмов кодирования/декодирования ОЛО-3 кодов;

• разработка методов выбора оптимальных параметров для ОЛО-2 и ОЛО-3 кодов, позволяющих найти код с максимальной скоростью передачи при заданных входной и выходной вероятностях ошибки.

Научная новизна работы

• Предложена модификация обобщенных кодов с локализацией ошибок — а именно, трехмерные обобщенные коды с локализацией ошибок.

• Для трехмерных обобщенных кодов с локализацией ошибок были разработаны алгоритмы кодирования и декодирования.

• Разработан теоретический метод расчёта вероятности неправильного декодирования для ОЛО-2 и ОЛО-3 кодов, позволяющий выбрать оп-

6

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

оценить вероятность неправильного декодирования для хороших уело-

12

вий передачи(<10~ ), что было бы крайне затратно при моделировании. • Было проведено моделирование в среде МАТЬАВ нескольких сигналь-но-кодовых конструкций на основе ОЛО-2 и ОЛО-3 кодов. Было произведено сравнение полученных результатов друг с другом и с некоторыми ныне существующими стандартами.

Теоретическая и практическая значимость работы

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

На защиту выносятся следующие основные результаты и

положения:

• Разработка теоретических методов расчета и оптимизации конструкций ОЛО-2 кодов на основе кодов Рида-Соломона для заданной вероятности неверного декодирования;

• Разработка конструкций ОЛО-3 кодов и оценка их параметров;

• Разработка теоретических методов расчета и оптимизации конструкций ОЛО-3 кодов на основе кодов Рида-Соломона для заданной вероятности неверного декодирования;

• Разработка алгоритмов кодирования/декодирования для рассматриваемых кодовых конструкций.

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

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

• XII симпозиум по проблеме избыточности в информационных системах, г. Санкт-Петербург, 2009 г.

• Конференция «Информационные технологии и системы» (ИТиС'09),

32-я конференция молодых ученых и специалистов И1111И РАН, п. Бека-сово, 2009 г.

• Конференция «Информационные технологии и системы» (ИТиС'Ю),

33-я конференция молодых ученых и специалистов ИППИ РАН, г. Геленджик, 2010 г.

• Конференция «Информационные технологии и системы» (ИТиС'11),

34-я конференция молодых ученых и специалистов ИППИ РАН, г. Геленджик, 2011 г.

• Конференция «Информационные технологии и системы» (ИТиС'12),

35-я конференция молодых ученых и специалистов ИППИ РАН, г. Петрозаводск, 2012 г.

Кроме того, результаты работы неоднократно докладывались на научных семинарах лаборатории №3 ИППИ РАН.

Структура и объем диссертации

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

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

Во второй главе проводится исследование вероятностных характеристик некоторых сигнально-кодовых конструкций на основе ОЛО-2 кодов (с использованием кодов Рида-Соломона) для различных типов каналов передачи данных. В этой главе проводится сравнение результатов моделирования с полученными ранее теоретическими оценками.

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

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

Общий объем диссертации 100 страниц, включая 47 рисунков. Библиография включает 37 наименований на 4 страницах.

Публикации

По теме диссертации опубликовано 3 статьи в рецензируемых отечественных и международных журналах [1-3], 5 тезисов докладов на конференциях [4-8]. Личный вклад соискателя в опубликованные работы является определяющим. Результаты, выносимые на защиту, получены автором самостоятельно. Все представленные в диссертации результаты получены лично автором.

Обзор литературы.

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

В 70-80 гг. XX века Э. Л. Блохом и В. В. Зябловым был выпущен ряд публикаций, посвященных различным конструкциям обобщенных каскадных кодов, в том числе, и с локализацией ошибок [9, 13, 17, 19].

После этого в развитии кодов с локализацией ошибок наступил длительный перерыв длившийся более десятилетия. Начиная с 1999 г., такие ученые, как М. Боссерт, В. В. Зяблов, Р. Кларер, X. Гриссер, Дж. Маухер снова начали развивать это направление. В течение нескольких лет ими были представлены публикации и доклады на различных международных конференциях по этой теме [11, 12, 20, 21, 22, 23].

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

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

Глава 1

Обобщенные коды с локализацией ошибок. Оценка кодового расстояния для ОЛО-2 кодов.

1.1 Введение

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

1.2 Кодирование и декодирование ЛО-кодами

В этой главе мы рассматриваем более простой случай кодов с локализацией ошибок - двумерные обобщенные коды с локализацией ошибок (далее обозначены как ОЛО-2 коды). Порядок ОЛО-2 кода т определяет количество используемых при кодировании внутренних и внешних кодов. Самым простым вариантом ОЛО-2 кода будет код порядка 1, или, иначе, ЛО-2 код. Рассмотрим кодирование и декодирование ЛО-2 кодами. Вначале мы заполняем большую часть матицы Е, изображенной на рисунке 1.1, размеров п = пАпв информационными символами, а ближний правый угол, отведенный для проверочных символов, пока заполняется нулями. Затем, умножая вертикальные столбцы матрицы Е на проверочную матрицу Нв внутренних кодов, мы вычисляем синдромы ошибки, которые образуют матрицу Е. При этом

символы, соответствующие ранее заполненной нулями части матрицы Е, пе-

13

реходят в проверочные символы внутреннего кода. Проверочная матрица внутреннего кода имеет вид Нв где 1Гв - единичная матрица разме-

ров гвхгв. Из проверочной части матрицы Е' мы убираем все проверочные символы внутренних кодов, заменяя их нулями. Оставшиеся синдромы иа), в свою очередь, можем рассмотреть как информационные символы внешнего кода над полем СЕ{дГс), с помощью которых мы можем вычислить проверочные символы Лт для внешнего кода.

Таким образом, получаем что

/-(о

Е' = (ит | Ят) = Нв ■ Е = (& | /,в )(£(1) | .

Далее, нетрудно вычислить проверочные символы собственно ЛО-2 кода: = £вс(1) + 1гРт Р(1) = - £ЯС(1).

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

1.3 Кодирование ОЛО-2 кодами

Проверочная матрица внутренних кодов ОЛО-2 кода имеет вид

гн оп 11 в /(1) 0 ... 0 ^

Нв = Н(2) 11 в = ф ф ¡(1) 0 0

Н{1) \пв ••• ей л

где Ь -количество внешних А и внутренних В кодов, где единичные матрицы, а некоторые матрицы с элементами из СР(д), / = = 0,£-1.

»в J—»/11 t

pljl

Га

£ т'1' R"

Рис. 1.1 Порядок кодирования ЛО-2 кодами.

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

ГВ ~ ПВ ~~ кв •

Далее, каждый из г(Ап подблоков длины ккодируется внутренним кодом Рида-Соломона с параметрами (пв к^ ,с/д}). В результате получаем гА

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

Затем для каждого из первых к(А подблоков матрицы Е длины пв находим вектор длины Гд° = пв -кЦ) по формуле ^ = у^)Нд)Т, где Н- прове-

15

рочная матрица кода /'-ой ступени в приведённо-ступенчатой форме, а - ¡и-ый подблок. Представляя векторы =1,...,кА, как элементы ОР(Т* ), получаем вектор из к^ символов над СР(2Г® ) и кодируем его внешним кодом Рида-Соломона с параметрами (. В результате получаем кодовое слово внешнего кода.

В конце, так же, как и для ЛО-2 кодов найдем проверочные символы собственно ОЛО-2 кода. Таким образом,

Е'<''> = (и(/) | Л<") = Я= | / „, )(Е<» |

в "

я(/) = +/ и)р(0 => Ри) = р0) -(^...о^ся

гв

"л

Е

Е'4'

С

Е"

С1

К

К-

К

<.1*1

г

р4'

г,1> 'в

' 141

гв

Рис. 1.2. Структура ОЛО-2 кода.

1.4 Декодирование ОЛО-2 кодами

Декодирование ОЛО-кода осуществляется в несколько этапов, количество которых равно порядку ОЛО-кода т. При передаче по каналу с шумом к кодовому слову ОЛО-кода С добавляется некоторая ошибка Е. Таким образом, полученная комбинация Ех задается как Ех = X Ф Е. В начале декоди-

рования вычисляются синдромы соответствующего данному шагу внутреннего кода, необходимые для определения символов внешнего кода 5(0 = НВ{,)ЕХ, после чего происходит декодирование соответствующим внешним кодом, в результате которого получаем я0) = Н В]Е.

Предполагая, что декодирование внешним кодом было успешным, находим столбцы матрицы Е Ъ} , считая что.?/0 = н}{)Ъ] .

На /-ом шаге мы комбинируем синдромы ^ / , полученные на шаге I, с

- (£) - ('+1)

синдромами .У/ , полученными на предыдущих шагах, и декодируем

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

(н(,)Л

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

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

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

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

Проверочную матрицу ОЛО-2 кода можно представить в виде:

' н(Р®н ил

НЕ =

нш ® н Ш

V А

, то есть

ГЛ >' ГЛ г,1 > ,пл ° у

где

о _ соответствующие элементы матрицы Н(А .

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

1.5 Нижняя оценка кодового расстояния

В рассматриваемом случае в качестве внутренних и внешних кодов выступают коды Рида-Соломона. Это МДР-коды, соответственно, для них выполняется соотношение <1 = п-к+1. Таким образом, величина 8{К) = <Ип может быть представлена как б{К) = {п-к+\)1 п = \-Я + \/п, где Я-к/п — скорость передачи. Пусть ^ - кодовое расстояние ОЛО-2-кода длины й - папь. Обозначим через 8{^(Я,т) нижнюю оценку для заданной скорости передачи Я ОЛО-2-кода при его порядке, равном т. Запишем скорость передачи для ОЛО-2-

Рис. 1.3. Декодирование ОЛО-2 кодом.

кода как

нЛЛ

п п

г

т т

/=1 ¡=1

=1 ■-1 - )+х (- к ж, =

/=1 /=1 т

<=1

где а, - количество проверочных символов /-го внешнего кода, а Ь, - количество проверочных символов внутреннего /-го кода, Яы - скорость передачи данных для вложенных внутренних кодов, Яьо = 1.

Нижнюю оценку для /'-ого шага запишем в следующем виде:

= (1 - Яа, + —)(1 - Яы + —) .

В данной работе мы рассматриваем фиксированные значения кодового

расстояния для вложенных внутренних кодов: с1м =2,с1Ь1 =3,...,с1Ьт =т + \, то

19

есть все внутренние коды имеют параметры (пь, пь-1, 2). Таким образом, получаем, что Яы =1—— ,г =1,..,т, а Ь, = /. Подставляя эти значения в выражения

пъ

для нижней оценки и скорости передачи ОЛО-кода, получаем

ПЬ Па

т 1

,=1 п.

ъ

д(н)п 1

Выразим Я через 6{"] как Яш-1 —'-—- + —, тогда полненные выраже-

/41 па

ния приобретут следующий вид:

«=1 ПЬ »' + 1 па 0' + 1К

¿Г (1 + 1) л

Таким образом, мы получили зависимость скорости передачи ОЛО-кода от величин ¿,(н). Запишем нижнюю оценку кодового расстояния для ОЛО-кода как

=тт {д?\Я,т)).

1.6 Выбор параметров кода, обеспечивающих максимальное кодовое расстояние.

Как результат, из предыдущего пункта получаем, что если мы хотим получить код с максимально возможным кодовым расстоянием, то естественным требованием является условие =<52(н) = обеспечивающее

максимальное значение . Любое ограничение, налагаемое на величины ¿(<и), связывающие величины Яа1 и ЯЬ1, представляет собой ограничение на структуру ОЛО-кода, которая определяется распределением скоростей передачи внутренних и внешних кодов.

Рис. 1.4. Зависимость S}H) от скоростей передачи внешних и внутренних кодов для п=64.

На рис. 1.4. изображена зависимость S'H> от скоростей передачи внешних и внутренних кодов. Разноцветные кривые на графике внизу - те значения Rai и Rhj при которых S\H) = const, то есть выбирая значения скоростей вдоль этих кривых мы получим ОЛО-2 код с максимальным (среди кодов одного и того же порядка т для заданной общей скорости передачи данных) кодовым расстоянием.

1.7 Теоретические оценки для вероятности неправильного декодирования для ОЛО-2 кодов

В начале каждого шага производится обнаружение ошибок с помощью внутреннего кода. Будем считать, что обнаружение ошибок для кода Рида-Соломона происходит, только если выполняется неравенство е+т<4-1, хотя, на самом деле, таких случаев больше. Затем производится исправление ошибок и стираний. Поскольку на каждом следующем шаге кодирование осу-

21

ществляется при помощи кода Рида-Соломона, то для успешного декодирования необходимо выполнение неравенства 2e+x<d-l. Если же при исправлении ошибок и стираний при избыточности d на текущем шаге, произошла ошибка декодирования, то на следующем шаге при избыточности d+1 ошибки будут обнаружены, только в том случае, если e+z=d.

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

рисправ.=z с>; Ё cn-tpi а -Ре- Pt т"е+z о; (1 - Р, г

t=0 e=f(rf-/)/2] t=d

/=0 e=d—t l=d

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

Peras=PB(e = 0..n-t,t>0) =

=s о: £ а -Ре~ р, у-,

1=1 е=0

Perr =PB(e>0,t = 0) = ¿ада -А - Л)"-*.

е=1

На самом первом этапе происходит декодирование первым внешним кодом A(L). При этом вероятность ошибки будет выглядеть как

d[A)-1 n-l п

p(L) _ у Qtpt "у yje ре (1_р _р у-'-е , К^1 Qt р> (Л _ р Л"~<

Aerr ^^d п eras ^^ n—t err У err eras' / л п eras У eras' '

'=0 e=\(di-t)/2 ] t=d

а вероятность правильного декодирования следующего внешнего кода можно представить как (1 - P^l )0 - (Рв+ У" )рлГУ)> гДе рл1~[) ~ вероятность правильного декодирования L-1 внешнего кода при условии, что предыдущий внешний код был декодирован верно, но при этом в кодовом слове еще остались какие-то ошибки и стирания. Необходимо отметить, что структура OJIO-кода такова, что если хотя бы один из внешних кодов будет декодирован неверно,

то неверно декодирован будет весь ОЛО-код. Дополнительную сложность в оценку вносит тот факт, что после использования каждого следующего внешнего кода, вероятность ошибки ре и вероятность стирания р( изменяется. Используемый на первом шаге внутренний код с расстоянием ¿/¿=2 может обнаружить одну ошибку в столбце кодового слова ОЛО-кода, или исправить одиночное стирание. Вероятность обнаружения ошибки первым внутренним кодом запишем как

Р£гI =Рв(е = и = 0) = С\ре{\-Ре ~Р,у-\

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

= Рв Се = О,* = 1) = С>, (1 -Рл- р, Г1.

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

=рв(е> и=1>=с>, х с:_хР: (1-Ре- Р, у'-е.

е=1 - -

Таким образом, вероятности стирания и ошибки в символах второго внешнего кода будут выглядеть следующим образом: =Рв(е>и = 1) + Рв(е*2,( = 0) =

с\Р, е с:_хР: а - Ре - Р, г1- + ± с>: ц-Ре- Р, ге,

е=1 е=2

=Рв(е = 0,1>2) + Рв(е = и = 0) =

±СпР\(1-Ре-р,)"-' + С\р\(1 -р, -р,)"-'.

1=2

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

4-1 »

р(£-1) _ Х-1 с' "V Се — Р^ _ рШу-'-е I Х"1 /">' —

ГАегг ~ п В( Аи п—1 Ве V1 гВе ГВ1 ) пГВ1 V1 ГВ1 )

'=° е=[К.-/)/2]

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

=PB(e = 2,t = 0) + PB(e = l,t = l) = С2„Реа~Ре ~Р,У2 + clP,cl-iPlО -Ре ~Р,Т2,

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

PbL+'1) = Рв о = °>' = 2) + рв (е = 1» t = 0) =

= С2„р? (1 -Ре- р, г2 + С\Р\ (1-ре- р, у-1.

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

=PB{e>\,t = 2) = С2р,2XCl2pl(1 -р, -ptу-2-е.

е=1

Запишем вероятности стирания й ошибки в символах третьего внешнего кода как

Pi1'1' =PB(e>l,t = 2) + PB(e>2,t = l) + PB(e>3,t = 0) =

CIp] z c:_2pi (i - Pe - p, y-2- +

e=l

+c\P, jr cup: a -p.- pt r-1 + Z a -Pe- p, ye,

e~2 e=3

Pb"~1) =PB(e = 0,t>3) + PB(e = 2,t = 0) + PB(e = l,t = l) =

s c>; (1 - Pe - p,)"-' + c2p2 (1 - p, - p, Г2 +

t=3

+cinplcllpUi-pe-pty-2.

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

р(£-2) _ Х"4 rt p{L-\)t ^ ^е p(L~\)e n _ р(Л-1) _ p(¿-l)yí-í-e 1 Aerr Bt n—t Be V1 ^Be 1 Bt ) "r

'=0 e=[KV')/2]

+ Ё c^^d-^r.

'=d¿-2

Таким образом, мы видим, что для z-oro шага вероятности стирания и ошибки в символах соответствующего внешнего кода записываются как рв'е = PB(t = {d, -1,..,0},е > d, -t), Р^ =PB(e = 0,...,n-t,t>dl) + PB(e + t = d,-l).

Соответственно, общая формула для i+1-то внешнего кода при условии, что все предыдущие были верно декодированы, выглядит следующим образом:

1 »-'

р('+>) _ X"1 p(i)t V Се р0)е П _ рО) _ р0)\"-'-е ,

Aerr — п Bt ¿_j n—t Be V1 rBe Г Bt ' "r

1=0 H"K-0/2l

i

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

Список литературы диссертационного исследования кандидат наук Кобозева, Ирина Геннадьевна, 2013 год

Список литературы

1. Кобозева И. Г., Зяблов В. В., "Оценка вероятности неправильного декодирования обобщенных кодов с локализацией ошибок", "Информационно-управляющие системы", 2013, №1, стр. 47-53

2. Кобозева И. Г., Зяблов В. В., " Исследование сигнально-кодовых конструкций на основе трехмерных кодов с локализацией ошибок", "Информационные процессы ", 2013, №1, стр. 1-18

3. Kobozeva I. G., Zyablov V. V., "Investigation of Signal- Code Structures Based on 3D Error-Locating Codes", Journal of Communications Technology and Electronics, 2013, Vol. 58, No. 6, pp. 648-660.

4. Kobozeva I., Zyablov V., "Using GEL Codes for Optical Channel", труды XII симпозиума по проблеме избыточности в -информационных системах, 2009, с. 126-129

5. Кобозева И. Г., Зяблов В. В., "Декодирование обобщенных кодов с локализацией ошибок", труды конференции ИТИС'09, с. 170-174.

6. Кобозева И. Г., Зяблов В. В., "Декодирование трехмерных обобщенных кодов с локализацией ошибок", труды конференции ИТИС'10, с. 99-103.

7. Кобозева И. Г., Зяблов В. В., "Комбинаторные оценки кодового расстояния для OJIO-кодов", труды конференции ИТИС'11, с. 123-126.

8. Кобозева И. Г., Зяблов В. В., "Кодирование трехмерными обобщенными кодами с локализацией ошибок", труды конференции ИТИС'12, с. 129132.

9. Блох Э. Л., Зяблов В. В., "Линейные каскадные коды", М.: Наука, 1982, 230 с.

10.Зяблов В. В. "Новая трактовка кодов для локализации ошибок, их корректирующие свойства и алгоритмы декодирования", М.: Наука, 1972, 10 с.

11.Fahrner A., Griesser H., Klarer R., Zyablov V.V., "Low-complexity GEL codes for digital magnetic storage systems", IEEE Transactions on Magnetics, volume 40(4), July 2004, p. 3093 - 3095

12. Fahrner A., Griesser H., Klarer R., Zyablov V.V., "Generalized GEL codes for

th

digital magnetic storage systems", 5 ITG Conference on Source and Channel Coding, January 2004, p. 219-226

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

14. Афанасьев В. Б., Габидулин Э. М., "Кодирование в радиоэлектронике", М.: Радио и связь, 1986, 176 с.

15. Некучаев, А. О., Зяблов В. В., "Проект "Континент" - новый подход для передачи данных по магистральным ВОЛС", Фотон-Экспресс, 2008, N 3, с. 40-42

16.,Галлагер Р., "Теория информации и надежная связь", М.: "Советское радио", 1974, 720 с.

17. J. К. Wolf, В. Elspas., "Error-Locating Codes - A New Concept in Error Control", IEEE Trans. On Information Theory, IT-9, N 2, 1965

18. J. K. Wolf, "On an Extended Class of Error-Locating Codes", Information and Control, N 8, 1965

19.Zheng Wu, "Channel Modeling, Signal Processing and Coding for Perpendicular Magnetic Recording", PhD Thesis, University of California, 2009, 122 p.

20.Zyablov V., Maucher J., Bossert M. "On the equivalence of generalized concatenated codes and generalized error location codes", IEEE Transactions on Information Theory, volume 46(2), March 2000, p. 642-649

21. Bossert M., Griesser H., Maucher J., Zyablov V., "Some Results on generalized concatenation of block codes", Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, vol. 1719 of Lecture Notes in Computer Science, 1999, p. 181-190

22. Bossert M., Griesser H., "On the decoding of the generalized error locating codes", proc. of 3rd ITG Conference on Source and Channel Coding, 2000, p. 209-214

23. Зяблов B.B., Шавгулидзе С. А., "Обобщенные каскадные помехоустойчивые конструкции на базе сверточных кодов", Наука, 1991, 207 с.

24.Зяблов В. В., Коробков Д. Л., Портной С. Л., "Высокоскоростная передача информации в реальных каналах", Радио и Связь, 1991, 288 с.

25.Э. Л. Блох, В. В. Зяблов, "Кодирование обобщенных каскадных кодов", Проблемы передачи информации, 10:3 (1974), с. 45-50

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

27. Берлекэмп Э., "Алгебраическая теория кодирования", М.: Мир, 1971, 477 с.

28. Лидл Р., Нидеррайтер Г., "Конечные поля", М.: Мир, 1988, т. 1-2, 818 с.

29. Bossert М., "Channel Coding for Telecommunication", Wiley, 1999, 495 p.

30.Шеннон К. Э. " Математическая теория связи ", пер. С. Карпова, М.: ИИЛ, 1963,830 с.

31.V. Guruswami and М. Sudan, "Improved decoding of Reed-Solomon and algebraic geometry codes," IEEE Trans. Inf. Theory, vol. 45, 1999, pp. 1757-1767

32. Питерсон У. У, Уэлдон Э. Дж., "Коды, исправляющие ошибки", М.: Мир, 1976, 594 с.

33. Сагалович Ю. Л., "Введение в алгебраические коды", М.: ИППИ РАН, 2010, 302 с.

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

35. Скляр Б., "Цифровая связь. Теоретические основы и практическое применение" , 2 изд., М.: «Вильяме», 2007, 1104 с.

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

37. Феллер В., " Введение в теорию вероятностей и ее приложения", Т. 1, М. Мир, 1984, 498 с.