Fast Walsh–Hadamard transform
- Fast Walsh–Hadamard transform
In computational mathematics, the Hadamard ordered fast Walsh–Hadamard transform (FWHTh) is an efficient algorithm to compute the Walsh–Hadamard transform (WHT). A naive implementation of the WHT would have a computational complexity of O(). The FWHTh requires only additions or subtractions.
The FWHTh is a divide and conquer algorithm that recursively breaks down a WHT of size into two smaller WHTs of size . This implementation follows the recursive definition of the Hadamard matrix :
:
The normalization factors for each stage may be grouped together or even omitted.
The Sequency ordered, also known as Walsh ordered, fast Walsh–Hadamard transform, FWHTw, is obtained by computing the FWHTh as above, and then rearranging the outputs.
References
* Fino, B.J., and Algazi, V.R., 1976, "Unified Matrix Treatment of the Fast Walsh–Hadamard Transform," "IEEE Transactions on Computers" 25: 1142–1146.
Wikimedia Foundation.
2010.
Look at other dictionaries:
Hadamard transform — The Hadamard transform (also known as the Walsh Hadamard transform, Hadamard Rademacher Walsh transform, Walsh transform, or Walsh Fourier transform) is an example of a generalized class of Fourier transforms. It is named for the French… … Wikipedia
Hadamard (disambiguation) — Hadamard may refer to* Jacques Hadamard * Hadamard gate * Hadamard matrix * Hadamard s inequality * Hermite–Hadamard inequality * Walsh–Hadamard transform * Fast Walsh–Hadamard transform … Wikipedia
List of mathematics articles (F) — NOTOC F F₄ F algebra F coalgebra F distribution F divergence Fσ set F space F test F theory F. and M. Riesz theorem F1 Score Faà di Bruno s formula Face (geometry) Face configuration Face diagonal Facet (mathematics) Facetting… … Wikipedia
FHT — FHT, a three letter acronym, may refer to:*Female hose thread, a type of threaded pipe usually found on garden hoses that connects to the male hose thread *Fetal heart tones, the normal rate of which remains 120 160 during pregnancy *Fast Walsh… … Wikipedia
Fwt — FWT, a three letter acronym, may refer to:*Fixed wireless terminal *Fast Walsh Hadamard transform … Wikipedia
MAGENTA — MAGENTA блочный шифр, разработанный Майклом Якобсоном и Клаусом Хубером для немецкой телекоммуникационной компании Deutsche Telekom AG. MAGENTA является сокращением от Multifunctional Algorithm for General purpose Encryption and Network… … Википедия
Multi-carrier code division multiple access — (MC CDMA) is a multiple access scheme used in OFDM based telecommunication systems, allowing the system to support multiple users at the same time. MC CDMA spreads each user symbol in the frequency domain. That is, each user symbol is carried… … Wikipedia
Rayleigh fading — is a statistical model for the effect of a propagation environment on a radio signal, such as that used by wireless devices.Rayleigh fading models assume that the magnitude of a signal that has passed through such a transmission medium (also… … Wikipedia
List of Fourier-related transforms — This is a list of linear transformations of functions related to Fourier analysis. Such transformations map a function to a set of coefficients of basis functions, where the basis functions are sinusoidal and are therefore strongly localized in… … Wikipedia
DFT matrix — A DFT matrix is an expression of a discrete Fourier transform (DFT) as a matrix multiplication. Contents 1 Definition 2 Examples 2.1 Two point 2.2 Four point … Wikipedia
