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

Abstract

In article the design method the wavelet filter in RNS is offered. It is shown that RNS pos-sesses high potential for increase in productivity of filters as in the considered task performance only of operations of addition and multiplication which can be calculated very quickly in a modular form is required. On the example of Dobesha’s filter Db4 it is shown how it is possible to transform coefficients from a position numeral system to RNS. Results of modeling showed that the rounding error which is inevitably arising upon such transition doesn’t cause significant deviations in operation of the filter.

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 показано, как можно преобразовать коэффициенты из позиционной системы счисления в СОК. Результаты моделирования показали, что ошибка округления, неизбежно возникающая при таком переходе, не вызывает значимых отклонений в работе фильтра. Построенный метод может быть успешно применен для реализации устройств цифровой обработки сигналов на программируемых логических интегральных схемах, а также в проблемно-ориентированных аппаратно-программных решениях для обработки видеоизображений,
×

References

  1. Chervyakov N.I., Lyakhov P.A., Babenko M.G. Digital filtering of images in a residue number system using finite-field wave-lets // Automatic Control and Computer Sciences. №48 (3), 2014. - Р 180-189.
  2. Столниц Э., Де Роуз Т., Салезин Д. Вейвлеты в компьютерной графике. Теория и приложения. Москва-Ижевск: Изд-во PXD, 2002. - 272 с.
  3. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии. М.: Триумф, 2003. -320 с.
  4. Червяков Н.И., Ляхов П.А. Реализация модулярного вейвлет-преобразования в нейросетевом базисе // Нейрокомпьютеры: разработка, применение. №11, 2011. - С. 18-25.
  5. Малла С. Вейвлеты в обработке сигналов. М.: Мир, 2005. - 671 с.
  6. Omondi А., Premkumar В. Residue Number Systems: Theory and Implementation. Imperial College Press, 2007. - 296 р.
  7. Cardarilli G.C., Nannarelli А., Re М. Residue Number System for Low-Power DSP Applications // Proc. 41st Asilomar Conf. Signals, Syst., Comput., 2007. - P. 1412 -1416.
  8. Afsheh А., Mojoodi А. An Improved Reverse Converter for Moduli Set // ISCIT 2010 International Symposium on Communications and Information Technologies Proceedings, 2010. - P. 928-933.
  9. Червяков Н.И., Сахнюк П.А., Шапошников А. В., Ряднов С. А. Модулярные параллельные вычислительные структуры нейропроцессорных систем. М.: Физ-матлит, 2003. - 288 С.
  10. Gbolagade K.A., Cotofana S.D. An O(n) Residue Number System to Mixed Radix Technique // ISCAS 2009 IEEE Interna-tional Symposium on Circuits and Systems, 2009. - P. 521-524.
  11. Червяков Н.И., Сахнюк П.А., Шапошников А.В., А.Н. Макоха А.Н. Нейрокомпьютеры в остаточных классах. М.: Радиотехника, 2003. - 272 с.
  12. Ramirez J., Fernández P.G., Meyer-Baese U., Taylor F., García A., Lloris A. Index-based RNS-DWT Architectures for Cus-tom IC Designs // Proc. of 2001 IEEE Workshop on Signal Processing Systems, 2001. - P. 70-79.
  13. Добеши И. Десять лекций по вейвлетам. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. - 464 с.
  14. Фрейзер М. Введение в вейвлеты в свете линейной алгебры. М.: БИНОМ. Лаборатория знаний, 2008. - 487 с.
  15. Чобану М. Многомерные многоскоростные системы обработки сигналов. Москва: Техносфера, 2009. - 480 с.
  16. Stamenković N. Digital FIR Filter Architecture Based on the Residue Number System // Facta Universitatis, Ser.: Elec. Energ. Vol. 22, No. 1, 2009. - P. 125-140.

Statistics

Views

Abstract: 29

PDF (Russian): 7

Article Metrics

Metrics Loading ...

Copyright (c) 2014 Anikueva O.V., Lyakhov P.A., Chervyakov N.I.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies