- •Тема 7. Коды Рида- Соломона (рс)
- •7.1. Определение и основные свойства
- •Пример 7.1
- •Пример 7.2
- •7.1.1. Расширенные рс-коды
- •Пример 7.3
- •7.1.2. Укороченные рс-коды
- •7.1.3. Отображение рс-кодов над gf(2m) на двоичные коды
- •7.1.4. Способы кодирования и декодирования рс-кодов
- •1. Многочлен локаторов ошибок:
- •2.Синдромный многочлен
- •3. Многочлен значений ошибок
- •7.2. Быстрое декодирование кодов бчх
- •7.2.1. Ключевое уравнение
- •7.2.2. Решение ключевого уравнения
- •7.2.3. Примеры решения ключевого уравнения
- •7.3.Кодирование на основе решения ключевого уравнения
- •7.4.Задачи
- •Тема 8. Непрерывные коды
- •8.1. Сверточное кодирование
- •8.2. Представление сверточного кодера
- •8.2.1. Представление связи
- •8.2.1.1. Реакция кодера на импульсное возмущение
- •8.2.1.2. Полиномиальное представление
- •8.2.2. Представление состояния и диаграмма состояний
- •8.2.3. Древовидные диаграммы
- •8.2.4. Решетчатая диаграмма
- •8.3. Формулировка задачи сверточного декодирования
- •8.3.1. Алгоритм сверточного декодирования Витерби
- •8.3.2. Пример сверточного декодирования Витерби
- •8.3.2.1. Процедура сложения, сравнения и выбора
- •8.3.2.2. Вид процедуры сложения, сравнения и выбора на решетке
- •8.3.3. Память путей и синхронизация
- •8.4. Свойства сверточных кодов
- •8.4.1. Пространственные характеристики сверточных кодов
- •8.4.1.1. Возможности сверточного кода в коррекции ошибок
- •8.4.2. Систематические и несистематические сверточные коды
- •8.4.3. Распространение катастрофических ошибок в сверточных кодах
- •8.4.4. Границы рабочих характеристик сверточных кодов
- •8.4.5. Эффективность кодирования
- •8.4.6. Наиболее известные сверточные коды
- •8.5. Задачи
- •Тема 9. Некоторые специальные классы кодов. Составные коды
- •9.1. Коды для исправления пачек ошибок
- •9.2. Коды на основе последовательностей максимальной длины
- •9.3. Коды для асимметричных каналов
- •9.3.1. Коды с постоянным весом
- •9.3.2. Коды Бергера
- •9.4 Каскадные коды
- •9.4.1. Принципы построения каскадных кодов
- •9.4.2. Режимы использования каскадных кодов
- •9.4.3. Построение двоичных каскадных кодов на основе кодов Рида–Соломона и Боуза–Чоудхури–Хоквингема
- •Пример 9.2.
- •Пример 9.3.
- •9.5. Задачи
- •Тема 10. Цикловая синхронизация
- •Назначение и классификация способов цикловой синхронизации
- •10.2. Способ установки фазы приемного распределителя путем сдвига.
- •10.3. Способ мгновенной установки фазы
- •10.3.1. Маркерный способ цикловой синхронизации на основе синхронизирующих кодовых последовательностей
- •10.4 . Способ выделения сигнала фазового запуска по зачетному отрезку
- •Тема 11. Системные методы защиты от ошибок без обратной связи
- •11.1. Классификация и основные характеристики систем повышения достоверности
- •11.1.1. Теоретические основы системных методов защиты от ошибок
- •11.1.2. Классификация системных методов защиты от ошибок
- •11.1.3 .Основные параметры и характеристики систем повышения достоверности
- •11.2. Методы повышения достоверности в однонаправленных системах
- •11.2.1.Однонаправленные системы с многократным повторением сообщений
- •11.2.2.Однонаправленные системы с исправляющим ошибки кодом
- •11.2.3.Однонаправленные системы с исправлением стираний
- •11.3. Задачи
- •Тема 12. Системные методы защиты от ошибок с обратной связью
- •12.1. Системы повышения достоверности с решающей обратной связью с непрерывной последовательной передачей сообщений и блокировкой (рос-пПбл).Общие положения
- •12.2. Описание работы системы рос-пПбл
- •12.3. Режим переспроса
- •12.4. Расчет параметров системы рос-пПбл Относительная скорость передачи
- •Расчет вероятности ошибок на выходе системы
- •Расчет времени доведения сообщений
- •Расчет емкости накопителя-повторителя
- •12.5. Рекомендации по выбору оптимального кода Расчет оптимальных характеристик помехоустойчивого кода
- •Охарактеризуем поток ошибок, пропущенных в приемник сообщений средней вероятностью ошибки на бит, равной и показателем группирования ошибок.
- •12.6. Выбор порождающего многочлена
- •12.7. Задачи
- •Тема 1. Основные понятия и определения в области пдс…………………………………..…...2
- •Тема 2. Системные характеристики систем передачи дискретных сообщений………………..11
- •Тема 3. Основные характеристики уровня дискретного канала пдс……………………...……21
- •Тема 4. Устройство синхронизации по элементам (усп)……………………………………….50
- •Тема 5. Линейные (n,k)-коды…….…………………………………………………………………..54
- •Тема 6. Двоичные циклические (n,k) – коды…………………………………………………… 105
- •Тема 7. Коды Рида- Соломона (рс)…………………………………………..…………………..165
- •7.1. Определение и основные свойства………………….…………………….……………...165
- •7.1.3. Отображение рс-кодов над gf(2m) на двоичные коды……………………………….170
- •Тема 8. Непрерывные коды……………………………………………...……………………….185
- •Тема 9. Некоторые специальные классы кодов. Составные коды………………………………210
- •9.4.1. Принципы построения каскадных кодов……………………………………………………………215
- •9.4.2. Режимы использования каскадных кодов…………………………………………………………..218
- •9.4.3. Построение двоичных каскадных кодов на основе кодов Рида–Соломона и Боуза–Чоудхури–Хоквингема………………..………………………………………………..…………………………………219
- •Тема10. Цикловая синхронизация……………………………...…………………………………………222
- •Тема 11. Системные методы защиты от ошибок без обратной связи………………………………..…234
- •Тема 12. Системные методы защиты от ошибок с обратной связью…..…………………….…...244
9.1. Коды для исправления пачек ошибок
Под пачкой ошибок длины l будем понимать последовательность ошибок, занимающую l последовательных элементов кодовой комбинации, при условии, что первый и последний элементы в этой последовательности искажены.
По аналогии под пачкой в кодовой комбинации будем называть некоторую ее часть, ограниченную с обеих сторон единицами.
Вполне понятно, что некоторый (n, k) – код обладает способностью обнаруживать или исправлять пачки ошибок длины l и менее тогда и только тогда, если его кодовые комбинации не содержат в своем составе пачек данной длины.
С помощью простых рассуждений можно установить минимальное число избыточных элементов в кодовой комбинации группового кода, способного обнаруживать все пачки ошибок длины l и менее.
Во-первых, необходимо, чтобы такой код не содержал пачек длины l и менее. Определим, когда это возможно. Рассмотрим разложение группы, составленной из п – элементных векторов не смежные классы по подгруппе, образующей данный (n, k) – код. Если кодовые комбинации не содержат пачек длины l и менее, то в одном и том же смежном классе не могут существовать 2 комбинации, в которых, начиная с одного и того же разряда, размещены пачки длины l и менее, так как в противном случае их сумма, являющаяся кодовой комбинацией, должна содержать пачку длины меньшей l.
Так как для некоторого фиксированного разряда кодовой комбинации можно указать 2l различных комбинаций, которые в силу сказанного выше должны принадлежать различным смежным классам, то число смежных классов не может быть меньшим 2l.
Таким образом, доказано следующее свойство групповых кодов.
Свойство 9.1. Групповой код, обнаруживающий все пачки ошибок длины l и менее, должен содержать, по крайней мере, l проверочных символов.
В случае циклического кода эта нижняя граница для числа проверочных символов является точной. Действительно, любая кодовая комбинация циклического кода может быть представлена как произведение где g(x) – порождающий многочлен кода степени n-k. Значит каждая кодовая комбинация циклического кода содержит или пачку длины n–k+1 (комбинации ) или линейную комбинацию циклически сдвинутых пачек длины n–k+1, сумма которых всегда дает пачку большей длины, т.е. справедливо следующее свойство.
Свойство 9.2. Любой циклический (n, k) – код обнаруживает все пачки ошибок длины (n - k) и менее.
В случае исправления пачек ошибок можно аналогичными рассуждениями получить нижнюю границу для числа проверочных элементов. Действительно, пусть известно, что групповой (n, k) – код исправляет все пачки ошибок длины b. Значит общее число смежных классов в таблице декодирования должно быть не меньше, чем число возможным пачек длины b. В комбинации длины п возможно всего п пачек длины 1, п-1 пачек длины 2, 2(п-2) пачек длины 3 и т.д. Общее число пачек длины b в комбинации длины п равно . Таким образом, число смежных классов равно
Используя формулу для арифметико-геометрической прогрессии, данное выражение прообразуем к виду
откуда, логарифмируя по основанию 2, получаем . Итак, справедливо следующее свойство групповых кодов.
Свойство 9.3. Число проверочных элементов (n, k) – кода, исправляющего все пачки ошибок длины b и менее равно самое меньшее .
Одним из самых обширных из известных в настоящее время классов кодов, специально предназначенных для исправления пачек ошибок, являются коды Файра.
Коды Файра – циклические коды, порождающий многочлен которых имеет вид , где Р(х) – неприводимый многочлен степени r, входящий в разложение и не являющийся сомножителем никакого двучлена меньшей степени.
Необходимо при этом, чтобы с не делилось на е. Длина кодовой комбинации п равна наименьшему общему кратному чисел е и с, т.к. только в этом случае g(x) делит
Число проверочных элементов равно , а число информационных . В [1] показано, что коды Файра исправляют любую одиночную пачку ошибок длины b или меньше и одновременно обнаруживают любую пачку ошибок длины или меньше, если выполняются соотношения и Если применять эти коды только для обнаружения ошибок, то можно обнаружить любую комбинацию из двух пачек ошибок, длина наименьшей из которых не превосходит r, а сумма длин которых не превосходит с+1, а так же и любую одиночную пачку ошибок, длина которой не превосходит числа проверочных символов с+r.
Указанные свойства кодов Файра обусловлены видом порождающего многочлена. Наличие в g(x) сомножителя достаточно для обнаружения одиночной пачки ошибок длины с. Дополнительная информация, требуемая для определения положения пачки ошибок, обеспечивается сомножителем Р(х).
Пример 9.1. Код Файра порождается многочленом Определить параметры кода и его корректирующие свойства.
Здесь r=3, е=7, с=4, n-k=r+c=7;
Итак, порождает код Файра (28,21). Данный код может исправить пачки ошибок длины b=2 и b=1, а также дополнительно обнаружить при этом пачки длины b=3 и b=4 соответственно. Если использовать этот код только для обнаружение ошибок, то модно обнаружить любую одиночную пачку ошибок длины 7 и комбинацию из двух пачек ошибок, из которых одна не превосходит 3, а сумма длин обоих равна 5 или менее.
Для оценки эффективности кодов Файра необходимо знать функцию распределения пачек различной длины в кодовых комбинациях. Поскольку этот вопрос выходит за рамки данного учебного пособия, то эффективность данных кодов строго оценена быть не может. Приближенная оценка может быть произведена при пересчете пачек на кратности ошибок. При таком упрощенном подходе вероятность ошибочного приема кодовой комбинации при одновременном исправлении и обнаружении:
и
.
Для кодов с обнаружением пачек ошибок:
и
На основании этих формул определяется эффективность кодов. Для случая исправления и обнаружения пачек ошибок
.
Для случая обнаружения пачек ошибок
.
Из определения кодов Файра вытекает, что при с=1 они совпадают с кодами Хэмминга, имеющими dmin=4, если при этом .