Linear Code (9,5): Is my Parity Check correct?

Question

I have an exercise about designing parity checks for the Hamming (9,5) group code with minimum distance $3$. I use the following notation for the generator matrix: $$ G=\begin{bmatrix}I&P\end{bmatrix} $$ so that $I$ is the identity $5\times 5$ matrix and $P$ is a $5\times 4$ matrix doing the parity checks. Now to my analysis and solution:

---

If $u,v\in\mathbb B^5$ have $d(u,v)=1$ we must have $d(uP,vP)\geq 2$ in order to have $d(uG,vG)\geq 3$. Now $d(u,v)=1$ iff. $u=v+e_i$ so it follows that $d(uP,vP)=wt(e_i P)\geq 2$ which shows that each row of $P$ must have weight at least 2.

If $d(u,v)=2$ we must have $u=v+e_i+e_j,i\neq j$ and $d(uP,vP)=wt(e_i P-e_j P)\geq 1$. This means that $e_i P$ and $e_j P$ has to be different, so this only implies that $P$ must have all rows different.

---

If I am correct thus far, I have found one solution to be $$ P= \begin{bmatrix} 1&1&0&0\\ 0&1&1&0\\ 0&0&1&1\\ 1&0&1&0\\ 0&1&0&1 \end{bmatrix} $$

---

So does my analysis make sense and is my solution valid?

NOTE: Please beware that this area is very new to me so keep it close to the level of difficulty I presented here, and I would be very grateful for that!

Answer 1

The solution and the logic leading up to it are impeccable. When a binary linear $(n,k)$-code is described in terms of a parity check matrix $H=M_{n-k,n}(\Bbb{F}_2)$ a known design criterion is: the minimum distance is $\ge d$, if no set of $d-1$ columns is linearly dependent.

If the generator matrix of a binary linear code is $G=(I_k|P)$, then the parity check matrix is $H=(P^T|I_{n-k})$. So in your case $$ H_{\mathrm{String}}=\left(\begin{array}{l}100101000\\110010100\\011100010\\001010001\end{array}\right). $$ Your conditions amounted to requiring that no two columns of this matrix should be equal, and this is manifestly the case.

Your code is an example of a shortened Hamming code. The (binary) Hamming code of length 15 and rank 11 has a check matrix consisting of all the fifteen non-zero binary columns of four bits $$ H_{\mathrm{Hamming}}=\left(\begin{array}{l}101010101010101\\011001100110011\\ 000111100001111\\000000011111111\end{array}\right). $$ You see that you get your check matrix by removing columns $7,9,11,13,14$ and $15$ from the Hamming check matrix and reordering the columns. The latter operation never affects the minimum distance.

Answer 2

This is a bit inconvenient to place as a comment and also as an edit to the original question, so I take the liberty to answer my own question checking that I get the details of Jyrki Lahtonen's (JL) insightful answer correct:

If we apply the strategy presented by JL to the well known Hamming $(7,4)$ code we get $$ \newcommand{\red}{\color{red}} \newcommand{\blue}{\color{blue}} \newcommand{\gray}{\color{gray}} H_{(7,4)}=\left(\begin{array}{l}\red1\gray0\blue1\gray0\blue{101}\\\gray0\red1\blue1\gray0\blue{011}\\ \gray{00}\blue0\red1\blue{111}\end{array}\right) $$ Naturally the identity part of $H$ is placed at columns $1,2,4$. Generally they will be at $1,2,4,...,2^{s-1}$. Thus the parity checks can be found in other positions in each row, namely $3,5,6,7$. Generally they are found in $\{1,2,...,2^s-1\}\setminus\{1,2,4,...,2^{s-1}\}$. So if we were to construct the generator matrix $G$ corrsponding to this, it would be $$ G= \begin{pmatrix} \blue1&\blue1&\gray1&\blue0&\gray0&\gray0&\gray0\\ \blue1&\blue0&\gray0&\blue1&\gray1&\gray0&\gray0\\ \blue0&\blue1&\gray0&\blue1&\gray0&\gray1&\gray0\\ \blue1&\blue1&\gray0&\blue1&\gray0&\gray0&\gray1 \end{pmatrix} $$ where the parity checks has been placed at columns $1,2,4$. The remaining columns of $G$ form the identity $I_4$. The order matters, since they have to be placed correctly to match the transposed version of the parity checks in $H$ so that the bit designated for the first row in $G$ ends up being multiplied by the third column in $H$ etc.

---

So in a computer one can easily implement this general description and work with Hamming code $(1023,1013)$ where $H$ is constructed by putting the binary digits of $1,2,...,2^s-1$ in columns and $G$ is constructed by picking out positions that are not powers of $2$ in the $i$-th row of $H$ and placing them in the $2^{i-1}$ column of $G$. If we remove the power-of-$2$-columns from $G$ we are left with a $k\times k$ identity matrix.