Исследование эхокомпенсатора и улучшение его характеристик в режиме одновременного разговора абонентов
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
е Фурье, то получится исходная последовательность {x}. Исходная последовательность состояла из действительных чисел, а последовательность {X} в общем случае комплексная. Теперь вернемся к формуле (7). Слева стоит действительное число xn, а справа - две суммы, одна из которых помножена на мнимую единицу j. Сами же суммы состоят из действительных слагаемых. Отсюда следует, что вторая сумма равна нулю, если исходная последовательность {x} была действительной. Отбросим ее и получим:
(9)
Поскольку при дискретизации мы брали tn = nT/N и xn = f(tn), то можем выполнить замену: n = tnN/T. Следовательно, в синусе и косинусе вместо 2?kn/N можно написать 2?ktn/T. В результате получим:
(10)
Сопоставим эту формулу с формулами (11) и (12) для гармоники:
x = A cos(2?t/T + ?) = A cos(2??t + ?) = A cos(?t + ?) (11) = Re cos(2?t/T) - Im sin(2?t / T) (12)
Мы видим, что сумма (9) представляет собой сумму из N гармонических колебаний разной частоты, фазы и амплитуды (13):
(13)
Далее будем функцию
Gk(t) = Ak cos(2?tk/T + ?k) (14)
называть k-й гармоникой.
Амплитуда, фаза, частота и период каждой из гармоник связаны с коэффициентами Xk формулами:
Итак, физический смысл дискретного преобразования Фурье состоит в том, чтобы представить некоторый дискретный сигнал в виде суммы гармоник. Параметры каждой гармоники вычисляются прямым преобразованием, а сумма гармоник - обратным.
Общий принцип БПФ
Одна из причин того, что анализ Фурье [7] играет такую важную роль в цифровой обработке сигналов, заключается в существовании эффективных алгоритмов дискретного преобразования Фурье. Вспомним, что дискретное преобразование Фурье (ДПФ) определяется выражением
( 15)
где. Обратное дискретное преобразование Фурье (ОДПФ) имеет вид
( 16)
В (15) и ( 16)как х(n), так X(k) могут быть комплексными. Выражения в (15) и (16)отличаются только знаком экспоненты от WN и скалярным коэффициентом 1/N. Поэтому рассуждения, касающиеся вычислительных процедур для (15), применимы с очевидными изменениями к (16).
Чтобы проиллюстрировать важность эффективных вычислительных алгоритмов, поучительно сначала рассмотреть непосредственное вычисление ДПФ. Так как х(n) может быть комплексным, то можно записать
Отсюда видно, что для каждого значения k при непосредственном вычислении X(k) требуется 4N умножений и (4N-2) сложений действительных чисел. Так как X(k) должно вычисляться для N различных значений k, непосредственное вычисление дискретного преобразования Фурье последовательности х(n) требует 4N2 умножений и N(4N-2) сложений действительных чисел или N2 умножений и N(N- 1) сложений комплексных чисел. Вдобавок к умножениям и сложениям при выполнении вычисления ДПФ на универсальных или специализированных цифровых вычислительных . машинах требуются, конечно, средства для хранения значений последовательности х(n) и коэффициентови средства обращения к памяти. Так как количество запоминаний и обращений к памяти в вычислительных алгоритмах обычно пропорционально числу арифметических операций, то оно считается разумной мерой сложности вычислительного алгоритма или времени, необходимого для вычислений. Таким образом, приемлемой мерой эффективности непосредственного вычисления дискретного преобразования Фурье является тот факт, что оно требует 4N2 умножений и N (4N-2) сложений действительных чисел. Так как количество вычислений, а следовательно, и время вычислений приблизительно-пропорциональны N/2, то ясно, что при прямом методе необходимое число арифметических операций становится очень большим при больших значениях N. По этой причине представляют значительный интерес вычислительные процедуры, уменьшающие количество умножений и сложений.
Большинство подходов к улучшению эффективности вычисления ДПФ использует следующие свойства величин
) =()* (18)
) == (19)
Например, используя первое свойство, т. е. свойство симметрии функции cos и sin, можно сгруппировать слагаемые в ( 17)следующим образом:
(20)
(21)
Аналогичную группировку можно произвести для других слагаемых в ( 17). Посредством этого метода число умножений можно сократить приблизительно вдвое. Можно также использовать тот факт, что для определенных значений произведения kn функции sin и cos принимают значения 1 или 0, при которых не требуется умножение. Однако при сокращениях такого типа количеств вычислений все еще остается приблизительно пропорциональным N2. К счастью, второе свойство, т. е. периодичность комплексной последовательности, позволяет достигнуть существенно большего сокращения количества вычислений.
Вычислительные алгоритмы, использующие как симметрию, так и периодичность последовательности, были известны задолго до появления быстродействующих ЭВМ В то время приветствовалась любая схема, уменьшающая количество ручных вычислений даже в 2 раза. Рунге (Runge) , а позже Даниэльсон (Danielson) и Лапцош (Lanczos) описали алгоритмы, при которых количество вычислений было приблизительно пропорционально N Log N, а не N2. Однако это различие не было слишком: важным для тех малых значений N, которые можно было осуществить при ручных вычислениях. В 1965 г. Кули (Cooley) и Тьюки (Tukey) опубликовали алгоритм вычисления дискретного преобразования Фурье, применимый при составном N, т. е. когда N является произведением двух или большего числа целых чисел. Опубликование этой статьи вызвало значительный интерес к дискретному преобразованию Фурье при обработке сигналов