Walsh–Hadamard code

In coding theory, the Walsh–Hadamard code, named after the American mathematician Joseph Leonard Walsh and the French mathematician Jacques Hadamard, is an example of a linear code over a binary alphabet that maps messages of length n to codewords of length 2ⁿ. The Walsh–Hadamard code is unique in that each non-zero codeword has Hamming weight of exactly 2^{n − 1}, which implies that the distance of the code is also 2^{n − 1}. In standard coding theory notation, this means that the Walsh–Hadamard code is a [2ⁿ,n,2ⁿ / 2]₂-code. The Hadamard code can be seen as a slightly improved version of the Walsh–Hadamard code as it achieves the same block length and minimum distance with a message length of n + 1, that is, it can transmit one more bit of information per codeword, but this improvement comes at the expense of a slightly more complicated construction.

The Walsh–Hadamard code is a locally decodable code, which provides a way to recover parts of the original message with high probability, while only looking at a small fraction of the received word. This gives rise to applications in computational complexity theory and particularly in the design of probabilistically checkable proofs. It can also be shown that, using list decoding, the original message can be recovered as long as less than 1/2 of the bits in the received word have been corrupted.

In code division multiple access (CDMA) communication, the Walsh–Hadamard code is used to define individual communication channels. It is usual in the CDMA literature to refer to codewords as “codes”. Each user will use a different codeword, or “code”, to modulate their signal. Because Walsh–Hadamard codewords are mathematically orthogonal, a Walsh-encoded signal appears as random noise to a CDMA capable mobile terminal, unless that terminal uses the same codeword as the one used to encode the incoming signal.

Definition

The $n \times 2^n$ generator matrix G for the Walsh–Hadamard code of dimension n is given by

$G = \begin{pmatrix} \uparrow & \uparrow & & \uparrow\\ g_0 & g_1 & \dots & g_{2^n-1} \\ \downarrow & \downarrow & & \downarrow \end{pmatrix}\,.$

where $g_i \in \{0,1\}^n$ is the vector corresponding to the binary representation of i. In other words, $g_0,g_1,\dots,g_{2^n-1}$ is the list of all vectors of {0,1}ⁿ in some lexicographic order. For example, the generator matrix for the Walsh–Hadamard code of dimension 3 is

$G = \begin{pmatrix} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{pmatrix}.$

As is possible for any linear code generated by a generator matrix, we encode a message $x\in\{0,1\}^n$, viewed as a row vector, by computing its codeword $z\in\{0,1\}^{2^n}$ using the vector-matrix product in the vector space over the finite field $\mathbb F_2$:

$z=x\cdot G\,.$

This way, the matrix G defines a linear operator $\text{WH}:\{0,1\}^n\to\{0,1\}^{2^n}$ and we can write z = WH(x).

A more explicit, equivalent definition of WH uses the scalar product $x \odot y$ over $\mathbb F_2^n$:

For any two strings $x,y\in\{0,1\}^n$, we have $x \odot y = \sum_{i=1}^{n} x_i y_i\ \bmod\ 2.$

Then the Walsh–Hadamard code is the function $\text{WH} :\{0,1\}^n\to\{0,1\}^{2^n}$ that maps every string $x\in\{0,1\}^n$ into the string $z\in\{0,1\}^{2^n}$ satisfying $z_y=x \odot y$ for every $y\in\{0,1\}^n$ (where z_y denotes the yth coordinate of z, identifying {0,1}ⁿ with $\{1,\dots,2^n\}$ in some way).

Distance

The distance of a code is the minimum Hamming distance between any two distinct codewords, i.e., the minimum number of positions at which two distinct codewords differ. Since the Walsh–Hadamard code is a linear code, the distance is equal to the minimum Hamming weight among all of its non-zero codewords. All non-zero codewords of the Walsh–Hadamard code have a Hamming weight of exactly 2^{n − 1} by the following argument.

Let $G = \begin{pmatrix} \uparrow & \uparrow & & \uparrow\\ g_0 & g_1 & \dots & g_{2^n-1} \\ \downarrow & \downarrow & & \downarrow \end{pmatrix}$ be the $n \times 2^n$ generator matrix for a Walsh-Hadamard code of dimension n.

Let wt(x) represent the Hamming weight of vector x.

Let $x=(x_0,\dots,x_{n-1})$ be a non-zero message in {0,1}ⁿ.

We want to show that $wt(x\cdot G) = 2^{n-1}$ for all non-zero codewords. Remember that all arithmetic is done over $\mathbf{F}_2$, which is the finite field of size 2.

Let x_i be a non-zero bit of arbitrary message, x. Pair up the columns of G such that for each pair (g_j,g_k), g_j + g_k = e_i (where e_i is the zero vector with a 1 in the i^th position). By the way G is constructed, there will be exactly 2^{n − 1} pairs. Then note that $x\cdot g_j + x\cdot g_k = x\cdot(g_j + g_k) = x\cdot e_i = 1$. $x\cdot g_j + x\cdot g_k = 1$, implies that exactly one of $x\cdot g_j$, $x\cdot g_k$ must be 1. There are 2^{n − 1} pairs, so $x\cdot G$ will have exactly 2^{n − 1} bits that are a 1.

Therefore, the Hamming weight of every codeword in the code is exactly 2^{n − 1}.

Being a linear code, this means that the distance of the Walsh-Hadamard code is 2^{n − 1}.

Locally Decodable

A locally decodable code is a code that allows a single bit of the original message to be recovered with high probability by only looking at a small portion of the received word. A code is q-query locally decodable if a message bit, x_i, can be recovered by checking q bits of the received word. More formally, a code, $C: \{0,1\}^k \rightarrow \{0,1\}^n$, is $(q, \delta\geq 0, \epsilon\geq 0)$-locally decodable, if there exists a probabilistic decoder, $D:\{0,1\}^n \rightarrow \{0,1\}^k$, such that (Note: Δ(x,y) represents the Hamming distance between vectors x and y):

$\forall x \in \{0,1\}^k, \forall y \in \{0,1\}^n$, $\Delta(y, C(x)) \leq \delta n$ implies that $Pr[D(y)_i = x_i] \geq \frac{1}{2} + \epsilon, \forall i \in [k]$

Theorem 1: The Walsh–Hadamard code is $(2, \delta, \frac{1}{2}-2\delta)$-locally decodable for $0\leq \delta \leq \frac{1}{4}$.

Lemma 1: For all codewords, c in a Walsh–Hadamard code, C, c_i + c_j = c_{i + j}, where c_i,c_j represent the bits in c in positions i and j respectively, and c_{i + j} represents the bit at position (i + j).

Proof of Lemma 1

---

Let $C(x) = c = (c_0,\dots,c_{2^n-1})$ be the codeword in C corresponding to message x

Let $G = \begin{pmatrix} \uparrow & \uparrow & & \uparrow\\ g_0 & g_1 & \dots & g_{2^n-1} \\ \downarrow & \downarrow & & \downarrow \end{pmatrix}$ be the generator matrix of C

By definition, $c_i = x\cdot g_i$. From this, $c_i+c_j = x\cdot g_i + x\cdot g_j = x\cdot(g_i+g_j)$. By the construction of G, g_i + g_j = g_{i + j}. Therefore, by substitution, $c_i + c_j = x\cdot g_{i+j} = c_{i+j}$.

Proof of Theorem 1

---

To prove theorem 1 we will construct a decoding algorithm and prove its correctness.

Algorithm

Input: Received word $y = (y_0, \dots, y_{2^n-1})$

For each $i \in \{1, \dots, n\}$:

1. Pick $j \in \{0, \dots, 2^n-1\}$ independently at random
2. Pick $k \in \{0, \dots, 2^n-1\}$ such that j + k = e_i where j + k is the bitwise xor of j and k.
3. $x_i \gets y_j+y_k$

Output: Message $x = (x_1, \dots, x_n)$

Proof of correctness

For any message, x, and received word y such that y differs from c = C(x) on at most δ fraction of bits, x_i can be decoded with probability at least $\frac{1}{2}+(1-2\delta)$.

By lemma 1, $c_j+c_k = c_{j+k} = x\cdot g_{j+k} = x\cdot e_i = x_i$. Since j and k are picked uniformly, the probability that $y_j \not = c_j$ is at most δ. Similarly, the probability that $y_k \not = c_k$ is at most δ. By the union bound, the probability that either y_j or y_k do not match the corresponding bits in c is at most 2δ. If both y_j and y_k correspond to c, then lemma 1 will apply, and therefore, the proper value of x_i will be computed. Therefore the probability x_i is decoded properly is at least 1 − 2δ. Therefore, $\epsilon = \frac{1}{2} - 2\delta$ and for $\epsilon$ to be positive, $0 \leq \delta \leq \frac{1}{4}$.

Therefore, the Walsh–Hadamard code is $(2, \delta, \frac{1}{2}-2\delta)$ locally decodable for $0\leq \delta \leq \frac{1}{4}$

See also

• Locally decodable code
• Linear code
• List decoding
• Hamming code

References

• Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge, ISBN 978-0-521-42426-4, http://www.cs.princeton.edu/theory/complexity/ 
• Lecture notes of Atri Rudra: Hamming code and Hamming bound