Class 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).

    See Also:
    Serialized Form
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method 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.
    • Constructor Detail

      • FastHadamardTransformer

        public FastHadamardTransformer()
        Empty constructor.

        This constructor is not strictly necessary, but it prevents spurious javadoc warnings with JDK 18 and later.

        Since:
        3.0
    • 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:
        MathIllegalArgumentException - if the lower bound is greater than, or equal to the upper bound
        MathIllegalArgumentException - 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.
        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.
        Short Table of manual calculation for N=8
        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
        0123 n + 1
        0 x0
        ← Dtop
        1x1
        2x2
        N / 2 - 1xN/2-1
        N / 2 xN/2
        ← Dbottom
        N / 2 + 1xN/2+1
        N / 2 + 2xN/2+2
        NxN
        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