Top Description Fields Constructors Methods
org.apache.commons.math3.transform

public Class FastHadamardTransformer

extends Object
implements RealTransformer, Serializable
Class Inheritance
All Implemented Interfaces
java.io.Serializable, org.apache.commons.math3.transform.RealTransformer
Imports
java.io.Serializable, org.apache.commons.math3.analysis.FunctionUtils, .UnivariateFunction, org.apache.commons.math3.exception.MathIllegalArgumentException, org.apache.commons.math3.exception.util.LocalizedFormats, org.apache.commons.math3.util.ArithmeticUtils
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

Field Summary

Modifier and TypeField and Description
pack-priv static final long
serialVersionUID

Serializable version identifier.

Constructor Summary

AccessConstructor and Description
public
FastHadamardTransformer()

Method Summary

Modifier and TypeMethod and Description
protected double[]

Returns:

the real transformed array, y
fht(double[]
the real data array to be transformed
x)

The FHT (Fast Hadamard Transformation) which uses only subtraction and addition.

protected int[]

Returns:

the integer transformed array, y
fht(int[]
the integer data array to be transformed
x)

Returns the forward transform of the specified integer data set.

public double[]
transform(final double[]
the real data array to be transformed (signal)
f, final TransformType
the type of transform (forward, inverse) to be performed
type)

Implements org.apache.commons.math3.transform.RealTransformer.transform.

Returns the (forward, inverse) transform of the specified real data set.

public double[]
transform(final UnivariateFunction
the function to be sampled and transformed
f, final double
the (inclusive) lower bound for the interval
min, final double
the (exclusive) upper bound for the interval
max, final int
the number of sample points
n, final TransformType
the type of transform (forward, inverse) to be performed
type)

Implements org.apache.commons.math3.transform.RealTransformer.transform.

Returns the (forward, inverse) transform of the specified real function, sampled on the specified interval.

public int[]

Returns:

the integer transformed array (spectrum)
transform(final int[]
the integer data array to be transformed (signal)
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.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

serialVersionUIDback to summary
pack-priv static final long serialVersionUID

Serializable version identifier.

Constructor Detail

FastHadamardTransformerback to summary
public FastHadamardTransformer()

Method Detail

fhtback to summary
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

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:double[]

the real data array to be transformed

Returns:double[]

the real transformed array, y

Exceptions
MathIllegalArgumentException:
if the length of the data array is not a power of two
fhtback to summary
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:int[]

the integer data array to be transformed

Returns:int[]

the integer transformed array, y

Exceptions
MathIllegalArgumentException:
if the length of the data array is not a power of two
transformback to summary
public double[] transform(final double[] f, final TransformType type)

Implements org.apache.commons.math3.transform.RealTransformer.transform.

Doc from org.apache.commons.math3.transform.RealTransformer.transform.

Returns the (forward, inverse) transform of the specified real data set.

Parameters
f:double[]

the real data array to be transformed (signal)

type:TransformType

the type of transform (forward, inverse) to be performed

Returns:double[]

the real transformed array (spectrum)

Exceptions
MathIllegalArgumentException:
if the length of the data array is not a power of two
transformback to summary
public double[] transform(final UnivariateFunction f, final double min, final double max, final int n, final TransformType type)

Implements org.apache.commons.math3.transform.RealTransformer.transform.

Doc from org.apache.commons.math3.transform.RealTransformer.transform.

Returns the (forward, inverse) transform of the specified real function, sampled on the specified interval.

Parameters
f:UnivariateFunction

the function to be sampled and transformed

min:double

the (inclusive) lower bound for the interval

max:double

the (exclusive) upper bound for the interval

n:int

the number of sample points

type:TransformType

the type of transform (forward, inverse) to be performed

Returns:double[]

the real transformed array

Exceptions
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
transformback to summary
public int[] transform(final 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:int[]

the integer data array to be transformed (signal)

Returns:int[]

the integer transformed array (spectrum)

Exceptions
MathIllegalArgumentException:
if the length of the data array is not a power of two