Индексация и перестановка спектральных отсчетов дискретного преобразования Фурье

Содержание
Введение
В предыдущем разделе мы получили выражения для прямого и обратного ДПФ:
$$ S(k) = \sum_{n=0}^{N-1} s(n) \cdot \exp \left( -j \cdot \frac{2\pi}{N} \cdot n \cdot k \right),\text{ } k=0 \ldots N-1; $$ $$ s(n) = \frac{1}{N} \cdot \sum_{k=0}^{N-1} S(k) \cdot \exp \left( j \cdot \frac{2\pi}{N} \cdot n \cdot k\right), \text{ } n=0 \ldots N-1. $$
(1)
Расчет ДПФ и ОДПФ ведется на основе индексов временных $n=0 \ldots N-1$ и частотных $k = 0 \ldots N-1$ отсчетов без учета частоты дискретизации.
Таким образом, можно использовать выражения для ДПФ и ОДПФ при любой частоте дискретизации, не меняя вычислительную программу.
В данном разделе мы рассмотрим, как привязать индексы ДПФ к значениям частоты $f$, выраженной в Герц, или к значениям циклической частоты $\omega = 2 \pi \cdot f$ рад/c.
Индексация спектральных отсчетов
При рассмотрении ДПФ мы говорили, что спектр $S(\omega)$ дискретного сигнала $s(n)$, $n = 0 \ldots N-1$, это периодическая функция с периодом $\Omega_{\textrm{max}} = 2 \pi \cdot F_{\textrm{s}}$ рад/c, где $F_{\textrm{s}}-$частота дискретизации исходного сигнала (Гц).
Соответственно период повторения спектра $S(f)$ дискретного сигнала $s(n)$, $n = 0 \ldots N-1$, для частоты $f$, выраженной в Герц, равен частоте дискретизации $F_{\textrm{max}} = F_{\textrm{s}}$ Гц.
ДПФ получается путем дискретизации периодической функции $S(\omega)$ на одном периоде повторения с шагом $\Delta \omega$
$$ \Delta \omega = \frac{\Omega_{\textrm{max}}}{N} = 2 \pi \cdot \frac{F_{\textrm{s}}}{N} \textrm{, рад/с}. $$
(2)
Таким образом, $k-$ый спектральный отсчет $S(k)$ соответствует частоте
$$ \omega(k) = k \cdot \Delta \omega = 2 \pi \cdot \frac{F_{\textrm{s}}}{N} \cdot k \textrm{, рад/с}, $$
(3)
или
$$ f(k) = k \cdot \Delta f = \frac{F_{\textrm{s}}}{N} \cdot k \textrm{, Гц}. $$
(4)
Пример 1. При частоте дискретизации $F_{\text{s}} = 120 \text{ кГц}$, при $N = 1024$, первый спектральный отсчет $S(0)$ соответствует частоте $f = \frac{0}{1024} \cdot 120 = 0 \text{ Гц}$.
Пример 2. При частоте дискретизации $F_{\text{s}} = 120 \text{ кГц}$, при $N = 1024$, спектральный отсчет с номером $k = 128$, $S(128)$ соответствует частоте $f = \frac{128}{1024} \cdot 120 = 15 \text{ кГц}$.
Перестановка спектральных отсчетов ДПФ
Рисунок 1. Амплитудный спектр сигнала $s(n)$
Пусть входной сигнал $s(n)$, $n = 0 \ldots N-1$, является комплексным и состоит из одной комплексной экспоненты с частотой $f_0 = -20$ Гц:
$$ s(n) = \exp\left( j \cdot 2\pi \cdot n \cdot \frac{f_0}{F_{\textrm{s}}}\right) . $$
(5)
Зададим частоту дискретизации равной $F_{\textrm{s}} = 120$ Гц и возьмем $N = 30$ отсчетов исходного сигнала.
Рассчитаем ДПФ $S(k)$, $k = 0 \ldots N-1$, данного сигнала и получим амплитудный спектр, как это показано на рисунке 1.
Как можно заметить на рисунке 1, в спектре сигнала присутствует только одна компонента с индексом $k = 25,$ что согласно (4) соответствует частоте
$$ f(25) = \frac{120}{30} \cdot 25 = 100 \textrm{, Гц}, $$
(6)
что может показаться странным, потому что мы задавали частоту исходного сигнала $f_0 = -20$ Гц.
Однако ничего особенного в этом нет, если вспомнить, что спектр $S(f)$ нашего дискретного сигнала $s(n)$ является периодической функцией с периодом $F_{\textrm{s}} = 120$ Гц, т.е. для нашего дискретного сигнала спектр $S(f)$ состоит из бесконечного числа гармоник с частотами $f(m) = f_0 + m \cdot F_{\textrm{s}}$ , $m = 0, \pm 1, \pm 2, \ldots$, как это показано на рисунке 2.
Рисунок 2. Периодический спектр $S(f)$ сигнала $s(n)$
Из рисунка 2 следует, что при дискретизации спектра $S(f)$ на одном периоде повторения от 0 до $F_{\textrm{s}}$ Гц (на рисунке 2 обозначено как период ДПФ) в выборку попадает периодическая гармоника на частоте 100 Гц. При этом спектр $S(f)$ в интервале частот от $\frac{F_{\textrm{s}}}{2}$ Гц до $F_{\textrm{s}}$ Гц периодически повторяет спектр $S(f)$ в интервале частот от $-\frac{F_{\textrm{s}}}{2}$ Гц до $0$ Гц.
Таким образом, мы можем произвести перестановку спектральных отсчетов ДПФ для анализа спектра сигнала в интервале частот от $-\frac{F_{\textrm{s}}}{2}$ до $\frac{F_{\textrm{s}}}{2}$ Гц.
Сделаем важное замечание. Частотная компонента, соответствующая частоте $\frac{F_{\textrm{s}}}{2}$ Гц, в силу периодичности спектра дискретного сигнала, также соответствует частоте $-\frac{F_{\textrm{s}}}{2}$ Гц. При перестановке мы будем относить эту компоненту к частоте $-\frac{F_{\textrm{s}}}{2}$ Гц.
Перестановка спектральных отсчетов ДПФ для четного $N$
В случае четного $N$ спектральный отсчет $S\left( \frac{N}{2}\right)$, согласно (4), соответствует частоте $\frac{F_{\textrm{s}}}{2}$ Гц. Как мы отметили выше, этот же отсчет соответствует частоте $-\frac{F_{\textrm{s}}}{2}$ Гц. Тогда можно записать спектр $S_\textrm{sh}(k)$ после перестановки для четного $N$ в виде:
$$ S_\textrm{sh}(k) = \begin{cases} S \left( k + \frac{N}{2}\right) &\text{если $k = 0 \ldots \frac{N}{2}-1$};\\ S \left( k - \frac{N}{2}\right) &\text{если $k = \frac{N}{2} \ldots N-1$}. \end{cases} $$
(7)
$k-$ый спектральный отсчет после перестановки $S_\textrm{sh}(k)$ соответствует частоте
$$ \omega_\textrm{sh}(k) = - 2 \pi \cdot \frac{F_{\textrm{s}}}{2} + k \cdot \Delta \omega =2 \pi \cdot \left( - \frac{F_{\textrm{s}}}{2} + \frac{F_{\textrm{s}}}{N} \cdot k \right) \textrm{, рад/с}, $$
(8)
или
$$ f_\textrm{sh}(k) = -\frac{F_{\textrm{s}}}{2} + k \cdot \Delta f = -\frac{F_{\textrm{s}}}{2} + \frac{F_{\textrm{s}}}{N} \cdot k \textrm{, Гц}. $$
(9)
Таким образом, отсчет $S_\textrm{sh}(0)$ соответствует частоте $f_\textrm{sh}(0) = -\frac{F_{\textrm{s}}}{2}$ Гц, отсчет $S_\textrm{sh} \left( \frac{N}{2} \right)$ соответствует частоте $f_\textrm{sh}\left( \frac{N}{2} \right) = 0$ Гц и отсчет $S_\textrm{sh}(N-1)$ соответствует частоте $f_\textrm{sh}\left( N-1\right) = \frac{F_{\textrm{s}}}{2} - \frac{F_{\textrm{s}}}{N}$ Гц.
Перестановка спектральных отсчетов для четного $N$ показана на рисунке 3a.

Рисунок 3. Перестановка спектральных отсчетов
a) для четного $N$, б) для нечетного $N$
Перестановка спектральных отсчетов ДПФ для нечетного $N$
В случае нечетного $N$ спектральный отсчет $S\left( \frac{N-1}{2}\right)$, согласно (4), соответствует частоте $\frac{F_{\textrm{s}}}{2} - \frac{F_{\textrm{s}}}{2 \cdot N}$ Гц, а спектральный отсчет $S\left( \frac{N+1}{2}\right)$ соответствует частоте $\frac{F_{\textrm{s}}}{2} + \frac{F_{\textrm{s}}}{2 \cdot N}$ Гц.
Спектр $S_\textrm{sh}(k)$ после перестановки для нечетного $N$:
$$ S_\textrm{sh}(k) = \begin{cases} S \left( k + \frac{N+1}{2}\right) &\text{если $k = 0 \ldots \frac{N-1}{2}-1$};\\ S \left( k - \frac{N-1}{2}\right) &\text{если $k = \frac{N-1}{2} \ldots N-1$}. \end{cases} $$
(10)
$k-$ый спектральный отсчет после перестановки $S_\textrm{sh}(k)$ соответствует частоте
$$ \omega_\textrm{sh}(k) = 2 \pi \cdot \left(- \frac{F_{\textrm{s}}}{2} + \frac{F_{\textrm{s}}}{2 \cdot N} \right)+ k \cdot \Delta \omega = 2 \pi \cdot \left(-\frac{F_{\textrm{s}}}{2} + \frac{F_{\textrm{s}}}{2 \cdot N} + \frac{F_{\textrm{s}}}{N} \cdot k \right) \textrm{, рад/с}, $$
(11)
или
$$ f_\textrm{sh}(k) = -\frac{F_{\textrm{s}}}{2} + \frac{F_{\textrm{s}}}{2 \cdot N} + k \cdot \Delta f = -\frac{F_{\textrm{s}}}{2} + \frac{F_{\textrm{s}}}{2 \cdot N} + \frac{F_{\textrm{s}}}{N} \cdot k \textrm{, Гц}. $$
(12)
Рисунок 4. Амплитудный спектр $|S_\textrm{sh}(k)|$
после перестановки и соответствующие
значения частоты $f_\textrm{sh}(k)$
После перестановки спектральных отсчетов, в случае нечетного $N$, спектральный отсчет $S_\textrm{sh}(0)$, согласно (12), соответствует частоте $f_\textrm{sh}(0) = -\frac{F_{\textrm{s}}}{2} + \frac{F_{\textrm{s}}}{2 \cdot N}$ Гц, спектральный отсчет $S_\textrm{sh} \left(\frac{N-1}{2} \right)$ соответствует частоте $f_\textrm{sh}\left(\frac{N-1}{2} \right) = 0$ Гц и последний отсчет $S_\textrm{sh}(N-1)$ соответствует частоте $f_\textrm{sh}(N-1) = \frac{F_{\textrm{s}}}{2} - \frac{F_{\textrm{s}}}{2 \cdot N}$ Гц.
Перестановка спектральных отсчетов для нечетного $N$ показана на рисунке 3б.
Пример перестановки спектральных отсчетов
Произведем перестановку спектральных отсчетов для корректного отображения отрицательных частот для приведенного выше примера (рисунок 1).
Количество отсчетов в приведенном примере $N = 30$, значит, мы можем воспользоваться выражением (7) для получения $S_\textrm{sh}(k)$. Тогда после перестановки спектральные отсчеты будут соответствовать частотам (9).
На рисунке 4 приведен амплитудный спектр $|S_\textrm{sh}(k)|$ после перестановки, а также значения частоты $f_\textrm{sh}(k)$ (Гц), которой соответствуют спектральные отсчеты $S_\textrm{sh}(k)$.
Как можно видеть на рисунке 4, после перестановки спектральных отсчетов компонента $S_\textrm{sh}(10)$ соответствует частоте $f_\textrm{sh}(10) = -20$ Гц, как мы и задавали для исходного сигнала.
Заинтересованные читатели могут самостоятельно повторить приведенные примеры выполнив скрипт dft_indexation.py.
							
						# -*- coding: utf-8 -*-
"""
Created on Sun May 14 11:44:47 2017

@author: bakhu
"""

import numpy as np
import matplotlib.pyplot as plt


# Размерность ДПФ
N = 30    
 
# Частота сигнала Hz 
f0 = -20.0

# Частота дискретизации Hz 
Fs = 120.0

n = np.linspace(0, N, N, endpoint = False, dtype = 'float64')

f = n/N * Fs

# Исходный сигнал
s = np.exp(2j * np.pi * n * f0 / Fs)

# ДПФ исходного сигнала
S = np.abs( np.fft.fft(s))

# Перестановка ДПФ
Ssh = np.fft.fftshift(S)
fsh = f - Fs/2.0

# Построение графиков
plt.figure(1)
plt.stem(f, np.abs(S))
plt.xlabel('f, Hz')
plt.ylabel('|S(f)|')


plt.figure(2)
plt.stem(fsh, np.abs(Ssh))
plt.xlabel('fsh, Hz')
plt.ylabel('|Ssh(fsh)|')

plt.show()
						
					
					
Выводы
В данном разделе мы рассмотрели вопрос индексации и перестановки спектральных отсчетов на выходе ДПФ.
Были приведены выражения для перестановки спектральных отсчетов для четного и нечетного $N$ для корректного отображения отрицательных частот после ДПФ.
Более детально свойства ДПФ будут рассмотрены в следующих разделах.

Ваши комментарии, вопросы и пожелания вы можете оставить на форуме или в гостевой книге.
Список литературы
[1] Сергиенко А.Б. Цифровая обработка сигналов. Питер, 2002.

[2] Оппенгейм А., Шафер Р. Цифровая обработка сигналов. Техносфера, 2006.

[3] Гольденберг Л.М., Матюшкин Б.Д., Поляк М.Н. Цифровая обработка сигналов. Радио и связь, 1985.

[4] Bracewell R.N. The Fourier Transform and its Applications. McGraw Hill, 2000.

[5] Oppenheim Alan V. and Schafer Ronald W. Discrete-Time Signal Processing. Second Edition. Prentice-Hall, New Jersey, 1999.

[6] Robert J. Marks II The Joy of Fourier: Analysis, Sampling Theory, Systems, Multidimensions, Stochastic Processes, Random Variables, Signal Recovery, Pocs, Time Scales, & Applications. Baylor University, 2006.

[7] Nussbaumer Henri J. Fast Fourier Transform and Convolution Algorithms. Second Corrected and Updated Edition. Springer-Verlag, 1982.

Oбнаружили ошибку в тексте? Выделите ее мышкой и нажмите
Описание (необязательно)
Закрыть Х