ЗАДАЧИ

10.1. Множество всех (7 X 7)-матриц над GF (2) образует векторное пространство. Выписать базис этого пространства. Сколько векторов содержит это пространство? Является ли подпространством множество всех таких матриц с нулевой главной диагональю? Если да, то сколько векторов содержит это подпространство?

10.2. Пусть р (х) = + X + 1 и (х) = X* + X + 1 - многочлены над-GF (2). Найти «китайские многочлены» а (х) и b (х), удовлетворяющие равенству а (х) р (х) + 6 (х) q (х) = 1.

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

а. Сколько ошибок может исправить код й"?

б. Привести пример двух конфигураций ошибок одинакового веса, обнаруживаемых кодом, но имеющих один и тот же синдром и, следовательно, неиспр авляемых.

10.4.а. С помощью перемежения расширенного кода Рида-Соломона над GF (64) построить (3840, 3360)-код, исправляющий пакеты из 240 6-битовых байтов. Чему равно минимальное расстояние кода-перемежения?

б. Перевести этот код в (4096, 3360)-код-произведение, который таюке исправляет пакеты из 240 байтов, но, кроме того, исправляет и случайные конфигурации ошибок из 22 байтов.

в. Описать декодеры для кодов из предыдущих пунктов задачи.

10.5. Сколько ошибок может исправлять произведение (7, 4)-кода Хэмминга на самого себя? Используя в качестве готового блока декодер для (7, 4)-кода Хэмминга, построить простой декодер, исправляющий ошибки в пределах радиуса упаковки кода-произведения.

10.6. Пусть а п b удовлетворяют равенству апу-}- бпг = 1 для взаимно простых til и ng. При заданном циклическом (tiy, куУкоце с порождающим многочленом gi (х) и заданном циклическом (/ig, /г2)-коде с порождающим многочленом g-g (х) доказать, что порождающий многочлен ци101ического кода-произведения длины ti = ппа равен

g (X) = НОД [gi (х"), g2 (х""), х"- 1].

лекэмпа-Месси для заполнения всех входов таблицы Ец-. Обратное двумерное преобразование Фурье завершает декодирование. Более простой процедурой является следующая. Вычислим одномерное обратное преобразование Фурье для 2t известных строк символов Ejj. Это дает множество из 2t компонент синдрома для каждого столбца; ненулевые компоненты могут иметь не более 2t столбцов и только к ним необходимо применить алгоритм Берлекэмпа-Месси.

На рис. 10. 7, б показан другой возможный способ выбора проверочных частот, который приводит к двумерному коду с большей скоростью, но с более сложным декодером. В этом случае алгоритм Берлекэмпа-Месси должен применяться для декодирования по1¥еременно строк и столбцов. При необходимости для вычисления новых компонент Ец- используются ограничения сопряженности.

ЗАМЕЧАНИЯ 353

ЗАМЕЧАНИЯ

Произведение кодов ввел Элайс 1.1954], доказавший, что минимальное расстояние кода-произведения равно произведению минимальных расстояний исходных кодов. Бартон и Уэлдон [1965] доказали, что при взаимно простых длинах произведение двух циклических кодов является циклическим кодом. В этой же работе изучалось исправление пакетов ошибок и независимых ошибок кодами-произведениями. Методы декодирования кода-произведения описали Редди и Робинсон [1972], а также Уэлдон [1971 ]. В § 10.4-10.6 развиваются идеи автора (Блейхут [1979]). Использовать дуальный код-произведение для исправления кратных низкоплотностных пакетов предложили Чень и Нг [1973].

ГЛАВА И

БЫСТРЫЕ АЛГОРИТМЫ

Хорошие коды с большой длиной и большим объемом алфавита, такие, как коды Рида-Соломона, находят все более широкое применение. В будущем потребуются еще более длинные коды, контролирующие ошибки, и поэтому задача уменьшения сложности алгоритмов декодирования становится важной. Мы уже рассмотрели "ticKOTOpbie эффективные алгоритмы декодирования кодов Рида-Соломона и связанных с ними кодов и знаем, как строить декодеры, содержащие порядка вычислений.

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

11.1. ЛИНЕЙНАЯ СВЕРТКА И ЦИКЛИЧЕСКАЯ СВЕРТКА

Линейная свертка

k=0.

может быть также записана в виде произведения многочленов

с(х) g(x)d(x).

Стандартный способ вычисления произведения двух многочленов требует примерно (deg d (х)) X (deg g (х)) умножений и ело-