An algorithm for calculating the exact bit error probability of a binary linear code over the binary symmetric channel

摘要

An efficient algorithm for calculating the i-th bit error probability of a binary linear code over the binary symmetric channel(BSC) are presented. It is proved that the exact i-th bit error probability of maximum likelihood (ML) decoding, bounded distance decoding, symbolwise maximum a posteriori probability(MAP) decoding and symbolwise MAP decoding with erasure can be obtained with time complexity O(n2{sup}(n-k)), where n, k denote length and dimension of the target code.