org.apache.commons.math3.transform

## Class FastHadamardTransformer

- java.lang.Object
- - org.apache.commons.math3.transform.FastHadamardTransformer

- All Implemented Interfaces:
    Serializable, RealTransformer

      public class FastHadamardTransformer
      extends Object
      implements RealTransformer, Serializable

  Implements the Fast Hadamard Transform (FHT). Transformation of an input vector x to the output vector y.

  In addition to transformation of real vectors, the Hadamard transform can transform integer vectors into integer vectors. However, this integer transform cannot be inverted directly. Due to a scaling factor it may lead to rational results. As an example, the inverse transform of integer vector (0, 1, 0, 1) is rational vector (1/2, -1/2, 0, 0).

  Since:
    2.0
  Version:
    $Id: FastHadamardTransformer.java 1244107 2012-02-14 16:17:55Z erans $
  See Also:
    Serialized Form

- - ### Constructor Summary

    Constructors
    Constructor and Description
    `FastHadamardTransformer()`

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `protected double[]` | `fht(double[] x)` The FHT (Fast Hadamard Transformation) which uses only subtraction and addition.
    `protected int[]` | `fht(int[] x)` Returns the forward transform of the specified integer data set.
    `double[]` | `transform(double[] f, TransformType type)` Returns the (forward, inverse) transform of the specified real data set.
    `int[]` | `transform(int[] f)` Returns the forward transform of the specified integer data set.The integer transform cannot be inverted directly, due to a scaling factor which may lead to double results.
    `double[]` | `transform(UnivariateFunction f, double min, double max, int n, TransformType type)` Returns the (forward, inverse) transform of the specified real function, sampled on the specified interval.

    - ### Methods inherited from class java.lang.Object

      `clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- - ### Constructor Detail

    - #### FastHadamardTransformer

          public FastHadamardTransformer()

  - ### Method Detail

    - #### transform

          public double[] transform(double[] f,
                           TransformType type)

      Returns the (forward, inverse) transform of the specified real data set.
      Specified by:
        `transform` in interface `RealTransformer`
      Parameters:
        `f` - the real data array to be transformed (signal)
        `type` - the type of transform (forward, inverse) to be performed
      Returns:
        the real transformed array (spectrum)
      Throws:
        `MathIllegalArgumentException` - if the length of the data array is not a power of two

    - #### transform

          public double[] transform(UnivariateFunction f,
                           double min,
                           double max,
                           int n,
                           TransformType type)

      Returns the (forward, inverse) transform of the specified real function, sampled on the specified interval.
      Specified by:
        `transform` in interface `RealTransformer`
      Parameters:
        `f` - the function to be sampled and transformed
        `min` - the (inclusive) lower bound for the interval
        `max` - the (exclusive) upper bound for the interval
        `n` - the number of sample points
        `type` - the type of transform (forward, inverse) to be performed
      Returns:
        the real transformed array
      Throws:
        `NonMonotonicSequenceException` - if the lower bound is greater than, or equal to the upper bound
        `NotStrictlyPositiveException` - if the number of sample points is negative
        `MathIllegalArgumentException` - if the number of sample points is not a power of two

    - #### transform

          public int[] transform(int[] f)

      Returns the forward transform of the specified integer data set.The integer transform cannot be inverted directly, due to a scaling factor which may lead to double results.
      Parameters:
        `f` - the integer data array to be transformed (signal)
      Returns:
        the integer transformed array (spectrum)
      Throws:
        `MathIllegalArgumentException` - if the length of the data array is not a power of two

    - #### fht

          protected double[] fht(double[] x)
                          throws MathIllegalArgumentException

      The FHT (Fast Hadamard Transformation) which uses only subtraction and addition. Requires `N * log2(N) = n * 2^n` additions.

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

      1. x is the input vector to be transformed,
      2. y is the output vector (Fast Hadamard transform of x),
      3. a and b are helper rows.

      x | a | b | y
      --- | --- | --- | ---
      x0 | a0 = x0 + x1 | b0 = a0 + a1 | y0 = b0+ b1
      x1 | a1 = x2 + x3 | b0 = a2 + a3 | y0 = b2 + b3
      x2 | a2 = x4 + x5 | b0 = a4 + a5 | y0 = b4 + b5
      x3 | a3 = x6 + x7 | b0 = a6 + a7 | y0 = b6 + b7
      x4 | a0 = x0 - x1 | b0 = a0 - a1 | y0 = b0 - b1
      x5 | a1 = x2 - x3 | b0 = a2 - a3 | y0 = b2 - b3
      x6 | a2 = x4 - x5 | b0 = a4 - a5 | y0 = b4 - b5
      x7 | a3 = x6 - x7 | b0 = a6 - a7 | y0 = b6 - b7

      ### How it works

      1. Construct a matrix with `N` rows and `n + 1` columns, `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])
      2. Place the input vector `x[N]` in the first column of the matrix `hadm`.
      3. The entries of the submatrix `D_top` are calculated as follows
         - `D_top` goes from entry `[0][1]` to `[N / 2 - 1][n + 1]`,
         - the columns of `D_top` are the pairwise mutually exclusive sums of the previous column.
      4. The entries of the submatrix `D_bottom` are calculated as follows
         - `D_bottom` goes from entry `[N / 2][1]` to `[N][n + 1]`,
         - the columns of `D_bottom` are the pairwise differences of the previous column.
      5. The consputation of `D_top` and `D_bottom` are best understood with the above example (for `N = 8`).
      6. The output vector `y` is now in the last column of `hadm`.
      7. Algorithm from chipcenter.

      ### Visually

      | 0 | 1 | 2 | 3 | … | n + 1
      0 | x0 | ↑ ← Dtop → ↓
      1 | x1
      2 | x2
      … | …
      N / 2 - 1 | xN/2-1
      N / 2 | xN/2 | ↑ ← Dbottom → ↓
      N / 2 + 1 | xN/2+1
      N / 2 + 2 | xN/2+2
      … | …
      N | xN

      Parameters:
        `x` - the real data array to be transformed
      Returns:
        the real transformed array, `y`
      Throws:
        `MathIllegalArgumentException` - if the length of the data array is not a power of two

    - #### fht

          protected int[] fht(int[] x)
                       throws MathIllegalArgumentException

      Returns the forward transform of the specified integer data set. The FHT (Fast Hadamard Transform) uses only subtraction and addition.
      Parameters:
        `x` - the integer data array to be transformed
      Returns:
        the integer transformed array, `y`
      Throws:
        `MathIllegalArgumentException` - if the length of the data array is not a power of two

Copyright © 2003-2012 The Apache Software Foundation. All Rights Reserved.