Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Ответы_2011.doc
Скачиваний:
30
Добавлен:
12.09.2019
Размер:
712 Кб
Скачать
☆

Линейные коды общего вида

Линейный блоковый код — такой код, что множество его кодовых слов образует k-мерное линей­ное подпространство (назовём его C) в n-мерном линейном простран­стве,изоморфное пространству k-битных векторов.

Линейные циклические коды

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

Циклическим кодом является линейный код, обладающий следующим свойством: если   явля­ется кодовым словом, то его циклическая перестановка также является кодовым словом.

Слова циклического кода удобно представлять в виде многочленов. Например, кодовое слово   представляется в виде поли­нома  . При этом циклический сдвиг кодового слова эквива­лентен умножению многочлена на x по модулю xn − 1.

Коды crc

Коды CRC (cyclic redundancy check — циклическая избыточная проверка) явля­ются систематическими кодами, предназначенными не для исправления ошибок, а для их обна­ружения. Они используют способ систематического кодирования, изложенный выше: «контроль­ная сумма» вычисляется путем деления xn − ku(x) на g(x). Ввиду того, что исправление ошибок не требуется, проверка правильности передачи может производиться точно так же.

Таким образом, вид полинома g(x) задаёт конкретный код CRC. Примеры наиболее популярных полиномов:

название кода

степень

Полином

CRC-12

12

x12 + x11 + x3 + x2 + x + 1

CRC-16

16

x16 + x15 + x2 + 1

CRC-CCITT

16

x16 + x12 + x5 + 1

CRC-32

32

x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1

Коды БЧХ

Коды Боуза — Чоудхури — Хоквингема (БЧХ) являются подклассом циклических кодов. Их отличи­тельное свойство — возможность построения кода БЧХ с минимальным расстоянием не меньше заданного. Это важно, потому что, вообще говоря, определение минимального расстояния кода есть очень сложная задача.

Математически полинома g(x) на множители в поле Галуа.

Коды коррекции ошибок Рида — Соломона

Коды Рида — Соломона — недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида-Соломона, работающие с байтами (октетами).

Математически коды Рида — Соломона являются кодами БЧХ.

Преимущества и недостатки блоковых кодов

Хотя блоковые коды, как правило, хорошо справляются с редкими, но большими пачками ошибок, их эффективность при частых, но небольших ошибках (например, в канале сАБГШ), менее вы­сока.

Свёрточные коды

Свёрточный кодер ( )

Свёрточные коды, в отличие от блоковых, не делят информацию на фрагменты и работают с ней как со сплошным потоком данных.

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

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

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