Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 6
Текст из файла (страница 6)
Технология цифровой обработки может непосредствецгю испольэовать БПФ, гак что имеется множество приложений, и позтону работа Кули и Гыоки стала гцирко известной. Липзь несколько лет спустя было осознанно, гго лругой БПФ.алгоритм, сильно щличающнйся от алгоритма Кули — Тьюки, был раарабоган раньше Гудом (7! 11960) и Томасом (8! (1963). В свое время публикация БПФ-ал:оритма Гуда — Томаса прошла почти незамеченной Позже Виноград 19, !0)(1976, !978) опубликовал свой более эффективаый, котя и более сложный, ВПФ.алгоритм, который к том) же позволил значительно глубже понять, что в дейсгеительностн оэна.
чает процесс вычисления днскретнога преобразования Фу.рье Неблагоприятным следствием популярности БПФ-алгоритма Кули †Тыч нвилось широкое ра растранение ненни о том, что дискретное преобразование Фурье практично применять лишь при штине блока, равной степени двух. Зто прцнело к тому, на БПФ-алгогитмы стали динтовать параметры применяемых устройств вместо того, чтобы приложения диктовали выбор под. ходящего алгоритма БПФ. Нз самом же деле «орошае БПФ~лгоритмы сущестиуют практически для произвольной длины олока.
Различмые вариации БПФ-алгоритмэ Кули — Тычки появились во многих обличьях. По существу та же самая идея используется для построения многалучевай плоско-фазированной радиолокационной антенны и известна под названием матрицы Бятлерэ П 1! (196!). Для малых длин блакоэ быстрые алгоритмы сверток были ~ первые построены Агарвалом и Кули (12! (1977) с использованием остроумнык догадон, на не не основе общего метола. Общий метод построения быстрых алгоритмов сеертки описал Виноград (10! (!9?8), доказав при этом нажиме теоремы несуществования лучших алгоритмов свертки для палей комплексных и нещесгаеных чисел.
Агарвал и Кули (121 также указали основанный на китайской теорене об остаткак метод разбиения задачи вычислены» длинных сверток иа задачи вычисления коротких сверток. Их метод в сочетании с методом Винограда, прнменяеммй для зычислення коротких сверток, дает харогпке результаты Самая ранна» идея того, что мы предпочитаеы называть быст. рыми алгоритмами, появилась намного раньше, чем БПФ-алгоритмы Алгоритм Левинсона (13! был опублинаван в 1947 г. как эффективный метод решения некоторых теплицевых систем уравнений.
Несмотря на чрезвычайную важность этого алгоритма а обработке сейсмических данных, литерэтура, посэященная ал. горигму Леаинсона, многие голы не пересекалась с литературой по БПФ-алгоритмам. Как правило, в этих ранних исследонаниях ие делалось попыток явно разграничить алгорити Левинсона нак вычислительную процедуру и задачи фильтрации, к решению которых алгоритьг применялся.
Подобно зтбиу, не всегда прово. дилась рааличие между БПФ как эмчислительным средствам и дискретным преобразованием Фурье, для вычисления которого используются БПФ-алгоритмы; аналогично зашстую ае различались алгоритм Витерби кэк вычислительная процедур» и задача поиска пути, к решению которой применяется алгоритм Витерби Задачи 1 ы Р „1 = гл,. Ч а„) Щ; ф ей 1, а * — 0, Уь Евген а=о, 1. З, т Х е е юыовано а з зи и э. ° енса с р нн х у Эо.ю щ . ащ аммый, г *» т .а щ — ат — ьт, /= (ац ь)( 4 Ф вЂ” ж — И. 32 Гл. 1. Вшдепке 2.1, Группы 2в ат Р.
т «с га вм. Кзкезм имю ш ил зпе ум е э га лг Р пз ясз з раа р асрю ваняя Фур, пзр й пршбр з в уг же шлак ш (пгэ) (Р ) ! и (з г )) (пзу„), 1.ш. д мат, ю «ппз с за оррш кна ду шмшз мх ш шшз- мл ш еа 9 н а удо зг ор г аю мпекзю 1— азиз ш унгчьпиш а а. гд 6 и си шстэ пи ресбр ик» Фур е поел швшел шт 2 и Замечаннв анх: Оп еиша э Шаф р (2)11975) н Рэа «р Гша (3! (1975). яоз шо знашзш.
Опз мю иа злюрк у м и з атр п нпнн в нмр эу 14! (19вв). Г пг ВВЕДЕНИЕ В АБСТРАКТИУ)Г Хорошие алгоритмы основаны на красивых алгебра тождествах Для построения таких алгоритмов иеабходи «омство с мощными структурами теори» чисел н современ гебры. Такие структуры, как множество целых чисел, мнсгочленав и паля Галуа, играют важную роль в пос алгоритмов обработки дискрепшх сигналов. В настояще излагаются алгебраические сведения, которые иеобхоли дальнейшего, но, как правила, неизвестны студентам, сп зирующимся в облапн обработки дискретных сигналов С изучаются математические структурм групп, колеи н по.
увидим, что двскретное преобразование Фурье может быт делена в произвольном иоле, «отя наиболее известно его ление в поле комплексных чисел. Затем будут рассмотр вестные понятия матричной алгебры и нектарных прост Мы попашем, что их можно корректно определить для поля. Наконец, мы изучии кольна целых чисел и колька членов, уделяя особое внимание алгормтму Евклида и ки теореме об остапах. Понятие группы является математической абстраккией определенной алгебраической структуры, часто встречающейся ва многик конкретиык видах Введение абстрактного понятия обус.
ловлена тем, что легче одновременна последовать все математические системы с общей структурой, чем изучать каждую из них па отдельности. Определение 2.1.1. Группой 6 называется множество элементов с определенной на нен операиий (обозначаемой '), кото. рая удовлетноряет следукнпим четырем свойствам; (1) (Замкнутость.) Длп каждой пары элементов а и Ь из этого множества элемент с = а' Ь принадлежит этому нвожеству. (2) (Ашацишпизлость) Для всех элементов а, Ь и с кз этога множества а (Ьзс) = (а*Ь) *с. 24 Гл 2 В я ге мр уп гаеру 2 1 ГРуп Р , 2Л Пр тр о « а рт н (3) <Сущгопмогалие единицы ) В этом множестве элемент е, наз ываемый едииичямм элементом, такай что этом множестве существует а'е — — е а .— а для любога элемента а рассчатриваемого множества (4) (Обратимость.) Для любого а оз данного множества со Ь вЂ” Ь а=-е.
Если С со е жи мэигчяой г гплой н . д р т конегаое число элементов, то она н азывается рг Число элементов в конечной группе О ется ее порядком Н а нс, 2 1 р называРнс, 1 прнвелек пример койечвой группы сб о существу здесь п едстав р лева одна и та же группа. во в Разных означенная В сл чае п той же структу ой, хот у когда две группы описываются одной ваются изоморфными ') РУ 'Р, я и а Разных обозначенвях, они наз ы Некоторые г уппы об.
р Фладают тесз дополнительным свойствам, что лля любых а и Ь иэ такой группы а Ь= Ь а Это свойство называется коммутатжисслггю. Г ппы, обла *тим дополнительным свай гю, руппы, о падающие м сво ством, называются коммуттпиеямми груп ами, или беггомми гррппали. Ь1ы все~да б ем 1'дем иметь дело В сл чае абелев .у . ых групп знак групповой операции обоеначаетса плюсом и взвыв вается сложением (Лаже тогда, когда операция не является обычным эрифчетнческнм слож н ).
В елнннчный элемент е наз женпем), этом случае ратный к а элемент записывается в виде — а, так что а -: — ( — а) = ( — а) г- а =- О. называется множен Иногда символ групповой операции обозначатес теса точкой и у жением (даже тогда, когда оно не является обыч- ным умножением) В этом случае елнничный элемент называется единицей и обозначается 1, а обратный к а элемент записывается в виде а ', так что па'=- а' а= Теормеа 2.1.2.
Едииичямй гг мент г каждой ~руопе гдиястген. Для каждого гггмеята группы обротпмй элемент также гдияспмеп, и (а ') ' =- а. Доказательмпю. Предположим, что е и е' являютсн единичными элементами. Тогда е = е * е' = е'. Далее предположим, что Ь и Ь' являются элементами, обратными к а; тогда Ь=Ь*( Ь')=<(м1 Ь'==Ь' Наконеи. а ' а = ага ' = е, так что а является обратным к а '. Но в силу единственности обратного элемента (а ') ' =. а Г) Многие общевзвестные группы содержат бесконечное число элементов, Примера н аляются' множество пслык поел с операдией сложения; множества положительных рацнональнмх чисел с операцией умножения '); множество вещественных (2х2)- матриц с операций слаженвя Многие другие групвы содержат только «онечиое число элементов Конечные группы могут быть устроены весьма хитро. Если групповая операция применяется два или более раз к одному н тому же элемеяту, то можно использовать степенное обозначение Таким образам, а' †.
ага н о"=а а' ... *а где справа стоят й копий элемента а Ция.ганской нааывается группа, в которой каждый элемент может быть записан в виде степени некоторого фиксированного элемента, назынаемаго образргогцгй группы Каждая конечная циклическая группа имеет внд О = (ае, ац ай, ог-'), тле б — порядок С, а — образующая, а о' — единичный элемент, а обратный к а' элемент равен а' — '.
Чтобы можно было на свмом деле задать группу таким способом, необкпдимо, чтобы выполнялось равенство а' = а'. Зтп вытекает нз того, что в противном случае, если а' = а' при ! чь О, то аг ' = а' †' и в противоречие с опрелелением мы получаем меньше, чем б. элементов. )Эзт ре р г гхб«в жьол, чтбн л*г прг рм.яг ж дг мр, аготогя .
В с у ротаог ещ б. а ру о груп о е. 2 зе Гл.з.п а«е ратуиаыору ЗЛ. Грг Важнейшей циклической группой с й злементами является группа. обозначаемая 2ДЗ), или иногда ха и задаваемая мнажествои гЛд) = (О. 1, 2,..., й — П со сложением по модулю 4 в'качестве групровой операции. Например. х((б) —. (О. 1, 2,..., 5( н 3 .«- 4 = 1 . Гр у и ив 7 Дй) может быть выбрана в качестве стандартного прототипа циклической группы с й элементами . Н а самом деле имеется толька одна группа с й алене игами; все остальные являются ее изоморфными копиями, различающимися обозначениями, на не структурой . Любую другую циклическую группу С с 4 элемент вин можно отобрав ать в 2((я) с заменой групповой а не р анини в С слож е н ие м по модулю й Любые свойства структуры в 6 справедливы н хйу), и наоборот По задан ны м двум г р у плач 6 и 6" маж на построить новую группу 6, нагорая пазы в ветс в произведениям г р у и 6 ' Г" Н- з н ач аег с я 6 = С ' х 6" Элема итачи С служат пары зле ментов (а', а '), первый из катары х принадлежит 6 , а второй — 6' Г р у п новаяя а пер а ц и я в произведении групп 6 о предела ется равенством (а', а') (ЬТ Ь") =(а'*ЬЧ а' Ь") В атон формуле звездочка используе~ся три раза а трех разных смыслах В левой части равенства она обозначает групповую операцию в 6, а в правой части †операц в группах 6' н 6' сиггветственна.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
