Field Guide · algorithm

Also known as: Hadamard code, Walsh–Hadamard code, Walsh code, Walsh function

A Hadamard code takes the rows of a Hadamard matrix — a square ±1 matrix whose rows are mutually orthogonal — and uses them (mapped to 0/1) as its codewords.1 The payoff is a huge minimum distance of n/2 for length n, meaning any two codewords differ in half their bits, at the cost of a very low rate: only log₂ n message bits per n transmitted bits. In its signal-processing guise the same rows are the Walsh functions, and the orthogonal Walsh codes they define are what let many CDMA users share one channel without interfering.

HH H−H → each row = one orthogonal Walsh codeword any two rows agree in exactly half their bits → minimum distance n/2
Doubling a Hadamard matrix by the Sylvester rule yields a sign checkerboard whose orthogonal rows are the Walsh codewords underpinning CDMA and low-rate deep-space codes.

How it works

The simplest Hadamard matrices are built by Sylvester’s recursion: start from H₁ = [1] and repeatedly form [[H, H], [H, −H]], doubling the size each step to n = 2^m. Every pair of rows is orthogonal — their dot product is zero — which in 0/1 terms means they differ in exactly n/2 positions. Encoding maps a k-bit message (k = log₂ n) to the corresponding matrix row.

Decoding is where Hadamard codes shine. Rather than compare the received word to each codeword one at a time, the receiver runs a fast Walsh–Hadamard transform — the same butterfly structure as an FFT but with only additions and subtractions — which correlates against all n codewords simultaneously in O(n log n). The largest transform coefficient names the most likely codeword. This makes an otherwise brute-force nearest-codeword search cheap, and it is exactly the soft-decision decoder used for the biorthogonal codes in deep-space links.

Variants

  • Augmented / biorthogonal code: adding the complements of the Hadamard rows gives 2n codewords of length n, which is precisely the Reed–Muller code RM(1, m). This is the form flown on Mariner deep-space missions.
  • Walsh codes: in CDMA the rows are used not as an error-correcting code but as orthogonal spreading sequences — each user is assigned a distinct Walsh row so that, under perfect timing, their signals separate cleanly at the receiver. Walsh codes provide orthogonality but poor autocorrelation, so they are layered over a maximal-length or Gold scrambling code that supplies the spread-spectrum timing properties.

Relevance to SDR

Hadamard/Walsh sequences are everywhere in spread-spectrum radio: IS-95 and CDMA2000 use 64-ary Walsh codes to separate forward-link channels, WCDMA uses variable-length orthogonal (OVSF) Walsh codes for channelisation, and GPS-style systems mix Walsh-like orthogonality with pseudorandom codes. As error-correcting codes, the low-rate biorthogonal Hadamard codes belong to the deep-space and beacon world where coding gain outweighs bandwidth. GopherTrunk targets narrowband land-mobile trunking (P25, DMR, NXDN, TETRA), which does not use Walsh spreading, so GT does not implement a Hadamard decoder — but the fast Walsh–Hadamard transform is a general SDR tool, useful for sequence correlation and for understanding how CDMA packs many callers onto one frequency.

Sources

  1. Hadamard code — Wikipedia, for the Hadamard-matrix construction, minimum distance n/2, the fast Walsh–Hadamard decoder, the biorthogonal/Reed–Muller link, and the Walsh-code CDMA application. ↩

See also