DESIGN OF THIRD ORDER WAVELET FILTERS OVER FINITE FIELDS BY USING SPECIAL BINOMIALS

Full Text

Введение Разработка моделей, методов и алгоритмов цифровой обработки сигналов (ЦОС) в конечных полях вызывает в последнее время повышенный интерес у исследователей. Данный факт объясняется особенностями строения конечного поля как алгебраической структуры. В конечных полях, так же, как и в полях действительных и комплексных чисел, сохраняется возможность выполнения арифметических операций сложения, вычитания, умножения и деления. С другой стороны, дискретная природа конечных полей эффективна при обработке квантованных величин, возникающих в ЦОС [1]. В настоящее время получило широкое распространение применение вейвлетов для решения разнообразных задач ЦОС. Вейвлет-преобразование возникло как альтернатива преобразованию Фурье - обработка с использованием вейвлетов позволяет получать не только частотную информацию о сигнале, но еще и его локальные особенности. В настоящее время вейвлеты широко применяются для задач сжатия сигнала [2], очистки от шума [3-4], анализа временных рядов [5], обработки данных в медицине [6] и во многих других областях. Однако в большинстве случаев на практике используются вейвлеты, построенные над полями действительных и комплексных чисел. Особенностью этих вейвлетов является относительная простота построения и применения на практике. Однако вейвлет-преобразование над полями действительных и комплексных чисел не лишено недостатков, к которым прежде всего следует отнести высокую вычислительную сложность обработки, а также неизбежное возникновение ошибок округления. Для устранения этих недостатков был разработан математический аппарат ЦОС с использованием вейвлетов конечного поля [7]. Предложены методы и алгоритмы кодирования [8-9], криптографической защиты информации [10-11] и обработки изображений [12] с использованием вейвлетов конечного поля. Одним из главных препятствий на пути использования вейвлетов конечного поля на практике является высокая сложность их построения, так как в настоящее время для этой цели используется алгоритм Берлекэмпа или его модификации [7]. В данной статье исследованы вейвлетные фильтры третьего порядка над конечными полями , построенные с использованием линейных двучленов специального вида. Представлены алгоритмы построения таких фильтров и приведены примеры. Вейвлет-преобразование в конечных полях Конечные поля (поля Галуа) делятся на два типа: простые поля и полиномиальные поля , , . Простое конечное поле содержит число элементов, равное простому числу . Любое конечное поле из элементов изоморфно полю классов вычетов по модулю , поэтому операции сложения, умножения и вычитания в могут рассматриваться как аналогичные операции над целыми числами, взятые по . Арифметика полиномиальных полей является более сложной и основана на свойствах многочленов над . В данной работе будут рассмотрены лишь простые поля . Пусть мы имеем конечное поле . Определим векторное пространство , элементы которого - вектора над полем . Предположим, что это пространство можно представить в виде прямой суммы двух подпространств , . (1) Если обозначить через линейную оболочку над векторами , то материнский вейвлет и скейлинг-функция , определяющие вейвлет-преобразование в конечном поле , должны удовлетворять следующим соотношениям [7] ; ; (2) ; , (3) и, кроме того, условиям ортонормированности базиса , ; (4) , ; (5) , . (6) Вейвлет-преобразованием в конечном поле является отображение, ставящее в соответствие вектору последовательность коэффициентов . Обратное преобразование осуществляется по формуле . (7) а) б) Рис. 1. Двухканальный набор фильтров дискретного вейвлет-преобразования: а) обычное изображение, б) изображение в многофазной форме. На практике вейвлет-преобразование реализуется при помощи наборов фильтров. На рис. 1а показан двухканальный набор фильтров дискретного вейвлет-преобразования. Здесь и - анализирующие фильтры; - оператор децимации; - оператор разрежающей выборки; и - синтезирующие фильтры. Этот же набор фильтров может быть представлен в многофазной форме (см. рис. 1б) [13]. С таким набором фильтров ассоциирована матрица , (8) элементы которой принадлежат кольцу многочленов . В конечных полях, так же как и в полях действительных и комплексных чисел, порядок фильтров, соответствующих материнскому вейвлету и скейлинг-функции должен быть нечетным [7]. Для того, чтобы набор фильтров обладал свойством точного восстановления сигнала, необходимо, чтобы матрица была параунитарной, то есть выполнялось соотношение , (9) где - единичная матрица [14]. Необходимым и достаточным условием точного восстановления сигнала является выполнение соотношения (10) между элементами матрицы (8). Пусть порядок фильтра определяется целым числом и - положительное число, такое что . Тогда многочлены и определяются следующими соотношениями: , , , (11) , , , (12) а многочлены и матрицы (8) находятся по формулам , . (13) Фильтры и можно найти по формулам ; (14) . (15) Фильтры и находятся из условий точного восстановления сигнала [1] , . (16) Построение набора фильтров на рис. 1 сводится к отысканию многочленов , и , из кольца многочленов , удовлетворяющих условию . (17) Каждая такая пара многочленов и определяет многочлены и по формулам ; , для ; (18) , для Основной сложностью при построении вейвлетных фильтров конечного поля является поиск многочленов и , удовлетворяющих условию (17). Далее будет исследован вопрос о нахождении многочленов и вида в полях для построения вейвлетных фильтров наименьшего нетривиального (третьего) порядка. Построение вейвлетных фильтров третьего порядка в полях Рассмотрим задачу о построении многочленов и из , для которых выполняется соотношение . Сформулируем и докажем вспомогательное утверждение, которое будет необходимо нам для решения поставленной задачи. Утверждение 1. Число является квадратичным вычетом по модулю для простых чисел вида и , а для простых чисел вида и является квадратичным невычетом по модулю . Доказательство. Пусть простое число имеет вид . Согласно основной теореме арифметики, любое целое число представляется в виде , (19) где различные простые числа, а , . Равенство (19) можно переписать в виде , () или , (, ). Следовательно, или . Тогда или . Рассмотрим каждый из этих случаев. 1. Пусть . Если четное число, то является квадратичным вычетом по модулю . Если нечетное число, то символ Лежандра , так как [15]. Следовательно, является квадратичным вычетом по модулю и при нечётном. 2. Пусть . Тогда символ Якоби [16] равен , учитывая что при . Следовательно, и в этом случае является квадратичным вычетом по модулю . Таким образом, является квадратичным вычетом по модулю для любых простых чисел вида . Если простое число имеет вид , то . Символ Якоби для этого случая равен . Если простое число имеет вид , то . Символ Якоби для этого случая равен , учитывая что является квадратичным невычетом по модулю . Если простое число имеет вид , то . Символ Якоби для этого случая равен . Обобщая все результаты, описанные выше, заключаем, что является квадратичным вычетом по модулю для простых чисел вида и квадратичным невычетом по модулю для простых чисел вида и . Утверждение доказано. Используя доказанное утверждение, сформулируем и докажем следующую теорему. Теорема 1. Для простых чисел вида и не существует пар многочленов и из , таких, что . Для простых чисел вида и многочлены и (20) из обладают свойством . Доказательство. Если и , то , а . Следовательно, . Если , то или . Из равенства следует, что . С учетом равенства имеем, что или . Последнее равенство возможно, в том и только том случае, если является квадратичным вычетом по модулю . Используя утверждение 1 заключаем, что, если и , то многочлены и из , для которых , не существуют. Если же и , то многочлены и из , для которых , существуют. В этом случае имеем две пары чисел и , удовлетворяющие поставленному требованию: и , а также и . Окончательно (с учетом порядка следования), имеем пару многочленов и , удовлетворяющих соотношению для и . Теорема доказана. Рассмотрим на примере процедуру построения вейвлетных фильтров третьего порядка с использованием теоремы 1. Пример 1. С помощью теоремы 1 найдем многочлены и из , для которых выполняется соотношение . Полученные многочлены приведены в таблице 1. Таблица 1. Многочлены и из Обратим внимание, что если число имеет вид , например , то в этом случае и многочлен . В таблице 1 этот случай встречается при и при . Построим теперь вейвлетный фильтр в поле с использованием многочленов и . Процесс последовательного построения многочленов , , из формул (11)-(13), а также анализирующих ( и ) и синтезирующих ( и ) фильтров схематично изображен на рис. 2. Многочлены и из теоремы 1 могут быть использованы для построения других пар многочленов, обладающих свойством . Теорема 2. Пусть , , , , , , , . Тогда, если для многочленов и из выполняется соотношение , то для и , где и выполняется соотношение . Доказательство. Преобразуем выражения , и : ; . Аналогично доказывается, что . Из этих равенств следует, что для . Аналогично доказывается, что для . Так как , то и для и , где и . Теорема доказана. Рис. 2. Схема построения анализирующих ( и ) и синтезирующих ( и ) вейвлетных фильтров из многочленов и в поле Теорема 2 дает возможность, имея пару многочленов и , для которых , построить с ее помощью ещё 15 пар многочленов и , для которых . Пример 2. В примере 1 было найдено, что в для и выполняется соотношение . Используя теорему 2 получим, что ,, , , , . Комбинируя разными способами и , где и получим 16 пар многочленов, удовлетворяющих условию . Каждая из таких пар может быть использована для построения вейвлетных фильтров третьего порядка над , аналогично схеме, показанной в примере 1. Заключение В работе исследован метод построения вейвлетных фильтров третьего порядка над полями с использованием двучленов специального вида. Показано, как предложенный подход может быть использован для построения вейвлетных фильтров над полями при и . Использование теорем 1 и 2 позволяет значительно сократить время построения вейвлетных фильтров конечного поля по сравнению с известными подходами, основанными на применениии алгоритма Берлекэмпа или его модификаций. Дальнейшая работа в данном направлении может быть направлена на исследование практического применения вейвлетных фильтров третьего порядка для задач ЦОС, а также в кодировании и шифровании. Перспективным подходом к использованию вейвлетов над полями является использование модулярной арифметики в системе остаточных классов с простыми модулями.

About the authors

Nikolay Ivanovich Chervyakov

North-Caucasus Federal University

Email: k-fmf-primath@stavsu.ru

Pavel Alekseyevich Lyakhov

North-Caucasus Federal University

Email: ljahov@mail.ru

Nataliya Fyodorovna Semyonova

North-Caucasus Federal University

References

Supplementary files