Глава 15. Другие основные методы кодирования и декодирования
15.1. Коды Сривэставы — нециклические коды с алгебраическим алгоритмом декодирования
Как было показано в разд. 10.1, в качестве локаторов кода над
удобно взять элементы поля
При этом задача декодирования сводится к отысканию минимального множества локаторов ошибок
соответствующего множества величин ошибок
удовлетворяющих проверочным соотношениям. Для БЧХ-кодов более удобным оказывается не непосредственный поиск множеств
а отыскание многочлена локаторов ошибок
и многочлена значений ошибок
Степеньмногочлена (15.12) всегда меньше числа ошибок. Используя формулы (15.11) и (15.12), получаем, что
Сривэстава [1967] предложил класс линейных кодов, задаваемых проверочной матрицей вида
где I — некоторое целое число,
различные элементы пота
элементы множества
Блоковая длина кода равна
Проверочные соотношения кода Сривэставы связаны с уравнением (15.13). Они определяют величины
для
Задача декодера состоит в определении многочленов
и
по этим известным величинам. При
существует не более одной пары многочленов
и
удовлетворяющих этим условиям. В самом деле, если существует и другое решение
то для
Согласно теореме 2.15, любой многочлен степени
обладающий
корнями, есть тождественный нуль. Так как
то из (15.15) вытекает, что
. В силу взаимной простоты многочленов
это означает, что существует не более одной пары многочленов
таких, что
при заданных значениях
Следовательно, код с проверочной матрицей (15.14) исправляет любые комбинации из
ошибок. Читатель легко может проверить, что минимальное расстояние кода равно по меньшей мере
Берлекэмп [1967] предложил эффективный метод декодирования кодов Сривэставы, основанный на использовании последовательности многочленов, сходящихся к
Можно также построить эффективную процедуру декодирования, основанную на численном методе отделимых разностей, описанном Милном [1949]. Любой из подходов приводит к декодированию, которое в случае длинных кодов Сривэставы лишь незначительно сложнее, чем для сравнимых БЧХ-кодов.
При
двоичные коды Сривэставы с проверочной матрицей (15.14) на самом деле исправляют
ошибок. В двоичном случае все ненулевые значения
равны 1 и уравнение (15.12) записывается в виде
[здесь
производная от
— нечетная часть
Проверочные соотношения тогда дают значения
в точках
Эти условия определяют не более одного многочлена локаторов ошибок степени
Если существуют два таких многочлена
и
то
откуда