Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 25
Текст из файла (страница 25)
Итоговая форма 5.то'осевого алгоритма Рейдера задается уравненнямя: б (х) =- о,хо -1- е,х' -1- о,к -1- пь з (х) = (Уо — Уо) х' + (1'4 — Уо) х' + (Уо — У ) х + (Уо — Уо) к з (х) = й (х) б (к) (щоб х' — 1). Многочлен й (х) фпксправзн. Многачлен 3 (х) образуется перестановкой козффнциентов многочлена о (х). Многочлен У (х) получается обратной перестановной коэффициентов многочлена з(х). Схематически этот алгоритм представлен на рнс. 4.13 Поучительно переписать алгоритм Рейдера в матричной фор. муляровке.
Для 5.точечнего преобразования Фурье такая фор. мулнровка имеет вяд 4зз пыл ймгаг !ьь Зь И. К. Г ! !аэ Гт 4 Бмстрм ю р н д саэ ю о р аэ ю Фуз Ри. 4.!3. Алгоритм Рчзаеза Э. ю эрюаг Фгр где я, .= и — 1, д, = м* — 1, й, = м' 1, 8, = Фг '1. Идея алгоритма Рейдера переносится иа случай, когда длина л преобразования равна степени нечетного простого числа.
В этом слу4ае, подобно тому, как нулевые компоненты временного и частотного векторов обрабатывались отдельно, еще некоторое «ели честна компонент временного и частотного векторов должны обрабатываться отдельно. Эта объясняется тем, что в кольпе Е((р ) ве существует элемента порядка р" — 1. Теорема 5.!.8 (которая будер доказана в гл. 5) гарантирует, однако, что для простого нечетногО р в этом кольце имеется элемент порядка р"-4(р — 1), и мм этим воспользуемся. При вычислении Уь= Е мгьоь й=б, ..., р — 1, Г 4 воспользуемся структурой кольца 2/(р") для тато, чтобы лере. упорядочить компоненты некторов. Эта структура описывается теоремой 5.1.8. Вели д раино с4епени простого нечетного числа, тО 8((р") СОдсржит ПИНЛИЧЕСКуЮ ПОдГруППу ПнрядКа рнш (р — 1), из (р" х р )-матрины зу = !и"! просто выбросим зсе вызы. ваю4цве трудности строки в столбцы так, чтобы к оставшейся матрице разь4ериости р -' (р — !) была применима идея Рейдера.
Вмброшенные строки и столбцы будем обрабатывать отдельно. Как мы увидим в следующем разделе, обработку даже этих вы. зывающих трудности столбцов и сгро» можно организовать как вычисление еще меньших циклических сверток. Таким образом, вычисление р точечного преобразования Фурье, хотя и слишком нерегулярвого для того, чтобы быть вычисляемым как единое целое, можно реализовать в ваде всего нескольких разумных фрагментов. Случай, когда длина преобразования равна степени двойк», является несколько более сложным и требует еще одного уровня вычислений. Это объясняется тем, что множество индексов, взаимнО про.
етых с 2 — множество нечетных индексов — не образует никли. ческой группм по умножению. Квк доказывается в теореме 5.1.8, это множество образует группу, «воморфную группе 24 х 2, з. Идея организации процедуры вычислений состоит в следующем. Иэ (2" х 2 ).матрицы ДУ = 1а'41 выбрасываются все строки н столбпы с четными нндексамн, так что остается матрица размерносю 2"л. Все оставшиеся индексы являются нечетными н по Умножению обРазУю~ гРУппУ, нзомоуфнУю гйрппе 24 Х дю з.
Этот нзомарфиэм используется для того, чтобы определить такую юз н соответственна ~з Р~= Емгзоь й=о, ..., 15, перестановку строк и столбеов матрицы, которая переводит ее в матрицу вила где %г и %, представляют собой (2 -'к2 -')-матрицы, каждая нз которых задает структуру циклической свертки. Точнее, пусть и = 3 и о = 2 — 1. Тогда по модулю 2" имеем о' == !. На самом деле группа нечетных целмх чисел относительно умножения по модулю 2 порождается элемевтами и и и: каждый элемент группы может бмть однозначно представлен .в ниле сгл', где 1' =.
О, 1 и 1" .=. О, ..., 2 -т. Следоцттельно, мы = и' " " " , и подходящей перестановкой строк и столбцов матрица % приводится к виду где 1" и г" соответственно ивлексы строк и столбцов в кажлой иэ падмшриц. Кавщая из четырех подматриц задает циклическую свертку длины 2" '. После выволнсния перестановки рассматриваемое вычисление приводится к виду матричной 2-точечной цикличесной свертки олив вз способов вычисления которой дается формулой Этим задача сводится к вычислению двух комплекснмк цикличе. ских сверток длины 2 ', мы увидим, что вычислении можно организовать несколько лучше.
В качестве примерз рассмотрим две %точечные цикличесние свертки, образующие серпцеаину 16-точечного преобразования Фурье. Пусть где им = 1. Рассмотрим матрицу, образуемую в результате вы- брасывании всех четных индексов в рассматриваемом диапазоне значений ! и й. Получим Чтобы найти нужную перестановку, выпишем индексы в виде чисел 15г.Эг лля 1'=.
О, 1 и Г= О, 1, 2, 3. Степени тройни по молулю 16 имеют вид Э' .= 1, 3' = Э, 3' = 9, 3' = !1, о. = 1, 3 ' = 11, Э ' = 9, 3 ' = 3, 15 3' = 15, 15 3' = !Э, !5 3* — — 7, !5 3' = 5, 15.з- = 15, 15.3 ' = 5, 15 3 * = 7, 15 3 ' =- 13 Выполним перестановку входных индексов, ваписывая их в гга рядке 15-и Э-и (шоб16), и перестановку выходных индексов записывая их а порядке 15г.йг (шоб 16]. Тогда Чтобы показать четыре образшшвшиеся при этом циклические свертки, матрица разбита на блоки. Если преобразование Фурье вычисляется в поле комплексиык чисел, то блоки связаны сам- вошеиием камплеисной сооряжеиности. Чтобы наглядно выявить зту связь, перепишем матричное уравнение а зиле Отметим, что четыре верхние строки иомплексио сопряжены с четырьмя нижними строками; выполнять паде только вычислеэия.
связанные с первмми четырьмя строками. Следовательно, хзльиейшие вычисления можно организовать в виде пиры циклических сверток Уэг'+ Уэх -)-1'ох «- Р1.= =- (ыох' «- ы'х'+ м'х-(- м) (с„х* Р о,х' + сэх+ о,) —;- .«- (и гзх «- ы 'хэ -(- м 'х -«- и ') (гьх + с х + омх+ оо) (шоб х' — 1), Лля комплексного поля можно испольэовшь и альтернативный способ, основанный на выписанной выше 2-точечной циклической свертне блоков: Заметим, что теперь мы получили две циплические свертки, одиа из которых чисто вещественна», а Лругая — чисто мнимая Для случа» эещественнога входного вектора необходимо вычис- лить только две вещественные свергни, .
(х) -- (сот 38х' .«- соз 96х' «- саз 118х -!. соз 8 ! Н (х) (шоб х' — 1) п г' (х) =- Ь(п 38х' + мп 98х' .«- Ып 110х -1- мп 0 ) 8' (х) (шоб х' — 1) Испольэу» .китайскую теорему об остатках для разложения х' — 1 = (х" — 1) (х" + 1), видим, что некоторые вычисления излишни, так как саз 30х' -1- саз 90»' «- соз 110х -~- соз 0 .=- О (шоб х' — 1) и юп 30х «- юп96х'-1- ып!16х-1- юп 0 = О (шобх' — 1). Следовательно, умножения, связанные с модулем х' — 1, ие нужны, Вычеты по модулю х' -Ь 1 требуют трех умножений каждый. Следовательно, вля вычисления двух циклических сверток асобходчмо в общем только шесть умножений. Исходное 16-точечное преобразование требует, таины образом, всего 10 петри виальных умножений. 4.0.
Алгоритм Винограда для быстрого преобразования Фурье малой длины 19 99 а* Из сш 99 и 99 ом 99 ссз 9 со гш аи 99 ~ Г ! 9 газ!9 (М, — ВО! = гэюэз г ги /ваза Г 99 ! ва 99 и 99 пэ г Из г ва 39 гааз « ~Р,~ ~! 11~1(тт, г Чг гхс при 0 = 2я(!б (сю 99 Этот БПФ-алгоритм Винограда предназначен для эффектна ного вычисления дискретного преобразования Фурье малой длины.
В основу алгоритма заложены две идеи: рассмотренный в предыдущем разделе алгоритм Рейдера для простык длин и рассмотренный в равд 3.4 алгоритм Винограда длв свертки. Рас. сьютрению подлежат три случая:(1) длина равна простому числу; (2) длина равна степени простого нечетного числа и (3) длина равна степени двойки. Наиболее попупярными длинами являются 2, 3, 4, б, 7, 8, 9 и !б.
Характеристики БПФ-алгоритма Винограда аля этих длин приведены на рис. 4.14. (Сами элгпритмы выписаны в приложении В.) Число умножений на этом рисунке упомииаетсч дважды: один раэ приведено число умножений беэ учета трчвиальныХ умножений, а другой раз — полное число умножений, вилючаюшее умножения на (~1) н (~!), Если БПФ.алгоритм малой длннм используется в качестве блока для гнездовога алгоритма. который будет изложен в гл. 8, та умножения ва (ж 1) и (ж)) а малом алгоритме приводят к нетривиальным умно.
уч» и«чагр а глх ии р о ар ашю их Фуи 169 2 6 В 17 36 ш И 34 94 74 !37 186 о 2 а 6 В 2 10 26 29 !а 36 38 2 3 4 6 9 В 11 21 2! 13 36 39 2 3 4 6 7 6 9 1! 13 16 17 19 Ре. 4 Ы. Хар»у с БПФ.»аюи аеэ Винограда мз ад даки . У =- Е ееи„д = б, ..., 4, »-4 ениям (и г ж ниям) б ием алгоритме. П тому мы аы нсываем как полное числа умножений, так и число умножений без учета тривиальных. В характеристики алгоритмов, приведенные на рис. 4.14, вкчю»сны также некоторые тривиальные сложения. Сюда атно.
сигея чисто вещественные и чисто мнимые сложения, которые согласно принятым определениям ие нвляютси сложениями На при подсчетах сложное»и мы не будем различать тривиальные и нетривиальные сложения. Если заменить вещественный вектор комплексным, то все сложения становятся нетривиальнмми комплексными сложениями. Длина преобразования равна лрасеаму числу. Первый шаг состоит в замене преобразования Фурье сверткай. Если и мало, то воспользуемся алгоритмом Рейдера для замены преобразования Фурье свар»кой, которую нычис.чим затем, нспольэуя алгоритм Винограда для сверток малой длины. Длина л выбирается не свишком большой, так как необходимые уравнения выписываютск вручную. Переход ст преобразования Фурье и свертке с помощью алгоритма Рейдера осуществляется только перестановкой индексов; этот шаг не содержит ни умножений, ии сложений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
