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).
* @version $Revision: 1070725 $ $Date: 2011-02-15 02:31:12 +0100 (mar. 15 févr. 2011) $ * @since 2.0 */ public class FastHadamardTransformer implements RealTransformer { /** {@inheritDoc} */ public double[] transform(double f[]) throws IllegalArgumentException { return fht(f); } /** {@inheritDoc} */ public double[] transform(UnivariateRealFunction f, double min, double max, int n) throws FunctionEvaluationException, IllegalArgumentException { return fht(FastFourierTransformer.sample(f, min, max, n)); } /** {@inheritDoc} */ public double[] inversetransform(double f[]) throws IllegalArgumentException { return FastFourierTransformer.scaleArray(fht(f), 1.0 / f.length); } /** {@inheritDoc} */ public double[] inversetransform(UnivariateRealFunction f, double min, double max, int n) throws FunctionEvaluationException, IllegalArgumentException { final double[] unscaled = fht(FastFourierTransformer.sample(f, min, max, n)); return FastFourierTransformer.scaleArray(unscaled, 1.0 / n); } /** * Transform the given real data set. *The integer transform cannot be inverted directly, due to a scaling * factor it may lead to double results.
* @param f the integer data array to be transformed (signal) * @return the integer transformed array (spectrum) * @throws IllegalArgumentException if any parameters are invalid */ public int[] transform(int f[]) throws IllegalArgumentException { return fht(f); } /** * The FHT (Fast Hadamard Transformation) which uses only subtraction and addition. *
*
* +----+----------+---------+----------+
* | 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
*
* +--------+---+---+---+-----+---+
* | 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
* @exception IllegalArgumentException if input array is not a power of 2
*/
protected double[] fht(double x[]) throws IllegalArgumentException {
// n is the row count of the input vector x
final int n = x.length;
final int halfN = n / 2;
// n has to be of the form n = 2^p !!
if (!FastFourierTransformer.isPowerOf2(n)) {
throw MathRuntimeException.createIllegalArgumentException(
LocalizedFormats.NOT_POWER_OF_TWO,
n);
}
// Instead of creating a matrix with p+1 columns and n rows
// we will use two single dimension arrays which we will use in an alternating way.
double[] yPrevious = new double[n];
double[] yCurrent = x.clone();
// iterate from left to right (column)
for (int j = 1; j < n; j <<= 1) {
// switch columns
final double[] yTmp = yCurrent;
yCurrent = yPrevious;
yPrevious = yTmp;
// iterate from top to bottom (row)
for (int i = 0; i < halfN; ++i) {
// Dtop
// The top part works with addition
final int twoI = 2 * i;
yCurrent[i] = yPrevious[twoI] + yPrevious[twoI + 1];
}
for (int i = halfN; i < n; ++i) {
// Dbottom
// The bottom part works with subtraction
final int twoI = 2 * i;
yCurrent[i] = yPrevious[twoI - n] - yPrevious[twoI - n + 1];
}
}
// return the last computed output vector y
return yCurrent;
}
/**
* The FHT (Fast Hadamard Transformation) which uses only subtraction and addition.
* @param x input vector
* @return y output vector
* @exception IllegalArgumentException if input array is not a power of 2
*/
protected int[] fht(int x[]) throws IllegalArgumentException {
// n is the row count of the input vector x
final int n = x.length;
final int halfN = n / 2;
// n has to be of the form n = 2^p !!
if (!FastFourierTransformer.isPowerOf2(n)) {
throw MathRuntimeException.createIllegalArgumentException(
LocalizedFormats.NOT_POWER_OF_TWO,
n);
}
// Instead of creating a matrix with p+1 columns and n rows
// we will use two single dimension arrays which we will use in an alternating way.
int[] yPrevious = new int[n];
int[] yCurrent = x.clone();
// iterate from left to right (column)
for (int j = 1; j < n; j <<= 1) {
// switch columns
final int[] yTmp = yCurrent;
yCurrent = yPrevious;
yPrevious = yTmp;
// iterate from top to bottom (row)
for (int i = 0; i < halfN; ++i) {
// Dtop
// The top part works with addition
final int twoI = 2 * i;
yCurrent[i] = yPrevious[twoI] + yPrevious[twoI + 1];
}
for (int i = halfN; i < n; ++i) {
// Dbottom
// The bottom part works with subtraction
final int twoI = 2 * i;
yCurrent[i] = yPrevious[twoI - n] - yPrevious[twoI - n + 1];
}
}
// return the last computed output vector y
return yCurrent;
}
}