User Tools

Site Tools


3485--bi-n-i-fourier-nhanhla-gi

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

3485--bi-n-i-fourier-nhanhla-gi [2018/11/07 17:09] (current)
Line 1: Line 1:
 +<​HTML><​br><​div id="​mw-content-text"​ lang="​vi"​ dir="​ltr"><​div class="​mw-parser-output"><​p>​Một <​b>​biến đổi Fourier nhanh (FFT)</​b>​ là một thuật toán hiệu quả để tính biến đổi Fourier rời rạc (DFT) và biến đổi ngược. Có nhiều thuật toán FFT khác nhau sử dụng kiến thức từ nhiều mảng khác nhau của toán học, từ số phức tới lý thuyết nhóm và lý thuyết số. Bài này chỉ giới thiệu tổng quan các kĩ thuật và một số tính chất tổng quát. Các thuật toán cụ thể được mô tả chi tiết hơn trong các bài khác được liên kết ở dưới.
 +</​p><​p>​Phép biến đổi DFT phân tích một dãy các số thành các thành phần ở các tần số khác nhau. Nó được sử dụng trong nhiều lĩnh vực khác nhau (xem các tính chất và ứng dụng ở biến đổi Fourier rời rạc) nhưng tính toán trực tiếp từ định nghĩa thường quá chậm trong thực tế. FFT là một cách để đạt được cùng kết quả đó nhưng nhanh hơn nhiều: tính DFT của <​i>​N</​i>​ điểm trực tiếp theo định nghĩa đòi hỏi O(<​i>​N<​sup>​2</​sup></​i>​) phép tính, trong khi FFT tính ra cùng kết quả đó trong O(<​i>​N</​i>​ log <​i>​N</​i>​) phép tính.
 +</p>
  
 +
 +
 +<​p>​Giả sử <​i>​x<​sub>​0</​sub>,​ x<​sub>​1</​sub>,​...,​ x<​sub>​n</​sub></​i>​ là các số phức. DFT được định nghĩa bởi công thức sau:
 +</p>
 +<​dl><​dd><​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle X_{k}=sum _{n=0}^{N-1}x_{n}e^{-{i2pi k{frac {n}{N}}}}qquad k=0,dots ,​N-1.}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​msub><​mi>​X</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mi>​k</​mi></​mrow></​msub><​mo>​=</​mo><​munderover><​mo>​∑<​!-- &sum; --></​mo><​mrow class="​MJX-TeXAtom-ORD"><​mi>​n</​mi><​mo>​=</​mo><​mn>​0</​mn></​mrow><​mrow class="​MJX-TeXAtom-ORD"><​mi>​N</​mi><​mo>​−<​!-- &minus; --></​mo><​mn>​1</​mn></​mrow></​munderover><​msub><​mi>​x</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mi>​n</​mi></​mrow></​msub><​msup><​mi>​e</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mo>​−<​!-- &minus; --></​mo><​mrow class="​MJX-TeXAtom-ORD"><​mi>​i</​mi><​mn>​2</​mn><​mi>​π<​!-- &pi; --></​mi><​mi>​k</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mfrac><​mi>​n</​mi><​mi>​N</​mi></​mfrac></​mrow></​mrow></​mrow></​msup><​mspace width="​2em"/><​mi>​k</​mi><​mo>​=</​mo><​mn>​0</​mn><​mo>,</​mo><​mo>​…<​!-- &​hellip;​ --></​mo><​mo>,</​mo><​mi>​N</​mi><​mo>​−<​!-- &minus; --></​mo><​mn>​1.</​mn></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle X_{k}=sum _{n=0}^{N-1}x_{n}e^{-{i2pi k{frac {n}{N}}}}qquad k=0,dots ,​N-1.}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​02a7699d274d226871209491c8a05976d6e46cf3"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -3.005ex; width:​42.418ex;​ height:​7.343ex;"​ alt="​{displaystyle X_{k}=sum _{n=0}^{N-1}x_{n}e^{-{i2pi k{frac {n}{N}}}}qquad k=0,dots ,​N-1.}"/></​span></​dd></​dl><​p>​Tính trực tiếp từ định nghĩa trên đòi hỏi O(<​i>​N<​sup>​2</​sup></​i>​) phép tính: có <​i>​N</​i>​ số <​i>​X<​sub>​k</​sub></​i>​ cần tính, để tính mỗi số cần tính một tổng <​i>​N</​i>​ số hạng. Một FFT là một phương pháp để tính cùng kết quả đó trong O(<​i>​N</​i>​ log <​i>​N</​i>​) phép tính.
 +</p>
 +
 +<​h3><​span id="​Thu.E1.BA.ADt_to.C3.A1n_Cooley.E2.80.93Tukey"/><​span class="​mw-headline"​ id="​Thuật_toán_Cooley–Tukey">​Thuật toán Cooley–Tukey</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​sửa<​span class="​mw-editsection-divider">​ | </​span>​sửa mã nguồn<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +<​dl><​dd/></​dl><​p>​Thuật toán FFT phổ biến nhất là thuật toán FFT Cooley-Tukey<​sup id="​cite_ref-1"​ class="​reference">​[1]</​sup>​. Đây là một thuật toán chia để trị dùng đệ quy để chia bài toán tính DFT có kích thước hợp số <​i>​N=N<​sub>​1</​sub>​N<​sub>​2</​sub></​i>,​ thành nhiều bài toán tính DFT nhỏ hơn có kích thước <​i>​N<​sub>​1</​sub></​i>​ và <​i>​N<​sub>​2</​sub></​i>,​ cùng với O(<​i>​N</​i>​) phép nhân với căn của đơn vị, thường được gọi là thừa số xoay (theo Gentleman và Sande, 1966)<​sup id="​cite_ref-2"​ class="​reference">​[2]</​sup>​.
 +</p>
 +<div class="​thumb tright"><​div class="​thumbinner"​ style="​width:​302px;"><​img alt=""​ src="​http://​upload.wikimedia.org/​wikipedia/​vi/​thumb/​6/​69/​B%C4%90NF_Cooley-Tukey.svg/​300px-B%C4%90NF_Cooley-Tukey.svg.png"​ width="​300"​ height="​304"​ class="​thumbimage"​ srcset="//​upload.wikimedia.org/​wikipedia/​vi/​thumb/​6/​69/​B%C4%90NF_Cooley-Tukey.svg/​450px-B%C4%90NF_Cooley-Tukey.svg.png 1.5x, //​upload.wikimedia.org/​wikipedia/​vi/​thumb/​6/​69/​B%C4%90NF_Cooley-Tukey.svg/​600px-B%C4%90NF_Cooley-Tukey.svg.png 2x" data-file-width="​790"​ data-file-height="​800"/> ​ <div class="​thumbcaption">​Giải thuật biến đổi Fourier nhanh Cooley-Tukey cho mảng dài 8 phân tử</​div></​div></​div>​
 +<​p>​Phương pháp này (cùng với ý tưởng chung về một FFT) được phổ biến rộng rãi bởi bài báo của J. W. Cooley và J. W. Tukey năm 1965 nhưng sau đó người ta nhận ra rằng hai tác giả đó đã phát hiện lại một cách độc lập thuật toán mà Carl Friedrich Gauss đã tìm ra khoảng năm 1805 (và sau đó được phát hiện lại nhiều lần trong những trường hợp đặc biệt).
 +</​p><​p>​Dạng phổ biến nhất của thuật toán Cooley-Tukey là chia biến đổi thành hai nửa kích thước <​i>​N</​i>​ / 2 ở mỗi bước (vì vậy chỉ dùng được cho kích thước là lũy thừa của 2) nhưng bất kì cách phân tích ra thừa số nào cũng đều có thể dùng được (điều này cả Gauss và Cooley/​Tukey đều nhận ra). Đây là dạng <​b>​cơ số 2</b> và dạng <​b>​nhiều cơ số</​b>​. Mặc dù ý tưởng cơ bản là đệ quy, khi lập trình, người ta thường sắp xếp lại thuật toán để tránh đệ quy. Ngoài ra, do thuật toán Cooley-Tukey chia một DFT thành các DFT nhỏ hơn, có thể phối hợp nó với các thuật toán khác cho DFT, chẳng hạn như những thuật toán mô tả dưới đây.
 +</p>
 +<​h3><​span id="​C.C3.A1c_thu.E1.BA.ADt_to.C3.A1n_FFT_kh.C3.A1c"/><​span class="​mw-headline"​ id="​Các_thuật_toán_FFT_khác">​Các thuật toán FFT khác</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​sửa<​span class="​mw-editsection-divider">​ | </​span>​sửa mã nguồn<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +<​p>​Có nhiều thuật toán FFT khác ngoài Cooley-Tukey. Với <​i>​N=N<​sub>​1</​sub>​N<​sub>​2</​sub></​i>​ và N<​sub>​1</​sub>,​ N<​sub>​2</​sub>​nguyên tố cùng nhau, có thể dùng thuật toán FFT thừa số nguyên tố (thuật toán Good-Thomas),​ dựa trên định lý số dư Trung Hoa, để phân tích DFT tương tự như Cooley-Tukey nhưng không cần thừa số xoay.
 +</p>
 +<​h3><​span id="​Thu.E1.BA.ADt_to.C3.A1n_FFT_cho_s.E1.BB.91_th.E1.BB.B1c_v.C3.A0_d.E1.BB.AF_li.E1.BB.87u_.C4.91.E1.BB.91i_x.E1.BB.A9ng"/><​span class="​mw-headline"​ id="​Thuật_toán_FFT_cho_số_thực_và_dữ_liệu_đối_xứng">​Thuật toán FFT cho số thực và dữ liệu đối xứng</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​sửa<​span class="​mw-editsection-divider">​ | </​span>​sửa mã nguồn<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +<​p>​Trong nhiều ứng dụng, dữ liệu vào cho DFT là số thực. Khi đó kết quả thỏa mãn điều kiện đối xứng sau
 +</p>
 +<​dl><​dd><​span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle X_{N-k}=X_{k}^{*},​}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​msub><​mi>​X</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mi>​N</​mi><​mo>​−<​!-- &minus; --></​mo><​mi>​k</​mi></​mrow></​msub><​mo>​=</​mo><​msubsup><​mi>​X</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mi>​k</​mi></​mrow><​mrow class="​MJX-TeXAtom-ORD"><​mo>​∗<​!-- &​lowast;​ --></​mo></​mrow></​msubsup><​mo>,</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle X_{N-k}=X_{k}^{*},​}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​24d5126f744c96634b9cf48dee3b55093e3fdc5b"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -1.005ex; width:​12.547ex;​ height:​2.843ex;"​ alt="​{displaystyle X_{N-k}=X_{k}^{*},​}"/></​span></​dd></​dl><​p>​và nhiều thuật toán FFT hiệu quả được thiết kế cho trường hợp này. Một phương pháp là lấy một thuật toán thông thường (chẳng hạn Cooley-Tukey) rồi bỏ đi phần tính toán không cần thiết, do đó tiết kiệm khoảng một nửa thời gian và bộ nhớ cần thiết.
 +</p>
 +
 +<​p>​Một bài toán mở quan trọng về mặt lý thuyết là chứng minh chặn dưới cho độ phức tạp tính toán và số phép tính của biến đổi Fourier nhanh. Hiện vẫn chưa có chứng minh nào cho việc DFT có thực sự đòi hỏi Ω(<​i>​N</​i>​ log <​i>​N</​i>​) phép tính, ngay cả trong trường hợp kích thước <​i>​N</​i>​ là lũy thừa của hai, mặc dù không có thuật toán nào có độ phức tạp thấp hơn. Chú ý rằng tuy số phép tính thường là quan tâm chính về mặt lý thuyết, trên thực tế, tốc độ thực thi phụ thuộc nhiều yếu tố khác như các tối ưu hóa cho bộ nhớ đệm và ống lệnh CPU (CPU Pipes).
 +</​p><​p>​Theo công trình của Winograd năm 1978<sup id="​cite_ref-3"​ class="​reference">​[3]</​sup>,​ chặn dưới chặt cho số phép nhân của FFT đã được biết là Θ(<​i>​N</​i>​).
 +</p>
 +
 +
 +
 +
 +<​!-- ​
 +NewPP limit report
 +Parsed by mw1271
 +Cached time: 20181010174629
 +Cache expiry: 1900800
 +Dynamic content: false
 +CPU time usage: 0.096 seconds
 +Real time usage: 0.326 seconds
 +Preprocessor visited node count: 278/1000000
 +Preprocessor generated node count: 0/1500000
 +Post&#​8208;​expand include size: 6505/​2097152 bytes
 +Template argument size: 355/2097152 bytes
 +Highest expansion depth: 6/40
 +Expensive parser function count: 0/500
 +Unstrip recursion depth: 0/20
 +Unstrip post&#​8208;​expand size: 3850/​5000000 bytes
 +Number of Wikibase entities loaded: 0/400
 +Lua time usage: 0.024/​10.000 seconds
 +Lua memory usage: 1.47 MB/50 MB
 +-->
 +<!--
 +Transclusion expansion time report (%,​ms,​calls,​template)
 +100.00% ​  ​86.269 ​     1 -total
 + ​89.20% ​  ​76.953 ​     1 B&#​7843;​n_m&#​7851;​u:​Tham_kh&#​7843;​o
 + ​57.68% ​  ​49.762 ​     2 B&#​7843;​n_m&#​7851;​u:​Ch&​uacute;​_th&​iacute;​ch_t&#​7841;​p_ch&​iacute;​
 +  9.87%    8.516      1 B&#​7843;​n_m&#​7851;​u:​JSTOR
 +  9.86%    8.508      1 B&#​7843;​n_m&#​7851;​u:​Cite_conference
 +  4.09%    3.525      1 B&#​7843;​n_m&#​7851;​u:​Hide_in_print
 +  3.89%    3.353      1 B&#​7843;​n_m&#​7851;​u:​Ch&​iacute;​nh
 +  2.33%    2.012      1 B&#​7843;​n_m&#​7851;​u:​Ch&#​7881;​_khi_in
 +  2.06%    1.781      1 B&#​7843;​n_m&#​7851;​u:​V&#​7845;​n_&#​273;&#​7873;​_m&#​7903;​
 +  0.17%    0.150      1 B&#​7843;​n_m&#​7851;​u:&#​7848;​n_khi_in
 +-->
 +
 +<!-- Saved in parser cache with key viwiki:​pcache:​idhash:​812615-0!canonical!math=5 and timestamp 20181010174629 and revision id 36989770
 + ​-->​
 +</​div><​noscript><​img src="​http://​vi.wikipedia.org/​wiki/​Special:​CentralAutoLogin/​start?​type=1x1"​ alt=""​ title=""​ width="​1"​ height="​1"​ style="​border:​ none; position: absolute;"/></​noscript></​div>​
 +
 +</​HTML>​
3485--bi-n-i-fourier-nhanhla-gi.txt · Last modified: 2018/11/07 17:09 (external edit)