International Symposium on Problems of Redundancy in Information and Control Systems (REDUNDANCY)

Bidirectional search application for polar codes with large kernels

Ilya Morzharetto, Peter Trifonov

Published Oct 25, 2021• 0 citations

Abstract

The paper introduces an algorithm for processing large polarization kernels. The proposed algorithm admits lower decoding complexity compared to other kernel processing algorithms, such as recursive trellis algorithm based processing, on certain kernels. The discussed kernel processor is based on bidirectional trellis decoding of linear codes, where the algorithm grows trees of trellis nodes originating from the first and the last layers of the trellis until these trees intersect.

DOI: 10.1109/redundancy52534.2021.9606463

Related papers

Fast Search Method for Large Polarization Kernels

Grigorii Trofimiuk

A novel search method for large polarization kernels is proposed. The algorithm produces a kernel with given partial distances by employing the depth-first search combined with the computation of coset leaders weight tables and sufficient conditions of code non-equivalence. Using the proposed method, we improved all existing lower bounds on the maximum error exponent for kernels of size from 17 to 29. We also obtained kernels which admit low complexity processing by the recently proposed recursive trellis algorithm. Numerical results demonstrate the advantage of polar codes with the obtained kernels compared with shortened polar codes and polar codes with small kernels.

arXiv:2310.08369IEEE Transactions on CommunicationsOct 16, 20233 citations

Recursive Trellis Processing of Large Polarization Kernels

Peter Trifonov

A reduced complexity algorithm is presented for computing the log-likelihood ratios arising in the successive cancellation decoder for polar codes with large kernels of arbitrary dimension. The proposed algorithm exploits recursive trellis representation of the codes generated by submatrices of the polarization kernel, and enables polar codes based on large kernels to provide better performance compared to the codes based on Arikan kernel with the same decoding complexity.

arXiv:2101.08081IEEE International Symposium on Information Theory (ISIT)Jul 12, 202112 citations

Recursive Processing Algorithm for Low Complexity Decoding of Polar Codes With Large Kernels

Peter Trifonov, Liudmila Karakchieva

A reduced complexity algorithm is presented for computing the log-likelihood ratios (LLRs) arising in the successive cancellation (SC) decoder for polar codes with large kernels of arbitrary dimension. The proposed algorithm exploits a recursive trellis representation of the codes generated by submatrices of the polarization kernel and enables polar codes based on large kernels to be decoded with lower complexity compared to the codes based on the Arıkan kernel with the same performance. Extensions to the case of non-binary kernels are presented.

IEEE Transactions on CommunicationsJun 13, 202315 citations

Design and Decoding of Polar Codes with Large Kernels: A Survey

Peter Trifonov

We present techniques for the construction of polar codes with large kernels and their decoding. A crucial problem in the implementation of the successive cancellation decoding algorithm and its derivatives is kernel processing, i.e., fast evaluation of the log-likelihood ratios for kernel input symbols. We discuss window and recursive trellis processing methods. We consider techniques for evaluation of the reliability of bit subchannels and for obtaining codes with improved distance properties.

Problems of Information TransmissionJan 1, 20238 citations

Trellis-based Decoding Techniques for Polar Codes with Large Kernels

Peter Trifonov

A recursive trellis-based algorithm is proposed for computing the probabilities arising in the successive cancellation (SC) decoding algorithm for polar codes with arbitrary linear kernels. This approach enables one to re-use intermediate values obtained at different phases. Arikan SC algorithm is shown to be a special case of this method.

IEEE Information Theory Workshop (ITW)Aug 1, 201911 citations

Recursive Trellis Decoding Techniques of Polar Codes

Peter Trifonov

Recursive trellis decoding of polar codes is considered. Polar codes are shown to have much lower recursive trellis decoding complexity compared to similar Reed-Muller codes. Furthermore, a low-latency decoding algorithm, which combines recursive trellis and successive cancellation decoding methods, is presented.

IEEE International Symposium on Information Theory (ISIT)Jun 1, 20205 citations