/* * Licensed to the Apache Software Foundation (ASF) under one or more * contributor license agreements. See the NOTICE file distributed with * this work for additional information regarding copyright ownership. * The ASF licenses this file to You under the Apache License, Version 2.0 * (the "License"); you may not use this file except in compliance with * the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ package org.apache.commons.math3.transform; import org.apache.commons.math3.analysis.FunctionUtils; import org.apache.commons.math3.analysis.UnivariateFunction; import org.apache.commons.math3.exception.MathIllegalArgumentException; import org.apache.commons.math3.exception.util.LocalizedFormats; import org.apache.commons.math3.util.ArithmeticUtils; import java.io.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 */ public class FastHadamardTransformer implements RealTransformer, Serializable { /** Serializable version identifier. */ static final long serialVersionUID = 20120211L; /** * {@inheritDoc} * * @throws MathIllegalArgumentException if the length of the data array is not a power of two */ public double[] transform(final double[] f, final TransformType type) { if (type == TransformType.FORWARD) { return fht(f); } return TransformUtils.scaleArray(fht(f), 1.0 / f.length); } /** * {@inheritDoc} * * @throws org.apache.commons.math3.exception.NonMonotonicSequenceException if the lower bound * is greater than, or equal to the upper bound * @throws org.apache.commons.math3.exception.NotStrictlyPositiveException if the number of * sample points is negative * @throws MathIllegalArgumentException if the number of sample points is not a power of two */ public double[] transform( final UnivariateFunction f, final double min, final double max, final int n, final TransformType type) { return transform(FunctionUtils.sample(f, min, max, n), type); } /** * 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. * * @param f the integer data array to be transformed (signal) * @return the integer transformed array (spectrum) * @throws MathIllegalArgumentException if the length of the data array is not a power of two */ public int[] transform(final int[] f) { return fht(f); } /** * The FHT (Fast Hadamard Transformation) which uses only subtraction and addition. Requires * {@code N * log2(N) = n * 2^n} additions. * *
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 | *
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 |