Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,916

АЛГОРИТМ ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЯ ХААРА В КОНЕЧНОМ ПОЛЕ

Калмыков И.А. 1 Ложечкин А.А. 1 Гапочкин А.В. 1 Калмыков М.И. 1
1 ФГАОУ ВПО «Северо-Кавказский федеральный университет»
Использование модулярной арифметики позволило эффективно решить задачи, связанные с цифровой обработкой сигналов (ЦОС), с реализацией криптографических преобразований, с вычислениями псевдослучайных функций повышенной эффективности. Одним из наиболее эффективных методов анализа сигналов в настоящее время выступает вейвлет-преобразования. Использование крупномасштабного анализа позволяет оценить сигнал как с точки зрения спектрального содержания, так и временного изменения. В работе предлагается реализовать вейвлет-преобразования Хаара в конечном поле. Применение модулярной арифметики позволит повысить точность проводимых исследований сигналов.
модулярная арифметика
крупномасштабная обработка сигналов
вейвлеты
преобразование Хаара
базисные функции Хаара конечное поле
1. Червяков Н.И., Сахнюк П.А., Шапошников А.В., Ряднов С.А Модулярные параллельные вычислительные структуры нейросетевых систем / под ред. Н.И. Червякова. – М.: Физматлит., 2003. – 303 с.
2. Червяков Н.И. Обобщенная вычислительная модель модулярного нейропроцессора цифровой обработки сигналов на основе программируемых логических интегральных схем // Нейрокомпьютеры: разработка и применение. – 2006. – № 10. – С. 37–40.
3. Калмыков И.А., Воронкин Р.А., Резеньков Д.Н, Емарлукова Я.В., Фалько А.А. Генетические алгоритмы в системах цифровой обработки сигналов // Нейрокомпьютеры: разработка и применение. – 2011. – № 5. – С. 20–27.
4. Калмыков И.А., Калмыков М.И. Структурная организация параллельного спецпроцессора цифровой обработки сигналов, использующего модулярные код// Теория и техника радиосвязи. – 2014. – № 2. – С. 60-66.
5. Калмыков И.А., Саркисов А.Б., Макарова А.В. Технология цифровой обработки сигналов с использованием модулярного полиномиального кода [Текст] // Известия ЮФУ Технические науки. – 2013. – № 12 (149). – С. 234–241.
6. Калмыков И.А., Зиновьев А.В., Резеньков Д.Н., Гахов В.Р. Применение систолических ортогональных преобразований в полиномиальной системе классов вычетов для повышения эффективности цифровой обработки сигналов // Инфокоммуникационные технологии. – 2010. – Т .8, № 3. – С. 4–11.
7. Калмыков И.А., Чипига А.Ф., Кихтенко О.А., Барильская А.В. Криптографическая защита данных в информационных технологиях на базе непозиционных полиномиальных систем // Известия ЮФУ Технические науки. – 2009. – Т. 100, № 11. – С. 210–220.
8. Калмыков И.А., Стрекалов Ю.А., Щелкунова Ю.О., Кихтенко О.А., Барильская А.В. Технология нелинейного шифрования данных в высокоскоростных сетях связи // Инфокоммуникационные технологии. – 2010. – Т.8, № 2. – С. 14–22.
9. Калмыков И.А., Дагаева О.И. Новые технологии защиты данных в электронных коммерческих системах на основе использования псевдослучайной функции // Известия ЮФУ Технические науки. – 2012. – Т. 137, № 12 (137). – С. 218–224.
10. Червяков Н.И., Чумаков Д.В., Мальцев Н.А. Применение нейронных сетей для реализации целочисленного вейвлет анализа сигналов, заданных конечным числом отсчетов-преобразований [Текст] / Н.И. Червяков // Нейрокомпьютеры: разработка и применение. – 2008. – № 1-2. – С. 43–50.

Известно, что применение алгебраических структур, обладающих свойством кольца и поля, позволяет выполнить алгоритмы цифровой обработки сигналов (ЦОС) в реальном масштабе времени. Так как базовыми операциями ЦОС являются операции сложения, вычитания и умножения, то эти операции можно эффективно реализовать с использованием модулярной арифметики. Именно такие операции составляют основу алгоритмов крупномасштабного анализа сигналов. Поэтому реализация дискретного вейвлет-преобразований в поле является актуальной задачей.

Постановка и решение задачи исследований

Модулярная арифметика в настоящее время расширяет сферу своего использования. В настоящее время в качестве основных направлений применения алгебраических структур, обладающих свойством кольца и поля, можно выделить:

– Цифровая обработка сигналов. В данной области достаточно много трудов связано с использованием математических моделей ортогональных преобразований сигналов в поле комплексных чисел, которые реализуются на основе системы остаточных классов (СОК). Использование модулярных кодов позволяет, кроме повышения производительности специализированных процессоров (СП) ЦОС, обеспечить высокую отказоустойчивость вычислительных устройств [1, 2]. С целью повышения точности обработки сигналов в ряде работ [3–5] предлагается выполнение алгоритмов ЦОС в кольце полиномов. Использование полиномиальной системы классов вычетов способствует повышению снижения погрешности при проведении ортогональных преобразований сигналов. Кроме того, подобно кодам СОК, полиномиальная система классов вычетов позволяет осуществлять поиск и коррекцию ошибок, возникающих в процессе функционирования спецпроцессоров ЦОС.

– Защита информации от несанкционированного доступа (НСД) на основе криптографических алгоритмов. Использование математических особенностей полей Галуа позволяет отказаться от операции суммирования по модулю и использовать мультипликативные операции по модулю и их комбинации [6–8]. Использование модулярных полиномиальных кодов позволяет обеспечить защиту потока данных в реальном масштабе времени.

– Построение псевдослучайных функций (ПСФ) повышенной эффективности. В работе [9] представлен алгоритм и основные сферы применения разработанной ПСФ, реализованной в конечном поле. Данная псевдослучайная функция в качестве аргумента использует входную последовательность (х1,…,хn) и ключи (g,s1,…,sn). В результате алгоритм ее вычисления определяется

kalm02.wmf, (1)

где h – первообразный элемент мультипликативной группы.

Проведенные исследования показали, что для области определения размером 2m значение n = m/log2l. Вследствие этого при вычислении данной функции требуется в log2l раз меньше умножений. Основным преимуществом данной ПСФ является использование меньшего объема памяти для вычисления значения функция, так как она использует ключ в log2l раз меньший размером по сравнения с ПСФ Наора-Рейнголда. При этом стойкость данной ПСФ основывается на предположении о сложности решения l-DDH проблемы.

Одним из наиболее перспективных направлением применения модулярной арифметики, реализованной в конечном поле, является крупномасштабный анализ сигналов. Известно, что дискретное преобразование Фурье (ДПФ), а также быстрое преобразование Фурье (БПФ) не используют для проведения анализа нестационарных сигналов, локализованных в некотором интервале времени. Это обусловлено тем, что ДПФ и БПФ не позволяют получить информацию о динамике изменения сигнала во временной области. Таким образом, ортогональные преобразования сигналов, проводимых в поле комплексных чисел, не позволяют правильно оценить изменения частотно-временных характеристик сигнала.

Данного недостатка лишены вейвлет-преобразования, которые положены в основу крупномасштабного анализа сигналов. Использование дискретного вейвлет-преобразования (ДВП) позволяет получить истинную картину при анализе сигнала, так как это преобразование производится как во временной области, так и в частотной области.

Одним из первых дискретных вейвлет-преобразований является преобразование Хаара, которое относится к разделимым, и может быть представлено в виде матриц

kalm03.wmf, (2)

где F – матрица сигнала; H – матрица преобразования; T – результат преобразования сигнала.

Для построения матрицы преобразования Хаара используются базисные функции Хаара hk(z). Следует отметить, что данные функции задаются на непрерывном замкнутом интервале z∈[0, 1]. Используемые при этом значения переменной k, располагаются в пределе от 0 до N-1, где N = 2n. При этом для каждого индекса k, определяется пара значений q и l, для которых справедливо,

kalm04.wmf, (3)

так чтобы выполнялось условие

kalm05.wmf. (4)

В работе [10] представлен алгоритм выбора значения индекса, согласно которому

kalm06.wmf (5)

Вычисленные, согласно выражения (5), значения индексов l и q используются для вычисления базисных функции Хаара. Если k = 0, то базисная функция имеет вид

kalm07.wmf, (6)

где z∈[0, 1].

При этом для вычисления остальных базисных функций используется выражение

kalm08.wmf, (7)

где z∈[0, 1].

Рассмотрим выполнение вейвлет преобразования Хаара для 8 точек. Тогда матрица преобразования Хаара будет иметь следующий вид

kalm09.wmf (8)

Анализ выражения (8) показывает, что преобразование Хаара можно реализовать в конечном поле GF(р), где kalm10.wmf. Это обусловлено тем, что матрица содержит целые числа. Однако в ней присутствует и корень из двух. Переход к вычислению вейвлет Хаара возможно, если конечное поле сможет обеспечить целочисленное вычисление kalm11.wmf. Данное свойство позволит осуществить переход от позиционного вычисления вейвлет-преобразования Хаара к преобразованию Хаара в конечном поле.

Выберем конечное поле GF(17), в котором существует kalm12.wmf. При этом значение нормирующего множителя в данном поле будет равно kalm13.wmf. В этом случае получаем следующую матрицу вейвлет-преобразования Хаара

kalm14.wmf (9)

Для удобства работы в конечном поле произведем нормализацию 8×8 матрицы преобразования Н8 в поле GF(17)

kalm15.wmf (10)

В данной матрице выполняются все требования, предъявляемые к вейвлет-преобразованию

kalm16.wmf. (11)

kalm17.wmf. (12)

kalm18.wmf, (13)

где kalm19.wmf.

Произведем выполнение крупномасштабного анализа сигнала с использованием нормализованной матрицы Хаара в конечном поле GF(17).

kalm20.wmf. (14)

Проведем прямое преобразование Хаара для входной последовательности отсчетов сигнала f(x) = [1, 1, 4, 4, 0, 0, 0, 1]. Тогда, используя математический аппарат, который связан с крупномасштабной теорией, имеем

kalm21.wmf

kalm22.wmf

kalm23.wmf

kalm24.wmf

kalm25.wmf

kalm26.wmf

kalm27.wmf

kalm28.wmf

Таким образом, результатом вейвлет-преобразования имеем

kalm29.wmf.

Произведем обратное преобразование с целью восстановления исходного сигнала. Для этого необходимо воспользоваться транспонированной матрицей Хаара kalm30.wmf, которая в конечном поле GF(17) имеет следующий вид

kalm31.wmf. (15)

Воспользуемся данной матрицей и произведем вычисление обратного преобразования. В качестве входного вектора используем

kalm32.wmf.

Тогда имеем

kalm33.wmf. (16)

Согласно (16) получаем

kalm34.wmf

kalm35.wmf

kalm36.wmf

kalm37.wmf

kalm38.wmf

kalm39.wmf

kalm40.wmf

kalm41.wmf

Таким образом, получена исходная входная комбинация, которую подвергали крупномасштабному анализу. Рассмотрим представление исходной последовательности в базисе вейвлет-преобразования

kalm42.wmf, (17)

Таким образом, выражение (17) можно представить в виде

kalm43.wmf. (18)

Проведенные исследования свидетельствуют о том, что использование вейвлет-преобразований в конечном поле представляет собой обратимые преобразования. При этом такое преобразование не имеет ошибок округления, которые определяются позиционной системой счисления.

Выводы

В работе рассмотрены вопросы применения вейвлет-преобразований для анализа сигнала. В качестве такого преобразования предлагается использовать преобразования Хаара. Показана целесообразность реализации данного преобразования в конечном поле. Приведены примеры прямого преобразования Хаара, а также реализация обратного преобразования в поле Галуа GF(17). Полученные результаты позволяют сделать вывод о том, что использование алгебраических структур, обладающих свойством поля, позволяет снизить ошибки округления при выполнении крупномасштабного анализа сигналов.


Библиографическая ссылка

Калмыков И.А., Ложечкин А.А., Гапочкин А.В., Калмыков М.И. АЛГОРИТМ ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЯ ХААРА В КОНЕЧНОМ ПОЛЕ // Современные наукоемкие технологии. – 2014. – № 11. – С. 18-23;
URL: http://top-technologies.ru/ru/article/view?id=34765 (дата обращения: 01.04.2020).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074