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

Министерство образования и науки Российской Федерации МОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ (ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ)

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

КОБОЗЕВА ИРИНА ГЕННАДЬЕВНА

Исследование сигнально-кодовых конструкций на основе обобщенных кодов с локализацией ошибок

05.13.17 - Теоретические основы информатики

Г:

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

005541953

Москва-2013

005541953

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации

По теме диссертации опубликовано 3 статьи в рецензируемых отечественных и международных журналах [1- 3], 5 тезисов докладов на конфе-

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

Содержание работы

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

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

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

пв 'ф /(,) 0 ... 0 4

н,= Н (2) пв = ф ор1 /<г> 0 0

\пв

где Ь -количество внешних А и внутренних В кодов, где /'''— единичные матрицы, а о!'1 некоторые матрицы с элементами из ОР(ц), / = \1,] = 0,£-1. Алгоритм кодирования ОЛО-2 кодами

Вначале информационные символы записываются в левую часть матрицы Е, изображенной на рис. 1, в правую часть записываются нули.

1. Информационные символы разбиваются на пА подблоков, из которых к^> первых подблоков имеют длину пв, а г^ оставшихся - длину гЦ* =пв- .

2. Каждый из л*" подблоков длины к^ кодируется внутренним кодом Рида-Соломона с параметрами (пЙкЦ],с/'11>). В результате получаем гА векторов

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

3. Для каждого из первых к™ подблоков матрицы Е длины пв находим вектор длины г'^ =ил-А4°по формуле где Я« - проверочная матрица кода /-ой ступени в приведённо-ступенчатой форме, а v^■^¡,) - ¿ц-ый подблок. Представляя векторы л", ^ =1,...,кА, как элементы ), получаем вектор из к%' символов над С/Г(2Г»>) и кодируем его внешним кодом Рида-Соломона с параметрами . В результате получаем кодовое слово внешнего кода. Затем находим проверочные символы собственно ОЛО-2 кода.

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

£'"> = (и10 |. д">) = = (бГ-бй I 1

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

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

Лемма 1. Количество операций при декодировании ОЛО-2 кода можно оценить как

N = 1ое(?)|сЛия \о£(пв)+Слплгвт \0&\пл)+пАпв^г^

где СА и Св - некоторые коэффициенты, явным образом не зависящие от длины кода.

Доказательство. В случае ОЛО-2 кодов на каждом шаге декодирования происходит исправление ошибок и стираний при помощи внешнего кода длины п, над полем СЯХ^*'), что дает нам 1ов(<7'»'")• сЦ' ■ пА ■ ) операций, после этого, имеет место исправление и обнаружение ошибок пл внутренними кодами длины пв над полем что дополнительно прибавляет нам

I.

^гс,' ^(д)-«., -ла («„) операций. Кроме того, для вычисления синдромов

1=1

нам необходимо умножатьпл векторов на проверочные матрицы размеров

13

вания + ошибки от отношения сигнал/шум на бит в канале для ОЛО-2 (4096, 3973), т = 12 избыточностью 3% при передаче по гауссовскому каналу. Все параметры кода выбраны в соответствии с описанными выше теоретическими методами. Кружочками обозначены результаты теоретических расчетов, квадратами - результаты моделирования. Для сравнения на этом же графике также изображена теоретическая оценка зависимости вероятности отказа от декодирования + ошибки для кода Рида-Соломона с параметрами (64, 63, 3), имеющего ту же избыточность. Как мы можем убедиться, при вероятности ошибки 10"12 выигрыш ОЛО-2 кода по сравнению с кодами Рида-Соломона составляет более 3,5 дБ.

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

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

ний код Л<0 с параметрами где п - длина кода, к"'и г"1- ко-

личество информационных и проверочных символов соответственно, а с1") -кодовое расстояние. Для примера, структура кодового слова обобщенного трехмерного кода с локализацией ошибок (далее обозначенного как ОЛО-3 код) порядка 4 представлена на рис. 3.

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

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

Министерство образования и науки Российской Федерации МОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ (ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ)

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

04201365704

КОБОЗЕВА ИРИНА ГЕННАДЬЕВНА

Исследование сигнально-кодовых конструкций на основе обобщенных кодов с локализацией ошибок

Специальность 05.13.17 - теоретические основы информатики

ДИССЕРТАЦИЯ на соискание учёной степени кандидата физико-математических наук

Научный руководитель д. т. н. Зяблов В. В.

Москва-2013

Оглавление

Введение..................................................................................................................5

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

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

1.1. Введение..........................................................................................................13

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

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

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

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

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

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

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

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

1.10 Выводы...........................................................................................................29

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

2.1. Введение..........................................................................................................31

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

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

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

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

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

2.7. Выводы............................................................................................................59

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

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

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

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

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

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

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

расстояние..............................................................................................................70

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

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

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

3.9. Выводы............................................................................................................79

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

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

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

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

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

4.5. Выводы............................................................................................................94

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

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

Введение

История кодирования началась в 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

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