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

<p>Sincerely Yours Alex</p>

<p>PS</p>

<p>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.</p>

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

CC BY-SA 3.0
2011-07-16T16:19:50.473Z
@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?
Jyrki Lahtonen
CC BY-SA 3.0
2011-09-12T22:45:07.090Z
To speed up decoding avoid the soft decision. Do the hard decision first and do the soft decision only if hard decision failed.
V15I0N
CC BY-SA 3.0
2011-09-13T14:37:50.870Z
@Alexander: What is the explicit BCM you are using that is the map from $\mathbb{F}_{2}$ to $\mathbb{C}$ you are using?
v s
CC BY-SA 3.0
2011-09-13T14:39:07.573Z
Too bad they don't have an information theory stack exchange!
v s
CC BY-SA 3.0
2011-11-12T09:37:07.737Z
Although an NP-hard problem in general ML decoding for information lengths of 10, is as mentioned already, only requiring you a mere set of 1024 candidate vectors to check, which is not bad at all. If you care about relaxations, there are some nice ones, such as the LP decoder that was introduced in

J. Feldman, M.J. Wainwright and D.R. Karger, "Using linear programming to Decode Binary linear codes," IEEE Transactions on Information Theory, 51:954–972, March 2005.
Dimitris
CC BY-SA 2.5
2010-11-28T10:17:31.647Z
For such a short code, you can do Maximum-Likelihood easily since there are only 1024 codewords to test.
Anthony Leverrier
CC BY-SA 2.5
2010-11-28T13:18:19.627Z
The Viterbi algorithm is the obvious one to try.
Peter Shor 
CC BY-SA 2.5
2010-11-28T14:41:31.847Z
Dear Anthony, it is exactly what I mentioned - brute force calculation of all distances - I want to reduce complexity of this.
Alexander Chervov
CC BY-SA 2.5
2010-11-28T14:44:17.523Z
Dear Peter, usually Viterbi is applied to convolutional codes, not block ones, I have heard something about Viterbi for block codes - but I am not expert here, is it really efficient (does it reduce complexity)? What are good references for it ?
Alexander Chervov
CC BY-SA 2.5
2010-11-28T15:48:45.907Z
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.
Peter Shor 
CC BY-SA 2.5
2010-11-28T15:57:37.880Z
I think the Viterbi algorithm will work well if there is a generating matrix (basis) where most of the codewords in this basis have $0$'s outside short spans; that is, all their $1$'s are in coordinates between $i$ and $j$, where $i$ is close to $j$.
Peter Shor 
CC BY-SA 2.5
2010-11-28T17:16:28.020Z
Dear Peter, I will send tomorrow the matrix - such codes are used in modern mobile standards UMTS, LTE for transmission of service information - like channel quality indicators, acknlodgement of data receive. (For main data - turbo codes are used).
Alexander Chervov
CC BY-SA 2.5
2010-11-28T17:18:22.170Z
The generating matrix is not defined uniquecly, is there algorithm to transform to form which is desired for You ?
Alexander Chervov
CC BY-SA 2.5
2010-11-28T17:20:58.373Z
How the complexity depends on the width of non-zero diagonal part ?
Alexander Chervov
<ds.algorithms><coding-theory>
Soft decoding of linear block (20,10) codes - what methods are used ?
Alexander Chervov
# Soft decoding of linear block (20,10) codes - what methods are used ?

(Asked by: username_0 on 2010-11-28)

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

**Tags:** ds.algorithms, coding-theory

> **Comments:**
> **username_5**: For such a short code, you can do Maximum-Likelihood easily since there are only 1024 codewords to test.  
> **username_6**: The Viterbi algorithm is the obvious one to try.  
> **username_0**: Dear Anthony, it is exactly what I mentioned - brute force calculation of all distances - I want to reduce complexity of this.  
> **username_0**: Dear Peter, usually Viterbi is applied to convolutional codes, not block ones, I have heard something about Viterbi for block codes - but I am not expert here, is it really efficient (does it reduce complexity)? What are good references for it ?  
> **username_6**: 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.  
> **username_6**: I think the Viterbi algorithm will work well if there is a generating matrix (basis) where most of the codewords in this basis have $0$'s outside short spans; that is, all their $1$'s are in coordinates between $i$ and $j$, where $i$ is close to $j$.  
> **username_0**: Dear Peter, I will send tomorrow the matrix - such codes are used in modern mobile standards UMTS, LTE for transmission of service information - like channel quality indicators, acknlodgement of data receive. (For main data - turbo codes are used).  
> **username_0**: The generating matrix is not defined uniquecly, is there algorithm to transform to form which is desired for You ?  
> **username_0**: How the complexity depends on the width of non-zero diagonal part ?  
> **username_1**: @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?  
> **username_2**: To speed up decoding avoid the soft decision. Do the hard decision first and do the soft decision only if hard decision failed.  
> **username_3**: @Alexander: What is the explicit BCM you are using that is the map from $\mathbb{F}_{2}$ to $\mathbb{C}$ you are using?  
> **username_3**: Too bad they don't have an information theory stack exchange!  
> **username_4**: Although an NP-hard problem in general ML decoding for information lengths of 10, is as mentioned already, only requiring you a mere set of 1024 candidate vectors to check, which is not bad at all. If you care about relaxations, there are some nice ones, such as the LP decoder that was introduced in  J. Feldman, M.J. Wainwright and D.R. Karger, "Using linear programming to Decode Binary linear codes," IEEE Transactions on Information Theory, 51:954–972, March 2005.  

---

## 0 answers

