Problem 1: Describe the Hamming code with 2 by 2 parity check matrix. What is the generator matrix?
Problem 2: Is the 3 by 2 rectangular code a linear code? Why?
To build a rectangular code, you partition your message into blocks
of length m and then factor m into k1 x k2 and arrange the bits in a
k1 by k2 rectangular array as in the figure below (read "digit" as
"bit"). Then you add parity bits along the right side and bottom of
the rows and columns. The code word is read row by row.
x x x ⋯x o
x x x ⋯x o
…..
x x x ⋯x o
o o o ⋯o
x = message bit o = parity bit
For example, if m is 4, then our only choice is a 2 by 2 array. The
message 1101 would be encoded as so
1 1| 0
0 1| 1
1 0
And the code
word is the string 11001110.
Thank you!
EDIT
I gave the definition of rectangular code and an example for 2×2 rectangular code.. The 3×2 rectangular code should look this way:
a b k
c d l
e f m
n p
where k is the parity check for first 2 bits (a and b or row #1), l is the parity check for 3th and 4th bit (c and d or row #2), m – for 5th and 6th (e and f or row #3), n – for column #1 (a, c and e) and p – for the second column (b, d and f).
Best Answer
This question uses many names in a nonstandard way (at least as far as the coding theory literature is English is concerned), and this confuses the issues.
The codes in question are single-error-correcting codes but are not Hamming codes in general. By Hamming code, one usually means a $[2^m-1,2^m-1-m]$ linear code with minimum distance $3$. It is a single-error-correcting code, but not all single-error-correcting codes are Hamming codes. Some might be shortened Hamming codes (set some data bits to $0$ and don't transmit them at all) but even this is not strictly necessary.
So, what are these "rectangular" codes? They are punctured product codes, where by a product code $\mathcal C_1\times \mathcal C_2$ is meant a rectangular $k_2\times k_1$ array of data bits bordered by parity bits such that each row is a codeword in $\mathcal C_1$ and each column is a codeword in $\mathcal C_2$ where, of course, $\dim(\mathcal C_i) = k_i$. The minimum distance of $\mathcal C_1\times \mathcal C_2$ is the product of the minimum distances of $\mathcal C_1$ and $\mathcal C_1$. If $\mathcal C_1$ and $\mathcal C_2$ are $[k_i+1,k_i]$ single parity check codes, then the minimum distance of $\mathcal C_1\times \mathcal C_2$ is $4$. But, the codes used by the OP are punctured product codes since the lower right-hand corner of the array (the parity of the parity bits!) has been deleted, and the minimum distance reduces by $1$.
Codewords in a product code can be regarded as a single vector of length $n_1n_2$ (just concatenate the rows into a single codeword) and so $\mathcal C_1\times \mathcal C_2$ is a $[n_1n_2,k_1k_2, d_1d_2]$ linear code. The codes called Hamming codes by the OP's instructor are thus $[n_1n_2-1,k_1k_2, 3]$ single-error-correcting codes, but they are not Hamming codes. Note for example that with $k_1=k_2=2$, the construction gives a $[8,4,3]$ code (punctured from a $[9,4,4]$ single-error-correcting, double-error-detecting code), and this is not the same as the $[7,4,3]$ Hamming code that all of us know and love. Of course, error correction is easy with this code. If one row parity-check sum fails as does one column parity-check sum, the error is in the data bit in that row and column. If only a row sum fails or only a column sum fails, the parity bit in the failed sum was received incorrectly.
-------
Sheesh! OK, $$\begin{align}c_1&=u_1\\c_2&=u_2\\c_3&=u_1+u_2\\c_4&=u_3\\c_5&=u_4\\c_6&=u_3+u_4\\c_7&=u_1+u_3\\c_8&=u_2+u_4\end{align}$$ giving $$\left[\begin{matrix}c_1\\c_2\\c_3\\c_4\\c_5\\c_6\\c_7\\c_8\end{matrix}\right]=\left[\begin{matrix}1&0&0&0\\0&1&0&0\\1&1&0&0\\0&0&1&0\\0&0&0&1\\1&0&1&0\\0&1&0&1\end{matrix}\right]\left[\begin{matrix}u_1\\u_2\\u_2\\u_4\end{matrix}\right]$$ Can you figure out $\mathbf G$ now? It will not be of the form $[I\mid P]$.