Главная > Разное > Теория кодирования и теория информации
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

11.5. Многочлены или векторы?

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

Можно считать, что такая точка зрения соответствует тому, что кодовые последовательности нулей и единиц задаются теперь своими производящими функциями.

Другим примером является последовательность 0, 1, 1, 0, 1, которой отвечает многочлен

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

Сложение ассоциативно, т. е.

Нулевая последовательность (0, 0, 0, 0, 0) соответствует нулевому многочлену. Поскольку каждый ненулевой многочлен совпадает со своим обратным относительно сложения и сумма двух многочленов снова является многочленом той же (точнее, не большей) степени, то множество всех многочленов данной степени

образует группу. Напомним, что коэффициентами многочленов могут быть только или 1.

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

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

В разд. 2.8 показано, почему в качестве основания следует брать простое число. Простое основание обладает тем свойством, что если произведение двух чисел равно 0, то по крайней мере одно из них равно 0. Если основание не является простым, то может случиться, что произведение двух чисел, каждое из которых отлично от нуля, оказывается нулевым. Аналогично, в качестве многочлена-основания следует брать простой многочлен. Простым называется такой многочлен, который нельзя представить в виде Ироизведения двух нетривиальных многочленов меньшей степени коэффициентами в том же поле).

Коэффициент при старшей степени у многочлена степени может случайно оказаться равным 0, так что фактически многочлен рудет иметь меньшую степень. Коэффициентами могут быть только Элементы поля или 1; многочлен, у которого коэффициент при старшей степени равен 1, будет называться унитарным.

У читателя может возникнуть вопрос: «Для чего нужно перемножать многочлены?» Ответ состоит в том, что в рассматриваемые в теории объекты желательно ввести как можно больше симметрии и упорядоченности. В этом и только в этом случае полуденные коды будут достаточно симметричными и упорядоченными, гак что можно надеяться, что аппаратура кодирования и декодирования будет иметь простую структуру (т. е. ее будет легко сконструировать или реализовать в виде программы для ЭВМ). На практике обычно нежелательно иметь случайные или недостаточно Структурированные коды.

<< Предыдущий параграф Следующий параграф >>
Оглавление