Рахман П.А. - Кодирование информации

92

Отметим, что мы ограничимся специальным частным случаем, используемым в алгебраической теории кодирования, когда старший коэффициент полинома делителя g(x)

равен единице, то есть gr 1, иным словами полином-делитель является нормированным.

Также заметим, что фактическое деление требуется только тогда, когда степень полинома Ψ(x) больше либо равна степени полинома g(x), то есть k 1 r , а в случае же k 1 r , очевидно, сам полином Ψ(x) является искомым полиномом-остатком R(x).

Следует отметить, что хотя деление полиномов, заданных над простым полем GF(2m ), во многом похоже на деление полиномов, заданных над полем действительных чисел, однако, здесь имеется один существенный момент. При делении полиномов «в столбик» используются операции умножения полинома-делителя на одночлен (в том числе на одночлен нулевой степени, то есть скаляр), а также операция вычитания полиномов. Эти операции, в свою очередь, приводят к операциям умножения и вычитания коэффициентов, которые в рассматриваемом нами случае по определению являются элементами поля GF(2m ). Соответственно, все операции с коэффициентами должны выполняться по

правилам арифметики поля GF(2m ), которые мы подробно рассматривали выше. Также отметим, что в арифметике поля GF(2m ) сложение и вычитание сводятся к одной и той же операции «побитового» XOR: a,b GF(2m ) a b a ( b) a b a b.

Пример. Вычислим остаток полинома Ψ(x) 49 x4 50 x3 51 x2 0 x 0 по модулю полинома g(x) x2 6 x 8, заданных над полем Галуа GF(28 ) , заданного с помощью неприводимого многочлена p(x) x8 x4 x3 x2 1.

R(x) 248 x 155

Таким образом, искомый полином-остаток R(x) Ψ(x)modg(x) 248 x 155.

Проверим корректность операции деления в предыдущем примере. Вычислив выражение Q(x) g(x) R(x), очевидно, мы должны снова получить исходное делимое:

Q(x) g(x) R(x) (49 x2 148 x 249) (x2 6 x 8) (248 x 155)

(49 1 x4 (49 6 148 1) x3 (49 8 148 6 249 1) x2 (148 8 249 6) x 249 8

(248 x 155) (49 x4 50 x3 51 x2 248 x 155) (248 x 155) 49 x4 50 x3 51 x2

Видим, что Q(x) g(x) R(x) 49 x4 50 x3 51 x2 не что иное, как исходный полином-делимое Ψ(x) в предыдущем примере.

Теперь остановимся на особенностях программной и аппаратной реализации вычисления остатка от полинома Ψ(x) степени k – 1 по модулю нормированного полинома

g(x)степени r, заданных над полем GF(2m ). Перепишем процедуру деления в вышеприведенном примере немного по-другому:

некоторый «остаточный» полином R(s)(x). В качестве начального «остаточного» полинома принимается полином, состоящий из старших r слагаемых полинома Ψ(x). Иными словами:

путем выполнения следующий операций:

К «остаточному» полиному R(s 1)(x), вычисленному на предыдущем шаге,

добавляется очередное слагаемое Ψk r s xk r s полинома-делимого Ψ(x). Тем самым, формируется полином (R(s 1)(x) Ψk r s xk r s).

Выбирается такой очередной коэффициент Qk r s для полинома-частного Q(x),

был равен Qk r s gr . Такой выбор является необходимым условием сходимости

коэффициентов. Поэтому с вычислительной точки зрения выгоднее хранить и обрабатывать не сам «остаточный» полином, а некоторый, так сказать, «смещенный остаточный» полином

s k r , «смещенный остаточный» полином совпадает с самим «остаточным» полиномом

и при сложении коэффициенты при xr всегда в сумме дают нуль. Это позволяет сэкономить

на одной ячейке памяти и на одной операции сложения коэффициентов при xr .

Тогда с учетом всего вышесказанного перепишем процедуру вычисления полинома-

Следует отметить, что процедура фактически сводится к последовательности операций сдвига r ячейного регистра (в каждой ячейке сдвигового регистра мы имеем m

обратной связью, причем на начальном этапе (перед непосредственным делением) загрузка коэффициентов Ψk 1 Ψk r осуществляется не параллельным, а последовательным

(сдвиговым) способом через младшую 0-ю ячейку сдвигового регистра. Соответственно, цикл работы схемы состоит из двух фаз: фаза последовательной загрузки «начального»

тактов, и фазы итерационного деления, выполняемой в течение k – r тактов. В итоге суммарно требуется k тактов для вычисления остатка. Ниже на рис. 3.1. приведена функциональная схема «вычислителя» остатка полинома Ψ(x) по модулю полинома g(x).

96

В приведенной схеме, на первой фазе, обратная связь разомкнута (сигнал Control = 0) на коммутационной схеме, обозначенной знаком , и в течение первых r тактов, q = 1…r, в регистр загружаются коэффициенты Ψk 1 Ψk r , поступающие через вход 0-й ячейки

регистра. Поскольку обратная связь разомкнута, то на схемах сложения они складываются с нулем, и поступают в регистр в неизменном виде. Во второй фазе, коммутатор замыкает обратную связь (сигнал Control = 1), и в течение k – r тактов, q = r + 1…k, на вход 0-й ячейки регистра поступают коэффициенты Ψk r 1 Ψ0, и итерационно вычисляется остаток.

Результат будет содержаться в r ячейках сдвигового регистра после завершения такта q = k. Clock – вход для тактового сигнала, по которому осуществляется запись информации

в ячейки регистра, поступающей на вход ячеек. Control – вход управления m-разрядной коммутационной схемой ( ), которая легко реализуется с помощью m двухвходовых логических элементов «И». Знаком обозначено сложение двух элементов поля Галуа GF(2m ). Сложение легко реализуется с помощью m двухвходовых логических элементов

XOR. Знаком обозначено умножение элементов поля Галуа GF(2m ). Заметим, что на

практике при аппаратной реализации схем вычисления остатка, коэффициенты gr 1 g0

полинома-делителя обычно являются константами, задаваемыми на этапе проектирования, поэтому в качестве схем умножения можно использовать быстрые и компактные «умножители на константу», которые мы рассматривали выше. Каждый из умножителей выполняет умножение на конкретную фиксированную константу gj , j 0 r 1.

Рис. 3.1. Функциональная схема последовательного вычислителя остатка полинома

97

Циклической сверткой полиномов будем называть остаток от произведения этих

полиномов по модулю полинома xr 1.

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

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

(x) 19 x2 93 x 1, заданных над полем GF(28), по модулю полинома x3 1. Имеем:

(Ψ0ξ2 Ψ1ξ1 Ψ2ξ0) x2 (51 1 50 19 49 93) (51 93 50 1 49 19) x

(51 19 50 93 49 1) x2 31 x2 103 x 233.

Вычисление формальной производной полинома. Достаточно очевидно, что вычисление производной от полинома, заданного в поле Галуа, требует особого подхода, хотя бы потому, что здесь мы, как в случае традиционной алгебры, не можем говорить о бесконечно малых величинах – в поле Галуа нет таких элементов, которые бы мы могли использовать в качестве бесконечно малого. Однако, никто нам не запрещает говорить о некоторой формальной бесконечно малой величине, обозначим ее , которая будет нами использоваться исключительно для выполнения математических преобразований для получения формальной производной от заданной функции y f x .

Кроме того, ради общности рассуждений мы рассмотрим формальную производную полинома, заданного над полем Галуа GF(pm), а затем рассмотрим частный случай производной над полем Галуа GF(2m).

Тогда, мы можем дать определение формальной производной функции f x :

98

Особо отметим, что не следует «в лоб» пытаться искать численное значение предела при конкретных значениях аргумента x. Формула задана исключительно для аналитических преобразований, подразумевающих исключение величины из итогового аналитического выражения для производной функции. Заметим, что так же, как и в традиционной алгебре, здесь справедливы следующие свойства формальной производной функции:

Теперь же выведем формальные производные для простейших функций: