FFT แบบแยกฐาน (split-radix FFT)เป็นอัลกอริธึมการแปลงฟูริเยร์แบบเร็ว (FFT) สำหรับการคำนวณ การแปลงฟูริเยร์แบบไม่ต่อเนื่อง (DFT) และได้รับการอธิบายครั้งแรกในบทความที่ไม่ได้รับความสนใจมากนักโดยR. Yavne (1968) [1]และต่อมาได้รับการค้นพบใหม่พร้อมกันโดยผู้เขียนหลายคนในปี 1984 (ชื่อ "split radix" ได้รับการบัญญัติโดยผู้คิดค้นใหม่สองคนนี้ คือP. DuhamelและH. Hollmann ) โดยเฉพาะอย่างยิ่ง split radix เป็นรูปแบบหนึ่งของอัลกอริธึม FFT ของ Cooley–Tukey ที่ใช้ฐานผสมของ 2 และ 4: มันแสดง DFT ที่มีความยาวNในรูปของ DFT ขนาดเล็กหนึ่งตัวที่มีความยาวN /2 และ DFT ขนาดเล็กสองตัวที่มีความยาวN /4

FFT แบบแยกฐาน (split-radix FFT) พร้อมด้วยรูปแบบต่างๆ ของมัน ได้รับการยกย่องมานานแล้วว่าสามารถใช้จำนวนการดำเนินการทางคณิตศาสตร์น้อยที่สุด (จำนวนการบวกและการคูณ จำนวน จริง ทั้งหมดที่จำเป็น) ในการคำนวณ DFT ที่มี ขนาดเป็นกำลังสองNได้ จำนวนการดำเนินการทางคณิตศาสตร์ของอัลกอริทึมแบบแยกฐานดั้งเดิมได้รับการปรับปรุงในปี 2004 (โดยได้ผลลัพธ์เบื้องต้นจากการทำงานที่ยังไม่ได้ตีพิมพ์โดย J. Van Buskirk ผ่านการปรับแต่งด้วยมือสำหรับN = 64 [2] [3] ) แต่ปรากฏว่ายังคงสามารถบรรลุจำนวนการดำเนินการที่ต่ำที่สุดใหม่ได้โดยการดัดแปลงแบบแยกฐาน (Johnson และ Frigo, 2007) แม้ว่าจำนวนการดำเนินการทางคณิตศาสตร์จะไม่ใช่ปัจจัยเดียว (หรืออาจไม่ใช่ปัจจัยหลัก) ในการกำหนดเวลาที่จำเป็นในการคำนวณ DFT บนคอมพิวเตอร์แต่คำถามเกี่ยวกับจำนวนการดำเนินการขั้นต่ำที่เป็นไปได้นั้นเป็นที่สนใจทางทฤษฎีมาอย่างยาวนาน (ปัจจุบันยังไม่มีการพิสูจน์ขอบเขตล่างที่แน่นอนของจำนวนการดำเนินการ)

อัลกอริทึมแบบแยกฐาน (split-radix algorithm) สามารถใช้ได้เฉพาะเมื่อNเป็นพหุคูณของ 4 เท่านั้น แต่เนื่องจากมันแบ่ง DFT ออกเป็น DFT ที่เล็กกว่า จึงสามารถนำไปใช้ร่วมกับอัลกอริทึม FFT อื่นๆ ได้ตามต้องการ

โปรดจำไว้ว่า DFT ถูกกำหนดโดยสูตร:

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}\omega _{N}^{nk}}$

โดยที่เป็นจำนวนเต็มตั้งแต่ถึงและหมายถึงรากปฐมภูมิของเอกภาพ : ${\displaystyle k}$${\displaystyle 0}$${\displaystyle N-1}$${\displaystyle \omega _{N}}$

${\displaystyle \omega _{N}=e^{-{\frac {2\pi i}{N}}},}$

และด้วยเหตุนี้: . ${\displaystyle \โอเมก้า _{N}^{N}=1}$

อัลกอริทึมแบบแยกฐานทำงานโดยการแสดงผลรวมนี้ในรูปของผลรวมย่อยสามผล (ในที่นี้ เราแสดงเวอร์ชัน "การลดจำนวนในเวลา" ของ FFT แบบแยกฐาน ส่วนเวอร์ชันการลดจำนวนในความถี่แบบคู่ขนานนั้นโดยพื้นฐานแล้วก็คือขั้นตอนย้อนกลับของขั้นตอนเหล่านี้)

ขั้นแรก คือผลรวมของดัชนีคู่ขั้นที่สอง คือผลรวมของดัชนีคี่ที่แบ่งออกเป็นสองส่วน คือและโดยขึ้นอยู่กับว่าดัชนีเป็น 1 หรือ 3 มอดูล 4 ในที่นี้หมายถึงดัชนีที่วิ่งจาก 0 ถึงผลรวมที่ได้จะมีลักษณะดังนี้: ${\displaystyle x_{2n_{2}}}$${\displaystyle x_{4n_{4}+1}}$${\displaystyle x_{4n_{4}+3}}$${\displaystyle n_{m}}$${\displaystyle N/m-1}$

${\displaystyle X_{k}=\sum _{n_{2}=0}^{N/2-1}x_{2n_{2}}\omega _{N/2}^{n_{2}k}+\omega _{N}^{k}\sum _{n_{4}=0}^{N/4-1}x_{4n_{4}+1}\omega _{N/4}^{n_{4}k}+\omega _{N}^{3k}\sum _{n_{4}=0}^{N/4-1}x_{4n_{4}+3}\omega _{N/4}^{n_{4}k}}$

โดยที่เราใช้ข้อเท็จจริงที่ว่า ผลรวมทั้งสามนี้สอดคล้องกับส่วนต่าง ๆของ ขั้นตอน Cooley–Tukey แบบฐาน 2 (ขนาดN /2) และฐาน 4 (ขนาดN /4) ตามลำดับ (แนวคิดพื้นฐานคือ การแปลงย่อยดัชนีคู่ของฐาน 2 ไม่มีตัวคูณอยู่ข้างหน้า ดังนั้นจึงควรปล่อยไว้เช่นเดิม ในขณะที่การแปลงย่อยดัชนีคี่ของฐาน 2 จะได้รับประโยชน์จากการรวมการหารย่อยแบบเรียกซ้ำครั้งที่สอง) ${\displaystyle \omega _{N}^{mnk}=\omega _{N/m}^{nk}}$

ผลรวมย่อยเหล่านี้ในขณะนี้คือ DFT ที่มีความยาวN /2 และN /4 อย่างแม่นยำ ซึ่งสามารถดำเนินการแบบเวียนซ้ำแล้วนำมารวมกันได้

โดยเฉพาะอย่างยิ่ง ให้แทนผลลัพธ์ของ DFT ที่มีความยาวN /2 (สำหรับ) และให้และแทนผลลัพธ์ของ DFT ที่มีความยาวN /4 (สำหรับ) จากนั้นผลลัพธ์ที่ได้ก็คือ: ${\displaystyle U_{k}}$${\displaystyle k=0,\ldots ,N/2-1}$${\displaystyle Z_{k}}$${\displaystyle Z'_{k}}$${\displaystyle k=0,\ldots ,N/4-1}$${\displaystyle X_{k}}$

${\displaystyle X_{k}=U_{k}+\omega _{N}^{k}Z_{k}+\omega _{N}^{3k}Z'_{k}.}$

อย่างไรก็ตาม วิธีนี้จะทำการคำนวณที่ไม่จำเป็น เนื่องจากพบว่ามีการคำนวณร่วมกันหลายอย่างกับ โดยเฉพาะอย่างยิ่ง ถ้าเราเพิ่มN /4 ให้กับk DFT ขนาดN /4 จะไม่เปลี่ยนแปลง (เพราะเป็นคาบในN /4) ในขณะที่ DFT ขนาดN /2 จะไม่เปลี่ยนแปลงหากเราเพิ่มN /2 ให้กับkดังนั้น สิ่งเดียวที่เปลี่ยนแปลงคือเทอมและซึ่งเรียกว่าปัจจัยทวิเดิลในที่นี้ เราใช้เอกลักษณ์ดังต่อไปนี้: ${\displaystyle k\geq N/4}$${\displaystyle k<N/4}$${\displaystyle \โอเมก้า _{N}^{k}}$${\displaystyle \โอเมก้า _{N}^{3k}}$

${\displaystyle \omega _{N}^{k+N/4}=-i\omega _{N}^{k}}$

${\displaystyle \omega _{N}^{3(k+N/4)}=i\omega _{N}^{3k}}$

เพื่อมาถึงข้อสรุปสุดท้าย:

${\displaystyle X_{k}=U_{k}+\left(\omega _{N}^{k}Z_{k}+\omega _{N}^{3k}Z'_{k}\right),}$

${\displaystyle X_{k+N/2}=U_{k}-\left(\omega _{N}^{k}Z_{k}+\omega _{N}^{3k}Z'_{k}\right),}$

${\displaystyle X_{k+N/4}=U_{k+N/4}-i\left(\omega _{N}^{k}Z_{k}-\omega _{N}^{3k}Z'_{k}\right),}$

${\displaystyle X_{k+3N/4}=U_{k+N/4}+i\left(\omega _{N}^{k}Z_{k}-\omega _{N}^{3k}Z'_{k}\right),}$

ซึ่งจะให้ผลลัพธ์ทั้งหมดหากเรากำหนดช่วงตั้งแต่ถึงในนิพจน์ทั้งสี่ข้างต้น ${\displaystyle X_{k}}$${\displaystyle k}$${\displaystyle 0}$${\displaystyle N/4-1}$

โปรดสังเกตว่านิพจน์เหล่านี้ถูกจัดเรียงไว้เพื่อให้เราต้องรวมเอาผลลัพธ์ DFT ต่างๆ เข้าด้วยกันโดยใช้การบวกและการลบเป็นคู่ๆ ซึ่งเรียกว่า " ผีเสื้อ " เพื่อให้ได้จำนวนการดำเนินการน้อยที่สุดสำหรับอัลกอริทึมนี้ จำเป็นต้องพิจารณากรณีพิเศษสำหรับ(ซึ่งปัจจัยทวิเดิลเป็นหนึ่ง) และสำหรับ(ซึ่งปัจจัยทวิเดิลเป็นและสามารถคูณกันได้เร็วกว่า) ดูตัวอย่างเช่น Sorensen et al. (1986) การคูณด้วยและโดยทั่วไปจะนับว่าฟรี (การปฏิเสธทั้งหมดสามารถดูดซับได้โดยการแปลงการบวกเป็นการลบหรือในทางกลับกัน) ${\displaystyle k=0}$${\displaystyle k=N/8}$${\displaystyle (1\pm i)/{\sqrt {2}}}$${\displaystyle \pm 1}$${\displaystyle \pm i}$

การแยกส่วนนี้จะดำเนินการแบบเรียกซ้ำเมื่อNเป็นกำลังของสอง กรณีพื้นฐานของการเรียกซ้ำคือN = 1 ซึ่ง DFT เป็นเพียงสำเนาและN = 2 ซึ่ง DFT เป็นการบวกและการลบ ${\displaystyle X_{0}=x_{0}}$${\displaystyle X_{0}=x_{0}+x_{1}}$${\displaystyle X_{1}=x_{0}-x_{1}}$

จากการพิจารณาเหล่านี้ ทำให้ได้จำนวนการบวกและการคูณจริง โดยที่N > 1 เป็นกำลังของสอง จำนวนนี้ถือว่า สำหรับกำลังคี่ของ 2 ตัวประกอบที่เหลือของ 2 (หลังจากขั้นตอนการแยกฐานทั้งหมด ซึ่งหารNด้วย 4) จะถูกจัดการโดยตรงด้วยนิยาม DFT (การบวกและการคูณจริง 4 ครั้ง) หรือเทียบเท่ากับขั้นตอน FFT ของ Cooley–Tukey ฐาน 2 ${\displaystyle 4N\log _{2}N-6N+8}$