Главная > Теория кодов, исправляющих ошибки
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
След.
Макеты страниц

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

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO

2.9. ПОСТРОЕНИЕ НОВЫХ КОДОВ ИЗ ЗАДАННЫХ КОДОВ (III)

Построение с помощью прямой суммы. Если заданы -код -код то их прямая сумма состоит из всех векторов где Ясно, что множество таких векторов образует -код. Этот способ прост, но не очень полезен. Более разумен «следующий способ.

Конструкция Если заданы -код одной и той же длины, то мы можем образовать новый код состоящий из всех векторов вида

Теорема 33. Код является -кодом.

Доказательство. Пусть — два различных слова кода , где Если то Предположим, теперь, что Тогда, учитывая упражнение 8 гл. 1, получаем

Этот способ построения очень быстро приводит к хорошим кодам.

Примеры. Выбрав в качестве [4, 3, 2]-код из всех слов четного веса и в качестве [4, 1, 4]-код с повторением, получим в качестве [8, 4, 4]- код Рида — Маллера первого порядка. Выбрав теперь в качестве полученный [8, 4, 4]-код и в качестве [8, 1, 8]-код, получим в качестве -код Рида-Маллера первого порядка. На самом деле, как мы увидим в гл. 13,

все коды Рида — Маллера могут быть построены так.

Замечания, (а). Если коды и имеют различные длины, то описанная конструкция применима, если мы добавим соответствующее число нулей в конце более короткого кода.

(b). Если коды и линейны, например то код представляет собой линейный код.

Бесконечное семейство нелинейных кодов, исправляющих одни ошибку. Беря в качестве исходных (8, 20, 3), -коды, приведенные в § 2.7, мы можем построить бесконечное семейство кодов:

Продолжая таким путем, мы получаем следующий результат.

Теорема 34. Для любой длины удовлетворяющей условию существует нелинейный -код, где (19/16) или (18/16).

Замечания. Из границы сферической упаковки (теорема 6 гл. 1) следует, что наибольший линейный код той же самой длины, исправляющий одну ошибку, который представляет собой укороченный код Хэмминга, имеет только кодовых слов.

Нелинейные коды Васильева, исправляющие одну ошибку. Коды Хэмминга, которые были построены в § 1.7, являются единственными, любой двоичный линейный код с параметрами эквивалентен коду Хэмминга. Это так, потому что проверочная матрица кода должна содержать все ненулевых двоичных -векторов в некотором порядке.

Это не так, если отбросить предположение о линейности кода.

Упражнения. (18). Коды Васильева. Пусть совершенный двоичный -код, исправляющий одну ошибку, не обязательно линейный. Пусть X — любое отображение слов кода в поле (причем которое является строго нелинейным: найдутся векторы для которых Положим или 1 в зависимости от того, четно или нечетно число

Показать, что код

является совершенным -кодом, исправляющим одиночные ошибки, который неэквивалентен никакому линейному коду. Показать, что такие коды существуют для всех

(19). Пусть обозначают линейные коды, Показать что:

ЗАМЕЧАНИЯ К ГЛ. 2

(см. скан)

(см. скан)

1
Оглавление
email@scask.ru