Связь ДПФ и ДВПФ

Дискретные преобразования сигналов. Лекция 3 апреля 2018 г.; МФТИ 4.5. Связь ДПФ и ДВПФ Пусть x(k ) – N-точечная последовательность. ДВПФ этой последовательности N 1 X ( )  t  x(k )e  j 2 k , k 0 где   f t  f / f д – нормированная частота (доли частота дискретизации). Используя формулу обратного ДПФ, получим N 1 N 1 X ( )  t  [  X (n) e j 2 nk N ] k 0 n0 N 1 N 1 n0 k 0 e  j 2 k  t  X (n)  e  j 2 (  n )k N . Просуммируем N членов геометрической прогрессии: N 1 e  j 2 (  n )k N  k 0 e  j (  1 e  j 2 (  1 e n )( N 1) N n )N N  j 2 (  n ) N  e  j (  e n )N N  j (  n ) N n )N N   n sin  (  ) N sin  (  n )N N . n sin  (  ) N sin  (  Поэтому для X ( ) можем записать n ) N  j (  n ) ( N 1) N N (4.5.1) X ( )  t  X (n) e . n n0 sin  (  ) N Это интерполяционная формула восстановления континуальной функции X ( ) по коэффициентам ДПФ X (n). В точках   n / N имеет место N 1 sin  (  (4.5.2) X (n )  N t X (n),   1/ N. Таким образом, коэффициенты ДПФ X (n) можно рассматривать как отсчёты функции X ( ) / N t , взятые с шагом   1/ N в соответствии с теоремой отсчётов в частотной области. На рис. 4.5.1а представлен одиночный импульс конечной длительности и модуль его спектра. Рисунок 4.5.1б показывает, что периодическому повторению импульса с периодом T соответствует дискретизованная версия непрерывного спектра. Отдельные отсчёты X (nf ) связаны с коэффициентами ряда Фурье C n простым соотношением 2  j nt 1 T dt  f X ( nf ), f  1/ T . x ( t ) e T T/2 T /2 Cn  Рис. 4.5.1 1 Дискретные преобразования сигналов. Лекция 3 апреля 2018 г.; МФТИ Дискретизация импульса с шагом t приводит к периодическому повторению его спектра с периодом f д  1/ t (по нормированной частоте с периодом 1). Дискретная последовательность x(k ) и её непрерывный спектр (ДВПФ) X ( ) показаны на рис. 4.5.1в. Наконец, периодическому повторению последовательности x(k ) с периодом N соответствует дискретизованная версия непрерывной функции X ( ) с шагом   1/ N . Отдельные дискреты этой функции связаны с коэффициентами ДПФ соотношением (4.5.2). Эта связь иллюстрируется на рис. 4.5.1г. Дискретное время и дискретная частота – именно это свойство ДПФ (а также существование быстрого алгоритма БПФ) объясняет его повсеместное распространение в цифровых системах обработки сигналов. 4.6. Интерполяция добавлением нулевых отсчётов X ( ) с помощью ограниченного набора из N коэффициентов ДПФ может оказаться недостаточным (рис. 4.5.1в, г). Практический способ увеличения числа отсчётов функции X ( ) состоит в следующем. Определим новую Иногда качество визуализации ДВПФ y(k ) длиной в M отсчётов ( M  N ) путём дополнения исходной последовательности x(k ) нулевыми отсчётами. Число таких нулевых отсчётов будет M  N: последовательность  x(k ), 0  k  N  1, y (k )   N  k  M  1. 0, Для этой последовательности отсчётные значения функции X ( ) в точках  m  m / M , m  0, 1, , M  1, взятые с новым шагом   1/ M , будут M 1 X ( m )  t  y (k ) e  j 2 mk / M . (4.6.1) k 0 Это выражение с точностью до множителя t / M представляет собой М-точечное ДПФ, которое может быть вычислено, например, с использованием быстрых алгоритмов. Характерно, что если взять M  2N , то дополнительные отсчёты X ( m ) будут расположены между N первоначальными. При этом улучшается качество визуализации спектральной функции X ( ), которая остаётся неизменной от такого дополнения, так как она определяется первоначальной длиной массива x(k ). Рис. 4.6.1 иллюстрирует такую возможность. На рис. 4.6.1а представлено непрерывное изображение X ( ) для 16-точечной последовательности x(k )  sin 2 (2,1/16)k  sin[2 (3,12 /16)k   / 2]  sin 2 (5,6 /16.)k , состоящей из трёх синусоид с относительными частотами  1  2,1/16;  2  3,12 /16;  3  5, 6 /16. Заметим, что относительные частоты синусоид находятся в промежутках между соседними бинами ДПФ (1бин=1/N). 2 Дискретные преобразования сигналов. Лекция 3 апреля 2018 г.; МФТИ Рис. 4.6.1. Интерполяция за счёт дополнения нулями На рис. 4.6.1б изображены относительные величины первых восьми отсчётов ДВПФ на интервале 0    0,5: n )  N t X (n), n  [0, N  1], N  16. N Остальные восемь отсчётов расположены симметрично на интервале 0,5    1 . Все эти отсчёты X (  рассчитаны по 16 коэффициентам ДПФ X (n) 16-точечной действительной последовательности x(k ). Шаг дискретизации функции X ( ) равен при этом   (1/ N )  1/16. На рис. 4.6.1в показаны отсчёты функции (4.6.1) при M  2N  32, т. е. после двукратного увеличения числа её отсчётов путём дополнения последовательности x(k ) нулевыми отсчётами. Шаг дискретизации функции X ( ) равен при этом   (1/ M )  1/ 32. Случай M  4 N  64 (четырёхкратное увеличение числа отсчётов) представлен на рис. 4.6.1г. При M   и   0 мы получаем непрерывное изображение X ( ) для 16-точечной последовательности (рис. 4.6.1а). 4.7. Интерполяция функций с ограниченной полосой с помощью ДПФ Задача состоит в нахождении значений точек между уже известными точками функции с ограниченной полосой. Аналоговая функция, дискретизованная с шагом t  1/ 2 f в , точно задаётся интерполяционным рядом Котельникова: x(t )    x(k t )  k  sin 2 f в (t  k t ) . 2 f в (t  k t ) Предположим теперь, что известно только N точек функции. Функция, которая равна нулю вне интервала от 0 до N t, не может быть ограниченной по полосе. Следовательно, строгая интерполяция рядом Котельникова в этом случае невозможна. Поэтому допустим, что известные N точек представляют один период периодической, ограниченной по полосе действительной функции (рис. 4.7.1а). Коэффициенты ДПФ X (n) этой последовательности симметрично расположены на интервале N в соответствии со свойствами симметрии ДПФ и изображены на рис. 4.7.1б для случая 3 Дискретные преобразования сигналов. Лекция 3 апреля 2018 г.; МФТИ N  8 . Поместим (r 1) N нулей в середину последовательности X (n). Модифицированное ДПФ показано на рис. 4.7.1в для случая r  2. Обратное преобразование будет иметь rN точек на одном периоде и изображено на рис. 4.7.1г. Прямое и обратное ДПФ могут быть вычислены с помощью алгоритма быстрого преобразования Фурье – БПФ. Разновидности этого алгоритма будут рассмотрены в курсе «Цифровая обработка сигналов». Рис. 4.7.1 4.8. Временная и частотная оси ДПФ Определим физические размерности, связанные со значениями индексов k и n в последовательностях x(k ) и X (n). До сих пор в наших рассуждениях это были просто целые числа, n [0, N 1]. Рассмотрим последовательность (рис. 4.8.1а) из L  6 отсчётов прямоугольного импульса через y(k ). ДВПФ этой последовательности причём и k [0, N 1], Y ()  L 1  k 0 и L 1 y (k ) e  j 2k   e  j 2 k   e  j ( L1) k 0 1  e  j 2 L 1  e  j 2  e  j L  sin L  e  j sin   j5 f / f д sin 6 f / f д sin L sin 6  e  j5 e . sin  sin  sin f / f д Модуль этой периодической функции (с периодом f д ) не зависит от начала отсчёта и изображён на рис. 4.8.1б пунктиром. Рис. 4.8.1 Рис. 4.8.1 4 Дискретные преобразования сигналов. Лекция 3 апреля 2018 г.; МФТИ x(k ) длиной в N  30 отсчётов получена путём дополнения последовательности y(k ) нулевыми отсчётами. Число таких нулевых отсчётов будет N  L. Отсчётные значения функции X () в точках n  n / N , n  0, 1, , N 1, взятые с шагом   1/ N , будут Последовательность X (n )  N 1  x(k ) e  j 2nk / N . k 0 Это выражение с точностью до множителя 1/ N представляет собой N-точечное ДПФ. На рис. 1б изображены относительные величины N коэффициентов ДПФ на интервале 0  n  N 1: X (n)  X (  n ), n [0, N  1], N  30. N Расстояние по сетке частот ДПФ f  f д / N  1/ N t  1/ 30t Гц. Видно, что улучшается качество визуализации спектральной функции Y (), которая остаётся неизменной от такого дополнения, так как она определяется первоначальной длиной массива y(k ). Если бы ДПФ вычислялось по N  L  6 отсчетам, т. е. без дополнения нулями, то на интервале 0  n  N 1 был бы всего один отсчет X (0) , по которому визуализация спектральной функции Y () была бы невозможна. Расстояние по сетке частот ДПФ было бы f  f д / N  1/ N t  1/ 6t Гц. Частотная ось ДПФ в Герцах (Гц) N -точечное ДПФ отображает N отсчётов во временной области в N отсчётов в спектральной. Если мы хотим связать X (n) с шагом дискретизации t секунд, или с частотой дискретизации f д  1 / t Гц, то частота будет принимать значения n / N t  n f д / N Гц. Действительно, в этом случае период повторения X (n) равен f д  1 / t Гц, шаг сетки частот ДПФ (разрешение) составляет f  f д / N  1/ N t Гц. Таким образом, каждый отсчёт X (n) соответствует частоте n / N t  n f д / N Гц (рис. 6.1б). Частотная ось ДПФ в радианах в секунду Перейдём к частоте дискретизации д  2 f д  2 / t в радианах /с. В этом случае период повторения X (n) равен д  2 / t радиан/с, шаг сетки частот ДПФ (разрешение)   д / N  2 / N t радиан/с. Таким образом, каждый отсчёт составляет X (n) соответствует частоте n 2 / N t  nд / N радиан/с. Частотная ось ДПФ для нормированной частоты Введём нормированную частоту v  f t  f / f д (доли частоты дискретизации) В этом случае период повторения X (n) равен 1, шаг сетки частот ДПФ (разрешение) составляет   1/ N . Эту величину называют бином. Таким образом, каждый отсчёт X (n) соответствует нормированной частоте n / N  n бин. 5 Дискретные преобразования сигналов. Лекция 3 апреля 2018 г.; МФТИ Частотная ось ДПФ для нормированной угловой частоты Введём нормированную частоту   t   2 / д . В этом случае период повторения X (n) равен 2 радиан, шаг сетки частот ДПФ (разрешение) составляет   2 / N радиан. Таким образом, каждому отсчёту X (n) соответствует угол n2 / N радиан. Рассмотренные способы маркировки частотной оси ДПФ перечислены в таблице 4.8.1. Т а б л и ц а 4.8.1 Размерность частотной оси Частотная Период Разрешение переменная повторения по частоте Диапазон изменения частоты Гц f  nf д / N fд f  f д / N [0, f д ) Радиан/c   nд / N д   д / N [0, д )   n/ N 1   1/ N [0, 1)   2n / N 2   2 / N [0, 2) Нормированная частота Нормированный угол в радианах Пример 4.8.1. ДПФ прямоугольного импульса и его периодического повторения Напомним формулы анализа и синтеза ДПФ: формула анализа X[n]  формула синтеза N 1 x[k ]e j (2/ N ) nk , (без масштабирующего множителя (1/ N ) ),  k 0 x[k ]  N 1 X[n]e j (2/ N ) nk .  n0 1) Рассмотрим последовательность x  k  , изображенную на рис. 1а. Рис. 1. Иллюстрация ДПФ прямоугольного импульса 6 Дискретные преобразования сигналов. Лекция 3 апреля 2018 г.; МФТИ При вычислении ДПФ эту последовательность можно считать конечной последовательностью, длина которой равна 5. Периодическая (с периодом 5) последовательность x  k  показана на рис. 1б. Поскольку ее отсчеты постоянны над отрезком [0,4], то X[n]  4  e j (2/5) nk k 0  1  e j 2n  5, n  0, 5, 10,...,  иначе, 1  e j 2n /5 0, т. е. коэффициенты X[n] отличны от нуля только при n, кратных 5 и показаны на рис. 1в. Там же присутствует график модуля ДВПФ X ()  4 x (k ) e j  k  k 0  1  e j 5 e j 5/2 sin(5 / 2)   j /2 . 1  e j e sin( / 2) Ясно, что X[n] - последовательность отсчетов функции X () , вычисленных при n  2n / 5 . Пятиточечное ДПФ X[n] с связано с периодической последовательностью X[n] следующим образом:  X[n]   X[n], 0  n  N 1, иначе.  0, График этого ДПФ изображен на рис. 1 г. 2) Рассмотрим последовательность x  k  , изображенную на рис. 2 а. При вычислении ДПФ эту последовательность можно считать конечной последовательностью, длина которой равна 5. Периодическая (с периодом 10) последовательность x  k  показана на рис. 2, б. Поскольку ее отсчеты постоянны над отрезком [0,4], то 4 1 e j n X[n]   e j (2 /10) nk  k 0 1 e j n/5  e j n/2 sin  n / 2  e j 4 n/10 sin  n / 2 . sin  n /10 e j n/10 sin  n /10 Рис. 2 Модуль sin  n / 2 и фаза (n)  4 n /10 коэффициентов ДПФ приведены на рис. 2 в и рис. 2 г sin  n /10 соответственно ( крестиками обозначены точки, в которых фаза не определена). Сравнивая рис. 1 и рис. 2 видим, что добавление к исходной последовательности x  k  5 нулевых отсчетов увеличивает размерность ДПФ с 5 до 10. При этом повышается качество визуализации ДВПФ 9 1  e j 5 e j 5/2 sin(5 / 2) X ()   x (k ) e j  k    j /2 . 1  e j e sin( / 2) k 0 7 Дискретные преобразования сигналов. Лекция 3 апреля 2018 г.; МФТИ Пример 4.8.2. Гармонический сигнал x(t )  cos2f 0t дискретизуется так, что на периоде образуется 8 отсчетов. 1. Изобразить последовательность x(k ) и ее спектр. 2. Найти и изобразить по модулю ДВПФ и ДПФ последовательности 15 y (k )   x(m)1(k  m) и . m0 Решение 1. x(k )  cos2f 0 k t  cos20 k , 0  f 0 t  f 0 / f д  частота косинусоиды, нормированная к частоте дискретизации (доли частоты дискретизации). Спектр дискретизованной косинусоиды – две дельтафункции (с весом ½), повторяющиеся с периодом 1. x( k )     - 0 0  Решение 2. Последовательность y(k ) представляет собой отрезок из двух периодов косинусоиды. С учетом 1 2 1 2 того, что cos 20 k  exp( j 20 k )  exp( j 20 k ) можем записать для ДВПФ последовательности y(k ) 1  N 1  j 2  0 k  N 1 1  N 1  j 2  0 k  1 k  m e     1 k  m  e        m 0 2  k 0  m 0 2  k 0 1 1 sin      0  N sin      0  N  j 0  N 1 2  j 0  N 1 2 e  e  . sin      0  sin      0  Y   N 1 Модуль этой функции изображен на рис. б. Здесь N=16. |Y(ν)| б N∕2 ·  · −1 – · · · · · · ДПФ X[n]  N 1 x[k ]e j (2/ N ) nk ,  k 0 связаны N  n0 N с отсчетами n ), n [0, N  1], N  16. Если  0 кратно бину ДПФ 1/N, т. е. N [0, N 1], N  16 будут всего два отсчета ДПФ X (n0 ) и X (N  n0 )  X  (n0 ). X ( n )  X (  8 ν 1 · · n0 Коэффициенты  +1/N n ДВПФ 0  соотношением n0 , то на интервале N Дискретные преобразования сигналов. Лекция 3 апреля 2018 г.; МФТИ Задачи к лекции 3 апреля 2018 г. 1. Вещественный сигнал x(t) с полосой 2fв = 10 кГц дискретизуется в соответствии с теоремой отсчетов. По последовательности x(k) = x(kΔt) длиной в N = 1000 отсчетов вычисляется N-точечное N 1 ДПФ X  n   x  k  e j 2 nk N , п = 0, 1, 2,…N–1. Известны два значения Х(900) = 1 В и Х(420) = 5В. k 0 Найти все значения ДВПФ N 1 X    t  x  k  e j 2 k , k 0 которые можно определить. 2. Вычислить коэффициенты ДПФ X (n) для  2 rk ), 0  k  cos( x(k )   N  0, при других  N 1, k. и фиксированного значения r  5 и N  16. 3. Действительный сигнал x(t) дискретизуется с частотой fд = 10 кГц так, что наложение отсутствует. Получающаяся последовательность x(k) содержит N =512 отсчетов. По этой последовательности вычисляется 512-точечное ДПФ, коэффициенты которого определяются по формуле N 1 X  n   x  k  e j 2 nk N . k 0 Известно, что Х(11) = 2000(1+j). Что можно сказать о других X(n) и о значениях ДВПФ N 1 X    t  x  k  e j 2 8k k 0 на соответствующих частотах? 9