2
$\begingroup$

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 2x2 rectangular code.. The 3x2 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).

$\endgroup$
6
  • $\begingroup$ How do you define code? I ask this because the second question is trivial if you're using the only definition I know which is: a code over a finite field $\Bbb F$ is a subset of $(\Bbb F)^n$, for some $n\in \Bbb N$. $\endgroup$
    – Git Gud
    Commented Apr 25, 2013 at 12:54
  • $\begingroup$ @Silvyia Consider the binary code $\left\{\begin{bmatrix}1 &1\\ 1 & 1\\ 0&0\end{bmatrix} \right\}$.Since $\begin{bmatrix}1 & 1\\ 1 & 1\\ 0&0\end{bmatrix}+\begin{bmatrix}1 &1\\ 1 & 1\\ 0&0\end{bmatrix}=0$ isn't in the code, it isn't linear. $\endgroup$
    – Git Gud
    Commented Apr 25, 2013 at 13:14
  • 1
    $\begingroup$ All the parity bits that you tag along the sides of the rectangle are clearly linear functions of the contents of the rectangle. Therefore the rectangular code is always linear as the image of a linear mapping from one vector space to another, no? $\endgroup$ Commented Apr 25, 2013 at 14:07
  • 1
    $\begingroup$ Is the first question asking to describe a Hamming code as a rectangular code? There are no Hamming codes with a 2x2 parity check matrix in the usual sense. $\endgroup$ Commented Apr 25, 2013 at 14:09
  • $\begingroup$ @ Jyrki Lahtonen Honestly, I have no idea about the first question. I don't think they meant rectangular code and this 2x2 parity check matrix confuses me. As for the second question - I thought so, but I wasn't sure if that was enough as a proof. Thanks $\endgroup$
    – Silviya
    Commented Apr 25, 2013 at 14:14

1 Answer 1

2
$\begingroup$

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]$.

$\endgroup$
7
  • $\begingroup$ Thanks, Dilip Sarwate. I am really having trouble finding the generator and parity check matrices. I have all the messages that are possible to be sent (64 of them) and I know how would they look like after the encoding and I think this information should be enough to find them (the matrices) but I don't know how. I am afraid matrices has never been one of my favorite parts of mathematics. Anyways I am not asking anyone do the "hard work" for me, but any tips would be appreciated... $\endgroup$
    – Silviya
    Commented Apr 26, 2013 at 13:27
  • $\begingroup$ Question: If I use a random message and its corresponding code-word, I can find a generator matrix using the matrix equation: MxG=C where M is the message (a1, a2, a3, a4, a5, a6), C is the corresponding codeword (a1, a2, a1+a2, a3, a4, a3+a4, a5, a6, a5+a6, a1+a3+a5, a2+a4+a6) and G is the matrix I am looking for. Would this be enough to call G a generator matrix? $\endgroup$
    – Silviya
    Commented Apr 26, 2013 at 13:30
  • 1
    $\begingroup$ @Silviya You are working too hard at it. For the $2\times 2$ case, with $\mathbf u=[u_1,u_2,u_3,u_4]$ and codeword $$\mathbf c=[c_1,c_2,\ldots,c_8]=\mathbf{uG}$$ you have that $$c_i=u_i,1\leq i\leq 4,~~c_5=u_1+u_2,c_6=u_3+u_4,c_7=u_1+u_3,c_8=u_2+u_4.$$ Can you figure out the entries in $\mathbf G$ from this? Hint: $\mathbf G$ is of the form $[\mathbf I\mid \mathbf P]$ where $\mathbf I$ is the $4\times 4$ identity matrix. $\endgroup$ Commented Apr 26, 2013 at 15:01
  • $\begingroup$ You rearranged the codeword? Doesn't it matter? The check bits in 2x2 case are supposed to be on 3rd, 6th, 7th and 8th positions... And another question: I understand that the [I**|**P] form of G is very convenient, but what I don't understand is where does P come from? $\endgroup$
    – Silviya
    Commented Apr 26, 2013 at 15:37
  • 1
    $\begingroup$ @Silviya See the end of my just-edited answer. $\endgroup$ Commented Apr 26, 2013 at 16:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .