First-order approximation of the ordered binary-symmetric channel

Soft-decision decoding algorithms of binary linear block codes require reordering of the received symbols within each block in decreasing reliability. Efficient decoding algorithms based on reordering have been devised. This paper presents different results related to the ordering of a sequence of N received symbols with respect to their reliability measure, for BPSK transmission over the AWGN channel model. First, a tight approximation of Pe(i; N), the probability that the hard decision associated with the ith symbol of the ordered sequence is in error, is derived. Then, it is shown that despite the fact that the random variables representing the noise at positions n₁, n₂,...,n_j of the ordering are no longer independent, the events of having a hard decision decoding error at these positions remain almost independent. Pe(n₁,n₂ ,...,n_j; N), the probability that the hard decisions associated with the symbols at positions n₁, n₂,...n_j in the ordered sequence are in error, is thus well approximated from each of the Pe (n_i; N), for i∈[1,j]. Finally, based on the independence of these events, the fully connected 2^N-state BSC representing the channel after ordering is simplified by N independent time-shared 2-state BSCss. This new model allows one to easily and tightly approximate the capacity of the channel after ordering