ในบริบทของอัลกอริธึมการแปลงฟูริเยร์แบบเร็วผีเสื้อคือส่วนหนึ่งของการคำนวณที่รวมผลลัพธ์ของการแปลงฟูริเยร์แบบไม่ต่อเนื่อง (DFT) ขนาดเล็กเข้าด้วยกันเป็น DFT ขนาดใหญ่ หรือในทางกลับกัน (การแบ่ง DFT ขนาดใหญ่เป็นการแปลงย่อย) ชื่อ "ผีเสื้อ" มาจากรูปร่างของไดอะแกรมการไหลของข้อมูลในกรณีฐาน 2 ดังที่อธิบายไว้ด้านล่าง^{[ 1 ]}เชื่อกันว่าคำนี้ปรากฏครั้งแรกในสิ่งพิมพ์ในรายงานทางเทคนิคของ MIT ในปี 1969 ^{[ 2 ] [ 3 ]}โครงสร้างเดียวกันนี้ยังพบได้ในอัลกอริธึม Viterbiซึ่งใช้สำหรับค้นหาลำดับของสถานะที่ซ่อนอยู่ที่น่าจะเป็นไปได้มากที่สุด

โดยทั่วไป คำว่า "ผีเสื้อ" มักปรากฏในบริบทของอัลกอริธึม Cooley–Tukey FFTซึ่งจะแบ่ง DFT ที่มีขนาดประกอบn  =  rmออกเป็นrการแปลงย่อยที่มีขนาดmโดยที่rคือ "ฐาน" ของการแปลง จากนั้น DFT ย่อยเหล่านี้จะถูกรวมเข้าด้วยกันโดยใช้ผีเสื้อขนาดrซึ่งตัวมันเองก็คือ DFT ขนาดr (ทำซ้ำmครั้งกับผลลัพธ์ที่สอดคล้องกันของการแปลงย่อย) ที่คูณด้วยรากของเอกภาพ (เรียกว่าตัวประกอบทวิเดิล ) ก่อน (นี่คือกรณี "การลดขนาดตามเวลา" เราสามารถทำขั้นตอนย้อนกลับได้เช่นกัน ซึ่งเรียกว่า "การลดขนาดตามความถี่" โดยที่ผีเสื้อจะมาก่อนและคูณด้วยตัวประกอบทวิเดิลภายหลัง ดู บทความ Cooley–Tukey FFT เพิ่มเติม )

ในกรณีของอัลกอริธึม Cooley–Tukey แบบ radix-2 นั้น ตัวผีเสื้อ (butterfly) ก็คือ DFT ขนาด 2 ที่รับอินพุตสองตัว ( x ₀ ,  x ₁ ) (เอาต์พุตที่สอดคล้องกันของการแปลงย่อยสองตัว) และให้เอาต์พุตสองตัว ( y ₀ ,  y ₁ ) โดยใช้สูตร (ไม่รวมปัจจัยทวิเดิล ):

${\displaystyle y_{0}=x_{0}+x_{1}\,}$

${\displaystyle y_{1}=x_{0}-x_{1}.\,}$

หากวาดแผนภาพการไหลของข้อมูลสำหรับการดำเนินการทั้งสองนี้ เส้น ( x ₀ ,  x ₁ ) ถึง ( y ₀ ,  y ₁ ) จะตัดกันและมีลักษณะคล้ายปีกผีเสื้อจึงเป็นที่มาของชื่อนี้ (ดูภาพประกอบทางด้านขวาประกอบ)

โดยเฉพาะอย่างยิ่ง อัลกอริทึม FFT แบบลดทอนตามเวลาแบบ radix-2 บน อินพุต n  = 2p ^โดยสัมพันธ์กับ รากที่ nของเอกภาพ แบบดั้งเดิม อาศัยผีเสื้อ O( n  log _2n )ในรูปแบบ:  ${\displaystyle \omega _{n}^{k}=e^{-{\frac {2\pi ik}{n}}}}$ 

${\displaystyle y_{0}=x_{0}+x_{1}\omega _{n}^{k}\,}$

${\displaystyle y_{1}=x_{0}-x_{1}\omega _{n}^{k},\,}$

โดยที่kเป็นจำนวนเต็มที่ขึ้นอยู่กับส่วนของการแปลงที่กำลังคำนวณ ในขณะที่การแปลงผกผันที่สอดคล้องกันสามารถทำได้ทางคณิตศาสตร์โดยการแทนที่ωด้วยω ⁻¹ (และอาจคูณด้วยตัวประกอบมาตราส่วนโดยรวม ขึ้นอยู่กับข้อกำหนดการทำให้เป็นมาตรฐาน) เรายังสามารถกลับด้านผีเสื้อได้โดยตรง:

${\displaystyle x_{0}={\frac {1}{2}}(y_{0}+y_{1})\,}$

${\displaystyle x_{1}={\frac {\omega _{n}^{-k}}{2}}(y_{0}-y_{1}),\,}$

ซึ่งสอดคล้องกับอัลกอริธึม FFT แบบลดความถี่

ผีเสื้อยังสามารถใช้เพื่อปรับปรุงความเป็นสุ่มของอาร์เรย์ขนาดใหญ่ของตัวเลขสุ่มบางส่วนได้ โดยการนำคำ 32 หรือ 64 บิตทุกคำมาสัมผัสเชิงสาเหตุกับคำอื่น ๆ ทุกคำผ่านอัลกอริทึมแฮชที่ต้องการ เพื่อให้การเปลี่ยนแปลงในบิตใดบิตหนึ่งมีโอกาสที่จะเปลี่ยนแปลงบิตทั้งหมดในอาร์เรย์ขนาดใหญ่ได้^{[ 4 ]}

• แผนภาพทางคณิตศาสตร์
• เลมมาของซาสเซนเฮาส์
• กราฟแสดงการไหลของสัญญาณ

• คำอธิบายเกี่ยวกับ FFT และแผนภาพผีเสื้อ
• แผนภาพผีเสื้อแสดงการใช้งาน FFT แบบต่างๆ (Radix-2, Radix-4, Split-Radix )