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

Abstract


This work is concerned on research of method for design of third order wavelet filters in finite fields by using special binomials. Finite field wavelets have many advantages in comparison with real or complex field wavelets. The main two of them are high rate data processing and lack of rounding error. However, the main disadvantage of finite field wavelets is high complexity of design based on using of polynomial properties and para-unitary matrixes over finite fields. The most known methods for design of finite filed wavelets utilize computing system based on Berlekamp algorithm or its modifications for polynomial expansion over finite field. We propose new method for design of third order wavelet filters over finite field. Presented method is based on using of special type binomials over those fields. We derived and proved analytical formulas for filter coefficient and demonstrated some examples.

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

  1. Cooklev T., Nishihara A., Sablatash M. Theory of filter banks over finite fields // Proc. IEEE Asia-Pacific Conf. On Circuits and Systems, Taipei, 1994. - Р. 260-265.
  2. Usevitch B.E. A tutorial on modern lossy wavelet image compression: foundations of JPEG 2000 // IEEE Signal Processing Magazine. V.18, No.5, 2001. - Р. 22-35.
  3. Zhang D., Bao P., Xiaolin Wu. Multiscale LMMSE-based image denoising with optimal wavelet selection // IEEE Transactions on Circuits and Systems for Video Technology. V.15, No.4, 2005. - Р. 469-481.
  4. Shukla K.K., Tiwari A.K. Efficient Algorithms for Discrete Wavelet Transform With Applications to Denoising and Fuzzy Inference Systems Series. SpringerBriefs in Computer Science, 2013.
  5. Fu-Chiang Tsui, Li C.-C., Mingui Sun, Sclabassi R.J. A comparative study of two biorthogonal wavelet transforms in time series prediction // Proc. IEEE Int. Conf. on Systems, Man, and Cybernetics, Computational Cybernetics and Simulation, Orlando. V.2, 1997. - Р. 1791-1796.
  6. Brechet L., Lucas M.-F., Doncarli C., Farina D. Compression of Biomedical Signals With Mother Wavelet Optimization and Best-Basis Wavelet Packet Selection // IEEE Transactions on Biomedical Engineering. V.54, No.12, 2007. - Р. 2186-2192.
  7. Fekri F., Mersereau R.M., Shafer R.W. Theory of wavelet transform over finite fields // Proc. IEEE Int. Conf. on Acoustics, Speech, and Signal Processing, Phoenix. V.3, 1999. - Р. 1213-1216.
  8. Sartipi M., Delgosha F., Fekri F. Two-Dimensional Half-Rate Codes Using Two-Dimensional Finite-Field Filter Banks // IEEE Transactions on Signal Processing. 2007. V.55, No.12, 2007. - Р. 5846-5853.
  9. Fekri F., McLaughlin S.W., Mersereau R.M., Schafer R.W. Block error correcting codes using finite-field wavelet transforms // IEEE Transactions on Signal Processing. V.54, No.3, 2006. - Р. 991-1004.
  10. Delgosha F., Fekri F. Stream cipher using finite-field wavelets // Proc. IEEE Int. Conf. On Acoustics, Speech, and Signal Processing. V.5, 2005. - Р. 689-692.
  11. Delgosha F., Fekri F. Public-key cryptography using paraunitary matrices // IEEE Transactions on Signal Processing. V.54, No.9, 2006. - Р. 3489-3504.
  12. Chervyakov N.I., Lyakhov P.A., Babenko M.G. Digital filtering of images in a residue number system using finite-field wavelets // Automatic Control and Computer Sciences. V.48, No.3, 2014. - P. 180-189.
  13. Vaidyanathan P.P. Multirate Systems and Filter Banks. Englewood Cliffs, NJ: Prentice-Hall, 1993.
  14. Phoong S., Vaidyanathan P.P. Paraunitary filter banks over finite fields // IEEE Transactions on Signal Processing. V.45, No.6, 1997. - P. 1443-1457.
  15. Виноградов И.М. Основы теории чисел. СПб.: Лань, 2009. - 176 с.
  16. Сизый С.В. Лекции по теории чисел. М.: Физматлит, 2007. - 192 с.

Statistics

Views

Abstract - 22

PDF (Russian) - 0

Cited-By


Article Metrics

Metrics Loading ...

PlumX

Dimensions


Copyright (c) 2015 Chervyakov N.I., Lyakhov P.A., Semyonova N.F.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies