- •Глава3 4
- •Часть 1 введение 4
- •Часть 2 коды хемминга, голея и рида-маллера 39
- •Часть 3 двоичные циклические коды и коды бчх 54
- •Часть 4 недвоичные бчх коды -коды рида-соломона 105
- •Глава3 часть 1 введение
- •1.1. Кодирование для исправления ошибок: Основные положения
- •1.1.1. Блоковые и сверточные коды
- •1.1.2. Хеммингово расстояние, Хемминговы сферы и корректирующая способность
- •1.2. Линейные блоковые коды
- •1.2.1. Порождающая и проверочная матрицы
- •1.2.2. Вес как расстояние
- •1.3. Кодирование и декодирование линейных блоковых кодов
- •1.3.1. Кодирование с помощью матриц g и н
- •1.3.2. Декодирование по стандартной таблице
- •1.3.3. Хемминговы сферы, области декодирования и стандартная таблица
- •1.4. Распределение весов и вероятность ошибки
- •1.4.1. Распределение весов и вероятность необнаруженной ошибки в дск.
- •1.4.2. Границы вероятности ошибки в дск, каналах с абгш и с замираниями
- •1.5 Общая структура жесткого декодера для линейных кодов
- •Часть 2 коды хемминга, голея и рида-маллера
- •2.1. Коды Хемминга
- •2.1.1. Процедуры кодирования и декодирования
- •2.2. Двоичный код Голея
- •2.2.1 Кодирование
- •2.2.2. Декодирование
- •2.2.3. Арифметическое декодирование расширенного (24,12,8) кода Голея.
- •2.3. Двоичные коды Рида-Маллера
- •2.3.1. Булевы полиномы и рм коды
- •2.3.2. Конечные геометрии и мажоритарное декодирование.
- •Часть 3 двоичные циклические коды и коды бчх
- •3.1. Двоичные циклические коды.
- •3.1.1. Порождающий и проверочный полиномы.
- •3.1.2. Порождающий многочлен
- •3.1.3. Кодирование и декодирование двоичных циклических кодов.
- •3.1.4. Проверочный полином.
- •3.1.5. Укороченные циклические коды и crc коды
- •3.2. Общий алгоритм декодирования циклических кодов
- •3.1.5 Пакеты ошибок
- •3.2.1. Арифметика gf(q)
- •3.3. Двоичные коды бчх
- •3.4. Полиномиальные коды
- •3.5. Декодирование двоичных бчх кодов
- •2. Евклидов алгоритм (еа)
- •3.5.1. Общий метод декодирования для бчх кодов
- •3.5.2. Алгоритм Берлекемпа-Мэсси (вма)
- •3.5.3. Декодер pgz
- •3.5.4. Евклидов алгоритм (еа)
- •3.5.5. Метод Ченя и исправление ошибок
- •3.5.6. Исправление стираний и ошибок
- •3.6. Распределение весов и границы вероятности ошибки
- •3.6.1. Оценка вероятности ошибки
- •Часть 4 недвоичные бчх коды -коды рида-соломона
- •4.1. Коды pc как полиномиальные коды
- •4.2. От двоичных кодов бчх к pc кодам
- •4.3. Декодирование кодов pc
- •4.3.1. Комментарий к алгоритмам декодирования
- •4.3.2. Исправление ошибок и стираний
- •4.4. Распределение весов
- •Глоссарий
- •Литература
4.4. Распределение весов
Как упоминалось выше, коды PC являются МДР кодами. Распределение весов МДР кодов вычисляется точно с помощью следующего выражения [MS, LC]:
Число кодовых слов веса i МДР (n,k,d) кода над GF(q) равно
(4.22)
Для оценки помехоустойчивости (n,k,d) PC кода над GF(q) можно использовать следующую границу (оценку сверху) вероятности ошибки на бит Рb алгебраического декодера PC2, которая легко вычисляется и дает достаточно хороший результат,
(4.23)
где Ps вероятность ошибки на символ на входе декодера PC,
и р вероятность ошибки на бит на входе декодера. Вероятность ошибки на слово (включая неправильное декодирование и отказ от декодирования) ограничена сверху границей (1.31),
(4.24)
Вопросы для самоконтроля
1. Расскажите о работе алгоритма Мэсси по декодированию кода РС
2. Расскажите о работе алгоритма Евклида по декодированию кода РС
3. Опишите принципы работы алгоритма Берлекэмпа-Мэсси для исправления ошибок и стираний
4. Как рассчитывается распределение весов для РС кода
Глоссарий
Кодовое слово - последовательность информационных и избыточных символов образующих кодовую последовательность;
Хеммингово расстояние - число позиций, на которых два двоичных вектора не совпадают;
Корректирующей способностью кода – способность кода исправлять t ошибок в принятом слове;
Стандартной таблицей (или стандартной расстановкой) для двоичного линейного (n, k, dmin) кода С называется таблица всех возможных принятых из канала векторов r, организованная таким образом, что может быть найдено ближайшее к r кодовое слово v;
Совершенными кодами называются коды удовлетворяющие границе Хемминга с равенством;
Вероятность правильного декодирования равна вероятности того, что вектор ошибок совпадает с одним из лидеров смежных классов;
Код Хемминга – это совершенный код, исправляющий одну ошибку;
Код Голея – совершенный код с параметрами (23,12,7)
Линейный блоковый код является циклическим тогда и только тогда, когда любой циклический сдвиг любого кодового слова оказывается другим (или тем же самым) кодовым словом;
CRC коды избыточные циклические коды для обнаружения ошибок.
Литература
(добавленная при переводе)
Э. Берлекэмп, Алгебраическая теория кодирования, «Мир», Москва 1971.
Р. Блейхут, Теория и практика кодов, исправляющих ошибки, «Мир», Москва, 1986.
Э. Л. Блох и В. В. Зяблов, Обобщенные каскадные коды, «Связь», Москва, 1976.
Э. Л. Блох и В. В. Зяблов, Линейные каскадные коды, «Наука», Москва 1982. Кларк и Кейн,
Г. С. Евсеев, «О сложности декодирования линейных кодов», Проблемы передачи информации, т. 19, №1, стр. 3-8, 1983.
Д. Форни, Каскадные коды, «Мир», Москва, 1970.
Р. Галлагер, Коды с малой плотностью проверок на четность, «Мир», Москва, 1966.
Р. Галлагер, Теория информации и надежная связь. «Советское радио», Москва 1974.
Р. Лидл и Г. Нидерайтер. Конечные поля, т. 1,2. «Мир», Москва 19X8.
Ф. Дж. Мак-Вильяме и Н. Дж. Слоэн, Теория кодов, исправляющих ошибки, «Связь», Москва 1979.
Дж. Мэсси, Пороговое декодирование, «Мир», Москва 1966.
Дж. Проакис, Цифровая связь, Пер. с англ./Под ред. Д.Д. Кловского. - М.: Радио и связь. 2000. - 800 с: ил. ISBN 5-256-01434-Х
У. Питерсон и Э. Уэлдон, Коды, исправляющие ошибки, Пер. с англ./ Под ред. Р.Л.
Добрушина и С.Н. Самойленко. — МИР, Москва, 1976. -594 с: ил.
К. Шэннон, Работы по теории информации и кибернетике, «Иностранная литература», Москва 1963.
А.Д. Витерби и Дж. Омура, Принципы цифровой связи и кодирования, «Радио и связь», Москва 1982.