Realizatsiya diskretnogo veyvlet-preobrazovaniya v sisteme ostatochnykh klassov spetsial'nogo vida

Full Text

Введение Обработка сигналов при помощи вейвлетов ( от англ. wavelet - волна) в настоящее время является весьма перспективным направлением, которое является серьезной альтернативой традиционному преобразованию Фурье. Основная причина этого явления заключается в способности вейвлетов к быстрому получению как частотных, так и локальных особенностей обрабатываемого сигнала. Возможность быстро и качественно получать частотно-временную информацию об объекте привела к тому, что в настоящее время вейвлеты используются в обработке изображений, речи, видео, очистке от шума и сжатии информации [1-4]. Основным методом вейвлетной обработки сигнала является применение дискретного вейвлет-преобразования (ДВП) по схеме Малла [5]. Основой ДВП является применение фильтров с конечной импульсной характеристикой (КИХ-фильтров), которые могут быть весьма эффективно реализованы в системе остаточных классов (СОК). СОК обладает большим потенциалом для увеличения производительности цифровых устройств благодаря замене операций сложения, вычитания и умножения чисел большой длины на параллельную обработку остатков гораздо меньшей разрядности [6]. Кроме того, СОК позволяет весьма эффективно проектировать и реализовывать различные цифровые устройства на программируемых логических интегральных схемах (FPGA) и интегральных схемах специального назначения (ASIC) [7]. Принципиальным недостатком СОК является сложность выполнения операции восстановления числа по его остаткам. В настоящей статье предлагается метод проектирования вейвлетных фильтров в СОК специального вида |2” -1,2", 2” +l|, так как в таких СОК можно в значительной степени уменьшить данный недостаток [8]. Система остаточных классов В СОК числа представляются в базисе взаимнопростых чисел, называемых модулями ß = {m1,...,mk}, ЯОД(тпту)=1, для i*j. к Произведение всех модулей СОК М = ^jni на- 1=1 зывается динамическим диапазоном системы. Любое целое число О<Х <М может быть единственным образом представлено в СОК в виде вектора fo,*2,•••»**}, где xt=\x\m = Xmodrn, [9]. Динамический диапазон СОК обычно делится на две примерно равные части таким образом, чтобы примерно половина диапазона представляла положительные числа, а остальная часть диапазона - отрицательные. Таким образом, любое целое число, удовлетворяющее одному из двух соотношений: - (М-1)/2<Х <(М-1)/2 для нечетных М и -М/2<Х<М/2 для четных М, может быть представлено в СОК. Операции сложения, вычитания и умножения в СОК определяются формулами А±В = \а1±Ъ\щ,...,\ак±Ьк |J; (1) ^x5 = («1x^|mi,-,kx^|mJ. (2) «Инфокоммуникационные технологии» Том 12, № 4, 2014 Червяков Н.И., Аникуева О.В., Ляхов П. А. 5 Равенства (1)-(2) показывают параллельную природу СОК, свободную от поразрядных переносов. Восстановление числа X по остаткам \х1,х2,...,хк\ основано на Китайской теореме об остатках Х = ÎLVlXi\mtMi i=0 (3) М где Mt = M/mi; элемент - мульти пликативный обратный для Mt по модулю т,•. Другим методом преобразования числа из СОК в позиционную форму является переход к обобщенной позиционной системе счисления [10]. Число Х<М имеет вид 0<х' < mi в обобщенной позиционной системе счисления, если: к-1 X = х[ + х'2тх + х'ът1т2 +...+ х'к\\ті > (4) <=i где х\ є [о ,тг) цифры числа X в обобщенной позиционной системе счисления, и х[ = хх modmj; х'2 = (х2 - xfycl2va.oàm2 ; 4 = ((*з ~А)°\ъ-х!2)с2Ъто<Ьщ ; (5) 4 = (-(С** “4kt-x'ihk ---4-iK-i^mod% • Константы Су являются мультипликативными обратными элементами для ті по модулю т ,• для всех 1 <і< і<к, то есть с,, -m,=l modm, для e J Vі J 1 <i<n, и могут быть вычислены, например, с помощью алгоритма Евклида. Таким образом, можно выделить два основных преимущества модулярной арифметики. 1. Арифметические операции сложения, вычитания и умножения выполняются без переносов, в отличие от позиционного представления чисел. 2. Для каждого значения модуля mi арифметические операции выполняются с парой соответствующих вычетов параллельно, при этом вычеты имеют гораздо меньшую разрядность, чем исходные операнды X и Y. Основной проблемой СОК является сложность выполнения операции деления и сравнения двух чисел. Однако несмотря на указанные недостатки, модулярная арифметика может быть эффективно реализована в приложениях, где основная доля вычислений приходится на операции умножения в сочетании со сложением и вычитанием [11]. Как будет видно далее, фильтрация сигналов является именно таким приложением. Дискретное вейвлет-преобразование в системе остаточных классов ДВП определяется последовательностью вложенных, закрытых подпространств, Vj^Vj-^...с^сГо, где V0=l2(z) - пространство последовательностей, суммируемых с квадратом. Подпространства удовлетворяют следующему свойству полноты, UVj=l2(z), je[0,j]. Допустим, что любой элемент из Vj может быть единственным образом представлен в виде суммы двух элементов из Vj+1 И Wj+1, где Vj - Vj+1 ® Wj+l. Для ортогональных вейвлетов Wj+1 определяется как ортогональное дополнение Vj+1 в Vj. Существует последовательность g„eV0 , такая, что {?n-2i}tez является базисом в Vx. Это означает, что последовательность hn є V0 может быть построена так, что eZ будет базисом в W1. Применив такой метод разложения J раз, можем получить следующее разложение для V0 : V0 = W1®JV2®...®Wj®Vj. (6) Одномерное ДВП А-го порядка последовательности хп определяется рекуррентными равенствами N-1 «Р = Z&fca2«-i > г = 1,2 ... J ; к=0 (7) к-0 где аР и ^Р - аппроксимирующие и детализирующие последовательности 7-го уровня; gk и описывают коэффициенты соответственно низкочастотного и высокочастотного фильтров. Исходный сигнал хп может быть точно восстановлен из коэффициентов кратномасштабного разложения по формуле агн) = N 2 2-і 2 _ (О к=0 k=Ü А-! 2 _ т- четное число; 1V -і 2 _ (8) ^ 1_к’ к=0 2 к к=0 т- нечетное число, «Инфокоммуникационные технологии» Том 12, № 4, 2014 6 Червяков Н.И., Аникуева О.В., Ляхов П.А. где gk и hk являются коэффициентами низкочастотного и высокочастотного синтезирующих фильтров соответственно. Как можно видеть, в (8) используются операции сложения и умножения. Использование только этих операций для вычисления ДВП позволяет наиболее полно использовать возможности модулярной арифметики для повышения быстродействия систем цифровой обработки сигналов по сравнению с системами, функционирующими в традиционных позиционных системах счисления. Построение вейвлетных наборов фильтров при помощи СОК обладает рядом преимуществ. Если коэффициенты вейвлетного фильтра зафиксированы априори, то использование умножителей на основе LUT-таблиц будет весьма эффек тивным решением, обеспечивающим высокую скорость вычислений и эффективность с аппаратной точки зрения [12]. Приведем формулы, по которым осуществляется прямое и обратное дискретное вейвлет-преобразование в СОК. Каждая из формул задает преобразование для отдельно взятого модуля, число модулей берется таким, чтобы покрыть требуемый диапазон вычислений; формулы для каждого из модулей аналогичны приведенным: №1 =ZI4|4-!| 1 ^ êo' ^ \Æ -VI/, I LH) I L(o)| =|x| . \an ~ ZJ k\p. \a2n-k\ > \an _rnL.’ P‘ Го Pj (9) la. H)| _ N -1 k=0 Pj r(0 -k N -1 + ^\hik k=0 PJ Pj "-1 2 |- ^ £>24+1 к=0 Pj ти-1 , --к 2 |-1 k=0 +1 m-k 2 Pj dm 1 m-1 , Pj --к 2 , m-четное число; , m-нечетное число. pi (10) Проектирование вейвлетного фильтра в системе остаточных классов Для моделирования вейвлетного фильтра в СОК был выбран вейвлет Добеши Db4, так как семейство вейвлетов Добеши обладает весьма важным во многих приложениях свойством ортогональности образуемого базиса [13-14]. ДВП можно реализовать при помощи комбинации КИХ-фильтров так, как это показано на рис. 1. Коэффициенты высокочастотного анализирующего КИХ-фильтра HD, соответствующего рассмотренному вейвлету Db4, приведены в таблице 1. Коэффициенты остальных фильтров LD, HR и Lr для данного вейвлета могут быть легко получены из коэффициентов HD путем перестановки коэффициентов и смен знака, так как схема, изображенная на рис. 1, является набором фильтров со свойством точного восстановления сигнала [15]. Рис. 1. Дискретное вейвлет-преобразование сигнала. «Инфокоммуникационные технологии» Том 12, № 4, 2014 Червяков Н.И., Аникуева О.В., Ляхов П.А. 7 Целочисленное значение коэффициентов фильтра Db4 в таблице 1 было получено преобразованием чисел двойной точности в числа шириной 10 бит, из которых 1 бит отведен для знака, а остальные 9 являются информационными. Описанный переход осуществлялся путем умножения исходных коэффициентов на 29=512 с последующим округлением результата. Полученное целочисленное значение было переведено в СОК вида {2" -1,2п,2п+1}, при п - 1, то есть {127,128,129}. Выбор такой СОК обусловлен тем, что для таких наборов модулей разработаны эффективные алгоритмы выполнения проблемной операции обратного преобразования числа из СОК в ПСС [8]. Выбранная СОК задает диапазон равный log2 (127-128-129) « 20,999912 бит, в то время как максимальный отклик фильтра равен ZI *<1 = 675, что соответствует « 9,398744 битам. Таким образом, данный фильтр можно использовать для обработки [20, 999912 - 9, 398744] = 11битных последовательностей входных данных, не опасаясь переполнения динамического диапазона системы. Таблица 1. Коэффициенты фильтра Db4 в ПСС и СОК Db4, позиционная форма Цело чис ленное значе ние Db4 в СОК {127,128,129} 0,162901714025649 83 {83, 83, 83} 0,505472857545915 259 {5,3,1} 0,446100069123380 228 {101, 100, 99} -0,019787513117822 -10 {117,118,119} -0,132253583684520 -68 {59, 60,61} 0,021808150237089 11 {11,11,11} 0,023251800535491 12 {12, 12, 12} -0,007493494665181 -4 {123,124,125} Разумеется, перевод коэффициентов фильтра в целочисленную форму 10-битного представления приводит к ошибкам округления. На рис. 2 показана амплитудно-частотная характеристика (АЧХ) этой ошибки для фильтра Db4. Видно, что максимальное значение ошибки не превосходит -50 Дб, что на практике является достаточно хорошим результатом, не приводящим к сколько-нибудь значимым искажениям обрабатываемого сигнала [16]. Рис. 2. АЧХ ошибки округления фильтра Db4 Основной характеристикой любого КИХ-филь-тра, в частности вейвлетного фильтра Db4, является его импульсная характеристика. Импульсной характеристикой цифровой системы называется отклик, выдаваемый при подаче на вход системы единичного сигнала <5>(и). В рассматриваемом нами случае при преобразовании числа в целочисленную форму единичный сигнал должен быть умножен на 2 =512, так как указанное преобразование выполнялось путем сдвига двоичного числа на 9 разрядов влево: £(и) = [512, п = 0, 0, пф 0. (11) При переходе к СОК {127, 128, 129} имеем [{4,0,125}, п-0, ö(n) = < {0,0,0}, пф 0. (12) На рис. 3 изображены импульсные характеристики каждого из модулярных фильтров. (а) (б) (в) Рис. 3. Импульсные характеристики фильтра Db4 в модулярной форме: а) щ =127, б) /«2=128, в) тз=129 «Инфокоммуникационные технологии» Том 12, № 4, 2014 8 Червяков Н.И., Аникуева О.В., Ляхов П.А. На рис. 4 представлена ошибка импульсной характеристики, полученная в результате перевода коэффициентов фильтра в СОК, с округлением. Максимальное значение ошибки по модулю не превосходит амплитуды подаваемого на вход фильтра импульса, что составляет менее 0,1% обрабатываемого сигнала. Таким образом, предложенная архитектура вейвлетного фильтра в СОК может быть использована в большинстве практических случаев за исключением тех, при которых требуется особая точность обработки. х Ю-4 Impulse Response 'il1!11,1 г.........і..........і...........і...........і..........і..........і...........і...........і..........і..........і......... 0 1 2 3 4 S 6 7 8 9 10 11 Samples Рис. 4. Ошибка импульсной характеристики фильтра Db4 в модулярной форме Заключение В статье предложен метод проектирования вейвлетных фильтров в СОК. Показано, что СОК обладает большим потенциалом для увеличения производительности фильтров, так как в рассматриваемой задаче требуется выполнение только операций сложения и умножения, которые можно очень быстро вычислять в модулярной форме. На примере фильтра Добеши Db4 показано, как можно преобразовать коэффициенты из позиционной системы счисления в СОК. Результаты моделирования показали, что ошибка округления, неизбежно возникающая при таком переходе, не вызывает значимых отклонений в работе фильтра. Построенный метод может быть успешно применен для реализации устройств цифровой обработки сигналов на программируемых логических интегральных схемах, а также в проблемно-ориентированных аппаратно-программных решениях для обработки видеоизображений,

About the authors

Ol'ga Viktorovna Anikueva

Email: anikueva2013@yandex.ru

Pavel Alekseevich Lyakhov

Email: ljahov@mail.ru

Nikolay Ivanovich Chervyakov

Email: k-fmf-primath@stavsu.ru

References

Supplementary files