Fast Search Method for Large Polarization Kernels

Abstract

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 commentAccepted for publication in IEEE Transactions on Communications. The source code is available at https://github.com/gtrofimiuk/KernelBruteforcer. arXiv admin note: text overlap with arXiv:2101.10269

References in corpus (7)

• Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels
• Finite-Length Scaling of Polar Codes
• Computer classification of linear codes
• Permutation Code Equivalence is not Harder than Graph Isomorphism when Hulls are Trivial
• High Speed Hashing for Integers and Strings
• Polar Codes' Simplicity, Random Codes' Durability
• Asymmetric Construction of Low-Latency and Length-Flexible Polar Codes