On classes of rate k/(k+1) convolutional codes and their decoding techniques

For the class of rate k/(k+1) convolutional codes, Yamada et al. (1983) proposed an efficient maximum-likelihood decoding algorithm called the YHM algorithm. In order to reduce the complexity of the YHM algorithm, this paper presents two techniques for simplifying the trellis diagram used in the YHM algorithm. We further observe that the proposed techniques effectively reduce the complexity of the YHM algorithm for two classes Ξ and Ξ_f (which is a subclass of Ξ) of rate k/(k+1) convolutional codes. The construction of codes in these classes is also discussed. It is shown that Ξ codes with d _free=3,4 can be obtained by simple construction. A code search algorithm for Ξ codes with d_free⩾5 is also introduced. Computer searches are performed to construct good Ξ and Ξ_f codes. For specified decoding complexities, a number of these new codes give better error performance than previously reported codes