Question

Define a Hadamard code generated from a 4 x 4 matrix, then calculate the corresponding generator and parity-check matrices. 11.5 (T):

Answer 1

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 nn: A H-matrix of order nn is a n×nn×n matrix, HnHn, with entries in {+1,−1}{+1,−1} such that HHT=nIHHT=nI (i.e. the dot product of any two different rows is zero and the dot product of a row with itself is nn). They exist only if nn is 1,2 or a multiple of 4.

You can show that H2n=[HnHnHn−Hn]H2n=[HnHnHn−Hn]. Noting H1=[1]H1=[1] gives you all H-matrices you will likely care about (which is likely at the end, when nn is a power of 22).

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 nn, call it AnAn). This keeps the orthogonality, and any two rows agree in n2n2 places and disagree in n2n2 places (this fact allows you to construct the codes given below).

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

• (n−1,n,n2)(n−1,n,n2) simplex code (rows of AnAn with first column deleted). Call this code AnAn.
• (n−1,2n,n2−1)(n−1,2n,n2−1) code consisting of AnAn and its complements.
• (n,2n,12n)(n,2n,12n) code consisting of the rows of AnAn with its complements.

Now, lets simplify the construction a bit for n=2rn=2r. 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 [2r−1,2r−r−1,3][2r−1,2r−r−1,3] Hamming code is specified by the parity check matrix consisting of all nonzero binary vectors of length rr as its columns. (One can prove these constructions are equivalent due to the construction of the H-matrix).