Occasionally you come across a concept that appears deceptively simple, yet later you're surprised at the elegance and breadth of its utility. The Hadamard transform provides such a surprise. Its wonderfully symmetric form lends itself to applications ranging across many technical fields. An enlightening book, Hadamard Matrix Analysis and Synthesis With Applications to Communications and Signal/Image Processing (Ref 1), focuses on both the analysis and application of Hadamard matrices. It serves as a good guide for exploring both the Hadamard transform and its efficient implementation, the fast Hadamard transform (FHT).

Build a Hadamard matrix

The origins of the Hadamard matrix go back at least to 1867 when, in a most interestingly titled article (Ref 2), J Sylvester published his construction of what later became known as the Hadamard matrix. Hadamard published his work in 1893, and later work in the same area came from Rademacher (1922) and Walsh (1923). Consequently, the Hadamard matrix and transform are known by a multitude of names, usually some combination of Hadamard-Rademacher-Walsh or Sylvester (see Refs 1 and 3 for references to the original papers.)

This article deals exclusively with the most convenient of the Hadamard matrices: the square Sylvester construction. They're all based on the fundamental matrix

If you multiply a 2-point vector (x = [x₀ x₁]^T) by H₁, you get the sum and difference of the two points. y = H₁x,

This result is the "2-point Hadamard transform" of the vector x, and it's exactly the same as a 2-point discrete Fourier transform (DFT). The sum and difference operation found in these 2-point transforms is called a 2-point butterfly because of the crossing flow of data from input to output. It's well known that this butterfly leads to the fast Fourier transform (FFT), but it leads to the fast Hadamard transform (FHT), as well.

Because a 2-point FHT isn't very useful, let's explore how to perform larger ones. Doing so requires the construction of larger Hadamard matrices. Sylvester's construction generates higher-order matrices by a simple recursion. For example, it generates the 4 x 4 Hadamard matrix, H₂, by taking the fundamental matrix, H₁, and substituting H₁ for each 1 inside:

For notational simplicity, a plus sign (+) indicates a value of +1, and a minus sign (-) indicates -1. Notice that H₂ is a square matrix with double the number of rows and columns as H₁.

To generate each successively higher-order matrix, repeat the substitution, this time using H₂ for each + and -H₂ for each - found in H₁. For example,

For any integer value of n, the n^th-order matrix, H_n, has a size N x N, where N= 2ⁿ. You can always find the next highest-order matrix, H_n, from H_n-1, by using the recursion H_n = H₁ ý H_n-1 where ý denotes the Kronecker product, which replaces each +/- entry in H₁ with ± H_n-1, according to the sign.

To calculate H_n using the above recursion, you first must generate all the lower-order matrices. Fortunately, researchers have developed several clever ways to generate H_n directly rather than with recursion (Refs 1 and 3). One of the cleverest uses a binary counting matrix, B_n, the elements of which simply run from 0 to N-1, in binary, with one value per row (N = 2ⁿ). Each binary number uses n bits, so B_n has 2ⁿ rows and n columns. For example, the first three counting matrices are:

To generate the n^th-order Hadamard matrix, simply calculate H_n = B_nB_n^T and then replace each 0 with +1 and each 1 with -1. For example,

Hadamard matrix properties

Hadamard matrices possess many curious and useful properties. The matrices are symmetric, which means the m^th row is equal to the m^th column. They're orthogonal, meaning that the dot product between any two rows equals zero, and by symmetry the dot product between any two columns also equals zero. Thus if you compare any two rows, they match in exactly N/2 places and differ in N/2 places, and so the Hamming distance between them is exactly N/2. Furthermore, exactly half of the places that match are +1s, and the other half are -1s. Exactly half of the places that differ are (-1, +1) pairs, and exactly half are (+1, -1) pairs. Every row of a Hadamard matrix (except for the first) has exactly N/2 instances of +1 and N/2 instances of -1. In addition, Hadamard matrices are self inverting (within a constant) such that H_n^-1 = (1/2ⁿ )H_n.

Another interesting property is the sequence number of each row, which indicates the number of transitions from +1 to -1 and from -1 to +1. A row's sequence number is called its sequency because it measures the number of zero crossings in a given interval. It's analogous to the frequency of a sinusoid. Each row has its own unique sequency value, in the range [0, N-1]. A row's sequency, however, doesn't match its natural order (the row number). You can see this by examining Table 1 for the row-by-row sequency values of H₁, H₂ and H₃.

Rows	0	1	2	3	4	5	6	7
H1	0	1
H2	0	3	1	2
H3	0	7	3	4	1	6	2	5

Table 1 -- Sequency values of each row (and column) of H1, H2 and H3.

An intriguing method exists to determine the sequency of any row in a Hadamard matrix. Begin by noting that the 1st binary counting matrix, B₁, exactly specifies the sequency of H₁: the sequency of Row 0 is 0, and the sequency of Row 1 is 1. In other words, the sequency matrix S₁ equals B₁. To determine the sequency values for H₂, construct the second sequency matrix S₂ by stacking S₁on top of itself and extending it to the right by one binary column:

As shown, S₂ has 2² rows and 2 columns (in binary). In decimal, it has 2² rows and 1 column. Notice that you generate S₂ by using S₁ twice. In doing so, you fill up the leftmost first binary column of S₂, but you still need to add an additional binary digit (column) so the sequency can count from 0 to 3. In the top half of S₂ (binary matrix above), you replicate the least-significant bit in each row of S₁. Let's denote the repeated bits as the 2 x 1 vector S_1-LSB. In this example S₁ has only one bit, so you simply replicate it. In the bottom half of S₂, reuse the bits in S_1-LSB but invert them. The overbar denotes this inversion.

More generally, you calculate the sequency matrix, S_n, for an n^th-order Hadamard matrix by continuing this procedure. S_n has 2ⁿ rows and n columns (in binary), or 2ⁿ rows and 1 column (in decimal). Using the binary version of the matrices, you generate S_n+1 from S_n as

where again, S_n-LSB is a column vector containing the single LSBs from the 2ⁿ rows of S_n. You calculate the sequency by converting the binary version of the array into decimal.

Fast Hadamard Transform

Now that you're familiar with the Hadamard matrix and how to work with it, note that the Hadamard transform of an N = 2ⁿ dimensional vector x is simply y = H_nx. Because the Hadamard matrix consists of ±1s, the computation consists of adding and subtracting the components of x. It involves no multiplies, and if the components of x are all integers, the computation doesn't require any floating-point operations at all. However, by implementing the Hadamard transform with a straightforward matrix multiplication as written, it requires a hefty N² = 2²ⁿ operations.

Instead, you should implement one of the fast Hadamard transform (FHT) algorithms that exploit many of the symmetries discussed above. Many of these fast algorithms require only Nlog₂N = n2ⁿ additions. Ref 1 presents several versions including the most elegant FHT algorithm this author has seen. That FHT algorithm proceeds as follows:

1. Construct n+1 columns, each with N = 2ⁿ rows.
2. Place the input vector x in the 1st column.
3. Moving left to right, fill in the next column as follows:

   a. In the top half of this column, place the pairwise, mutually exclusive sums of the previous column.
   b. In the bottom half, place the pairwise differences.

4. Repeat (Step 3) for each of the remaining columns.
5. The last column contains the Hadamard transform, y, of the input vector, x.

Listing 1at the end of this article shows Matlab code that implements this algorithm. Despite its computational efficiency, it takes just ten lines of code due to Matlab's succinct way of describing matrix operations; an equivalent C routine would be somewhat longer. Table 2 shows an example calculation for an 8-point FHT. The first part of the table describes the computations for the 8-point FHT, and the second part carries out the computations for an example input vector x = [1 4 -2 3 0 1 4 -1], which appears in the first column. It's worth emphasizing that if you set the input vector x equal to the m^th row of H, then the output vector y is zero everywhere except for the m^th row -- simply a restatement of the orthogonality property.

Table 2 -- Example calculation for an 8-point FHT

Applications of the FHT

Because the rows in a Hadamard matrix are orthogonal, you can use the FHT to decompose any signal into its constituent Hadamard components. It functions just like an FFT, except the Hadamard components are based on sequency rather than frequency. Signal-compression applications, for example, commonly use an FFT as the compression agent. They perform an FFT and retain only select components. You can use the FHT in an identical fashion: retain only the key Hadamard components and throw away the rest. But because an FHT requires fewer computations (it omits the FFT's twiddle factors), you can implement the FHT on smaller, cheaper hardware. Ref 3 describes how scientists exploited it to compress lunar-landing images in the late 1960s.

One key difference between FHTs and FFTs is that the magnitude of an FFT is invariant to phase shifts in the signal. This fact isn't true of the FHT because a circular shift in one row of the Hadamard matrix doesn't leave it orthogonal to the other rows. In fact, the shifted row might be closer (in Hamming distance) to other rows than to the original. Thus data alignment is critically important to FHT applications. For this reason, the FHT is less useful than the FFT in most spectral-analysis applications.

On the other hand, its strictly binary nature helps the Hadamard transform find wide application in digital communications. The premier example is its central role in the CDMA cellular standard, IS-95 (Ref 4). That standard uses a 64 x 64 Hadamard matrix, H₆, in both base-to-mobile (forward channel) and mobile-to-base (reverse channel) transmissions. Interestingly, each direction exploits different properties of the Hadamard transform.

Fig 1 -- In IS-95 base-to-mobile transmissions, the transmitter assigns different codes from a 64 x 64 Hadamard matrix to each mobile user. For each outbound data bit, it transmits 64 Hadamard bits instead. Doing so spreads the signal and separates the different base-to-mobile transmissions.

The forward channel employs the Hadamard matrix for two purposes. First, each base station uses it to separate outbound transmissions targeted for different mobile users. Second, the base station employs it to spread the signal bandwidth of the transmission. It accomplishes both purposes elegantly as follows.

The base station communicates with as many as 64 mobile users in its cell by assigning to each user a unique row (code) from the 64 rows in the H6 matrix. Because of the codes' orthogonality, the unique assignment enables each mobile user to separate its incoming signal from other signals originating at that base station.

The base station also uses the Hadamard code to spread the outbound signal spectra. For every single information bit it wants to send to a user, it replaces the bit with the entire 64 bits of that user's code. Depending upon the bit's polarity, the base station either sends the code or the code's binary complement. (Inverting the bits doesn't affect the orthogonality properties of the code.) As shown in Fig 1, this scheme increases the outbound datarate from 19.2k bps to 1.2288M bps. The mobile radio receives this signal and, for every 64 bits, correlates the signal with its assigned Hadamard code. This feat collapses the 64 received bits down to either a +1 or -1 depending upon the original bit's polarity. It also reduces the datarate back down to 19.2k bps. The large expansion of the transmission bandwidth at the base station and contraction at the receiver is characteristic of spread-spectrum communications, for which IS-95 is well known.

Fig 2 -- Looking at the reverse situation from Fig 1, in IS-95 mobile-to-base transmissions, all mobile units use a 64 x 64 Hadamard matrix to encode the data six bits at a time (a). The six bits act as an index and determine which 64-bit row of the matrix to send. Then, at the base station, a 64-point FHT robustly determines which six data bits the mobile actually did send (b).

The reverse radio channel (from mobile to base station) uses the Hadamard matrix differently. For every six information bits it generates, the mobile radio instead transmits one 64-bit row of the Hadamard matrix (Fig 2a). It uses the six data bits in a lookup-table fashion to select one of the Hadamard matrix rows, and it substitutes the 64 bits of this row for the six data bits. This action both encodes and spreads the signal, as in the forward link, but by a smaller spreading factor, 64/6 = 10.75.

This encoding acts primarily as a robust error-correction scheme that a mobile radio can perform efficiently and cheaply. When the base station receives the encoded signal, it uses an inverse FHT to decode the data (Fig 2b). Because the data bits are unknown, the base station performs an FHT on every 64 received bits. Ideally, only one of the 64 resultant FHT coefficients is nonzero. The row number of that coefficient, represented in binary, yields the six data bits sent.

In reality, transmission problems cause the base station to receive some bits in error; in that case, it selects the strongest component of the FHT output. This scheme is highly tolerant of errors because the Hamming distance between each Hadamard code is 32, which means that as many as 15 bits can arrive in error (per block of 64) without corrupting the six information bits actually sent. However, because all mobile users share the 64 Hadamard codes, IS-95 must separate the different mobile signals at the base station by some other means. (It uses a spreading code unique to each mobile subscriber.) Of course, you can apply FHTs to various applications and exploit the many other mathematical properties of Hadamard matrices. Ref 1 provides great insight into these other areas, although it doesn't discuss IS-95. An important set of properties not discussed in this article is the relation between Hadamard matrices and wavelets (Refs 1 and 5). Wavelets prove useful in many signal-processing applications, and fast wavelet transforms (FWTs) exist that are even more efficient than the FHT.

References

1. Yarlagadda, RKR and Hershey, JE, Hadamard Matrix Analysis and Synthesis With Applications to Communications and Signal/Image Processing, Kluwer Academic Publishers (Boston, MA) 1997.
2. Sylvester, J, "Thoughts on Inverse Orthogonal Matrices, simultaneous Sign-successions, and Tessellated Pavements in two or more colours, with applications to Newton's Rule, Ornamental Tile-work, and the Theory of Numbers," Phil Mag, 1867, Series 4, No 34, pgs 461-475.
3. Pratt, WK, Kane, J and Andrews, HC, "Hadamard Transform Image Coding," Proc IEEE, January 1969, Vol 57, No 1, pgs 58-68.
4. Whipple, DP, "The CDMA Standard," Applied Microwave & Wireless, Winter/Spring 1994, Vol 6, No 2, pgs 24-37.
5. Strang, G, and Nguyen, T, Wavelets and Filter Banks, Wellesley-Cambridge Press, (Wellesley, MA), 1996, ISBN 0-9614088-7-1.

Charles (Chuck) Gumas serves as Principal Communications Engineer at the MITRE Corp's Information Systems and Technology Division (Reston, VA). He received an MSEE from Lehigh University and a BS in physics from the University of Pennsylvania. He maintains a web site at www.dc.net/spartan/chuck.html and can be contacted via email at cgumas@mitre.org.

This article originally appeared in Personal Engineering & Instrumentation News, November 1997, pgs 57-63. Reprinted with permission of PEC Inc; all rights reserved.

		Click here to get your listing up.