Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 32
Текст из файла (страница 32)
Иногда электронные компоненты для вычислений в некотором пале доступнее, шм для задиннога поля, и тогда, если требуемые вычисления дапускакп подходящую нереформулировку, резоннее, перейти а зта поле Возможны ситуации, когда желательно раз- . работать стандартный вычислительный молуль обработки баль. ших массивов данных и использовать ега при решении разносб. разных задач для абработии дискретных сигналов.
Подгонка одного типа вычислений к другому мажет осуществляться тогда с целью ' стандартизации. Другой важной причиной использования суррогатных полей является улучшение точности вычислений. Вычисления в полях Галуа не солержат погрешностей округления и поэтому всегда точны. Если задачу вычисления в поле вещественных или комп. лексных чисел удастся погрузить в поле Галуа, та это может прн. вести к увеличению точности результата.
В большинстне задач обработки дискретных сигналов можно ограничиться нычиспе-' ниями с фиксированной запятой; обычно оказывается достаточной )б.битовая арифметика с фиксированной запятой. Если поле Галуа достаточно велика, чтобы содержать 16.битоные целые числа, та в ега пределах можно правильна осуществлять многие' целочисленные операции, если только результаты не выходят. эа пределы (б.битовых целых чисел. 6.1. Свертка в суррогатных полях Свертка в пале вещественных чисел часто может быть эам иена сверткой в подходящем поле Галуа. В реальных задача нещественные числа записываются в виде кшгечного числа сятичных или дноичных знаков; в цифровой обработке сигнал сщ свср а э сурршпвиз ншех обычна используется запись с фиксированной запятой.
Дваичаае предстазэеггне с конечным числом знаков может ограничиваться 12 или 16 битами. При вычислениях можно предполагать, по двоичная тачка находится справа — все числа являются целыми. Сдвиг двоичной точки во входных данных с целью валю. челна остальных случаев является пчень простым делом. Итан, линейную свертку э (х) = 6 (х) 6 (х] в поле вещественных чисел мы замевяем сверткой в кольце целых чисел.
Дч» зтога нужно то тько входные данные интерпретировать как целые числа Внешний взд уравнения, апнсывагощего свертку, не меняется, на операции приобретают смысл стандартной цела. численной арифметики. Затем уравнение в кальке целых чисел можно погрушть н аодходищее иоле Галуа, скажем, простое поле Галуа, СР (р), есчи простое числа р достаточно велико. Если все входящие в свертку целые числа иоложитсльны, то задающее про.
стае поле бр (р) простое число р должна быть столь гюльшим, чтосы выходные коэффициенты свертки нс превасходилн р — 1. Тогда выаолаяегся сраввеиие з (х)'=- 6 (з) б (х) (шаб р), и условие вычислений по модулю р излишне. Если з, могут при. нимать и отрицательные значения, то задающее простое поле ВР (р) простое число р нада выбирать так, чтобы э, попадали н 1гиапазан — (р — 1)(2 ъ з, < (р — 1)(2. Тогда отрицательные истые числа могут быть представлены положительвыыи целыми числами в интервале от (р 1))2 до р — 1. Свертка в поле Галуа.
может быль вычислена любым из пригодяыт в данном ноле лсгодан. Некоторые прямые методы рас. смэтриваются в следующем разделе Можно также васпальвс ааться преобразованием Фурье н данном поле и теоремой о свертке. На рис. 6.1 приводится сравнение такого вычисления в пале Га. зуа и в поле комплексных чисел. Мы видим, па на обеих сторонах рисунка выписаны одинаковые уравненнн, хати, конечно, заложенные в них арифметики различны.
Так как пнклическан свертка в иоле Галуа приводит к тому же сачаку ответу, что и ииклическая свертка в кельне целых чисел, то использование преабразанания Фурье даннога поля Галуа также приводит н правильному атщпу. Так кан арифмети. «ои паля бР (р) является арифметика по модулю р, то перепал. веаня по модулю р в прамежупзчных вычислениях роли не играют, 1ю ногут оказаться существенными в выходных вычаслениях; если р выбрзно достаточно большим, то переполнения в выходных ааеных невозможны. Б э г Р в.!. Озер» В урр тввх П ГАХ »С! о(о»ы г ~ г г гщ гз. ь. и «х э «Увгщзт з пюзз !!=с!!и! д л чв» ггг; и и гюгг »с» »»лпщ жв) УЩ) Рп. б.г, Ор» х У* Р п кур в Ртхз. В качестве примера рассмотрим вычисление 5.точечной никли.
ческой свертки, з (к) = 8 (х) д (х) (пюб х' — 1). Выберем простое р раввыьг 31 и будем работать в поле 6Р (3!). Зго пале полходит к рассматриваемой зада!е постольку, поскольку иам известно, что «оэффипиеиты свертки э(х) нс превосходят 30. Для реально возникающих задач поле 68 (31) слишиом мала и мы его аыбрвлп тольао яля примера Твк как 5 делят р -- 1 =- 30, то в данном поле существует преобразование Фурье длины 5. Ядром преобразования можно выбрать элемент 2, так как его порядок равен 5. Пусть бг —— 2, бт .= б, бз = 4, бз =.
4, б, = О, д, = 3, дг =- Оо8, = 2, щ = 1, щ = 2. 5.точечное преобразование вектора б задается равенствами ()э=Ей оо й =О,..о 4; !=э лля вектора й имеют место аналогичные соотношения. В матрич. ной записи соответственно имеем Таким образом, кошювегщм вектороппргобрззовэнвй даются равевстввми 6»=18,(УУ.=О, 6»=5, Р,=29,6»=22, 6»=8, 6„=-20, 6,.=22, 6» —.
О, 6, =.27. Перемножая 6, и 6!, для 3» получаем. 8,=4,3»=0,3,=-17,3» -0,3»=5. Тзк как 5 25.: 1 в поле 6Г (3!), то 5 ' = 25. Следовательно, обратное преобразование Фурье задается рввеиствоы очреяеляющии окаичательаый реэулюат. Непосредственное вы»вглсиие этой свертки в колько ггелых чисел Лает тот же резул~тат. Если мы выберем большие входные компоненты, то некоторые «омгоиеиты свертки окажутся больше 30. В этом случае вычнслени ° з;ртки в 68 (31) проведет к переполневпю выходных иомпонент в лает неправильный результат.
Тогда нужно использовать большее пале; в практических приложениях полезны поля, сохсржагцве по меньшей мере 2ы элементов. Если клива слова слашком велика для поля желаемой мощно. сгн, то можно носпользопаться китайской теоремой аб остатках и работать с вы мтзми целых чисел, разбивая таким образом длинные слом на кораткве похслова Эго использование китайской тео.
г' ремы ой остагиах отличаегся от ее предыдущего вюользования при построеняи переунорядочнвания линейною потока данных в таплнцт Теперь она используется только для разбиения самих чисел, не затрагивая индексацию данных данные следуют в своем естественном порядке Новые свергни, конечно,ыожна вычислять, аспольэуя опять китайскую теорему оо остаткак, по на сей раз, в отличке от предыду~цего, ова пувет аспользоваться для вновь сформярованнмх шгогочленов н их индексов ПУсть Яггг! обозначает вычет зг (шай шг) дла г взаимно пРостых целых чисел тм тт,, т,.
Тогда я — ! з=о, ..., 6+Дг — 1, = К 6)"ьй)ьо (спой тг), ь.э тле йг ! = д~ (шой ж,) и 6) ~ = Ф (шо4 юг). По китайской теореме ой остатках вели зины я, восстанавлииаются по вы'мгам я! '. !и Следовательно, вычисление свертки, солержащей Оодьшне це- лые числа, мм свели к вычисчению г сверток, содержащих малые целые иола. Дл .
енн э их состэ . щих сверток мозхно поэьзоэаться уже описанными способами илн оыстрымн алгорнт- мами вычисления сверток в кольце целых чисел. 6.2. Числовые преобразования Ферма Простейший вид алгоритмы вычисления преобразования Фурье имеют в полях Галуа вида СЕ (2 — 1), которые действительна являются попами, если р — — 2 -(- 1 — простое число. Известна, что число 2" + 1 не явлаехся простым, если ш не равно степени двух. Одвака обратное утверждение неверно, так как число 2м щ 1 является составным Но прн ш = 2, 4, 6 и 16 число 2 -4- 1 является простым, равным соответственно 5, 17, 257 и 66 537.
Это множества целык чисел известно под назвавием простых чисел Ферма. Если д — простое число Ферыа, то в поле СЕ (д) число д — 1 и люоой его делитель равны некоторой степени двойки. Преобразование Фурье г Рь =-. ~; ммоь й =- О,, и — 1, г-э определена, если л делит 2 и существует элемент м порядка и'). Таким о5разом, в поле СЕ (2ы 4 1) определены преобразования Фурье длин 2", 2ой 2м, ..., 2', 2. Используя алгоритм Купив Тычки, ~зреойраэоэание Фурье в поле СЕ (2 -1 1) можно пред- 197 ставить в виде гюследавательносгн преобразований по основавию дза для реалнэапин которой требуется всего лишь примерно (г62) 1ой, л умножений и (пг2) 1ой, а сложений Преобразование данны 32 и меньше в пояс ОЕ(2ы. 1) делаются на самоьг деле ванного пропю. Это пйусловлено тон, *по порядок элеыента 2 в этом поле ранен 32 Чтосы уэ«деть это, достаточна заметить, что 2м ч- 1 = О в поле СЕ (2м — П.
Следовательно, 2м =. — 1 и 2м .— ! Преобразование Фурье записывается в виде з1 !'„. 7' 2' о„й = О... 31, г-.э и умаожение е данной арифтгетн ~есной снстеьте сводится просто к цнкли"ескгму сдвигу. так как представляет собой умножение на степенк двойки Такое преобразование вычисляется чрезвычайно просто, но длшы 32 слишком мэлэ для многих приложений В общем случае простого числа Ферма 2 -," 1 порядок элеи:нта 2 в по.г«СЕ (2" -! П равен 2ж, так по 2 может бать исполшаваио в качестве ядра пргойрыоианяя дл»ы 2 ЕСя исз роения преойразоаания Фурье длины 4ш можно воспользоваться ядром гг2, В тих полях.
ка легко проверить возведением а квадрат и использованием соотношения 2 = — 1, выпалннотся равевстоо 1' 2 — 2ю'(2"дт — 1) Поэтому каждая степень элемента г 2 имеет вид 2' ~ 25 Например, преооразоиание Фурье длины 64 в поле СЕ (2м - 1) записывается в энде ез !'„=. Ч' (2ы — 2з)гь ог, й - О..., 63. —.э Есля для этого вычисления аасгюльюваться ВПФ-алгорптмом Кули — Тычки по основанию лна, то все умножения на константы будут умножениями на числа из да 2* ж 2' и, гледовательно, :огут быть реализованы как пара цнклическвх сдвшав и вычитаие В общем случае поля СЕ (2' П преобразование Фурье алины большей чем 2" вседа содержит нетрианахьвые учноже1гг~я.
Число этих умножений можно уьгеньппгть сведением ЬПФ- алгоритма Куля — Тьюкп в форму многочернога преайразоэанвя, а каждом нз измереннй которо~о используется не более чем 2т. то ечиос преобразование. Напрямер. рассмотрим 1024-точечаое преобразование в поле СЕ (2м -1 П: з где * — элемент порядка 1024, который можно полагать разаым пн, где я — примитивный элемент полн. Элемент 3 в поле 19а Гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
