1

I am learning Hadamard encoding/decoding and one thing I couldn't figure out was how to obtain the generator matrix of Hadamard code matrix of a given size? I do understand how to obtain the Hadamard code matrix of a given size. One of the tutorials I referred has given the generator Matrix of Hadamard code matrix of 16x8 (which is derived from the 8x8 Hadamard Matrix) without mentioning how it was obtained.

Thanks in advance for any answers on this.

Hasini Gunasinghe
  • 11
  • 2

1 Answers1

1

Section 2.3 of Macwilliams and Sloane's The Theory of Error Correcting Codes is devoted to the Hadamard codes.

The following is essentially taken from there, though I am omitting some (many) details, such as the Paley construction, which is interesting for things not over GF(2), and details on equivalent Hadamard matrices and what not).

First, the definition of a Hadamard matrix (H-matrix herein, since I don't want to keep typing that) of order $n$: A H-matrix of order $n$ is a $n \times n$ matrix, $H_n$, with entries in $\{+1,-1\}$ such that $H H^T = n I$ (i.e. the dot product of any two different rows is zero and the dot product of a row with itself is $n$). They exist only if $n$ is 1,2 or a multiple of 4.

You can show that $H_{2n} = \begin{bmatrix} H_n & H_n \\ H_n & -H_n \end{bmatrix}$. Noting $H_1 = [1]$ gives you all H-matrices you will likely care about (which is likely at the end, when $n$ is a power of $2$).

A H-matrix is normalized if its first row and column contains only +1's. All H-matrix discussed henceforth are normalized. (You can normalize by multiplying the -1 starting rows and columns by -1 to get another H-matrix).

A binary H-matrix is normalized H-matrix where where +1's are replaced with 0's and -1's are replaced by 1's (when this matrix is of order $n$, call it $A_n$). This keeps the orthogonality, and any two rows agree in $\frac{n}{2}$ places and disagree in $\frac{n}{2}$ places (this fact allows you to construct the codes given below).

You can get 3 (generally nonlinear) codes from this:

  • $(n-1,n,\frac{n}{2})$ simplex code (rows of $A_n$ with first column deleted). Call this code $\cal{A}_n$.
  • $(n-1,2n,\frac{n}{2}-1)$ code consisting of $\cal{A}_n$ and its complements.
  • $(n, 2n, \frac{1}{2}n)$ code consisting of the rows of $A_n$ with its complements.

Now, lets simplify the construction a bit for $n=2^r$. In this case, we get the usual Hadamard code that undergrads see, which is a nice linear code (usually presented as the dual of a Hamming code. The $[2^r-1,2^r-r-1,3]$ Hamming code is specified by the parity check matrix consisting of all nonzero binary vectors of length $r$ as its columns. (One can prove these constructions are equivalent due to the construction of the H-matrix). S

Batman
  • 19,390