- * Requires Nlog2N = n2n additions. - *
- *
- * Short Table of manual calculation for N=8: + * The FHT (Fast Hadamard Transformation) which uses only subtraction and + * addition. Requires {@code N * log2(N) = n * 2^n} additions. + * + *

### Short Table of manual calculation for N=8

*
- *
1. x is the input vector we want to transform
2. - *
3. y is the output vector which is our desired result
4. - *
5. a and b are just helper rows
6. + *
7. x is the input vector to be transformed,
8. + *
9. y is the output vector (Fast Hadamard transform of x),
10. + *
11. a and b are helper rows.
12. *
- * + *
+ * * * * @@ -94,109 +93,127 @@ public class FastHadamardTransformer imp * * * - * + * * * * * * - * + * * * * * * - * + * * * * * * - * + * * * * * * - * + * * * * * * - * + * * * * * * - * + * * * * * * - * + * * * * * + * *
xay
x0x0a0 = x0 + x1b0 = a0 + a1y0 = b0+ b1
x1x1a1 = x2 + x3b0 = a2 + a3y0 = b2 + b3
x2x2a2 = x4 + x5b0 = a4 + a5y0 = b4 + b5
x3x3a3 = x6 + x7b0 = a6 + a7y0 = b6 + b7
x4x4a0 = x0 - x1b0 = a0 - a1y0 = b0 - b1
x5x5a1 = x2 - x3b0 = a2 - a3y0 = b2 - b3
x6x6a2 = x4 - x5b0 = a4 - a5y0 = b4 - b5
x7x7a3 = x6 - x7b0 = a6 - a7y0 = b6 - b7
* - * How it works + *

### How it works

*
- *
1. Construct a matrix with N rows and n+1 columns
(If I use [x][y] it always means [row-offset][column-offset] of a Matrix with n rows and m columns. Its entries go from M[0][0] to M[n][m])
2. - *
3. Place the input vector x[N] in the first column of the matrix hadm
4. - *
5. The entries of the submatrix Dtop are calculated as follows. - *
Dtop goes from entry [0][1] to [N/2-1][n+1]. - *
The columns of Dtop are the pairwise mutually exclusive sums of the previous column + *
6. Construct a matrix with {@code N} rows and {@code n + 1} columns, + * {@code hadm[n+1][N]}.
+ * (If I use [x][y] it always means [row-offset][column-offset] of a + * Matrix with n rows and m columns. Its entries go from M[0][0] + * to M[n][N])
7. + *
8. Place the input vector {@code x[N]} in the first column of the + * matrix {@code hadm}.
9. + *
10. The entries of the submatrix {@code D_top} are calculated as follows + *
+ *
• {@code D_top} goes from entry {@code [0][1]} to + * {@code [N / 2 - 1][n + 1]},
• + *
• the columns of {@code D_top} are the pairwise mutually + * exclusive sums of the previous column.
• + *
*
11. - *
12. The entries of the submatrix Dbottom are calculated as follows. - *
Dbottom goes from entry [N/2][1] to [N][n+1]. - *
The columns of Dbottom are the pairwise differences of the previous column + *
13. The entries of the submatrix {@code D_bottom} are calculated as + * follows + *
+ *
• {@code D_bottom} goes from entry {@code [N / 2][1]} to + * {@code [N][n + 1]},
• + *
• the columns of {@code D_bottom} are the pairwise differences + * of the previous column.
• + *
*
14. - *
15. How Dtop and Dbottom you can understand best with the example for N=8 above. - *
16. The output vector y is now in the last column of hadm
17. - *
18. Algorithm from: http://www.archive.chipcenter.com/dsp/DSP000517F1.html
19. + *
20. The consputation of {@code D_top} and {@code D_bottom} are best + * understood with the above example (for {@code N = 8}). + *
21. The output vector {@code y} is now in the last column of + * {@code hadm}.
22. + *
23. Algorithm from chipcenter.
24. *
- *
- * Visually - * - * - * - * - * - * - * - * + *

### Visually

+ *
 0 1 2 3 ... n + 1
+ * + * + * + * + * * * - * + * * - * - * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * *
0 1 2 0 x0 ↑ + * ↑ + * ← Dtop → + * ↓ + * x1 x2 … xN/2-1 xN/2 + * ↑ + * ← Dbottom → + * ↓ + * xN/2+1 xN/2+2 … xN
- *
```-     *        +--------+---+---+---+-----+---+
-     *        |   0    | 1 | 2 | 3 | ... |n+1|
-     * +------+--------+---+---+---+-----+---+
-     * |0     | x0     |       /\            |
-     * |1     | x1     |       ||            |
-     * |2     | x2     |   <= Dtop  =>       |
-     * |...   | ...    |       ||            |
-     * |N/2-1 | xN/2-1  |       \/            |
-     * +------+--------+---+---+---+-----+---+
-     * |N/2   | xN/2   |       /\            |
-     * |N/2+1 | xN/2+1  |       ||            |
-     * |N/2+2 | xN/2+2  |  <= Dbottom  =>      | which is in the last column of the matrix
-     * |...   | ...    |       ||            |
-     * |N     | xN/2   |        \/           |
-     * +------+--------+---+---+---+-----+---+
-     * ```
* - * @param x input vector - * @return y output vector + * @param x the input vector + * @return the output vector, {@code y} * @exception IllegalArgumentException if input array is not a power of 2 */ protected double[] fht(double[] x) throws IllegalArgumentException {