1
$\begingroup$

What algorithms are advised for soft-decoding of linear block codes (20,10) ? What are advised references ?

Sincerely Yours Alex

PS

By soft-decoding - I mean that input - is set of 20 real numbers (r_1, ... r_20) and I want to find the codeword which is most close in the Eucledian metric to this vector. I can do brute force full search of all 2^10 codewords and find the nearest one - to get the answer. But I am interested in some speeding up the process. I've heard several methods, but advises are highly welcome.

PSPS My code is over F_2, e.g. 0,1, not the other Galois field

Improve this question
$\endgroup$
  • 1
    $\begingroup$ For such a short code, you can do Maximum-Likelihood easily since there are only 1024 codewords to test. $\endgroup$ – Anthony Leverrier Nov 28 '10 at 10:17
  • 1
    $\begingroup$ The Viterbi algorithm is the obvious one to try. $\endgroup$ – Peter Shor Nov 28 '10 at 13:18
  • $\begingroup$ Dear Anthony, it is exactly what I mentioned - brute force calculation of all distances - I want to reduce complexity of this. $\endgroup$ – Alexander Chervov Nov 28 '10 at 14:41
  • 3
    $\begingroup$ Alexander, I think whether there's something that's substantially better than brute force really depends on the structure of the code, and you haven't told us that. You could certainly try the Viterbi algorithm. $\endgroup$ – Peter Shor Nov 28 '10 at 15:48
  • 1
    $\begingroup$ @Alexander The complexity depends on the trellis (state) complexity. This depends on how many generators are 'active' at a 'time' (ideally we want the non-zero spans not to overlap). To optimize the complexity some permutation (=interleaving) may be needed, but that may be a difficult problem. It should be doable for a relatively short code like this, but is (IIRC) NP-complete in general. There may also be other short cuts to achieve ML-decoding. If there is still some interest in this, can you provide a link to the description of this code? $\endgroup$ – Jyrki Lahtonen Jul 16 '11 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.