I am dealing with error correction using a (10,6,3) shortened hamming code. I can do the linear algebra for decoding a (7,4) hamming code so i sort of understand what going on here. However now I am working on a (10,6,3) shortened hamming code and I have not been given the the parity check matrix. i need to implement the decoder in c++.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
The answer is too easy.
(1) let G be the generator matrix. Take the identity matrix out of G
(2) let P be the remaining n x (n-m) matrix. transpose P
(3) add n-m columns to the transpose of P and insert an identity matrix
The result from step 3 will be the H for G.
$\begingroup$
$\endgroup$
2
A $(10,6,3)$-code is gotten by shortening a $(15,11,3)$ Hamming code. You can find the parity check matrix of the latter for example here. Take the four top rows and the first 15 columns of that table. Basically any check matrix with the fifteen columns being all the non-zero combinations four bits will do as long as the users agree on it, but this one is most common.
Shortening by five bits simply means that five data bits are set to zero. Again you need to agree with the other users, which five were picked to be zero. My first guess would be that in the linked diagram you set the five last data bits $d_7=d_8=d_9=d_{10}=d_{11}=0$. The point of this is that as those bits are always zero there is no need to transmit them. The decoder of $(15,11,3)$-code will work just fine on $(10,6,3)$-code, because it, too, knows that those five bits were set to zero.
Extra(not necessary for your question, a pet peeve with that Wiki-article): When using an error-correcting code there is, at least in theory, no sharp division between parity and data bits. Any set of linearly independent columns will serve equally well. Of course, the users of the said code need to agree how the payload message is encoded, but there are several possible ways to do that.
answered Sep 1, 2013 at 5:18
-
$\begingroup$ Alright, so I have the generator matrix for both the standard (15,11,3) and the shortened (10,6,3) code. they are derived from the code generated from the polynomial: g(x)=x^4+x+1=23 in octal. the generator for this shortened code is determined by deleting particular rows and columns, not just the left hand columns and tops rows. the purpose of this is to improve the likelihood of error detection. Anyways; since i have the generator matrix is it possible to solve for the parity matrix? $\endgroup$– mattSep 1, 2013 at 10:55
-
$\begingroup$ Ok. So you are using the code in a shortened cyclic form. The passage from generator matrix to parity check matrix is discussed in this answer. That may not help you, if you don't have that identity matrix block available. You could edit that generator matrix to your question, and I (or somebody else) can take a look. Missus calling, something about peeling some potatoes... $\endgroup$ Sep 1, 2013 at 11:02