Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 26
Текст из файла (страница 26)
Структура алгоритма свертки такова, гго сначала выполняется иенаторое множество сложений, затем некоторое ыноже«гво умножений, а затем опять некоторое множество сложений. Рассмотрим 5-точечный двоичный БПФ-алгоритм Винограда, вы'желающий где е =. 4- " . Сначала воспользуемся описанным в равд. 4.5 !» я алгоритмом Рейдера, переводящим рассматриваемое преобразо- вание Фурье в цнкляческую савраску 3 (х) й (х) б (х) (н»об х* —.
1), где многочлен Рейдера й (х) = (е — 1) х .1- (е' — !) х» + (е' — 1) х ф (е — 1) имеет фиксированные коэффициенты. Вход я выход фильтра опи- сываются соответственно многочленамн б (х) — а»х' + и,х + аах + и», з(х) = (Ув — 14)х -! (У» ! )х» ()» У)х+ (1»» — 14). Коэффнциенты многочлена 3(х) получаются перестановкой козф. фицнентов входного многочлена и(х); козффицие»пм многочлена У (х) на аь»ходе алгоритма (с точностью до слагаемого У,) полу- чаются обратной перестановкой каэ)фнциен»ов миогочлена з(х) на выходе фил»шра. 5-точечный БПФ-алгоритм Винограда получается, если нро. и»ведение д (х! Л (х) вы ислять с и мощью ал.оритма Винограда хля малой свертки.
Васпользуеися приведенным на рис 3 !4 и сапержащвм пять умножений алгоритмом 4-точечной цикличе- ской свертки. Его можно приспособить лля вычисления преобразо- вания Фурье, введя в матрицу свертки операции перестановок путем соответствующей перестановки ее строк и столбцов Таь к»к коэффициенты многочлеиа 5(х) фиксированы, то вычисление произведения вектора й на его матрицу также можно выполнить заранее.
Если в алгоритме 4-точечиой свертки произвести все эти изменения и инестн в него члены и, и Уе то и папу »ится 5-точеч- ный БПФ-алгоритм Винограда, ша»»двртная матричная форма которого показана иа рис. 4.15 Зта стандартная форма окажется очень подезной при построении в гл. 3 гвеэдовых метадон. Заме- тим, !га в алгоритме на рис. 4.15 матрины предслажеивй и пост- е,»ожений не являются квадратными.
5-точечаый вушдной вектор дополняется до Б.точечного вектора, к компонентам которого применяется умножение. Верхние две страни связующей матривы не содержат умножений, таи как связывают а, и Уе Другие пять строк соагиететвуют алгоритму вычисления 4-точечной цикличе- ской свертки. Одна ив констант умножения сказалась равной единице, так что на самом деле алгоритм содержит только пять нетривиальных умножений и одно тривиальное.
На рис. 4.15 видна также н другая важная деталь алгоритма, Хата нет никаких причин ожидать этого, все диагональные зле. менты оказались чисто вещесгвеннымн или чисто мнимыми '). '! пу ч грацу пс еа к аиа. Тогд з ти х и аьиай рнцм а у «и о ыщ нева на. 4.6 Ал рити Вн рга лш 6 рм прмермо Фурье 464 ч — м. = СВА ь в,=| ( г+ гп — 4 ,4 е — ав г ! 1 ! 1 г о г о г 2 з -г -г г — г гз Р .
4.Ш. Э-гочтнна ВПФ. р ч Ваг грела. Эта существенно потому, что означает, чта в случае вещественного входного вектора каждому умножению отвечает одно вещественное умножение, а в случае камплеи«нога входного вектора каждому умножению отвечают два вешествениык уиншкения. Это явление оказывается довольно общим. Если р почетна, то можно записать 1=(„ы — пп П(Н вЂ” игг ! !) Делителя многочлена х' ' — ! делвт один из множителей, стоящих справа в этом равенстве Следовательно, когда алгоритм Винаграда для вычисления свертки разбивается на подзадачи, соответствующие делителям мнагачлена хе †' — 1, та ситуация описывается следующей теоремой.
Теорема 4.4.!. Лугом д (л) — мвогочлев Рейдера! тогда для каждого нештнош р коэффициенты ииоаочлени д (х) (шод хгг — 'гав — 1) легяются ееиреапеелвмми, а юаффичиелты лногочлеиа . д(х) (пгобхг 'гл -1- 1) являются мл чили. [1[ 1~:. ! Докшатггьс~аю. Так как элемент и примитивен, то ле†' .= 1 и п' аг' =- — 1. Так каи г — г д (х) - Е (м" — 1) х", та коэффициенты миагочлеив й (х) (шад х1 тги ~ !) даются ра земствами ( г !) ( 4;-(г-гггз !) Утверждение теоремы вьпенавт теперь из того, чта пгг — цгг = = — 1.
С4 Мы показали, как строится БПФ.алгоритм Винограда малой длины лля случаи, когда длина преобразования л является простыы числам. БПФ-алгоритм Винограда малой длины может быть построен и в случае, когда длина л преобразования равна степени простого числа. Эта канструкния также основана на аналогичной алгоритму Рейгера идее перехода от преобразования Фурье длины р", р просюе, к свертке. Однако множества целык чисел и дулю р не образует поля, у у спгует элемент гг порядка р" — 1. Случаи р = 2 н нечетного простота р решаются двумя различными методамн, Сначала рассмотрим случей нечетного простого р )(лича нреоур ыоеилия розна слитии просглою нечетного число. Конструкция несколько усложняется. Сначала для выделения циклической группы порядка р'-'(р — 1) иэ множества (1, 2, ..., р' — 1) всех индеисов удаляются целые числа, кратные р. Эта циклическая группа привозит к свертке длины д' '(р — 1), которая образует ядра алгоритма вычислення преобразования Фурье.
Как н прежде, она вычисляется бысгрыы алгоритмам свертки. Компоненты свертки нужна переставить по правилу, обратному перестановке входных компонент свер~ки, и подправить члевамп, учитывающими выброшенные р'л строк и столбцов Как мы увндим, юи поправочные члены можно вычислить алгоритмами еще меньших сверток, так как онн представнмы в ваде алгоритмов преобразования Фурье малой ллвны. Например, прн Рр = 9 -. 3' удаление номеров О, 3 н б из множества всех индексов приводит к подмножеству (1, 2, 4, 5, 7, 8), образующему относительно умножения по модулю 9 циклнческую группу, изоморфную аддитивной группе д, целых чисел (О.
1, 2, 3, 4, 5) относительно сложения па модулю 8. Мультнпликативная группа порождается степенями 2 по модулю 9, так как эти степени равны соответственна !1, 2, 4, 8, 7, 5!. Таким образам, 9-точечное преобразование Фурье содержит шесть строк, которые можне иволнровать, переставить и вычислить в виде свертки. Нетрудно предвидепь, что остальные строки и столбцы (с индексами, равными О, 3 и б) имеют структуру, близкую к 3-точечному З з *в г !бз г б. Алг Реи Вне грели л» б Р * Р бР н ФРР * ые Гл.
!. Вн Р * злюртн д Р ог ире бр тине Фуо преобразованиго Фурье, так что некоторые из попрапочшгх членов могут быть выражены в виде свертки малой длины. Построение 9-точечвога БПФ-алгоритма Винограла проводится следующим образом. Вмпишем матричное ураннение ! ! ! 11 ! ! ! ! 1 Р) 1 Посмотрев иа эту матрипу, можно убедиться, что строка и столбцы с номерами О, 3 и 6 яилян~св для нас новыми, так иак содержат псвториюшаесе э емегпы.
Переставим стра и и столбцы матрним тзк, чтобм эти строки и столбцы оказались в новой матриие первмми, остальные с~роки расположились в порядке степеней двойки па модулю 9, т. е. в порядке 1, 2, 4, 8, 7, 5, а столбцы— в оорядке степеней 2 ' по модулю 9, т. е и порндке 1, 5, 7, 8, 4, 2. Тогда вычисление преобразуется к виду 1 ! ! Пунктирные разбиении, сделанные в матрице, показывают сформировавшиеся циклические свертки: одну 6.точечную цаклическую свер~ку и иметь 2.точечвы» инклических саертои.
Те 2-тачечвме оеср! ьи, которые распагюжены во второй и третьей строках матрицы, содержат повторяющиеся вычисления, чта позволяет переписать входюцне в эти две строки вычисления в виде Таким образом, полходищим способом выполненные перестановки н разбиения входяых данных н матрииы преобразования поэзо. лили представить рассматриваемое преобразование Фурье в виде одной 6-точечной ииилической свертки и двух 2-точечных цикличесиих сверток.Можно было бы ожидать, чта так организованное вычисление потребует 12 комплексных умножений..Однако, «ак показывает слепующая теорема, происходят две вещи: 1.
Все умножения являются чисто вещественными или чист мнимыми, так что !2 комплексных умножений превращаются в \2 вещественнмх умножений 2 г!испо необхоанммх умножений уменьшается до 1О, так как два коэффициента оказываются равными нулю На самом деле мм выпишем алгоритм с 11 умножениями. Одна умножение иа единицу необходимо добавить для гаго, чтобы строку с номером нуль записать в алгоритме в таком же виде, как и остальные строки. Теорема 4.6.2. Пусть т > 1 целю, а р — простое нечеткое чи яо. Пу Ь = (Л вЂ” !) р — '. Пусте д(х) — обебивкк Д кког-! гоч ея Рейдера, д (х) — — ~ в"гхд где в †коре из единицы етег-е неки р" и я целое число порядка Ь относительно умножения ° модулю р .
Тогда: (1) Коэффициенты мкогочгека д (л) (тод хьг' — !) т явлия еещестеенкмни числили; (В) Козффкциекяв! лкою гела д (х) (шод хгж -1- 1) являются ккимммп числами (ГВ) Коэффициентм мкоючтки д (х) гтод хггг — 1) ртты кулю Доказаомльстео Доказательство первых двух утверждений теоремы аналогична доказательству теоремы 4.6.1. Так квк поря. док числа и равен Ь, а Ь четно, та и' = 1 н я'!' = — 1 Тогда ьоэффициенты миогочлена д (х) (тод х!'! ~ !) равны дг = в Ш вы! "гг!'.
Так кап и'Л вЂ” — — 1, то отсюда сразу вытекают пер. вые два утверждения теореим. Для доказательства утверждения (пг) рассмотрни многочлен г-1 д'(х) =д(х) (шод хмг — 1) =- ~ во!хе (!под хюг--1). г-е Коэффициент де равен сумме тех «азффицнеитов многочлена д (х), индекс Д которых кратен числу Ь(р. Таких членов имеется р и!тук. и — ! де= ггв б' 1Э4 Г . 4 Н р с элыр т ттр»ттт прворают Фуг е 46 А гв В а*град ю а г эг Юр г тиг Фгг геэ В общем случае коэффициент у) дается равенстэом -г Требуетсз доказать, что й, равен нулю двя всех таких г. Перепишем выражение для у, а виде — ! у,' - ~ (вы)" г=о Так как в»' опнть яалвется корнем степени р" иэ е,ганиды.
то утверждение достаточно доказать тол»ко для г, рваного нулю, т. е. для уо '=' ~ в , гле в = и'гг представляет собой элемент 4=4 порядка р. Последнее равенства можно переписать в зиле йс - о'й (гг')", »=о где в' являеюя корнем степени р из единицы. Следовательно, 16 = О, и доказательство теоремы закоачево. (2 Таиим образом, чы умеем строить ВПФ-алгоритм Винограда малых длин, равных степени нечетного простого числа. Матрица преобразования Фурье размера р" к р разбиваетсл на (рв — р" ')-точечную циклическую свертку и р" ' -1- 1 (р — 1]- точечных циклических сверток. Согласно теореме 4.6.2, все эти свертки вычнсляются с помощью алгоритма Винаграла длн шгклических сверток, содержащего тол~ко чйсго вещественные и часто мнимые умножение.
Л ино аргаброюеония рагяа слмоеаи двойки. Прсабраэоиапие Фурье, длина которога равна степени двойки, приходятся рас-, сматривать отдельно, так как целые 'пыла, не превосходящие 2», взаимна простые с 2, не образуют относитечьно операции умножения па модулю 2 циклической группы (за искчюченвем случаев т = 1 и т = 2).
Это множество чисел образует группу, изоморфную группе л» х 2, г. По этой причине коншрукцггя ВПФ- алгоритма Винограда ллины 2 содержит на адин шаг больше. Прежде всего, отберем 2» — ' строк и столбцов матрицы с нечетными индексами, подобно тому как зто было сделано в раза. 4.5. Эта подмножество элементов матрицы будет переупорядочено тегюрь не в одну, а в четыре циклические свертки Строки и столбцы с четнымн иидексачи можно представать в виде преобраэованэя Фурье длины 2"-' несколькими способамн.. Эта часть вычислений представляет собой 2 -пточечиое преобра-, зование Фурье. Разбиение а некотором смысле аначогичва олному шагу алю- ритма Кули †Тыч по основанию 2 Предположим, чта мы уже умеем строить 2"' пточечнае быстрое преобразовавне Фурье Для задандога 1'» = ~ вмиг, й = О...., л — 1, «омпаненты — с с четными значениями индекса й можно записать в аиде мг-~ )'з» ..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
