1 | /*************************************************************************
|
---|
2 | Copyright (c) 2009, Sergey Bochkanov (ALGLIB project).
|
---|
3 |
|
---|
4 | >>> SOURCE LICENSE >>>
|
---|
5 | This program is free software; you can redistribute it and/or modify
|
---|
6 | it under the terms of the GNU General Public License as published by
|
---|
7 | the Free Software Foundation (www.fsf.org); either version 2 of the
|
---|
8 | License, or (at your option) any later version.
|
---|
9 |
|
---|
10 | This program is distributed in the hope that it will be useful,
|
---|
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
13 | GNU General Public License for more details.
|
---|
14 |
|
---|
15 | A copy of the GNU General Public License is available at
|
---|
16 | http://www.fsf.org/licensing/licenses
|
---|
17 |
|
---|
18 | >>> END OF LICENSE >>>
|
---|
19 | *************************************************************************/
|
---|
20 |
|
---|
21 | using System;
|
---|
22 |
|
---|
23 | namespace alglib
|
---|
24 | {
|
---|
25 | public class fht
|
---|
26 | {
|
---|
27 | /*************************************************************************
|
---|
28 | 1-dimensional Fast Hartley Transform.
|
---|
29 |
|
---|
30 | Algorithm has O(N*logN) complexity for any N (composite or prime).
|
---|
31 |
|
---|
32 | INPUT PARAMETERS
|
---|
33 | A - array[0..N-1] - real function to be transformed
|
---|
34 | N - problem size
|
---|
35 |
|
---|
36 | OUTPUT PARAMETERS
|
---|
37 | A - FHT of a input array, array[0..N-1],
|
---|
38 | A_out[k] = sum(A_in[j]*(cos(2*pi*j*k/N)+sin(2*pi*j*k/N)), j=0..N-1)
|
---|
39 |
|
---|
40 |
|
---|
41 | -- ALGLIB --
|
---|
42 | Copyright 04.06.2009 by Bochkanov Sergey
|
---|
43 | *************************************************************************/
|
---|
44 | public static void fhtr1d(ref double[] a,
|
---|
45 | int n)
|
---|
46 | {
|
---|
47 | ftbase.ftplan plan = new ftbase.ftplan();
|
---|
48 | int i = 0;
|
---|
49 | AP.Complex[] fa = new AP.Complex[0];
|
---|
50 |
|
---|
51 | System.Diagnostics.Debug.Assert(n>0, "FHTR1D: incorrect N!");
|
---|
52 |
|
---|
53 | //
|
---|
54 | // Special case: N=1, FHT is just identity transform.
|
---|
55 | // After this block we assume that N is strictly greater than 1.
|
---|
56 | //
|
---|
57 | if( n==1 )
|
---|
58 | {
|
---|
59 | return;
|
---|
60 | }
|
---|
61 |
|
---|
62 | //
|
---|
63 | // Reduce FHt to real FFT
|
---|
64 | //
|
---|
65 | fft.fftr1d(ref a, n, ref fa);
|
---|
66 | for(i=0; i<=n-1; i++)
|
---|
67 | {
|
---|
68 | a[i] = fa[i].x-fa[i].y;
|
---|
69 | }
|
---|
70 | }
|
---|
71 |
|
---|
72 |
|
---|
73 | /*************************************************************************
|
---|
74 | 1-dimensional inverse FHT.
|
---|
75 |
|
---|
76 | Algorithm has O(N*logN) complexity for any N (composite or prime).
|
---|
77 |
|
---|
78 | INPUT PARAMETERS
|
---|
79 | A - array[0..N-1] - complex array to be transformed
|
---|
80 | N - problem size
|
---|
81 |
|
---|
82 | OUTPUT PARAMETERS
|
---|
83 | A - inverse FHT of a input array, array[0..N-1]
|
---|
84 |
|
---|
85 |
|
---|
86 | -- ALGLIB --
|
---|
87 | Copyright 29.05.2009 by Bochkanov Sergey
|
---|
88 | *************************************************************************/
|
---|
89 | public static void fhtr1dinv(ref double[] a,
|
---|
90 | int n)
|
---|
91 | {
|
---|
92 | int i = 0;
|
---|
93 |
|
---|
94 | System.Diagnostics.Debug.Assert(n>0, "FHTR1DInv: incorrect N!");
|
---|
95 |
|
---|
96 | //
|
---|
97 | // Special case: N=1, iFHT is just identity transform.
|
---|
98 | // After this block we assume that N is strictly greater than 1.
|
---|
99 | //
|
---|
100 | if( n==1 )
|
---|
101 | {
|
---|
102 | return;
|
---|
103 | }
|
---|
104 |
|
---|
105 | //
|
---|
106 | // Inverse FHT can be expressed in terms of the FHT as
|
---|
107 | //
|
---|
108 | // invfht(x) = fht(x)/N
|
---|
109 | //
|
---|
110 | fhtr1d(ref a, n);
|
---|
111 | for(i=0; i<=n-1; i++)
|
---|
112 | {
|
---|
113 | a[i] = a[i]/n;
|
---|
114 | }
|
---|
115 | }
|
---|
116 | }
|
---|
117 | }
|
---|