Most introductions to Walsh-Hadamard transforms are heavily mathematical and difficult to relate to practice. But the transformation process itself is just arithmetic, and has an easily-comprehended structure which could be widely understood. The result is often thought of as "a poor-man's fast Fourier transform (FFT)" representing the conversion of a time-sampled signal into an equivalent frequency-sampled form. Since a fast Walsh transform (FWT) is much faster than an FFT, there is ample motive to seek reasonable applications. Unfortunately, the Walsh-Hadamard form of "digital frequency," or sequency is not intuitively close to the sine-wave form we normally associate with "frequency."
Fortunately, other aspects of the Walsh-Hadamard representation can be useful on their own. The transform can identify correlations in combining functions. Transformed data can be easier to manipulate for differential or integral equation solution, and some parts of digital circuit synthesis. There is apparently also an inherent relation to linear feedback shift registers which may be worth exploiting.
Shanks, J. 1969. Computation of the Fast Walsh-Fourier Transform. IEEE Transactions on Computers. C-18: 457-459.
"Abstract: -- The discrete, orthogonal Walsh functions can be generated by a multiplicative iteration equation. Using this iteration equation, an efficient Walsh transform computation algorithm is derived which is analogous to the Cooley-Tukey algorithm for the complex-exponential Fourier transform."
Henderson, K. 1970. Comment on "Computation of the Fast Walsh-Fourier Transform." IEEE Transactions on Computers. C-19: 850-851.
"Abstract -- The matrix form of the Walsh functions . . . can be generated by the modulo-2 product of two generating matrices: the natural binary code, and the transpose of the bit-reversed form of the first. As a result, the coefficients of the Walsh transform occur in bit-reversed order. By simply reordering the Walsh functions themselves to correspond to generation by the product of two such code matrices, neither or both in bit-reversed form, the Walsh coefficients occur in natural order."
Yuen, C. 1970. Walsh Functions and Gray Code. Proceedings of the Walsh Function Symposium. 68-73.
"Gray code is a natural way of ordering binary vectors in dyadic space, hence it appears frequently in connection with Walsh functions. In Paley's definition of Walsh functions their sequencies are arranged in Gray code."
"While neither Paley or Fine mentioned this, we now know that"
pal(g(i),x) = wal(i,x)
[ That is, the ith Walsh sequence is the same as the g(i)th Paley sequence, for Gray code function g(), e.g.: (0,1,3,2,6,7,5,4). ]
Kak, S. 1971. Classification of Random Binary Sequences Using Walsh-Fourier Analysis. Proceedings of Applications of Walsh Functions. 74-77. Washington, D.C., 1971.
"This paper presents a straightforward procedure using Walsh functions to determine the pattern in a binary sequence."
". . . classification of data amounts to the computation of structure with respect to some criterion."
"A sequence shall be said to have no pattern or be random if the number of independent amplitudes in the Wash-Fourier transform is equal to the length of the sequence itself, i.e., 2k."
"The measure of randomness r(s) shall be defined by"
r(s) = no. of independent amplitudes of W(s) / length of the sequence = i(s) / L(s)
"The number of independent amplitudes of W(s) shall equal the number of its component Walsh waves." [ The number of non-zero terms? ]
Yuen, C. 1972. Remarks on the Ordering of Walsh Functions. IEEE Transactions on Computers. C-21: 1452.
". . . Walsh functions are characters of the dyadic group, which is the group of binary vectors under bitwise addition modulo 2." "Since there is no natural ordering of the dyadic group, there is no natural ordering for Walsh functions."
"At least three different orderings of Walsh functions are known to have been used. The ordering originally employed by Walsh [6] is commonly known as 'sequency ordering.' This is characterized by the fact that the ith function wal(i,x) has i sign changes in the interval x in [0.1]. As the number of sign changes is used as a generalized frequency [7], the ordering is favored by communications engineers . . . ."
"A different ordering used by Paley [10] is characterized by the fact that in this form Walsh functions can be readily expressed as products of Rademacher functions. Most mathematical discussions use this form [11]."
"A third ordering, proposed by Henderson . . . is simply Paley's ordering in reversed binary. It is the ordering that emerges if one computes fast Walsh transforms without sorting, hence it is computationally advantageous."
"The conversion from Paley's ordering to Walsh's ordering is the same as conversion from Gray code to binary . . . ." "Just as we form a path of minimum length on the real line if we order integers by their arithmetic value, Gray code orders points in dyadic space into a path of minimum length."
Manz, J. 1972. A Sequency-Ordered Fast Walsh Transform. IEEE Transactions on Audio and Electroacoustics. AU-20: 204-205.
"The only drawback with the fast Hadamard transform (FHT) is that those matrices that possess a simple recursive formula and, therefore, a fast algorithm, are not capable of directly producing the output coefficients ordered by increasing frequency [4], [5]. Sequency, as define by Harmuth [6, p. 50], is one-half the average number of zero crossings per unit time interval. The ordering of the output coefficients of a typical FHT is called dyadic or Paley ordering [5]."
"In order to convert from dyadic to sequency ordering, the output coefficient ordering must be decoded by using a Gray code-to-binary decoder [5], [7]."
"By suitably modifying the FHT approach, a sequency-ordered FWT can be computed that shares all of the good properties of the FHT but eliminates the Gray code decoding."
"In the modified FHT, the input must be bit reversed prior to the actual transformation."
Carl, J. and R. Swartwood. 1973. A Hybrid Walsh Transform Computer. IEEE Transactions on Computers. C-22(7): 669-672.
"Good [5] developed a matrix factorization technique that leads to a fast transform algorithm."
"The . . . factorization results in a flow diagram for a computation algorithm that has the form of Fig. 1. Note the recursive structure of the algorithm: the interconnections of successive layers are identical."
"These results are easily extended to higher dimensions, but it is simpler to note that higher order transforms can be expressed as on-dimensional transforms with the inputs and outputs relabeled.
Edwards, C. 1973. The Application of the Rademacher/Walsh Transform to Digital Circuit Synthesis. Theory and Applications of Walsh Functions. The Hatfield Polytechnic; June 28th and 29th, 1973.
". . . certain operations in the Rademacher/Walsh transform domain may be used to facilitate logic synthesis. These operations are easily carried out with the aid of a small digital processor."
"If optimum syntheses of predominantly first-order functions are available then logic synthesis may be carried out wholly in the transform domain."
"The application of the Rademacher/Walsh transform to conventional logic synthesis serves to emphasize the, often neglected, role that exclusive-OR function plays in the completion of Boolean functions. Indeed, although the use of the exclusive-OR gate is usually avoided in conventional logic methods, it appears that their use is essential to the generation of elegant syntheses."
Corrington, M. 1973. Solution of Differential and Integral Equations with Walsh Functions. IEEE Transactions on Circuit Theory. CT-20(5): 470-476.
"Abstract -- Any well-behaved periodic waveform can be expressed as a series of Walsh functions. If the series is truncated at the end of any group of terms of a given order, the partial sum will be a stairstep approximation to the waveform. The height of each step will be the average value of the waveform over the same interval.
"If a zero-memory nonlinear transformation is applied to a Walsh series, the output series can be derived by simple algebraic processes. The coefficients of the input series will change, but there will be no new terms not in the original groups.
"Nonlinear differential and integral equations can be solved as a Walsh series, since the series for derivatives can always be integrated by simple table lookup. The differential equation is solved for the highest derivative first and the result is then integrated the required number of times to give the solution."
Larsen, H. 1976. An Algorithm to Compute the Sequency Ordered Walsh Transform. IEEE Transactions on Acoustics, Speech, and Signal Processing. ASSP-24: 335-336.
"The coefficients from Shanks' algorithm are in 'dyadic,' or Paley order, which is merely the naturally ordered coefficients after bit reversal. In many applications the most convenient ordering is with the coefficients corresponding to the Walsh functions arranged by increasing number of zero crossings. This is known as sequency ordering. Sequency ordering can be obtained from dyadic ordering by a permutation based on the gray code [3], [4]."
"In 1972, however, Manz [5] introduced a sequency ordered FWT which eliminates gray code reordering by suitably modifying the basic FHT structure." "Manz's algorithm requires the input data in bit-reversed order, returning the coefficients in sequency order."
"The algorithm presented here is complementary to the one developed by Manz, and has all the same advantages, namely that it is in place, and is its own inverse. It differs from Manz's algorithm in that it has a decimation-in time structure, and accepts data in normal order, returning the coefficients in bit-reversed sequency order."
Yuen, C. 1977. Testing Random Number Generators by Walsh Transform. IEEE Transactions on Computers. C-26(4): 329-333.
"Abstract -- A truly random sequence of numbers has an asymptotically flat Walsh power spectrum. This fact is used to devise a new test for the randomness of the output of random number generators."
"One essential randomness test is that of uncorrelatedness, i.e., that the autocorrelation of the sequence is approximately a d-function."
"A property equivalent to uncorrelatedness is that the power spectrum be flat."
"In this paper we propose another randomness test equivalent to the correlation test: that the Walsh power spectrum be flat." "Thus, testing the flatness of the spectrum is equivalent to testing for uncorrelatedness of the values of x."
". . . the band spectrum estimate can also be evaluated by spectrum averaging . . . ."
"With segment averaging there is no longer any difficulty with core requirements. When we wish to test a sequence of 2n values, we would read in, or generate 2n-m values at a time, compute the 2n-m-point fast Walsh transform of the segment, square, and add the squares to the 2n-m memory locations which have been initially set to zero. After all 2m segments have been processed these memory locations will contain the band spectrum estimate, and we can then proceed to examine if it is consistent with a flat S."
"Another possible additional test is that we permute the random numbers in some way before Walsh transformation. Given a truly random sequence, we should still get a flat spectrum regardless of what permutation was tried."
Cohn, M. and A. Lempel. 1977. On Fast M-Sequence Transforms. IEEE Transactions on Information Theory. IT-23: 135-137.
"An M-sequence is a binary sequence generated by a linear feedback shift-register whose characteristic polynomial is primitive. An M-sequence can be shown to have an impulse-like autocorrelation function [1]; for this reason M-sequences are often called "pseudo-noise sequences," and their distinct cyclic permutations, or phases, form a useful signalling alphabet [1]-[3]. A drawback is that correlation-detection at the receiver end [is very costly]." "The cost of this computation can be drastically reduced by exploiting the equivalence between the M-sequence matrix and the Walsh-Hadamard matrix." "[This] has been successfully used in the rapid decoding of first-order Reed-Muller codes [3]-[5]."
Brown, R. 1977. A Recursive Algorithm for Sequency-Ordered Fast Walsh Transforms. IEEE Transactions on Computers. C-26(8): 819-822.
"The FWT [Fast Walsh Transform] may be developed by analog with the Cooley-Tukey algorithm [7] for the fast Fourier transform (FFT). Implementation of the FWT results in a reduction of the number of computations from N2 to Nlog2N when applied to a sampled data set of N elements. Shanks [8] described such an FWT, which used the multiplicative iteration equations for calculating the discrete Walsh functions. However, this algorithm produced FWT in dyadic or natural order instead of the sequency order more useful for spectral analysis. (Sequency, first defined by Harmuth [2], is one-half the average number of zero-crossings per unit interval.) A similar FWT algorithm, based on the Cooley-Tukey algorithm, was developed by Manz [9] which produced sequency-ordered transforms but required bit-reversal of the input data."
Shih, Y. and J. Han. 1978. Double Walsh series solution of first-order partial differential equations. International Journal of Systems Science. 9(5): 569-578.
"A double Walsh series is introduced to represent approximately functions of two independent variables, and is then applied to analyze single as well as simultaneous first-order partial differential equations. The solutions for the coefficient matrices can be obtained directly from Kronecker product formulae, which are suitable for computer computation. An example for a single first-order partial differential equation is solved by a double Walsh series approximation with satisfactory results."
Beer, T. 1978. (Book Review.) Search. 9: 421.
". . . the Walsh transform proceeds by additions and subtractions and is thus far more efficient in use of computer time than the Fourier transform. There has long been a need for a readable, comprehensive text on Walsh functions and their applications. This need continues unabated."
"It is inexcusable that Beauchamp, who is described as Director of Computer Services at the University of Lancaster, presents a volume full of incorrect and inefficient computer programs."
Beer, T. 1981. Walsh transforms. American Journal of Physics. 49(5): 466-472.
"Walsh functions are an orthogonal set of square-wave functions that arise when dealing with digital data. The Walsh transform and inverse Walsh transform are easy to calculate by hand, and can be very quickly done on digital computers. Examples of the uses of Walsh transform include . . . the rapid solution of nonlinear differential equations."
". . . I have found that undergraduate students experience a great amount of difficulty in understanding the concept of digital Fourier transforms. The study of Walsh transforms provides an excellent introduction to this, because their simplicity enables calculations to be made by hand . . . ."
Beauchamp, K. 1984. Applications of Walsh and Related Functions. Academic Press.
This is currently the one book with the most information in one place (but see Beer for a review of the earlier version).
Perhaps the most useful section is 2.3, which gives a number of Fast Walsh Transforms (FWT's) in graphic "butterfly" diagrams.
A butterfly is the fundamental operation in many fast transforms, and shows the processing of two elements in one stage of the transform. For FWT's, typically the sum and difference of the two elements are calculated. Frequently, these operations conveniently occur in place, that is, the results are placed back into the same storage elements.
Various butterfly diagrams are given, including:
Tezuka, S. 1987. Walsh-Spectral Test for GFSR Pseudorandom Numbers. Communications of the ACM. 30(8): 731-735.
"ABSTRACT: By applying Weyl's criterion for k-distributivity to GFSR sequences, we derive a new theoretical test for investigating the statistical property of GFSR sequences."
"It is well known that Walsh-spectral analysis provides certain information about the dyadic correlation of a sequence [1]. This paper shows that Walsh-spectral analysis can also be exploited to investigate the k-distribution of the sequence."
Feldman, F. 1987. Fast Spectral Tests for Measuring Nonrandomness and the DES. Advances in Cryptology -- CRYPTO '87. 243-254. Springer-Verlag.
"Abstract -- Two spectral tests for detecting nonrandomness were proposed in 1977. One test, developed by J. Gait [1], considered properties of power spectra obtained from the discrete Fourier transform of finite binary strings."
"Another test, developed by C. Yuen [2], considered analogous properties for the Walsh transform. In estimating variance of spectral bands, Yuen assumes the spectral components to be independent. Except for the special case of Gaussian random numbers, this assumption introduces a significant error into his estimate."
"A new test, based on an evaluation of the Walsh spectrum, is presented here. This test extends the earlier test of C. Yuen."
"We prove that our measure of the Walsh spectrum is equivalent to a measure of the skirts of the logical autocorrelation function. It is clear that an analogous relationship exists between Fourier periodograms and the circular autocorrelation function."
Guo-Zhen, X. and J. Massey. 1988. A Spectral Characterization of Correlation-Immune Combining Functions. IEEE Transactions on Information Theory. 34(3): 569-571.
"Abstract -- It is shown that a Boolean combining function f(x) of n variables is mth-order correlation immune if and only if its Walsh transform F(w) vanishes for all w with Hamming weights between 1 and m, inclusive."
Last updated: 1996-08-15