Глава 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) записывается в виде [здесь производная от — нечетная часть Проверочные соотношения тогда дают значения в точках Эти условия определяют не более одного многочлена локаторов ошибок степени Если существуют два таких многочлена и то

откуда

где Следовательно, ввиду формулы (15.16) и теоремы 2.15,

Каждая из строк проверочной матрицы (15.14) является элементом поля Если эту матрицу продолжить на то код Сривэставы будет иметь проверочных символов. Однако в общем случае строки проверочной матрицы линейно зависимы. Ранг системы строк матрицы будет зависеть от выбора элементов Пока не известно ни одного метода хорошего выбора этих элементов.

Мало что известно и о числе информационных символов кодов Сривэставы. Во всяком случае они лишь незначительно хуже БЧХ-кодов, а в лучшем случае обеспечивают значительно большую скорость передачи информации.

Коды Сривэставы, несомненно, заслуживают дальнейшего исследования.