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.

- 1969
*Algorithm:*Shanks gives an algorithm producing the dyadic (Paley) or bit-reversed form of the result.

- 1970
- 1971
*Application:*Kak applies Walsh-Fourier transforms to measuring the amount of randomness in a finite random sequence.

- 1972
- 1973
*Algorithm:*Carl and Swartwood present an algorithm for taking in-order data to bit-reversed sequency results. Interestingly, each stage performs exactly the same operations on exactly the same element positions.*Application:*Edwards discusses the synthesis of logic-gate design by transforming the desired function into a Walsh series and operating on that.*Application:*Corrington solves differential and integral equations by converting the equations to a truncated Walsh series then working on the Walsh representation.

- 1976
*Algorithm:*Larsen presents a FWT complementary to Manz, taking data in normal order and returns the result in bit-reversed sequency order.

- 1977
*Application:*Yuen proposes using Walsh transforms to test random number sequences.*Application:*Cohn and Lempel show a relationship between LFSR sequences and Walsh-Hadamard matrices. This can be exploited and a fast Walsh algorithm applied to identify the signal "phase" from a given LFSR.*Algorithm:*Brown presents a fast Walsh transform (FWT) which takes in-order data to in-order sequency results.

*Application:*Shih and Han show how Walsh functions can be used to help solve first-order partial differential equations.*Review:*Beer has some comments on Beauchamp's book.

- 1981
*Tutorial:*Beer provides an introduction to the theory and application of Walsh transforms.

- 1984
- 1987
- 1988
*Application:*Guo-Zhen and Massey relate Walsh transforms to correlation in combining functions.

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 i^{th} 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., 2^{k}."

"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 *i*th 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
2^{n} values, we would read in, or generate
2^{n-m} values at a time, compute the
2^{n-m}-point fast Walsh transform of the
segment, square, and add the squares to the
2^{n-m} memory locations which have been
initially set to zero. After all 2^{m} 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 *N*^{2} to *N*log_{2}*N*
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:

- Fig. 2.3, "A flow diagram for a sequency-ordered Walsh transform," but apparently produces the dyadic (Paley) ordering.
- Fig. 2.6, "A dyadic-ordered Walsh transform," shows input in sequential order, but apparently should actually be in bit-reversed order.
- Fig. 2.7 is "A natural-ordered Walsh transform."
- Fig. 2.8 is "A Manz sequency-ordered Walsh transform."
- Fig. 2.9 is "A Larsen sequence-ordered Walsh transform."

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 *m*th-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