Согласно доказанной теореме, любые 2t компонент синдрома, расположенных в таблице на произвольной прямой (горизонтальной, вертикальной или идущей под любым углом) можно продолжать до всех компонент синдрома на этой прямой. Далее, в силу ограничений сопряженности каждая из этих новых компонент синдрома определяет все сопряженные с ней компоненты. Конечно, не обязательно, чтобы вычисленные так компоненты синдрома давали остальные его компоненты. Размеры таблицы не всегда задаются взаимно простыми числами, так что продолжение прямой не обязательно включает все компоненты.

Посмотрим теперь, как граница БЧХ обобщается на случай двух (или более) размерностей. Предположим, что где-то в первой строке имеются 2t подряд идущих компонент синдрома. Тогда их продолжение дает все компоненты синдрома в первой строке.

такая процедура не дает однозначного решения для пар (Xi, Yi) при / = 1, 2, V, так как некоторые ошибки попадают в один и тот же столбец. В общем случае для Пу = = п справедлива следующая теорема, которую можно обобщить, заменив п на НОК Пг).

Теорема 10.6.1. Предположим, что произошло v < / ошибок и что для любых целых /д, и а, а известны компоненты синдрома Sj+ak. г+ак при k=l,...,2t. Tozdu компонвнты синдрома Sj+ak. г+ак при k= 1, п определяются однозначно.

Доказательство. Нам даны 2t уравнений для k = 1, 2t:

= izc (XrYio) {X-Yfy. 1=1

Обозначим через v число различных величин XlXf при всех /, череК;-, Г = 1, v, различные значения в этом наборе, а через Xi сумму всех множителей при фиксированном в данном уравнении (она имеет одно и то же значение для всех k). Тогда

Sj+ak. pQ+ak = liXfYi,, k = I,. . .,2t,

где теперь все Yr различны и v < Алгоритм Берлекэмпа- Месси с последующим рекуррентным продолжением позволяет вычислить остальные компоненты синдрома

V

/"о+о/г, 1+ак = Ij Xi- Y[, k = \,. . ., п. □

10.7. ДЛИННЫЕ КОДЫ НАД МАЛЫМИ полями 347

Аналогично расположенные где-то во второй строке подряд идущие 2t компонент синдрома могут быть использованы для вычисления всех компонент синдрома во второй строке. Далее, любые расположенные подряд 2t компонент синдрома в первых 2t строках могут быть продолжены до всех компонент синдрома в каждой из этих 2t строк и, следовательно, 2t непрерывно расположенных компонент синдрома по столбцам. Последние в свою очередь могут быть продолжены до всех компонент синдрома в своем столбце, а этого уже достаточно для однозначного вычисления конфигурации ошибок. Простейший пример дается (2 X 2/)-таблицей известных компонент синдрома. Общая ситуация описывается следующим образом.

Теорема 10.6.2 (двумерная граница БЧХ). Если а взаимно просто спи число ошибок v не превосходит t, то. множество компонент синдрома

где а, а и ти - некоторые целые числа, k = 1, 2t, k = 1, 2t, однозначно определяет конфигурацию ошибок. Доказательство. Для каждого k воспользуемся предыдущей теоремой для вычисления компонент синдрома

Sa {mjJt-k-), а- {m+k-)+k, к = \,...,П, k=\,...,2t.

Переопределим индекс k так, чтобы отбросить в индексах числа т и записать известные компоненты синдрома в виде

Sak. ak+kj k = \,. . .,П, k = \, . . . ,2t.

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

Sak, ak+k, к = \,...,П, к=\,...,П.

Поскольку к пробегает все значения от 1 до п, его можно переопределить так, чтобы избавиться от ак; таким образом, вычисляются все компоненты синдрома Sak-.k, при к = 1, п и к = 1, п. Поскольку сип взаимно просты, то индекс ак пробегает все п значений. Следовательно, синдром вычислен полностью и конфигурация ошибок определена. □

10.7. ДЛИННЫЕ КОДЫ НАД МАЛЫМИ ПОЛЯМИ

Для кодов с очень большой длиной и высокой скоростью сложность декодера может являться более важным фактором, чем скорость кода. С практической точки зрения разница между скоростями 0,98 и 0,99 может быть не столь уж существенной,

если декодеры для этих двух кодов сильно отличаются в цене. В настоящем параграфе рассматриваются коды очень большого объема, декодеры для которых имеют ограниченную сложность. Все рассматриваемые коды являются многомерными; характеристики этих кодов в общем случае лучше, чем у кодов-произведений, а декодирование реализуется с помощью вычислений в поле Галуа, мощность которого намного меньше длины кода. Такие коды могут быть противопоставлены кодам БЧХ.

Для кода БЧХ длины п = cf - 1 декодер производит вычисления в поле GF (cf). При больших п мощность такого поля Галуа очень велика. Коды, которые будут сейчас описаны, можно декодировать с помощью вычислений в малом поле Галуа. Одним из этих пршЙеров будет двоичный код, слова которого задаются двумерной таблицей с п = 2" - 1 строк и таким же числом столбцов. Следовательно, длина кода равна п, но мы надеемся все вычисления провести в поле GF (2"). Хотя скорость такого кода ниже скорости кода БЧХ с теми же п и d, в некоторых приложениях он моя$ет оказаться предпочтительнее из-за малой длины, на которой производит вычисления декодер.

Первым примером является произведение двух кодов БЧХ, а именно (п, ky, Й1)-кода и (п, К, й-коа, и, следовательно, является кодом с параметрами (пщ, kyk, dyd. Например, произведение расширенного (256, 232, 25)-кода Рида-Соломона на самого себя дает (65 536, 53 824, 625)-код над GF (256), который позволяет исправлять 312 8-битовых байтов, пакеты длины 3072 8-биТовых байтов, а также многие конфигурации ошибок более чем из 312 байтов. Вместо этого можно воспользоваться (65 536, 64 289, 625)-кодом БЧХ, который позволяет также исправлять 312 случайных байтов и обеспечивает при этом существенно большую скорость, но его декодирование требует вычислений в 16-битовой арифметике поля GF (2"). Код-про изведен не компенсирует это другим преимуществом, позволяя помимо 312 случайных байтов исправлять многие другие конфигурации ошибок, чего не может код БЧХ. Декодировать код-произведение можно описанным в § 10.3 способом.

Второй пример дается кодом, дуальным к коду-произведению двух кодов Рида-Соломона или их подкодов над подполями. Дуальный код исправляет случайные ошибки, а также конфигурации многократных низкоплотностиых пакетов, определяемых как конфигурации, состоящие из сегментов ошибок, вес которых больше типичного. Исправляющие многократные низко-плотностные пакеты ошибок коды полезны для тех каналов, в которых происходит ритмичное изменение вероятности ошибки, например для каналов с замиранием.

В частности, дуальный к квадрату (255 239, 25)-кода Рида-Соломона код представляет собой (65 025, 64 769, 17)-код