Paaris ja paarituteks spektrikomponentiteks. Saame valemid N -1 2 S N ( 2k ) = s ( n) exp(- j nk ),0 k N / 2 - 1 n =0 N /2 N -1 2 S N (2k + 1) = s (n) exp(- j (2k + 1)n),0 k N / 2 - 1 n =0 N Nendes valemites exp funktsioon on perioodiline f-n perioodiga N/2. See tähendab, et nN/2 korral hakkavad tema väärtused korduma. Tänu sellele väheneb korrutustehete arv kaks korda. Taandame protsessi kaks korda lühema DFT protseduurile. Saame järgmised valemid s ( n) = s ( n) - s ( N / 2 + n),0 n N / 2 - 1 2 s (n) =s (n) exp(- j n) = s (n)W N (n),0 n N / 2 -1 N Mida suurem on signaali pikkus N , seda effektiivsem on FFT võrreldes DFT-ga. FFT maatriksalgoritm Eeldame , et signaali kestvus N on esitatav kahe arvu korrutisena N=FT , kus jagame sagedusala F osakuks
lõpliku korpusesse. Neid lõplike korpusi nim. Galois korpusteks ja tähistatakse GF (pm ). Siin p on algarv ja m on täisarv. Tehted lõpliku korpuse elementidega: liitmine ja korrutamine. Hulkliikmete liitmine: Korpuses GF(2) on elemente kaks 0 ja 1 ja nende liitmine toimub modulo 2: 0+modulo20=0, 0+modulo21=1, 1+modulo20=1, 1+modulo21=0 Hulkliikmete korrutamine: On siis kaks varianti -> 1. Otsene ehk tavaline ja 2. Faktorringis 1. Lõplik korpus on kinnine liitmistehete ja korrutustehete suhtes. See tähendab,et korpuse elementide liitmisel ja korrutamisel saame sellesse korpusesse kuuluva elemendi. 2. Igale elemendile a leidub liitmise suhtes pöördelement a. Igale nullist erinevale elemendile leidub korrutamise suhtes pöörelement a-1 . See võimaldab defineerida lisaks liitmisele ja korrutamisele ka lahutamise ja jagamise nullist erineva elemendiga: a-b= a+ (-b) ja a/b=a*b-1
annaabi.ee 
