การประมวลผลด้านสัญญาณในปัจจุบันอาศัยการแปลงข้อมูลที่เรารับรู้เช่นเสียงหรือภาพไปอยู่ในโดเมนของความถี่ (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
