Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 40
Текст из файла (страница 40)
иов по нодулю х' 1, каждое иэ которых требует грех умноже. ний; зто дает алгоритм, содержащий девять умножений. Аналогично, вычисление произведения по модулю»н -1- 1 маятно свести к вычислению семи произведений мкогочленов по модулю га -1- 1, что приведет к алгоритму с полным числом умвожевий, рав. ным 63 или 49 в аависимосги ст выбора алгоритма вычисления произведения мнагочленов па модулю х' -)- 1. Характеристики описанного итеративного алгоритма в зависимости ст выбора составляющих подалгорнтмов приведены на рнс. 7 7 Варианты определяются способом разложения длины л на множители л' и лЧ и можно разложить далее Все они выписаны в последнем столбце таблицы.
24З М 93 2 2 В ИУ В р чедуру иод*я+ 1 15 2. 4 (2 2) Рж. 7Д. Хчр ир Р РИ 999 В СР И сшВиив во 3 слупи *" Р(. нню с необкоднмым их числом] вычксленню произведения много. членов. Г)дивно твквя форма Влгорвтмв позвалнет прн больших л' получить преимущества в числе предслаженнй н постсложений, если всспользоввться БПФ.влгорнтмам Кули †Тью по осно. ввнвю 2. Здесь мм уже продвинулнсь в нсследовзннях столь глу. боко, что подошли к новому методу. известному лод нвзвеннеы полнномнвльного преобрвзовзния. Зтому методу посеян)енв остен. швяля часть данной главы.
Мы прервем нить нзложения, кшорай следовали до снх пор, твк квк полнномнвльное преабрвзаввние должно быть введено более фундвментвльным образам. Т.Б. Полнпомиальное представление расвнпреппй полей Наиболее часто применяемое двскретяое преобрвзавзние Фурье длнны л отображает вектор с вещественными компонентвмн в вектор с «омпленсными компонентами. В првктнческих задачах обработки дискретных сигналов векторы с произвольными веще. ственнымн значениями компонент никогда не нужны; нсегдв окв.
зыввется достаточным огрвнячнть рассмотрение рвпионвльными числами, иля, даже еше проще, пелымн. В данном разделе область определенна преобразования Фурье ограничена множеством рзпнонвльных чнсел. Зго ограничение не снижает првктяческой пенности зло)ритмов, но пр» зтом оно пряводнт к совершенно другому взгляду нв характер вмчнслений Преобрввоввние Фурье длнны л отабрзжвет вентер длины л с рвпноввльными компанентвмн в вектор длины л, компоненты 242 Ги 7. В тр 9 В гсрюмн и мзсм р ме р ВВисд В проц дур д " е 1 Рнс. 7.б. Пр «ш и Взьквя Ви В хт рати Ваш ВЛ ср Несколько вндоивмененнвя версия алгоритма получается, если выбрать ' — 3 ш (к) = П (х — г') (х + г') —.— )-9 2 ' †) — П (х — «') (шобр'+ 1). Теперь степень основного модуяя ш (х) равна 2л", хотя достз.
точной является степень 2л — 1 Следовательно, такой выбор многочленв )я (х) прнводнт к одному дополнительному (по срввне. ) 9 ! * 2 2 + 1 53 И )29 м 3)5 )ИЗ *" )ВИ ПВС) 255)5 5)435 П9 39 )593 ) 559 4553 )ВЗН 2ИП 5ВВИ МЗВ ) ЗВИЕ (2 П 29 (2 4) В О О 22 В (2 9) 9 (го гв )9 ( (2 29 )5 И (2 О 2)В )г (4 о и тп В (9 о и гв) м (9 о (г ги 244 Г . т. Б тэ е алтаре и и»огамерз 4 с р т.а. Вшя з се р э аз* рзсиэр из и з которого принадлежат некоторому подмножеству комплексных чисел, на самом деле счетному подмножеству. Обычно в исслело. ваннах преобразовании Фурье в качестве значений компонент выходного вектора допуснаются произвольные «амплексные числа, которые з практических вычислениях ограничиваются «анечным множеством путем финсации разрялнасти допустимых чисел. Зто можва сделать до некоторой степени произвольно; условность представления проявляется в выборе необходиьгой длины слова с учетам допустимой погрешности оируглениа.
Даже тогда, когда областью определения преобразования Фурье валяется множество целых чисел, для точного вычисления преобразования необхо . димо, чтобы разрядность двоичного представления числа была бескоаечнай. В настоящем разлеле рассматривается другой подход к зада. нию областей определения и значения преобразования Фурье. Он сосшит в полииомиальном описании расширений полей рациональных или камплекснык ~исел. Пусть ч представляет собой вектор длины л с рациональными иомпонентами и пусть м = 4 †""'".
Тогда задаваемый преобраза. ванием Фурье нектар — ! 1'„= ~ мыа„2 =0,..., и — 1, г=э имеет комплексные компоненты. Тем пе менее произвольное «омплексное число ие может быть результатом преобразования. Все возможные в результате вычисления преобразованяя Фурье номпаненты принадлежат подпалю (,(ь), или, в более простых або.
значениях, подпалю С,'", которое представляет собой казмеиьшее содержашее м подполе поля камплексаых чисел Зго подполе салержит поле рациональных чисел, поскольку любое подполе поля камвлексных чисел содержит все рациональные числа. Пусть над полем рациональнмк чисел разложение мнагочленз х" — 1 на простые множители дается равенствам х' — 1: — Р, (х) Р, (х) .. Р, (х). Простые делители являются круговыми много женами, и для малых л их ком)фицненты раним — 1, б, 1. Так как элемент м як ляется корнем многачлеиа х — 1, та он лалжен быть караем одного из круговых многачлегюв, скажем, корнем мпошчлена р (х) шепенп и со старшим каир(ицгиептам, равиыи единице: р(х)=х фр„гх--'г .-!-рзх+24.
Так как р (ы) =- О, та ы" = — р м" — ' . - ... — р м — рь Следовательно, м" может быть выражен в виде линейной комби. нации мемьших степеней элемента ю. Для меньших степеней элемента м такое представление иевоаможна, так «ак в прогна. ном случае м был бы корнем многочлена степени меньше, чем степень многачлена р (х). Поле О может быть задано как ьноже тво всех ьиогочлеиов от м с рациовальаыми коэффициентами степеней, пе превосходящих ю — 1.
Операпией сложения в ганом представлении поля является сложение миагачленав, а операцией умиожеивя — умнг жение миогочленав ао модулю многачлена р (м). Много«лены задаются списком своих и коэффициентов Такой способ задания этемеиюв поля О" требует ш слов памяти вместо двух, необхо. димых для запоминания компзекснога числа. с(тобы подчерниуть, что сами числа задаются многачленами, а не их «омплексиым» значениями в точке а, будем в записи чисел пользоваться символом х вместо м.
Тогда числа поля равны а =.а,х '+а х — '+ ... — оН+а, и даются списком коэффициентов аь Конечно, если мы пожелзем узнать истинное» комплексное значение числа о, та надо вместо х в мнагочленнае выражение дла о подставить м н произвести сост. ветствуюшие этому многочлену вычисления Однако наша дель состоит в разрзботие алгоритмов, внутренние переменные катарьы имеют палиномиальнае представление, и в некоторых отношенилх такая форма действитеаьна привалит « более простым алгоритмам Например, если л равно степени двух, то (х" — !) -- (хм+ Ц(хл-1-1)...
(х-!-1)(х — 1). Круговой мпагочлен х"гз -)- 1 приводит к рзсюиренню пола („ все элементы ноторого цредставлакп собой многочлеиы с рациональными коаффициентами степени меньше, чем л(2 Сггажеггнеьг в и ле является сложение мвагочлеаоа, а умножением умно. жеане миогачлеиов по модулю х"а -1- 1. Например, поле Оэ состоит из всех миогачленов с рацианаль. аыми коэффициентами степени ие более семи с арифметикой, выполняемой по модулю многачлеиа х'.(- 1. Пример умножения в поле дается равенством (»т — — х' -1- — ) (х' — 1) =- х' — хг— 1 ! 4) з ! ! з — — — — — — х' — — х' и — х' — х — —.
2 4 4 2 4 4 Палиномиальное представление расширения палей относится не тольиа к полю рациональных чисел Вго можно нсаочьзавать и для расширений поля комплексных чисел Например, поле комплекс«ых ро«иоиозь«ых чисел — эта множество иамплексных чисел вида и = а -1- !Ь, где а и Ь вЂ” рациональные числа. Зто цадмважество являегсн подполем поля камплексимх чисел, каторое иногда обозначается через („(!). Во иногих приложеннях цифровой обработки сигналов компоненты обрабатываемых вен- 246 г.т.врце.ржэзеэ торов «вляются «омплексвымн.
Так как разрядность записи ком. плексных чисел првктнческн эсегда огра««чена, то по существу всегда рассматрнваютсн векторы с комплексными рацнанальнымн кампо«с«там« (нлн, даже более частный случай, с комплексными целымн кампонентамн). Поле комплексных ран«опальных чисел можно расшнрнть, присОединив корень е степени л нз единицы.
Эта лает наименьшее расшнренне С (е), в котором нмеется преобразование Фурье длины л. Если С (гэ) содержит 1 (т. е. содержнт корень иного. члена х' -1- 1), то такое расширение (; (е] содержит все «омплекс. ные рациональные числа. Это именно то расшнреане, которое нам нужно. Если «руганей многочлен равен х' -1- 1 для некого.
рога четнага числа г, то это всегла так. В противном случае эле. мент 1 вада прнсаедннять. Пусть я не равна степени двойкн, е обозначает корень степени и нз еднннцы, а р (х) обоэвачает круговой многочлен сте. пенн и, корнем которого е является, Тогда раси«репке („'((, б), нлн, в баяее простык обозначен«ах, С (1), нредставляет собой! множества многочленов с коэффициентами нз паля С (1), степенн' которых не превосходят и — 1. Спаженне в поле совпадает со ело.
женнем многочленов, а умножение — с умноженнем многачленоа по модулю р (х). Козффнцненты этих мнагочленав снлздмааэлоя н вычнтанлсн как «омплексные чнсла Для такога задан«я одного элемента пала С Цу е) требуется 2и рацнонзльаых чисел. С точностью да этого различия н более общнх правил слаженна н умножения казффнцаентов многочле. нав, все. что буде~ сказана в следующих разделах главы относя. тельна обработка последовательностей рациональных чвсел, справедлнва н для последовательностей «омплексных рацпональных чисел Таким образом, к |юлю «омплексных рацнавальвых чисел можно больше не возвращатьс«.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
