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

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

பலபரிமாண DFT கட்டுரையில் வரையறுக்கப்பட்டுள்ளபடி, பின்வரும் பல பரிமாண DFT  
:<math>X_\mathbf{k} = \sum_{\mathbf{n}=0}^{\mathbf{N}-1} e^{-2\pi i \mathbf{k} \cdot (\mathbf{n} / \mathbf{N})} x_\mathbf{n}</math>  
ஆனது <math>\mathbf{n}=(n_1, n_2, \ldots, n_d)</math> முனைகளை உடைய <math>d</math>-பரிமாண வெக்டார் கொண்ட <math>x_\mathbf{n}</math> எனும் ஒரு அணியை <math>d</math> குழு கூடு கூட்டல்களுக்கு (ஒவ்வொரு <math>j</math> க்கும் <math>n_j = 0 \ldots N_j-1</math> க்கும் மேலாக) மாற்றுகிறது. இதில் பிரிவு <math>\mathbf{n} / \mathbf{N}</math>, <math>\mathbf{n} / \mathbf{N} = (n_1/N_1, \cdots, n_d/N_d)</math> என வரையறுக்கப்படுகிறது, அது ஒவ்வொரு உறுப்புவாரியாக செயல்படுத்தப்படுகிறது. சமமான விதத்தில், அது ஒற்றைப் பரிமாண DFTகளின் <math>d</math> குழுக்களின் தொடர்ச்சியான கூட்டமைப்பே ஆகும். இது ஒரு நேரத்தில் ஒரு பரிமாணத்தின் வழியாக மட்டுமே (ஏதேனும் ஒரு வரிசையில்) செயல்படுத்தப்படுகிறது.  
இந்தக் கணக்கீட்டியல் கருத்துக் கண்ணோட்டமானது எளிய மற்றும் மிகப் பொதுவான பல பரிமாண DFT வழிமுறையை வழங்குகிறது. அது (கீழே விவரிக்கப்படும் இரு பரிமாண நிகழ்வைக் கொண்டு) **நிரை-நிரல்** வழிமுறை என அழைக்கப்படுகிறது. அதாவது, ஒருவர் வெறுமென <math>d</math> ஒற்றைப் பரிமாண FFTகளின் தொடரை மட்டுமே செயல்படுத்துகிறார் (மேலே கூறப்பட்ட வழிமுறைகளில் ஏதேனும் ஒன்றின் மூலம்): முதலில் <math>n_1</math> பரிமாணத்தின் வழியே மாற்றம் செய்கிறீர்கள், பின்னர் <math>n_2</math> பரிமாணம், இதே போல் தொடர்கிறீர்கள் (அல்லது உண்மையில் எந்த வரிசையிலும் இது சரியாக முடிவைக் கொடுக்கும்). இந்த முறையானது <math>O(N \log N)</math> சிக்கலான தன்மையைக் கொண்டிருப்பதாக எளிதாக நிரூபிக்கப்பட்டது. இதில் <math>N = N_1 N_2 \cdots N_d</math> என்பது மாற்றப்பட்ட தரவுப் புள்ளிகளின் மொத்த எண்ணிக்கையாகும். குறிப்பாக, <math>N_1</math>, போன்ற அளவுடைய <math>N/N_1</math> உருமாற்றங்கள் உள்ளன, ஆகவே FFTகளின் தொடரின் சிக்கலான தன்மை பின்வருமாறு:  
:<math> \begin{align} &amp; {} \qquad \frac{N}{N_1} O(N_1 \log N_1) + \cdots + \frac{N}{N_d} O(N_d \log N_d) \\[6pt] &amp; = O\(N \[\log N_1 + \cdots + \log N_d\]\) = O(N \log N). \end{align} </math>  
இரு பரிமாணங்களில், <math>x_\mathbf{k}</math> ஐ ஒரு <math>n_1 \times n_2</math> அணியாகக் கருதலாம். மேலும் இந்த வழிமுறையானது முதலில் அணியின் அனைத்து நிரைகளின் FFT ஐ செயல்படுத்தி பின்னர் அனைத்து நிரல்களின் FFT ஐ செயல்படுத்தும் முறையைக் கொண்டது (அல்லது மறுதிசையில்), இதனாலே இம்முறைக்கு இந்தப் பெயர் வந்தது.  
இரு பரிமாணத்திற்கும் அதிகமான நிகழ்வில், பல சமயங்களில் பதுக்கக இட அமைப்பை மீண்டும் மீண்டும் குழுப்படுத்துதல் என்பது பயன்மிக்கதாக இருக்கும். எடுத்துக்காட்டுக்கு, ஒரு முப்பரிமாண FFT ஆனது முதலில் ஒவ்வொரு நிலையான <math>n_1</math> க்குமான ஒவ்வொரு தள "ஸ்லைஸின்" இரு-பரிமாண FFTகளை செயல்படுத்தலாம், பின்னர் அது ஒற்றைப் பரிமாண FFTகளை <math>n_1</math> திசையில் செயல்படுத்தலாம். பொதுவாக, ஒரு தொலைத்தொடுகோட்டு சிறப்பு பதுக்கக-நினைவகக் குறை வழிமுறையில், மீண்டும் மீண்டும் மாற்றம் செய்யப்படும் பரிமாணங்களை மீண்டும் மீண்டும் <math>(n_1, \cdots, n_{d/2})</math> மற்றும் <math>(n_{d/2+1}, \cdots, n_d)</math> என இரு குழுவாகப் பிரிக்கும் நிகழ்வு இடம்பெறுகிறது (<math>d</math> என்பது இரட்டையாக இல்லாதபட்சத்தில் அது முழுமையாக்கும்) (காண்க: ஃப்ரிகோ மற்றும் ஜான்சன், 2005). இருப்பினும், இது இரு-நிரல் வழிமுறையின் நேர்பாங்கான வகையாக உள்ளது, இதற்கு அடிப்படை நிகழ்வாக மொத்தம் ஒற்றைப் பரிமாண FFT வழிமுறையே தேவைப்படுகிறது, மேலும் இதில் <math>O(N \log N)</math> சிக்கலான தன்மை மட்டுமே உள்ளது. மாற்றம் செய்யப்படும் பரிமாணங்களுக்கிடையே அணி இடமாற்றத்தைச் செயல்படுத்துவது என்பது இன்னுமொரு வகையாகும், ஆகவே உருமாற்றமானது அருகாமைத் தரவின் மீதே செயல்படுகிறது. குறிப்பாக இது அருகாமையிலல்லாத தரவை அணுகுவது என்பது அதிக நேரம் எடுத்துக்கொள்ளும் நிகழ்வாக உள்ள, மையத்திற்கு புறத்தேயான மற்றும் பகிரப்பட்ட நினைவக சூழ்நிலைகளுக்கு முக்கியமானதாகும்.  
நிரை-நிரல் வழிமுறையிலிருந்து வேறுபட்டுள்ள பிற பலபரிமாண FFT வழிமுறைகளும் உள்ளன, இருப்பினும் அவை அனைத்திலும் <math>O(N \log N)</math> சிக்கலான தன்மை உள்ளது. மிக எளிய நிரல்-நிரை அல்லாத FFT வெக்டார்-ரேடிக்ஸ் FFT வழிமுறையாக இருக்கலாம், அது வழக்கமான கூலி-டக்கி வழிமுறையின் பொதுமையாக்கலாக உள்ளது, அதில் நாம் உருமாற்றப் பரிமாணங்களை ஒவ்வொரு படியிலும் <math>\mathbf{r}=(r_1, r_2, \cdots, r_d)</math> என்ற ரேடிக்ஸ் வெக்டாரால் வகுக்கிறோம். (இதில் பதுக்கக நன்மைகளும் இருக்கலாம்.) அனைத்து ரேடிக்ஸ்களும் சமமாக இருப்பது என்பது வெக்டார்-ரேடிக்ஸின் எளிய நிகழ்வாகும் (எ.கா. வெக்டார்-ரேடிக்ஸ்-2, பரிமாணங்கள் *அனைத்தையும்* இரண்டால் வகுக்கிறது), ஆனால் இது அவசியம் என்பதல்ல. ஒரு நேரத்தில் ஒன்றல்லாத ஒரே ஒரு ரேடிக்ஸைக் கொண்டுள்ள வெக்டார், அதாவது <math>\mathbf{r}=(1, \cdots, 1, r, 1, \cdots, 1)</math>, கட்டாயமாக ஒரு நிரை-நிரல் வழிமுறையாகவே இருக்கும். மற்ற மிகச் சிக்கலான முறைகளில் நுஸ்ஸம்பரின் (1977) பல்லுறுப்புக்கோவை உருமாற்ற வழிமுறைகள் போன்றவை அடங்கும். அதன்படி உருமாற்றங்கள் சுழற்சிகளாகவும் பல்லுறுப்புக்கோவை விளைபலன்களாகவும் கருதப்படுகின்றன. மேலும் தகவல்களுக்கும் குறிப்புதவிகளுக்கும் டுஹாமெல் மற்றும் வெட்டெர்லி (1990) என்பதைக் காண்க.