Fast Fourier Transform: Forskelle mellem versioner
Content deleted Content added
Forkert formulering. |
→Beregningstid: , eksempel tilføjet. |
||
Linje 62:
Ved at benytte FFT reduceres antallet af beregninger af exponentialfuktionen til <math>\operatorname{log_2}(n)</math> og antallet af multiplikationer til <math>n \cdot \operatorname{log_2}(n)</math>.<br />
Hvis n eksempelvis er 1024, så reduceres antallet af trigonometriske beregninger og multiplikationer fra 1.048.576 til 10 og 10240, hhv. Alt andet lige reducerer det beregningstiden med mindst en faktor 100.<br />
=== Et enkelt eksempel ===
For at vise hvordan metoden virker er her et eksempel med en serie med længden 8.
I eksemplet benyttes størrelsen:
<math>\kappa = e^{-2\pi\cdot i/8}</math>
I beregningerne udnyttes at:
<math>\kappa^8 = e^{-2\pi \cdot i} = 1</math>
Det medfører yderligere at:
<math>\kappa^{8 \cdot n + k} = \kappa^k</math>
Her benyttes regnereglerne:
<math>\kappa^n \cdot \kappa^m = \kappa^{n + m}</math>
og:
<math>\kappa^{n \cdot m} = (\kappa^n)^m</math>
Skemaet illustrerer hvordan beregningerne udføres:
{| class="wikitable"
|-
! height=40px |
! f<sub>0</sub>
! f<sub>1</sub>
! f<sub>2</sub>
! f<sub>3</sub>
! f<sub>4</sub>
! f<sub>5</sub>
! f<sub>6</sub>
! f<sub>7</sub>
! <i>beregning</i>
|-
! height=50px | F<sub>0</sub><br />
| f<sub>0</sub>•κ<sup>0</sup>=f<sub>0</sub>
| f<sub>1</sub>•κ<sup>0</sup>=f<sub>1</sub>
| f<sub>2</sub>•κ<sup>0</sup>=f<sub>2</sub>
| f<sub>3</sub>•κ<sup>0</sup>=f<sub>3</sub>
| f<sub>4</sub>•κ<sup>0</sup>=f<sub>4</sub>
| f<sub>5</sub>•κ<sup>0</sup>=f<sub>5</sub>
| f<sub>6</sub>•κ<sup>0</sup>=f<sub>6</sub>
| f<sub>7</sub>•κ<sup>0</sup>=f<sub>7</sub>
| ((f<sub>0</sub>+f<sub>4</sub>)+(f<sub>2</sub>+f<sub>6</sub>))+((f<sub>1</sub>+f<sub>5</sub>)+(f<sub>3</sub>+f<sub>7</sub>))
|-
! height=50px | F<sub>1</sub>
| f<sub>0</sub>•κ<sup>0</sup>=f<sub>0</sub>
| f<sub>1</sub>•κ
| f<sub>2</sub>•κ<sup>2</sup>
| f<sub>3</sub>•κ<sup>3</sup>
| f<sub>4</sub>•κ<sup>4</sup>
| f<sub>5</sub>•κ<sup>5</sup>
| f<sub>6</sub>•κ<sup>6</sup>
| f<sub>7</sub>•κ<sup>7</sup>
| ((f<sub>0</sub>+f<sub>4</sub>•κ<sup>4</sup>)+(f<sub>2</sub>+f<sub>6</sub>•κ<sup>4</sup>)•κ<sup>2</sup>)+((f<sub>1</sub>+f<sub>5</sub>•κ<sup>4</sup>)+(f<sub>3</sub>+f<sub>7</sub>•κ<sup>4</sup>)•κ<sup>2</sup>)•κ
|-
! height=50px | F<sub>2</sub>
| f<sub>0</sub>•κ<sup>0</sup>=f<sub>0</sub>
| f<sub>1</sub>•κ<sup>2</sup>
| f<sub>2</sub>•κ<sup>4</sup>
| f<sub>3</sub>•κ<sup>6</sup>
| f<sub>4</sub>•κ<sup>8</sup>=f<sub>4</sub>
| f<sub>5</sub>•κ<sup>10</sup>=f<sub>5</sub>•κ<sup>2</sup>
| f<sub>6</sub>•κ<sup>12</sup>=f<sub>6</sub>•κ<sup>4</sup>
| f<sub>7</sub>•κ<sup>14</sup>=f<sub>7</sub>•κ<sup>6</sup>
| ((f<sub>0</sub>+f<sub>4</sub>)+(f<sub>2</sub>+f<sub>6</sub>)•κ<sup>4</sup>)+((f<sub>1</sub>+f<sub>5</sub>)+(f<sub>3</sub>+f<sub>7</sub>)•κ<sup>4</sup>)•κ<sup>2</sup>
|-
! height=50px | F<sub>3</sub>
| f<sub>0</sub>•κ<sup>0</sup>=f<sub>0</sub>
| f<sub>1</sub>•κ<sup>3</sup>
| f<sub>2</sub>•κ<sup>6</sup>
| f<sub>3</sub>•κ<sup>9</sup>=f<sub>3</sub>•κ
| f<sub>4</sub>•κ<sup>12</sup>=f<sub>4</sub>•κ<sup>4</sup>
| f<sub>5</sub>•κ<sup>15</sup>=f<sub>5</sub>•κ<sup>7</sup>
| f<sub>6</sub>•κ<sup>18</sup>=f<sub>6</sub>•κ<sup>2</sup>
| f<sub>7</sub>•κ<sup>21</sup>=f<sub>7</sub>•κ<sup>5</sup>
| ((f<sub>0</sub>+f<sub>4</sub>•κ<sup>4</sup>)+(f<sub>2</sub>+f<sub>6</sub>•κ<sup>4</sup>)•κ<sup>2</sup>•κ<sup>4</sup>)+((f<sub>1</sub>+f<sub>5</sub>•κ<sup>4</sup>)+(f<sub>3</sub>+f<sub>7</sub>•κ<sup>4</sup>)•κ<sup>6</sup>)•κ<sup>3</sup>
|-
! height=50px | F<sub>4</sub>
| f<sub>0</sub>•κ<sup>0</sup>=f<sub>0</sub>
| f<sub>1</sub>•κ<sup>4</sup>
| f<sub>2</sub>•κ<sup>8</sup>=f<sub>2</sub>
| f<sub>3</sub>•κ<sup>12</sup>=f<sub>3</sub>•κ<sup>4</sup>
| f<sub>4</sub>•κ<sup>16</sup>=f<sub>4</sub>
| f<sub>5</sub>•κ<sup>20</sup>=f<sub>5</sub>•κ<sup>4</sup>
| f<sub>6</sub>•κ<sup>24</sup>=f<sub>6</sub>
| f<sub>7</sub>•κ<sup>28</sup>=f<sub>7</sub>•κ<sup>4</sup>
| ((f<sub>0</sub>+f<sub>4</sub>)+(f<sub>2</sub>+f<sub>6</sub>))+((f<sub>1</sub>+f<sub>5</sub>)+(f<sub>3</sub>+f<sub>7</sub>))•κ<sup>4</sup>
|-
! height=50px | F<sub>5</sub>
| f<sub>0</sub>•κ<sup>0</sup>=f<sub>0</sub>
| f<sub>1</sub>•κ<sup>5</sup>
| f<sub>2</sub>•κ<sup>10</sup>=f<sub>2</sub>•κ<sup>2</sup>
| f<sub>3</sub>•κ<sup>15</sup>=f<sub>3</sub>•κ<sup>7</sup>
| f<sub>4</sub>•κ<sup>20</sup>=f<sub>4</sub>•κ<sup>4</sup>
| f<sub>5</sub>•κ<sup>25</sup>=f<sub>5</sub>•κ
| f<sub>6</sub>•κ<sup>30</sup>=f<sub>6</sub>•κ<sup>6</sup>
| f<sub>7</sub>•κ<sup>35</sup>=f<sub>7</sub>•κ<sup>3</sup>
| ((f<sub>0</sub>+f<sub>4</sub>•κ<sup>4</sup>)+(f<sub>2</sub>+f<sub>6</sub>•κ<sup>4</sup>)•κ<sup>2</sup>)+((f<sub>1</sub>+f<sub>5</sub>•κ<sup>4</sup>)+(f<sub>3</sub>+f<sub>7</sub>•κ<sup>4</sup>)•κ<sup>2</sup>)•κ<sup>5</sup>
|-
! height=50px | F<sub>6</sub>
| f<sub>0</sub>•κ<sup>0</sup>=f<sub>0</sub>
| f<sub>1</sub>•κ<sup>6</sup>
| f<sub>2</sub>•κ<sup>12</sup>=f<sub>2</sub>•κ<sup>4</sup>
| f<sub>3</sub>•κ<sup>18</sup>=f<sub>3</sub>•κ<sup>2</sup>
| f<sub>4</sub>•κ<sup>24</sup>=f<sub>4</sub>
| f<sub>5</sub>•κ<sup>30</sup>=f<sub>5</sub>•κ<sup>6</sup>
| f<sub>6</sub>•κ<sup>36</sup>=f<sub>6</sub>•κ<sup>4</sup>
| f<sub>7</sub>•κ<sup>42</sup>=f<sub>7</sub>•κ<sup>2</sup>
| ((f<sub>0</sub>+f<sub>4</sub>)+(f<sub>2</sub>+f<sub>6</sub>)•κ<sup>4</sup>)+((f<sub>1</sub>+f<sub>5</sub>)+(f<sub>3</sub>+f<sub>7</sub>)•κ<sup>4</sup>)•κ<sup>6</sup>
|-
! height=50px | F<sub>7</sub>
| f<sub>0</sub>•κ<sup>0</sup>=f<sub>0</sub>
| f<sub>1</sub>•κ<sup>7</sup>
| f<sub>2</sub>•κ<sup>14</sup>=f<sub>2</sub>•κ<sup>6</sup>
| f<sub>3</sub>•κ<sup>21</sup>=f<sub>3</sub>•κ<sup>5</sup>
| f<sub>4</sub>•κ<sup>28</sup>=f<sub>4</sub>•κ<sup>4</sup>
| f<sub>5</sub>•κ<sup>35</sup>= f<sub>5</sub>•κ<sup>3</sup>
| f<sub>6</sub>•κ<sup>42</sup>=f<sub>6</sub>•κ<sup>2</sup>
| f<sub>7</sub>•κ<sup>49</sup>=f<sub>7</sub>•κ
| ((f<sub>0</sub>+f<sub>4</sub>•κ<sup>4</sup>)+(f<sub>2</sub>+f<sub>6</sub>•κ<sup>4</sup>)•κ<sup>6</sup>)+((f<sub>1</sub>+f<sub>5</sub>•κ<sup>4</sup>)+(f<sub>3</sub>+f<sub>7</sub>•κ<sup>4</sup>)•κ<sup>6</sup>)•κ<sup>7</sup>
|}
Som det ses, er der mange udregninger, som kan genbruges. Eksempelvis indgår <math>(f_0 + f_4 \cdot \kappa^4)</math> flere steder. I algoritmen udregnes denne størrelse kan én gang, og derved spares en del regnetid.
I dette eksempel, hvor serien af hensyn til overskueligheden er ganske lille, er besparelsen også lille. Når serien bliver stor, bliver besparelsen større.
=== Alternative metoder ===
| |||