Near Optimal Decoding for Short Block Transmission

The great invention "Turbo Codes" can closely approach the Shannon limit. Recently, Dolinar, Divsalar and Pollara showed at ISIT'98, Boston, USA, that "the Turbo code family is uniformly nearly perfect for all block sizes above 1000 bits." (within 0.7dB of sphere packing bound) and within 1 dB for block sizes from 200 bits to 1000 bits. They also showed that for block sizes less than 50 bits, the Golay code and Quadratic Residue code can achieve 0.5 dB from Shannon Sphere Packing lower bound. Clearly how to approach the Limit for a block size between 100 bits to 1000 bits is still an open problem. This research aims to tackle this problem. It is worth mentioning that block size of 100-3000 bits are widely used in most speech communications systems such as cellular mobile systems and satellite mobile systems.

In 1996, we noted that the near optimal multiuser detection (well known as the M-algorithm decoder) might be able to be extended to decode convolutional codes. But how to control the side-effect of the M-algorithm is a very difficult problem. Based on Anderson et. al.'s work, we first established some theoretical understanding of the problem and then found a near optimal decoding algorithm to decode long convolutional codes. Currently, our efforts are focusing on the following aspects.

• Hierarchical Decoding Algorithm (HDA) for Near Optimal Decoding Long Convolutional Codes in a Short Packet Format (<500 bits).
• Bootstrap Iterative Viterbi Algorithm (BIVA) for a Medium Size Block Transmission.(300-3000 bits).
• HDA and BIVA for TCM.
• Near Optimal Robust Decoding Algorithms for MLD and MAP decoders.

• L.Wei, "Near Near Optimal Decoding for Long Convolutional Codes in Short Packet", Proceeding of IEEE International Symposium on Information Theory (ISIT'98), Boston, USA.
• L.Wei, "Near Shannon Limit Decoding for 1% Packet Error Rate", Proceeding of IEEE Globecom, 1998, Sydney, accepted.
• Y. Wei and L. Wei, "A Simple Method for Designing Fast Recovery Convolutional Codes for M-algorithm Using Large Deviation Technique", Proceeding of IEEE Globecom, 1998, Sydney.
• L. Wei, "Decoding Method and Apparatus", Patent filed.
• L. Wei, "Near Optimal Limited Search Decoding: part 2. Convolutional Codes", (submitted).

1. Here is a glimpse of the imperfectness of terminated long convolutional codes versus the Shannon sphere packing lower bound.
   
   block error rate of 1%.
   block error rate of 10^-4.
   1. (2,1,14) code: g[1]=56721, g[2]=61713, decoded by the Hierarchical Decoder with M=1024. 14 tail bits are used. The average complexity is less than that of the 500 and 400 states VA for a block error rate of 1% or 10^-4 respectively.
   2. (2,1,19) code: g[1]=5122642, g[2]=7315626, decoded by the Hierarchical Decoder with M=( 256,1024,4096). Three parity bits and 19 tail bits are used. The average complexity is less than that of the 350 and 170 states VA for a block error rate of 1% or 10^-4 respectively. Side-effects (false joint and 3 parity bits) increase Eb/No by 0.15-0.2 dB. This is why the (2,1,19) code has a worse performance than the (2,1,14) code. These side-effects will disappear for codes with longer memory lengths.
   3. (2,1,25) code: g[1]=665041116, g[2]=516260772, decoded by the Hierarchical Decoder with M=( 256,1024,4096,16384). Three parity bits and 25 tail bits are used. The average complexity is less than that of the 1043 and 195 states VA for a block error rate of 1% or 10^-4 respectively.
   4. (2,1,30) code: g[1]=66504111704, g[2]=51626077364, decoded by the Hierarchical Decoder with M=(256,1024,4096,16384,32768). No parity bits and 30 tail bits are used. The average complexity is less than that of the 1250-2130 and 80-180 states VA for a block error rate of 1% or 10^-4 respectively.
   5. (2,1,40) code: coming soon.
   
   More information about imperfectness of other codes can be found at JPL Imperfectness Web Page.
   
   
2. BIVA using the convolutional code (n,k,m)=(2,1,8) and the 256 state Viterbi Algorithm can match with the performances of Burrou et. al.'s turbo codes for block sizes from 500 to 2000 bits. We have achieved 1.25dB away from the Shannon Limit using a two dimensional BIVA decoder for a block size of 15,600 bits.
3. Both HDA and BIVA have been extended to TCM. A modest gain over the 256 state VA can be achieved at the cost of 4 iterations.
4. An optimal robust decoding algorithm has been formulated, but too complicated. Two simple, near optimal robust decoding algorithms have been found and their performances are within 0.5 dB of the optimal decoder.