Improved bound on the error probability of fixed convolutional codes

Hung Nguyen Tung, Takeshi Hashimoto

Andrew J. Viterbi

Rolf Johannesson, Kamil Sh. Zigangirov

Lower bounds on the list minimum weight and list weight are obtained for ensembles of systematic and nonsystematic encoders. >From these bounds it follows that the necessary list size grows exponentially with the number of corrected errors. We obtain an expurgated upper bound on the probability of the correct path loss for the ensemble of time-invariant binary convolutional codes. The notion of an l-list weight enumerator is introduced and used to obtain an upper bound on the probability of the correct path loss for list decoding of a fixed convolutional code.

Ruslan Morozov, Peter Trifonov

A lower bound on the minimum distance of convolutional polar codes is provided. The bound is obtained from the minimum weight of the generalized cosets of the codes generated by the bottom rows of the polarizing matrix. Moreover, a construction of convolutional polar subcodes is proposed, which provides improved performance under successive cancellation list decoding. For sufficiently large list size, the decoding complexity of convolutional polar subcodes appears to be lower compared with Arikan polar subcodes with the same performance. The error probability of successive cancellation list decoding of convolutional polar subcodes is lower than that of Arikan polar subcodes with the same list size.

Andrew J. Ferris, Christoph Hirche, David Poulin

Arikan's Polar codes attracted much attention as the first efficiently decodable and capacity achieving codes. Furthermore, Polar codes exhibit an exponentially decreasing block error probability with an asymptotic error exponent upper bounded by 1/2. Since their discovery, many attempts have been made to improve the error exponent and the finite block-length performance, while keeping the bloc-structured kernel. Recently, two of us introduced a new family of efficiently decodable error-correction codes based on a recently discovered efficiently-contractible tensor network family in quantum many-body physics, called branching MERA. These codes, called branching MERA codes, include Polar codes and also extend them in a non-trivial way by substituting the bloc-structured kernel by a convolutional structure. Here, we perform an in-depth study of a particular example that can be thought of as a direct extension to Arikan's Polar code, which we therefore name Convolutional Polar codes. We prove that these codes polarize and exponentially suppress the channel's error probability, with an asymptotic error exponent log_2(3)/2 which is provably better than for Polar codes under successive cancellation decoding. We also perform finite block-size numerical simulations which display improved error-correcting capability with only a minor impact on decoding complexity.

Karin Engdahl, Michael Lentmaier, Kamil Sh. Zigangirov