Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 46
Текст из файла (страница 46)
Так как безразлично, вычисляюгся ли первыми преобразования по строкам или преобразования по столбцам, то чажно также записать Ч .= %'%'т. Это обьясняется тем, что операции по строкач «омчутируигг с операциями по столбцам, так как такая запись означает просто изменение парадна суммирования. Пред- хтз Га. В. В р алюрэтн огонез нх пр Ерзюза»за З.з. ят *р Л знс зз — взрззсз положим теперь, что имеются малые БПФ-алгоритмы Винограда с ХЧ' = С'В'А' и УУ" = С"В"А'.
Тогда Ч --(С'В"А")(С'В'А') ч .= (С'В'А') (С"В"А") т. Две матрицы с одним я тем же количеством штрихов не номмутируюг. Однако, как мы виделн при исследовании гиевдоаого метода Винограда, матрицы с различным количеством штрихов иоммутвруют. Для формального доказательства можно обратиться и теореме о кронекеровском проиаведеннн матриц. На самом деле, это опять не более чем изменение порядка суммирования. Таким образом, можно записать равенство У = С'С" В'В'А'А "ч, н о е Ч з которое представляет собой большой БПФ-алгоритм Винограда.
Его можно записать также в виде Ч = С'В'С В'А'А'т. Для построения БПФ-алгоритма Джонсона †Барра необхо- дима еще одна хитрость. Прежде чем менять порядок следования матриц суммировавия, разложим нх в виде произведений: Вг' = (6'Н') В' (Е'Р'), В' = (6" Н ) В" (Е "Р'), где С' = 6'Н' и тан далее. Тогда мы получаем произведение Ч = 6'Н'В'Е'Р'6'Н" В'Е Р"ч, н к л щ ш.
чь «оторсе можно переупорядочить следующим образом: У = (6'6"Н'Н')(В'В ) (Е'Е"Р'Р') ч. В эгей форме записи обе диагональнме матрицы В' и В" собраны вместе и даже заключены в скобки, чтобы подчеркнуть этот факт. Зги идеи хорошо нллюстрируютсп 35-точечным преобразованием Фурье.
На рнс. 8.6 вмписаны 5-точсчный и 7-точечный БПФ.алгоритмы Винограда, каждый из которых состоит из пята этапов вычяслевий. Имеется множество способов сочетании их в 35-точечный алгоритм БПФ, наиболее интересные три нз которых указаны на рисунке. Два из них соответствукп гнездовому методу Гула — Томаса и гнездавому методу Винограда. Гнездовой метод Гудз — Томаса привадат к меньшему числу сложений, а гнездовой метод Винограда — к меньшему числу умножений.
Надобности выбирать между этими альтернативамн, однако, ие вовинкает, так каи имеется гнездовой алгоритм Джонсона †Барра, который содержит столько же умножений, сколько алгоритм Винограда. и число сложений. близкое к числу сложений в алгоритме Гуда †Тома, и, следовательно, ему надо отдать предпочтение.
Зэа Гл.з,виста г р тмэи»зггбэ З Зб А. З гыэм Использование БПФ алгоритма Джонсона — Барраса не приводит к каким-либо осложнениям Все новое, что он привносит, сводится н разбиению сложений на отлельные пакеты, которые можно реализовать в виде отдельнмх подпрограмм н затем обращаться к ннм, вызывая нх в нужной последовательности. В процессе вычнсленяй мы по«тоявио переходим ат сложений ва строкам к сложениям па столбцам н обратно 8.6. Алгоритмы разложения Милый БПФ.алгоритм Винограда сводит задачу вычисления одиоыернога преобразования Фурье к задаче вычисления одномерной циклической свертки, используя для этого алгоритм Рейдера. Теперь мы восвользуемсв этой же процедурой для многанерных преобразований.
В общем случае вычисление преобрззава. ния разлагается в вычисление нескольких циклических сверток. Число точек преобразования по каждой из осей многомерного преобрзэавания должно быть равно простому числу или степени простата числа, хотя и не обязательно одной и тай же для различных измерений. Сначала, используя вдоль каждой из осей алгоритм Рейдера ил» его обобщение, сведем мнагпмерное преобразование Фурье н многомерной свертке. Теперь применим алгоритм быстрого вычисления многомерной свертки Для тато случая, «агда число точек преобразования вдоль всех осей одно и то же, в равд.
8 7 будет описан алгоритм с лучи!ими характеристиками, которому и следует отдать предпочтение. Поэтому алгоритмы разложения представляют интерес в первую очередь для тех случаев, когда соответствующие различным асям числа точек преобразования различим. Идея сводится к простому обобщению процедуры для однамер. ногослучая.
Начнемсдвумерного(п' х п')-преобразования Фурье для взаимно простых и' и л", возможно, различных: й' = О, ..., и' — 1, дг м'гр'гт Для того чтобы васвользозаться алгоритмом Рейдера, надо исключить нуль из показателя степени. Для этого па аналогии с алгоритмом Рейдера рззобъем уравнения на четыре группы: " †! Уэ,г= Х Е апът ! =л !"=г — ! Уг.! — Уг.г = гъг (рггм — 1) ~ пг, г, й" — —. 1, ..., л* — 1, !" — ! ! -г )„, г У,, = Е ( " ' - !) Е аг и, й' -.. 1,..., и' — 1, ,"-а ' — ! уг,! — 1'г.г — !'е,г"-!.уг.г = ъ У ('а' !)(р' Паг,г, г ! !" — г й'=1...., л' — 1, й"=.1,..., «" — 1.
Сделав такое разбиение н применив перестановку, даваемую алга. ритмом Рейдера, мы сводим зздзчу н вычислению (и' — 1)точечной свертки, (л — !).точечной свертки и (и' — 1) х (л" — 1)- точечной двумерной свертки. Для вычисления обеих одномернык сверток можно воспольаоваться построенными в гл. 3 алгоритманн Винограда. Согласно теоремам 4.6.! и 4.6.2, все умножения в этих алгоритмах являются умножениями талька на веп!ественные или только на мнимые константы, и, следовательно, требуют в случае вещественного входа талька по одному вещественному умножению Для вычислении двумерной свертки можно воспользоваться любым хорошим методом. Одним из них является описанное в гл 7 налиномиаль нас преобразование.
Алгоритм двумерной ((л' — 1) х к (и' — П)-точечной свертка можно также строить гнездовым методам, используя подходящие двумерные циклические свертки меньюнх объемов нли даже малые алгоритмы одномерных никли. ческнх свертан Напрнмер, задачу вычисления двумерной (4 х х 12)-свертки можно преобразовать, используя по «тарой оси алгоритм Агарвала †Ку, в задачу вычистення трехмерной цик. лической (4 х 4 к 3)-свертки.
Для решения последней задачи можно воспользоваться гнеэдовым методом сочетания алгоритма вычисления двумерной циклической (бх4)-свертки с алгоритмом 3-точечной цинличесной свертки. Если для вычисления двумерного преобразования Фурье используется алгоритм двумерной циклической свертки, то во всех умножениях один нз множителей всегда оказывается либо чисто выцествениым числам, лигю чисто мнимым числам. Частный случай этого утвержденна дается следующей теоремой, представляющей собой аналог теоремы 4.6.1.
Ттрема 3.6.1. Пусть р — иечетисе лрттгг ч сга и у (х, у)— .иэагаюгэ Рейдера ат дгух пгргмгини степени р — ! па «лждай из иих Пусть () (х) и !3' (х) — кругагиг мпаигыгии, дглящиг хг— — !. Тогда ла модулю Б (х) и аа модулю (г' (у) кагффипигити ииагач гил у (х, у) «ргдстагляют собой либо нисою ееигстггииыг числа, либо чиста миииьи число.
Доказательство аналогична доказательству теоремы 4.6.1, ! ) Можно доказать более общую теорему для случая, когда числа точен вреабразовання по обеим осям равны (не обязательно адина. казмм) простым числам или степеням простых чисел. В 6 ааг Эат м раза ме еа 84 68 424 84 660 1.28 1.39 133 1 36 1 74 9 20 13.26 Н 21 11 30 14 Ю л 78 36 34 424 78 650 282 Гл. В. Б Р э загар и и р»н р серзюзэ В Вх6 ЗЗ 32 230 тхт 69 68 660 9х 9 ИЮ 108 908 тхв Вг 86 712 ВХ13 114 Нз 917 Р с, 8.12.
Хзрачт ра та«щ юг р Р Нтые т Р— Кыйхелла. ! Характеристики некоторых по. строенных таким способом двумерных алгоритмов выписаны на рис. 8.12. Если сравнить эти характеристики с приведенными иа рис. 8.18 характеристиками, то можно увидеть, чш для 5 (р Х р)-точечных БПФ-алгоритмов ланный способ проигрывает приведенному на рис.
8.18. В качестве орнмера рассмотрим 7 двумерное (7 х 7)-точечное пр собр а зава- ние Фурье. Как показано на рис. 8.13, 1714'71 „,',П 'з,„„„„„о „Оиа РаелаДастеа В ВЫЧИСЛЕНИЕ ДВУХ 6-точечных циклических сверток и одной двумерной (ВХВ)-точечной цннлической свертки. Для вычисления каждой 6-точечной цннлической свергни необходимо восемь вещественных умножений. Алгоритм вычисления двулгерной (6х6)- свертки ыожно строить гнездовмм методом, сочетая алгоритм циклической (2х2)-свертки с алгоритмом циклической (ЗхЗ)- свертки, данным на рис. 7.3. Для такого вычисления необходимо 52 умножения, так па а общей сложности полуеаем 68 умиаженнй.
Еще одно, тривиальяое, умножение (нв !) нужно для гаго, пабы представить в том же виде вычисление компоненты Уьы это существенво при нспальзовэнии данного Пху)-БПФ-алгорлитма в качестве составляющей в гнездоьом методе построения больших БПФ.алгоритмов., Подсчет числа сложений несколько более громоздок, и результат зависит от шго, насколько удачно организованы уравнения. Сначала рассмотрим уравнения в там виде, на» пни были выписаны выше.
Тогда вычисления состоят нз некоторых предсложений, предшествующих обращению к двум 6-точечным циклическим сверт«ам н одной (бхб)-точечной двумерной циклической свертке, и следующих за этим постсложеннй. Некоторые предсложения и пштслаження входят ханже и в алгоритмы сверток. Полное гисло сложений тогда вычислнетси так: Предсложения Две 6-точечные циклнмюкие свертки Цищгическея (бх 6)-свертка Постсложения Однако мы знаем, что если собрать вместе все предслажепия, внлючая н те, которые вкодят в алгоритмы сверток, та возможно уменьшение числа сложений. Аналогичного уменьшения чнсла слежений можно добиться, собирая вместе все постсложепив.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
