Mengapa DFT Menganggap Sinyal Transformasi Berkala?

10

Dalam banyak buku pemrosesan sinyal, diklaim bahwa DFT mengasumsikan sinyal yang ditransformasikan menjadi berkala (dan inilah alasan mengapa kebocoran spektral misalnya dapat terjadi).

Sekarang, jika Anda melihat definisi DFT, tidak ada asumsi seperti itu. Namun, dalam artikel Wikipedia tentang transformasi Fourier diskrit-waktu (DTFT), dinyatakan bahwa

Ketika urutan data input adalah periodik, Persamaan.2 dapat direduksi secara komputasi menjadi transformasi Fourier diskrit (DFT) $x[n]$ $N$

Jadi, apakah asumsi ini berasal dari DTFT?
Sebenarnya, ketika menghitung DFT, apakah saya sebenarnya menghitung DTFT dengan asumsi bahwa sinyal itu periodik?

discrete-signals signal-analysis dft pengguna10839
sumber

Karena DFT X [k] dari x [n] adalah periode pertama dari Discrete Fourier Series (DFS) dari sinyal periodik xp [n] yang periode pertamanya diambil sebagai x [n]

Fat32

1

Sepertinya saya harus menulis jawaban yang berbeda untuk ini. DFT menganggap sinyal yang ditransformasikan adalah periodik karena cocok dengan seperangkat fungsi dasar untuk sinyal yang ditransformasikan, yang semuanya adalah periodik.

robert bristow-johnson

1

DFT hanyalah ekspresi sederhana dari DFS, sehingga asumsi periodik secara inheren ada.

lxg

12

Sudah ada beberapa jawaban yang baik, tetapi saya masih merasa ingin menambahkan penjelasan lain, karena saya menganggap topik ini sangat penting untuk memahami banyak aspek pemrosesan sinyal digital.

Pertama-tama, penting untuk dipahami bahwa DFT tidak 'mengasumsikan' periodisitas sinyal yang akan diubah. DFT hanya diterapkan pada sinyal hingga dengan panjang dan koefisien DFT yang sesuai ditentukan oleh $N$

\begin{matrix} (1) & X [k] = \sum_{n = 0}^{N - 1} x [n] e^{- j 2 π n k / N}, k = 0, 1, \dots, N - 1 \end{matrix}

$X[k]=\sum_{n=0}^{N-1}x[n]e^{-j2\pi nk/N},\quad k=0,1,\ldots,N-1\tag{1}$

Dari (1) jelas bahwa hanya sampel dalam interval yang dipertimbangkan, jadi tidak ada periodisitas yang diasumsikan. Di sisi lain, koefisien dapat diartikan sebagai koefisien Fourier dari kelanjutan periodik sinyal . Ini dapat dilihat dari transformasi invers $x[n]$ $[0,N-1]$ $X[k]$ $x[n]$

\begin{matrix} (2) & x [n] = \sum_{k = 0}^{N - 1} X [k] e^{j 2 π n k / N} \end{matrix}

$x[n]=\sum_{k=0}^{N-1}X[k]e^{j2\pi nk/N}\tag{2}$

yang menghitung dengan benar dalam interval , tetapi juga menghitung kelanjutan periodik di luar interval ini karena sisi kanan dari (2) adalah periodik dengan periode . Properti ini melekat dalam definisi DFT, tetapi tidak perlu mengganggu kita karena biasanya kita hanya tertarik pada interval . $x[n]$ $[0,N-1]$ $N$ $[0,N-1]$

Mempertimbangkan DTFT $x[n]$

\begin{matrix} (3) & X (ω) = \sum_{n = - \infty}^{\infty} x [n] e^{- j n ω} \end{matrix}

$X(\omega)=\sum_{n=-\infty}^{\infty}x[n]e^{-jn\omega}\tag{3}$

kita dapat melihat dengan membandingkan (3) dengan (1), bahwa jika adalah urutan terbatas dalam interval , koefisien DFT adalah sampel dari DTFT : $x[n]$ $[0,N-1]$ $X[k]$ $X(\omega)$

\begin{matrix} (4) & X [k] = X (2 π k / N) \end{matrix}

$X[k]=X(2\pi k/N)\tag{4}$

Jadi salah satu penggunaan DFT (tapi tentu saja bukan satu-satunya) adalah untuk menghitung sampel DTFT. Tetapi ini hanya berfungsi jika sinyal yang akan dianalisis memiliki panjang yang terbatas . Biasanya sinyal panjang terbatas ini dikonstruksi dengan memberi sinyal yang lebih panjang. Dan ini adalah jendela yang menyebabkan kebocoran spektral.

Sebagai komentar terakhir, perhatikan bahwa DTFT dari kelanjutan periodik dari urutan hingga dapat diekspresikan dalam hal koefisien DFT dari : $\tilde{x}[n]$ $x[n]$ $x[n]$

\begin{matrix} (5) & \tilde{x} [n] = \sum_{k = - \infty}^{\infty} x [n - k N] \end{matrix}

$\tilde{x}[n]=\sum_{k=-\infty}^{\infty}x[n-kN]\tag{5}$

\begin{matrix} (6) & \tilde{X} (ω) = \frac{2 π}{N} \sum_{k = - \infty}^{\infty} X [k] δ (ω - 2 π k / N) \end{matrix}

$\tilde{X}(\omega)=\frac{2\pi}{N}\sum_{k=-\infty}^{\infty}X[k]\delta(\omega-2\pi k/N)\tag{6}$

EDIT: Fakta bahwa dan diberikan di atas adalah pasangan transformasi DTFT dapat ditunjukkan sebagai berikut. Catatan pertama bahwa DTFT sisir impuls waktu diskrit adalah sisir Dirac: $\tilde{x}[n]$ $\tilde{X}(\omega)$

\begin{matrix} (7) & \sum_{k = - \infty}^{\infty} δ [n - k N] ⟺ \frac{2 π}{N} \sum_{k = - \infty}^{\infty} δ (ω - 2 π k / N) \end{matrix}

$\sum_{k=-\infty}^{\infty}\delta[n-kN]\Longleftrightarrow\frac{2\pi}{N}\sum_{k=-\infty}^{\infty}\delta(\omega-2\pi k/N)\tag{7}$

Urutan dapat ditulis sebagai konvolusi dengan sisir impuls: $\tilde{x}[n]$ $x[n]$

\begin{matrix} (8) & \tilde{x} [n] = x [n] ⋆ \sum_{k = - \infty}^{\infty} δ [n - k N] \end{matrix}

$\tilde{x}[n]=x[n]\star \sum_{k=-\infty}^{\infty}\delta[n-kN]\tag{8}$

Karena konvolusi berhubungan dengan perkalian dalam domain DTFT, DTFT dari diberikan oleh perkalian dengan sisir Dirac: $\tilde{X}(\omega)$ $\tilde{x}[n]$ $X(\omega)$

\begin{matrix} (9) & \begin{aligned} \tilde{X} (ω) & = X (ω) \cdot \frac{2 π}{N} \sum_{k = - \infty}^{\infty} δ (ω - 2 π k / N) \\ = \frac{2 π}{N} \sum_{k = - \infty}^{\infty} X (2 π k / N) δ (ω - 2 π k / N) \end{aligned} \end{matrix}

$\begin{align}\tilde{X}(\omega)&=X(\omega)\cdot\frac{2\pi}{N}\sum_{k=-\infty}^{\infty}\delta(\omega-2\pi k/N)\\&=\frac{2\pi}{N}\sum_{k=-\infty}^{\infty}X(2\pi k/N)\delta(\omega-2\pi k/N)\end{align}\tag{9}$

Menggabungkan dengan menetapkan hasil . $(9)$ $(4)$ $(6)$

Matt L.
sumber

panah bawah jawaban ini karena alasan yang sama saya punya jawaban yang lebih baru @ hotpaw2. dalam pernyataan ini: "Dari (1) jelas bahwa hanya sampel dalam interval yang dipertimbangkan, jadi tidak ada periodisitas yang diasumsikan." $x[n]$ $[0,N−1]$ kesimpulannya tidak mengikuti dari premis.

robert bristow-johnson

4

@ robertbristow-johnson: Ya. Beri saya sampel berturut-turut, dan saya beri Anda DFT. Saya tidak perlu berasumsi apa pun tentang sinyal di luar kisaran , bahkan keberadaannya pun tidak. Ini adalah satu-satunya hal yang saya klaim dalam kalimat itu, dan itu jelas benar. Untuk menghitung DFT saya tidak perlu tahu apa pun kecuali nilai-nilai dalam interval . Tidak yakin bagaimana Anda bisa salah mengerti atau salah membaca pernyataan saya. Jika ini masalah formulasi maka saya akan senang untuk mengklarifikasi kalimat saya, tetapi konten-bijaksana itu sebenarnya sepele.

N

$N$

[0, N - 1]

$[0,N-1]$

[0, N - 1]

$[0,N-1]$

Matt L.

4

baca jawaban lain di bawah ini dan jawaban saya di utas lainnya. ini bukan tentang apa yang Anda asumsikan tentang luar . ini tentang apa yang "diasumsikan" transformasi (jika kita diizinkan untuk melakukan antropomorfisasi sedikit) tentang luar . kita bisa mengetahui apa yang diasumsikan berubah ketika kita menjalankan operasi dalam satu domain yang menggeser domain lain dengan jumlah integer.

x [n]

$x[n]$

0 \leq n \leq N - 1

$0 \le n \le N-1$

x [n]

$x[n]$

0 \leq n \leq N - 1

$0 \le n \le N-1$

robert bristow-johnson

@MattL. (9) harus membaca alih-alih

= \frac{2 π}{N} \sum_{k = - \infty}^{\infty} X [k] \cdot δ (ω - 2 π k / N)

$=\dfrac{2\pi}{N} \sum_{k=-\infty}^{\infty}X[k]\cdot \delta\left(\omega-2\pi k /N\right)$

= \frac{2 π}{N} \sum_{k = - \infty}^{\infty} X (2 π k / N) \cdot δ (ω - 2 π k / N)

$=\dfrac{2\pi}{N} \sum_{k=-\infty}^{\infty}X(2\pi k/ N)\cdot \delta\left(\omega-2\pi k /N\right)$

jomegaA

@jomegaA: Tidak dalam kedua kasus. Seperti yang dinyatakan dalam kalimat terakhir dari jawaban saya, hasil akhir (6) disimpulkan dari menggabungkan (9) dengan (4), jadi tentu saja , tetapi dalam (9) ) itu berasal dari DTFT . Dan mengenai faktor penskalaan , itu pasti perlu ada di sana. Jangan bingung ekspresi menggunakan dan , mereka memiliki faktor penskalaan yang berbeda.

X [k] = X (2 π k / N)

$X[k]=X(2\pi k/N)$

X (ω)

$X(\omega)$

2 π / N

$2\pi/N$

ω

$\omega$

f

$f$

Matt L.

8

Itu berasal dari definisi sinyal domain waktu:

x [n] = \sum_{k = 0}^{N - 1} X [k] e^{\frac{2 π i n k}{N}}

$x \left[ n \right] = \sum_{k = 0}^{N - 1} X \left[ k \right] {e}^{\frac{2 \pi i n k}{N}}$

Anda dapat melihat dengan definisi bahwa . Di sisi lain DFT merekonstruksi dengan sempurna sampel N sinyal. Oleh karena itu Anda dapat menyimpulkannya dengan menganggapnya sebagai kelanjutan yang berkala. $x \left[ n \right] = x \left[ n + N \right]$

Sudut pandang lain akan melihat DFT sebagai Finite Discrete Fourier Series (Sebenarnya, Lihat di Discrete Fourier Series - DFS ), yang tentu saja menunjukkan bahwa sinyal bersifat periodik (Penjumlahan sinyal hingga terbatas dengan periode adalah sinyal yang memiliki periode ). $T$ $T$

Royi
sumber

2

Saya tidak melihat bagaimana itu datang dari definisi.

user10839

1

@ user10839: Cukup evaluasi dan Anda akan melihat bahwa itu sama dengan . Sebagaimana ditunjukkan dalam jawabannya, DFT hanyalah serangkaian Fourier dari sinyal domain waktu. Panjang sinyal domain waktu yang terbatas dianggap sebagai periode fundamental.

x [n + N]

$x[n+N]$

x [n]

$x[n]$

Matt L.

@ user10839, Cukup tancapkan ke persamaan. Eksponen dapat didefinisikan dengan fungsi Cosine dan Sine, yang seperti terlihat memiliki periode .

\frac{n k}{N}

$\frac{nk}{N}$

Royi

1

DFT bukan DFS. Ini luar biasa, tetapi DFT memberi Anda koefisien deret Fourier. Penting untuk dicatat bahwa DFT sama seperti transformasi linear lainnya. Ini adalah perkalian matriks. Matriksnya adalah orthonormal, yang membuatnya bagus. Dapat juga ditunjukkan bahwa koefisien keluaran sama dengan ekspansi deret Fourier yang sesuai dari data, tetapi transformasi Fourier bukanlah deret Fourier (tipe mismatch: p).

thang

@thang, aku tidak tahu apa maksudmu. DFT adalah DFS. Mereka sama. Sangat mudah untuk melihatnya. Perhatikan, ini adalah Discrete Fourier Series dan bukan Fourier Series (With integral). Lihat di sini en.wikipedia.org/wiki/Discrete_Fourier_series dan lihat itu DFT.

Royi

5

Ini adalah asumsi yang tidak perlu (dan seringkali salah). DFT hanyalah basis transformasi dari vektor terbatas.

Vektor-vektor dasar DFT kebetulan merupakan potongan-potongan fungsi periodik yang dapat diperluas secara tak terbatas. Tetapi tidak ada yang secara inheren periodik tentang input atau hasil DFT kecuali Anda memperpanjang vektor basis di luar aperture DFT. Banyak bentuk analisis sinyal tidak memerlukan ekstensi atau asumsi apa pun di luar jendela sampel atau vektor data terbatas.

Setiap artefak "kebocoran" juga dapat diasumsikan berasal dari konvolusi jendela persegi panjang standar dengan sinyal yang tidak periodik atau periodisitas atau stasioneritas yang tidak diketahui. Ini jauh lebih masuk akal ketika menganalisis tumpang tindih jendela FFT, di mana asumsi periodisitas di luar salah satu jendela DFT atau FFT dapat tidak konsisten dengan data di jendela lain.

Periodisitas dapat membuat matematika yang menghubungkan DFT ke DTFT lebih mudah ditelusur. Tetapi setiap hubungan dengan DTFT mungkin atau mungkin tidak diperlukan ketika benar-benar menggunakan FFT untuk pemrosesan sinyal (tergantung pada sifat transformasi Fourier mana yang diperlukan untuk analisis lebih lanjut dari metode pemrosesan).

hotpaw2
sumber

panah bawah untuk alasan yang sama saya panah bawah jawaban baru Anda tentang hal ini.

robert bristow-johnson

5

Ok, jawaban saya akan agak berbeda dari jawaban lainnya. jawaban saya menerima premis pertanyaan alih-alih menyangkal premis pertanyaan.

alasan bahwa DFT "mengasumsikan" sinyal input (sinyal yang akan ditransformasikan, apa yang saya asumsikan OP maksudkan dengan "sinyal yang ditransformasi") bersifat periodik adalah karena DFT cocok dengan kumpulan fungsi dasar untuk sinyal input tersebut, yang semuanya bersifat periodik.

pertimbangkan serangkaian fungsi basis yang berbeda:

g_{k} (u) ≜ u^{k} 0 \leq k < N

$g_k(u) \triangleq u^k \quad \quad 0 \le k < N$

dan diberikan sampel input : $N$

x [n] 0 \leq n < N

$x[n] \quad \quad 0 \le n < N$

kita dapat memasukkan jumlah linier dari fungsi-fungsi dasar ini ke urutan input $g_k(n)$

\begin{aligned} x [n] & = \sum_{k = 0}^{N - 1} X [k] g_{k} (n) \\ = \sum_{k = 0}^{N - 1} X [k] n^{k} \end{aligned}

$\begin{align} x[n] & = \sum\limits_{k=0}^{N-1} X[k] g_k(n) \\ & = \sum\limits_{k=0}^{N-1} X[k] n^k \\ \end{align}$

dengan pemilihan koefisien bijaksana . menghitung semua membutuhkan pemecahan linear persamaan dengan tidak diketahui. Anda dapat menggunakan eliminasi Gaussian untuk melakukannya. $X[k]$ $X[k]$ $N$ $N$

dengan nilai yang benar untuk untuk , kita dapat memastikan bahwa jumlah fungsi daya ini (yang merupakan polinomial urutan- ) akan dievaluasi secara tepat untuk untuk setiap sedemikian rupa sehingga . $N$ $X[k]$ $0 \le k \le N-1$ $(N-1)$ $x[n]$ $n$ $0 \le n \le N-1$

sekarang bagaimana jika Anda menggunakan penjumlahan itu untuk melampaui interval ? Anda dapat mengevaluasi untuk setiap . Anda akan melihat bahwa perilaku fungsi tersebut adalah polinomial orde- karena memang begitulah adanya. untuk cukup besar, hanya daya tertinggi dengan koefisien bukan nol yang akan menentukan tren untuk ekstrapolasi . $0 \le n \le N-1$ $n$ $(N-1)$ $n$ $x[n]$

jadi sekarang, dengan DFT kami menyesuaikan satu set fungsi basis yang berbeda dengan urutan input kami:

g_{k} (u) ≜ \frac{1}{N} e^{+ j 2 π k u / N} 0 \leq k < N

$g_k(u) \triangleq \frac{1}{N} e^{+j 2 \pi k u/N} \quad \quad 0 \le k < N$

\begin{aligned} x [n] & = \sum_{k = 0}^{N - 1} X [k] g_{k} (n) \\ = \frac{1}{N} \sum_{k = 0}^{N - 1} X [k] e^{+ j 2 π n k / N} \end{aligned}

$\begin{align} x[n] & = \sum\limits_{k=0}^{N-1} X[k] g_k(n) \\ & = \frac{1}{N} \sum\limits_{k=0}^{N-1} X[k] e^{+j2\pi n k/N} \\ \end{align}$

dan koefisien, , dapat dipecahkan untuk dan adalah: $X[k]$

X [k] = \sum_{n = 0}^{N - 1} x [n] e^{- j 2 π n k / N}

$X[k] = \sum\limits^{N-1}_{n=0} x[n] \ e^{-j2\pi n k/N}$

penempatan adalah masalah konvensi. saya letakkan di mana sebagian besar literatur menempatkan faktor . itu bisa dihapus dari persamaan dan dimasukkan ke dalam persamaan . atau "setengah" darinya ( ) dapat ditempatkan dengan kedua persamaan. itu hanya masalah konvensi. $\frac{1}{N}$ $\frac{1}{N}$ $x[n]$ $X[k]$ $\sqrt{\frac{1}{N}}$

tapi di sini kita menyesuaikan satu set fungsi basis yang semuanya periodik dengan periode ke aslinya . sehingga bahkan jika berasal dari urutan lagi tidak periodik, DFT sedang mempertimbangkan bahwa adalah jumlah dari sekelompok fungsi dasar masing-masing yang periodik dengan periode . jika Anda menjumlahkan banyak fungsi periodik, semua dengan periode yang sama, jumlahnya juga harus periodik dengan periode yang sama. $N$ $x[n]$ $x[n]$ $x[n]$ $N$

robert bristow-johnson
sumber

untuk polemik yang lebih sedikit, di mana saya membantah anggapan bahwa DFT tidak perlu memperpanjang data yang diteruskan secara berkala, lihat jawaban sebelumnya dari saya . saya lebih suka tidak mengulanginya di sini.

robert bristow-johnson

1

DFT bersifat diskrit. DTFT kontinu. Kita bisa mendapatkan DFT dari DTFT dengan mengambil sampelnya dengan kereta pulsa periode yang tepat, yang sebenarnya sama dengan mengalikannya dengan kereta pulsa. Perkalian dalam domain transformasi sama dengan konvolusi dalam domain waktu diskrit, ini menyiratkan periodisitas sinyal.

pelajar
sumber

DTFT kontinu? Bagaimana bisa?

jojek

2

Hasil DTFT bersifat kontinu (dalam frekuensi).

Deve

Memang - dengan demikian Anda harus menyatakannya dengan jelas untuk menghindari kesalahpahaman dan menyediakan persamaan yang memadai.

jojek

@jojek Thats true, saya juga berpikir jawaban ini dapat ditingkatkan dengan beberapa persamaan

Deve

1

Saya akan menambahkan rincian lebih lanjut segera.

pelajar

0

Hanya DFT yang praktis di dunia digital diskrit karena asumsi berkala pada kedua domain. (Jika Anda menyebutnya seperti itu.) Karena sinyal non periodik pada satu domain menyebabkan sinyal kontinu pada domain lainnya dan Anda hanya dapat menyimpan sinyal diskrit dalam memori digital. Jadi, Anda perlu berasumsi bahwa sinyal-sinyal tersebut periodik pada kedua domain untuk membuatnya terpisah pada kedua domain.

Ketika Anda menghitung DTFT Anda mendapatkan sinyal kontinu dalam domain frekuensi sebagai output.
Saya tidak berpikir Anda akan menggunakan prosedur yang sama ketika Anda menghitung DFT secara praktis. Ketika Anda benar-benar menghitung DTFT dan DFT, Anda akan memahami bahwa kedua transformasi perhitungan adalah cerita yang berbeda.

Penasaran Sam
sumber

0

Karena sinyalnya periodik, sinyalnya yang bergeser waktu tidak mengubah besaran absolut dari domain frekuensi.

X [k] = \sum_{k = 0}^{N - 1} x [n] e^{\frac{2 π i n k}{N}}

$X \left[ k \right] = \sum_{k = 0}^{N - 1} x \left[ n \right] {e}^{\frac{2 \pi i n k}{N}}$

e^{\frac{- 2 π i D k}{N}} X [k] = \sum_{k = 0}^{N - 1} x [n - D] e^{\frac{2 π i n k}{N}} e^{\frac{- 2 π i D k}{N}}

${e}^{\frac{-2 \pi i D k}{N}}X \left[ k \right] = \sum_{k = 0}^{N - 1} x \left[ n - D \right] {e}^{\frac{2 \pi i n k}{N}}{e}^{\frac{-2 \pi i D k}{N}}$

Ngomong-ngomong, tidak ada yang menghentikan Anda dari mengambil FFT dari sinyal non-periodik, tetapi ada sedikit penggunaan praktis jika tidak ada transformasi yang bekerja.

FreedomToWin
sumber

Mengapa DFT Menganggap Sinyal Transformasi Berkala?

Jawaban: