We provide two results concerning the optimality of the stochastic-mutual information (SMI) decoder, which chooses the estimated message according to a posterior probability mass function, which is proportional to the...
详细信息
We provide two results concerning the optimality of the stochastic-mutual information (SMI) decoder, which chooses the estimated message according to a posterior probability mass function, which is proportional to the exponentiated empirical mutual information induced by the channel output sequence and the different codewords. First, we prove that the error exponents of the typical random codes under the optimal maximum likelihood (ML) decoder and the SMI decoder are equal. As a corollary to this result, we also show that the error exponents of the expurgated codes under the ML and the SMI decoders are equal. These results strengthen the well-known result due to Csiszar and Korner, according to which, the ML and the maximum-mutual information (MMI) decoders achieve equal random-coding error exponents, since the error exponents of the typical random code and the expurgated code are strictly higher than the random-coding error exponents, at least at low coding rates. The universal optimality of the SMI decoder, in the random-coding error exponent sense, is easily proven by commuting the expectation over the channel noise and the expectation over the ensemble. This commutation can no longer be carried out, when it comes to typical and expurgated exponents. Therefore, the proof of the universal optimality of the SMI decoder must be completely different and it turns out to be highly non-trivial.
Linear and cyclic codes are typically used to combat substitution errors. However, synchronization errors, associated with the deletion and insertion of symbols, can cause severe performance degradation unless the cod...
详细信息
Linear and cyclic codes are typically used to combat substitution errors. However, synchronization errors, associated with the deletion and insertion of symbols, can cause severe performance degradation unless the coding scheme possesses the capability to recover from such errors. It is shown that linear codes of rate greater than 1/2 cannot correct deletion or insertion errors but there are linear codes of rate 1/2 that can correct these errors. Although cyclic codes, except for repetition codes, cannot correct deletion or insertion errors, two approaches are investigated to yield codes, based on cyclic codes, that can correct these errors. In the first approach, it is shown that a binary or nonbinary cyclic code of rate at most 1/3 or 1/2, respectively, can be extended by one symbol to make it capable of correcting synchronization errors. In the second approach, a cyclic code of rate at most 1/2 is expurgated by appropriately deleting codewords such that the expurgated code is capable of correcting synchronization errors. It is shown that deleting codewords costs at most two information bits if the code is binary and one information symbol if the code is nonbinary.
暂无评论