Комплементарное представление многочленов над конечными полями

Челябинский физико-математический журнал. 2017. Т. 2, вып. 2. С. 199-209.

УДК 519.725

КОМПЛЕМЕНТАРНОЕ ПРЕДСТАВЛЕНИЕ МНОГОЧЛЕНОВ НАД КОНЕЧНЫМИ ПОЛЯМИ

А. А. Соловьёв

Челябинский государственный университет, Челябинск, Россия alsol@csu.ru

Доказывается, что всякий многочлен над конечным полем является порождающим многочленом вейвлет-кода.

Ключевые слова: конечное поле, вейвлет-код, биортогональное преобразование.

Введение

Вейвлет-коды являются подклассом квазициклических кодов с циклическим сдвигом кодовых слов на две позиции [1]. Первоначально порождающая матрица вейвлет-кодов строилась с помощью ортогональных фильтров масштабирующей и вейвлет- функций [2; 3]. В работе [4] была предложена улучшенная схема помехоустойчивого кодирования над конечным полем с использованием биортогональных наборов фильтров точного восстановления. Вместо алгоритма факторизации использовалась лифтинговая схема [5], основанная на алгоритме Евклида нахождения НОД многочленов. Подобный подход позволил упростить и расширить возможности построения вейвлет-кодов с заданными свойствами.

Встаёт вопрос: какое место среди квазициклических кодов занимают вейвлет-коды? В работе доказывается, что класс вейвлет-кодов совпадает с подклассом 2-циркулянтных квазициклических кодов.

В поле чётной характеристики 2-циркулянтные коды являются циклическими кодами. Поэтому каждый циклический код является вейвлет-кодом.

1. Биортогональное кодирование над конечными полями нечётной характеристики

Содержание этого параграфа является кратким изложением работы [4]. В ней доказывается эквивалентность понятия биортогонального разложения векторного пространства и условия точного восстановления над конечным полем. Для двухка-нальной системы анализа-синтеза устанавливается связь с полифазным разложением. И, наконец, описывается схема биортогонального кодирования.

Рассмотрим конечное поле GF(pm), p — простое и p = 2. Положим n = pm — 1. Предположим, что найдётся пара разбиений пространства векторов GF(pm)n = V0

V0 = Vi 0 Wi = v1 0 Wi,

таких, что dim V1 = dim W1 = n/2 и dim V2 = dim W2 = n/2. В подпространствах V1 и Vi и в их дополнениях W1 и W1 выберем базисы и составим матрицы H, G, H и G из компонент базисных векторов в качестве строк. Будем говорить, что разбиения

пространства Уо удовлетворяют условиям биортогональности, если

НН* = In/2, сС = 1п/2,

НС* = Оп/2, ОН* = Оп/2 , и удовлетворяют условию точного восстановления, если

н'Н + с* С = 1п-

Здесь и далее символом I будем обозначать единичную матрицу, а символом О — нулевую матрицу. Нижний индекс указывает на размер квадратной матрицы, верхний индекс Ь означает транспонирование.

В следующих двух теоремах формулируются критерии точного восстановления. Доказательства этих теорем приведены в работе [4].

Теорема 1. [4]. Для двух разбиений пространства У0 вида (1), заданных двумя парами матриц Н, С и Н, С, условие биортогональности (2) выполняется тогда и только тогда, когда выполняется условие точного восстановления (3).

Матрицу размера п/2 х п, каждая строка которой, начиная со второй, получается двойным циклическим сдвигом вправо предыдущей строки, будем называть 2-циркулянтной матрицей и обозначать как с\г2(ао, а1,... , ап-\).

В биортогональном кратномасштабном анализе разложение сигнала осуществляется при помощи свёртки с парой фильтров (к, д), а восстановление — при помощи свёртки с другой парой фильтров — (к,Рр). Процедура разложения и восстановления описываются 2-циркулянтными матрицами

Н = с\г2(ко, кг,..., К-1), С = сп^ (до ,д1,..., дп-г), Н = с1г2(ко, кг,..., кп-г), С = аг2 (до ,Р1,... ,Рп-1),

которые должны удовлетворять условию точного восстановления (3).

Для построения требуемых фильтров воспользуемся лифтинговой схемой на основе алгоритма Евклида нахождения НОД в усечённом кольце полиномов над конечным полем СЕ(д)[х]/(хп — 1), д = рт (см. [5]). Фильтру к = {ккЩ-о поставим в соответствие многочлен

п— 1

к(х) = ^^ к^хг = ко + кгх + к2х2 + ... + кп-1хп-1.

г=о

Многочлен к(х) представим в виде суммы полифазных компонент

к(х) = ке(х2) + хк0(х2),

где ке(х) содержит только чётные компоненты и к0(х) — только нечётные компоненты:

п/2-1 п/2-1

ке(х) = ^ к2кхк, ко(х) = ^ к2к+1хк. к=о к=о

С фильтрами д, дк и дд поступим подобным же образом. Все полифазные компоненты рассматриваются как элементы кольца СЕ(ц)[х]/(хп/2 — 1). Введём в рассмотрение полифазные матрицы

Р (х) =

ке

ко

Р

ке

дк0

и воспользуемся далее полифазным представлением условия точного восстановления.

Теорема 2. [4]. Для двухканальной схемы анализа-синтеза условие точного восстановления выполняется тогда и только тогда, когда полифазные матрицы Р и Р пар фильтров (Л, д) и (Л, р связаны соотношением

Р (х)Р(хп/2-1)4 = I

п/2.

Фильтры Л и д называются комплементарными, если определитель соответствующей полифазной матрицы равен 1. Для комплементарных фильтров Л и д многочлены Ле(х) и Л0(х) взаимно просты.

По фильтру Л всегда можно построить пару комплементарных фильтров (Л, д) и пару двойственных фильтров (Л,р так, чтобы выполнялось условие точного восстановления (4) (см. [5]).

Алгоритм Евклида нахождения НОД для полифазных компонент фильтра Л приводит к соотношению

Ле

Ло

п

г=1

9г(х) 1 1 0

к 0

К — еош^

которое позволяет построить фильтр д, комплементарный Л:

п

г=1

9г(х) 1 10

к0

0 (—1)т1/К

Ле

Л0(х) д0(х)_

Р (х).

Ясно, что Р(х) = 1.

С помощью лифтинга [5] по паре (Л, д) можно построить другие комплементарные пары фильтров (Л, д8) с полифазной матрицей

Рв

1 з(х) 01

где з(х) € (д)[х]/(хп/2 — 1), д = рт. Фильтр д3, комплементарный Л, определяется следующим образом: д8(х) = д(х) + Л(х)в(х2).

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

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

Ле(х) = д0(хп/2-1), Л0(х) = —де(хп/2-1), де (х) = —Л0(хп/2-1), д0(х) = Ле(хп/2-1).

Из этих соотношений и (4) следует, что двойственная пара фильтров (Л, р) находится из соотношений

р(х) = —хд(—хп-1), р(х) = хЛ(—хп-1).

В [2] и [3] процедура вейвлет-кодирования определена как умножение информационного многочлена ^(х2) на порождающий многочлен кода вида Л(х) + ах2д(х), где Л(х) и д(х) — комплементарная пара фильтров, а € ^.

2. Описание вейвлет-кодов над конечным полем нечётной характеристики

В этом разделе будет доказана теорема о том, что всякий многочлен степени не более п — 1 представим в виде к(х) + ах2д(х), где (к(х),д(х)) — комплементарная пара фильтров.

Введём процедуру кодирования с помощью полифазных компонент

Ce

he

1

ax

v(x) =

he

v

где v(x) — информационный многочлен степени не выше n/2 — 1, a Е GF(q) — константа, c(x) — кодовый многочлен. Предложенная схема полифазного кодирования является схемой биортогонального вейвлет-кодирования (см. [4]), так как

he(x2) + ax2ge(x2) + x(ho(x2) + ax2 go(x2)) = h(x) + ax2g(x).

Пары комплементарных фильтров (h, g) и (h, g) со свойством точного восстановления обеспечивают возможность синдромного декодирования кодового многочлена c(x). В самом деле, для a Е Fq и b Е Fq, таких, что ab = (p — 1) modp, имеем

[he(xn/2-1) + bxn/2-1~ge(xn/2-1) ho(xn/2-1) + bxn/2-1~g0(xn/2-1)] x

he

x

ho

=

+ (—ge(x) + bxn/2-1 he(x))(ho(x) + axgo(x)) = = (go(x)he(x) — ge(x)ho(x)) + abxn/2(—ho(x)ge(x) + he(x)go(x)) = = 1 + ab • 1 = [1 + (p — 1)] mod p = 0.

Отметим, что преобразование кодирования инъективно. В частности, по кодовому многочлену восстанавливается информационный:

[he(xn/2-1) ~ho(xn/2-1)]

he

= go(x)(he(x) + axge(x)) — ge (x)(ho(x) + axgo(x)) = = (go(x)he(x) — ge(x)ho(x)) = 1.

Теорема 3. Для всякого многочлена f (x), deg f ^ n — 1, над полем GF(pm) найдётся комплементарная пара фильтров (h(x),g(x)), степени которых не превосходят n — 1, такая, что f (x) = h(x) + ax2g(x) mod (xn — 1), где a Е Fq, a = 0.

Доказательство. Пусть f (x) — многочлен степени ^ (n — 1):

f (x) = fo + fix + ...fn-ixn-1.

Убедимся в том, что последовательность f0, f1,... , fn-1) принадлежит одному из вейвлет-кодовых пространств.

Выберем в поле Fq примитивный элемент а. В точках x = аг должно выполняться условие комплементарности

he(a2l)g0(a21) — h0(a2l)ge(a21) = 1, г = 0,1,...,n — 1.

Принадлежность вектора (/0, /ь... , /п-1) кодовому пространству, согласно (5), проверяется условием

(#0(х) - ЬхП-1Л.0(ж)) /е(х) + ( - 0е(ж) + ЬхП-1 Ъе(х)) /0(х) = 0.

В точке х = а2* проверочное условие запишется в виде

(у0(а2*) - 6а-2^0(а2*))/е(а2г) + ( - Уе(а2*) + Ьа^Ма^Ща2*) = 0.

Составим систему линейных уравнений:

М«2г)р0

-р0(а2/(а2г) + ре(а2г)/0(«2г), г = 0

Определитель г-й системы относительно Ъе(а2*) и Ъ0(а2г) имеет вид

Уо

Ьа-270

п - 1

Ьа-2^Ре(«2г)/0(«2г) - £0(а2г)/е(а2*) = Ьа-2*А*

Если вторая строка матрицы ненулевая, то система уравнений относительно Л,е(а2г) и Л,0(а2г) перепишется в виде

йе(а2гЫ«2г) - й0(а2*Ы«2г) = 1, -Ъ (а2*)/о(а2*) + Ма2/ (а2* ) =

аа2*(-р0(а2*)/е(а2*) + Уе (а2*)/0(а2*)) = аа2*А

Матрица системы имеет вид

Определитель матрицы равен - А. Выберем у0 (а2*) и де(а2г) так, чтобы определитель системы равнялся единице, то есть - А =1. Тогда обратная матрица запишется в виде

/е(а2*) £е(а2У

/о

Выполним проверку:

#о

-/о

,2г\ г /

X

/е

2г\ г /

^0

0

-/0

-А*

0 -А*

-А ,,/2

= -= ^х2.

Перепишем систему в матричном виде:

у0(а2*) -0е (а2*)! Ъ (а2*)" 1 1

-/о(а2*) /е (а2*) _ _Ъ0(а2*)_ аа2*А * - аа2*

0

Тогда

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

к е

к0

¡е

1

X —аа2г

ке(а2г) = ¡е(а) — аа де(а),

к0

и к(аг) = Не(а2г) + агк0(а2г) = ¡(аг) — аа2гд(аг). В результате получаем

к(аг) + аа2гд(аг) = ¡ (аг), г = 0 ...и — 1.

Выполняя обратное преобразование Фурье, находим, что в рассматриваемом случае к(х) + ах2д(х) = ¡ (х).

Если вторая строка матрицы системы (6) нулевая, то второе уравнение системы выполняется тождественно. Добьёмся того, чтобы к(аг) и д(аг) удовлетворяли (7) и условию

к

Выберем д0(а2г) = 0 и перепишем (8) следующим образом:

ке (а2г) + аа2где (а2г) + аг(к0 (а2г) + аа2гд0(а2г)) = 0.

Умножим это соотношение на д0(а2г) и вычтем из условия комплементарности.

Получим д0(а2г)ке(а2г) + аа2где(а2г)д0(а2г) + аг(к0(а2г)д0(а2г) + аа2гд0(а2г)д0(а2г)) = 0 ------- -------------- _ --------- , /^

и —к0(а2г)де (а2г) — аа2где (а2г)д0(а2г) — аг( к0(а2г)д0(а2г) + аа2гд0(а2г)д0(а2г)) = 1 или — к0(а2г)(де(а2г) + агд0(а2г)) = аа2г(де(а2г)д0(а2г) + агд0(а2г)д0(а2г)) + 1. Поэтому

К(а2г)(де (а2г) + агд0(а2г)) = —аа2гд0(а2г)(де (а2г) + агд0(а2г)) — 1.

В результате получаем

1

к0(а2г) = —аа2гд0(а2г)--Г~2%\ ! г ( 2гу

де

Подставляя к0(а2г) в условие комплементарности, найдём ке(а2г):

ке (а) = —ааде (а) +

а

де (а2г) + агд0(а2г)'

Тогда ке(а2г) + агк0(а2г) = —аа2г(де(а2г) + агд0(а2г)). Выберем де(а2г) таким образом, чтобы де(а2г) + агд0(а2г) = 0. В этом случае для выбранных де(а2г), д0(а2г) и найденных ке(а2г) и к0(а2г) выполняется равенство к(аг) + аа2гд(аг) = 0.

Для рассматриваемых г = 0,... , п — 1 элементы поля а2г все различны. Поэтому

П _ 1 П _ 1

по найденным {ке(а2г)}2=0 и {к0(а2г)}2=0 из системы линейных уравнений находим

• 1

к0,к1,... , кп-1, а значит, находим к(х). Аналогично по выбранным {де(а2г)}2=0 и • 1

{д0(а2г)}2=0 находим д(х). Таким образом, вектор ¡0, ¡1,... , ¡п-1 для найденных к(х) и д(х) удовлетворяет проверочному соотношению и условию комплементарно-сти. Приходим к выводу, что можно подобрать комплементарную пару фильтров к(х) и д(х), такую, что вектор ¡о, ¡1,..., ¡п-1 является кодовым вектором вейвлет-кода. Теорема доказана.

Так как всякий линейный циклический код является дважды циклическим, то порождающая функция циклического кода является порождающей функцией вейвлет-кода. Таким образом, кодовое вейвлет-пространство совпадает с кодовым пространством 2-циклического кода.

3. Полиномиальная схема построения циклического

биортогонального вейвлет-кода в поле характеристики два

Выберем в поле ^2т примитивный элемент а. Опишем биортогональные циклические вейвлет-коды длины п = 2т — 1 с длиной информационного слова 1.

Фильтру Н с импульсным откликом {Н& }П=о поставим в соответствие многочлен

n— 1

h(x) = ^^ hx1 = h0 + h1 x + ... hn—1x

n—1

i=0

Представим многочлен h(x) в виде суммы полифазных компонент h(x) = he(x2) + xho(x2), где

(n—1)/2 (n—3)/2

he(x) = ^ h2k xk, h0(x) = ^ h2fc+1xk. fc=0 fc=0

n1

Наряду с фильтром h рассмотрим фильтр g = {gkЩ=0.

Введём полифазную матрицу

P (x) =

he

ho

Фильтры Н и g комплементарны, если det Р(ж) = 1.

Пусть V = (ь0 ... ) — вектор с компонентами из С^1 (2т). Дискретным преобразованием Фурье является вектор V = Т(V) = ("о,... , с компонентами

п— 1

" = ^ а*Ь, ^ = 0,..., п — 1.

г=0

Обратное преобразование Фурье восстанавливает исходный вектор V:

n1

Vj, i = 0,...,n - 1.

i=0

Определение. Полифазные компоненты кодового многочлена с(ж) в кольце С^1 (2т)[ж]/(жп — 1) определим следующим образом:

v(x2).

Ce(x2) he(x2) ge(x2) 1

c0(x2)_ h0(x2) g0(x2) x2

Здесь v(x) = jn=0 )/ Vjxj — информационный многочлен степени не выше п=—, и длина информационного слова равна п==1.

В определении и в последующих рассуждениях умножение производится в кольце F2m [x]/(xn - 1).

Кодовый многочлен c(x), как и при биортогональном кодировании, запишется в виде

c(x) = ce(x2) + xco(x2) = (h(x) + x2g(x)) v(x2) mod (xn — 1).

Многочлен F(x) = h(x) + x2g(x) будем называть порождающим.

Вместе с парой фильтров (h, g) рассмотрим пару комплементарных фильтров (h, g) с полифазной матрицей

P

he

h0

V

Введём условие точного восстановления Р(х2)Р(хп-1) = 12х2, отличное от условия точного восстановления в поле нечётной характеристики (см. (4)).

Согласно правилу Крамера связь между полифазными компонентами (к,д) и (к, д) выражается соотношениями

go(x2) = he(xn-i), ge(x2) = — ho(xn-1), ho (x2) = —ge(xn-1), he(x2) = ~go(xn-1).

Информационное слово восстанавливается по кодовому с помощью фильтров к и д. В самом деле,

[he(xn-1 ) ~ho(xn-1)}

he (x2) ge(x2) 1

ho(x2) go(x2)_ x2

= [go(x2) -ge(x2)]

= (he(x2)go(x2) — ge(x2)ho(x2)) + x2 (go(x2)ge(x2) — ge(x2)go(x2)) = 1. Если порождающая матрица имеет вид

G =

he

e

ho

то проверочная матрица запишется в виде

Н = [ке(хп-1) + хп-2де(хп-1) к0(хп-1) + хп-2 до(хп-1

Учитывая (9), проверочное соотношение при вейвлет-кодировании перепишется следующим образом:

[go(x2) — xn 2ho(x2) — ge(x2) + xn 2he(x2

fe

0.

Выполнив действия, представим проверочное соотношение в виде

— xn-2fe

или

fo

Более подробное изложение схемы построения биортогональных вейвлет-кодов в поле характеристики 2 можно найти в работе [6].

4. Описание вейвлет-кодов над полем характеристики 2

Пусть ¡(х) — многочлен степени не выше и — 1. Покажем, что найдутся ком-

плементарные фильтры h(x) = 5^n=o hjxj и g(x) = ^П=о gjxj с порождающим многочленом h(x) + x2g(x) mod (xn — 1), равным f (x).

Теорема 4. Для всякого многочлена f (x), deg f ^ n — 1, над полем GF (2m) найдётся комплементарная пара фильтров (h(x), g(x)), степени которых не превосходят n — 1, такая, что f (x) = h(x) + x2g(x) mod (xn — 1).

Доказательство. В точках x = аг условие комплементарности запишется в виде he(a2i)go(a2i) — h0(a2i)ge(a2i) = 1, г = 0,...,n — 1.

Принадлежность вектора (/0, /1,... , /п—1) вейвлет-кодовому пространству проверяется условиями

ge (а2>7о(а2г) — g0(а2V /е(а2г) = Не(а2г)а_г/о(а2г) — Н0(а2г)а_г/е(а2г) при г = 0,1,... , п — 1. Составим систему линейных уравнений:

Не(а2%0(а2г) — Н0(а2*Ыа2г) = 1, Не(а2г)/о (а2г) — Н0(а2г)/(а2г) = а2гА,

где Аг = ge(а2i)/0(а2i) — g0(а2i)/e(а2i).

Определитель г-й системы относительно Не(а2г) и Но(а2г) имеет вид

Аг.

Если вторая строка матрицы ненулевая и Аг = 0, то система уравнений (10) имеет единственное решение. Выберем ge(a2г) и go(а2г) так, чтобы Аг = 0. Тогда Не(а2г) и Но(а2г) определятся из системы (10). А именно: Но(а2г) = —А—1/0(а2г) + а2^о(а2г) и Не(а2г) = —А—1/е(а2г) + а2^е(а2г). Отсюда находим, что

^ (аг) = Н(аг) + а2^(аг) = —А_1/(аг).

Ничто не мешает выбрать ge(а2г) и go(а2г) так, чтобы А—1 = —1. Для таких г получаем, что ^(аг) = /(аг).

Если же вторая строка определителя Аг нулевая, то второе уравнение выполняется тождественно. В этом случае выберем ge(a2г), go(а2г), Не(а2г) и Но(а2г) так, чтобы выполнялось условие комплементарности и имело место равенство

Н(аг) + а2^(аг) = 0.

Перепишем это соотношение в виде

Не(а2г) + а2^(а2г) + аг(Н0(а2г) + а2^0(а2г)) = 0.

Добьёмся того, чтобы система

'Н(а2гЫа2г) — Н0(а2гЫа2г) = 1, Не(а2г) + а2^е(а2г) + аг(Н0(а2г) + а2^0(а2г)) = 0

была разрешима.

Выберем go(а2г) не равным нулю. Умножим последнее соотношение в системе на go(a2г) и вычтем из условия комплементарности. Получим

—Н0(а2гЫа2г) — а2^(а2%0(а2г) — агН0(а2%0(а2г) — а3^0(а2%0(а2г) = 1.

Выразим Но(а ):

Но(а2г) =--г ( 2А — а2^0(а2г).

ge

Подставляя найденное Но

Не

Выберем де(а2г) таким образом, чтобы де(а2г) + агд0(а2г) = 0. В этом случае для найденных к0(а2г), ке(а2г) д0(а2г) и де(а2г) выполняется равенство

к(аг) + а2гд(аг) = 0.

Таким образом, в первом случае, в предположении f (аг) = 0, д0(а2г) и де(а2г) выбирались так, чтобы Аг = — 1, и были построены к0(а2г), ке(а2г), для которых верно равенство Е(аг) = к(аг) + а2гд(аг) = f (аг).

Во втором случае, когда f (аг) = 0, д0(а2г) и де(а2г) выбирались так, чтобы д0(а2г) = 0 и де(а2г) + агд0(а2г) = 0. Тогда для найденных к(аг) выполняется равенство к(аг) + а2гд(аг) = f (аг) = 0.

Так как в поле характеристики 2 все а2г различны, г = 0,1,... ,п — 1, то из системы линейных уравнений относительно к0,к\,... , кп-\ находится многочлен к(х). Построенные многочлены к(х) и д(х) таковы, что для порождающего многочлена вейвлет-кода Е(х) = к(х) + х2д(х) спектральный многочлен ^Т—о Е(аг)у^ совпадает со спектральным многочленом У~]П-п f (а%)У^. Поэтому порождающий многочлен вейвлет-кода совпадает с многочленом f (х).

В частности, доказано, что всякий порождающий многочлен циклического кода является порождающим многочленом вейвлет-кода.

Построенное представление многочлена над полем Ед будем называть комплементарным.

Список литературы

1. Мак-Вильямс, Ф. Дж. Теория кодов, исправляющих ошибки / Ф. Дж. Мак-Вильямс, Н.Дж.А.Слоэн. - М. : Связь, 1979. - 744 с.

2. Double circulant self-dual codes using finite-field wavelet transforms / F. Fekri, S.W. McLaughlin, R. M. Mersereau and R. W. Schafer // Applied Algebra, Algebraic Algorithms and Error Correcting Codes Conf. (Honolulu, HI, 1999). Lecture Notes in Computer Sciences. - 1999. - Vol. 1719. - P. 355-364.

3. Error Control Coding Using Finite-Field Wavelet Transforms / F. Fekri, S.W. McLaughlin, R. M. Mersereau and R. W. Schafer // Atlante : Center for Signal Image Processing, Georgia Inst. of Technology. - 1999. - No. 30332. - P. 1-13.

4. Chernikov, D. V. Error-correcting codes using biorthogonal filter banks / D. V. Chernikov // Siberian Electronic Mathematical Rep. - 2015. - Vol. 12. - P. 704-713.

5. Doubechies, I. Factoring wavelet transforms into lifting steps / I. Doubechies, W. Sweldens // The J. of Fourier Analysis and Applications. - 1998. - Vol. 4, no. 3. -P. 247-269.

6. Соловьев, А. А. Биортогональный вейвлет-код в полях характеристики два / А. А. Соловьев, Д. В. Черников // Челяб. физ.-мат. журн. - 2017. - Т. 2, вып. 1. -С. 66-79.

Поступила в редакцию 10.05.2017 После переработки 24.06.2017

Сведения об авторе

Соловьёв Александр Артёмович, доктор физико-математических наук, профессор, заведующий кафедрой компьютерной безопасности и прикладной алгебры, Челябинский государственный университет, Челябинск, Россия; e-mail: alsol@csu.ru.

Chelyabinsk Physical and Mathematical Journal. 2017. Vol. 2, iss. 2. P. 199-209.

COMPLEMENTARY REPRESENTATION OF POLYNOMIALS OVER FINITE FIELDS

A.A. Soloviev

Chelyabinsk State University, Chelyabinsk, Russia alsol@csu.ru

In the paper it is proved that every polynomial over a finite field is a generating polynomial of the wavelet-code.

Keywords: finite field, wavelet-code, biorthogonal transform.

References

1. MacWilliams F.J., Sloane N.J.A. Teoriya kodov, ispravlyayushchikh oshibki [The theory of error-correcting codes]. Moscow, Svyaz' Publ., 1979. 744 p. (In Russ.).

2. Fekri F., McLaughlin S.W., Mersereau R.M., Schafer R.W. Double circulant self-dual codes using finite-field wavelet transforms. Applied Algebra, Algebraic Algorithms and Error Correcting Codes Conference (Honolulu, HI, 1999), Lecture Notes in Computer Sciences, 1999, vol. 1719, pp. 355-364.

3. Fekri F., McLaughlin S.W., Mersereau R.M., Schafer R.W. Error Control Coding Using Finite-Field Wavelet Transforms. Atlanta, Center for Signal Image Processing, Georgia Institute of Technology, 1999, no. 30332, pp. 1-13.

4. Chernikov D.V. Error-correcting codes using biorthogonal filter banks. Siberian Electronic Mathematical Reports, 2015, vol. 12, pp. 704-713.

5. Doubechies I., Sweldens W. Factoring Wavelet Transforms into Lifting Steps. The Journal of Fourier Analysis and Applications, 1998, vol. 4, no. 3, pp. 247-269.

6. Soloviev A.A., Chernikov D.V. Biortogonal'nyy veyvlet-kod v polyakh kharakteristiki dva [Biorthogonal wavelet code in fields of characteristic two]. Chelyabinskiy fiziko-matematicheskiy zhurnal [Chelyabinsk Physical and Mathematical Journal], 2017, vol. 2, iss. 1, pp. 66-79.

Accepted article received 10.05.2017 Corrections received 24.06.2017