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

Цель исследования

Использование целочисленной арифметики позволяет повысить точность выполнения ДВП сигналов. Так в работе [9] представлен метод выполнения ДВП Хаара с использованием GF(p), что позволило заменить коэффициенты ДВП целочисленными значениями. В результате была достигнута максимальная точность реализации ДВП сигнала.

Однако увеличение разрядности обрабатываемых дискретных отсчетов сигнала приводит к значительному увеличению значения модуля р, а значит, и схемных затрат. Устранить данный недостаток можно за счет применения модулярных кодов СОК. Поэтому целью работы является повышение точности и скорости выполнения ДВП за счет использования модулярных кодов.

Материалы и методы исследования

Модулярный код системы остаточных классов в качестве оснований использует взаимно простые числа рi, i = 1, 2, …, k. В этом случае число А задается набором остатков, полученных при делении А на модули mi, в виде

, (1)

где ; i = 1, 2, …, k.

Применяя изоморфизм, порожденный китайской теоремой об остатках (КТО), коды СОК позволяют операции над операндами
и  представить в виде

, (2)

где  – операции сложения, вычитания и умножения по модулю.

Произведение оснований кода СОК определяет рабочий диапазон

. (3)

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

Так как вычисления в СОК выполняются параллельно и независимо по модулям кода над малоразрядными остатками, то это позволяет повысить скорость выполнения вычислений задач ЦОС [5, 7, 10]. В работах [8, 10] показано, что основу кратномасштабного анализа сигналов составляют операции сложения, вычитания и умножения

(4)

где X = [x(0), x(1),…, x(N – 1)] – входной вектор;  – скалинг-функции ДВП; Wa(0,0) и Wd(m, j) – аппроксимирующие и детализирующие последовательности.

В настоящее время широкое применение нашли дискретные вейвлет-преобразования Добеши. Это обусловлено их достоинствами, приведенными в работах [3, 4]. Рассмотрим выполнение ДВП Добеши (Db4). Пусть обработке подвергается входной вектор, содержащий 8 точек. Тогда матрица для выполнения ДВП Добеши-4 примет следующий вид:

, (5)

где ; ; ; .

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

, (6)

где ; i = 1, 2, …, k.

Значение детализирующей последовательности будет иметь вид

, (7)

где ; i = 1, 2, …, k.

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

; ;

. (8)

Очевидно, что аппроксимирующие и детализирующие последовательности Wa(0,0) и Wd(m, j) представлены в виде наборов остатков по основаниям СОК. Преобразуем полученный результат в позиционный код, используя китайскую теорему об остатках (КТО). Тогда

(9)

где Bi – ортогональные базисы кода СОК; rA – ранг числа, показывающий количество превышений рабочего диапазона.

Результаты исследования и их обсуждение

Рассмотрим реализацию ДВП Добеши в коде СОК, в котором выбраны основания р1 = 23, р2 = 47, р3 = 71. Вычислим коэффициенты Добеши по модулю р1 = 23. Получаем , . Тогда имеем ; ; ; .

Вычислим коэффициенты Добеши по модулю р2 = 47. Получаем , . Тогда коэффициенты равны ; ;
; .

Вычислим коэффициенты Добеши по модулю р3 = 71. Получаем , . Тогда коэффициенты равны ; ; ; .

Тогда матрицы для проведения ДВП Добеши-4 в коде СОК имеют вид

Пусть необходимо провести кратномасштабный анализ сигнала, входной вектор которого равен x(n) = {7, 2, 5, 17, 6, 11, 2, 18}. Для этого вычислим произведение данного вектора на матрицу Добеши по модулю р1 = 23. В результате получаем

.

Реализация ДВП Добеши по модулю р1 = 23 позволила получить разложение сигнала . Тогда сглаживающие коэффициенты ДВП определяются свертками входного сигнала, которые получены с помощью первой, третьей, пятой и седьмой строк матрицы, т.е. . Данные коэффициенты можно вычислить, используя низкочастотный фильтр Н. При этом детализирующие коэффициенты представляют собой свертки входного сигнала со второй, четвертой, шестой и восьмой строками матрицы, т.е. . Данные коэффициенты можно вычислить, используя высокочастотный фильтр G. Тогда исходный сигнал имеет вид

,

где Hi – коэффициенты НЧ-фильтра; Gi – коэффициенты ВЧ-фильтра; i – номер строки матрицы ДВП Добеши.

Проведем кратномасштабный анализ входного сигнала по модулю р2 = 47. Получаем

.

Реализация дискретного вейвлет-преобразования Добеши по модулю р2 = 47 позволила получить разложение сигнала в базисе .

Вычислим дискретное вейвлет-преобразование Добеши по модулю р3 = 71. Тогда

.

Реализация дискретного вейвлет-преобразования Добеши по модулю р3 = 71 позволила получить разложение сигнала в базисе .

В результате выполнения дискретного вейвлет-преобразования Добеши в системе остаточных классов были получены следующие значения

Так как результат прямого ДВП представлен в коде СОК, то его необходимо перевести в позиционную систему счисления (ПСС), используя равенство (9). Для этого необходимо вычислить ортогональные базисы для заданной системы оснований СОК. Воспользуемся алгоритмом вычисления ортогональных базисов, приведенным в работе [2].

Для вычисления ортогонального базиса В1 определим .
Вычислим . Определим значение веса В1 из условия . Получаем m1 = 12. Тогда ортогональный базис равен .

Для вычисления второго ортогонального базиса определим .
2. Вычислим . Определим значение веса В2 из условия . Получаем m2 = 43. Тогда ортогональный базис равен .

Для вычисления третьего ортогонального базиса кода СОК определим значение . Вычислим . Определим значение веса В3 из условия . Получаем m3 = 40. Тогда ортогональный базис равен .

Произведем обратное преобразование из модулярного кода а00 = (0, 38, 54) в позиционный код. Воспользуемся равенством (9). В результате получаем

.

Тогда разложение входного сигнала в базисе Добеши, представленном в коде СОК, будет равен W = {14467, 41210, 40256, 40952, 52058, 55323, 56990, 59159}. Очевидно, что использование кодов СОК позволяет повысить скорость выполнения ДВП. Так набор модулей СОК позволяет обеспечить обработку 16-разрядных данных, так как . При этом максимальная разрядность остатка по модулю р3 = 71 составляет 7 разрядов. Известно, что временные затраты на выполнение операции умножения пропорциональны разрядности операндов. Таким образом, снижение разрядности обрабатываемых данных в СОК позволило сократить временные затраты на выполнение ДВП Добеши в 2,29 раза без учета выполнения операций прямого ПСС-СОК и обратного СОК-ПСС преобразований, обеспечивая при этом максимальную точность вычислений.

Заключение

В статье представлена разработанная математическая модель выполнения дискретного вейвлет-преобразования Добеши с использованием модулярных кодов. Представление сглаживающих и детализирующих коэффициентов Добеши в виде целочисленных остатков позволяет обеспечить максимальную точность выполнения ДВП. Применение кодов СОК позволяет повысить скорость вычисления дискретного вейвлет-преобразования за счет параллельной обработки малоразрядных остатков. Такое распараллеливание вычислений на уровне арифметических операций позволяет повысить скорость обработки сигналов. Так, уже при обработке 16-разрядных данных использование трех оснований СОК р1 = 23, р2 = 47, р3 = 71 позволило сократить временные затраты на выполнение ДВП Добеши в 2,29 раза по сравнению с ПСС без учета выполнения прямого и обратного преобразований. Очевидно, что при увеличении разрядности обрабатываемых отсчетов эффективность использования разработанной математической модели выполнения ДВП Добеши-4 в коде СОК увеличивается.

Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 17-37-50009.