Айфичер Э., Джервис Б. Цифровая обработка сигналов, практический подход (2-е изд., 2004) (1095888), страница 31
Текст из файла (страница 31)
Кроме того, скорость можно увеличить, убрав ненужные операции умножения на коэффициент Игл (который часто называют ленивым коэффициентом!), если Игл = ~1 или Ы. При этом также уменьшается число операций сложения. Для реализации этого при Итзт = х1 нли ~з добавляется отдельная "бабочка". В результате, например, получается двоичный плоский алгоритм ВД с двумя "бабочками". Дополнительно можно сократить время вычислений, если вначале найти синусоидальные и косинусоидальные части Игл, а затем сохранить их значения в справочной таблице. Возможны и другие усовершенствования. Итак, ясно, что существует не одно БПФ, а много. Чтобы осветить эту тему полностью, нужны значительные затраты времени и описание громоздких математических аппаратов.
Также неплохо было бы разбираться в современной теории матриц, многоразмерном индексном отображении и теории чисел. Но такой всесторонний подход к этой теме выходит за рамки цели, поставленной в этой главе, задача которой — объяснить принципы дискретных преобразований тем способом, который будет понятен большинству людей, занимающихся цифровой обработкой сигналов. Существует ряд других книг, например, [3] и [5) с более специализированным подходом, и именно они и рекомендуются читателям для дальнейшего изучения. Как уже говорилось, есть множество алгоритмов, кроме того, специалисты могут написать собственные алгоритмы, наиболее подходящие для данного приложения. Однако сокращение числа необходимых операций сложения и умножения не всегда приводит к пропорциональному увеличению скорости вычислений.
Результатом снижения количества операций умножения может даже оказаться увеличение программного кода или числа операций сложения. Если используются специальные процессоры обработки сигналов, то они могут налагать свои собственные ограничения, сводящие на нет все попытки усовершенствования алгоритма. Поскольку коэффициент увеличения скорости редко превышает 2, авторы склонны рекомендовать для универсальных задач, в которых скорость не так критична, основное двоичное БПФ с ВД.
В книге [5) представлено большое количество программ для вычисления БПФ на языке ЕОКТКАХ. Даются также программы, которые можно реализовать аппаратным способом. В приложении 3А рассматривается программа на языке С для вычисления двоичного БПФ с ВД. ' 3,8". Другие диоКретные преобразоваНия'''. Существует множество других преобразований. Преобразование Винограда — Фурье ([2б]; см. также [3„5, 15, 19, 22]) и алгоритм первоначального множителя ([3], см. также [15]) представляют собой оригинальные, но слишком сложные методы повышения скорости вычисления БПФ.
Дискретное косинус-преобразование особенно подходит для сжатия данных (см. раздел 3.8.1). При преобразовании Уолша (раздел 3.8.2) сигнал З.В, Другие дискретные преобразования раскладывается на прямоугольные импульсы, а не на синусоиды, и оно вычисляется быстрее, чем БПФ. Преобразование Адамара (раздел 3.8.3), построенное с помощью перестановки последовательности Уолша, вычисляется еще быстрее. Хотя для нежгторых целей преобразования Уолша н Адамара позволяют получить определенные преимушества, они имеют ряд недостатков, которые ограничивают область их применения (см. разделы 3.8.2 и 3.8.3). Наконец, преобразование Хаара особенно полезно для определенна краев при обработке изображений [20] и в подобных приложениях. Вообще, стоит порекомендовать книгу (3] — хороший источник информации для начинающих„которые хотели бы больше знать о преобразованиях и их применении.
В 1990-х годах возрос интерес к вейвлетному преобразованию (4, б, 10, 1Ц, поэтому оно также представлено ниже, в разделе 3.8.4. ",: 3;еуг.":-,; дискретное косинус-преобразование Помимо того, что преобразования используются для ускоренна вычисления корреляции и свертки, а также в спектральном анализе, эти методы применяются еще и для сжатия данных при, например, передаче речи или видеосигналов, а также для записи медицинских сигналов, таких как сигналы ЭКГ или ЭЭГ. Кроме того, они используются при распознавании шаблонов.
В названных приложениях задействованы только самые значительные компоненты преобразований. В результате этого снижается количество битов, необходимое для их кодирования, что позволяет ускорить передачу, использовать линии передачи с более узкой полосой, а также облегчает распознавание шаблонов (благодаря уменьшению объема информации). Эти три немаловажных признака преобразования и определяют его эффективность с точки зрения сжатия данных, которая связана с концентрацией энергии на низких частотах, простотой вычислений и минимальной среднеквадратической ошибкой.
С этой точки зрения идеальным преобразованием является преобразование Карунена-Лоэва, но его нельзя задать в виде алгоритма.' Впрочем, дискретное косинус-преобразование (ДКП) обладает фактически теми же свойствами, и его можно представить в виде алгоритма. По сути, оно представляет собой действительную часть ДПФ. Это определение справедливо, поскольку ряд Фурье из действительных и четных функций содержит толью косинусондальиые члены, а при использовании, например, дискретных значений напряжения данные действительные, и их можно сделать симметричными — удвоить путем прибавления к ним их зеркального отображения.
Итак, ДПФ задается следующим образом (уравнение (3.41)): Дг-1 Х(н) = ~~г х е "'" Г 1=0,1,...,Ж вЂ” 1. Определив ДКП Х,(й) как действительную часть этого преобразования, получим Дг-1 Х,(й) = Не(Х(н)( = ~~г х„созг 1,/с =0,1,...,1ч' — 1. (З.бб) 1. )У /' »=0 гом, книгу У. Прап. Цифроаа» обработка сига»»оа, г. К Там но»иапо, но монна. Правда, вычнс»нгс»ьнаа свонношь сагорнгма Карунсна-Ловы сшс вышн чсм у нсонгнмнанрованного ДПФ вЂ” Прим, ред.
Глава 3, Дискратныа преобразования Это одна из нескольких форм ДКП. Более общий вид (см. (1, 3, 27]: Х,(/с) = — ~~~ х„соз ~ ( = 1 //22кп+ кя'1 а=О (3.67) — х„соз ~ ~, /О = 0,1,...,/У вЂ” 1. 1 (йя(2п+1)1 п=О Сушествуют также и другие формы (см. (2, 17, 18, 27]). Разработаны реализации ДКП, основанные на БПФ [16], кроме того, есть также быстрое ДКП, скорость которого в шесть раз выше указанных преобразований (7].
Еще одна версия — это С-матричное преобразование, которое намного проше реализовать на аппаратном уровне (23]. ';"'»::ьзЗ:2;::. Преобразование Уолша Преобразования, обсуждавшиеся выше, были основаны на функциях косинус и синус. Намного проше и быстрее считаются преобразования, основанные на импульсоподобных сигналах, которые принимают значения толью х1.
Кроме того, они больше подходят для описания сигналов с нарушением непрерывности, которые встречаются, например, в изображениях. И, наоборот, они менее пригодны для описания непрерывных сигналов и могут не быть инварнантнымн по фазе, а если это так, полученный спектр может искажаться. Поэтому такие сигналы обычно используются при обработке изображений (астрономия и спектроскопия), кодировании сигналов и фильтрации.
Точно так же, как ДПФ основывается на наборе гармонических косинусоидальных и синусоидальных сигналов, дискретное преобразование Уолша (ДПУ) основано на наборе гармонических прямоугольных импульсов, которые называются функциями Уолша. Однако для прямоугольных импульсов частота не определена, поэтому используется аналоговый термин "последовательность".
Последовательность — зто половина среднего числа переходов через нуль за единицу времени. На рис. 3.6 показаны функции Уолша до порядка /У = 8, расположенные по возрастанию. В таком виде их называют упорядоченными ло Уолшу. Функция Уолша со временем т и порядком п обозначается УЧАТ(п,е). Внимательно изучая рис.
3.6, видим, что сушествует равное количество четных и нечетных функций Уолша, точно так же, как и косинусоидальных и синусоидальных компонентов ряда Фурье. Четные функции Ч'АЕ(2Й,1) записываются как САЦ)О, т)„а нечетные функции %А(,(21 + 1, 1) записываются как БАЕ(2к + 1,1), где /О = 1, 2,..., Аг/2 — Е Любой сигнал Я) можно разложить по набору функций Уолша (аналог разложения в ряд Фурье) как 12/2-1 Л/2-1 ,((т) = аО%А1 (О, т) + ~~~ ~~1 (о,БА1 (1', 1) + 61СА1 (2, т)], (3.68) где а; и 6, — коэффициенты ряда. 3.8. Друше дискретные преобразования 1 ЗУАЦО, О о -1 1 шах(1, о а -1 1 ЗУАЬ(2, О а ча.д, О а %М.(4. О О -1 1 ООА' (5, о О ЗОАЫО, Л О -1 ! ЮАЕ(7, С) О Рнс.
З.б. Упорядоченные по возраетвннш функции Уояша до н = 7, которые покшыяавн времена днснмтишцни дяя матрицы преобразования Уояшв порядка 8 к 8 Для любых двух функций Уолша А7-1 А нас(,~!%Ос(,,О - ( О=а т.е. функции Уолша ортогональны. Пара дискретных Уолш-образов — это (С-1 Ха = — ~~! х,зу!(А1(!О,з)!с = 0,1,...,А( — 1 (3.69) (=о х, = ~~ ХО%А1 (!с,з)(с = 0,1,...,А( — 1, (3.70) где следует заметить, что, не считая множителя 1/Ф, обратное преобразование идентично прямому, и (ОАЬ((с, О) = х1. Следовательно, пару образов можно найти простым Глава 3. Дискретные преобразование 170 (3.71) где ан = [хсхзхз...
хи з[ — последовательность данных, И'и И'ог ... пан — ~ И'и тки-га 1Рм-ьт .. И'и-ьн-~ матрица преобразования Уолша, а Хь — — [ХсХз... Хн,] — (М вЂ” 1) компонентов ДПУ. Заметим, что Игы — это матрица порядка 1т' х 1т', где 1т' — юличество заданных точек, т.е. точек дискретного сигнала.
Следовательно, если есть 1т' точек данных, то нужно рассматривать первые 1т' упорядоченных функций Уолша. Каждая из них дискретизуется )т' раз, при этом Й-я строка матрицы %ы соответствует )т' дискретным значениям Й-го юмпонента последовательности. Ирна(ар, З.б' В качестве примера найдем ДПУ последовательности данных (1, 2, О, 3). Она состоит из )т' = 4 точек, так что Жм — это матрица порядка 4 х 4, которая получается из первых четырех строк рис. 3.6: 1 1 1 1 1 1 -1 — 1 1 -1 -1 1 1 -1 1 — 1 (3.72) Следовательно, из уравнения (3.71) Х(/с) задается как 1 1 1 1 1 1 -1 -1 1 -1 -1 1 1 = — [6 0 2 -4], Х(Й)= — [1 2 0 3] 1 4 1 -1 1 так что Хс — — 1,5, Х~ —— О, Хз — — 0,5 и Хз — — — 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
