1
$\begingroup$

I need to construct a random code which corrects T errors, has R check bits and has N maximum bits in the transmitting word.

I have researched the topic and found a few theorems about the bounds (The Varshamov-Gilbert bound, for instance). Neither of them suggests an algorithm of how to construct the code.

How do I build the random code with the specified parameters? I assume the algorithm should be probabilistic, but I'm not certain.

Improve this question
$\endgroup$
8
  • $\begingroup$ The Gilbert-Varshamov bound can be proved algorithmically, though the algorithm isn't efficient (it runs in exponential time). $\endgroup$
    – Yuval Filmus
    Commented Jun 3, 2019 at 9:22
  • $\begingroup$ Generally speaking, the problem of determining the optimal tradeoff between the parameters $T,R,N$ is very hard, so you shouldn't expect any simple algorithm that works in general. $\endgroup$
    – Yuval Filmus
    Commented Jun 3, 2019 at 12:36
  • $\begingroup$ Thank you. I've come across several proofs, where they use a probabilistic approach. But I still don't understand how to build the code from scratch. There are some methods, as they call them "Building codes from other codes", such as the parity check bit method or the puncturing method, which are based upon some already existing codes. The methods are discussed in the Algorithmic Introduction to Coding Theory lectures by M. Sudan. $\endgroup$
    – Evgeny Mamaev
    Commented Jun 3, 2019 at 13:57
  • $\begingroup$ Coding theory is a vast topic. Entire books have been written on it. This makes your question quite broad. $\endgroup$
    – Yuval Filmus
    Commented Jun 3, 2019 at 13:59
  • $\begingroup$ The task I'm trying to accomplish is to write an algorithm, which accepts three numbers, named T, R, N, and shows the generator matrix of the code as a result. Let it be an arbitrary code without any specific constraints on the input parameters. $\endgroup$
    – Evgeny Mamaev
    Commented Jun 3, 2019 at 14:09

2 Answers 2

Reset to default
1
$\begingroup$

Look at Reed–Solomon codes. They are MDS codes, and AFAIK, MDS codes are most efficient codes that operates on independent blocks of bits.

If you need to support only erasures, there is simple to describe algorithm - consider input words as values of some polynomial at points 0..n-1, and compute (using a Galois Field) values of the same polynomial at points n..n+m-1 - it will be possible to restore polynomial coefficients from any n survived values.

If you can read Russian, I wrote more about erasure-only codes at ReedSolomonFFT-ru.md.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for the article of the erasure-only codes, you should definitely translate it to English. I liked its conciseness in Russian. However, I have not accepted your answer, since I had not found the answer in the article on how to construct the code. $\endgroup$
    – Evgeny Mamaev
    Commented Jun 4, 2019 at 6:32
0
$\begingroup$

I wrote a piece of code which solves the problem. Refer to the readme.md. The code is documented, all the explanations are taken from MacWilliams and Sloane "The Theory of Error-Correcting Codes". https://github.com/Evgeniy-Mamaev/code-correcting-n-errors

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.