This paper proposes a method to maximize the rate of reliable communication for polar codes operating on channels with memory. The channel is learned implicitly from data by optimizing a neural polar decoder (NPD). This approach enables simultaneous optimization of the code rate over the input distribution and the design of a practical coding scheme within the framework of polar codes. The proposed approach applies to scenarios where the channel model is unknown and treated as a black-box that produces output samples from input samples. We use NPDs to estimate the mutual information (MI) between the channel inputs and outputs, and optimize a parametric model of the input distribution. The methodology involves a two-phase process: a training phase and an inference phase. In the training phase, two steps are repeated iteratively. The first step optimizes the NPD to estimate the MI of the channel inputs and outputs. The second step improves the input distribution parameters by maximizing the MI estimate obtained with the NPD. In the inference phase, the optimized model is used to construct polar codes. This approach uses the Honda-Yamamoto (HY) scheme, which implements polar codes with optimized input distributions, together with list decoding. Experimental results on memoryless and finite state channels (FSCs) demonstrate the effectiveness of this approach, particularly in cases where the channel’s capacity-achieving input distribution is non-uniform. For these cases, significant improvements in MI and bit error rates (BERs) are shown over those achieved by uniform and independent and identically distributed (i.i.d.) input distributions, validating our method for block lengths up to 1024. This data-driven approach can be utilized in real-world communication systems, bridging theoretical capacity estimation and practical coding performance.

In this work, we explore the enhancement of polar codes for channels with memory, focusing on achieving low decoding complexity and optimizing input distributions for maximum transmission rates. Polar codes are known for their efficient decoding, exhibiting a complexity of O($N$log$N$) in memoryless channels, and complexity of O(| S |3N log$N$) in finite state channels (FSCs), where|$S$| is the state space size. A notable recent advancement is the integration of neural networks (NNs) to create an neural polar decoder (NPD), which is adept at learning from data without the knowledge of the channel model, effectively bypassing the cubic complexity growth associated with the channel state size. In this paper, we propose a framework to optimize the input distribution for polar codes, aiming to maximize the mutual information of effective bit channels. This framework has been tested on both memoryless and FSCs, including the additive white Gaussian noise (AWGN) channel and the Ising channel, yielding promising results. The key contribution of this paper is the demonstration of the feasibility of simultaneously selecting an optimal input distribution and creating a practical decoder for various channel types, even in the absence of a channel model. This approach paves the way for new advancements in data-driven communication theory, especially for channels with memory.

This paper presents a data-driven methodology for estimating capacity regions in multi-user communication scenarios, focusing on channels with discrete alphabets, both with and without feedback. Prior research has successfully utilized neural networks for estimating capacity regions in continuous domains. However, the shift to discrete alphabets introduces a significant challenge due to the lack of end-to-end differentiability of the joint model. To tackle this issue, we first formulate the optimization problem of the causally conditioned directed information rate as a decentralized Markov decision process (MDP). Building on this formulation, we introduce a tractable optimization procedure specifically designed to estimate rate pairs that lie on the boundary of the capacity region. In addressing the inherent complexity of the MDP state space, we employ a reinforcement learning (RL) algorithm to learn optimal policies. We demonstrate the performance of our methodology by applying it to various communication scenarios, including the two-way channel and the multiple access channel (MAC). The results showcase the adaptability and performance of the proposed RL-based framework in estimating capacity regions without explicit knowledge of the underlying channel model, whether there is feedback or not.

In this work, a novel data-driven methodology for designing neural polar decoders for channels with and without memory is proposed. The methodology is suitable for the case where the channel is given as a “black-box” and the designer has access to the channel for generating observations of its inputs and outputs, but does not have access to the explicit channel model. The proposed method leverages the structure of the successive cancellation (SC) decoder to devise a neural SC (NSC) decoder. The NSC decoder uses neural networks (NNs) to replace the core elements of the original SC decoder, the check-node, the bit-node and the soft-decision. Along with the NSC, we devise additional NN that embeds the channel outputs into the input space of the SC decoder. The proposed method is supported by theoretical guarantees that include the consistency of the NSC. Additionally, the computational complexity of the NSC decoder does not increase with the channel’s memory size and is given by$O(mdN\log N)$, where N is the block length, and d and m represent the dimensions of the input and the hidden units of the implemented NNs, respectively. This sets its main advantage over successive cancellation trellis (SCT) decoder for finite state channels (FSCs) that has complexity of$O(|{\mathcal {S}}|^{3} N\log N)$, where$|{\mathcal {S}}|$denotes the number of channel states. We demonstrate the performance of the proposed algorithms on memoryless channels and on channels with memory. The empirical results are compared with the analytic polar decoder, given by the SC and SCT decoders. We further show that our algorithms are applicable for the case where there SC and SCT decoders are not applicable.

In this paper, we investigate the capacity of finite-state channels (FSCs) in the presence of delayed feedback. We show that the capacity of a FSC with delayed feedback can be computed as that of a new FSC with instantaneous feedback and an extended state. Consequently, graph-based methods to obtain computable upper and lower bounds on the delayed feedback capacity of unifilar FSCs are proposed. Based on these methods, we establish that the capacity of the trapdoor channel with delayed feedback of two time instances is given by$\log _{2}\left ({\frac {3}{2}}\right )$. In addition, we derive an analytical upper bound on the delayed feedback capacity of the binary symmetric channel with a no consecutive ones input constraint. This bound also serves as a novel upper bound on its non-feedback capacity, which outperforms all previously known bounds. Lastly, we demonstrate that feedback does improve the capacity of the dicode erasure channel.

In this work, a novel data-driven methodology for designing polar codes is proposed. The methodology is suitable for the case where the channel is given as a "black-box" and the designer has access to the channel for generating observations of its inputs and outputs, but does not have access to the explicit channel model. The methodology consists of two components: (1) a neural estimation of the sufficient statistic of the channel outputs using recent advances in Kullback Leibler (KL) estimation, and (2) a neural successive cancellation (NSC) decoder using three neural networks that replace the core elements of the successive cancellation (SC) decoder. The parameters of the neural networks are determined during a training phase where the mutual information of the effective channels is estimated. We demonstrate the performance of the algorithm on memoryless channels and on finite state channels. Then, we compare the results with the optimal decoding given by the SC and SC trellis decoders, respectively.

In this paper, we introduce a data-driven methodology for estimating capacity regions of continuous channels in multi-user communication systems. Computing capacity regions is a long standing open problem, even in simple communication scenarios. Nevertheless, it is often possible to represent their capacity regions as the limit of an optimization problem (a multi-letter expression). In many cases, these multi-letter expressions can be expressed in terms of directed information (DI) rates. Accordingly, our approach utilizes neural networks to estimate capacity regions, leveraging the recent introduction of the directed information neural estimator (DINE). The main idea of our methodology involves training DINE-based models using samples of channel inputs and outputs, and using these models to estimate the DI rate terms that are intrinsic to the studied capacity region. To estimate the capacity region rates, we optimize the DI rates over the involved input distributions which are parameterized by a neural distribution transformer (NDT), and execute an alternating maximization procedure between the NDT models and DINE-based models until convergence is achieved. The methodology is suitable for the case where the channel is treated as a "black-box" and the designer can only gather observations of its inputs and outputs, lacking any knowledge of the explicit channel model. The performance of our proposed algorithm is shown via several well-known settings, including the Gaussian two-way channel and the two-user Gaussian multiple-access channel with and without feedback.

This paper proposes a novel methodology for the estimation of the rate distortion function (RDF) in both continuous and discrete reconstruction spaces. The approach is input-space agnostic and does not require prior knowledge of the source distribution, nor the distortion function, i.e., it treats them as "black box" models. Thus, our method is a general solution to the RDF estimation problem. The approach leverages neural estimation and optimization of information measures to optimize a generative model of the input distribution. In continuous spaces we learn a sample generating model and a PMF model is proposed for discrete spaces. Formal guarantees of the proposed method are explored and implementation details are discussed. We demonstrate the performance on both high dimensional and large alphabet synthetic data. This work has the potential to contribute to the fields of data compression and machine learning through the development of provably consistent and competitive compressors optimized for the fundamental limit of the RDF.

We show that the trapdoor channel’s capacity with delayed feedback of two time-instances is given by\begin{equation*}{\text{C}}_2^{{\text{fb}}} = {\log _2}(3/2).\end{equation*}This demonstrates that the feedback capacity degrades sharply even with a single time-instance delay of the channel outputs. The capacity result is established by showing that the delayed feedback capacity can be formulated as a capacity problem with instantaneous feedback and an extended state. Consequently, graph-based methods can be applied to obtain new computable upper and lower bounds on the capacity, which are shown to coincide for the trapdoor channel.

We consider the use of the well-known dual capacity bounding technique for deriving upper bounds on the capacity of indecomposable finite-state channels (FSCs) with finite input and output alphabets. In this technique, capacity upper bounds are obtained by choosing suitable test distributions on the sequence of channel outputs. We propose test distributions that arise from certain graphical structures called Q-graphs. As we show in this paper, the advantage of this choice of test distribution is that, for the important sub-classes of unifilar and input-driven FSCs, the resulting upper bounds can be formulated as a dynamic programming (DP) problem, which makes the bounds tractable. We illustrate this for several examples of FSCs, where we are able to solve the associated DP problems explicitly to obtain capacity upper bounds that either match or beat the best previously reported bounds. For instance, for the classical trapdoor channel, we improve the best known upper bound of 0.661 (due to Lutz (2014)) to 0.584, shrinking the gap to the best known lower bound of 0.572, all bounds being in units of bits per channel use.

The capacity of unifilar finite-state channels in the presence of feedback is investigated. We derive a new evaluation method to extract graph-based encoders with their achievable rates, and to compute upper bounds to examine their performance. The evaluation method is built upon a recent methodology to derive simple bounds on the capacity using auxiliary directed graphs. While it is not clear whether the upper bound is convex, we manage to formulate it as a convex optimization problem using transformation of the argument with proper constraints. The lower bound is formulated as a non-convex optimization problem, yet, any feasible point to the optimization problem induces a graph-based encoder. In all examples, the numerical results show near-tight upper and lower bounds that can be easily converted to analytic results. For the non-symmetric trapdoor channel and binary fading channels (BFCs), new capacity results are established by computing the corresponding bounds. For all other instances, including the Ising channel, the near-tightness of the achievable rates is shown via a comparison with corresponding upper bounds. Finally, we show that any graph-based encoder implies a simple coding scheme that is based on the posterior matching principle and achieves the lower bound.

In this paper, we study the capacity of unifilar finite-state channels. We derive upper bounds that are based on the dual capacity bounding technique using test distributions with memory on directed Q-graphs. The bounds hold for any choice of graph-based test distribution and result in a multi-letter expression. The computability of the upper bound is shown via a novel dynamic programming formulation that can be efficiently evaluated. We further show that the bounds can be simplified to simple single-letter expressions by solving the corresponding Bellman equation explicitly. In particular, for the Ising and Trapdoor channels, we provide simple analytic upper bounds which outperform all previous bounds from the literature.

This paper investigates graph-based encoders for the unifilar finite-state channel (FSC) with feedback. A recent paper introduced the Q-graph as a tool for the recursive quantization of channel outputs on a directed graph. The Q- graph approach yielded single-letter lower and upper bounds on the feedback capacity of unifilar FSCs, termed here Q-LB and Q-UB, respectively. The current paper provides two computable optimization problems for the Q-LB and the Q-UB. The first, for the Q-LB, aims to find the graph-based encoder with the highest achievable rate. Specifically, for a structured cooperation between the encoder and the decoder, that is given by a particular Q-graph, the optimization problem maximizes the Q-LB over all input distributions. The resultant graph-based encoder from the optimization problem has a corresponding posterior matching scheme that achieves the Q-LB. The second optimization problem provides a formulation of the Q-UB as a convex optimization problem. Numerical results of the Q-LB and the Q-UB are presented for the Ising channel and a simplified version of a fading channel. The numerical results are then translated into analytical expressions for graph-based encoders and their achievable rates.