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

விரைவு ஃபூரியே உருமாற்றம் (FFT) என்பது இலக்கமியல் ஃபூரியே உருமாற்றத்தையும் (DFT) அதன் தலைகீழியையும் கணக்கிடுவதற்கான செயல்திறன் மிக்க வழிமுறையாகும். பல்வேறு பரந்த அளவிலான கணிதங்களுடன் சம்பந்தப்பட்ட பல வேறுபட்ட FFT வழிமுறைகள் உள்ளன, அவற்றில் எளிய சிக்கலெண் எண்கணிதத்திலிருந்து குழுக் கோட்பாடு மற்றும் எண் கோட்பாடு வரையிலான பல பிரிவுகள் அடங்கும். இந்தக் கட்டுரை கிடைக்கக்கூடிய உத்திகள் மற்றும் அவற்றின் பொதுவான பண்புகளில் சிலவற்றை மட்டும் மேலோட்டமாக விளக்குகிறது. தனிப்பட்ட வழிமுறைகள், கீழே பட்டியலிடப்பட்டுள்ள தனித்தனி துணைக் கட்டுரைகளில் விளக்கப்பட்டுள்ளன.

ஒரு DFT ஆனது ஒரு தொடர்வரிசை மதிப்புகளை வெவ்வேறு அதிர்வெண்ணுள்ள கூறுகளாகப் பிரிக்கிறது. இந்தச் செயல்பாடானது பல துறைகளில் பயன்மிக்கதாகும் (உருமாற்றத்தின் பண்புகள் மற்றும் பயன்களுக்கு இலக்கமியல் ஃபூரியே உருமாற்றம் என்பதைக் காண்க) ஆனால் வரையறையிலிருந்து இதனை நேரடியாகக் கணக்கிடுவது என்பது நடைமுறையில் இயலாத அளவுக்கு மிகவும் மெதுவான செயலாகும். FFT என்பது அதே முடிவை விரைவாகக் கணக்கிடும் வழியாகும்: வரையறையைப் பயன்படுத்தி தெளிவான வழியில் N புள்ளிகளின் ஒரு DFT ஐக் கணக்கிடும் போது, O(N ²) எண்கணித செயல்பாடுகள் தேவைப்படுகின்றன. அதே நேரத்தில் இதே முடிவை ஒரு FFT முறையானது O(N log N ) செயல்பாடுகளிலேயே கணக்கிடக்கூடும். வேகத்திலுள்ள வேறுபாடானது குறிப்பிடத்தக்க அளவிலிருக்கக்கூடும், குறிப்பாக N மதிப்பு ஆயிரக்கணக்கில் அல்லது மில்லியன் கணக்கில் இருக்கும் வகையிலான தரவுத் தொகுப்புகளுக்கு இந்த வேறுபாடு அதிகமாக இருக்கும். நடைமுறையில் இது போன்ற சந்தர்ப்பங்களில் கணக்கீட்டு நேரத்தை எண்ணளவில் பல மடங்குகள் குறைக்க முடியும். இந்த மேம்பாடானது N /log(N ) க்கு நேர்த்தகவில் இருக்கும். இந்தப் பெரிய மேம்பாட்டினால் பல DFT-அடிப்படையிலான வழிமுறைகள் நடைமுறையில் சாத்தியமாயின. பல பயன்பாடுகளில் FFTகள் மிக முக்கியமானவையாகும், அதில் எண்முறை குறிகை செயலாக்கம் மற்றும் நடைமுறை வகையீட்டு சமன்பாடுகளைத் தீர்த்தல் போன்றவற்றிலிருந்து விரைவாக பெரிய முழு எண்களைப் பெருக்கற்பலன் காணுதல் வரையிலான செயல்கள் அடங்கும்.

மிகவும் பிரபலமான FFT வழிமுறைகள் N இன் காரணியாக்கத்தினைப் பொறுத்துள்ளன, ஆனால் (பிரபலமான தவறான கருத்துக்கு மாறாக) N இன் மதிப்பு அனைத்து மதிப்புகளுக்கும் O(N log N ) கடின தன்மை கொண்டுள்ள FFTகளும் உள்ளன, பகா N மதிப்புகளுக்கும் கூட இது பொருந்தும். பல FFT வழிமுறைகள் $e^{-{2\pi i \over N}}$ என்பது ஒரு $N$வது ஒன்றின் தொடக்கநிலை மூலமாக உள்ளது என்ற உண்மையைச் சார்ந்தவையாக உள்ளன, மேலும் இதனால் எண்-கோட்பாட்டு உருமாற்றங்கள் போன்ற எந்த வரையறை புலங்களுக்கும் இதைப் பயன்படுத்தலாம்.

தலைகீழ் DFT என்பது DFT ஐப் போன்றதே, ஆனால் அடுக்கிலும் ஒரு 1/N காரணியிலும் எதிர்க்குறியைக் கொண்டுள்ளது என்பதால், எந்த FFT வழிமுறையையும் அதற்கு எளிதாகப் பயன்படுத்தலாம்.

வரையறையும் வேகமும்

ஒரு FFT ஆனது DFT ஐக் கணக்கிட்டு DFT வரையறையை நேரடியாகக் கணக்கிடுவதால் கிடைக்கும் அதே முடிவைக் கொடுக்கிறது. FFT மிகவும் வேகமாக உள்ளது மட்டுமே வேறுபாடாகும். (முழுமையாக்கல் பிழை இருக்கும்பட்சத்தில், பல FFT வழிமுறைகளும் DFT வரையறையை நேரடியாகக் கணக்கிடுவதைக் காட்டிலும் துல்லியமாக உள்ளன, அது கீழே விவாதிக்கப்பட்டுள்ளது.)

x ₀, ...., x _{N -1} ஆகியவை சிக்கலெண்கள் என்க. பின்வரும் சூத்திரத்தால் DFT வரையறுக்கப்படுகிறது

$X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{i2\pi k{\frac {n}{N}}}}\qquad k=0,\dots ,N-1.$

இந்த வரையறையை நேரடியாகக் கணக்கிடுவதற்கு O (N ²) செயல்பாடுகள் தேவைப்படுகின்றன: அதற்கு N வெளியீடுகள் X _k உள்ளன, மேலும் ஒவ்வொரு வெளியீட்டுக்கும் மொத்தம் N உறுப்புகள் தேவைப்படுகின்றன. ஒரு FFT என்பது இதே முடிவை O(N log N ) செயல்பாடுகளில் கணக்கிடுவதற்கான முறையாகும். மேலும் துல்லியமாக, அறியப்பட்ட FFT வழிமுறைகள் அனைத்திற்குமே Θ(N log N ) செயல்பாடுகள் அவசியமாகிறது (நுட்ப ரீதியாக, O என்பது ஒரு மேல் வரம்பையே குறிக்கிறது), இருப்பினும் இதை விடச் சிறந்த சிக்கலான தன்மை சாத்தியமற்றது என்பதற்கான நிரூபணம் இல்லை.

ஒரு FFT இன் சேமிப்பை விளக்க, பல சிக்கலான பெருக்கல் மற்றும் கூட்டல்களைக் கருதுக. DFT இன் கூட்டுத்தொகையை நேரடியாகக் கணக்கிடுவதற்கு N ² சிக்கலெண் பெருக்கலும் N (N  − 1) சிக்கலெண் கூட்டலும் [அதில் 1 ஆல் பெருக்குதல் போன்ற சிறிய பல செயல்பாடுகளை நீக்குவதன் மூலம் O (N ) செயல்பாடுகள் சேமிக்கப்பட முடியும்] தேவைப்படுகின்றன. மிகவும் பிரபலமான N இன் அடுக்கு 2 க்கான அடிமானம்-2 கூலி-டக்கி வழிமுறையில், இதே முடிவை வெறும் (N /2) log₂ N சிக்கலெண் பெருக்கல்கள் (இதிலும் 1 ஆல் பெருக்குதல் மற்றும் அது போன்ற எளிய செயல்பாடுகளைத் தவிர்ப்பதன் மூலம்) மற்றும் N  log₂N சிக்கலெண் கூட்டல்கள் ஆகிய செயல்பாடுகளிலேயே கணக்கிட முடியும். நடைமுறையில், வழக்கமாக தற்கால கணினிகளிலான உண்மையான செயல்திறனானது எண் கணிதம் தவிர்த்த பிற காரணிகளால் கட்டுப்படுத்தப்படுகிறது. மேலும் சிக்கலான விஷயமாகவும் உள்ளது (காண்க: எ.கா., ஃப்ரிகோ & ஜான்சன், 2005), ஆனால் Θ(N ²) இலிருந்து Θ(N log N ) வரையிலான ஒட்டுமொத்த மேம்பாடு உள்ளது.

கணக்கீட்டு சிக்கல்கள்

சிக்கலான தன்மையின் வரம்புகள் மற்றும் செயல்பாடு எண்ணிக்கைகள்

விரைவு ஃபூரியே உருமாற்றங்களின் சிக்கலான தன்மையின் கீழ் வரம்புகள் மற்றும் செயல்பாடுகளின் துல்லியமான எண்ணிக்கை ஆகியவை நீண்டகாலமாக இருந்துவரும் கோட்பாட்டியல் கருத்தின் ஓர் அடிப்படைக் கேள்வியாகும், அதுமட்டுமின்றி பல கணக்குகள் இன்னும் தீர்க்கப்படாமலே உள்ளன. DFTகளுக்கு உண்மையிலேயே $\Omega (N\log N)$ (அதாவது $N\log N$ என்னும் அளவில் அல்லது அதைவிட அதிக) செயல்பாடுகள் தேவை என பெரிதாக நிரூபிக்கப்படவில்லை, அடுக்கு இரண்டு என்ற அளவிலான சிறிய நிகழ்வுகளுக்கும் அது நிரூபிக்கப்படவில்லை, இருப்பினும் குறைவான சிக்கலான தன்மை கொண்டுள்ள வழிமுறைகளும் இல்லை. வழக்கமாக குறிப்பாக, இது போன்ற கேள்விகளின் மையமாக இருப்பது எண் கணித செயல்பாடுகளின் எண்ணிக்கையே ஆகும், இருப்பினும் தற்கால கணினிகளிலான உண்மையான செயல்திறனானது தேக்ககம் அல்லது CPU பைப்லைன் உகந்ததாக்கல் போன்ற பிற பல காரணிகளால் தீர்மானிக்கப்படுகிறது.

வினோக்ராடின் (1978) முன்னோடிப் பணிகளைத் தொடர்ந்து, FFT க்கு தேவையான மெய் பெருக்கல்களின் எண்ணிக்கைக்கான ஒரு இறுக்கமான $\Theta (N)$ கீழ் வரம்பு அறியப்பட்டது. அடுக்கு இரண்டு மற்றும் நீளம் $N=2^{m}$ கொண்ட ஒரு DFTஐக் கணக்கிட வெறும் $4N-2\log _{2}^{2}N-2\log _{2}N-4$ விகிதமுறா மெய் பெருக்கல்களே தேவை எனக் காண்பிக்க முடியும். மேலும், இந்த எண்ணிக்கையை அடையும் வெளிப்படையான வழிமுறைகள் அறியப்பட்டன (ஹெயிட்மேன் & புர்ரஸ், 1986. டுஹேமல், 1990). துரதிருஷ்டவசமாக, குறைந்தது, வன்பொருள் பெருக்கிகளைக் கொண்ட நவீன கணினிகளில் இந்த வழிமுறைகளுக்கு நடைமுறையில் அதிக கூட்டல்கள் தேவைப்பட்டன.

தேவையான கூட்டல்களின் எண்ணிக்கையிலான ஓர் இறுக்கமான கீழ் வரம்பு அறியப்படவில்லை , இருப்பினும் வழிமுறைகளிலான சில கட்டுப்படுத்தல் கருதுகோள்களின் அடிப்படையில் சில கீழ் வரம்புகள் நிரூபிக்கப்பட்டுள்ளன. 1973 ஆம் ஆண்டில், வழிமுறைகளுக்கான கூட்டல் எண்ணிக்கையிலான ஒரு $\Omega (N\log N)$ கீழ் வரம்பை மார்கென்ஸ்டர்ன் (Morgenstern) நிரூபித்தார். அதில் பெருக்கல் தொடர்பான மாறிலிகளுக்கு கட்டுண்ட எண்ணளவுகள் இருந்தன (இது பெரும்பாலான FFT வழிமுறைகளுக்கு மெய்யாகும், ஆனால் அனைத்து வழிமுறைகளுக்குமல்ல). பேன் (Pan) (1986) ஒரு $\Omega (N\log N)$ கீழ் வரம்பை நிரூபித்தார், அவர் FFT வழிமுறையின் "ஒத்திசைவின்மை" அளவிலான வரம்பைக் கருத்தில் கொண்டார். ஆனால் இந்தக் கருதுகோளின் பொதுத்தன்மையானது தெளிவாக இல்லை. $N$ இன் அடுக்கு இரண்டு என்ற நிபந்தனைக்கு, பாப்படிமித்ரியோ (Papadimitriou) (1979), கூலி டக்கி வழிமுறையைப் பயன்படுத்திப் பெறப்பட்ட சிக்கலெண் கூட்டல்களின் எண் $N\log _{2}N$ ஆனது வழிமுறையின் வரைபடத்தின் சில குறிப்பிட்ட கருதுகோள்களின் அடிப்படையில் சிறந்ததாக உள்ளது என விவாதித்தார் (அவரது கருதுகோள்கள் பிற அம்சங்களுடன் ஒன்றின் மூலங்களிலுள்ள கூட்டல் உறுப்புகள் எதுவும் பயன்படுத்தப்படவில்லை என்பதையும் குறிப்பிடுகிறது). (இந்த விவாதமானது குறைந்தபட்சம் $2N\log _{2}N$ மெய் கூட்டல்கள் தேவைப்படுகின்றன எனக் குறிப்பிடுகின்றது, இருப்பினும் இது இறுக்கமான வரம்பு கிடையாது, ஏனெனில் சிக்கலெண் பெருக்கலின் பகுதியாக கூடுதல் கூட்டல்கள் தேவைப்படுகின்றன.) இதுவரை வெளியிடப்பட்ட FFT வழிமுறை எதுவும், $N$ இன் அடுக்கு இரண்டுக்கான $N\log _{2}N$ க்கும் குறைவான சிக்கலெண் கூட்டல்கள் எண்ணிக்கையை (அல்லது அதற்கு சமமான எண்ணிக்கையை) சாத்தியமாக்கவில்லை.

மொத்த மெய் பெருக்கங்கள் மற்றும் கூட்டல்களின் எண்ணிக்கையைக் குறைப்பது மூன்றாவது சிக்கலாகும், இது சில நேரங்களில் "எண் கணிதவியல் சிக்கலான தன்மை" என அழைக்கப்படுகிறது (இருப்பினும் இந்தச் சூழலில் அது கருதப்படும் தொலைத் தொடுகோட்டு ரீதியான சிக்கலான தன்மையாக இல்லாமல் துல்லியமான எண்ணிக்கையாக உள்ளது). இறுக்கமான எல்லை எதுவும் நிரூபிக்கப்படவும் இல்லை. இருப்பினும் 1968 ஆம் ஆண்டிலிருந்து, $N$ இன் அடுக்கு இரண்டுக்கான வெளியிடப்பட்ட குறைந்தபட்ச எண்ணிக்கை ஸ்ப்ளிட்-ரேடிக்ஸ் FFT வழிமுறையின் மூலம் சாத்தியப்பட்டுள்ளது. அதற்கு $N>1$ என்ற நிபந்தனையில், $4N\log _{2}N-6N+8$ மெய்ப் பெருக்கங்களும் கூட்டல்களும் தேவைப்பட்டன. இது சமீபத்தில் $\sim {\frac {34}{9}}N\log _{2}N$ எனக் குறைக்கப்பட்டது (ஜான்சன் மற்றும் ஃப்ரிகோ, 2007; லண்டி மற்றும் வேன் பஸ்கிர்க், 2007).

FFT வழிமுறைகளின் சிக்கலான தன்மையைக் குறைக்க அல்லது நிரூபிப்பதற்கான பெரும்பாலான முயற்சிகள் சாதாரண சிக்கலான தரவு நிகழ்வுகளிலேயே கவனம் செலுத்தியுள்ளன, ஏனெனில் அவை எளிமையானவை. இருப்பினும், சிக்கலான தரவு FFTகள் மெய்-தரவு FFTகள், இலக்கமியல் கொசைன் உருமாற்றங்கள், இலக்கமியல் ஹார்ட்லி உருமாற்றங்கள் போன்ற தொடர்புடைய சிக்கல்களுக்கான வழிமுறைகளுடன் மிகவும் நெருக்கமான தொடர்புடையவை. அதாவது இதில் ஏதேனும் ஒன்றின் மேம்பாடு உடனடியாக மற்றவற்றின் மேம்பாடுகளுக்கு வழிவகுக்கும் (டுஹாமெல் & வெட்டர்லி, 1990).

துல்லியமான தன்மையும் தோராயமாக்கல்களும்

கீழே விவாதிக்கப்பட்டுள்ள அனைத்து FFT வழிமுறைகளும் DFT ஐ துல்லியமாகக் கணக்கிடுகின்றன (துல்லியமான எண் கணிதத்தில், அதாவது ஃப்ளோட்டிங் - பாயிண்ட் பிழைகளைப் புறக்கணிக்கின்றன). இருப்பினும், DFT ஐ தோராயமாகக் கணக்கிடும் ஒரு சில "FFT" வழிமுறைகளும் முன்மொழியப்பட்டுள்ளன, அவை அதிகமான கணக்கீடுகளின் சிரமத்துடன் ஒப்பிடுகையில் சீரற்ற முறையிலான மிகச் சிறிய பிழைகளைக் கொண்டிருக்கலாம். அது போன்ற வழிமுறைகள் அதிகரிக்கப்பட்ட வேகம் அல்லது பிற பண்புகளுக்கான தோராயமாக்கல் பிழைகளைக் கையாளுகின்றன. எடுத்துக்காட்டுக்கு, ஈடில்மேன் மற்றும் பலரால் முன்மொழியப்பட்ட (1999) ஒரு தோராய FFT வழிமுறையானது இணைக் கணக்கீட்டுக்கான குறைவான தகவல்தொடர்பு தேவைகளைக் கொண்டுள்ளது. அதற்கு ஒரு வேகப் பன்முக முறை உதவியாக உள்ளது. குவோ மற்றும் பர்ரஸ் அவர்களால் முமொழியப்பட்ட (1996) ஒரு சிற்றலை-அடிப்படையிலான தோராய FFT, ஒரு துல்லியமான FFT கொண்டு சாத்தியப்படுவதை விட அடர்த்தியற்ற உள்ளீடுகள்/வெளியீடுகளை (நேரம்/அதிர்வெண் இடமறிதல்) முக்கியமாகக் கருத்தில்கொள்கிறது. DFT வெளியீடுகளுக்கான துணைக்குழுவின் தோராயக் கணக்கீட்டுக்கான மற்றொரு வழிமுறை ஷெண்ட்டோவ் மற்றும் பலரால் கண்டுபிடிக்கப்பட்டது. (1995). இருப்பினும், அடர்த்தியற்ற மற்றும் அடர்த்தியான ஆகிய இரு வகை தரவுகளுக்கும் ஈடில்மேன் வழிமுறையே சிறப்பாகப் பயன்பட்டது. ஏனெனில் அது தரவின் சுருக்கக்கூடிய தன்மையை அடிப்படையாகக் கொண்டிருக்காமல் ஃபூரியே அணியின் சுருக்கக்கூடிய தன்மையை அடிப்படையாகக் கொண்டிருக்கிறது.

புள்ளி இலக்க எண் கணிதங்கள் பயன்படுத்தப்படும் போது "துல்லியமான" FFT வழிமுறைகளிலும் பிழைகள் உள்ளன வரையறுக்கப்பட்ட-துல்லியம், ஆனால் இந்தப் பிழைகள் வழக்கமாக மிகச் சிறியன. பெரும்பாலான FFT வழிமுறைகள், எ.கா. கூலி-டக்கி, சிறந்த எண்ணியல் பண்புகளைக் கொண்டுள்ளன. ε என்பது மெஷின் ஃப்ளோட்டிங் பாயிண்ட் தொடர்பு நிலையாக உள்ள, நீவ் DFT சூத்திரத்துக்கான (ஜெண்டில்மேன் மற்றும் சாண்டி, 1966) O(εN ^3/2) உடன் ஒப்பிடுகையில் கூலி டக்கி வழிமுறைக்கான தொடர்புப் பிழையிலான மேல் வரம்பானது O(ε log N ) ஆக உள்ளது. உண்மையில், சராசரி வர்க்கமூலப் (rms) பிழைகள் இந்த மேல் வரம்புகளைக் காட்டிலும் சிறந்தவை. அவற்றின் மதிப்பு கூலி டக்கி முறைக்கு O(ε √log N ) என்றும் நீவ் DFTக்கு (ஸ்கேட்ஸ்மேன், 1996) O(ε √N ) என்றும் உள்ளது. இருப்பினும், இந்த முடிவுகள் FFT இல் (அதாவது, திரிகோணமிதி சார்புகளின் மதிப்புகள்) பயன்படுத்தப்படும் சுழற்றுக் காரணிகளின் துல்லியத் தன்மையால் நுட்பமாக பாதிக்கப்படக்கூடியவை, மேலும் கவனக்குறைவான FFT செயல்படுத்தல்கள் மிக மோசமான துல்லியத்தன்மையைக் கொண்டிருப்பது அரிதானதல்ல, எ.கா. அவை துல்லியமற்ற திரிகோணமிதி மறுநிகழ்வு சூத்திரங்களைப் பயன்படுத்தலாம். ரேடர்-ப்ரென்னர் வழிமுறை போன்று, கூலி டக்கி தவிர்த்த சில FFTகள், உண்மையில் குறைவான நம்பகத்தன்மை கொண்டவை.

நிலையான-புள்ளி எண்கணிதத்தில், FFT வழிமுறைகளால் சேர்ந்த வரையறுக்கப்பட்ட-துல்லியப் பிழைகள் மிக மோசமானவை, கூலி டக்கி வழிமுறைக்கு (வெல்ச், 1969) அவற்றின் rms பிழைகள் O(√N ) என்ற அளவில் உள்ளன. மேலும், துல்லியத் தன்மை இழப்பதைக் குறைப்பதற்காக இந்த அளவு துல்லியமான தன்மையை அடைவதற்கும் கூட, அளவிடுவதில் அதிக கவனம் தேவைப்படுகிறது. மேலும் நிலையான-புள்ளி FFT வழிமுறைகளில் கூலி-டக்கி போன்ற பிரித்துக்கணக்கிடலின் ஒவ்வொரு இடை நிலையிலும் மறு அளவீடும் தேவைப்படுகிறது.

ஒரு FFT செயல்படுத்தலின் சரியான தன்மையை உறுதிப்படுத்த, உருமாற்றத்தின் சீரற்ற உள்ளீடுகளின் நேரியல் தன்மை, தூண்டல் எதிர்வினை மற்றும் கால உருமாற்றப் பண்புகளைச் சோதிக்கும் ஒரு எளிய செயலின் மூலம் (எர்கன், 1995) O(N log N ) நேரத்தில், உறுதியான உத்தரவாதங்களைப் பெற முடியும்.

வழிமுறைகள்

கூலி–டக்கி வழிமுறை

முதன்மைக் கட்டுரை: Cooley–Tukey FFT algorithm

தற்போது வழங்கிவரும் FFT-க்களில் மிகப் பொதுவான ஒன்று, கூலி–டக்கி வழிமுறையே ஆகும். இது ஒரு பிரித்து வெல்லும் வழிமுறையாகும். இதில் N = N ₁N ₂ என்பது போன்று சிக்கலான அளவுள்ள ஒரு DFT, N ₁ மற்றும் N ₂ என்ற அளவிலான பல சிறு DFTகளாக தொடர்ந்து மீண்டும் மீண்டும் உடைக்கப்படுகிறது. இதில் வழக்கமாக (ஜெண்ட்டில்மேன் மற்றும் சாண்டி ஆகியோரின் பெயரின் நினைவாக, 1966) சுழல் காரணிகள் என அழைக்கப்படும் ஒன்றின் சிக்கலெண் மூலங்களால் O(N) முறை பெருக்கப்படும் செயலும் நடைபெறுகிறது.

இந்த முறை (மற்றும் FFT என்ற பொதுவான கருத்து) ஜே. டபள்யூ. கூலி மற்றும் ஜே. டபள்யூ. டக்கி ஆகியோரால் 1965 ஆம் ஆண்டு வெளியீட்டினால் பிரபலமானது, ஆனால் அந்த இரண்டு ஆசிரியர்களும், கார்ல் ஃப்ரெட்ரிக் காஸ் என்பவரால் 1805 ஆம் ஆண்டுவாக்கில் கண்டுபிடிக்கப்பட்ட (மேலும் பலரால் பல முறை குறைந்த வடிவத்தில் மீண்டும் கண்டுபிடிக்கப்பட்டது) முறையையே தனிப்பட்ட முறையில் வழிமுறையை மீண்டும் கண்டுபிடித்தனர் என்பது பின்னர் கண்டுபிடிக்கப்பட்டது (ஹெயிட்மேன் & பர்ரஸ், 1984).

ஒவ்வொரு படியிலும் ஒரு உருமாற்றத்தை $N/2$ என்ற அளவு கொண்ட இரு துண்டுகளாகப் பிரிப்பதே கூலி–டக்கி வழிமுறையின் மிகவும் பிரபலமான பயனாகும், மேலும் இதனால் அடுக்கு இரண்டு என்ற அளவுகளுக்கு மட்டுமே என்ற வரம்பை உடையதாக உள்ளது, ஆனால் பொதுவாக எந்தக் காரணியாக்கத்தையும் பயன்படுத்த முடியும் (காஸ் மற்றும் கூலி/டக்கி ஆகிய இரு முறைகளுக்குமே இது பிரபலமானதாகும்). இவை முறையே ரேடிக்ஸ்-2 மற்றும் மிக்ஸ்டு-ரேடிக்ஸ் நிகழ்வுகள் என அழைக்கப்படுகின்றன, (மேலும் ஸ்பிளிட்-ரேடிக்ஸ் FFT போன்ற பிற வடிவங்களுக்கு தனித்தனிப் பெயருள்ளன). அடிப்படைக் கருத்தானது மீண்டும் மீண்டும் இடம்பெறுவது எனினும், மிகவும் பழைய செயல்படுத்தல்கள் வெளிப்படையான மறுநிகழ்வுகளைத் தவிர்ப்பதற்காக வழிமுறையை மீண்டும் மாற்றியமைத்தன. கூலி–டக்கி வழிமுறை DFT ஐ சிறு DFTகளாக பிரிப்பதாலும், கீழே விவரிக்கப்பட்டுள்ளனவற்றைப் போன்ற DFTக்கான பிற எந்த வழிமுறைகளுடனும் இதைச் சேர்த்துப் பயன்படுத்தலாம்.

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

முதன்மைக் கட்டுரைகள்: Prime-factor FFT algorithm, Bruun's FFT algorithm, Rader's FFT algorithm, மற்றும் Bluestein's FFT algorithm

கூலி டக்கி முறையிலிருந்து வேறுபட்டுள்ள பிற FFT வழிமுறைகளும் உள்ளன. இணை பகா எண் $N_{1}$ மற்றும் $N_{2}$ என்று உள்ள $N=N_{1}N_{2}$ க்கு, கூலி டக்கியைப் போல, ஆனால் சுழல் காரணிகள் இன்றி DFT ஐ காரணிப்படுத்த, சைனீஸ் மீதித் தேற்றத்தை அடிப்படையாகக் கொண்ட பகா-காரணி (கூட்-தாமஸ்) வழிமுறையைப் (PFA) பயன்படுத்தலாம். ரேடர்-ப்ரென்னர் வழிமுறை (1976) ஒரு கூலி-டக்கி வழிமுறையைப் போன்ற காரணிப்படுத்தலாகும், ஆனால் அதில் முழுக்க கற்பனையான சுழல் காரணிகள் உள்ளன. அதில் அதிகரிக்கப்பட்ட கூட்டல்களுடன் எண்ணியல் நிலைத்தன்மை குறைந்து, பெருக்கல்கள் குறைவாக உள்ளன. பின்னர் அது கூலி-டக்கியின் ஸ்பிளிட்-ரேடிக்ஸ் வகையால் வெல்லப்பட்டது (அது துல்லியத் தன்மையை இழக்காமல், குறைவான கூட்டல்களுடன் அதே பெருக்கல்களை சாத்தியமாக்குகிறது). மீண்டும் மீண்டும் DFT ஐ சிறிய செயல்பாடுகளாகக் காரணிப்படுத்தும் DFTகளல்லாத பிற வழிமுறைகளில் ப்ரன் மற்றும் QFT வழிமுறைகள் ஆகியன அடங்கும். (ரேடர்-ப்ரன் மற்றும் QFT வழிமுறைகள் அடுக்கு இரண்டு என்ற அளவுகளுக்காக முன்மொழியப்பட்டன, ஆனால் அவற்றை சிக்கலான $n$ க்குப் பயன்படுத்துவது சாத்தியமல்ல. ப்ரன்னின் வழிமுறை தனிப்பட்ட சிக்கலான அளவுகளுக்கும் பொருந்துகிறது.) ப்ரன்னின் வழிமுறை, குறிப்பாக, FFT ஐ $z^{N}-1$ பல்லுறுப்புக்கோவையின் மீண்டும் மீண்டும் நிகழும் ஒரு காரணிப்படுத்தலாகப் புரிதல் விளக்கம் செய்தலை அடிப்படையாகக் கொண்டதாகும், இங்கு $z^{M}-1$ வகை மெய் குணகப் பல்லுறுப்புக் கோவைகளாகக் காரணியாக்கம் செய்கிறது, மேலும் $z^{2M}+az^{M}+1$.

மற்றொரு பல்லுறுப்புக் கோவைக் கண்ணோட்டம் வினோக்ராட் வழிமுறையால் பயன்படுத்தப்பட்டது, அது $z^{N}-1$ ஐ சைக்ளோட்டமிக் பல்லுறுப்புக் கோவைகளாகக் காரணியாக்கம் செய்கிறது—இவை பெரும்பாலும் 1, 0 அல்லது −1 என்ற குணகங்களாகும், மேலும் அதனால் இதற்கு (இருந்தால்) சில பெருக்கல்கள் தேவைப்படுகின்றன, ஆகவே வினோக்ராட் வழிமுறையை குறைந்தபட்ச பெருக்கல்கள் கொண்ட FFTகளைப் பெறப் பயன்படுத்தலாம். மேலும் அது பெரும்பாலும் சிறு காரணிகளுக்கான வழிமுறைகளைக் கண்டறியப் பயன்படுத்தப்படுகிறது. உண்மையில், DFT ஐ வெறும் $O(N)$ விகிதமுறாப் பெருக்கல்களை மட்டும் கொண்டு கணக்கிட முடியும் என வினோக்ராட் வழிமுறை காண்பித்தது. இதனால் அடுக்கு இரண்டு என்ற அளவுகளுக்கான பெருக்கல்களின் எண்ணிக்கைக்கான அடையத்தக்க கீழ் வரம்பு நிரூபிக்கப்பட்டது. துரதிருஷ்டவசமாக, இதற்கு பல கூட்டல்கள் தேவைப்பட்டது, இந்த பிரதிபலன் சிரமமானது வன்பொருள் பெருக்கிகளைக் கொண்டுள்ள தற்கால செயலிகளில் ஆதரிக்கத்தக்கதல்ல. குறிப்பாக, வினோக்ராட் வழிமுறை PFA ஐயும் அதே போல் பகா அளவு FFTகளுக்கான ரேடரின் ஒரு வழிமுறையையும் பயன்படுத்துகிறது.

ரேடரின் வழிமுறை, பெருக்கத்தக்க குழு மட்டு பகா $N$ க்கான உருவாக்கியின் இருப்பையும் பயன்படுத்துகிறது. அது $n$ பகா அளவுள்ள ஒரு DFT ஐ $N-1$ அளவுள்ள சுழற்சித் தன்மையுள்ள சுழற்சியாகக் (சிக்கலான) குறிப்பிடுகிறது. அதை சுழற்சித் தேற்றத்தைப் பயன்படுத்தி சாதாரண FFT இணையைக் கணக்கிடுவதன் மூலம் கணக்கிட முடியும் (இருப்பினும் வினோக்ராட் பிற சுழற்சி முறைகளையும் பயன்படுத்துகிறது). மற்றொரு பகா-அளவு FFT எல். ஐ. ப்ளூஸ்டெயினால் முன்மொழியப்பட்டது. அது சில நேரங்களில் சிர்ப்-z வழிமுறை என அழைக்கப்பட்டது. அதுவும் அதே DFT ஐ சுழற்சியாகக் குறிப்பிடுகிறது, ஆனால் இதில் $nk=-(k-n)^{2}/2+n^{2}/2+k^{2}/2$ முற்றொருமையின் மூலம் கண்டறியப்படும் எண் அதே அளவைப் (இதை அடுக்கு இரண்டு என்ற அளவுக்கு பூச்சிய மென்மைப்படுத்தலுக்குட்படுத்த முடியும், மேலும் இதை ரேடிக்ஸ்-2 கூலி-டக்கி மூலம் கணக்கிட முடியும்) பயன்படுத்துகிறது.

மெய் மற்றும்/அல்லது சமச்சீர் தரவுகளுக்கென பிரத்யேகமான FFT வழிமுறைகள்

பல பயன்பாடுகளில், DFT க்கான உள்ளீடு தரவுகள் முழுமையாக மெய் எண்களாகும். இந்நிலையில் வெளியீடுகள் சமச்சீர் நிபந்தனைக்குட்பட்டிருக்கின்றன.

$X_{N-k}=X_{k}^{*},$

மேலும், இந்தச் சூழ்நிலைக்காக செயல்திறன் மிக்க FFT வழிமுறைகள் உருவாக்கப்பட்டன (காண்க: எ.கா. சோரன்சென், 1987). ஒரு அணுகுமுறையில் ஒரு சாதாரண வழிமுறையை (எ.கா. கூலி-டக்கி) எடுத்துக்கொண்டு அதன் கணக்கீட்டின் தேவையற்ற பகுதிகளை நீக்கிவிட்டு பயன்படுத்தப்படுவதால், நேரம் மற்றும் நினைவகம் ஆகிய இரண்டிலும் கிட்டத்தட்ட இரண்டு காரணியளவு சேமிக்கப்படுகிறது. மாற்று முறையாக, ஒரு இரட்டை -நீளமுள்ள மெய்-உள்ளீடு DFT ஐ அதன் நீளத்தில் பாதியளவுள்ள ஒரு சிக்கலான DFT ஆகக் குறிப்பிடுவதும் சாத்தியமே (அதன் மெய் மற்றும் கற்பனை பகுதிகள் அசல் தரவின் இரட்டை/ஒற்றை உறுப்புகளாக உள்ளன). இது O(N ) பின் செயலாக்க செயல்பாடுகளுக்கு அடுத்து கிடைக்கின்றன.

இலக்கமியல் ஹார்ட்லி உருமாற்றத்தைப் (DHT) பயன்படுத்தி மெய்-உள்ளீடு DFTகள் செயல்திறன் மிக்க வகையில் கணக்கிட முடியும் என ஒரு காலத்தில் நம்பப்பட்டது, ஆனால் அதனைத் தொடர்ந்து சிறப்பாக்கம் செய்யப்பட்ட மெய்-உள்ளீடு DFT வழிமுறையில் (FFT) வழக்கமாக அதே எண்ணிக்கை உள்ளீடுகளுக்கு அதற்குரிய DHT வழிமுறையில் (FHT) தேவைப்படுவதை விட குறைவான செயல்பாடுகளே தேவைப்பட்டது என விவாதிக்கப்பட்டது. ப்ரன்னின் வழிமுறை (மேலே கூறப்பட்டது), மெய் உள்ளீடுகளைப் பயன்படுத்திக்கொள்ள ஆரம்பத்தில் முன்மொழியப்பட்ட மற்றொரு முறையாகும், ஆனால் அது பிரபலமாக நிரூபிக்கப்படவில்லை.

இரட்டை/ஒற்றை சமச்சீர்மை கொண்ட நிகழ்வுகளுக்கான மேலும் சில FFT சிறப்பாக்கங்களும் உள்ளன. அவற்றின் நிகழ்வுகளில் ஒன்று மற்றதன் (கிட்டத்தட்ட) இரு காரணியளவு நேரத்தையும் நினைவகத்தையும் சேமிக்கிறது. மேலும் DFT ஆனது தனிப்பட்ட கொசைன்/சைன் உருமாற்றமாக (உருமாற்றங்களாக) மாறுகிறது (DCT/DST). ஒரு FFT வழிமுறையை இந்த நிகழ்வுக்காக மாற்றியமைப்பதற்கு பதிலாக, DCTகள்/DSTகள் O(N ) முன்/பின் செயலாக்கங்களுடன் சேர்ந்த FFTகளின் மெய் தரவுகளின் மூலமாகவும் கணக்கிடலாம்.

பலபரிமாண FFTகள்

பலபரிமாண DFT கட்டுரையில் வரையறுக்கப்பட்டுள்ளபடி, பின்வரும் பல பரிமாண DFT

$X_{\mathbf {k} }=\sum _{\mathbf {n} =0}^{\mathbf {N} -1}e^{-2\pi i\mathbf {k} \cdot (\mathbf {n} /\mathbf {N} )}x_{\mathbf {n} }$

ஆனது $\mathbf {n} =(n_{1},n_{2},\ldots ,n_{d})$ முனைகளை உடைய $d$-பரிமாண வெக்டார் கொண்ட $x_{\mathbf {n} }$ எனும் ஒரு அணியை $d$ குழு கூடு கூட்டல்களுக்கு (ஒவ்வொரு $j$ க்கும் $n_{j}=0\ldots N_{j}-1$ க்கும் மேலாக) மாற்றுகிறது. இதில் பிரிவு $\mathbf {n} /\mathbf {N}$, $\mathbf {n} /\mathbf {N} =(n_{1}/N_{1},\cdots ,n_{d}/N_{d})$ என வரையறுக்கப்படுகிறது, அது ஒவ்வொரு உறுப்புவாரியாக செயல்படுத்தப்படுகிறது. சமமான விதத்தில், அது ஒற்றைப் பரிமாண DFTகளின் $d$ குழுக்களின் தொடர்ச்சியான கூட்டமைப்பே ஆகும். இது ஒரு நேரத்தில் ஒரு பரிமாணத்தின் வழியாக மட்டுமே (ஏதேனும் ஒரு வரிசையில்) செயல்படுத்தப்படுகிறது.

இந்தக் கணக்கீட்டியல் கருத்துக் கண்ணோட்டமானது எளிய மற்றும் மிகப் பொதுவான பல பரிமாண DFT வழிமுறையை வழங்குகிறது. அது (கீழே விவரிக்கப்படும் இரு பரிமாண நிகழ்வைக் கொண்டு) நிரை-நிரல் வழிமுறை என அழைக்கப்படுகிறது. அதாவது, ஒருவர் வெறுமென $d$ ஒற்றைப் பரிமாண FFTகளின் தொடரை மட்டுமே செயல்படுத்துகிறார் (மேலே கூறப்பட்ட வழிமுறைகளில் ஏதேனும் ஒன்றின் மூலம்): முதலில் $n_{1}$ பரிமாணத்தின் வழியே மாற்றம் செய்கிறீர்கள், பின்னர் $n_{2}$ பரிமாணம், இதே போல் தொடர்கிறீர்கள் (அல்லது உண்மையில் எந்த வரிசையிலும் இது சரியாக முடிவைக் கொடுக்கும்). இந்த முறையானது $O(N\log N)$ சிக்கலான தன்மையைக் கொண்டிருப்பதாக எளிதாக நிரூபிக்கப்பட்டது. இதில் $N=N_{1}N_{2}\cdots N_{d}$ என்பது மாற்றப்பட்ட தரவுப் புள்ளிகளின் மொத்த எண்ணிக்கையாகும். குறிப்பாக, $N_{1}$, போன்ற அளவுடைய $N/N_{1}$ உருமாற்றங்கள் உள்ளன, ஆகவே FFTகளின் தொடரின் சிக்கலான தன்மை பின்வருமாறு:

${\begin{aligned}&{}\qquad {\frac {N}{N_{1}}}O(N_{1}\log N_{1})+\cdots +{\frac {N}{N_{d}}}O(N_{d}\log N_{d})\\[6pt]&=O\left(N\left[\log N_{1}+\cdots +\log N_{d}\right]\right)=O(N\log N).\end{aligned}}$

இரு பரிமாணங்களில், $x_{\mathbf {k} }$ ஐ ஒரு $n_{1}\times n_{2}$ அணியாகக் கருதலாம். மேலும் இந்த வழிமுறையானது முதலில் அணியின் அனைத்து நிரைகளின் FFT ஐ செயல்படுத்தி பின்னர் அனைத்து நிரல்களின் FFT ஐ செயல்படுத்தும் முறையைக் கொண்டது (அல்லது மறுதிசையில்), இதனாலே இம்முறைக்கு இந்தப் பெயர் வந்தது.

இரு பரிமாணத்திற்கும் அதிகமான நிகழ்வில், பல சமயங்களில் பதுக்கக இட அமைப்பை மீண்டும் மீண்டும் குழுப்படுத்துதல் என்பது பயன்மிக்கதாக இருக்கும். எடுத்துக்காட்டுக்கு, ஒரு முப்பரிமாண FFT ஆனது முதலில் ஒவ்வொரு நிலையான $n_{1}$ க்குமான ஒவ்வொரு தள "ஸ்லைஸின்" இரு-பரிமாண FFTகளை செயல்படுத்தலாம், பின்னர் அது ஒற்றைப் பரிமாண FFTகளை $n_{1}$ திசையில் செயல்படுத்தலாம். பொதுவாக, ஒரு தொலைத்தொடுகோட்டு சிறப்பு பதுக்கக-நினைவகக் குறை வழிமுறையில், மீண்டும் மீண்டும் மாற்றம் செய்யப்படும் பரிமாணங்களை மீண்டும் மீண்டும் $(n_{1},\cdots ,n_{d/2})$ மற்றும் $(n_{d/2+1},\cdots ,n_{d})$ என இரு குழுவாகப் பிரிக்கும் நிகழ்வு இடம்பெறுகிறது ($d$ என்பது இரட்டையாக இல்லாதபட்சத்தில் அது முழுமையாக்கும்) (காண்க: ஃப்ரிகோ மற்றும் ஜான்சன், 2005). இருப்பினும், இது இரு-நிரல் வழிமுறையின் நேர்பாங்கான வகையாக உள்ளது, இதற்கு அடிப்படை நிகழ்வாக மொத்தம் ஒற்றைப் பரிமாண FFT வழிமுறையே தேவைப்படுகிறது, மேலும் இதில் $O(N\log N)$ சிக்கலான தன்மை மட்டுமே உள்ளது. மாற்றம் செய்யப்படும் பரிமாணங்களுக்கிடையே அணி இடமாற்றத்தைச் செயல்படுத்துவது என்பது இன்னுமொரு வகையாகும், ஆகவே உருமாற்றமானது அருகாமைத் தரவின் மீதே செயல்படுகிறது. குறிப்பாக இது அருகாமையிலல்லாத தரவை அணுகுவது என்பது அதிக நேரம் எடுத்துக்கொள்ளும் நிகழ்வாக உள்ள, மையத்திற்கு புறத்தேயான மற்றும் பகிரப்பட்ட நினைவக சூழ்நிலைகளுக்கு முக்கியமானதாகும்.

நிரை-நிரல் வழிமுறையிலிருந்து வேறுபட்டுள்ள பிற பலபரிமாண FFT வழிமுறைகளும் உள்ளன, இருப்பினும் அவை அனைத்திலும் $O(N\log N)$ சிக்கலான தன்மை உள்ளது. மிக எளிய நிரல்-நிரை அல்லாத FFT வெக்டார்-ரேடிக்ஸ் FFT வழிமுறையாக இருக்கலாம், அது வழக்கமான கூலி-டக்கி வழிமுறையின் பொதுமையாக்கலாக உள்ளது, அதில் நாம் உருமாற்றப் பரிமாணங்களை ஒவ்வொரு படியிலும் $\mathbf {r} =(r_{1},r_{2},\cdots ,r_{d})$ என்ற ரேடிக்ஸ் வெக்டாரால் வகுக்கிறோம். (இதில் பதுக்கக நன்மைகளும் இருக்கலாம்.) அனைத்து ரேடிக்ஸ்களும் சமமாக இருப்பது என்பது வெக்டார்-ரேடிக்ஸின் எளிய நிகழ்வாகும் (எ.கா. வெக்டார்-ரேடிக்ஸ்-2, பரிமாணங்கள் அனைத்தையும் இரண்டால் வகுக்கிறது), ஆனால் இது அவசியம் என்பதல்ல. ஒரு நேரத்தில் ஒன்றல்லாத ஒரே ஒரு ரேடிக்ஸைக் கொண்டுள்ள வெக்டார், அதாவது $\mathbf {r} =(1,\cdots ,1,r,1,\cdots ,1)$, கட்டாயமாக ஒரு நிரை-நிரல் வழிமுறையாகவே இருக்கும். மற்ற மிகச் சிக்கலான முறைகளில் நுஸ்ஸம்பரின் (1977) பல்லுறுப்புக்கோவை உருமாற்ற வழிமுறைகள் போன்றவை அடங்கும். அதன்படி உருமாற்றங்கள் சுழற்சிகளாகவும் பல்லுறுப்புக்கோவை விளைபலன்களாகவும் கருதப்படுகின்றன. மேலும் தகவல்களுக்கும் குறிப்புதவிகளுக்கும் டுஹாமெல் மற்றும் வெட்டெர்லி (1990) என்பதைக் காண்க.

பிற பொதுமையாக்கல்கள்

N ² கணுக்களைக் கொண்ட S ² என்னும் கோளத்தின் மீதான கோள இசைவுக்கான ஒரு O (N ^5/2 log N ) பொதுமையாக்கல் மோலென்கேம்ப் என்பவரால்(1999) விவரிக்கப்பட்டது, அவருடைய விளக்கத்துடன் O (N ² log² N ) என்ற சிக்கலான தன்மையைக் கொண்டிருப்பதாகக் கூறப்படும் (ஆனால் நிரூபிக்கப்படாத) வழிமுறையும் வழங்கப்பட்டது. மோலென்கேம்ப் லிப்ட்ஃப்ஷ் நூலகத்திலான பரணிடப்பட்டது 2010-06-23 at the வந்தவழி இயந்திரம் செயல்படுத்தலையும் வழங்குகிறது. O (N ² log N ) என்ற சிக்கலான தன்மை கொண்ட ஒரு கோள-இசைவு வழிமுறை ராக்லின் மற்றும் டைகர்ட் (2006) ஆகியோரால் விவரிக்கப்பட்டது.

பல குழுக்களும் சம இடைவெளிப்படுத்தாத தரவுகளுக்கான "FFT" வழிமுறைகளை வெளியிட்டுள்ளன. அவை பாட்ஸ் மற்றும் பலவற்றால் மறுஆய்வு செய்யப்பட்டன. (2001). இது போன்ற வழிமுறைகள் DFT ஐ மிகச் சரியான விதத்தில் கணக்கிடுவதில்லை (அது சம இடைவெளித் தரவுகளுக்கு மட்டுமே வரையறுக்கப்பட்டதாகும்), ஆனால் அதற்கு மாறாக சில தோராயமாக்கல்கள் (ஒரு சீரற்ற இலக்கமியல் ஃபூரியே உருமாற்றம் அல்லது பெரும்பாலும் தோராயமாகவே கணக்கிடப்படுவதாகும் NDFT) உள்ளன.

குறிப்புதவிகள்

• என். ப்ரன்னர் மற்றும் சி. ரேடர், 1976, அ நியூ ப்க்ரின்சிப்பல் ஃபார் ஃபாஸ்ட் ஃபோரியர் ட்ரான்ஸ்ஃபர்மேஷன், IEEE அக்கௌஸ்டிக்ஸ், ஸ்பீச் & சிக்னல் ப்ராசசிங் 24 : 264-266.
• Brigham, E.O. (2002), The Fast Fourier Transform, New York: Prentice-Hall
• கூலி, ஜேம்ஸ் டபள்யூ., மற்றும் ஜான் டபள்யூ. டக்கி, 1965, "அன் அல்காரிதம் ஃபார் த மெஷின் கால்குலேஷன் ஆஃப் அ காம்ப்ளெக்ஸ் ஃபோரியர் சீரியஸ்," மேத். கம்ப்யூட். 19 : 297–301.
• தாமஸ் எச். கார்மன், சார்லஸ் இ. லெய்சர்சன், ரொனால்ட் எல். ரிவெஸ்ட், அண்ட் க்ளிஃபோர்டு ஸ்டெயின், 2001. இண்ட்ரடக்ஷன் டு அல்காரிதம்ஸ் , 2ஆம் பதிப்பு MIT ப்ரஸ் அண்ட் மெக்க்ராவ்-ஹில். பன்னாட்டுத் தரப்புத்தக எண் 0-262-03293-7. குறிப்பாக அதிகாரம் 30, "பாலினாமியல்ஸ் அண்ட் த FFT."
• ப்யேர் டுஹாமெல், 1990, [4], IEEE ட்ரான்ஸ். அக்கௌஸ்ட். ஸ்பீச். சிக். ப்ராச. 38 : 1504-151.
• பி. டுஹாமெல் அண்ட் எம். வெட்டர்லி, 1990, Fast Fourier transforms: a tutorial review and a state of the art , சிக்னல் ப்ராசசிங் 19 : 259–299.
• ஏ. ஈடில்மேன், பி. மெக்கார்க்வோடேல், அண்ட் எஸ். டோலிடோ, 1999, The Future Fast Fourier Transform? , SIAM ஜே. சை. கம்ப்யூட்டிங் 20 : 1094–1114.
• ஃபண்டா எர்கன், 1995, Testing multivariate linear functions: Overcoming the generator bottleneck , ப்ராச. 27த் ACM சிம்போசியம் ஆன் த தியரி ஆஃப் கம்ப்யூட்டிங் : 407–416.
• எம். ஃப்ரிகோ அண்ட் எஸ். ஜி. ஜான்சன், 2005, "த டிசைன் அண்ட் இம்ப்ளிமெண்ட்டேஷன் ஆஃப் FFTW3," ப்ரொசீடிங்ஸ் ஆஃப் த IEEE 93 : 216–231.
• கார்ல் ஃப்ரெட்ரிக் காஸ், 1866. "நச்லாஸ்: Theoria interpolationis methodo nova tractata," வெர்க்கே பேண்ட் 3 , 265–327. Göttingen: Königliche Gesellschaft der Wissenschaften.
• டபள்யூ. எம். ஜெண்டில்மேன் அண்ட் ஜி. சாண்டி, 1966, "ஃபாஸ்ட் ஃபோரியர் ட்ரான்ஸ்ஃபார்ம்ஸ்—ஃபார் ஃபன் அண்ட் ப்ராஃபிட்," ப்ராச. AFIPS 29 : 563–578.
• எச். குவோ அண்ட் சி. எஸ். பர்ரஸ், 1996, Fast approximate Fourier transform via wavelets transform , ப்ராச. SPIE Intl. Soc. Opt. இங்கி. 2825 : 250–259.
• ------- அண்ட் ஜி. ஏ. சிட்டான், 1994, The Quick Discrete Fourier Transform , ப்ராச. IEEE கான்ஃப். அக்கௌஸ்ட். ஸ்பீச் அண்ட் சிக். ப்ராசசிங் (ICASSP) 3 : 445–448.
• ஹெயிட்மேன், எம். டி., டி. எச். ஜான்சன் அண்ட் சி. எஸ். பர்ரஸ், "காஸ் அண்ட் த ஹிஸ்டரி ஆஃப் த ஃபாஸ்ட் ஃபோரியர் ட்ரான்ஸ்ஃபார்ம்," IEEE ASSP இதழ், 1, (4), 14–21 (1984).
• மைக்கேல் டி. ஹெயிட்மேன் அண்ட் சி. சிட்னி பர்ரஸ், 1986, ஆன் த நம்பர் ஆஃப் மல்ட்டிப்ளிகேஷன்ஸ் நெசசரி டு கம்ப்யூட் அ லெண்த்-$2^{n}$ DFT, IEEE ட்ரான்ஸ். அக்கௌஸ்ட். ஸ்பீச் சிக். ப்ராச. 34 : 91-95.
• -------- அண்ட் டி. எச். ஜான்சன், 1984, காஸ் அண்ட் த ஹிஸ்டரி ஆஃப் த ஃபாஸ்ட் ஃபோரியர் ட்ரான்ஸ்ஃபார்ம், IEEE ASSP இதழ் 1 : 14–21.
• எஸ். ஜி. ஜான்சன் அண்ட் எம். ஃப்ரிகோ, 2007. "அ மாடிஃபைடு ஸ்பிளிட்-ரேடிக்ஸ் FFT வித் ஃபியூவர் அரித்மெட்டிக் ஆப்பரேஷன்ஸ்," IEEE ட்ரான்ஸ். சிக்னல் ப்ராசசிங் 55 (1): 111–119.
• டி. லண்டி அண்ட் ஜே. வேன் பஸ்கிர்க், 2007. "அ ஃஇயூ மேட்ரிக்ஸ் அப்ரோச் டு ரியல் FFTஸ் அண்ட் கன்வல்யூஷன்ஸ் ஆஃப் லெண்த் 2^k," கம்ப்யூட்டிங் 80 (1): 23-45.
• ஜாக்வெஸ் மார்கன்ஸ்டன், 1973, Note on a lower bound of the linear complexity of the fast Fourier transform , J. ACM 20 : 305-306.
• எம். ஜே. மோலன்கேம்ப், 1999, "அ ஃபாஸ்ட் ட்ரான்ஸ்ஃபார்ம் ஃபார் ஸ்பெரிக்கல் ஹார்மோனிக்ஸ்", ஜே. ஃபோரியர் அனால். அப்ப்ளி. 5 , 159–184. (ப்ரீப்ரிண்ட் பரணிடப்பட்டது 2007-02-06 at the வந்தவழி இயந்திரம்)
• எச். ஜே. நுஸ்பாமர், 1977, Digital filtering using polynomial transforms , எலக்ட்ரானிக்ஸ் லெட். 13 : 386-387.
• வி. பேன், 1986, The trade-off between the additive complexity and the asyncronicity of linear and bilinear algorithms , இன்ஃபர்மேஷன் ப்ராச. லெட். 22 : 11-14.
• கிரிஸ்டோஸ் எச். பாப்படிமித்ரியோ, 1979, Optimality of the fast Fourier transform , ஜே. ACM 26 : 95-102.
• டி. பாட்ஸ், ஜி. ஸ்டெயிடில் அண்ட் எம். டாஸ்கி, 2001. "ஃபாஸ்ட் ஃபோரியர் ட்ரான்ஸ்ஃபார்ம்ஸ் ஃபார் நான் - ஈக்விஸ்பேஸ்டு டேட்டா: அ டுட்டோரியல்", இன்: ஜே.ஜே. பெனிடேட்டோ அண்ட் பி. ஃபெரெயிரா (ஆசிரியர்கள்.), மாடன் சேம்ப்ளிங் தியரி: மேத்தமட்டிக்ஸ் அண்ட் அப்ளிகேஷன்ஸ் (பிர்க்காசர்).
• விளாடிமிர் ராக்ளின் அண்ட் மார்க் டைகர்ட், 2006, "ஃபாஸ்ட் அல்காரிதம்ஸ் ஃபார் ஸ்பெரிக்கல் ஹார்மோனிக் எக்ஸ்பேன்ஷன்ஸ்," SIAM ஜே. சை. கம்ப்யூட்டிங் 27 (6): 1903-1928.
• ஜேம்ஸ் சி. ஸ்காட்ஸ்மேன், 1996, அக்யூரசி ஆஃப் த டிஸ்க்ரீட் ஃபோரியர் ட்ரான்ஸ்ஃபார்ம் அண்ட் த ஃபாஸ்ட் ஃபோரியர் ட்ரான்ஸ்ஃபார்ம், SIAM ஜே. சை. கம்ப். 17 : 1150–1166.
• ஓ. வி. ஷெண்ட்டோவ், எஸ். கே. மித்ரா, யு. ஹியூட் அண்ட் ஏ. என். ஹாஸென், 1995, Subband DFT. I. Definition, interpretations and extensions , சிக்னல் ப்ராசசிங் 41 : 261–277.
• எச். வி. சோரன்சென், டி. எல். ஜோன்ஸ், எம். டி. ஹெயிட்மேன் அண்ட் சி. எஸ். பர்ரஸ், 1987, ரியல்-வேல்யூட் ஃபாஸ்ட் ஃபோரியர் ட்ரான்ஸ்ஃபார்ம் அல்காரிதம்ஸ், IEEE ட்ரான்ஸ். அக்கௌஸ்ட். ஸ்பீச் சிக். ப்ராசசிங் ASSP-35 : 849–863. கரக்ஷன்ஸ் டு "ரியல்-வேல்யூட் ஃபாஸ்ட் ஃபோரியர் ட்ரான்ஸ்ஃபார்ம் அல்காரிதம்ஸ்"
• பீட்டர் டி. வெல்ச், 1969, அ ஃபிக்ஸ்டு-பாயிண்ட் ஃபாஸ்ட் ஃபோரியர் ட்ரான்ஸ்ஃபார்ம் எரர் அனாலிசிஸ், IEEE ட்ரான்ஸ். ஆடியோ எலக்ட்ரோ அக்கௌஸ்டிக்ஸ் 17 : 151–157.
• எஸ். வினோக்ராட், 1978, ஆன் கம்ப்யூட்டிங் த டிஸ்க்ரீட் ஃபோரியர் ட்ரான்ஸ்ஃபார்ம், மேத். கம்ப்யூட்டேஷன் 32 : 175-199.

புற இணைப்புகள்

• ஃபாஸ்ட் ஃபோரியர் ட்ரான்ஸ்ஃபார்ம்ஸ் , கொன்னெக்ஷன்ஸ் ஆன்லைன் புத்தகம் - ஆசிரியர் சி. சிட்னி பர்ரஸ்,- அதிகாரங்கள்: சி. சிட்னி பர்ரஸ், ஐவன் செல்ஸ்னிக், மார்க்கஸ் ப்யூஸ்கெல், மேட்டியோ ஃப்ரிகோ அண்ட் ஸ்டீவன் ஜி. ஜான்சன் (2008).
• FFT கால்குலேட்டர். பரணிடப்பட்டது 2009-08-23 at the வந்தவழி இயந்திரம்
• லின்க்ஸ் டு FFT கோட் அண்ட் இன்ஃபர்மேஷன் ஆன்லைன்.
• FFT ப்ரோக்ராமிங் இன் C++ — கூலி-டக்கி அல்காரிதம்.
• ஆன்லைன் ஆவணமாக்கல், இணைப்புகள், புத்தகம் மற்றும் குறியீடுகள்.
• யூசிங் FFT டு கன்ஸ்ட்ரக்ட் அக்ரிகேட் ப்ராபபிலிட்டி டிஸ்ட்ரிபியூஷன்ஸ்
• ஸ்ரீ வேலரத்னா, "30 இயர்ஸ் ஆஃப் FFT அனலைசர்ஸ் பரணிடப்பட்டது 2008-05-29 at the வந்தவழி இயந்திரம்", சௌண்ட் அண்ட் வைப்ரேஷன் (ஜனவரி 1997, 30ஆம் ஆண்டு வெளியீடு). அ ஹிஸ்டாரிக்கல் ரிவியூ ஆஃப் ஹார்ட்வேர் FFT டிவைசஸ்.
• FFT பேசிக்ஸ் அண்ட் கேஸ் ஸ்டடி யூசிங் மல்டி-இன்ஸ்ட்ருமெண்ட்
• FFT டெக்ஸ்ட்புக் நோட்ஸ், PPTஸ் அட் ஹோலிஸ்டிக் நியூமரிக்கல் மெத்தட்ஸ் இன்ஸ்டிட்டியூட்.