it's time for practical coding theory. I am trying to write a simple program that will detected if a given binary code word is "correct" or not. If it is not correct, I want to detect/correct (since its binary i guess these two are pretty much the same :) ) the error, find out where it is. It will be of length $63$. Below is the algorithm I am trying to apply: given
H = \begin{bmatrix} 1 & \alpha & \alpha^2 & . & . & . &\alpha^{62} \\ 1 & \alpha^3 & \alpha^6 & \alpha^9 & . & . & .\\ 1 & \alpha^5 & \alpha^{10} & \alpha^{15} & . & . & . \end{bmatrix} where
1 = \begin{bmatrix} 1\\ 0\\ 0\\ 0\\ 0\\ 0\end{bmatrix} $\alpha$ = \begin{bmatrix} 0\\ 1\\ 0\\ 0\\ 0\\ 0\end{bmatrix} and so on. Next I will find some $\dot c \in F_2^{63}$ such that $H \dot c ^T = 0$. Now when given some codeword, say, $ \dot y $ with errors such that $\dot y = \dot c + e$ where $e$ is the error. I should find out how many errors (maximum 3) and where they/it are/is. In order to achieve that below are the steps I have taken, since
$H \dot y^T = H( \dot c + e ) = He^T =$ \begin{bmatrix}
1 \\ 0 \\ 0 \\ 1 \\ . \\.\\.
\end{bmatrix} $18$ x $1$ matrix = \begin{bmatrix}
z_1 \\ z_2 \\ z_3
\end{bmatrix} $z_i , i = 1,2,3$ is $6$ bits and it is some power of $\alpha$.\
To be specific,
$z_1 = \alpha^i + \alpha^j + \alpha^k$
$z_2 = \alpha^{3i} + \alpha^{3j} + \alpha^{3k}$
$z_3 = \alpha^{5i} + \alpha^{5j} + \alpha^{5k}$
$1.$ If $z_1 = z_2 = z_3 = 0$ then we have no errors
$2.$ If $z_1 ~= 0, z_2 = z_1^3, z_3 = z_1^5$ then we have one error in $z_1$
My questions:
Do i have to perform similar checks for the others too?
How can I check if two or three errors occur?
Is there any sample code with any of you gurus? Matlab or Mathematica would be super awesome. But ofcourse other languages can be suggested. Which is the best choice for me now? Mathematica or MATLAB? Thanks alot.
You are rediscovering the decoding algorithms for Bose-Chaudhuri-Hocquenghem (BCH) codes. For double- and triple- error-correcting codes, people have worked simpler algorithms that do not require matrix inversion as the Peterson algorithm that has been pointed out to you. See, for example, Polkinghorn, "Decoding of double and triple error correcting Bose-Chaudhuri codes, IEEE Transactions on Information Theory, October 1966, and van der Horst and Berger, "Complete decoding of triple-error-correcting binary BCH codes," IEEE Transactions on Information Theory, March 1976.