கேள்வி: விரைவு ஃபூரியே உருமாற்றம் என்பது என்ன?
பதில்: விரைவு ஃபூரியே உருமாற்றம் (FFT) என்பது இலக்கமியல் ஃபூரியே உருமாற்றத்தையும் (DFT) அதன் தலைகீழியையும் கணக்கிடுவதற்கான செயல்திறன் மிக்க வழிமுறையாகும். பல்வேறு பரந்த அளவிலான கணிதங்களுடன் சம்பந்தப்பட்ட பல வேறுபட்ட FFT வழிமுறைகள் உள்ளன, அவற்றில் எளிய சிக்கலெண் எண்கணிதத்திலிருந்து குழுக் கோட்பாடு மற்றும் எண் கோட்பாடு வரையிலான பல பிரிவுகள் அடங்கும். இந்தக் கட்டுரை கிடைக்கக்கூடிய உத்திகள் மற்றும் அவற்றின் பொதுவான பண்புகளில் சிலவற்றை மட்டும் மேலோட்டமாக விளக்குகிறது. தனிப்பட்ட வழிமுறைகள், கீழே பட்டியலிடப்பட்டுள்ள தனித்தனி துணைக் கட்டுரைகளில் விளக்கப்பட்டுள்ளன. ஒரு DFT ஆனது ஒரு தொடர்வரிசை மதிப்புகளை வெவ்வேறு அதிர்வெண்ணுள்ள கூறுகளாகப் பிரிக்கிறது. இந்தச் செயல்பாடானது பல துறைகளில் பயன்மிக்கதாகும் (உருமாற்றத்தின் பண்புகள் மற்றும் பயன்களுக்கு இலக்கமியல் ஃபூரியே உருமாற்றம் என்பதைக் காண்க) ஆனால் வரையறையிலிருந்து இதனை நேரடியாகக் கணக்கிடுவது என்பது நடைமுறையில் இயலாத அளவுக்கு மிகவும் மெதுவான செயலாகும். FFT என்பது அதே முடிவை விரைவாகக் கணக்கிடும் வழியாகும்: வரையறையைப் பயன்படுத்தி தெளிவான வழியில் ''N'' புள்ளிகளின் ஒரு DFT ஐக் கணக்கிடும் போது, O(N 2) எண்கணித செயல்பாடுகள் தேவைப்படுகின்றன. அதே நேரத்தில் இதே முடிவை ஒரு 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'' 0, ...., ''x'' ''N'' -1 ஆகியவை சிக்கலெண்கள் என்க. பின்வரும் சூத்திரத்தால் DFT வரையறுக்கப்படுகிறது : X_k = \sum_{n=0}^{N-1} x_n e^{-{i 2\pi k \frac{n}{N}}} \qquad k = 0,\dots,N-1. இந்த வரையறையை நேரடியாகக் கணக்கிடுவதற்கு ''O'' (''N'' 2) செயல்பாடுகள் தேவைப்படுகின்றன: அதற்கு ''N'' வெளியீடுகள் ''X'' ''k'' உள்ளன, மேலும் ஒவ்வொரு வெளியீட்டுக்கும் மொத்தம் ''N'' உறுப்புகள் தேவைப்படுகின்றன. ஒரு FFT என்பது இதே முடிவை O(''N'' log ''N'' ) செயல்பாடுகளில் கணக்கிடுவதற்கான முறையாகும். மேலும் துல்லியமாக, அறியப்பட்ட FFT வழிமுறைகள் அனைத்திற்குமே Θ(''N'' log ''N'' ) செயல்பாடுகள் அவசியமாகிறது (நுட்ப ரீதியாக, ''O'' என்பது ஒரு மேல் வரம்பையே குறிக்கிறது), இருப்பினும் இதை விடச் சிறந்த சிக்கலான தன்மை சாத்தியமற்றது என்பதற்கான நிரூபணம் இல்லை. ஒரு FFT இன் சேமிப்பை விளக்க, பல சிக்கலான பெருக்கல் மற்றும் கூட்டல்களைக் கருதுக. DFT இன் கூட்டுத்தொகையை நேரடியாகக் கணக்கிடுவதற்கு ''N'' 2 சிக்கலெண் பெருக்கலும் ''N'' (''N'' &nbsp;−&nbsp;1) சிக்கலெண் கூட்டலும் [அதில் 1 ஆல் பெருக்குதல் போன்ற சிறிய பல செயல்பாடுகளை நீக்குவதன் மூலம் ''O'' (''N'' ) செயல்பாடுகள் சேமிக்கப்பட முடியும்] தேவைப்படுகின்றன. மிகவும் பிரபலமான ''N'' இன் அடுக்கு 2 க்கான அடிமானம்-2 கூலி-டக்கி வழிமுறையில், இதே முடிவை வெறும் (''N'' /2)&nbsp;log2&nbsp;''N'' சிக்கலெண் பெருக்கல்கள் (இதிலும் 1 ஆல் பெருக்குதல் மற்றும் அது போன்ற எளிய செயல்பாடுகளைத் தவிர்ப்பதன் மூலம்) மற்றும் ''N'' &nbsp;log2''N'' சிக்கலெண் கூட்டல்கள் ஆகிய செயல்பாடுகளிலேயே கணக்கிட முடியும். நடைமுறையில், வழக்கமாக தற்கால கணினிகளிலான உண்மையான செயல்திறனானது எண் கணிதம் தவிர்த்த பிற காரணிகளால் கட்டுப்படுத்தப்படுகிறது. மேலும் சிக்கலான விஷயமாகவும் உள்ளது (காண்க: எ.கா., ஃப்ரிகோ & ஜான்சன், 2005), ஆனால் Θ(''N'' 2) இலிருந்து Θ(''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 ஆனது வழிமுறையின் வரைபடத்தின் சில குறிப்பிட்ட கருதுகோள்களின் அடிப்படையில் ''சிறந்ததாக'' உள்ளது என விவாதித்தார் (அவரது கருதுகோள்கள் பிற அம்சங்களுடன் ஒன்றின் மூலங்களிலுள்ள கூட்டல் உறுப்புகள் எதுவும் பயன்படுத்தப்படவில்லை என்பதையும் குறிப்பிடுகிறது). (இந்த விவாதமானது குறைந்தபட்சம் 2 N \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-க்களில் மிகப் பொதுவான ஒன்று, கூலி–டக்கி வழிமுறையே ஆகும். இது ஒரு பிரித்து வெல்லும் வழிமுறையாகும். இதில் ''N'' = ''N'' 1''N'' 2 என்பது போன்று சிக்கலான அளவுள்ள ஒரு DFT, ''N'' 1 மற்றும் ''N'' 2 என்ற அளவிலான பல சிறு DFTகளாக தொடர்ந்து மீண்டும் மீண்டும் உடைக்கப்படுகிறது. இதில் வழக்கமாக (ஜெண்ட்டில்மேன் மற்றும் சாண்டி ஆகியோரின் பெயரின் நினைவாக, 1966) சுழல் காரணிகள் என அழைக்கப்படும் ஒன்றின் சிக்கலெண் மூலங்களால் O(N) முறை பெருக்கப்படும் செயலும் நடைபெறுகிறது. இந்த முறை (மற்றும் FFT என்ற பொதுவான கருத்து) ஜே. டபள்யூ. கூலி மற்றும் ஜே. டபள்யூ. டக்கி ஆகியோரால் 1965 ஆம் ஆண்டு வெளியீட்டினால் பிரபலமானது, ஆனால் அந்த இரண்டு ஆசிரியர்களும், கார்ல் ஃப்ரெட்ரிக் காஸ் என்பவரால் 1805 ஆம் ஆண்டுவாக்கில் கண்டுபிடிக்கப்பட்ட (மேலும் பலரால் பல முறை குறைந்த வடிவத்தில் மீண்டும் கண்டுபிடிக்கப்பட்டது) முறையையே தனிப்பட்ட முறையில் வழிமுறையை மீண்டும் கண்டுபிடித்தனர் என்பது பின்னர் கண்டுபிடிக்கப்பட்டது (ஹெயிட்மேன் & பர்ரஸ், 1984). ஒவ்வொரு படியிலும் ஒரு உருமாற்றத்தை N / 2 என்ற அளவு கொண்ட இரு துண்டுகளாகப் பிரிப்பதே கூலி–டக்கி வழிமுறையின் மிகவும் பிரபலமான பயனாகும், மேலும் இதனால் அடுக்கு இரண்டு என்ற அளவுகளுக்கு மட்டுமே என்ற வரம்பை உடையதாக உள்ளது, ஆனால் பொதுவாக எந்தக் காரணியாக்கத்தையும் பயன்படுத்த முடியும் (காஸ் மற்றும் கூலி/டக்கி ஆகிய இரு முறைகளுக்குமே இது பிரபலமானதாகும்). இவை முறையே ரேடிக்ஸ்-2 மற்றும் மிக்ஸ்டு-ரேடிக்ஸ் நிகழ்வுகள் என அழைக்கப்படுகின்றன, (மேலும் ஸ்பிளிட்-ரேடிக்ஸ் FFT போன்ற பிற வடிவங்களுக்கு தனித்தனிப் பெயருள்ளன). அடிப்படைக் கருத்தானது மீண்டும் மீண்டும் இடம்பெறுவது எனினும், மிகவும் பழைய செயல்படுத்தல்கள் வெளிப்படையான மறுநிகழ்வுகளைத் தவிர்ப்பதற்காக வழிமுறையை மீண்டும் மாற்றியமைத்தன. கூலி–டக்கி வழிமுறை DFT ஐ சிறு DFTகளாக பிரிப்பதாலும், கீழே விவரிக்கப்பட்டுள்ளனவற்றைப் போன்ற DFTக்கான பிற எந்த வழிமுறைகளுடனும் இதைச் சேர்த்துப் பயன்படுத்தலாம்.
கேள்வி: விரைவு ஃபூரியே உருமாற்றம் - பிற FFT வழிமுறைகள் பற்றி விளக்கவும்.
பதில்: கூலி டக்கி முறையிலிருந்து வேறுபட்டுள்ள பிற 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களின் மெய் தரவுகளின் மூலமாகவும் கணக்கிடலாம்.
கேள்வி: விரைவு ஃபூரியே உருமாற்றம் - குறிப்புதவிகள் என்பது என்ன?
பதில்: * என். ப்ரன்னர் மற்றும் சி. ரேடர், 1976, [http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1162805 அ நியூ ப்க்ரின்சிப்பல் ஃபார் ஃபாஸ்ட் ஃபோரியர் ட்ரான்ஸ்ஃபர்மேஷன்], ''IEEE அக்கௌஸ்டிக்ஸ், ஸ்பீச் &amp; சிக்னல் ப்ராசசிங்'' 24 : 264-266. * * கூலி, ஜேம்ஸ் டபள்யூ., மற்றும் ஜான் டபள்யூ. டக்கி, 1965, "அன் அல்காரிதம் ஃபார் த மெஷின் கால்குலேஷன் ஆஃப் அ காம்ப்ளெக்ஸ் ஃபோரியர் சீரியஸ்," ''மேத். '' ''கம்ப்யூட்.'' 19 : 297–301. * தாமஸ் எச். கார்மன், சார்லஸ் இ. லெய்சர்சன், ரொனால்ட் எல். ரிவெஸ்ட், அண்ட் க்ளிஃபோர்டு ஸ்டெயின், 2001. ''இண்ட்ரடக்ஷன் டு அல்காரிதம்ஸ்'' , 2ஆம் பதிப்பு MIT ப்ரஸ் அண்ட் மெக்க்ராவ்-ஹில். . குறிப்பாக அதிகாரம் 30, "பாலினாமியல்ஸ் அண்ட் த FFT." * ப்யேர் டுஹாமெல், 1990, [4], ''IEEE ட்ரான்ஸ். அக்கௌஸ்ட். '' ''ஸ்பீச். '' ''சிக். '' ''ப்ராச.'' 38 : 1504-151. * பி. டுஹாமெல் அண்ட் எம். வெட்டர்லி, 1990, , ''சிக்னல் ப்ராசசிங்'' 19 : 259–299. * ஏ. ஈடில்மேன், பி. மெக்கார்க்வோடேல், அண்ட் எஸ். டோலிடோ, 1999, , ''SIAM ஜே. சை. கம்ப்யூட்டிங்'' 20 : 1094–1114. * ஃபண்டா எர்கன், 1995, , ''ப்ராச. 27த் ACM சிம்போசியம் ஆன் த தியரி ஆஃப் கம்ப்யூட்டிங்'' : 407–416. * எம். ஃப்ரிகோ அண்ட் எஸ். ஜி. ஜான்சன், 2005, "[http://fftw.org/fftw-paper-ieee.pdf த டிசைன் அண்ட் இம்ப்ளிமெண்ட்டேஷன் ஆஃப் 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, , ''ப்ராச. SPIE Intl. Soc. Opt. '' ''இங்கி.'' 2825 : 250–259. * ------- அண்ட் ஜி. ஏ. சிட்டான், 1994, , ''ப்ராச. IEEE கான்ஃப். அக்கௌஸ்ட். '' ''ஸ்பீச் அண்ட் சிக். '' ''ப்ராசசிங் (ICASSP)'' 3 : 445–448. * ஹெயிட்மேன், எம். டி., டி. எச். ஜான்சன் அண்ட் சி. எஸ். பர்ரஸ், "[http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1162257 காஸ் அண்ட் த ஹிஸ்டரி ஆஃப் த ஃபாஸ்ட் ஃபோரியர் ட்ரான்ஸ்ஃபார்ம்]," IEEE ASSP இதழ், 1, (4), 14–21 (1984). * மைக்கேல் டி. ஹெயிட்மேன் அண்ட் சி. சிட்னி பர்ரஸ், 1986, [http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1164785 ஆன் த நம்பர் ஆஃப் மல்ட்டிப்ளிகேஷன்ஸ் நெசசரி டு கம்ப்யூட் அ லெண்த்-2^n DFT], ''IEEE ட்ரான்ஸ். அக்கௌஸ்ட். '' ''ஸ்பீச் '' ''சிக். '' ''ப்ராச.'' 34 : 91-95. * -------- அண்ட் டி. எச். ஜான்சன், 1984, [http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1162257 காஸ் அண்ட் த ஹிஸ்டரி ஆஃப் த ஃபாஸ்ட் ஃபோரியர் ட்ரான்ஸ்ஃபார்ம்], ''IEEE ASSP இதழ்'' 1 : 14–21. * எஸ். ஜி. ஜான்சன் அண்ட் எம். ஃப்ரிகோ, 2007. "[http://www.fftw.org/newsplit.pdf அ மாடிஃபைடு ஸ்பிளிட்-ரேடிக்ஸ் FFT வித் ஃபியூவர் அரித்மெட்டிக் ஆப்பரேஷன்ஸ்]," ''IEEE ட்ரான்ஸ். சிக்னல் ப்ராசசிங்'' 55 (1): 111–119. * டி. லண்டி அண்ட் ஜே. வேன் பஸ்கிர்க், 2007. "அ ஃஇயூ மேட்ரிக்ஸ் அப்ரோச் டு ரியல் FFTஸ் அண்ட் கன்வல்யூஷன்ஸ் ஆஃப் லெண்த் 2k," ''கம்ப்யூட்டிங்'' 80 (1): 23-45. * ஜாக்வெஸ் மார்கன்ஸ்டன், 1973, , ''J. ACM'' 20 : 305-306. * [http://dx.doi.org/10.1007/BF01261607 எம். ஜே. மோலன்கேம்ப், 1999, "அ ஃபாஸ்ட் ட்ரான்ஸ்ஃபார்ம் ஃபார் ஸ்பெரிக்கல் ஹார்மோனிக்ஸ்", ''ஜே. ஃபோரியர் அனால். '' ][http://dx.doi.org/10.1007/BF01261607 ''அப்ப்ளி.'' ][http://dx.doi.org/10.1007/BF01261607 5 , 159–184.] ([http://www.math.ohiou.edu/~mjm/research/MOHLEN1999P.pdf ப்ரீப்ரிண்ட்] ) * எச். ஜே. நுஸ்பாமர், 1977, , ''எலக்ட்ரானிக்ஸ் லெட்.'' 13 : 386-387. * வி. பேன், 1986, , ''இன்ஃபர்மேஷன் ப்ராச. லெட்.'' 22 : 11-14. * கிரிஸ்டோஸ் எச். பாப்படிமித்ரியோ, 1979, , ''ஜே. ACM'' 26 : 95-102. * டி. பாட்ஸ், ஜி. ஸ்டெயிடில் அண்ட் எம். டாஸ்கி, 2001. "[http://www.tu-chemnitz.de/~potts/paper/ndft.pdf ஃபாஸ்ட் ஃபோரியர் ட்ரான்ஸ்ஃபார்ம்ஸ் ஃபார் நான் - ஈக்விஸ்பேஸ்டு டேட்டா: அ டுட்டோரியல்]", இன்: ஜே.ஜே. பெனிடேட்டோ அண்ட் பி. ஃபெரெயிரா (ஆசிரியர்கள்.), ''மாடன் சேம்ப்ளிங் தியரி: மேத்தமட்டிக்ஸ் அண்ட் அப்ளிகேஷன்ஸ்'' (பிர்க்காசர்). * விளாடிமிர் ராக்ளின் அண்ட் மார்க் டைகர்ட், 2006, "[http://pantheon.yale.edu/~mwt7/sph2.pdf ஃபாஸ்ட் அல்காரிதம்ஸ் ஃபார் ஸ்பெரிக்கல் ஹார்மோனிக் எக்ஸ்பேன்ஷன்ஸ்]," ''SIAM ஜே. சை. கம்ப்யூட்டிங்'' 27 (6): 1903-1928. * ஜேம்ஸ் சி. ஸ்காட்ஸ்மேன், 1996, [http://portal.acm.org/citation.cfm?id=240432 அக்யூரசி ஆஃப் த டிஸ்க்ரீட் ஃபோரியர் ட்ரான்ஸ்ஃபார்ம் அண்ட் த ஃபாஸ்ட் ஃபோரியர் ட்ரான்ஸ்ஃபார்ம்], ''SIAM ஜே. சை. கம்ப்.'' 17 : 1150–1166. * ஓ. வி. ஷெண்ட்டோவ், எஸ். கே. மித்ரா, யு. ஹியூட் அண்ட் ஏ. என். ஹாஸென், 1995, , ''சிக்னல் ப்ராசசிங்'' 41 : 261–277. * எச். வி. சோரன்சென், டி. எல். ஜோன்ஸ், எம். டி. ஹெயிட்மேன் அண்ட் சி. எஸ். பர்ரஸ், 1987, [http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1165220 ரியல்-வேல்யூட் ஃபாஸ்ட் ஃபோரியர் ட்ரான்ஸ்ஃபார்ம் அல்காரிதம்ஸ்], ''IEEE ட்ரான்ஸ். அக்கௌஸ்ட். '' ''ஸ்பீச் சிக். '' ''ப்ராசசிங்'' ASSP-35 : 849–863. [http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1165284 கரக்ஷன்ஸ் டு "ரியல்-வேல்யூட் ஃபாஸ்ட் ஃபோரியர் ட்ரான்ஸ்ஃபார்ம் அல்காரிதம்ஸ்"] * பீட்டர் டி. வெல்ச், 1969, [http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1162035 அ ஃபிக்ஸ்டு-பாயிண்ட் ஃபாஸ்ட் ஃபோரியர் ட்ரான்ஸ்ஃபார்ம் எரர் அனாலிசிஸ்], ''IEEE ட்ரான்ஸ். ஆடியோ எலக்ட்ரோ அக்கௌஸ்டிக்ஸ்'' 17 : 151–157. * எஸ். வினோக்ராட், 1978, [http://www.jstor.org/view/00255718/di970565/97p0015m/0 ஆன் கம்ப்யூட்டிங் த டிஸ்க்ரீட் ஃபோரியர் ட்ரான்ஸ்ஃபார்ம்], ''மேத். '' ''கம்ப்யூட்டேஷன்'' 32 : 175-199.
கேள்வி: விரைவு ஃபூரியே உருமாற்றம் - புற இணைப்புகள் பற்றி விளக்கவும்.
பதில்: * ''[http://cnx.org/content/col10550/ ஃபாஸ்ட் ஃபோரியர் ட்ரான்ஸ்ஃபார்ம்ஸ்]'' , கொன்னெக்ஷன்ஸ் ஆன்லைன் புத்தகம் - ஆசிரியர் சி. சிட்னி பர்ரஸ்,- அதிகாரங்கள்: சி. சிட்னி பர்ரஸ், ஐவன் செல்ஸ்னிக், மார்க்கஸ் ப்யூஸ்கெல், மேட்டியோ ஃப்ரிகோ அண்ட் ஸ்டீவன் ஜி. ஜான்சன் (2008). * [http://www.fftcalculator.com/ FFT கால்குலேட்டர்.] * [http://www.fftw.org/links.html லின்க்ஸ் டு FFT கோட் அண்ட் இன்ஃபர்மேஷன் ஆன்லைன்.] * [http://www.librow.com/articles/article-10 FFT ப்ரோக்ராமிங் இன் C++ — கூலி-டக்கி அல்காரிதம்.] * [http://www.jjj.de/fxt/ ஆன்லைன் ஆவணமாக்கல், இணைப்புகள், புத்தகம் மற்றும் குறியீடுகள்.] * [http://www.vosesoftware.com/ModelRiskHelp/index.htm#Aggregate_distributions/Aggregate_modeling_-_Fast_Fourier_Transform_FFT_method.htm யூசிங் FFT டு கன்ஸ்ட்ரக்ட் அக்ரிகேட் ப்ராபபிலிட்டி டிஸ்ட்ரிபியூஷன்ஸ்] * ஸ்ரீ வேலரத்னா, "[http://www.dataphysics.com/support/library/downloads/articles/DP-30%20Years%20of%20FFT.pdf 30 இயர்ஸ் ஆஃப் FFT அனலைசர்ஸ்] ", ''சௌண்ட் அண்ட் வைப்ரேஷன்'' (ஜனவரி 1997, 30ஆம் ஆண்டு வெளியீடு). அ ஹிஸ்டாரிக்கல் ரிவியூ ஆஃப் ஹார்ட்வேர் FFT டிவைசஸ். * [http://www.multi-instrument.com/doc/D1002/FFT_Basics_and_Case_Study_using_Multi-Instrument_D1002.pdf FFT பேசிக்ஸ் அண்ட் கேஸ் ஸ்டடி யூசிங் மல்டி-இன்ஸ்ட்ருமெண்ட்] * [http://numericalmethods.eng.usf.edu/topics/fft.html FFT டெக்ஸ்ட்புக் நோட்ஸ், PPTஸ்] அட் ஹோலிஸ்டிக் நியூமரிக்கல் மெத்தட்ஸ் இன்ஸ்டிட்டியூட். பகுப்பு:கணிதம் பகுப்பு:கூகுள் தமிழாக்கம்-கணிதவியல்