Замечания
Коды, описываемые в этой главе, были получены независимо Хоквингемом [141] и Боузом и Рой-Чоудхури [29, 30]. Интересно, что коды, построенные ранее Ридом и Соломоном [250] и описанные в разд. 9.2, оказались частным случаем БЧХ-кодов. Результаты по определению истинного минимального расстояния БЧХ-кодов основаны на работе [167].
Если вы следите за курсом доллара к рублю, то вы наверняка заметили резкое падение рубля из за санкций США. На этом можно неплохо заработать на форексе. Можно работать как самому, так и написать советника. В этом поможет метаредактор для торговых советников.
Первым был найден способ исправления ошибок, описанный в начале разд. 9.6. В большинстве случаев коды, методы кодирования и исправления ошибок обобщаются тривиальным образом, но эта схема исправления ошибок существенно зависит от того факта, что в двоичном случае при вычислении синдрома находятся некоторые симметрические функции номеров позиций ошибок. Поэтому полученная Цирлером и Горенстейном схема декодирования, которая описана в разд. 9.4, была совершенно неожиданной. Математически их метод тесно связан с интерполяционной задачей [329]. Итеративные алгоритмы, представленные в разд. 9.5 и 9.6, были построены Берлекэмпом [21], а алгоритмы для решения аналогичной совокупности уравнений над полем действительных чисел использовались ранее Тренчем [306]. Приведенное здесь изложение алгоритмов основано на работе Месси [211].
Этапы 3 и 4 (разд. 9.4) были упрощены соответственно Цянем [49] и Фор ни [89].
Идеи разд. 9.7 основаны на работах [24, 89]. Негациклические коды были построены Берлекэмпом [20].
Задачи
9.1. Покажите, что любой двоичный код, порожденный многочленом g(X) = g*(X)
, имеющим 1 среди своих корней, есть БЧХ-код с минимальным расстоянием не меньше 6. Покажите, что это утверждение применимо к любым из двух двоичных циклических (17,8) -кодов.
9.2. Покажите, что если в определении БЧХ-кодов элемент а заменить на любой другой элемент а' того же порядка, то получится эквивалентный код. (Указание: сначала покажите, что каж дый из элементов а и а' может быть представлен как степень другого.)
9.3. Покажите, что код Рида — Соломона с символами из GF(q), порожденный многочленом
g(X)^(X-a){X-oF) ... (Х-аа-1),
где а — примитивный корень GF(q), имеет минимальное расстояние d.
9.4. Пусть Ci — двоичный циклический (и, k) -код с конструктивным расстоянием 2tx. Предполагается, что порождающий многочлен gi(X) кода С\ не делится на X-\- 1. Пусть теперь С2 — циклический (и,k— 1)-код, порожденный (X + l)gx(X)
, и этот код имеет конструктивное расстояние 2t2 > 2^. Покажите, что действительное минимальное расстояние Сх равно по меньшей мере 2U + 1.
9.5. Используя результаты предыдущей задачи, докажите, что (17,9)- и (65,53)-коды БЧХ имеют расстояние 5.
9.6. Используя результаты двух предыдущих задач, покажите, что все циклические (2™ + 1,2™-f-1—2т)
-коды имеют расстояние 5. Заметим, что эти коды несколько лучше, чем примитивные БЧХ-коды с тем же минимальным расстоянием и числом проверочных символов. |
Главная
Каталог файлов
