Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2402.08864

DeepPolar: Inventing Nonlinear Large-Kernel Polar Codes via Deep Learning

S. Ashwin Hebbar, Sravan Kumar Ankireddy, Hyeji Kim, Sewoong Oh, Pramod Viswanath

Published Feb 14, 2024• 11 citations
arXivHTMLPDF

Abstract

Progress in designing channel codes has been driven by human ingenuity and, fittingly, has been sporadic. Polar codes, developed on the foundation of Arikan's polarization kernel, represent the latest breakthrough in coding theory and have emerged as the state-of-the-art error-correction code for short-to-medium block length regimes. In an effort to automate the invention of good channel codes, especially in this regime, we explore a novel, non-linear generalization of Polar codes, which we call DeepPolar codes. DeepPolar codes extend the conventional Polar coding framework by utilizing a larger kernel size and parameterizing these kernels and matched decoders through neural networks. Our results demonstrate that these data-driven codes effectively leverage the benefits of a larger kernel size, resulting in enhanced reliability when compared to both existing neural codes and conventional Polar codes.

DOI
10.48550/arxiv.2402.08864

Related papers

Deep code: representation and learning algorithms for neural networks & their applications to communication codes

Ashok Vardhan Makkuva

Codes are the backbone of modern information age.Codes, composed of encoder and decoder pairs, are the basic mathematical objects that enable reliable communication.Landmark codes include convolutional, Reed-Muller, turbo, LDPC, and polar: each is linear and represents a mathematical breakthrough.Their impact on humanity is huge; each of these codes has been used in global communication standards over the past six decades.On the other hand, designing codes is a challenging task, mostly driven by human ingenuity.Befittingly, historically, the progress in discovery of codes has been sporadic.In this thesis, we present a new paradigm to invent codes via harnessing tools from deep-learning.Our major result is the invention of KO codes, a computationally efficient family of deep-learning driven codes that outperform the state-of-the-art RM and polar codes, in the challenging short-to-medium block length regime.The key technical innovation behind KO codes is the design of a novel family of neural architectures inspired by the computation tree of the Kronecker Operation (KO) central to RM and polar codes.These architectures pave the way for discovery of a much richer class of hitherto unexplored non-linear codes.This design technique can be viewed as an instantiation of the classical neural augmentation principle.In the process, we also study a popular neural network model called Mixture-of-Experts (MoE) that realizes this principle.We provide the first set of consistent and efficient algorithms with global learning guarantees for learning the parameters in a MoE which has been an open problem for more than two decades.B.1 Comparison of SGD on our losses (L 4 , L log ) vs. ℓ 2 and the EM algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . .106 C.2 KO code achieves a significant gain over the Polar(64, 7) code in BLER when trained on AWGN channel.KO decoder also matches the optimal MAP decoder. . . . . . . . . . . . .108 xii C.6 KO(6, 1) code.Left: KO(6, 1) code achieves significant gain over RM(6, 1) code (with Dumer) when trained on AWGN channel.Right: Under the optimal MAP decoding, KO(6, 1) and RM(6, 1) codes achieve the same performance.Error rates for a random Gaussian codebook are also plotted as a baseline. . . . . . . . . . . . . . . . . . . . . . . . . . . .120 C.1 Plotkin trees for the Polar(64, 7) encoder and our neural KO encoder counterpart.Both codes have dimension k = 7 and blocklength n = 64. . . . . . . . . . . . . . . . . . . . . .121 C.3 The same KO(8,2) encoder and decoder as those used in Figure 4.4 achieve a significant gain (without any retraining or fine-tuning) when list decoding is used together with the KO decoder.The magnitude of the gain is comparable to the gain achieved by the same list decoding technique on the successive cancellation decoder of the RM(8,2) code.We used the list decoding from [1] but without the permutation technique. . . . . . . . . . . . . . . . . . . . . . . . . . . . .122 C.4 Plotkin trees for RM(8,2) and KO(8,2) encoders.Leaves are highlighted in green.Both codes have dimension k = 37 and blocklength n = 256. . . . . . . . . . . . . . . . . . . . . .123 C.5 Plotkin trees for the RM(8, 2) and KO(8, 2) decoders.Red arrows indicate the bit decoding order. . . . . . . .

•Jul 15, 2022•0 citations

Scaling Deep Learning-Based Decoding of Polar Codes via Partitioning

Sebastian Cammerer, Tobias Gruber, Jakob Hoydis +1 more

The training complexity of deep learning-based channel decoders scales exponentially with the codebook size and therefore with the number of information bits. Thus, neural network decoding (NND) is currently only feasible for very short block lengths. In this work, we show that the conventional iterative decoding algorithm for polar codes can be enhanced when sub-blocks of the decoder are replaced by neural network (NN) based components. Thus, we partition the encoding graph into smaller sub-blocks and train them individually, closely approaching maximum a posteriori (MAP) performance per sub-block. These blocks are then connected via the remaining conventional belief propagation decoding stage(s). The resulting decoding algorithm is non-iterative and inherently enables a highlevel of parallelization, while showing a competitive bit error rate (BER) performance. We examine the degradation through partitioning and compare the resulting decoder to state-of-the art polar decoders such as successive cancellation list and belief propagation decoding.

Globecom•Dec 1, 2017•208 citations

Polar List Decoding for Large Polarization Kernels

Bhaskar Gupta, Hanwen Yao, Arman Fazeli +1 more

Polar codes constructed with large polarization kernels were recently proven to be able to achieve optimal finite-length scaling properties. However, straightforward decoding for large kernel polar codes introduces a complexity coefficient that is exponential to the kernel sizes, which makes such codes generally believed to be impractical. In this paper, we present a new method that decodes large kernel polar codes with a complexity coefficient that is polynomial to the kernel sizes. This could facilitate the implementation of large kernel polar codes for practical use in the future.Successive cancellation decoding for large kernel polar codes requires calculation on the probabilities of its bit channels. Similar to conventional polar codes, those bit channels follow a recursive relation, which make this calculation boil down to computing the probabilities for bit channels of a single polarization kernel. This kernel-level computation can be shown equivalent to soft-output maximum-likelihood (ML) decoding on a single bit of a linear block code. In our proposed method, we first use linear operations to represent the considered linear block code as a polar code with dynamically frozen bits, and then use a modified polar list decoder to get an approximate value on the soft-output of the desired bit. This method is motivated by the observation that at short block lengths, polar list decoding with a large enough list size can well-approximate ML decoding. The proposed low-complexity method allows us to decode polar codes constructed with a 64 × 64 polarization kernel with scaling exponent µ ≈ 2.87 for the first time.

IEEE Globecom Workshops (GC Wkshps)•Dec 1, 2021•7 citations

Multi-kernel construction of polar codes

Frédéric Gabry, Valerio Bioglio, Ingmar Land +1 more

We propose a generalized construction for binary polar codes based on mixing multiple kernels of different sizes in order to construct polar codes of block lengths that are not only powers of integers. This results in a multi-kernel polar code with very good performance while the encoding complexity remains low and the decoding follows the same general structure as for the original Arikan polar codes. The construction provides numerous practical advantages as more code lengths can be achieved without puncturing or shortening. We observe numerically that the error-rate performance of our construction outperforms state-of-the-art constructions using puncturing methods.

IEEE International Conference on Communications workshops•May 1, 2017•82 citations

Convolutional Polar Codes

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.

arXiv:1704.00715•Apr 3, 2017•23 citations

Multi-Kernel Construction of Polar Codes

Frédéric Gabry, Valerio Bioglio, Ingmar Land +1 more

We propose a generalized construction for binary polar codes based on mixing multiple kernels of different sizes in order to construct polar codes of block lengths that are not only powers of integers. This results in a multi kernel polar code with very good performance while the encoding complexity remains low and the decoding follows the same general structure as for the original Arikan polar codes. The construction provides numerous practical advantages as more code lengths can be achieved without puncturing or shortening. We observe numerically that the error-rate performance of our construction outperforms stateof the-art constructions using puncturing methods.

arXiv:1612.06099•Dec 19, 2016•2 citations
Progress in designing channel codes has been driven by human ingenuity and, fittingly, has been sporadic. Polar codes, developed on the foundation of Arikan's polarization kernel, represent the latest breakthrough in coding theory and have emerged as the state-of-the-art error-correction code for short-to-medium block length regimes. In an effort to automate the invention of good channel codes, especially in this regime, we explore a novel, non-linear generalization of Polar codes, which we call DeepPolar codes. DeepPolar codes extend the conventional Polar coding framework by utilizing a larger kernel size and parameterizing these kernels and matched decoders through neural networks. Our results demonstrate that these data-driven codes effectively leverage the benefits of a larger kernel size, resulting in enhanced reliability when compared to both existing neural codes and conventional Polar codes.
Codes are the backbone of modern information age.Codes, composed of encoder and decoder pairs, are the basic mathematical objects that enable reliable communication.Landmark codes include convolutional, Reed-Muller, turbo, LDPC, and polar: each is linear and represents a mathematical breakthrough.Their impact on humanity is huge; each of these codes has been used in global communication standards over the past six decades.On the other hand, designing codes is a challenging task, mostly driven by human ingenuity.Befittingly, historically, the progress in discovery of codes has been sporadic.In this thesis, we present a new paradigm to invent codes via harnessing tools from deep-learning.Our major result is the invention of KO codes, a computationally efficient family of deep-learning driven codes that outperform the state-of-the-art RM and polar codes, in the challenging short-to-medium block length regime.The key technical innovation behind KO codes is the design of a novel family of neural architectures inspired by the computation tree of the Kronecker Operation (KO) central to RM and polar codes.These architectures pave the way for discovery of a much richer class of hitherto unexplored non-linear codes.This design technique can be viewed as an instantiation of the classical neural augmentation principle.In the process, we also study a popular neural network model called Mixture-of-Experts (MoE) that realizes this principle.We provide the first set of consistent and efficient algorithms with global learning guarantees for learning the parameters in a MoE which has been an open problem for more than two decades.B.1 Comparison of SGD on our losses (L 4 , L log ) vs. ℓ 2 and the EM algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . .106 C.2 KO code achieves a significant gain over the Polar(64, 7) code in BLER when trained on AWGN channel.KO decoder also matches the optimal MAP decoder. . . . . . . . . . . . .108 xii C.6 KO(6, 1) code.Left: KO(6, 1) code achieves significant gain over RM(6, 1) code (with Dumer) when trained on AWGN channel.Right: Under the optimal MAP decoding, KO(6, 1) and RM(6, 1) codes achieve the same performance.Error rates for a random Gaussian codebook are also plotted as a baseline. . . . . . . . . . . . . . . . . . . . . . . . . . . .120 C.1 Plotkin trees for the Polar(64, 7) encoder and our neural KO encoder counterpart.Both codes have dimension k = 7 and blocklength n = 64. . . . . . . . . . . . . . . . . . . . . .121 C.3 The same KO(8,2) encoder and decoder as those used in Figure 4.4 achieve a significant gain (without any retraining or fine-tuning) when list decoding is used together with the KO decoder.The magnitude of the gain is comparable to the gain achieved by the same list decoding technique on the successive cancellation decoder of the RM(8,2) code.We used the list decoding from [1] but without the permutation technique. . . . . . . . . . . . . . . . . . . . . . . . . . . . .122 C.4 Plotkin trees for RM(8,2) and KO(8,2) encoders.Leaves are highlighted in green.Both codes have dimension k = 37 and blocklength n = 256. . . . . . . . . . . . . . . . . . . . . .123 C.5 Plotkin trees for the RM(8, 2) and KO(8, 2) decoders.Red arrows indicate the bit decoding order. . . . . . . .
The training complexity of deep learning-based channel decoders scales exponentially with the codebook size and therefore with the number of information bits. Thus, neural network decoding (NND) is currently only feasible for very short block lengths. In this work, we show that the conventional iterative decoding algorithm for polar codes can be enhanced when sub-blocks of the decoder are replaced by neural network (NN) based components. Thus, we partition the encoding graph into smaller sub-blocks and train them individually, closely approaching maximum a posteriori (MAP) performance per sub-block. These blocks are then connected via the remaining conventional belief propagation decoding stage(s). The resulting decoding algorithm is non-iterative and inherently enables a highlevel of parallelization, while showing a competitive bit error rate (BER) performance. We examine the degradation through partitioning and compare the resulting decoder to state-of-the art polar decoders such as successive cancellation list and belief propagation decoding.
Polar codes constructed with large polarization kernels were recently proven to be able to achieve optimal finite-length scaling properties. However, straightforward decoding for large kernel polar codes introduces a complexity coefficient that is exponential to the kernel sizes, which makes such codes generally believed to be impractical. In this paper, we present a new method that decodes large kernel polar codes with a complexity coefficient that is polynomial to the kernel sizes. This could facilitate the implementation of large kernel polar codes for practical use in the future.Successive cancellation decoding for large kernel polar codes requires calculation on the probabilities of its bit channels. Similar to conventional polar codes, those bit channels follow a recursive relation, which make this calculation boil down to computing the probabilities for bit channels of a single polarization kernel. This kernel-level computation can be shown equivalent to soft-output maximum-likelihood (ML) decoding on a single bit of a linear block code. In our proposed method, we first use linear operations to represent the considered linear block code as a polar code with dynamically frozen bits, and then use a modified polar list decoder to get an approximate value on the soft-output of the desired bit. This method is motivated by the observation that at short block lengths, polar list decoding with a large enough list size can well-approximate ML decoding. The proposed low-complexity method allows us to decode polar codes constructed with a 64 × 64 polarization kernel with scaling exponent µ ≈ 2.87 for the first time.
We propose a generalized construction for binary polar codes based on mixing multiple kernels of different sizes in order to construct polar codes of block lengths that are not only powers of integers. This results in a multi-kernel polar code with very good performance while the encoding complexity remains low and the decoding follows the same general structure as for the original Arikan polar codes. The construction provides numerous practical advantages as more code lengths can be achieved without puncturing or shortening. We observe numerically that the error-rate performance of our construction outperforms state-of-the-art constructions using puncturing methods.
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.
We propose a generalized construction for binary polar codes based on mixing multiple kernels of different sizes in order to construct polar codes of block lengths that are not only powers of integers. This results in a multi kernel polar code with very good performance while the encoding complexity remains low and the decoding follows the same general structure as for the original Arikan polar codes. The construction provides numerous practical advantages as more code lengths can be achieved without puncturing or shortening. We observe numerically that the error-rate performance of our construction outperforms stateof the-art constructions using puncturing methods.