มีคัยรู้จัก Fast Fourier Transform มั่งคับ

[WiZz]

ช่วยอธิบายหน่อยคับว่า มันคืออะไรแล้วต่างจาก Fourier Transform ธรรมดายังงัยคับ

แล้วผมอยากรู้ว่า Fourier Transform สัมพันธ์ Laplace Transform ยังงัยคับ
คือผมกำลังเรียนอยู่แต่ว่างงมากๆ ว่ามันมีที่มายังงัยคับ (ช่วยอธิบายละเอียดหน่อยนะคับ)
ขอบคุณมากๆคับ

[M@gpie]

อะไรคือ fast fourier อ่ะ ไม่เคยรู้จัก
ผมเรียนพวกนี้เหมือนกัน แอดเมล์มาคุย msn กันได้คับ

ผมก็รู้ไม่มากนัก อธิบายเท่าที่จำได้นะครับ

การทำ Fourier Transform จะมีชื่อเรียกต่างกันออกไปตามลักษณะของฟังก์ชันครับ กล่าวคือ
1. หากเป็นฟังก์ชันรายคาบแบบต่อเนื่อง (Periodic and Continous) จะมีชื่อเรียกว่า อนุกรมฟูเรียร์ (Fourier Series : FS)
2. หากเป็นฟังก์ชันไม่มีคาบแบบต่อเนื่อง (Non Periodic and Continous) จะมีชื่อเรียกว่า ฟูเรียร์ทรานส์ฟอร์ม (Fourier Transform : FT)
3. หากเป็นฟังก์ชันรายคาบแบบไม่ต่อเนื่อง (Periodic and Discrete) จะมีชื่อเรียกว่า อนุกรมฟูเรียร์ไม่ต่อเนื่อง (Discrete Fourier Series : DFS)
4. หากเป็นฟังก์ชันไม่มีคาบแบบไม่ต่อเนื่อง (Non Periodic and Discrete) จะมีชื่อเรียกว่า ฟูเรียร์ทรานส์ฟอร์มไม่ต่อเนื่อง (Discrete Fourier Transform : DFT)

ฟังก์ชันแบบที่ 3 และ 4 จะใช้ในงาน DSP (Discrete Time Signal Processing) มาก แต่หากคำนวณการแปลงตรงๆจะมีปัญหา เพราะใช้เวลาคำนวณนานมาก และเกิดความผิดพลาดสะสมในการคำนวณมากด้วย จึงมีผู้คิดเทคนิคหลายแบบ ที่ช่วยให้คำนวณได้เร็วขึ้นและมีความผิดพลาดสะสมลดลง เรียกว่า Fast Fourier Transform (FFT)

ผลการแปลง Laplace Transform ไม่มีความหมายทางกายภาพแต่อย่างใด แต่ช่วยวิเคราะห์ผลตอบของระบบเชิงเส้น และแก้สมการดิฟเฟอเรนเชียลได้ โดเมนผลลัพธ์ของ Laplace Transform นั้นกว้างกว่าของ Fourier Transform โดย โดเมนผลลัพธ์ของ Fourier Transform เป็นเพียงแกนจินตภาพของ S Plane ของ Laplace Transform เท่านั้น

หมายเหตุ : Laplace Transform ที่รู้จักกันทั่วไป มีอีกชื่อเรียกหนึ่งว่า ลาปลาสทรานส์ฟอร์มข้างเดียว ยังมีลาปลาสทรานส์ฟอร์มสองข้าง ที่อินทิเกรตจาก ลบอนันต์ไปจนถึงอนันต์ด้วย และหากเราแทน s ในลาปลาสทรานส์ฟอร์มสองข้าง ด้วย jw ก็จะได้การแปลงฟูเรียร์นั่นเอง

Fast Fourier Transform เป็น algorithm การทำ Discrete Fourier Transform ที่ complexity ลดลงครับ
ผมจำไม่ได้ว่าลดจากเท่าไรเป็นเท่าไร (คิดว่าจาก O(n^2) เป็น O(nlogn))
โดยผลลัพธ์การทำ FFT ที่ได้จะตรงกับการทำ DFT ทุกประการนะครับ เพียงแต่เร็วกว่า (ในแง่ของ complexity)
โดย FFT ก็ไม่ได้หมายถึง algorithm ใด algorithm หนึ่งเฉพาะเจาะจงนะครับ มีคนเสนอมาหลายแบบ แต่ก็จะมีแบบหนึ่งที่นิยมใช้กัน (ผมจำไม่ได้อีกแล้วว่าของใคร ขอโทษด้วยครับ)
อย่างไรก็ตาม ก็ยังมี FFT แบบที่ให้คำตอบไม่ตรงเป๊ะด้วยนะ แลกกันกับความเร็วครับ

[gon]

เห็นว่ามีการนำ FFT ไปใช้คำนวณหาค่า p ด้วยครับ

[warut]

ถ้าผมเข้าใจไม่ผิดการใช้ FFT ในการหาค่า p หรือเลขอื่นๆที่มีจำนวนหลักเยอะๆนั้น
มีจุดประสงค์เพื่อเร่งความเร็วในการคูณเป็นสำคัญครับ การคูณเลข n bits 2 ตัวเข้าด้วยกัน
แบบธรรมดา (long multiplication) จะมี complexity เป็น O(n²) แต่ถ้าใช้
FFT multiplication จะลดเหลือเพียง O(nlog(n)loglog(n)) (มั้ง ) ครับ

[chevasit]

ผมเรียนมาทางไฟฟ้า สื่อสารครับ และก็มีการใช้ Fourier Transform ในการคำนวนด้วย แต่ไม่มีรายละเอียดที่มา ที่ไปของการนำสูตรนี้มาใช้เลย จนต้องทิ้งความไม่เข้าใจอันนี้เอาไว้ก่อน แล้วก็เพียงจำสูตรไปใช้ก็พอ เพราะมีอีกหลายเรื่องต้องเรียน(ถ้ายังอยากจะจบ!!!)...จนวันหนึ่งผมกลับมาใคร่ครวญ กับมันใหม่ จนได้ความรู้แบบใหม่ จึงจะสามารถเข้าใจ Fourier transform ,Laplace transform และความหมายของจำนวนจินตภาพ(i), (complex number) จำนวนเชิงซ้อนและระบบจำนวนทั้งหมดครับ ทั้งหมดนี้ผมเขียนไว้ใน blog หนึ่งชื่อ ฟิสิกส์ของฉัน:ฟิสิกส์ทางเลือกและการหมุน
http://chevasit.blogspot.com/2012/01...e-physics.html