Performance Comparison of Short-Length Error-Correcting Codes

Johannes Van Wonterghem and Joseph J. Boutros 
 
Ghent University, Belgium 
Texas A&M University at Qatar 
 

May 2018

1 Outline

1.1 Structure of this page

 
 
Researchers and Engineers from all fields are welcome.

2 ML over BEC

2.1 The Binary Erasure Channel (BEC)

We consider the ergodic binary erasure channel (BEC). The channel input is binary and its output is ternary. Only erasures occur on this channel, no errors.


PIC


2.2 Maximum-Likelihood Decoding over the BEC (part 1)

2.3 Maximum-Likelihood Decoding over the BEC (part 2)

Example: Extended-Shortened BCH code [n = 10,k = 5,d = 4]2.
The code has |C| = 2k = 32 codewords each of length n = 10 bits.

     (  1  0  0  0   0  1  1  1  0  0 )
     |                                |
     ||  0  1  0  0   0  0  1  1  1  0 ||
G =  |  0  0  1  0   0  1  1  1  1  1 |
     (  0  0  0  1   0  1  0  1  1  0 )
        0  0  0  0   1  1  0  0  1  1

     (                                )
        1  0  1  1  1  1  0   0  0  0
     |  1  1  1  0  0  0  1   0  0  0 |
     ||                                ||
H  = |  1  1  1  1  0  0  0  1   0  0 |
     (  0  1  1  1  1  0  0   0  1  0 )
        0  0  1  0  1  0  0   0  0  1

b = ( 1  0  0  1  1 ) then c = bG = ( 1  0  0  1  1  1  1  0  0  1 ).
Check Hct = ( 0  0  0  0  0 )t.

2.4 Maximum-Likelihood Decoding over the BEC (part 3)

2.5 Maximum-Likelihood Decoding over the BEC (part 4)

3 OSD over BI-AWGN

3.1 The Binary-Input Additive White Gaussian Noise (BI-AWGN) Channel

 

Maximum-Likelihood Decoding, known as Soft-Decision Decoding:

3.2 OSD Decoding over the BI-AWGN (part 1)

3.3 OSD Decoding over the BI-AWGN (part 2)

The OSD does not need to know the channel noise variance σ2.

3.4 OSD Decoding over the BI-AWGN: order 0

     (  1  2  3  4  5  6  7  8  9  10 )
     |                                |
     ||  1  0  0  0  0  1  1  1  0   0 ||
G  = |  0  1  0  0  0  0  1  1  1   0 |
     ||  0  0  1  0  0  1  1  1  1   1 ||
     (  0  0  0  1  0  1  0  1  1   0 )
        0  0  0  0  1  1  0  0  1   1

Codeword in F2:
c = ( 1  0  0  1  1  1  1  0  0  1 )

Bipolar codeword:
s = (  + 1   - 1   - 1   + 1   + 1   + 1   + 1   - 1   - 1   + 1 )

Received noisy word:
r = ( +1.91  -2.64   + 0.54  +1.13  +1.23  +1.54  +0.56   + 0.20  -0.17  +1.24 )

Confidence values and detected word via threshold detection:
α = ( 1.91  2.64  0.54  1.13  1.23  1.54  0.56  0.20  0.17  1.24 )
y = ( 1  0  1  1  1  1  1  1  0  1 )

3.5 OSD Decoding over the BI-AWGN: order 0

     (                                )
        1  2  3  4  5  6  7  8  9  10
     |  1  0  0  0  0  1  1  1  0   0 |
     ||  0  1  0  0  0  0  1  1  1   0 ||
G  = ||                                ||
     |  0  0  1  0  0  1  1  1  1   1 |
     (  0  0  0  1  0  1  0  1  1   0 )
        0  0  0  0  1  1  0  0  1   1

Codeword in F2:
c = ( 1  0  0  1  1  1  1  0  0  1 )

Bipolar codeword:
s = (  + 1   - 1   - 1   + 1   + 1   + 1   + 1   - 1   - 1   + 1 )

Received noisy word:
r = ( +1.91  -2.64   + 0.54  +1.13  +1.23  +1.54  +0.56   + 0.20  -0.17  +1.24 )

Confidence values and detected word via threshold detection:
α = ( 1.91  2.64  0.54  1.13  1.23  1.54  0.56  0.20  0.17  1.24 )
y = ( 1  0  1  1  1  1  1  1  0  1 )

Sorted confidence values:
π1(α) = ( 2.64  1.91  1.54  1.24  1.23  1.13  0.56  0.54  0.20  0.17 )

3.6 OSD Decoding over the BI-AWGN: order 0

     (  2  1  6  10  5  4  7  3  8  9 )
     |                                |
     |  0  1  1   0  0  0  1  0  1  0 |
G′ = ||  1  0  0   0  0  0  1  0  1  1 ||
     ||  0  0  1   1  0  0  1  1  1  1 ||
     (  0  0  1   0  0  1  0  0  1  1 )

        0  0  1   1  1  0  0  0  0  1

Codeword in F2:
c = ( 1  0  0  1  1  1  1  0  0  1 )

Bipolar codeword:
s = (  + 1   - 1   - 1   + 1   + 1   + 1   + 1   - 1   - 1   + 1 )

Received noisy word:
r = ( +1.91  -2.64   + 0.54  +1.13  +0.17  +1.54  +0.56   + 0.20  -1.23  +1.24 )

Sorted confidence values:
π1(α) = ( 2.64  1.91  1.54  1.24  1.23  1.13  0.56  0.54  0.20  0.17 )

Sorted threshold detection:
π1(y) = ( 0  1  1  1  1  1  1  1  1  0 )

3.7 OSD Decoding over the BI-AWGN: order 0

     (  2  1  6  10  5  4  7  3  8  9 )
     |                                |
     |  1  0  0   0  0  0  1  0  1  1 |
˜G  = ||  0  1  0   0  0  1  1  0  0  1 ||
     ||  0  0  1   0  0  1  0  0  1  1 ||
     (  0  0  0   1  0  1  1  1  0  0 )
        0  0  0   0  1  0  1  1  1  0

Codeword in F2:
c = ( 1  0  0  1  1  1  1  0  0  1 )

Bipolar codeword:
s = (  + 1   - 1   - 1   + 1   + 1   + 1   + 1   - 1   - 1   + 1 )

Received noisy word:
r = ( +1.91  -2.64   + 0.54  +1.13  +0.17  +1.54  +0.56   + 0.20  -1.23  +1.24 )

Sorted confidence values:
π1(α) = ( 2.64  1.91  1.54  1.24  1.23  1.13  0.56  0.54  0.20  0.17 )

Sorted threshold detection:
π1(y) = ( 0  1  1  1  1  1  1  1  1  0 )

3.8 OSD Decoding over the BI-AWGN: order 0

     (  2  1  6  10  5  4  7  3  8  9 )
     |                                |
     |  1  0  0   0  0  0  1  0  1  1 |
˜G  = ||  0  1  0   0  0  1  1  0  0  1 ||
     ||  0  0  1   0  0  1  0  0  1  1 ||
     (  0  0  0   1  0  1  1  1  0  0 )
        0  0  0   0  1  0  1  1  1  0

Codeword in F2:
c = ( 1  0  0  1  1  1  1  0  0  1 )

Bipolar codeword:
s = (  + 1   - 1   - 1   + 1   + 1   + 1   + 1   - 1   - 1   + 1 )

Sorted threshold detection:
π1(y) = ( 0  1  1  1  1  1  1  1  1  0 )

Re-encoding from MRB (the 5 bits on the left, i.e. the most confident):
π1(ĉ) = ( 0  1  1  1  1  1  1  0  0  0 )

Final codeword (order-0 OSD):
ĉ = ( 1  0  0  1  1  1  1  0  0  1 ) = c

3.9 OSD Decoding over the BI-AWGN: order 1

3.10 OSD Decoding over the BI-AWGN: order 2

3.11 OSD Decoding over the BI-AWGN: order

 
The OSD is asymptotically optimal if min{⌈d∕4 - 1,k} (Fossorier & Lin 1995). The OSD order is taken to be much smaller when improvement rules are applied, e.g. skipping rule based on weighted Hamming distance or the use of multiple MRB.

4 Codes

4.1 List of Codes for Short-Length Error Correction

4.2 Joint Decoding of Codes with CRC

I. Tal and A. Vardy (2011):
Cyclic redundancy check (CRC) code to improve list decoding of polar codes.
 

Our Approach:

5 Performance

5.1 Linear Binary Codes over the BEC, No CRC

PIC

 

Van Wonterghem, Alloum, Boutros, Moeneclaey, 2016

5.2 Linear Binary Codes over the BEC, 16-bit CRC

PIC

 

Van Wonterghem, Alloum, Boutros, Moeneclaey, 2016

5.3 Linear Binary Codes over the BI-AWGN, No CRC

PIC

 

Van Wonterghem, Alloum, Boutros, Moeneclaey, 2016

5.4 Linear Binary Codes over the BI-AWGN, 16-bit CRC

PIC

 

Van Wonterghem, Alloum, Boutros, Moeneclaey, 2016

6 Conclusions

6.1 BCH Minimum Distance versus Bounds

PIC
Result from J.J. Boutros, Techniques Modernes de Codage, ENST Paris, 1998

6.2 Normalized Rates of Codes over BI-AWGN, Pe = 10-4

PIC
    Result from Yury Polyanskiy, October 2016 (private communication)