Soft-input soft-output decoding of linear block codes based on ordered statistics

In this paper, reduced-complexity soft-input soft-output decoding of linear block codes is considered. The near-optimum low complexity soft decision decoding algorithm based on ordered statistics of Fossorier and Lin (1995) is modified so that soft outputs are delivered by the decoder. This algorithm performs nearly as well as the max-log-MAP decoding algorithm since in most cases, only the soft outputs corresponding to the least reliable bits may differ. For good (N,K,d_H) block codes of length N⩽128, dimension K and minimum Hamming distance dH⩽4K, the corresponding decoding complexity is O((N-K)(K+1)n(d_H,K)) real operations with n(d _H,K)=Σ_i=0([d_H/4])(_i ^K). Consequently, this algorithm allows to achieve practically the same error performance as the max-log-MAP decoding algorithm in iterative or concatenated systems with block codes for which the associated trellis complexity is simply too large for implementation of trellis based decoding algorithms