Содержание к диссертации
Введение
Глава 1. Обобщенные коды с локализацией ошибок. Оценка кодового расстояния для ОЛО-2 кодов 13
1.1. Введение 13
1.2. Кодирование и декодирование ЛО-кодами 13
1.3. Кодирование ОЛО-2 кодами 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 кодами информации по каналу с модуляцией QAM 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 кодами информации по частотно-позиционному каналу 4.4. Передача закодированной ОЛО-3 кодами информации по каналу с модуляцией QAM 90
4.5. Выводы 94
Основные результаты работы 96
Список литературы
- Кодирование ОЛО-2 кодами 1.4 Декодирование ОЛО-2 кодами
- Передача закодированной ОЛО-2 кодами информации по гауссовскому каналу
- Выбор параметров кода, обеспечивающих максимальное кодовое расстояние
- Передача закодированной ОЛО-3 кодами информации по гауссовскому каналу
Введение к работе
История кодирования началась в 1948 г. с публикацией знаменитой статьи К. Шеннона «Математическая теория связи». Шеннон показал, что с любым каналом передачи данных связано измеряемое в битах в секунду и называемое пропускной способностью канала число С. Если требуемая от системы связи скорость передачи информации R (измеряемая в битах в секунду) меньше С, то, используя исправляющие ошибки коды, для данного канала можно построить такую систему связи, что вероятность ошибки на выходе будет сколь угодно мала. В самом деле, понятно, что построение очень хороших каналов является сложной задачей; экономически гораздо выгоднее использовать кодирование. Шеннон, однако, не указал, как найти подходящие коды, а лишь доказал их существование.
С тех пор, течение более чем 60 лет, прошедших с момента появления кодов, исправляющих ошибки, наблюдается устойчивый рост требований к их корректирующим свойствам, и предлагаются новые, все более сложные кодовые конструкции. В последнее годы требования к качеству передаваемой информации еще более ужесточились (вероятность ошибки декодирования
порядка 10" и менее). Кроме того, из-за очень высокой скорости передачи данных необходимыми условиями также являются использование методов кодирования и декодирования, требующих относительно малое количество вычислений на бит передаваемой информации, а также возможность параллельных вычислений при кодировании и декодировании. В свою очередь, при высокой кратности модуляции, обеспечивающей большую скорость передачи, более целесообразно использовать недвоичные коды, которые имеют лучшую корректирующую способность по сравнению с двоичными кодами с той же избыточностью.
Можно выделить несколько классов кодов, позволяющих построить длинный код с хорошей корректирующей способностью. Обычно это каскадные коды или МПП-коды. Среди этих кодов особое место занимает подкласс
обобщенных каскадных кодов, а именно обобщенные коды с локализацией ошибок (далее обозначены как ОЛО-коды), которые и являются основным предметом исследований в данной работе. В работе будут исследованы две разновидности ОЛО-кодов - обычные ОЛО-коды (в дальнейшем, чтобы избежать путаницы, обозначены как ОЛО-2 коды) и их новая трехмерная разновидность (далее обозначены как ОЛО-3 коды).
Цели и задачи диссертационной работы
Цель диссертационной работы состоит в исследовании методов повышения защиты от помех и увеличения пропускной способности информационных коммуникаций с использованием кодов с локализацией ошибок. Существенной частью работы является исследование свойств кодов с локализацией ошибок, включая предложенную автором усложнённую трёхмерную версию, а также разработка методов, позволяющих аналитически определять оптимальные параметры для ОЛО-2 и ОЛО-3 кодов.
Для достижения поставленных целей были решены следующие задачи:
анализ существующих способов кодирования и декодирования обобщенными кодами с локализацией ошибок;
разработка алгоритмов кодирования/декодирования ОЛО-3 кодов;
разработка методов выбора оптимальных параметров для ОЛО-2 и ОЛО-3 кодов, позволяющих найти код с максимальной скоростью передачи при заданных входной и выходной вероятностях ошибки.
Научная новизна работы
Предложена модификация обобщенных кодов с локализацией ошибок - а именно, трехмерные обобщенные коды с локализацией ошибок.
Для трехмерных обобщенных кодов с локализацией ошибок были разработаны алгоритмы кодирования и декодирования.
Разработан теоретический метод расчёта вероятности неправильного декодирования для ОЛО-2 и ОЛО-3 кодов, позволяющий выбрать оптималь-
ные параметры кода для известного канала передачи, а также оценить вероятность неправильного декодирования для хороших условий переда-чи(<10" ), что было бы крайне затратно при моделировании.
Было проведено моделирование в среде MATLAB нескольких сигнально-
кодовых конструкций на основе ОЛО-2 и ОЛО-3 кодов. Было произведено
сравнение полученных результатов друг с другом и с некоторыми ныне
существующими стандартами.
Теоретическая и практическая значимость работы
Работа носит, в целом, теоретический характер. Теоретическая ценность диссертации определяется теоретическими методами оценки вероятности неправильного декодирования для ОЛО-2 и ОЛО-3 кодов, позволяющими выбрать подходящие параметры для избыточности каждого из кодов-компонентов. Данный вопрос является весьма существенным, так как ОЛО-коды позиционируются как коды с малой избыточностью, для которых важно рациональное использование каждого проверочного символа. Описанные в работе методы позволяют подобрать ОЛО-код с максимальной скоростью передачи при заданных входных вероятностях ошибки и стирания в канале и выходной вероятности неверного декодирования. На защиту выносятся следующие основные результаты и положения:
Разработка теоретических методов расчета и оптимизации конструкций ОЛО-2 кодов на основе кодов Рида-Соломона для заданной вероятности неверного декодирования;
Разработка конструкций ОЛО-3 кодов и оценка их параметров;
Разработка теоретических методов расчета и оптимизации конструкций ОЛО-3 кодов на основе кодов Рида-Соломона для заданной вероятности неверного декодирования;
Разработка алгоритмов кодирования/декодирования для рассматриваемых кодовых конструкций.
Апробация результатов работы
Основные результаты диссертации докладывались на следующих конференциях:
XII симпозиум по проблеме избыточности в информационных системах, г. Санкт-Петербург, 2009 г.
Конференция «Информационные технологии и системы» (ИТиС'09), 32-я конференция молодых ученых и специалистов ИППИ РАН, п. Бека-сово, 2009 г.
Конференция «Информационные технологии и системы» (ИТиС'10), 33-я конференция молодых ученых и специалистов ИППИ РАН, г. Геленджик, 2010 г.
Конференция «Информационные технологии и системы» (ИТиС'П), 34-я конференция молодых ученых и специалистов ИППИ РАН, г. Геленджик, 2011 г.
Конференция «Информационные технологии и системы» (ИТиС'12), 35-я конференция молодых ученых и специалистов ИППИ РАН, г. Петрозаводск, 2012 г.
Кроме того, результаты работы неоднократно докладывались на научных семинарах лаборатории №3 ИППИ РАН.
Структура и объем диссертации
Кодирование ОЛО-2 кодами 1.4 Декодирование ОЛО-2 кодами
На каждом шаге для соответствующего внутреннего кода происходит как обнаружение, так и исправление стираний и ошибок. Таким образом, если количество обнаруженных ошибок или число стираний в кодовом слове внутреннего кода превышает корректирующую способность этого кода, то для соответствующего этому слову символа внешнего кода выносится вердикт «стирание».
Если же в кодовом слове внутреннего кода, неверно исправленном на предыдущем шаге, на текущем шаге вновь будут обнаружены ошибки, то это слово становится таким, каким оно было на предыдущем шаге. В рассмотренном в работе случае восстановление прежнего значения происходит только в том случае, если ошибки обнаружены на следующем же шаге после неверного исправления, хотя, в принципе, возможен возврат и на несколько шагов назад. При декодировании на каждом следующем шаге используется информация о стертых символах, полученная на предыдущем шаге.
Аналогичные действия производятся на всех последующих шагах. Можно отметить, что при неправильном декодировании хотя бы одного внешнего кода, все последующие вычисления будут неверными, поэтому очень важно правильно подобрать избыточность внешних кодов.
Следует отметить, что используемое выше прямое кронекеровское произведение, строго говоря, является некоммутативной операцией, поэтому обязательно следует умножать матрицы в указанном порядке.
В рассматриваемом случае в качестве внутренних и внешних кодов выступают коды Рида-Соломона. Это МДР-коды, соответственно, для них выполняется соотношение d=n-k+l. Таким образом, величина 5{R) = d/n может быть представлена как S(R) = (n-k + l)In = l-R + l/n, где R = k/n — скорость передачи. Пусть d - кодовое расстояние ОЛО-2-кода длины d = папь. Обозначим через 8( {R,m) нижнюю оценку для заданной скорости передачи R ОЛО-2-кода при его порядке, равном т . Запишем скорость передачи для ОЛО-2 Вычисление синдромов L-oro внутреннего кода (символов L-ro внешнего кода) Декодирование L-ым внешним кодом Обнаружение и исправление ошибок и стираний L-ым внутренним кодом Вычисление синдромов L-1-ого внутреннего кода (символов L-1-го внешнего кода) ! Декодирование L-1-ым внешним кодом где я, - количество проверочных символов /-го внешнего кода, а bt - количество проверочных символов внутреннего /-го кода, Rhi - скорость передачи данных для вложенных внутренних кодов, Rh0 = 1.
Нижнюю оценку для /-ого шага запишем в следующем виде: В данной работе мы рассматриваем фиксированные значения кодового расстояния для вложенных внутренних кодов: dM=2,dh2=3,...,dhm=m + \, то есть все внутренние коды имеют параметры (щ, пь-1, 2). Таким образом, по лучаем, что Rb =1 ,i = l,..,m, а Ъ =i. Подставляя эти значения в выражения для нижней оценки и скорости передачи ОЛО-кода, получаем
Как результат, из предыдущего пункта получаем, что если мы хотим получить код с максимально возможным кодовым расстоянием, то естественным требованием является условие 5р = 52Си) =... = S, обеспечивающее максимальное значение 8 щ . Любое ограничение, налагаемое на величины S , связывающие величины Лш и Rbl, представляет собой ограничение на структуру ОЛО-кода, которая определяется распределением скоростей передачи внутренних и внешних кодов. Рис. 1.4. Зависимость Sj" от скоростей передачи внешних и внутренних кодов для п=64.
На рис. 1.4. изображена зависимость S.H) от скоростей передачи внешних и внутренних кодов. Разноцветные кривые на графике внизу - те значения Rai и Rbl при которых S\H) = const, то есть выбирая значения скоростей вдоль этих кривых мы получим ОЛО-2 код с максимальным (среди кодов одного и того же порядка т для заданной общей скорости передачи данных) кодовым расстоянием.
В начале каждого шага производится обнаружение ошибок с помощью внутреннего кода. Будем считать, что обнаружение ошибок для кода Рида-Соломона происходит, только если выполняется неравенство e+x d-l, хотя, на самом деле, таких случаев больше. Затем производится исправление ошибок и стираний. Поскольку на каждом следующем шаге кодирование осу ществляется при помощи кода Рида-Соломона, то для успешного декодирования необходимо выполнение неравенства 2e+r d-l. Если же при исправлении ошибок и стираний при избыточности d на текущем шаге, произошла ошибка декодирования, то на следующем шаге при избыточности d+1 ошибки будут обнаружены, только в том случае, если e+T=d.
Ниже приведены используемые для вычислений формулы вероятности неудовлетворительного исхода при исправлении и при обнаружении ошибок для кодов Рида-Соломона: а вероятность правильного декодирования следующего внешнего кода можно представить как (l--PJtr)(i-( i+))" )-pi+ 1) гДе РИ 1} - вероятность правильного декодирования L-1 внешнего кода при условии, что предыдущий внешний код был декодирован верно, но при этом в кодовом слове еще остались какие-то ошибки и стирания. Необходимо отметить, что структура ОЛО-кода такова, что если хотя бы один из внешних кодов будет декодирован неверно, то неверно декодирован будет весь ОЛО-код. Дополнительную сложность в оценку вносит тот факт, что после использования каждого следующего внешнего кода, вероятность ошибки ре и вероятность стирания р, изменяется. Используемый на первом шаге внутренний код с расстоянием dL=z2 может обнаружить одну ошибку в столбце кодового слова ОЛО-кода, или исправить одиночное стирание. Вероятность обнаружения ошибки первым внутренним кодом запишем как
Передача закодированной ОЛО-2 кодами информации по гауссовскому каналу
Вначале скажем несколько слов о выборе средств и платформы реализации ПО. В качестве средства реализации использовался язык программирования MATLAB. Основными преимуществами языка MATLAB являются: В этой главе будут проанализированы характеристики сигнально-кодовых конструкций на основе ОЛО-2 кодов. Ниже будут рассмотрены ОЛО-2 коды на основе кодов Рида-Соломона с длинами 16 и 64, для каждой длины были получены вероятности неверного декодирования для кодов с избыточностью 3, 5, 7, 10 и 20%. Будет проведено сравнение полученных в предыдущей главе теоретических оценок и результатов моделирования. Для каждого рассмотренного в главе ОЛО-2 кода было проведено сравнение с близким по избыточности кодом Рида-Соломона над тем же полем.
В работе рассматривается оптический канал передачи данных, передача по которому ведется на нескольких значениях частоты X. Будут исследованы случаи А=16 и А=8. Таким образом, за один символ будет передаваться 6, 4 и 3 бита соответственно.
Рассмотрим передачу на 8 X. При передаче одного символа по рассматриваемой ВОЛС за один такт передается только один единичный сигнал (сигнал, превышающий порог). Таким образом, мы имеем для восьми частот 8 различных комбинаций, что и соответствует 3 битам. Выше на рис. 2.1 схематично изображена передача по ВОЛС. подавлен и, одновременно с этим, на какой-то другой частоте за счет шума сигнал превысил установленный порог. Стирание возникает в двух следующих случаях: если ни один из сигналов не превысил порог и если, напротив, порог превысило несколько сигналов. Из всего этого следует, что вероятность ошибки при подобном способе передачи будет невелика относительно вероятности стирания. Ниже на рис. 2.2 приведены кривые зависимости вероятности ошибки и стирания при передаче одного символа от отношения сигнал/шум в канале.
Для сравнения на нем также изображена зависимость ошибки при передаче данных по каналу с использованием одной частоты. Во всех случаях мы считаем, что в канале передачи данных есть только белый аддитивный гауссовский шум. 14 вероятность того, что передаваемый сигнал был подавлен, а є+ - вероятность того, что сигнал на частоте, на которой передача не велась, из-за шума превысил заданный порог. Из графиков мы видим, что данный способ более предпочтителен, нежели передача сигнала на одной частоте. Также можно отметить, что вероятность ошибки примерно на два порядка меньше вероятности стирания. В случае передачи на 16 частотах мы просто объединяем два рассмотренных выше канала на восьми частотах, что в итоге дает нам 6 бит на символ. Понятно, что при таком способе передачи передаваемый символ будет стерт, если стирание произойдет хотя бы в одном из подканалов, а ошибка получится, если хотя бы в одном из подканалов будет ошибка (в отсутствие стираний).
Дополнительно, построим канал, схожий с описанным выше каналом на 8 частотах, но с вдвое большим количеством частот. Такой канал за один такт будет передавать 4 бита. Вероятности символьных ошибки и стирания для данного канала от отношения сигнал/шум изображены на рисунке 2.4.
Также в этой главе будет рассмотрена передача по каналам с модуляцией QAM16 и QAM64. Вероятности ошибки на символ от отношения сигнал/шум для этих типов квадратурной амплитудной модуляции изображены на рисунке 2.5.
В данной работе было проведено моделирование передачи закодированной ОЛО-2 кодами информации по каналам различных типов в среде MATLAB. Все рассмотренные в этой главе ОЛО-2 коде имеют внутренние коды вида (q, щ, щ-1, 2), что позволяет нам делать все вычисления в поле GF(q). Количе ство шагов и избыточность внешних кодов выбраны в соответствии со схемой, описанной в главе 1, обеспечивающей оптимальное соотношение корректирующей способности и скорости передачи.
Количество проведенных испытаний для каждого значения отношения сигнал/шум равно 106. В результате большого количества численных экспериментов было установлено, что полученная в работе теоретическая оценка является достаточно точной оценкой сверху.
Вначале рассмотрим самый простой случай, а именно передачу данных в канале с аддитивным гауссовским шумом. На первом шаге к передаваемому слову добавляются только ошибки, но затем, по мере декодирования внутренними кодами, появляются и стирания. Сначала рассмотрим случай, когда коды-компоненты ОЛО-2 кода имеют длину 16. На рис. 2.6 приведена зависимость вероятности отказа от декодирования + ошибки от отношения сигнал/шум в канале для ОЛО-2 кода порядка 2 с параметрами (256,249). В качестве вложенных внутренних кодов для него были использованы коды Рида-Соломона длины 16 с кодовым расстоянием от 2 до 3, в качестве внешних - коды Рида-Соломона с параметрами (16, 12, 5), (16, 13, 4). Избыточность данного ОЛО-2 кода равна примерно 3%. При выборе параметров кода мы считали, что вероятность отказа для ОЛО-2 кода не должна превышать =10 14 при 12 dB. Кружочками обозначены результаты теоретических расчетов, квадратами - результаты моделирования.
Для сравнения на этом же графике также изображена теоретическая оценка зависимости вероятности ошибки + отказа от декодирования для кода Рида-Соломона с параметрами (16, 15, 2) (ближайший из возможных по избыточности 6%) от отношения сигнал/шум в канале.
Выбор параметров кода, обеспечивающих максимальное кодовое расстояние
В целях сравнения на этом же графике также изображена теоретическая оценка зависимости вероятности ошибки +отказа от декодирования для кода Рида-Соломона на бит с параметрами (64, 62, 3) от отношения сигнал/шум в канале. Выигрыш при є=10" 2 в данном случае составляет порядка 3 дБ. Рис. 2.19. Зависимость вероятности отказа от декодирования от отношения сигнал/шум в канале для ОЛО-2(4096, 3891), т=15 избыточностью 5% при передаче по ЧП-каналу (6 бит).
На рис. 2.19 приведена зависимость вероятности отказа от декодирования + ошибки от отношения сигнал/шум на бит в канале для ОЛО-2 кода порядка 15 с параметрами (4096, 3891). В качестве внутренних кодов для него были использованы коды Рида-Соломона длины 64 с кодовым расстоянием от 2 до 16, а в качестве внешних кодов — коды Рида-Соломона с параметрами (64, 1, 64), (64, 21, 44), (64, 41, 24), (64, 46, 19), (64, 50, 15), (64, 55, 10), (64, 56, 9), (64, 58, 7), (64, 59, 6), (64, 60, 5), (64, 60, 5), (64, 61, 4), (64, 62, 3), (64, 62, 3), (64, 63, 2). Избыточность данного ОЛО-2 кода равна примерно 5%.
Также на этом же графике приведена теоретическая оценка зависимости вероятности ошибки + отказа от декодирования для кода Рида-Соломона с параметрами (64, 61, 4), избыточностью тоже 5%, от отношения сигнал/шум в канале. Выигрыш при є=10" в данном случае составляет порядка ЗдБ.
Далее рассмотрим передачу данных в канале с аддитивным гауссов-ским шумом и квадратурной амплитудной модуляцией. На первом шаге к передаваемому слову добавляются только ошибки, но затем, по мере декодирования внутренними кодами, появляются и стирания. Количество шагов и избыточность внешних кодов опять же выбираются в соответствии со схемой, обеспечивающей оптимальное соотношение корректирующей способности и скорости передачи.
Вначале рассмотрим коды длины 16. Будем считать, что информация передается по каналу с модуляцией QAM 16.
На рис. 2.20 приведена зависимость вероятности отказа от декодирования + ошибки от отношения сигнал/шум в канале для ОЛО-2 кода порядка 2 с параметрами (256,249). В качестве внутренних кодов в нем были использованы коды Рида-Соломона длины 16 с кодовым расстоянием от 2 до 3, в качестве внешних — коды Рида-Соломона с параметрами (16,12, 5), (16,14, 4), избыточность данного ОЛО-2 кода примерно равна 3%. Кружочками обозна чены результаты теоретических расчетов, квадратами - результаты моделирования.
Для сравнения на этом же графике также изображена теоретическая оценка зависимости вероятности ошибки + отказа от декодирования на бит передаваемой информации для кода Рида-Соломона с параметрами (16, 15, 2) (ближайший из возможных по избыточности « 6%) от отношения сигнал/шум в канале. Мы можем видеть, что в этом случае при вероятности отказа 10"12 ОЛО-2 код дает выигрыш более 2,5 децибел по сравнению с кодом PC вдвое большей избыточности.
На рис. 2.21 изображена зависимость вероятности отказа от декодирования + ошибки от отношения сигнал/шум в канале для ОЛО-2 кода порядка 4 с параметрами (256,244). В качестве внутренних кодов в нем были исполь зованы коды Рида-Соломона длины 16 с кодовым расстоянием от 2 до 5, в качестве внешних кодов в нем были использованы коды Рида-Соломона с параметрами (16,10,7), (16,13,4), (16,14,3),(16,15,2); избыточность данного ОЛО-2 кода равна 5%.
Кроме того, на этом же графике также изображена теоретическая оценка зависимости вероятности ошибки + отказа от декодирования на бит передаваемой информации для кода Рида-Соломона с параметрами (16, 15, 2) (ближайший из возможных по избыточности « 6%) от отношения сигнал/шум в канале. Мы можем видеть, что в этом случае при вероятности отказа 10" ОЛО-2 код дает выигрыш почти 4 децибела по сравнению с кодом PC вдвое большей избыточности. На рис. 2.22 изображена зависимость вероятности отказа от декодирования + ошибки от отношения сигнал/шум в канале для ОЛО-2 кода порядка 4 с параметрами (256,239). В качестве внутренних кодов в нем были использованы коды Рида-Соломона длины 16 с кодовым расстоянием от 2 до 5, в качестве внешних кодов в нем были использованы коды Рида-Соломона с параметрами (16, 7, 10), (16, 12, 5), (16, 14, 3), (16, 14, 3). Избыточность данного ОЛО-2 кода равна приблизительно 7%.
Зависимость вероятности отказа от декодирования от отношения сигнал/шум в канале для ОЛО-2 (256,239), т=4 избыточностью 7% при передаче по каналу с QAM16. В рассмотренном случае при вероятности отказа 10"12 ОЛО-2 код дает выигрыш более 4 децибелов по сравнению с кодом РС(16, 15, 2) избыточностью 6%. На рис. 2.23 изображена зависимость вероятности отказа от декодиро вания + ошибки от отношения сигнал/шум в канале для ОЛО-2 кода порядка 6 с параметрами (256,231). В качестве внешних кодов для него были использованы коды Рида-Соломона с параметрами (16, 6, 11), (16, 10, 7), (16, 12, 5), (16, 14, 3), (16, 14, 3), (16, 15, 2), а в качестве вложенных внутренних - коды Рида-Соломона с кодовым расстоянием от 2 до 7. Избыточность данного ОЛО-2 кода равна 10%. 2 4 6 8 10 12 14 1Б 13 20
Передача закодированной ОЛО-3 кодами информации по гауссовскому каналу
И в ЛО-3, и в ОЛО-3 кодах первым всегда декодируется внешний код. После этого последовательно осуществляется декодирование промежуточного и внутреннего кодов. Декодирование ОЛО-3 кодами (в отличие от кодирования, где все проверочные символы для каждой тройки кодов-компонентов можно вычислять параллельно) происходит последовательно в L итераций. Рассмотрим схему декодирования более подробно.
На рис 3.3 для примера схематически изображен 1 шаг декодирования ОЛО-3 кодом. Вначале каждого шага последовательно вычисляются синдромы сначала внутреннего кода, затем промежуточного, являющиеся соответственно символами промежуточного и внешнего кодов. После этого происходит декодирование внешним кодом, причем необходимо, чтобы его избыточности хватило для исправления всех ошибок и стираний, поскольку, если хотя бы один из внешних кодов будет декодирован неверно, то и весь ОЛО-3 код будет впоследствии неверно декодирован.
После этого необходимо провести декодирование соответствующим промежуточными кодом. Затем происходит исправление и обнаружение ошибок соответствующим вложенным внутренним кодом с проверочной матрицей
Таким образом, если количество обнаруженных ошибок или число стираний в кодовом слове внутреннего кода превышает корректирующую способность этого кода, то для соответствующего этому слову символа внешнего кода выносится вердикт «стирание». Матрица \! Матрица " Вычисляем синдромы внутреннего кода. переходим В П01Є GFtqrc)
Если же в кодовом слове внутреннего кода, неверно исправленном на предыдущем шаге, на текущем шаге вновь обнаружены ошибки, то это слово становится таким, каким оно было на предыдущем шаге. В результате чего, к началу каждого следующего шага вероятности появления ошибок и стираний в исходной матрице Е ц - Е$ изменяются по сравнению с предыдущим шагом. Отметим, что обнаружение происходит только внутренними кодами, и только потом, на следующей итерации, обнаруженные ошибки будут учтены.
Соответственно, при декодировании на каждом следующем шаге используется информация о стертых и ошибочных символах, полученная на предыдущем шаге, это означает, что на следующих шагах декодирования мы можем брать меньшую избыточность внешних кодов, так как часть ошибок и стираний уже исправлена. Аналогичные действия производятся на всех последующих шагах. На рис. 3.4 схематично изображен процесс декодирования ОЛО-3 кодами.
В случае ОЛО-3 кодов с двойным вложением, о которых упоминалось выше, все происходит несколько сложнее. Чтобы получить вложение не только для внутренних кодов, но и для промежуточных, нам приходится соединить горизонтальные слои матрицы синдромов внутреннего кода в одну матрицу большего размера. Проверочная матрица вложенного промежуточного кода будет выглядеть как при этом длина вложенного внутреннего кода будет отлична от первоначальной длины пв, и будет равна пв =пві. Затем, после декодирования промежуточным кодом будет иметь место исправление и обнаружение ошибок соответствующим вложенным внутренним кодом с проверочной матрицей.
Основная проблема в данном случае заключается в том, что из-за того, что вложенные промежуточные коды изменяют свою длину с каждым шагом, то мы не можем использовать в качестве промежуточных кодов коды Рида-Соломона, так как их длина не может сильно увеличиваться в фиксированном поле. Соответственно, все теоретические выкладки по оценке вероятности неверного декодирования и подбору параметров не будут действовать, так как мы не можем предсказать, сколько ошибок на каждом шаге будет исправлять промежуточный код.
В качестве внутренних, промежуточных и внешних кодов выступают коды Рида-Соломона. Это МДР-коды, соответственно, для них выполняется соотношение d = n-k+\. Таким образом, величина S(R) = dln может быть представлена как 8(R) = (n-k + \)ln = \-R + \ln, где R = kln - скорость передачи.
Общую нижнюю оценку кодового расстояния для ОЛО-кода можно представить как 8( щ =mm(S "\rf,r ),r ),m)). В результате, получаем, что если необходимо получить код с максимально возможным кодовым расстоянием, то естественным требованием является условие 5i(B) = 52(п) =... = 5 , обеспечивающее максимальное значение 8 2, .
Любое ограничение, налагаемое на величины «У/" , связывающие величины rf,r и г , представляет собой ограничение на структуру ОЛО-кода, которая определяется распределением скоростей передачи внутренних и внешних кодов.
На рис. 3.5. изображен пример зависимости 8 от скоростей передачи внешних и внутренних кодов. Необходимо подобрать значения Rm и Rbl при которых 5 (н) = const. Выбирая значения скоростей таким образом, мы получим ОЛО-3 код с максимальным (среди кодов одного и того же порядка т для заданной общей скорости передачи данных) кодовым расстоянием.
Рассмотрим механизм оценки отказа от декодирования. Поскольку, как и в предыдущем случае, на каждом следующем шаге кодирование осуществляется при помощи кода Рида-Соломона, то для успешного декодирования необходимо выполнение неравенства 2e+T d-l.
Если же при исправлении ошибок и стираний при избыточности d на текущем шаге произошла ошибка декодирования, то на следующем шаге при избыточности d+І ошибки будут обнаружены, только в том случае если e+x=d. Формулы для вероятности неудовлетворительного исхода при исправлении и при обнаружении ошибок для кодов Рида-Соломона имеют следующий вид:
