Дискретный ряд Фурье

Рассмотрим периодическую последовательность с периодом N, т. е. такую, что

(1.94)

где r – любое целое число.

Как и непрерывные периодические сигналы, такие последовательности можно представить рядом Фурье, состоящим из сумм комплексных экспотенциальных последовательностей, т. е. экспонент, частоты которых кратны основной частоте (2/ N):

(1.95)

где k – целое число.

При этом выражение

(1.96)

называют дискретным рядом Фурье (ДРФ).

Как видно, в отличие от непрерывных периодических сигналов, для представления которых в виде ряда Фурье требуется бесконечно много комплексных экспонент, в ряде Фурье для N -периодического дискретного сигнала участвует только N таких последовательностей. Это является следствием того, что комплексные экспоненты из равенства (1.95) удовлетворяют тождествам: и т. д., поскольку для любых целых чисел k и n имеют место равенства:

(1.97)

Множитель 1/ N введен для удобства и не влияет на характер представления.

Чтобы найти коэффициенты ряда Фурье последовательности воспользуемся попарной ортогональностью комплексных экспонент. Для этого умножим обе части равенства (1.96) на и просуммируем результат по n от 0 до N – 1. Получим

(1.98)

Учитывая далее ортогональность комплексных экспонент, которая означает, что

(1.99)

Выражение (1.98) можно представить в виде:

(1.100)

Отсюда следует, что коэффициент ряда (1.96) получаются из последовательности по следующей формуле

(1.101)

Следует отметить, что последовательность также периодической с периодом N, так как для любого целого k имеет место следующее:

(1.102)

Коэффициенты удобнее рассматривать как бесконечную периодическую последовательность, отсчеты которой определяются формулой (1.101), так как в этом случае сохраняется дуальность между временным и частотным представлением периодических последовательностей рядом Фурье формулы (1.96) и (1.010) составляют пару анализа-синтеза и называются представлением периодической последовательности в виде ДРФ.

Для удобства введем обозначение

(1.103)

Тогда пара выражений, определяющая ДРФ, принимает следующий вид:

(1.104)

12. Свойства дискретных рядов Фурье. Периодическая свертка двух последовательностей.

Дискретные ряды Фурье, как и ряды Фурье, преобразования Фурье и Лапласа непрерывных сигналов и z -преобразование дискретных апериодических последовательностей, обладают целым рядом важных свойств, которые позволяют успешно применять их при обработке сигналов. Многие из основных свойств ДРФ аналогичны свойствам преобразования Фурье и z -преобразования. Однако ввиду периодичности последовательностей и здесь имеются и свои важные отличия. Более того, между временной частотной областями в ДРФ существует четкая действительность, в то время как ее нет ни в преобразовании Фурье, ни в z -преобразовании последовательностей.

1. Линейность. Если две периодические последовательности и с периодом, равным N, имеют коэффициенты ДРФ и соответственно, то для последовательности

коэффициенты ДРФ определяются как

(1.105)

где все последовательности периодичны с периодом N.

2. Сдвиг последовательности. Если периодическая последовательность имеет коэффициенты дискретного ряда Фурье то сдвинутая по­следовательность имеет коэффициенты

Вследствие того, что коэффициенты ряда Фурье периодической последовательности представляют также периодическую последовательность, то аналогичный результат справедлив и для сдвига коэффициентов Фурье. В этом случае значения периодической последовательности являются коэффициентами ряда Фурье последовательности где l – целое число.

3. Двойственность. Формулы (1.104) свидетельствует о том, что анализ и синтез ДРФ отличаются друг от друга только множителем 1/ N и знаком экспоненты W_N. Более того, исходная последовательность и коэффициенты ее ДРФ представляют собой один и тот же тип последовательностей – периодический. В этом случае с учетом множителя 1/ N и знаков экспонент в (1.104) можно получить, что

(1.106)

или, меняя местами k и n,

(1.107)

Легко видеть, что равенство (1.107) очень похоже на формулу для Другими словами, – это коэффициенты ДРФ периодической последовательности Другими словами, чтобы найти коэффициенты ДРФ последовательности необходимо обратить порядок исходной последовательности и умножив все ее члены на N.

Более кратко свойства двойственности формулируются следующим образом: если последовательность имеет коэффициенты дискретно­го ряда Фуье то последовательность имеет коэффициенты ДРФ, равные

4. Симметричность. Симметрии ДРФ, как и симметрии преобразования Фурье, часто упрощают решение конкретных задач. Однако преж­де чем обсуждать это важное свойство приведем некоторые определения.

Сопряженно-симметричной последовательностью называется после­довательность, для которой а сопряженно-кососимметри­ческой последовательность, удовлетворяющая условиям где символ * обозначает комплексное сопряжение. Любую последовательность можно представить в виде суммы сопряженно-симметричной и сопряженно-кососимметричной последовательностей:

(1.108)

где

(1.109)

(1.110)

Вещественнозначную сопряженно-симметричную последовательность, для которой называют четной, а вещественнозначную сопряженно-кососимметричную – нечетной.

Таким образом, если у комплексной последовательности коэффи­циенты ДРФ равны , то у последовательности эти коэффи­циенты будут равны , а для последовательности – Следствием этого является то, что коэффициенты ДРФ для Re[ x (n)] есть а ДРФ –

Для действительной (вещественной) последовательности свойство симметрии следующие:

(1.111)

Кроме того, для последовательности коэффициенты ДРФ равны а для последовательности –

5. Периодическая свёртка. Пусть и две периодические последовательности периода N с коэффициентами ДРФ и соответственно. Тогда последовательность будет являться коэффициентами ДРФ последовательности , получаемой путём объединения последовательностей и следующим образом:

(1.112)

Видно, что последовательности и объединяются способом, похожим на свёртку. Однако в отличие от свёртки апериодических последовательностей последовательности и входящие в данное выражение, периодичны по m с периодом N и, следовательно, периодичны их произведения. Суммирование производится только по одному периоду. Этот тип свёртки называется периодической свёрткой. Изменяя индекс суммирования, можно получить, что

(1.113)

Пример 1.10. Вычислим периодическую свертку двух последовательностей и с периодом N = 4:

={3,2,1,0}; = {2,2,1,1}.

Рис. 1.18 иллюстрирует процедуру вычисления периодической свертки.

Последовательность которая является «фиксированной» представлена на рис. 1.18а, а сдвигаемая или «скользящая» последовательность – на рис. 1.18

б. Зеркально отображенная последовательность или представлена на рис. 1.18 в, а результат ее последовательного сдвига – на рисунках 1.18 г – ж.

 

Рис. 1.18. Вычисление периодической свертки

Рассмотрим вычисление свертки на одном периоде: первый отсчет вычисляется как сумма произведений последовательностей и второй отсчет – как сумма произведе­ний последовательностей и и далее, аналогично: – последовательностей и – и

Следующий отсчет должен вычисляться как произведение после­довательностей и Однако, в силу периодичности последовательности и на интервале [0; N –1] ® [0;3] оказываются одинаковыми и поэтому результаты вычислений будут повторяться с периодом N = 4.

При этом типе свертки, как видно из рисунка 1.18, когда один период последовательности выходит из интервала суммирования, следующий период входит в него.

Результаты вычислений свертки для данного примера приведены в таблице 1.5.

Вычисление периодической свертки

 

N

Рис. 1.19. Результат вычисления периодической свертки

Если поменять местами время и частоту (теорема двойственности), то можно получить аналогичные результаты и для коэффициентов дискретного ряда Фурье. Это значит, что периодическая последовательность имеет коэффициенты ДРФ, определяемые выражением:

(1.112)

и с точностью до коэффициента равные периодической свёртке последовательностей и

13. Дискретное преобразование Фурье. Основные свойства.

Последовательность конечной длины N представляется периодической последовательностью периода N, один период которой совпадает с исходной. Следовательно, заданная последовательность будет иметь такое же представление по Фурье, что и периодическая.

Итак, рассмотрим последовательность конечной длины N, для которой всюду, за исключением интервала Соответствующая периодическая последовательность периода N, одним периодом которой является будет определяться следующим образом:

(1.113)

Так как имеет конечную длину N, то отсутствует перекрытие между членами для различных значений r. Поэтому данное выражение можно представить в виде

(1.114)

Как известно, выражение означает, что n представляет собой число, которое после многократного деления на N дает остаток a. Например или где k – целое число.

Последовательность конечной длины получается из выделением одного периода, т. е.

(1.115)

Для удобства введём прямоугольную последовательность

(1.116)

При такой записи будем иметь

(1.117)

Так как коэффициенты дискретного ряда Фурье периодической последовательности также являются периодической последовательностью периода N, то аналогичное представление используются и для них

(1.118)

Для периодических последовательностей и как известно справедливы соотношения:

(1.119)

Так как суммирование в этих выражениях распространяется только на интервал от 0 до N – 1, то из последних трёх равенств (1.117), (1.118) и (1.119) следует, что

формула анализа (1.120)

формула синтеза (1.121)

Эта пара выражений и есть дискретное преобразование Фурье (ДПФ), причём, первое из них называется прямым (формула анализа), а второе – обратным (формула синтеза).

Следует отметить, что различие между последовательностью конечной длины N и периодической последовательностью периода N невелико в том смысле, что обе они определяются только N значениями и поэтому различия между их Фурье-представлениями также невелики.

1.4.2.1. Свойства ДПФ. 1. Линейность. Если две последовательности конечной длины и линейно складываются так, что

то ДПФ этой последовательности будет определяться следующим образом:

(1.122)

где и – ДПФ последовательностей и соответственно.

Ясно, что если N ₁ – число ненулевых отсчетов последовательности x ₁(n), а– длина последовательности x ₂(n), то длина их линейной комбинации будет равна Следовательно, формула (1.122) будет корректна в том случае, когда оба ДПФ в ее правой части вычисляется с одним и тем же параметром Если, например, то при вычислении ДПФ последовательность x ₁(n) должна дополняться нулями до формальной длины N ₂.

2. Круговой сдвиг последовательности. Пусть у нас имеется последовательность конечной длины ДПФ которой

В качестве примера возьмём последовательность следующего вида (рис. 1.20 а). Ее периодический аналог будет выглядеть так, как на рис. 1.20 б, а сдвинутая последовательность при m=2 представлена на рис. 1.20 в.

Сдвинутая последовательность конечной длины, которую обозначим через может быть получена из последовательности выделением одного периода на интервале как показано на рис.1.20 г, т. е.

(1.123)

Рис. 1.20. Круговой сдвиг последовательности конечной длины

Из верхнего и нижнего рисунков видно, что не соответствует линейному сдвигу и в действительности обе последовательности со­средоточены на интервале от 0 до N – 1. Сдвиг, конечно, происходит, но не линейный. Из средних двух рисунков видно также, что при сдвиге периодической последовательности, как только одна из выборок выходит из интервала от 0 до N – 1, точно такая же выборка входит в интервал с другого конца. Поэтому можно представить себе формирование из таким образом, что как только выборка выходит из интервала от 0 до N – 1 с одного конца, она входит в него с другого.

Для трактовки такого сдвига представим, что последовательность конечной длины расположена на поверхности цилиндра в N точках. При движении по поверхности цилиндра наблюдаемая последовательность будет периодической При этом линейный сдвиг периодической последовательности соответствует вращению цилиндра. Такой сдвиг последовательностей обычно называют круговым (циклическим) сдвигом.

В общем случае круговой сдвиг можно выразить следующим образом:

(1.124)

и

(1.125)

Так как коэффициенты ДРФ периодических последовательностей и связаны соотношением:

(1.126)

то,

(1.127)

Другими словами, ДПФ последовательности конечной длины, сдвинутой на m отсчетов вправо (влево) соответствует умножению ДПФ исходной последовательности на

3. Двойственность. Поскольку ДПФ тесно связано с коэффициентами дискретного ряда Фурье, то естественно ожидать, что и ему присуще свойство двойственности. Действительно, из сравнения формулы анализа (1.120) и синтеза (1.121) следует, что они отличаются друг от друга только множителем 1/ N и знаком показателя экспоненты

Двойственность ДПФ можно получить на основе зависимости между ДПФ и ДРФ. Опуская достаточно простые рассуждения, свойство двойственности ДПФ можно сформулировать следующим образом: если последовательность конечной длины x (n) имее ДПФ X (k), то ДПФ последовательности X (n) будет равно Nx (– k mod N), Последовательность Nx (– k mod N) получается из Nx (k) обращением знаков у индексов по модулю N. Как и циклический сдвиг, это обращение лучше всего представлять исходя из подразумеваемой периодичности исходной последовательности.

4. Свойство симметрии. Если последовательность является дей­ствительной (вещественной), то её ДПФ являющееся комплексной величиной, удовлетворяет следующему условию:

(1.130)

Это значит, что ДПФ является сопряженно-симметрической относительно

Справедливы также выражения:

(1.131)

Как видно, модуль ДПФ является чётной функцией, а аргумент – нечётной.

Коэффициенты ДПФ с номерами от до могут рассматриваться как гармонические составляющие отрицательной частоты с номерами от до –1.

5. Круговая (циклическая)свёртка. Если последовательности и имеют дискретные преобразования Фурье и k = 0, 1, …, N – 1 соответственно, то последовательность заданная в виде их свёртки

(1.134)

будет иметь ДПФ заданное формулой

(1.135)

а последовательность

(1.136)

будет иметь ДПФ в виде свертки ДПФ исходных последовательностей

(1.137)

Этот вид свертки часто называют круговой, или циклической, сверткой.

14. Общая характеристика ряда и интеграла Фурье, дискретного ряда Фурье и дискретного преобразования Фурье. Равенство Парсеваля.

1.4.2.2. Равенство Парсеваля. Пусть имеются две последовательности конечной длины и ДПФ которых равны и соответственно. В этом случае последовательность можно представить в виде обратного дискретного преобразования Фурье:

(1.141)

Умножим правую и левую часть данного выражения на и найдём среднее значение полученного произведения:

(1.142)

Изменив порядок суммирования в правой части последней формулы, получим:

(1.143)

Так как

(1.144)

то будем иметь:

(1.145)

Если то и тогда

(1.146)

где – энергия сигнала, вычисленная по переменной n (во вре­менной области), с новой строки – энергия сигнала, вычисленная по переменной k (в частотной области).

Это и есть равенство (теорема) Парсеваля, устанавливающее связь меж­ду энергией последовательности и её преобразованием Фурье

15. Прямой метод вычисления ДПФ. Основные подходы к улучшению эффективности вычисления ДПФ.

Рассмотрим непосредственное вычисление прямого ДПФ

(1.147) где

Выражение для X (k) можно представить в виде следующей системы уравнений:

(1.148)

Видно, что для того, чтобы получить коэффициент X (0) необходимо выполнить N операций комплексного умножения и (N – 1) операцию ком­плексного сложения. Для получения X (1) требуется также N операций комплексного умножения и (N – 1) операций комплексного сложения.

Для того, чтобы вычислить два коэффициента X (0) и X (1) требуется 2 N операций комплексного умножения и 2(N – 1) операция комплексного сложения.

Продолжив наши рассуждения дальше, получим, что, если требуется определить все N коэффициентов X (0), X (1), …, X (N – 1), то необходимо выполнить N ² операций комплексного умножения и N (N – 1) операций комплексного сложения. Представив (1.147) в виде последовательности операций над вещественными числами, получим откуда следует, что на каждое умножение комплексных чисел требуется четыре умножения и два сложения вещественных чисел, а каждое сложение комплексных чисел получается за счет сложения двух вещественных. Таким образом, при прямом вычислении одного значения ДПФ необходимо выполнения 4 N вещественных умножений и (4 N – 2) вещественных сложений. Для полного вычисления N -точечного ДПФ общее число умножений вещественных чисел достигнет 4 N ², а сложений N (4 N – 2).

Вдобавок к умножению и сложению при вычислении ДПФ на универсальных или специализированных ЭВМ необходимо хранить N значений входной последовательности x (n), столько же комплексных экспонент и постоянно обращаться к ним в процессе вычислений. Так как количество запоминаний и обращений к памяти в вычислительных алго­ритмах обычно пропорционально числу арифметических операций, то это число считается разумной мерой сложности вычислительного алго­ритма или времени, необходимого для выполнения вычислений. По­скольку количество операций, а, следовательно, и время вычислений приблизительно пропорциональны N ², то при прямом методе вычисления ДПФ необходимое число арифметических операций становится весьма большим при больших значениях N.

16. Алгоритмы БПФ с прореживанием по времени. Основные свойства.

 

Принцип прореживания по времени наиболее удобно иллюстрируется в частном случае, когда N равно степени числа 2, т. е. В этом случае из исходной последовательности x (n), формируют две -точечные подпоследовательности и из четных и нечетных членов соответственно:

(1.155)

С учетом этого прямое ДПФ последовательности можно представить следующим образом:

(тут пропущен множитель W^k)

С учетом того, что последнее выражение можно переписать в виде:

(1.156)

или

0 £ k £ N – 1, (1.157)

где и – -точечные ДПФ последовательностей и соответственно.

Поскольку определено для а и определены только для то необходимо доопределить полученное выражение для Для этой цели воспользуемся свойством периодичности ДПФ. Действительно, и – периодические функции переменной k с периодом Следовательно

(1.158)

(1.159)

Тогда

(1.160)

Так как то выражение (1.157) и (1.160) можно записать таким образом:

(1.161)

В этом случае для вычисления двух -точечных ДПФ требуется комплексных умножений и приблизительно столько же комплексных сложений. Затем два -точечных ДПФ должны быть объединены, что потребует комплексных умножений и комплексных сло­жений. Следовательно, для всех значений k требуется или комплексных умножений, что уже при меньше чем

Проиллюстрируем вычисление X (k) в соответствии с полученным выражением для Для этой цели используем направленные сигнальные графы следующего вида (рис. 1.23).

 

Рис. 1.23. Направленные сигнальные графы

 

При этом предполагается, что ветви, входящие в узел суммируются (вычитаются), причем верхний выход соответствует сумме, а нижний – разности. Стрелка обозначает операцию умножения на значение множителя, указанного под стрелкой; если множитель не указан – передача по ветви равна 1.

Из рисунка 1.24 видно, что вычисляются два четырехточечные ДПФ четных и нечетных значений входной последовательности. Затем получается путем умножения на и прибавления Значение получается умножением на и прибавления Значение получается умножением на и вычитания из

Аналогичным образом вычисляются и остальные значения.

 

 

Рис. 1.24. Вычисление ДПФ для N = 8 на основе двух 4-х точечных

Рассмотренная схема вычислений может быть использована для расчета -точечных ДПФ в соответствии с полученными формулами. В этом случае -точечные ДПФ могут быть представлены как комбинация двух