10.6. ДЕКОДИРОВАНИЕ МНОГОМЕРНЫХ КОДОВ

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

Тогда соответствующая компонента двумерного синдрома для конфигурации ошибок веса определяется равенством

и может быть вычислена по принятому слову

Опишем теперь конфигурацию ошибок, используя строчные локаторы, столбцовые локаторы и величины ошибок. Локаторы в строке и столбце определяются соответственно равенствами Величину ошибки обозначим Компоненты синдрома при этом принимают вид

Двумерные коды естественно определять так, чтобы система выписанных выше уравнений была разрешима относительно при Например, проверочные частоты можно выбрать так, чтобы получилась следующая система уравнений:

которая уже встречалась в описании алгоритма декодирования кода Рида-Соломона. Имеется только одно отличие: не обязательно различны, так как в одном и том же столбце может произойти несколько ошибок. Можно, однако, сгруппировать ошибки с одинаковыми и это приведет к аналогичной системе с меньшим которое также удовлетворяет условию Тогда опять можно воспользоваться алгоритмом Берлекэмпа-Месси и рекуррентным продолжением для вычисления хотя

такая процедура не дает однозначного решения для пар при так как некоторые ошибки попадают в один и тот же столбец. В общем случае для справедлива следующая теорема, которую можно обобщить, заменив на

Теорема 10.6.1. Предполооким, что произошло ошибок и что для любых целых а известны компоненты синдрома при Тогда компоненты синдрома при определяются однозначно.

Доказательство. Нам даны уравнений для

Обозначим через число различных величин при всех через различные значения в этом наборе, а через сумму всех множителей при фиксированном в данном уравнении (она имеет одно и то же значение для всех Тогда

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

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

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

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

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

где некоторые целые числа, однозначно определяет конфигурацию ошибок.

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

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

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

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