Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 27
Текст из файла (страница 27)
)) (иг + е, .»т,)вн », й = О. . . л)2 - 1. г г Это 2 -кточечное преобразование Фурье может быть вычнслено уже известным алгоритмом Компоненты с нечетными значениями индекса д можно записать в ваде У ° —. Х,'О Вы М»ЬП 1- ~ ~О г .г г=э Так как в' является корнси из единицы степени 2 — -', та небаль. шие вычисления позволяют первую сумму переписать в виде преобразования Фурье ллинм 2 ' Так м образом, 1 уг» гг — Хюг (в г и»г' — в г оны„м) в ' + г -с 12 — 1 + хг ииыгвт """+", Д:=О,, а)2 — 1, г.— о где первая сумма подлежит вычислению только дла первых п)4 зна- чений индекса АС й =- О...
п(4 — 1, так как патоы зти значения суммы повторяются. Если входная послеповательнасть давних валяется вещественной, то эта 'ысть вычислений состоит из 1п)2) — 6 вещественных умножений н (л)4)-точечного преобразо- вания Фурье. а если входная последоватетьнасть данных является комплексной, то к (п)4)-точечному преобразованию Фурье добав- ляется (3)4) л — 6 вещественных умножений, Вторая сумма е уравнениях лля У,» 4, мажет быть вычислена рассмотренным в предыдупгем разделе абабигенным алгоритмом Рейдера.
Он сводится к вы гислению двух циклических сверток .шины 2" — '. Слелующан теорема показывает, чта если эти цикли- ческие свертки вычисляются на осаоианин китайской теоремы аб астатиах, та часть умножений является умнажев ем на г)ль и мажет быть выброшена Теорема 4.6.3. Пусть т > 2 есть целое шсю и й(х, у)— обобиунимй дгумергмй много»щи Рейдера гида ' †! у(х. у) .
— ~ й,' в " ' х у', г=о г-с где в яе мпт х раем степени 2" из единицы. Тогда щу уравнения в виде Тогда Г„"',1 '.:::;-- ~-:!л ':"-'] =- ~'] '!бб Гл. 4. Бмтр ютр т д сеу и ео «рюбрюою Фурье (1) Коеффидиеяти мятюелгяа д (х, д) (тоб д — 1) являются еетесттллмми числами. (Б) Коэффибиелтм мяогоеюиа д (х, д) (гпаб д -1- 1) мияются млиммми числами. (ГВ) Кюффициелты млогачлеиа д (х, д) (тоб «"'г' — 1) раним лдлю. Дояатателэспгю аналагкчно доказательству теоремы 4.6.2. П Согласно первой части теоремы цннлнческая снерткз па мо.
дулю х" Г' — ! представляет собой дае вещественные цнклнческае свертки (точнее, одну чисто мянмую в опну чисто вещественную). Вторая часть теаремм утверждает, что вычисление циклической свертки сводится только к вычнслеаням, связанным с модулем х"г -1- 1, так как остальные вычеты обращаются в нуль. В силу неприволимасгя многочлена х"г' , '! на этн вычисления требуется 2 (л)В) — вещественных умножений. Теперь мы палучклн разбиение преобразования Фурье на следующие фрагменты: (1) 2 стачечное преобразование Фурье; (2) 2 — з.точечное преобразование Фурье, к т ро. у пред по теует 2" — - '— 1 комплексных умножений; (3) два произведения многочленов по модулю непрнводнмого многочлена х"г' -1- 1.
В-точечное преобразование Фурье разбивается на две части, 4-точечное преобразование Фурье Вторую часть сначала выпишем в следующем ваде: ~:']4:':: ]~:'! Тенер яреобразуе этн равеаства есколько гаче, чем в общем случае, е 4 о, Фзспользуемся услов ем м' ! ~ерег ше 1(икляческую свертку можно вычислить по правилу Ф;] ~! !]~~об а])! 4;/ю —..., Описанный 8-точечный БПФ.алгорнтьг Вннограда содержит всего два нетривиальных умнонгения, кроме того, имеется шесть тривиальных умножений.
Еглп даяна преобразованин равна большой степени двух, то ныпнсызать все необходимые лля вычисления по БПФ.алга. ригму Вннограда уравнения становятся скучно. Лучше предста. вшь этот алгоритм в рекурренгном виде. Мы отложим такое представление до гл. 10. В разл. 10.4 б>дет описан эффективный БПФ. алгоритм по осаовюгню лвв, построенный на идее Винограда, выписанной в рекуррептной форме.
Задачи 4.!. Пу э дз а устройггю зн л- о з х прмбре й Фуры. 4.З. Путь зеа . у у й те эыее «у буюо Фут б. И уе эагоретн Рейдера, з е П-о у брюезю м а„ г е юз 168 Гл. 4. Б.мтр елюр тм д с р ю прюбр зоюп Фурю з()=-8(л)б(). в и ию» многочмн 4(), «(л) ну() ч рю юнит нюты кыров н у н»юммп й й р и дул ою дтва ю пг 4 12 алгтрнпю Кую — Т»ма с ючкамн Бг —. (е(з г )' пр д ткюму мою о уалгорн у,еюннсмы ююню рюбр юев я Фур н тюрю» о слертю. р РЮдера д. » пр с ы чн«р В гр да вюнск иня сюртки прнволнт к упмуБПФ.ю риту,ч с е аюр майл юла с алг р мои В югред в юл н юзр кн.
М Вы у вать тр т м пр чи ут 4.7. Ней рюти пю чила в н ', екн* ч л( ', ю .юючнмй БПФ- р ю В грю южрмю Юльше умюим й, лию й 4.10. Ва р Гуд — Тю д л р л рувтяи рзн у. 1и оо !ю з ы з т г з т т т 8-оч о нр брз ыфур ы(ьр нюьнми)уммк. р ну.ы Бок ют, т б.ю ч й БПФ-а горнтм Внзм рмм олтн. 4.13.
16- «0БПФ- л р В гр л дрм )йу Ф мнй.б лвкюо- Знмсчанм» Гула 131 Прбб) Т . а 141 Прбз) Рюл ° з р.б бы оаи юм Гуди(6)П971) Эффк всма рю зия р Ку — Тези 6л пр дл мн Р Ид ро н Брел р (6) (1976) д ф н р ю Преу 171 (П82) Р ал.р 161П906) вйак й БП(НП0) .. оп с д.н я пр Мр' эю и Фурь ксюрне Цюырб Рйдр б о ыююни дне рт простого чнсю, б лт ю т В р д (П1 П978) БПФалюримВ рл юла рою зрю Пп) 1976г юно н Баррасом П21()98П Вру л» ре брюс Фур юучм нсь Гера ю ПЗ) П968) Сер й П41 (1978) ТЕОРИЯ ЧИСЕЛ И АЛГЕБРАИЧЕСКАЯ ТЕОРИЯ ПОЛЕЙ так что г' я 1" являются соответственно элементами колец х ° и 8, . Так как НОД(д', д") = 1, та отображение индекса ! в пару индексов (г', !") является взаимно однозначным, н для некоторых О' и О' выполняются равенства =дЕ ф-, = Е +'.
В предыдущей главе при построении ВПФ-алгорнтман мм уже пользовались некоторыми результатами теории чисел, которые, однако, доказаны не были. В настоящей главе, представляющед собой математическую ннтерлюдяю, докззмваются все нспользо. ванные ранее результаты, а также резулыатм, которые панадобвтся а двльпеншслг. Им также вернемся к рассмотрению палуб, поскольку нам попадабцтсн более глубокое раввитне идеи расширения аолей. Алгебраическая структура поля будет играть важную роль в следующей гтыае прл пос роения теоретико-шслонмк преабразонаннй, а также в гл.
7 я 8 прн построении многомерных алгоритмов свертки н прсобразоваввя Фурье. Вд, Элементарная теория чисел В польце целых чясел уч по модулю д некоторые элемевтн взаимно прастн с д. а некоторые делят д Нам важно знать, сколько нмевна элементов относится к каждому типу. Определение 8.1.! (Эйлер) Фдикция Эйлера, обозначаемая д (д), длз д ) 1 определяется как число ненулевых элементов э рм вааимно простых с д; д (д) -.. 1 для д = 1. Если д —.— р простое, то все ненудееме элементы копыта х, взаамно просты с д, так что д (р) = р — 1.
Если д равно тепеггй простого числа, д = р, то нс взапмно простым» с д являются толька те элементы, которые кратнм р. Следовательно, е (р ) = = р ' †'(р — 1). Все остальные значения функции Эйлера можно получить, используя следующую теорему. Теорема б!2. Если НОД(д', д1= 1, таф(дд) = д (д) е (д ). Даказатшьстза. ЗанУмеРУсм элементы кольЦа хтш ннцек- сам г' для г' .= О,, д'д' — 1, а затем вмпншем их в заде двумерной таблицы, нумеруя каждый элемент кольце хт.т. парой индексов по правнлу — (тод д ), (шод д ) Предположим, что г' не имеет общих делнтелен с д', а х" не имеет общих делнтелей с д'.
Тогда г не вмеет общих делителей нк с д', нн с д, н, следовательно, общих делителей с д'д". Следовательно, д (д'д") > д (д') е (д ). Обратно, еслн г не имеет общих делителей с д'д", то г не вмеет общих дехншлей нн с д', нн с дц Следовательно,!' не нмшп общих делителей с д', а г" не имеет общих делителей с дц Такам образам, 9 (дд) < Е (д') р (д") н теорема !оказана гг Слсдствне 8.1.3. Если раэложекие числа д иа простив инажители даансэ разгнстзои д = р~ Р,' ... р ', «ю Е (д) - Р( Р Р (р~ — 1) (Рт !) (Р 1) (у Часта оказывается полезнмм другое важное свойство функции Эдлера. Предположнм, что д делит д н обозна гим через ) (д) нека оную функцию аг д.
Под символом ~((д) будем понимать сумму значеннб ! (д) лля всех д, деляшнх д Очевнлна, по х!т так как (д(д) делит д всякий раз, котла д делит д более уднвнтельнай является следующая теорема. Теорема 6.1.4. Функция Эйлера ддовлхтворяет равенству х) Е(д) =д. х~т Даказалшхьстаа. Для каждого д, делящего д, рассмотрнм в гт множество (! ( НОД (г, д) =- д). Каждый элемеят кольца дт йрнггадлежвт точно одному такому множеству. Следовательно, суммируя числа злеменхов во всех этих ножествак, мм должны получить д. Теперь расс отр м экв валент ое о ределе не этога же мно. жества, )!) НОД ! — ', д ) .= 1~.
Это множества содержит л ' л гтэ точно ф (р(й) элементов Сумыиру» па всем подмножествам, по- лучаем откуда вытенает утверждение теореыы. Элементы кольна 7 относител~на сложения образуют группу. Относительна умно кегия ненулевые элементы кольца 2, также могут образовывать группу, хата и ве обязательна Однако в 7, всегда мангна указать подмножества, образующее отнаснтельао умножения в кольце группу, и, следовательно, являющееся подгруппой группы ненулевых элементов кольца 2 в том случае, когда ненулевые элементы таиже образукп подгруппу относительно умножения ПУсть а пРоизвольвый элемент кольца хг.
ПоРожпаемаа элементом и пяклнческая группа равна множеству га, а', а', ... ..., а - ', Н. Порядком шемента а называется число элементов в циклической паюруппс, порождаемой элементам а. Пусть 6 обозна и же к л ц ь ишка р и взаимно простых с р Относительно уинажения па модулю р множество 6г образует группу с ф (ф элементами. Следующая теорема дает информацию о порядке элементов нз группы 6 . Теорема 5.1.5 (теореьга Эйлера) Если НОД (а, р) = 1, та агмг = 1 (той р), так чта порядок элемелти а делит ф (4).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
