Class FastHadamardTransformer
java.lang.Object
org.apache.commons.math.transform.FastHadamardTransformer
- All Implemented Interfaces:
RealTransformer
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:
- $Revision: 1070725 $ $Date: 2011-02-15 02:31:12 +0100 (mar. 15 févr. 2011) $
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprotected double[]
fht
(double[] x) The FHT (Fast Hadamard Transformation) which uses only subtraction and addition.protected int[]
fht
(int[] x) The FHT (Fast Hadamard Transformation) which uses only subtraction and addition.double[]
inversetransform
(double[] f) Inversely transform the given real data set.double[]
inversetransform
(UnivariateRealFunction f, double min, double max, int n) Inversely transform the given real function, sampled on the given interval.double[]
transform
(double[] f) Transform the given real data set.int[]
transform
(int[] f) Transform the given real data set.double[]
transform
(UnivariateRealFunction f, double min, double max, int n) Transform the given real function, sampled on the given interval.
-
Constructor Details
-
FastHadamardTransformer
public FastHadamardTransformer()
-
-
Method Details
-
transform
Transform the given real data set.- Specified by:
transform
in interfaceRealTransformer
- Parameters:
f
- the real data array to be transformed (signal)- Returns:
- the real transformed array (spectrum)
- Throws:
IllegalArgumentException
- if any parameters are invalid
-
transform
public double[] transform(UnivariateRealFunction f, double min, double max, int n) throws FunctionEvaluationException, IllegalArgumentException Transform the given real function, sampled on the given interval.- Specified by:
transform
in interfaceRealTransformer
- Parameters:
f
- the function to be sampled and transformedmin
- the lower bound for the intervalmax
- the upper bound for the intervaln
- the number of sample points- Returns:
- the real transformed array
- Throws:
FunctionEvaluationException
- if function cannot be evaluated at some pointIllegalArgumentException
- if any parameters are invalid
-
inversetransform
Inversely transform the given real data set.- Specified by:
inversetransform
in interfaceRealTransformer
- Parameters:
f
- the real data array to be inversely transformed (spectrum)- Returns:
- the real inversely transformed array (signal)
- Throws:
IllegalArgumentException
- if any parameters are invalid
-
inversetransform
public double[] inversetransform(UnivariateRealFunction f, double min, double max, int n) throws FunctionEvaluationException, IllegalArgumentException Inversely transform the given real function, sampled on the given interval.- Specified by:
inversetransform
in interfaceRealTransformer
- Parameters:
f
- the function to be sampled and inversely transformedmin
- the lower bound for the intervalmax
- the upper bound for the intervaln
- the number of sample points- Returns:
- the real inversely transformed array
- Throws:
FunctionEvaluationException
- if function cannot be evaluated at some pointIllegalArgumentException
- if any parameters are invalid
-
transform
Transform the given real data set.The integer transform cannot be inverted directly, due to a scaling factor it may lead to double results.
- Parameters:
f
- the integer data array to be transformed (signal)- Returns:
- the integer transformed array (spectrum)
- Throws:
IllegalArgumentException
- if any parameters are invalid
-
fht
The FHT (Fast Hadamard Transformation) which uses only subtraction and addition.
Requires Nlog2N = n2n additions.
Short Table of manual calculation for N=8:- x is the input vector we want to transform
- y is the output vector which is our desired result
- a and b are just 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 | +----+----------+---------+----------+
- 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][m]) - Place the input vector x[N] in the first column of the matrix hadm
- 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 - 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 - How Dtop and Dbottom you can understand best with the example for N=8 above.
- The output vector y is now in the last column of hadm
- Algorithm from: http://www.archive.chipcenter.com/dsp/DSP000517F1.html
Visually+--------+---+---+---+-----+---+ | 0 | 1 | 2 | 3 | ... |n+1| +------+--------+---+---+---+-----+---+ |0 | x0 | /\ | |1 | x1 | || | |2 | x2 | invalid input: '<'= Dtop => | |... | ... | || | |N/2-1 | xN/2-1 | \/ | +------+--------+---+---+---+-----+---+ |N/2 | xN/2 | /\ | |N/2+1 | xN/2+1 | || | |N/2+2 | xN/2+2 | invalid input: '<'= Dbottom => | which is in the last column of the matrix |... | ... | || | |N | xN/2 | \/ | +------+--------+---+---+---+-----+---+
- Parameters:
x
- input vector- Returns:
- y output vector
- Throws:
IllegalArgumentException
- if input array is not a power of 2
-
fht
The FHT (Fast Hadamard Transformation) which uses only subtraction and addition.- Parameters:
x
- input vector- Returns:
- y output vector
- Throws:
IllegalArgumentException
- if input array is not a power of 2
-