Đồng nghĩa từKhoái tốc phó lập diệp biến hoán( khoái tốc phó lập diệp biến hoán ) nhất bàn chỉ FFT nguyên lý
FFT thị nhất chủng DFT đích cao hiệu toán pháp, xưng vi khoái tốc phó lí diệp biến hoán ( fast Fourier transform ).Phó lí diệp biến hoánThị thời vực nhất tần vực biến hoán phân tích trung tối cơ bổn đích phương pháp chi nhất. Tại sổ tự xử lý lĩnh vực ứng dụng đíchLy tán phó lí diệp biến hoán(DFT: Discrete Fourier Transform) thị hứa đa sổ tự tín hào xử lý phương pháp đích cơ sở[1].
- Trung văn danh
- FFT nguyên lý
- Ngoại văn danh
- fast Fourier transform
- Định nghĩa
- Nhất chủng DFT đích cao hiệu toán pháp
- Lĩnh vực
- Sổ lý khoa học
- Phân loại
- Thời gian trừu thủ pháp hòa tần suất trừu thủ pháp
Mục lục
Do vu kế toán cơ kỹ thuật đích khoái tốc phát triển, tại 70 niên đại trung kỳ, mỹ quốc hòa nhật bổn đích nhất ta điện tử thiết bị xí nghiệp khai thủy thiết kế hòa sinh sản sổ tự thứcPhó lí diệp phân tích nghi,Đãn thị do vuLy tán phó lí diệp biến hoánĐích kế toán lượng giác đại, trực đáo DFT đích khoái tốc toán pháp (FFT) phát hiện chi hậu, hữu hạn ly tán phó lí diệp biến hoán (DFT) tài chân chính hoạch đắc liễu quảng phiếm đích ứng dụng[2].
FFT thị nhất chủng DFT đích cao hiệu toán pháp, xưng vi khoái tốc phó lí diệp biến hoán ( fast Fourier transform ). FFT toán pháp khả phân vi án thời gian trừu thủ toán pháp hòa án tần suất trừu thủ toán khóa tuần gian pháp, tiên giản yếu giới thiệu FFT đích cơ bổn nguyên lý. Tòng DFT vận toán khai thủy, thuyết minh FFT đích cơ bổn nguyên lý.
DFT đích vận toán vi đương lâm thi hiệt phóng ương:
Đồ 1Hung nhạc tưởng điệp biện táo thức trung
Do giá chủng phương pháp kế toán DFT đối vu X ( K ) đích mỗi cá K trị, nhu yếu tiến hành 4N thứ thật sổ tương thừa hòa ( 4N-2 ) thứ tương gia, đối vu N cá k trị, cộng nhu N liêu khóa cố *N thừa hòa N ( 4N-2 ) thứ thật sổ tương gia. Cải tiến DFT toán pháp, giảm tiểu tha đích vận toán lượng, lợi dụng DFT trung
FFT cơ bổn thượng khả phân vi lưỡng loại, thời gian trừu thủ pháp hòa tần suất trừu thủ pháp, nhi nhất bàn đích thời gian trừu thủ pháp hòa tần suất trừu thủ pháp chỉ năng xử lý trường độ N=2MĐích tình huống, lánh ngoại hoàn hữu tổ hợp sổ cơ tứ FFT lai xử lý nhất bàn trường độ đích FFT.
Sở vị trừu tuyển, tựu thị bả trường tự liệt phân vi đoản tự liệt đích quá trình, khả tại thời vực dã khả tại tần vực tiến hành. Tối thường dụng đích thời vực trừu tuyển phương pháp thị án kỳ ngẫu tương trường tự liệt bất đoạn địa biến vi đoản tự liệt, kết quả sử thâu nhập tự liệt vi đảo tự, thâu xuất tự liệt vi thuận tự bài liệt, giá tựu thị Coolly—Tukey toán pháp[3].
Thời gian trừu thủ
Thiết N điểm tự liệt x(n),
Đồ 2Cải tả vi:
Đồ 3Nhất cá N điểm DFT phân giải vi lưỡng cá N/2 điểm đích DFT,
Đồ 4
Đồ 5Kỳ toán pháp hữu như hạ quy luật:
Lưỡng cá 4 điểm tổ thành đích 8 điểm DFT:
Điệp hình toán phápTứ cá 2 điểm tổ thành đích 8 điểm DFT:
Án thời gian trừu thủ đích 8 điểm DFT:
Nguyên vị kế toán
Đương sổ cư thâu nhập đáo tồn trữ khí trung dĩ hậu, mỗi nhất cấp vận toán đích kết quả nhưng nhiên trữ tồn tại đồng nhất tổ tồn trữ khí trung, trực đáo tối hậu thâu xuất, trung gian vô nhu kỳ tha tồn trữ khí.
Tự sổ trọng bài
Đối án thời gian trừu thủ FFT đích nguyên vị vận toán kết cấu, đương vận toán hoàn tất thời, giá chủng kết cấu tồn trữ đan nguyên A(1), A(2),…, A(8) trung chính hảo thuận tự tồn phóng trứ X(0), X(1), X(2),…, X(7), nhân thử khả trực tiếp án thuận tự thâu xuất, đãn giá chủng nguyên vị vận toán đích thâu nhập x(n) khước bất năng án giá chủng tự nhiên thuận tự tồn nhập tồn trữ đan nguyên trung, nhi thị án X(0), X(4), X(2), X(6),…, X(7) đích thuận tự tồn nhập tồn trữ đan nguyên, giá chủng thuận tự khán khởi lai tương đương tạp loạn, nhiên nhi tha dã thị hữu quy luật đích. Đương dụng nhị tiến chế biểu kỳ giá cá thuận tự thời, tha chính hảo thị “Mã vị đảo trí” đích thuận tự.
Điệp hình loại hình tùy điệt đại thứ sổ thành bội tăng gia.
Mỗi thứ điệt đại đích điệp hình loại hình bỉ thượng nhất thứ điệp đại tăng gia nhất bội, sổ cư điểm gian cách dã tăng đại nhất bội.
Tần suất trừu thủ
Tần suất trừu thủ 2FFT toán pháp thị án tần suất tiến hành trừu thủ đích toán pháp.
Thiết N=2M,Tương x(n) án tiền hậu lưỡng bộ phân tiến hành phân giải,
DFT biến hoán công thứcÁn K đích kỳ ngẫu phân vi lưỡng tổ, tức
FFT nguyên lýĐắc đáo lưỡng cá N/2 điểm đích DFT vận toán. Như thử phân giải, tịnhĐiệt đại,Tổng đích kế toán lượng hòa thời gian trừu thủ ( DIT ) cơ 2FFT toán pháp tương đồng.
Toán pháp quy luật như hạ:
Điệp hình kết cấu hòa thời gian trừu thủ bất nhất dạng đãn thị điệp hình cá sổ nhất dạng, đồng dạng cụ hữu nguyên vị kế toán quy luật, kỳ điệt đại thứ sổ thành bội giảm tiểu.
Tổ hợp sổ cơ tứ FFT
N≠2MThời, khả thải thủ bổ linh sử kỳ thành vi N=2, hoặc giả tiên phân giải vi lưỡng cá p, q đích tự liệt, kỳ trung p*q=N, nhiên hậu tiến hành kế toán.
Chirp-z biến hoán
Tiền diện giới thiệu, thải dụng FFT toán pháp khả dĩ ngận khoái toán xuất toàn bộ N điểm DFT trị, tức z biến hoán X ( z ) tại z bình diện đan vị viên thượng đích toàn bộ đẳng gian cách thủ dạng trị. Thật tế trung dã hứa ① bất nhu yếu kế toán chỉnh cá đan vị viên thượng z biến hoán đích thủ dạng, như đối vu trách đái tín hào, chỉ nhu yếu đối tín hào sở tại đích nhất đoạn tần đái tiến hành phân tích, giá thời hi vọng tần phổ đích thải dạng tập trung tại giá nhất tần đái nội, dĩ hoạch đắc giác cao đích phân biện suất, nhi tần đái dĩ ngoại đích bộ phân khả bất khảo lự, ② hoặc giả đối kỳ tha vi tuyến thượng đích z biến hoán thủ dạng cảm hưng thú, lệ như ngữ âm tín hào xử lý trung, nhu yếu tri đạo z biến hoán đích cực điểm sở tại tần suất, như cực điểm vị trí ly đan vị viên giác viễn, tắc kỳ đan vị viên thượng đích tần phổ tựu ngận bình hoạt, giá thời ngận nan tòng trung thức biệt xuất cực điểm sở tại đích tần suất, như quả thải dạng bất thị duyên đan vị viên nhi thị duyên nhất điều tiếp cận giá ta cực điểm đích hồ tuyến tiến hành, tắc tại cực điểm sở tại tần suất thượng đích tần phổ tương xuất hiện minh hiển đích tiêm phong, do thử khả giác chuẩn xác địa trắc định cực điểm tần suất. ③ hoặc giả yếu cầu năng hữu hiệu địa kế toán đương N thị tố sổ thời tự liệt đích DFT, nhân thử đề cao DFT kế toán đích linh hoạt tính phi thường hữu ý nghĩa.
Loa toàn tuyến thải dạng thị nhất chủng thích hợp vu giá chủng nhu yếu đích biến hoán, thả khả dĩ thải dụng FFT lai khoái tốc kế toán, giá chủng biến hoán dã xưng tác Chirp-z biến hoán.
FFT kế toán IDFT
DFT biến hoán tắc thuyết minh đối vu thời gian hữu hạn đích tín hào ( hữu hạn trường tự liệt ), dã khả dĩ đối kỳ tiến hành tần vực thải dạng, nhi bất đâu thất nhậm hà tín tức. Sở dĩ chỉ yếu thời gian tự liệt túc cú trường, thải dạng túc cú mật, tần vực thải dạng dã tựu khả giác hảo địa phản ánh tín hào đích tần phổ xu thế, sở dĩ FFT khả dĩ dụng dĩ tiến hành liên tục tín hào đích tần phổ phân tích.
Đương nhiên, giá lí tác liễu kỉ thứ cận tự xử lý:
1, dụng ly tán thải dạng tín hào đích phó lí diệp biến hoán lai đại thế liên tục tín hào đích tần phổ, chỉ hữu tại nghiêm cách mãn túc thải dạng định lý đích tiền đề hạ, tần phổ tài bất hội hữu cơ biến, phủ tắc chỉ thị cận tự;
2, dụng hữu hạn trường tự liệt lai đại thế vô hạn trường ly tán thải dạng tín hào.
FFT kế toán tuyến tính quyển tích
Tuyến tính quyển tích thị cầu ly tán hệ thống hưởng ứng đích chủ yếu phương pháp chi nhất, hứa đa trọng yếu ứng dụng đô kiến lập tại giá nhất lý luận cơ sở thượng, như quyển tích lự ba đẳng.
Dĩ tiền tằng thảo luận liễu dụng viên chu quyển tích kế toán tuyến tính quyển tích đích phương pháp quy nạp như hạ:
Tương trường vi N2Đích tự liệt x(n) diên trường đáo L, bổ L-N2Cá linh
Tương trường vi N1Đích tự liệt h(n) diên trường đáo L, bổ L-N1Cá linh
Như quả L≥N1+N2-1, tắc viên chu quyển tích dữ tuyến tính quyển tích tương đẳng, thử thời, khả hữu FFT kế toán tuyến tính quyển tích, phương pháp như hạ:
a. Kế toán X(k)=FFT[x(n)]
b. Cầu H(k)=FFT[h(n)]
c. Cầu Y(k)=H(k)Y(k) k=0～L-1
d. Cầu y(n)=IFFT[Y(k)] n=0～L-1
Khả kiến, chỉ yếu tiến hành nhị thứ FFT, nhất thứ IFFT tựu khả hoàn thành tuyến tính quyển tích kế toán. Kế toán biểu minh,L>32 thời, thượng thuật kế toán tuyến tính quyển tích đích phương pháp bỉ trực tiếp kế toán tuyến quyển tích hữu minh hiển đích ưu việt tính, nhân thử, dã xưng thượng thuật viên chu quyển tích phương pháp viKhoái tốc quyển tích pháp
FFT kế toán tương quan hàm sổ
Hỗ tương quan hòaTự tương quan hàm sổĐích kế toán khả lợi dụng FFT thật hiện. Do vu ly tán phó lí diệp biến hoán ẩn hàm trứ chu kỳ tính, sở dĩ dụng FFT kế toán ly tán tương quan hàm sổ dã thị đối chu kỳ tự liệt nhi ngôn đích. Trực tiếp tố N điểm FFT tương đương vu đối lưỡng cá N điểm tự liệt x(n), y(n) tác chu kỳ diên thác, tác tương quan hậu tái thủ chủ trị ( loại tự viên chu quyển tích ). Nhi thật tế nhất bàn yếu cầu đích thị lưỡng cá hữu hạn trường tự liệt đích tuyến tính tương quan, vi tị miễn hỗn hào, nhu thải dụng dữ viên chu quyển tích cầu tuyến tính quyển tích tương loại tự đích phương pháp, tiên tương tự liệt diên trường bổ 0 hậu tái dụng thượng thuật phương pháp.
Thật sổ tự liệt FFT
Tín hào thị thật sổ tự liệt, nhậm hà thật sổ đô khả khán thành hư bộ vi linh đích phục sổ, lệ như, cầu mỗ thật tín hào y(n) đích phục phổ, khả nhận vi thị tương thật tín hào gia thượng sổ trị vi linh đích hư bộ biến thành phục tín hào (x(n)+j0), tái dụng FFT cầu kỳ ly tán phó lí diệp biến hoán. Giá chủng tác pháp ngận bất kinh tế, nhân vi bả thật tự liệt biến thành phục tự liệt, tồn trữ khí yếu tăng gia nhất bội, thả kế toán cơ vận hành thời, tức sử hư bộ vi linh, dã yếu tiến hành thiệp cập hư bộ đích vận toán, lãng phí liễu vận toán lượng. Hợp lý đích giải quyết phương pháp thị lợi dụng phục sổ cư FFT đối thật sổ cư tiến hành hữu hiệu kế toán, hạ diện giới thiệu phương pháp.
Nhất cá N điểm FFT đồng thời kế toán lưỡng cá N điểm thật tự liệt đích DFT
Thiết x1(n), x2(n) thị bỉ thử độc lập đích lưỡng cá N điểm thật tự liệt, thả X1(k)=DFT[x1(n)], X2(k)=DFT[x2(n)]
Khả thông quá nhất thứ FFT vận toán đồng thời hoạch đắc X1(k), X2(k). Toán pháp như hạ:
Thủ tiên tương x1(n), x2(n) phân biệt đương tác nhất phục tự liệt đích thật bộ cập hư bộ, lệnh
x(n)=x1(n)+jx2(n)
Thông quá FFT vận toán khả hoạch đắc x(n) đích DFT trị X(k)=DFT[x1(n)]+jDFT[x2(n)]=X1(k)+jX2(k)
Lợi dụng ly tán phó lí diệp biến hoán đích cộng ách đối xưng tính
X1(K)=1/2*[X(k)+[X(N-k) cộng ách ]]
X2(K)=1/2*[X(k)-[X(N-k) cộng ách ]]
Hữu liễu x(n) đích FFT vận toán kết quả X(k), do thượng thức tức khả đắc đáo X1(k),X2(k) đích trị.
