Biến đổi Fourier Rời Rạc (DFT). Biến đổi Fourier Rời Rạc

Nó là thuận tiện để phân tích nhiều tín hiệu bằng cách phân hủy chúng thành hình sin (sóng hài). Cái này có một vài nguyên nhân. Ví dụ, tai người hoạt động theo cách tương tự. Nó phân hủy âm thanh thành các dao động riêng biệt có tần số khác nhau. Ngoài ra, có thể chỉ ra rằng hình sin là "hàm riêng" của hệ tuyến tính (vì chúng đi qua hệ tuyến tính mà không thay đổi hình dạng mà chỉ có thể thay đổi pha và biên độ). Một lý do khác là định lý Kotelnikov được xây dựng dưới dạng phổ tín hiệu.

Phép biến đổi Fourier là sự phân rã các hàm thành dạng sin (sau đây, chúng ta còn gọi hàm cosin là dạng sin, vì chúng khác với dạng sin "thực" chỉ ở pha). Có một số kiểu biến đổi Fourier.

1. Một tín hiệu liên tục không tuần hoàn có thể được khai triển thành một tích phân Fourier.

2. Một tín hiệu liên tục tuần hoàn có thể được khai triển thành một chuỗi Fourier vô hạn.

3. Một tín hiệu rời rạc không tuần hoàn có thể được khai triển thành một tích phân Fourier.

4. Một tín hiệu rời rạc tuần hoàn có thể được khai triển thành một chuỗi Fourier hữu hạn.

Một máy tính chỉ có thể hoạt động với một lượng dữ liệu hạn chế, vì vậy nó chỉ có thể thực sự tính được loại biến đổi Fourier cuối cùng. Chúng ta hãy xem xét nó chi tiết hơn.

DFT phức tạp

Cho đến nay, chúng tôi đã xem xét DFT từ các tín hiệu thực. Bây giờ chúng ta tổng quát DFT cho trường hợp của các tín hiệu phức tạp. Gọi x [n], n = 0,…, N-1 là tín hiệu phức ban đầu gồm N số phức. Kí hiệu X [k], k = 0,… N-1 - phổ phức của nó, cũng bao gồm N số phức. Khi đó, các công thức sau cho phép biến đổi Fourier trực tiếp và nghịch đảo là hợp lệ:

Nếu một tín hiệu thực được phân tách thành phổ bằng cách sử dụng các công thức này, thì hệ số phức N / 2 + 1 đầu tiên của phổ sẽ trùng với phổ của DFT thực "thông thường", được trình bày ở dạng "phức", và phần còn lại hệ số sẽ là phản xạ đối xứng của chúng đối với một nửa tần số lấy mẫu. Đối với hệ số cosin thì phản xạ là chẵn và đối với hệ số sin thì phản xạ là lẻ.

2D DFT

Đối với hình ảnh là tín hiệu hai chiều, phổ cũng là tín hiệu hai chiều. Các hàm cơ bản của phép biến đổi Fourier có dạng:

và các giai đoạn cũng có thể khác nhau. Trong hình ảnh, mỗi hàm cơ sở này đại diện cho một sóng có tần số nhất định, một định hướng nhất định và một pha nhất định.

Ở đây N 1 xN 2 là kích thước của tín hiệu gốc, nó cũng là kích thước của phổ. k 1 và k 2 là số của các hàm cơ sở (số của hệ số DFT hai chiều mà các hàm này được tìm thấy). Vì kích thước của phổ bằng kích thước của tín hiệu gốc nên k 1 = 0,…, N 1 -1; k 2 = 0,…, N 2 -1.

n 1 và n 2 - đối số biến của hàm cơ sở. Vì miền xác định của các hàm cơ sở trùng với miền xác định của tín hiệu nên n 1 = 0,…, N 1 -1; n 2 \ u003d 0, ..., N 2 -1.

DFT hai chiều (ở dạng phức hợp) được xác định bằng các công thức sau (ở đây x là tín hiệu gốc và X là phổ của nó):

Việc tính toán trực tiếp DFT hai chiều bằng các công thức trên đòi hỏi chi phí tính toán rất lớn. Tuy nhiên, có thể chứng minh rằng DFT hai chiều có thuộc tính phân tách, tức là nó có thể được tính toán tuần tự trên hai chiều.

Để tính DFT 2D, chỉ cần tính DFT phức hợp 1D của tất cả các hàng trong hình ảnh, sau đó tính DFT phức hợp 1D của tất cả các cột trong "hình ảnh" kết quả.

Trong trường hợp này, kết quả của tất cả các DFT phức tạp một chiều phải được viết thay cho dữ liệu ban đầu cho các DFT này. Ví dụ, khi tính toán DFT một chiều của dòng đầu tiên của hình ảnh, bạn cần ghi kết quả của DFT vào dòng đầu tiên của hình ảnh này (nó có cùng kích thước). Để làm điều này, bạn cần lưu trữ mỗi "pixel" dưới dạng một số phức.

Do đó, một thuật toán hiệu quả để tính DFT của một hình ảnh là tính toán FFT một chiều trước tiên từ tất cả các hàng, sau đó từ tất cả các cột của hình ảnh.

Trong kỹ thuật vô tuyến, khái niệm tích chập của hai tín hiệu thường được sử dụng. Vì vậy, ví dụ, tín hiệu ở đầu ra của một tứ cực có thể được tìm thấy bằng cách sử dụng tích chập của tín hiệu đầu vào và đáp ứng xung của tứ cực. Vì các tín hiệu kỹ thuật số và rời rạc đã được xem xét, chúng tôi xác định khái niệm chập cho các tín hiệu rời rạc, hoặc tích chập rời rạc.

Để có một tín hiệu rời rạc x D (t), bao gồm N bài đọc x k và một tín hiệu rời rạc y q (r), bao gồm N bài đọc tại k, sau đó tích chập rời rạc hai tín hiệu này được gọi là tín hiệu z A (t), mà

Tín hiệu rời rạc được sử dụng rộng rãi trong việc tạo ra các hệ thống có điều chế xung.

Thiết bị lấy mẫu trong trường hợp đơn giản nhất là một tầng (khóa) có định hướng mở trong một thời gian t và với chu kỳ A (Hình 4.7).

Cơm. 4.

Khoảng thời gian lấy mẫu A có thể không đổi (lấy mẫu đồng nhất) hoặc thay đổi (lấy mẫu thích ứng). Dạng tùy biến phổ biến nhất là đồng nhất, dựa trên định lý Kotelnikov.

Bộ điều chế xung -đây là thiết bị có hai đầu vào, một đầu vào được cung cấp tín hiệu tương tự và đầu vào thứ hai nhận các xung đồng bộ hóa ngắn với chu kỳ lặp lại A. Đồng thời, tại thời điểm xung đồng bộ đến, giá trị tức thời của tín hiệu ls (r) được đo. Tại đầu ra của bộ điều chế, một chuỗi các xung xuất hiện, mỗi xung có diện tích tỷ lệ với giá trị tham chiếu tương ứng của tín hiệu tương tự (Hình 4.7).

Tín hiệu Hmpn ( t) ở đầu ra của bộ điều chế xung được gọi là tàu xung điều chế(MIP). Về mặt toán học, MIP được viết là

một Mật độ quang phổ MIPđược biểu thị bằng mật độ phổ của tín hiệu tương tự như sau:

Mô hình tín hiệu rời rạc giả định rằng các giá trị tham chiếu của tín hiệu tương tự có thể thu được tại một số điểm không giới hạn trên trục thời gian. Trong thực tế, quá trình xử lý luôn được thực hiện trong một khoảng thời gian hữu hạn.

Xem xét các đặc điểm của biểu diễn quang phổ của một tín hiệu rời rạc được đưa ra trên khoảng thời gian bởi các mẫu của nó x 0, x x, ..., x N _ x. Tổng số lần đọc N - T/ NHƯNG.

Kỹ thuật để nghiên cứu các tín hiệu rời rạc như vậy là mẫu kết quả của các giá trị tham chiếu được lặp lại một cách tinh thần với số lần vô hạn. Kết quả là, tín hiệu trở nên tuần hoàn (Hình 4.8).

Bằng cách so sánh một tín hiệu như vậy với một mô hình toán học, người ta có thể sử dụng sự mở rộng trong một chuỗi Fourier và tìm các hệ số biên độ tương ứng. Sự kết hợp của các hệ số này tạo thành phổ của một tín hiệu tuần hoàn rời rạc.

Cơm. 4.8.

Chúng tôi viết mô hình của một tín hiệu tuần hoàn giới hạn dưới dạng một chuỗi các xung delta:

Hãy để chúng tôi mở rộng tín hiệu Xmip (0 trong chuỗi Fourier:

Đây có phải là một sự thay đổi của các biến? = f / A. Cuối cùng, chúng tôi thu được

Công thức này xác định chuỗi các hệ số tạo thành biến đổi Fourier rời rạc (DFT) của tín hiệu được xem xét.

DFT có các thuộc tính sau:

1. DFT là một phép biến đổi tuyến tính, tức là nếu z k = a x k + /? tại k, sau đó

C "Z P ~ ^ C X p R Su p .

2. Số lượng các hệ số khác nhau Cq, Ci, ..., C n _i bằng số N số đếm cho khoảng thời gian, với N = N hệ số C N= C 0.

3. С 0 là giá trị trung bình của tất cả các lần đọc С 0 = - ^ xđến.

N đến= o

• 4. Nếu N là số chẵn thì C N \ u003d - ^ (-1) k x k.
• 7 ^? = O
• 5. Nếu đếm x k- số thực và N là một số chẵn, sau đó C N = C * N, / = 0; L / 7 2 -1.
• - + tôi - -tôi
• 6. Nếu yk = xk + m, m = l; JV-l, TO C, t = C, * e ~ j2rrkm, N.
• 2tf-l
• 7. Nếu zk= -> T0 C z k = C X k C y k

iy / i=0

DFT được sử dụng để tính toán phổ của các hàm được cho trong bảng hoặc đồ thị, xử lý dữ liệu thực nghiệm, tìm tín hiệu ở đầu ra của bộ lọc rời rạc, v.v.

Nếu dựa trên các bài đọc x 0, x l, ..., x N _ l một số tín hiệu, hệ số DFT được tìm thấy C 0, Ci, ... 9 C n / 2, khi đó có thể khôi phục tín hiệu tương tự với phổ hạn chế x (t). Chuỗi Fourier của một tín hiệu như vậy có dạng (đối với N)

ở đâu | Q | - môđun của các hệ số DFT; = arg - góc pha (đối số)

Hệ số DFT. Tần số sóng hài đầu tiên: f = -/ in = - = - / i- lẻ N số hạng cuối cùng trong công thức (4.17) bằng:

Để tính toán các mẫu rời rạc x k theo các hệ số DFT có sẵn, có công thức sau:

Công thức này được gọi là biến đổi Fourier rời rạc nghịch đảo (ODFT).

Mã chương trình cho phép biến đổi Fourier trực tiếp và nghịch đảo được đưa ra. Phép biến đổi Fourier nhanh được coi là.

Biến đổi Fourier rời rạc (DFT) là một công cụ phân tích mạnh mẽ được sử dụng rộng rãi trong lĩnh vực xử lý tín hiệu kỹ thuật số (DSP). Có các phép biến đổi Fourier thuận và nghịch. Biến đổi Fourier rời rạc trực tiếp chuyển tín hiệu từ miền thời gian sang miền tần số và được sử dụng để phân tích phổ tần số của tín hiệu. Phép biến đổi nghịch đảo thực hiện hoàn toàn ngược lại: nó khôi phục tín hiệu trong miền thời gian từ phổ tần số của tín hiệu.

Để tính toán biến đổi Fourier, một quy trình tính toán gia tốc thường được sử dụng - cái gọi là. biến đổi Fourier nhanh (FFT). Điều này cho phép bạn giảm đáng kể thời gian xử lý cho các phép tính toán học khá phức tạp và tốn nhiều tài nguyên.

1 Tổ hợp con số

Để bắt đầu, chúng ta cần một lớp bổ trợ sẽ mô tả các số phức. Số phức là một loại số đặc biệt trong toán học. Mọi số phức đều có hai phần - thực và ảo. Bây giờ chúng ta đã đủ biết về số phức liên quan đến DFT rằng phần thực của số phức lưu trữ thông tin về biên độ của tín hiệu và phần ảo - về pha.

Mã lớp để mô tả số phức(mở ra) "" " """ Số phức. """ Public Class ComplexNumber "" " "" "Phần thực của số phức." "" Public Real As Double = 0 "" " "" "Phần ảo của một số phức." "" Public Imaginary As Double = 0 Public Sub Mới () Real = 0 Imaginary = 0 End Sub "" " "" "Tạo một số phức." "" """ Phần thực của một số phức. """ Phần ảo của một số phức. Public Sub New (ByVal r As Double, Tùy chọn ByVal im As Double = 0) Real = r Imaginary = im End Sub Private usCult As New Globalization.CultureInfo ("en-US") các phần phân số được phân tách bằng dấu chấm, không phải dấu phẩy "" " "" "Trả về một chuỗi bao gồm phần thực và phần ảo được phân tách bằng ký tự tab." "" Chức năng ghi đè công khai ToString () Như chuỗi trả về (Real.ToString (usCult) & ControlChars.Tab & Imaginary.ToString (usCult)) Lớp kết thúc chức năng kết thúc

2 trực tiếp rời rạc nhanh chóng Biến đổi Fourier

Một mảng các số phức được chuyển đến đầu vào của hàm. Phần thực của nó đại diện cho một tín hiệu rời rạc tùy ý, với các số đọc trong khoảng thời gian đều đặn. Phần ảo chứa các số không. Số lượng mẫu trong tín hiệu phải là lũy thừa của hai. Nếu tín hiệu của bạn ngắn hơn, hãy đệm nó bằng các số không thành bội số của 2: 256, 512, 1024, v.v. Tín hiệu càng dài thì độ phân giải tần số của phổ tính toán càng cao.

Mã chuyển đổi Fourier nhanh trực tiếp VB.NET(mở ra) "" " "" "Tính toán phổ của tín hiệu bằng phương pháp biến đổi Fourier nhanh. Chỉ sử dụng (N / 2 + 1) giá trị trả về (lên đến một nửa tốc độ mẫu)." "" """ Tín hiệu chứa một số mẫu là bội số của hai và bao gồm phần thực và phần ảo. Tất cả các phần ảo của tín hiệu đều được lấp đầy bởi các số không. """ Trả về một mảng các số phức phổ. "" "Chỉ N / 2 + 1 đầu tiên là đáng kể, còn lại là phần đối xứng tương ứng với tần số âm." "" Giá trị đầu tiên của phổ là thành phần không đổi, giá trị cuối cùng tương ứng với một nửa tần số lấy mẫu (Nyquist tần số). "" "Giá trị trên một nửa tỷ lệ mẫu - không sử dụng." "" Hàm chia sẻ công khai FFT (Tín hiệu ByVal Như Số Phức ()) Như Số Phức () Thứ tự Dim As Integer = signal.Length "DFT order CheckFftOrder (order)" Kiểm tra xem thứ tự đó có phải là lũy thừa của hai Phổ Dim hay khôngLen As Integer = order \ 2 Dim j As Integer = spectreLen "Sắp xếp ngược bit: For i As Integer = 1 To order - 2 If (i< j) Then Dim tmpRe As Double = signal(j).Real Dim tmpIm As Double = signal(j).Imaginary signal(j).Real = signal(i).Real signal(j).Imaginary = signal(i).Imaginary signal(i).Real = tmpRe signal(i).Imaginary = tmpIm End If Dim k As Integer = spectrumLen Do Until (k >j) j - = k k \ = 2 Vòng lặp j + = k Tiếp theo "Vòng lặp qua các mức phân rã: Đối với mức As Integer = 1 To CInt (Math.Log (order) / Math.Log (2)) Dim lvl As Integer = CInt (2 ^ cấp) Dim lvl2 As Integer = lvl \ 2 Dim tmp As Double = Math.PI / lvl2 Dim sr As Double = Math.Cos (tmp) Dim si As Double = -Math.Sin (tmp) Dim tr As Double = 0 Dim ur As Double = 1 Dim ui As Double = 0 For jj As Integer = 1 To lv2 "Chu kỳ qua phổ trong mức Cho i As Integer = (jj - 1) Tới (thứ tự - 1) Bước lvl" Chu kỳ qua từng con bướm Dim ip As Integer = i + lvl2 tr = signal (ip) .Real * ur - signal (ip) .Imaginary * ui "Hoạt động của bướm" Dim ti As Double = signal (ip) .Real * ui + signal (ip ) .Imaginary * ur signal (ip) .Real = signal (i) .Real - tr signal (ip) .Imaginary = signal (i) .Imaginary - ti signal (i) .Real = signal (i) .Real + tr signal (i) .Imaginary = signal (i) .Imaginary + ti Next tr = ur ur = tr * sr - ui * si ui = tr * si + ui * sr Next Next "Điền vào mảng các số phức được FFT xử lý : Phổ mờ (thứ tự - 1) Như Số phức Đối với i Là Số nguyên = 0 Theo thứ tự - 1 Với phổ tín hiệu (i) (i) = Số Phức mới (.Real, .Imaginary) Kết thúc Với Phổ trở lại Tiếp theo Kết thúc Chức năng

3 Đảo ngược nhanh chóng rời rạc Biến đổi Fourier

Biến đổi Fourier rời rạc đảo ngược (IDFT) một trong các bước tính toán bao gồm DFT trực tiếp trên một mảng số phức, trong đó phần ảo là phần nghịch đảo về trục X của phần ảo của phổ.

Mã tính toán biến đổi Fourier nhanh nghịch đảo trong VB.NET(mở ra) "" " "" "Tái tạo lại tín hiệu từ phổ của nó bằng cách sử dụng phép biến đổi Fourier nhanh nghịch đảo." "" """ Phổ tín hiệu chứa số lần đọc, bội số của hai, và bao gồm các phần thực và ảo. Hàm chia sẻ công khai InverseFFT (Phổ ByVal Như Số phức ()) Như Số Phức () Thứ tự mờ Như Số nguyên = Phổ.Length "Thứ tự của DFT nghịch đảo. CheckFftOrder (thứ tự)" Thay đổi dấu số học của các phần tử của phần ảo: Với Như Số nguyên = 0 Đến phổ. Độ dài - 1 phổ (i) .Imaginary = -spectrum (i) .Imaginary Tiếp theo "Tính FFT trực tiếp: Dim directFFT As ComplexNumber () = FFT (phổ)" Chia theo thứ tự trong miền thời gian bằng số học Thay đổi dấu hiệu của phần ảo: Tín hiệu Dim (directFFT.Length - 1) As ComplexNumber For i As Integer = 0 To directFFT.Length - 1 Dim ReX As Double = directFFT (i) .Real / order Dim ImX As Double = -directFFT ( i) .Imaginary / order signal (i) = New ComplexNumber (ReX, ImX) Tiếp theo Tín hiệu trả về Chức năng Kết thúc

Và tất nhiên, chúng tôi sẽ mô tả phương thức được sử dụng để kiểm tra số phần tử của mảng được truyền:

""" "" "Kiểm tra xem thứ tự của FFT có phải là lũy thừa của hai hay không, và nếu không, hãy ném một ngoại lệ." "" """ Đặt hàng FFT. Private Shared Sub CheckFftOrder (ByVal order As Integer) Dim chk As Double = Math.Abs ​​(Math.Floor (Math.Log (order, 2)) - Math.Log (order, 2)) If (chk> 0,0001) Then Throw ArgumentException mới (String.Format ("Độ dài của mảng ((0)) không phải là bội số của lũy thừa hai.", Order)) End If End Sub

4 Kiểm tra chuyển tiếp và đảo ngược Biến đổi Fourier

Bây giờ hãy kiểm tra xem các chức năng của chúng ta có hoạt động không. Để làm điều này, hãy chuyển một tín hiệu tùy ý thông qua cơ chế của phép biến đổi Fourier trực tiếp, và sau đó "thu thập" nó trở lại bằng cách sử dụng phép biến đổi Fourier ngược. Tín hiệu được tái tạo thực tế phải trùng với tín hiệu ban đầu. Lỗi làm tròn xảy ra khi làm việc với các con số trong máy tính diễn ra, vì vậy các tín hiệu sẽ không hoàn toàn giống hệt nhau, nhưng độ lệch của chúng với nhau sẽ không đáng kể.

Ví dụ: hãy lấy hàm sin làm tín hiệu ban đầu và dữ liệu biểu mẫu có độ dài 128 mẫu như sau:

Dim cn (127) As ComplexNumber For i As Integer = 0 To cn.Length - 1 cn (i) = New ComplexNumber (Math.Sin (i * 3 * Math.PI / 180)) Tiếp theo

Chúng tôi nhận được tín hiệu sau:

Ở đây, dọc theo trục X là số lần đọc trong miền thời gian, dọc theo trục Y là biên độ. Lưu ý rằng tín hiệu chỉ bao gồm các phần thực và phần ảo trên toàn bộ đoạn bằng "0".

Bây giờ hãy chuyển tín hiệu này đến đầu vào của hàm FFT (). Dựa trên các dãy số phức thu được trong quá trình biến đổi Fourier trực tiếp, chúng tôi xây dựng hai đồ thị - phần thực (Re) và phần ảo (Im) của phổ:

Ở đây, dọc theo trục X - số đọc trong miền tần số, dọc theo trục Y - biên độ. Để có được các giá trị tần số thực, cần phải tính toán chúng, coi rằng "0" của trục Y tương ứng với tần số không, cực đại của trục Y tương ứng với tần số lấy mẫu.

Phổ tín hiệu thu được sẽ được chuyển tới hàm của phép biến đổi Fourier nghịch đảo IFFT (). Chúng tôi nhận được một mảng các số phức, trong đó phần thực sẽ chứa tín hiệu được khôi phục:

Như bạn có thể thấy, tín hiệu được khôi phục hoàn toàn lặp lại tín hiệu ban đầu.

Để cho được f(x 1 , x 2) là một hàm của hai biến. Bằng cách tương tự với phép biến đổi Fourier một chiều, chúng ta có thể giới thiệu phép biến đổi Fourier hai chiều:

Hàm tại các giá trị cố định ω 1, ω 2 mô tả một sóng phẳng trong mặt phẳng x 1 , x 2 (Hình 19.1).

Các đại lượng ω 1, ω 2 có ý nghĩa là tần số không gian và thứ nguyên mm−1, và hàm F (ω 1, ω 2) xác định phổ của tần số không gian. Thấu kính hình cầu có khả năng tính toán phổ của tín hiệu quang học (Hình 19.2). Trong Hình 19.2, các ký hiệu sau được giới thiệu: φ - độ dài tiêu cự,

Hình 19.1 - Định nghĩa tần số không gian

Phép biến đổi Fourier hai chiều có tất cả các tính chất của phép biến đổi một chiều, ngoài ra, chúng ta lưu ý thêm hai tính chất nữa, việc chứng minh nó dễ dàng theo định nghĩa của phép biến đổi Fourier hai chiều.

Hình 19.2 - Tính toán phổ của tín hiệu quang sử dụng thấu kính hình cầu

Thừa số. Nếu tín hiệu hai chiều được phân tích nhân tử,

thì phổ của nó cũng được phân tích thành nhân tử:

Đối xứng xuyên tâm. Nếu tín hiệu 2D là đối xứng xuyên tâm, nghĩa là

Hàm Bessel bậc 0 ở đâu. Công thức xác định mối quan hệ giữa tín hiệu hai chiều đối xứng xuyên tâm và phổ không gian của nó được gọi là phép biến đổi Hankel.

BÀI GIẢNG 20. Biến đổi Fourier rời rạc. bộ lọc thông thấp

Phép biến đổi Fourier rời rạc hai chiều trực tiếp (DFT) biến đổi một hình ảnh được cho trong một hệ tọa độ không gian ( x, y), thành một phép biến đổi hình ảnh rời rạc hai chiều được chỉ định trong hệ tọa độ tần số ( u, v):

Biến đổi Fourier rời rạc nghịch đảo (IDFT) có dạng:

Có thể thấy DFT là một phép biến đổi phức tạp. Mô đun của phép biến đổi này biểu thị biên độ của phổ ảnh và được tính bằng căn bậc hai của tổng bình phương của phần thực và phần ảo của DFT. Pha (góc dịch pha) được định nghĩa là tiếp tuyến cung của tỷ số giữa phần ảo của DFT và phần thực. Phổ năng lượng bằng bình phương biên độ của quang phổ, hoặc tổng bình phương của phần ảo và phần thực của quang phổ.

Định lý chuyển đổi

Theo định lý tích chập, tích chập của hai hàm trong miền không gian có thể nhận được bằng ODFT của tích DFT của chúng, tức là

Lọc trong miền tần số cho phép bạn chọn đáp ứng tần số của bộ lọc từ DFT của hình ảnh, cung cấp sự chuyển đổi hình ảnh cần thiết. Xem xét đáp ứng tần số của các bộ lọc phổ biến nhất.

Đây là một trong những phép biến đổi Fourier được sử dụng rộng rãi trong các thuật toán xử lý tín hiệu kỹ thuật số (các biến đổi của nó được sử dụng để nén âm thanh trong MP3, nén hình ảnh trong JPEG, v.v.), cũng như trong các lĩnh vực khác liên quan đến phân tích tần số rời rạc (ví dụ: , tín hiệu số hóa tương tự). Biến đổi Fourier rời rạc yêu cầu một hàm rời rạc làm đầu vào. Các hàm như vậy thường được tạo ra bằng cách lấy mẫu (lấy mẫu giá trị từ các hàm liên tục). Các phép biến đổi Fourier rời rạc giúp giải các phương trình đạo hàm riêng và thực hiện các phép toán như tính chập. Các phép biến đổi Fourier rời rạc cũng được sử dụng tích cực trong thống kê, trong phân tích chuỗi thời gian. Các phép biến đổi là một chiều, hai chiều và thậm chí cả ba chiều.

Chuyển đổi trực tiếp:

Chuyển đổi ngược lại:

Chỉ định:

§ N- số lượng các giá trị tín hiệu được đo trong khoảng thời gian, cũng như số lượng các thành phần phân hủy;

§ - các giá trị tín hiệu đo được (tại các điểm thời gian rời rạc với các con số, là dữ liệu đầu vào để chuyển đổi trực tiếp và dữ liệu đầu ra để chuyển đổi ngược lại;

§ - N biên độ phức tạp của tín hiệu hình sin tạo nên tín hiệu ban đầu; là dữ liệu đầu ra để chuyển đổi trực tiếp và dữ liệu đầu vào để chuyển đổi ngược lại; vì các biên độ là phức tạp, nên cả biên độ và pha có thể được tính toán đồng thời từ chúng;

§ - biên độ thông thường (thực) của tín hiệu hình sin thứ k;

§ arg ( X k) - pha của tín hiệu hình sin thứ k (đối số số phức);

§ k- tần số của tín hiệu thứ k, bằng, trong đó T- khoảng thời gian dữ liệu đầu vào được lấy.

Từ thứ hai có thể thấy rằng sự biến đổi phân hủy tín hiệu thành các thành phần hình sin (được gọi là sóng hài) với tần số từ N dao động trong một chu kỳ đến một dao động trong một chu kỳ. Vì bản thân tần số lấy mẫu bằng N mẫu mỗi chu kỳ, các thành phần tần số cao không thể được hiển thị chính xác - hiệu ứng moiré xảy ra. Điều này dẫn đến thực tế là nửa sau của N biên độ phức tạp, trên thực tế, là hình ảnh phản chiếu của phần đầu và không mang thêm thông tin.

Xem xét một số tín hiệu định kỳ x(t) với chu kỳ bằng T. Chúng ta hãy mở rộng nó thành một chuỗi Fourier:

Hãy để chúng tôi loại bỏ tín hiệu sao cho có N mẫu mỗi chu kỳ. Chúng tôi biểu diễn tín hiệu rời rạc dưới dạng các bài đọc: x n = x(t n), trong đó, những bài đọc này thông qua chuỗi Fourier sẽ được viết như sau:

Sử dụng tỷ lệ:, chúng tôi nhận được:

ở đâu

Vì vậy, chúng tôi có biến đổi Fourier rời rạc nghịch đảo.

Bây giờ chúng ta nhân biểu thức vô hướng cho x n và chúng tôi nhận được:

Ở đây chúng tôi sử dụng: a) một biểu thức cho tổng của một số hạng hữu hạn (số mũ) của một cấp số nhân hình học và b) một biểu thức cho ký hiệu Kronecker làm giới hạn tỷ lệ của hàm Euler đối với số phức. Từ đó nó dẫn đến:

Công thức này mô tả biến đổi Fourier rời rạc trực tiếp.

Trong y văn, người ta thường viết cấp số nhân dưới dạng biến đổi nghịch đảo, do đó các công thức biến đổi thường được viết dưới dạng sau:

Phép biến đổi Fourier rời rạc là một phép biến đổi tuyến tính chuyển một vectơ của mẫu thời gian thành vectơ của các mẫu phổ có cùng độ dài. Vì vậy, phép biến đổi có thể được thực hiện như nhân một ma trận vuông với một vectơ: