# விரைவு ஃபூரியே உருமாற்றம்

## வழிமுறைகள்

### பிற FFT வழிமுறைகள்

கூலி டக்கி முறையிலிருந்து வேறுபட்டுள்ள பிற FFT வழிமுறைகளும் உள்ளன. இணை பகா எண் <math>N_1</math> மற்றும் <math>N_2</math> என்று உள்ள <math>N = N_1 N_2</math> க்கு, கூலி டக்கியைப் போல, ஆனால் சுழல் காரணிகள் இன்றி DFT ஐ காரணிப்படுத்த, சைனீஸ் மீதித் தேற்றத்தை அடிப்படையாகக் கொண்ட பகா-காரணி (கூட்-தாமஸ்) வழிமுறையைப் (PFA) பயன்படுத்தலாம். ரேடர்-ப்ரென்னர் வழிமுறை (1976) ஒரு கூலி-டக்கி வழிமுறையைப் போன்ற காரணிப்படுத்தலாகும், ஆனால் அதில் முழுக்க கற்பனையான சுழல் காரணிகள் உள்ளன. அதில் அதிகரிக்கப்பட்ட கூட்டல்களுடன் எண்ணியல் நிலைத்தன்மை குறைந்து, பெருக்கல்கள் குறைவாக உள்ளன. பின்னர் அது கூலி-டக்கியின் ஸ்பிளிட்-ரேடிக்ஸ் வகையால் வெல்லப்பட்டது (அது துல்லியத் தன்மையை இழக்காமல், குறைவான கூட்டல்களுடன் அதே பெருக்கல்களை சாத்தியமாக்குகிறது). மீண்டும் மீண்டும் DFT ஐ சிறிய செயல்பாடுகளாகக் காரணிப்படுத்தும் DFTகளல்லாத பிற வழிமுறைகளில் ப்ரன் மற்றும் QFT வழிமுறைகள் ஆகியன அடங்கும். (ரேடர்-ப்ரன் மற்றும் QFT வழிமுறைகள் அடுக்கு இரண்டு என்ற அளவுகளுக்காக முன்மொழியப்பட்டன, ஆனால் அவற்றை சிக்கலான <math>n</math> க்குப் பயன்படுத்துவது சாத்தியமல்ல. ப்ரன்னின் வழிமுறை தனிப்பட்ட சிக்கலான அளவுகளுக்கும் பொருந்துகிறது.) ப்ரன்னின் வழிமுறை, குறிப்பாக, FFT ஐ <math>z^N-1</math> பல்லுறுப்புக்கோவையின் மீண்டும் மீண்டும் நிகழும் ஒரு காரணிப்படுத்தலாகப் புரிதல் விளக்கம் செய்தலை அடிப்படையாகக் கொண்டதாகும், இங்கு <math>z^M-1</math> வகை மெய் குணகப் பல்லுறுப்புக் கோவைகளாகக் காரணியாக்கம் செய்கிறது, மேலும்
<math>z^{2M} + az^M + 1</math>.  
மற்றொரு பல்லுறுப்புக் கோவைக் கண்ணோட்டம் வினோக்ராட் வழிமுறையால் பயன்படுத்தப்பட்டது, அது <math>z^N-1</math> ஐ சைக்ளோட்டமிக் பல்லுறுப்புக் கோவைகளாகக் காரணியாக்கம் செய்கிறது—இவை பெரும்பாலும் 1, 0 அல்லது −1 என்ற குணகங்களாகும், மேலும் அதனால் இதற்கு (இருந்தால்) சில பெருக்கல்கள் தேவைப்படுகின்றன, ஆகவே வினோக்ராட் வழிமுறையை குறைந்தபட்ச பெருக்கல்கள் கொண்ட FFTகளைப் பெறப் பயன்படுத்தலாம். மேலும் அது பெரும்பாலும் சிறு காரணிகளுக்கான வழிமுறைகளைக் கண்டறியப் பயன்படுத்தப்படுகிறது. உண்மையில், DFT ஐ வெறும் <math>O(N)</math> விகிதமுறாப் பெருக்கல்களை மட்டும் கொண்டு கணக்கிட முடியும் என வினோக்ராட் வழிமுறை காண்பித்தது. இதனால் அடுக்கு இரண்டு என்ற அளவுகளுக்கான பெருக்கல்களின் எண்ணிக்கைக்கான அடையத்தக்க கீழ் வரம்பு நிரூபிக்கப்பட்டது. துரதிருஷ்டவசமாக, இதற்கு பல கூட்டல்கள் தேவைப்பட்டது, இந்த பிரதிபலன் சிரமமானது வன்பொருள் பெருக்கிகளைக் கொண்டுள்ள தற்கால செயலிகளில் ஆதரிக்கத்தக்கதல்ல. குறிப்பாக, வினோக்ராட் வழிமுறை PFA ஐயும் அதே போல் *பகா* அளவு FFTகளுக்கான ரேடரின் ஒரு வழிமுறையையும் பயன்படுத்துகிறது.  
ரேடரின் வழிமுறை, பெருக்கத்தக்க குழு மட்டு பகா <math>N</math> க்கான உருவாக்கியின் இருப்பையும் பயன்படுத்துகிறது. அது <math>n</math> பகா அளவுள்ள ஒரு DFT ஐ <math>N-1</math> அளவுள்ள சுழற்சித் தன்மையுள்ள சுழற்சியாகக் (சிக்கலான) குறிப்பிடுகிறது. அதை சுழற்சித் தேற்றத்தைப் பயன்படுத்தி சாதாரண FFT இணையைக் கணக்கிடுவதன் மூலம் கணக்கிட முடியும் (இருப்பினும் வினோக்ராட் பிற சுழற்சி முறைகளையும் பயன்படுத்துகிறது). மற்றொரு பகா-அளவு FFT எல். ஐ. ப்ளூஸ்டெயினால் முன்மொழியப்பட்டது. அது சில நேரங்களில் சிர்ப்-z வழிமுறை என அழைக்கப்பட்டது. அதுவும் *அதே* DFT ஐ சுழற்சியாகக் குறிப்பிடுகிறது, ஆனால் இதில் <math>nk = -(k-n)^2/2 + n^2/2 + k^2/2</math> முற்றொருமையின் மூலம் கண்டறியப்படும் எண் அதே அளவைப் (இதை அடுக்கு இரண்டு என்ற அளவுக்கு பூச்சிய மென்மைப்படுத்தலுக்குட்படுத்த முடியும், மேலும் இதை ரேடிக்ஸ்-2 கூலி-டக்கி மூலம் கணக்கிட முடியும்) பயன்படுத்துகிறது.