Аппаратная реализация циклического кодирования

Рекуррентные соотношения деления многочленов над GF(q)

Напомним, что, согласно соотношению (1.18) деления многочленов с остатком (см. подпараграф 1.3.2), для любых двух многочленов а(х) и Ь(х) над GF(q) можно записать:

где г(х) - остаток от деления, степень которого не превосходит степень а(х).

При этом равенство степеней а(х) и г(х) возможно только в случае, если степень Ь(х) меньше степени а(х). При этом Q(x) = 0 и г(х) = а(х).

Пусть п - степень а(х), к - степень Ь(х).

1. Пусть а(х) и Ь(х) - многочлены одинаковой степени п = к и п > 0 (далее всегда будем иметь в виду, что п > 0). Тогда:

Выразим Q(x) и г(х):

Таким образом, при п = к:

2. Пусть к- п-1:

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

где С/(х) - многочлен промежуточного результата. В данном случае / = 1,2.

3. Продолжая рассуждения, для любого п>к можно записать:

где с,(х) - многочлен переменной степени т = m(i), которая принимает значение п при / = 0 и далее при каждом следующем / уменьшается на 1:

Так как степень остатка г(х) не превосходит к - 1, то максимальное значение / (обозначим его /max) - это первое значение i, при котором m(i) < к или ш(/тах) = = /с-1.

Согласно соотношению (2.29), m[i + 1 ) = n-i, откуда n-imax = к-1. Тогда:

где п - степень делимого, к - степень делителя.

Таким образом:

>

Рассмотрим многочлен с,(х) из соотношения (2.31):

где с(Д / = 0,1,2,..., п- к + 1 - коэффициент при степени s = 0,1,2,..., т неопределенной переменной.

Очевидно, при i = 0 с, (х) = со(х) = а(х), а искомый остаток г(х) равен многочлену с(х) при i = п - к + 1.

Переменный множитель h из соотношения (2.31) принимает значения:

Подставим запись Ь(х) в соотношение (2.31) и запишем многочлен c/ + i(x):

Из последнего соотношения можно выразить искомые рекуррентные формулы для выражения коэффициентов многочлена с,(х), i = 0,1, 2.....п - к + 1:

Основу функциональной схемы аппаратного деления многочленов составляет часть равенств (2.32), выделенная фигурной скобкой.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >