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

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

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

கீழே விவாதிக்கப்பட்டுள்ள அனைத்து FFT வழிமுறைகளும் DFT ஐ துல்லியமாகக் கணக்கிடுகின்றன (துல்லியமான எண் கணிதத்தில், அதாவது ஃப்ளோட்டிங் - பாயிண்ட் பிழைகளைப் புறக்கணிக்கின்றன). இருப்பினும், DFT ஐ *தோராயமாகக்* கணக்கிடும் ஒரு சில "FFT" வழிமுறைகளும் முன்மொழியப்பட்டுள்ளன, அவை அதிகமான கணக்கீடுகளின் சிரமத்துடன் ஒப்பிடுகையில் சீரற்ற முறையிலான மிகச் சிறிய பிழைகளைக் கொண்டிருக்கலாம். அது போன்ற வழிமுறைகள் அதிகரிக்கப்பட்ட வேகம் அல்லது பிற பண்புகளுக்கான தோராயமாக்கல் பிழைகளைக் கையாளுகின்றன. எடுத்துக்காட்டுக்கு, ஈடில்மேன் மற்றும் பலரால் முன்மொழியப்பட்ட (1999) ஒரு தோராய FFT வழிமுறையானது இணைக் கணக்கீட்டுக்கான குறைவான தகவல்தொடர்பு தேவைகளைக் கொண்டுள்ளது. அதற்கு ஒரு வேகப் பன்முக முறை உதவியாக உள்ளது. குவோ மற்றும் பர்ரஸ் அவர்களால் முமொழியப்பட்ட (1996) ஒரு சிற்றலை-அடிப்படையிலான தோராய FFT, ஒரு துல்லியமான FFT கொண்டு சாத்தியப்படுவதை விட அடர்த்தியற்ற உள்ளீடுகள்/வெளியீடுகளை (நேரம்/அதிர்வெண் இடமறிதல்) முக்கியமாகக் கருத்தில்கொள்கிறது. DFT வெளியீடுகளுக்கான துணைக்குழுவின் தோராயக் கணக்கீட்டுக்கான மற்றொரு வழிமுறை ஷெண்ட்டோவ் மற்றும் பலரால் கண்டுபிடிக்கப்பட்டது. (1995). இருப்பினும், அடர்த்தியற்ற மற்றும் அடர்த்தியான ஆகிய இரு வகை தரவுகளுக்கும் ஈடில்மேன் வழிமுறையே சிறப்பாகப் பயன்பட்டது. ஏனெனில் அது தரவின் சுருக்கக்கூடிய தன்மையை அடிப்படையாகக் கொண்டிருக்காமல் ஃபூரியே அணியின் சுருக்கக்கூடிய தன்மையை அடிப்படையாகக் கொண்டிருக்கிறது.  
புள்ளி இலக்க எண் கணிதங்கள் பயன்படுத்தப்படும் போது "துல்லியமான" FFT வழிமுறைகளிலும் பிழைகள் உள்ளன வரையறுக்கப்பட்ட-துல்லியம், ஆனால் இந்தப் பிழைகள் வழக்கமாக மிகச் சிறியன. பெரும்பாலான FFT வழிமுறைகள், எ.கா. கூலி-டக்கி, சிறந்த எண்ணியல் பண்புகளைக் கொண்டுள்ளன. ε என்பது மெஷின் ஃப்ளோட்டிங் பாயிண்ட் தொடர்பு நிலையாக உள்ள, நீவ் DFT சூத்திரத்துக்கான (ஜெண்டில்மேன் மற்றும் சாண்டி, 1966) O(ε*N* <sup>3/2</sup>) உடன் ஒப்பிடுகையில் கூலி டக்கி வழிமுறைக்கான தொடர்புப் பிழையிலான மேல் வரம்பானது 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* ) நேரத்தில், உறுதியான உத்தரவாதங்களைப் பெற முடியும்.