เร็วกว่าเดิม! นักวิจัยจาก MIT คิดอัลกอริทึมคำนวณ Fourier Transform ได้เร็วว่า FFT

By: lew
Writer
on Fri, 20/01/2012 - 02:54

การประมวลผลด้านสัญญาณในปัจจุบันอาศัยการแปลงข้อมูลที่เรารับรู้เช่นเสียงหรือภาพไปอยู่ในโดเมนของความถี่ (Frequency Domain) อย่างหนัก เพื่อจะกรองข้อมูลบางอย่างที่ไม่สำคัญออกไปจากการทำงาน เช่นความถี่ที่สูงมากๆ หรือต่ำมากๆ จนเกินการรับรู้ของคนทั่วไป หรือกระทั่งการปรับแต่งเสียงใน Equalizer ให้เสียงเป็นไปตามความต้องการของเราก็ตามที

อัลกอริทึมที่ได้รับความนิยมกันตลอดมาคือ Fast Fourier Transform (FFT) ที่สามารถคำนวณสัญญาณดิจิตอลแบบจำกัดการสุ่มข้อมูลออกมาเป็นโดเมนความถี่ได้ภายใน \(\begin{align}
O\left( n\log\left( n\right)\right)
\end{align}
\) ความเร็วทำให้ FFT ถูกใช้งานในอุปกรณ์ประมวลสัญญาณแบบดิจิตอลจำนวนมาก ซีพียูหลายตัวมีคำสั่งเฉพาะเพื่อเร่งความเร็วการทำงานของ FFT

อัลกอริทึมใหม่นี้ให้ผลได้ภายในเวลา \(\begin{align}
O\left( k\log\left( n\right)\log\left(\frac{ n}{ k}\right)\right)
\end{align}
\) ในกรณีทั่วไป ซึ่งดีกว่า FFT โดยอาศัยฟิลเตอร์แยกคลื่นออกเป็นช่วงแคบๆ ที่มีความถี่บางความถี่เป็นความถี่หลัก จากนั้นจึงคำนวณหาความแรงของความถี่หลักนั้นๆ กระบวนการนั้นไม่ตรงไปตรงมาเนื่องจากฟิลเตอร์ไม่สามารถกรองความถี่ได้อย่างสมบูรณ์อย่างที่เราหวัง แต่ความถี่ข้างเคียงยังคงอยู่โดยจะถูกลดทอนความแรงลงไป อัลกอริทึมใหม่ สร้างกระบวนการกรองที่ทำให้แน่ใจได้ว่าความถี่เป้าหมายจะไม่ไปอยู่ในช่วงที่ถูกลดความแรงสัญญาณพอดี

การคำนวณ FFT เป็นเรื่องค่อนข้างซับซ้อนและเป็นเรื่องพื้นฐานในสายวิชาไฟฟ้า อย่างไรก็ดี การที่เรามีอัลกอริทึมที่เร็วขึ้นทำให้มีความเป็นไปได้ที่เราจะคำนวณสัญญาณที่ซับซ้อนขึ้น การประมวลผลสัญญาณจำนวนมากในอุปกรณ์อิเล็กทรอนิกส์จะใช้พลังงานน้อยลงเป็นต้น

ที่มา - MIT, arXiv:1201.2501v1

5 Comments

idxn's picture

อ่านข่าวนี้แล้ว คิดถึงสมัยเรียนมหาลัยเลย

hisoft's picture

แค่เห็นคำว่า Fourier Transform ก็นั่งน้ำตาซึม Signal & Digital Signal Processing ลอยขึ้นมาในหัว (T-T)

The Phantom Thief