СИНТЕЗ СИГНАЛОВ РЯДАМИ ХААРА В ДВОИЧНОЙ СИСТЕМЕ СЧИСЛЕНИЯ

Постановка проблемы и анализ литературы. Современные высокоэффективные алгоритмы обработки сигналов и изображений базаруються, в основном, на методах вейвлет-анализа, среди которых знаковое место занимает классический ортогональный базис Хаара [1– 4]. Функции Хаара позволяют оценить локальные свойства исследуемых сигналов и их часто называют вейвлетами Хаара [5, 6]. Так же важным свойством системы Хаара является минимальный объем вычислений, как для процедуры получения коэффициентов, так и для процедуры суммирования рядов Хаара. Поэтому весьма актуальной является задача исследования вычислительных возможностей системы Хаара при двоично-кодированном задании аргументов и параллельном способе организации вычислений в специализированных процессорах обработки сигналов.

Известно много вариантов алгоритмов и устройств обработки сигналов в дискретном базисе Хаара [1,3,4, 6,7,8]. Основным недостатком таких схем является то, что их архитектура в большинстве случаев неадекватна структуре решаемой задачи или структуре внутренних связей моделируемого процесса, что влечет за собой большой объем вычислений или оборудования.

Цель статьи. Развитие методов преобразований Хаара на основе объединения свойств быстрых алгоритмов Хаара и особенностей суммирования рядов Хаара при двоичном кодировании аргументов восстанавливаемой функции, что позволит получить максимально эффективный в вычислительном отношении алгоритм обработки.

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

Задаваясь коэффициентами Хаара amj и полагая для простоты  , запишем последовательность вычислений в следующем виде

    (1)

Вместо коэффициентов   более удобно оперировать с числами . Тогда (1) можно переписать как

Из анализа свойств функций Хаара [2] легко видеть, что для каждого фиксированного “ ” в этой сумме найдется не более чем m0 отличных от нуля слагаемых. Действительно, среди отрезков   с   лишь один содержит точку х. Пусть это будет отрезок  . Тогда и, следовательно,   

В [2] утверждается и доказывается следующая теорема.

Если в двоичной системе счисления х=0, ε1, ε2,…, εS…, то

                  (2)

где опять таки в двоичной системе

                                      (3)

(при m=1 правую часть (10) надо полагать равной нулю).

Здесь все εS– двоичные цифры, то есть либо нули, либо единицы. В десятичной системе значение х и формула (3) будут выглядеть так:

Из (2) и (3) следует весьма простой способ вычисления   на ЭВМ, использующих двоичную систему. Так как аргумент х задается своим двоичным представлением х=0,ε1,ε2,…, то при каждом m легко выделить цифры ε1 ε2… εm-1. Для этого нужны только простейшие логические операции. По значениям m и jm можно сформировать адрес ячейки, содержащей  . Если следующая цифра в двоичной записи числа х (то есть ε2) равна нулю, то   прибавляется к накапливаемой сумме, а если следующая цифра равна 1, то   вычитается:

                    (4)

где .

Начав с  , получим  .

Рассмотрим работу алгоритма при восстановлении исходной информации, например, при х=0,010. Присваивая m значение 1 по формуле jm=0, ε1, ε2,…, εm-1+1 вычислим индексы коэффициентов Хаара, которые будут равны

Определим теперь знак этого коэффициента, анализируя первый разряд после запятой в двоичном представлении числа х, и так как он равен 0, коэффициент b11 берем со знаком плюс. Аналогично при m=2 и 3 jm=0,010+1=1 и jm=0,010+1=2 коэффициенты b21 и b32 суммируются со знаком минус и плюс соответственно. Таким образом, значение исходной функции в точке х=0,010 определяется как

            (5)

Такой же результат дают классические вычисления.

В каждом цикле приведенного алгоритма производится одно сложение и несколько логических операций, и общее число вычислений в одной точке стремится к значению двоичного логарифма размерности базиса Хаара, а все время суммирования составит Q=N log N, где N – число дискрет аргумента на единичном интервале.

Недостатком рассмотренного метода является его вычислительная избыточность. Покажем, что объем вычислений при восстановлении исходных данных по коэффициентам Хаара в двоичной системе счисления может быть существенно уменьшен .

Для этих целей прежде, чем суммировать коэффициенты Хаара на основании анализа двоичных разрядов в дискретных точках восстановления исходных функций, сформируем суммы следующего вида[9, 10]:

    (6)

где 

Тогда суммирование коэффициентов Хаара в каждой точке восстановления можно представить в виде:

               (7)

где jm=ε1ε2… εm-1+(N/2-2) для первого слагаемого, и  =ε1ε2… εm-1+1 для второго слагаемого, причем m=m0.

Так в случае, если  , то процесс вычислений будет начинаться с определения соответствующих сумм вида:

Затем осуществляется восстановление данных в каждой точке отсчета исходной функции по выражению (7) с учетом того, что первому отсчету соответствует двоичное представление вида 0,000, второму 0,001, третьему 0,010 и т.д. Для точки 0,010 получим: jm=0,010+2=3 и j*m=0,010+1=2. или с двоичными индексами,  .

Значения индексов коэффициентов и их знаков совпадают со значениями, определенными на основе свойств классических функций Хаара, но количество операций типа сложение-вычитание составляет при этом 2(N-1) вместо N log2N известного метода [2].

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

 Литература

1. Ахмед, Н. Ортогональные преобразования при обработке цифровых сигналов [Текст] / Н. Ахмед, К.Р. Рао. – М.: Связь, 1980. – 248 с.
2. Соболь, И.М. Многомерные квадратурные формулы и функции Хаара [Текст] / И.М. Соболь. – М.: Наука, 1970. – 288 с.
3. Залманзон Л.А. Преобразование Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. – М.: Наука. гл. ред. физ.-мат. лит., 1989. – 496 с.
4. Миано, Дж. Форматы и алгоритмы сжатия изображений в действии: учеб. пособ. [Текст] / Дж. Миано – М.: Триумф, 2003. – 336 с.
5. Дебеши, И. Десять лекций по вейвлетам [Текст] / И. Дебеши // Пер. с англ. – М.: Ижевск, 2001. – 464 с.
6. Гонсалес, Р. Цифровая обработка изображений [Текст] / Р. Гонсалес, Р. Вудс. – М.: Техно¬сфера, 2005. – 1072 с.
7. Сверхбольшие интегральные схемы и современная обработка сигналов [Текст]: пер. с англ. / Под ред. С. Гуна, Х. Уайтхадса, Т. Кайлата. – М.: Радио и связь, 1989. – 472 с.
8. Итенберг И.И. Мультипроцессоры для цифровой обработки изображений в системах реального времени / Известия вузов. Электроника. – Москва, 2002. – № 4. – С. 71-78.
9. Іванов, В.Г. Параллельные и последовательные структуры Хаара для цифровой обработки сигналов [Текст] / В.Г. Іванов // Электронное моделирование. – 2005. – № 3. – С.55-66.
10. Іванов, В.Г. Формальное описание дискретных преобразований Хаара [Текст] / В.Г. Іванов // Проблемы управления и информатики. – 2003. – № 5. – С. 68-75.