ПОСТРОЕНИЕ В КОНЕЧНЫХ ПОЛЯХ ВЕЙВЛЕТНЫХ ФИЛЬТРОВ ТРЕТЬЕГО ПОРЯДКА С ИСПОЛЬЗОВАНИЕМ ДВУЧЛЕНОВ СПЕЦИАЛЬНОГО ВИДА
- Авторы: Червяков Н.И.1, Ляхов П.А.1, Семенова Н.Ф.1
-
Учреждения:
- Северо-Кавказский Федеральный университет
- Выпуск: Том 13, № 2 (2015)
- Страницы: 111-117
- Раздел: Статьи
- URL: https://journals.eco-vector.com/2073-3909/article/view/56028
- DOI: https://doi.org/10.18469/ikt.2015.13.2.01
- ID: 56028
Цитировать
Полный текст
Аннотация
В работе исследован метод построения вейвлетных фильтров третьего порядка над конечными полями с использованием двучленов специального вида. Использование предложенного подхода позволяет значительно сократить время построения вейвлетных фильтров конечного поля по сравнению с известными методами, основанными на применении алгоритма Берлекэмпа или его модификаций.
Ключевые слова
Полный текст
Введение Разработка моделей, методов и алгоритмов цифровой обработки сигналов (ЦОС) в конечных полях вызывает в последнее время повышенный интерес у исследователей. Данный факт объясняется особенностями строения конечного поля как алгебраической структуры. В конечных полях, так же, как и в полях действительных и комплексных чисел, сохраняется возможность выполнения арифметических операций сложения, вычитания, умножения и деления. С другой стороны, дискретная природа конечных полей эффективна при обработке квантованных величин, возникающих в ЦОС [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 позволяет значительно сократить время построения вейвлетных фильтров конечного поля по сравнению с известными подходами, основанными на применениии алгоритма Берлекэмпа или его модификаций. Дальнейшая работа в данном направлении может быть направлена на исследование практического применения вейвлетных фильтров третьего порядка для задач ЦОС, а также в кодировании и шифровании. Перспективным подходом к использованию вейвлетов над полями является использование модулярной арифметики в системе остаточных классов с простыми модулями.×
Об авторах
Николай Иванович Червяков
Северо-Кавказский Федеральный университет
Email: k-fmf-primath@stavsu.ru
Павел Алексеевич Ляхов
Северо-Кавказский Федеральный университет
Email: ljahov@mail.ru
Наталия Федоровна Семенова
Северо-Кавказский Федеральный университет
Список литературы
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Delgosha F., Fekri F. Public-key cryptography using paraunitary matrices // IEEE Transactions on Signal Processing. V.54, No.9, 2006. - Р. 3489-3504.
- 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.
- Vaidyanathan P.P. Multirate Systems and Filter Banks. Englewood Cliffs, NJ: Prentice-Hall, 1993.
- Phoong S., Vaidyanathan P.P. Paraunitary filter banks over finite fields // IEEE Transactions on Signal Processing. V.45, No.6, 1997. - P. 1443-1457.
- Виноградов И.М. Основы теории чисел. СПб.: Лань, 2009. - 176 с.
- Сизый С.В. Лекции по теории чисел. М.: Физматлит, 2007. - 192 с.
Дополнительные файлы
![](/img/style/loading.gif)