Deepfake speech detection presents a growing challenge as generative audio technologies continue to advance. We propose a hybrid training framework that advances detection performance through novel augmentation strategies. First, we introduce a dual-stage masking approach that operates both at the spectrogram level (MaskedSpec) and within the latent feature space (MaskedFeature), providing complementary regularization that improves tolerance to localized distortions and enhances generalization learning. Second, we introduce compression-aware strategy during self-supervised to increase variability in low-resource scenarios while preserving the integrity of learned representations, thereby improving the suitability of pretrained features for deepfake detection. The framework integrates a learnable self-supervised feature extractor with a ResNet classification head in a unified training pipeline, enabling joint adaptation of acoustic representations and discriminative patterns. On the ASVspoof5 Challenge (Track~1), the system achieves state-of-the-art results with an Equal Error Rate (EER) of 4.08% under closed conditions, further reduced to 2.71% through fusion of models with diverse pretrained feature extractors. when trained on ASVspoof2019, our system obtaining leading performance on the ASVspoof2019 evaluation set (0.18% EER) and the ASVspoof2021 DF task (2.92% EER).

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 paper, we adapt and analyze Neural Polar Decoders (NPDs) for end-to-end communication systems. While prior work demonstrated the effectiveness of NPDs on synthetic channels, this study extends the NPD to real-world communication systems. The NPD was adapted to complete OFDM and single-carrier communication systems. To satisfy practical system requirements, the NPD is extended to support any code length via rate matching, higher-order modulations, and robustness across diverse channel conditions. The NPD operates directly on channels with memory, exploiting their structure to achieve higher data rates without requiring pilots and a cyclic prefix. Although NPD entails higher computational complexity than the standard 5G polar decoder, its neural network architecture enables an efficient representation of channel statistics, resulting in manageable complexity suitable for practical systems. Experimental results over 5G channels demonstrate that the NPD consistently outperforms the 5G polar decoder in terms of BER, BLER, and throughput. These improvements are particularly significant for low-rate and short-block configurations, which are prevalent in 5G control channels. Furthermore, NPDs applied to single-carrier systems offer performance comparable to OFDM with lower PAPR, enabling effective single-carrier transmission over 5G channels. These results position the NPD as a high-performance, pilotless, and robust decoding solution.

This study introduces an innovative deep-learning-based waveform design approach for single-carrier (SC) satellite communication systems. Neural network (NN) models are used for comprehensive optimization to mitigate the nonlinearities introduced by high-power amplifiers (HPAs). We propose two distinct NN architectures: a convolutional autoencoder (CAE) for end-to-end joint optimization and a mutual information neural estimation (MINE)-based architecture designed to optimize the transmitter and receiver components independently. Both models simultaneously enhance spectral purity by improving the adjacent channel power ratio (ACPR), reducing the peak-to-average power ratio (PAPR), and optimizing the bit error rate (BER). A key feature of our approach is its ability to generalize across diverse HPA models, enabling quick and effective adaptation to previously unseen amplifiers through minimal retraining. Additionally, our use of gradual loss learning allows for the effective balancing of multiple optimization objectives across various signal-to-noise ratio (SNR) scenarios. Rigorous evaluations using realistic satellite terminal block upconverter (BUC) HPA models, demonstrate the robustness and adaptability of the proposed NN solutions. A comparative analysis against conventional PAPR reduction and digital predistortion techniques confirms that our NN-based approaches deliver superior performance, addressing contemporary satellite communication demands, particularly in high-order QAM applications requiring stringent spectral constraints.

Large-language models (LLMs) are now able to produce text that is indistinguishable from human-generated content. This has fueled the development of watermarks that imprint a “signal” in LLM-generated text with minimal perturbation of an LLM's output. This paper provides an analysis of text watermarking in a one-shot setting. Through the lens of hypothesis testing with side information, we formulate and analyze the fundamental trade-off between watermark detection power and distortion in generated textual quality. We argue that a key component in watermark design is generating a coupling between the side information shared with the watermark detector and a random partition of the LLM vocabulary. Our analysis identifies the optimal coupling and randomization strategy under the worst-case LLM next-token distribution that satisfies a minentropy constraint. We provide a closed-form expression of the resulting detection rate under the proposed scheme and quantify the cost in a max-min sense. Finally, we numerically compare the proposed scheme with the theoretical optimum.

Large language model (LLM) watermarks enable authentication of text provenance, curb misuse of machine-generated text, and promote trust in AI systems. Current watermarks operate by changing the next-token predictions output by an LLM. The updated (i.e., watermarked) predictions depend on random side information produced, for example, by hashing previously generated tokens. LLM watermarking is particularly challenging in low-entropy generation tasks -- such as coding -- where next-token predictions are near-deterministic. In this paper, we propose an optimization framework for watermark design. Our goal is to understand how to most effectively use random side information in order to maximize the likelihood of watermark detection and minimize the distortion of generated text. Our analysis informs the design of two new watermarks: HeavyWater and SimplexWater. Both watermarks are tunable, gracefully trading-off between detection accuracy and text distortion. They can also be applied to any LLM and are agnostic to side information generation. We examine the performance of HeavyWater and SimplexWater through several benchmarks, demonstrating that they can achieve high watermark detection accuracy with minimal compromise of text generation quality, particularly in the low-entropy regime. Our theoretical analysis also reveals surprising new connections between LLM watermarking and coding theory.

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.

Despite the popularity of information measures in analysis of probabilistic systems, proper tools for their visualization are not common. This work develops a simple matrix representation of information transfer in sequential systems, termed information matrix (InfoMat). The simplicity of the InfoMat provides a new visual perspective on existing decomposition formulas of mutual information, and enables us to prove new relations between sequential information theoretic measures. We study various estimation schemes of the InfoMat, facilitating the visualization of information transfer in sequential datasets. By drawing a connection between visual pattern in the InfoMat and various dependence structures, we observe how information transfer evolves in the dataset. We then leverage this tool to visualize the effect of capacity-achieving coding schemes on the underlying exchange of information. We believe the InfoMat is applicable to any time-series task for a better understanding of the data at hand.

Max-sliced mutual information (mSMI) was recently proposed as a data-efficient measure of dependence. This measure extends popular correlation-based methods and proves useful in various machine learning tasks. In this paper, we extend the notion of mSMI to discrete variables and investigate its role in popular problems of information theory and statistics. We use mSMI to propose a soft version of the Gacs-Korner common information, which, due to the mSMI structure, naturally extends to continuous domains and multivariate settings. We then characterize the optimal growth rate in a horse race with constrained side information. Additionally, we examine the error of independence testing under communication constraints. Finally, we study mSMI in communications. We characterize the capacity of discrete memoryless channels with constrained encoders and decoders, and propose an mSMI-based scheme to decode information obtained through remote sensing. These connections motivate the use of max-slicing in information theory, and benefit from its merits.

This paper proposes a novel algorithm to verify entropic vectors with probability mass functions parametrized and generated by neural networks. Given a target vector, we minimize the normalized distance by training a neural network, which reveals the entropic nature of the target, with the underlying distribution obtained accordingly. Empirical results demonstrate improved normalized distances and convergence performances compared with prior works. We also conduct optimizations of Ingleton score and Ingleton violation index, where a new lower bound of Ingleton violation index is obtained. An inner bound of the almost entropic region with four random variables is constructed with the proposed method, presenting the current best inner bound measured by the volume ratio.

An enhanced framework for peak-to-average power ratio (PAPR) reduction and waveform design for Multiple-Input-Multiple-Output (MIMO) orthogonal frequency-division multiplexing (OFDM) systems, based on a convolutional-autoencoder (CAE) architecture, is presented. The end-to-end learning-based autoencoder (AE) for communication networks represents the network by an encoder and decoder, where in between, the learned latent representation goes through a physical communication channel. We introduce a joint learning scheme based on projected gradient descent iteration to optimize the spectral mask behavior and MIMO detection under the influence of a non-linear high power amplifier (HPA) and a multipath fading channel. The offered efficient implementation novel waveform design technique utilizes only a single PAPR reduction block for all antennas. It is throughput-lossless, as no side information is required at the decoder. Performance is analyzed by examining the bit error rate (BER), the PAPR, and the spectral response and compared with classical PAPR reduction MIMO detector methods on 5G simulated data. The suggested system exhibits competitive performance when considering all optimization criteria simultaneously. We apply gradual loss learning for multi-objective optimization and show empirically that a single trained model covers the tasks of PAPR reduction, spectrum design, and MIMO detection together over a wide range of SNR levels.

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.

We consider finite-state channels (FSCs) with feedback and state information known causally at the encoder. This setting is quite general and includes: a memoryless channel with i.i.d. state (the Shannon strategy), Markovian states that include look-ahead (LA) access to the state and energy harvesting. We characterize the feedback capacity of the general setting as the directed information between auxiliary random variables with memory to the channel outputs. We also propose two methods for computing the feedback capacity: (i) formulating an infinite-horizon average-reward dynamic program; and (ii) a single-letter lower bound based on auxiliary directed graphs called$Q$-graphs. We demonstrate our computation methods on three examples. In the first example, we introduce a channel with LA and establish a closed-form, analytic lower bound on its feedback capacity. Furthermore, we extend the channel with general parameters, and derive numerical lower bounds for each parameter. In the second example, we show that the mentioned methods achieve the feedback capacity of known unifilar FSCs such as the Ising channel. Finally, in the last example, we generalize the Ising channel such that the state is stochastically dependent on the input, and investigate its feedback capacity.

Directed information (DI) is a fundamental measure for the study and analysis of sequential stochastic models. In particular, when optimized over input distributions it characterizes the capacity of general communication channels. However, analytic computation of DI is typically intractable and existing optimization techniques over discrete input alphabets require knowledge of the channel model, which renders them inapplicable when only samples are available. To overcome these limitations, we propose a novel optimization framework for estimated DI over discrete spaces. We formulate DI optimization as a Markov decision process and leverage reinforcement learning techniques to optimize a deep generative model of the input process probability mass function (PMF). Combining this optimizer with the recently developed DI neural estimator, we obtain an alternating optimization algorithm which is applied to estimating the (feedforward and feedback) capacity of various discrete channels with memory. Furthermore, we demonstrate how to use the optimized PMF model to (i) obtain theoretical bounds on the feedback capacity of unifilar finite-state channels; and (ii) perform probabilistic shaping of constellations in the peak power-constrained additive white Gaussian noise 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.

This work develops a new method for estimating and optimizing the directed information rate between two jointly stationary and ergodic stochastic processes. Building upon recent advances in machine learning, we propose a recurrent neural network (RNN)-based estimator which is optimized via gradient ascent over the RNN parameters. The estimator does not require prior knowledge of the underlying joint/marginal distributions and can be easily optimized over continuous input processes realized by a deep generative model. We prove consistency of the proposed estimation and optimization methods and combine them to obtain end-to-end performance guarantees. Applications for channel capacity estimation of continuous channels with memory are explored, and empirical results demonstrating the scalability and accuracy of our method are provided. When the channel is memoryless, we investigate the mapping learned by the optimized input generator.

Density estimation plays an important role in modeling random variables (RVs) with continuous alphabets. This work provides an algorithm that estimates the probability density function (PDF) of stationary and ergodic random processes using recurrent neural networks (RNNs). The main idea is to decompose the target PDF into a known auxiliary PDF and a likelihood ratio between the target and auxiliary PDFs. The algorithm focuses on estimating the likelihood ratio using the Donsker Vardhan (DV) variational formula of Kullback Leibler (KL) divergence. Together, the maximizer of the DV formula and the auxiliary PDF are used to construct the estimator of the target PDF in the form of a Gibbs density. The obtained estimator converges to the target PDF in total variation (TV) and in distribution. Also, we show that proposed estimator minimizes the cross entropy (CE) between the target and auxiliary distribution, and that with a proper choice of the auxiliary distribution, it defines a tight upper bound on the entropy rate. We demonstrate this approach by estimating the density of a Gaussian hidden Markov model.

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.

Directed information (DI) is a fundamental measure for the study and analysis of sequential stochastic models. In particular, when optimized over the input distribution, it characterizes the capacity of general communication channels. However, existing optimization methods for discrete input alphabets assume full knowledge of the channel model, and are therefore not applicable when only samples are available. We derive a new method that overcomes this limitation and enables optimizing DI over unknown channels. To that end, we formulate the problem as a Markov decision process and leverage reinforcement learning techniques to optimize a deep generative model of the channel input probability mass function (PMF). Combining our optimizer with the DI neural estimator, we obtain an end-to-end estimation-optimization scheme which is applied for estimating the capacity of various discrete channels with memory. We provide empirical results that demonstrate the utility of the proposed framework and further show how to use the optimized PMF generator to obtain theoretical bounds on the feedback capacity for unifilar finite state channels.

We propose a new method to compute the feedback capacity of unifilar finite state channels (FSCs) with memory using reinforcement learning (RL). The feedback capacity was previously estimated using its formulation as a Markov decision process (MDP) with dynamic programming (DP) algorithms. However, their computational complexity grows exponentially with the channel alphabet size. Therefore, we use RL, and specifically, its ability to parameterize value functions and policies with neural networks, to evaluate numerically the feedback capacity of channels with a large alphabet size. The outcome of the RL algorithm is a numerical lower bound on the feedback capacity, which is used to reveal the structure of the optimal solution. The structure is modeled by a graph-based auxiliary random variable that is utilized to derive an analytic upper bound on the feedback capacity with the duality bound. The capacity computation is concluded by verifying the tightness of the upper bound by testing whether it is Bahl-Cocke-Jelinek-Raviv (BCJR) invariant. We demonstrate this method on the Ising channel with an arbitrary alphabet size. For an alphabet size smaller than or equal to 8, we derive the analytic solution of the capacity. Next, the structure of the numerical solution is used to deduce a simple coding scheme that achieves the feedback capacity and serves as a lower bound for larger alphabets. For an alphabet size greater than 8, we present an upper bound on the feedback capacity. For an asymptotically large alphabet size, we present an asymptotic optimal coding scheme.

We consider finite-state channels (FSCs) where the channel state is stochastically dependent on the previous channel output. We refer to these as Noisy Output is the STate (NOST) channels. We derive the feedback capacity of NOST channels in two scenarios: with and without causal state information (CSI) available at the encoder. If CSI is unavailable, the feedback capacity is$C_{\text {FB}}= \max _{P(x|y')} I(X;Y|Y')$, while if it is available at the encoder, the feedback capacity is$C_{\text {FB-CSI}}= \max _{P(u|y'),x(u,s')} I(U;Y|Y')$, where$U$is an auxiliary RV with finite cardinality. In both formulas, the output process is a Markov process with stationary distribution. The derived formulas generalize special known instances from the literature, such as where the state is i.i.d. and where it is a deterministic function of the output.$C_{\text {FB}}$and$C_{\text {FB-CSI}}$are also shown to be computable via convex optimization problem formulations. Finally, we present an example of an interesting NOST channel for which CSI available at the encoder does not increase the feedback capacity.

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.

In many information-theoretic channel coding problems, adding an input cost constraint to the operational setup amounts to restricting the optimization domain in the capacity formula. This paper shows that, in contrast to common belief, such a simple modification does not hold for the cost-constrained (CC) wiretap channel (WTC). The secrecy-capacity of the discrete memoryless (DM) WTC without cost constraints is described by a single auxiliary random variable. For the CC DM-WTC, however, we show that two auxiliaries are necessary to achieve capacity. Specifically, we first derive the secrecy-capacity formula, proving the direct part via superposition coding. Then, we provide an example of a CC DM-WTC whose secrecy-capacity cannot be achieved using a single auxiliary. This establishes the fundamental role of superposition coding over CC WTCs.

Calculating the capacity (with or without feedback) of channels with memory and continuous alphabets is a challenging task. It requires optimizing the directed information (DI) rate over all channel input distributions. The objective is a multi-letter expression, whose analytic solution is only known for a few specific cases. When no analytic solution is present or the channel model is unknown, there is no unified framework for calculating or even approximating capacity. This work proposes a novel capacity estimation algorithm that treats the channel as a `black-box', both when feedback is or is not present. The algorithm has two main ingredients: (i) a neural distribution transformer (NDT) model that shapes a noise variable into the channel input distribution, which we are able to sample, and (ii) the DI neural estimator (DINE) that estimates the communication rate of the current NDT model. These models are trained by an alternating maximization procedure to both estimate the channel capacity and obtain an NDT for the optimal input distribution. The method is demonstrated on the moving average additive Gaussian noise channel, where it is shown that both the capacity and feedback capacity are estimated without knowledge of the channel transition kernel. The proposed estimation framework opens the door to a myriad of capacity approximation results for continuous alphabet channels that were inaccessible until now.

We consider finite state channels (FSCs) with feedback and state known causally at the encoder. This setting is general and includes both a channel with a Markovian state in which the state is input-independent, but also many other cases where the state is input-dependent such as the energy harvesting model. We characterize the capacity as a multi-letter expression that includes auxiliary random variables with memory. We derive a single-letter computable lower bound based on auxiliary directed graphs that are used to provide an auxiliary structure for the channel outputs and are called Q-graphs. This method is implemented for binary energy-harvesting model with a unitsized battery and the noiseless channel, whose exact capacity has remained an open problem. We identify a structure of Q-graphs, with achievable rates that outperform the best achievable rates known in the literature.

In this paper, a neural network based Multiple-Input-Multiple-Output (MIMO) algorithm is presented. The algorithm is specifically designed to be integrated in a coded MIMO-OFDM system, and is based upon projected gradient descent iterations. We combine our model as a part of a modern coded MIMO-OFDM system, and we compare its performance with common MIMO detectors on simulated data, as well as on field data. We also investigated our model's performance in the presence of several common communication impairments, and demonstrated empirically its robustness. We show empirically that a single trained model is suited for the detection of both coded and uncoded data, with or without impairments, and in the presence of a wide range of tested SNR levels.

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.

We study the trade-off between secret message (SM) and secret key (SK) rates, simultaneously achievable over a state-dependent (SD) wiretap channel (WTC) with non-causal channel state information (CSI) at the encoder. This model subsumes other instances of CSI availability as special cases, and calls for efficient utilization of the state sequence for both reliability and security purposes. An inner bound on the semantic-security (SS) SM-SK capacity region is derived based on a superposition coding scheme inspired by a past work of the authors. The region is shown to attain capacity for a certain class of SD-WTCs. SS is established by virtue of two versions of the strong soft-covering lemma. The derived region yields an improvement upon the previously best known SM-SK trade-off result reported by Prabhakaran et al., and, to the best of our knowledge, upon all other existing lower bounds for either SM or SK for this setup, even if the semantic security requirement is relaxed to weak secrecy. It is demonstrated that our region can be strictly larger than those reported in the preceding works.

In this paper, we propose a novel method to compute the feedback capacity of channels with memory using reinforcement learning (RL). In RL, one seeks to maximize cumulative rewards collected in a sequential decision-making environment. This is done by collecting samples of the underlying environment and using them to learn the optimal decision rule. The main advantage of this approach is its computational efficiency, even in high dimensional problems. Hence, RL can be used to estimate numerically the feedback capacity of unifilar finite state channels (FSCs) with large alphabet size. The outcome of the RL algorithm sheds light on the properties of the optimal decision rule, which in our case, is the optimal input distribution of the channel. These insights can be converted into analytic, single-letter capacity expressions by solving corresponding lower and upper bounds. We demonstrate the efficiency of this method by analytically solving the feedback capacity of the well-known Ising channel with a ternary alphabet. We also provide a simple coding scheme that achieves the feedback capacity.

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.

The multiple access channel (MAC) with degraded message sets and feedback is considered. We show that feedback does not increase the capacity region of this setting, and present a capacity-achieving coding scheme. The coding scheme is inspired by the posterior matching principle for the memoryless channel, but for two transmitters. It is shown that the recursive design of the transmitters and decoder is also maintained in this multiuser setting, leading to a constructive and simple coding scheme. It is interesting to note that the weak transmitter performs its encoding with respect to the decoder's belief as expected, but the strong encoder performs its encoding with respect to the weak encoder's belief and not the decoder's belief. To the best of our knowledge, this is the first matching scheme for a multi-user setting with finite alphabets and feedback.

An analogy framework between wiretap channels (WTCs) and state-dependent point-to-point channels with non-causal encoder channel state information (referred to as Gelfand-Pinker channels (GPCs)) is proposed. A good sequence of stealth-wiretap codes is shown to induce a good sequence of codes for a corresponding GPC. Consequently, the framework enables exploiting existing results for GPCs to produce converse proofs for their wiretap analogs. The analogy readily extends to multiuser broadcasting scenarios, encompassing broadcast channels (BCs) with deterministic components, degradation ordering between users, and BCs with cooperative receivers. Given a wiretap BC (WTBC) with two receivers and one eavesdropper, an analogous Gelfand-Pinsker BC (GPBC) is constructed by converting the eavesdropper's observation sequence into a state sequence with an appropriate product distribution (induced by the stealth-wiretap code for the WTBC), and non-causally revealing the states to the encoder. The transition matrix of the state-dependent GPBC is extracted from WTBC's transition law, with the eavesdropper's output playing the role of the channel state. Past capacity results for the semi-deterministic (SD) GPBC and the physically-degraded (PD) GPBC with an informed receiver are leveraged to furnish analogy-based converse proofs for the analogous WTBC setups. This characterizes the secrecy-capacity regions of the SD-WTBC and the PD-WTBC, in which the stronger receiver also observes the eavesdropper's channel output. These derivations exemplify how the wiretap-GP analogy enables translating results on one problem into advances in the study of the other.

The state-dependent (SD) wiretap channel (WTC) with non-causal channel state information (CSI) available at the encoder is considered. An inner bound on the trade-off region between admissible secret key (SK) and secret message (SM) rates is provided. The result is derived under the stringent semantic-security metric. Our inner bound recovers the best-known achievability results for either SK generation, SM transmission, or simultaneous execution of both. Since some of these past benchmarks were derived under weaker security metrics, our results imply that an upgrade to semantic-security is possible without inflicting any rate loss. It is shown that for certain instances of the considered SD-WTC, the derived region is strictly larger than the previously best-known SK-SM trade-off region reported by Prabhakaran et al., and that a recently reported SK rate for this setup cannot be achieved.

A framework of analogy between wiretap channels (WTCs) and state-dependent point-to-point channels with noncausal encoder channel state information (referred to as Gelfand-Pinker channels (GPCs)) is proposed. A good (reliable and secure) sequence of wiretap codes is shown to induce a good (reliable) sequence of codes for a corresponding GPC. Consequently, the framework enables exploiting existing results for GPCs to produce converse proofs for their wiretap analogs. The fundamental limits of communication of two analogous wiretap and GP models are characterized by the same rate bounds; the optimization domains may differ. The analogy readily extends to multiuser broadcasting scenarios, encompassing broadcast channels (BCs) with deterministic components, degradation ordering between users, and BCs with cooperative receivers. The analogy is exploited to characterize the secrecy-capacity regions of the semideterministic WTBC (an open problem until this work) and a class of physically degraded WTBC. The derivations are based on known solutions for the corresponding GPBCs.

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.

We present algorithms for initializing a convolutional network coding (CNC) scheme in networks that may contain cycles. An initialization process for finding global encoding kernels (GEK) is needed if the network is unknown or if local encoding kernels are chosen randomly. During the initialization process every source node transmits basis vectors and every sink node gets the impulse response of the network. The impulse response is then used to find the GEK, which are needed for a decoding algorithm and to find the set of all achievable rates. We present two initialization algorithms that find the GEK and one algorithm that finds achievable rates from the GEK. In the first initialization algorithm it is assumed that we can perform a reset operation on the network at some fixed times, while the second algorithm does not operate under this assumption. Unlike acyclic networks, for which it is sufficient to transmit basis vectors one after another, the initialization of cyclic networks is more involved, as test symbols from different times interfere with each other and the impulse response is of infinite duration. Our algorithms use only a finite number of the initial values of the impulse response to find the full GEK. This is possible because a CNC scheme can be described by a state space representation and, using the Cayley-Hamilton theorem, it is possible to find its full impulse response from its initial values.

In this paper, a general binary-input binary-output channel is investigated in the presence of feedback and input constraints. The feedback capacity and the optimal input distribution of this setting are calculated for the case of an $(1,\infty )$ -RLL input constraint, that is, the input sequence contains no consecutive ones. These results are obtained via explicit solution of an equivalent dynamic programming optimization problem. A simple coding scheme is designed based on the principle of posterior matching, which was introduced by Shayevitz and Feder for memoryless channels. The posterior matching scheme for our input-constrained setting is shown to achieve capacity using two new ideas: history bits, which captures the memory embedded in our setting, and message-interval splitting, which eases the analysis of the scheme. Additionally, in the special case of an S-channel, we give a very simple zero-error coding scheme that is shown to achieve capacity. For the input-constrained binary symmetric channel, we show using our capacity formula that feedback increases capacity when the cross-over probability is small.

Motivated by the recent emergence of energy harvesting and wirelessly powered transceivers, we study communication over a memoryless channel with a transmitter, whose battery is recharged at random or deterministic times known to the receiver. We characterize the capacity of this channel as the limit of an n-letter maximum mutual information rate under various assumptions: causal and noncausal transmitter knowledge of the battery recharges, with or without feedback from the receiver to the transmitter. While the resultant n-letter capacity expressions are not computable in the general case, we demonstrate their usefulness by focusing on two important special cases, namely, the binary erasure channel (BEC) and the additive white Gaussian noise (AWGN) channel, where they lead to some interesting, and somewhat surprising, insights. By focusing on the BEC, we show that output feedback can strictly increase the capacity of this channel, even though the channel is memoryless and the battery recharging process is independent over time. Interestingly, this provides a counter example to an old claim by Shannon stated without proof in his 1956 paper. On the other hand, by focusing on the AWGN channel, we are able to show that the capacity with noncausal knowledge of the battery recharging times at the transmitter is strictly larger than that with causal knowledge, even though the battery recharging process is independent over time and known to the receiver. The n-letter expressions can also be used to derive explicit upper and lower bounds on capacity. In particular, we derive simple upper and lower bounds on the capacity of the AWGN channel with random battery recharges, which are within 1.05 b/s/Hz of each other for all parameter values.

The capacity of two semi-deterministic channels with the presence of non-causal channel state information (CSI) is characterized. The first channel is a state-dependent semi-deterministic relay channel. The CSI is available only at the transmitter and receiver, but not at the relay. The second channel is a state-dependent multiple access channel (MAC) with partial cribbing and CSI only at one transmitter and the receiver. In the semi-deterministic relay channel without states, the capacity can be achieved using partial-decode-forward scheme. The transmission is split to blocks; in each block, the relay decodes a part of the message and cooperation is established using those bits. When the channel depends on a state, the decoding procedure at the relay reduces the transmission rate. Recently, a cooperative bin forward scheme has been proposed which establishes cooperation without requiring the relay to decode a part of the message. In this scheme, the relay maps its received sequence, which is a deterministic function of the transmitted sequence, into bins. The transmitter coordinates its transmission with the bin index that is chosen by the relay. This scheme achieves the capacity when the CSI is available causally. In this work, we present a variation of the cooperative-bin-forward scheme that achieves capacity for non-causal CSI. The bin index corresponding to the deterministic output of the relay is selected by the transmitter in such a way that the relay's transmission is coordinated with the states. This coding scheme also applies for the MAC with partial cribbing and non-causal CSI at one transmitter and receiver. The capacity is achieved by the new variation of cooperative bin-forward. On top of that, we show an example in which the capacity with non-causal CSI is strictly greater than with causal CSI.

We study the state-dependent (SD) wiretap channel (WTC) with non-causal channel state information (CSI) at the encoder. This model subsumes all other instances of CSI availability as special cases, and calls for an efficient utilization of the state sequence both for reliability and security purposes. A lower bound on the secrecy-capacity, that improves upon the previously best known result by Chen and Han Vinck, is derived based on a novel superposition coding scheme. The improvement over the Chen and Han Vinck result is strict for some SD-WTCs. Specializing the lower bound to the case where CSI is also available to the decoder reveals that it is at least as good as the achievable formula by Chia and El-Gamal, which is already known to outperform the adaptation of the Chen and Han Vinck code to the encoder and decoder CSI scenario. The results are derived under the strict semantic-security metric that requires negligible information leakage for all message distributions. The proof of achievability relies on a stronger version of the soft-covering lemma for superposition codes.

The input-constrained binary erasure channel (BEC) with strictly causal feedback is studied. The channel input sequence must satisfy the (0, k)-runlength limited (RLL) constraint, i.e., no more than k consecutive `0's are allowed. The feedback capacity of this channel is derived for all k ≥ 1, and is given by C(0,k)fb(ε) = max ε̅H2(δ0)+Σi=1k-1(εi+1H2(δi) Πm=0i-1δm)/1+Σi=0k-1(ε̅i+1Πm=0iδm) where ε is the erasure probability, ε̅ = 1 - ε and H2(·) is the binary entropy function. The maximization is only over δk-1, while the parameters δifor i ≤ k - 2 are straightforward functions of δk-1. The lower bound is obtained by constructing a simple coding for all k ≥ 1. It is shown that the feedback capacity can be achieved using zero-error, variable length coding. For the converse, an upper bound on the non-causal setting, where the erasure is available to the encoder just prior to the transmission, is derived. This upper bound coincides with the lower bound and concludes the search for both the feedback capacity and the non-causal capacity. As a result, non-causal knowledge of the erasures at the encoder does not increase the feedback capacity for the (0, k)-RLL input-constrained BEC. This property does not hold in general: the (2, ∞)-RLL input-constrained BEC, where every `1' is followed by at least two `0's, is used to show that the feedback capacity can be strictly smaller than the non-causal capacity.

A binary-input binary-output (BIBO) channel is investigated in the presence of feedback and input constraints. The feedback capacity and the optimal input distribution of this setting are presented for the case where the input sequence contains no consecutive ones. A simple coding scheme is designed based on the principle of posterior matching, which was introduced by Shayevitz and Feder for memoryless channels. The posterior matching scheme for our input-constrained setting is shown to achieve capacity using two new ideas: which captures the memory embedded in the setting, and splitting, which simplifies the scheme analysis. Additionally, in the special case of an S-channel, we give a very simple zero-error coding scheme that achieves capacity.

The broadcast channel (BC) with one common and two private messages with leakage constraints is studied, where leakage rate refers to the normalized mutual information between a message and a channel symbol string. Each private message is destined for a different user and the leakage rate to the other receiver must satisfy a constraint. This model captures several scenarios concerning secrecy, i.e., when both, either or neither of the private messages are secret. Inner and outer bounds on the leakage-capacity region are derived when the eavesdropper knows the codebook. The inner bound relies on a Marton-like code construction and the likelihood encoder. A uniform approximation lemma is established that states that the marginal distribution induced by the encoder on each of the bins in the Marton codebook is approximately uniform. Without leakage constraints the inner bound recovers Marton's region and the outer bound reduces to the UVW-outer bound. The bounds match for semi-deterministic (SD) and physically degraded (PD) BCs, as well as for BCs with a degraded message set. The leakage-capacity regions of the SD-BC and the BC with a degraded message set recover past results for different secrecy scenarios. A Blackwell BC example illustrates the results and shows how its leakage-capacity region changes from the capacity region without secrecy to the secrecy-capacity regions for different secrecy scenarios.

A broadcast channel (BC) where the decoders cooperate via a one-sided link is considered. One common and two private messages are transmitted and the private message to the cooperative user should be kept secret from the cooperation-aided user. The secrecy level is measured in terms of strong secrecy, i.e., a vanishing information leakage. An inner bound on the capacity region is derived by using a channel-resolvability-based code that double-bins the codebook of the secret message, and by using a likelihood encoder to choose the transmitted codeword. The inner bound is shown to be tight for semideterministic and physically degraded BCs, and the results are compared with those of the corresponding BCs without a secrecy constraint. Black well and Gaussian BC examples illustrate the impact of secrecy on the rate regions. Unlike the case without secrecy, where sharing information about both private messages via the cooperative link is optimal, our protocol conveys parts of the common and non-confidential messages only. This restriction reduces the transmission rates more than the usual rate loss due to secrecy requirements. An example that illustrates this loss is provided.

This paper studies the problem of the distributed compression of correlated sources with an action-dependent joint distribution. This class of problems is, in fact, an extension of the Slepian-Wolf model, but where cost-constrained actions taken by the encoder or the decoder affect the generation of one of the sources. The purpose of this paper is to study the impact of actions on the achievable rates. In particular, two cases where transmission occurs over a rate-limited link are studied; case A for actions taken at the decoder and case B where actions are taken at the encoder. A complete single-letter characterization of the set of achievable rates is given in both cases. Furthermore, a network coding setup for the case where actions are taken at the encoder is investigated. The sources are generated at different nodes of the network and are required at a set of terminal nodes, yet transmission occurs over a general, acyclic, directed network. For this setup, generalized cut-set bounds are derived, and a full characterization of the set of achievable rates using single-letter expressions is provided. For this scenario, random linear network coding is proved to be optimal, even though this is not a classical multicast problem. In addition, two binary examples are investigated and demonstrate how actions taken at different nodes of the system have a significant effect on the achievable rate region, when compared with a naive time-sharing strategy.

Motivated by the recent developments in wireless power transfer, we study communication with a remotely powered transmitter. We propose an information-theoretic model where a charger can dynamically decide on how much power to transfer to the transmitter based on its side information regarding the communication, while the transmitter needs to dynamically adapt its coding strategy to its instantaneous energy state, which in turn depends on the actions previously taken by the charger. We characterize the capacity as an n-letter mutual information rate under various levels of side information available at the charger. When the charger is finely tunable to different energy levels, referred to as a “precision charger,” we show that these expressions reduce to single-letter form and there is a simple and intuitive joint charging and coding scheme achieving capacity. The precision charger scenario is motivated by the observation that in practice the transferred energy can be controlled by simply changing the amplitude of the beamformed signal. When the charger does not have sufficient precision, for example, when it is restricted to use a few discrete energy levels, we show that the computation of the n-letter capacity can be cast as a Markov decision process if the channel is noiseless. This allows us to numerically compute the capacity for specific cases and obtain insights on the corresponding optimal policy, or even to obtain closed-form analytical solutions by solving the corresponding Bellman equations, as we demonstrate through examples. Our findings provide some surprising insights on how side information at the charger can be used to increase the overall capacity of the system.

In this paper, we introduce construction techniques for network coding in bidirectional networks with arbitrary transmission delays. These coding schemes reduce the number of transmissions and achieve the optimal rate region in the corresponding broadcast model for both multiple unicast and multicast cases with up to three users, under the equal rate constraint. The coding schemes are presented in two phases; first, coding schemes for line, star and line-star topologies with arbitrary transmission delays are provided and second, any general topology with multiple bidirectional unicast and multicast sessions is shown to be decomposable into these canonical topologies to reduce the number of transmissions. As a result, the coding schemes developed for the line, star, and line-star topologies serve as building blocks for the construction of more general coding schemes for all networks. The proposed schemes are proved to be real time in the sense that they achieve the minimum decoding delay. With a negligible size header, these coding schemes are shown to be applicable to unsynchronized networks, i.e., networks with arbitrary transmission delays. Finally, we demonstrate the applicability of these schemes by extensive simulations. The implementation of such coding schemes on a wireless network with arbitrary transmission delays can improve performance and power efficiency.

The secrecy capacity of the type II wiretap channel (WTC II) with a noisy main channel is currently an open problem. Herein its secrecy-capacity is derived and shown to be equal to its semantic-security (SS) capacity. In this setting, the legitimate users communicate via a discrete-memoryless (DM) channel in the presence of an eavesdropper that has perfect access to a subset of its choosing of the transmitted symbols, constrained to a fixed fraction of the blocklength. The secrecy criterion is achieved simultaneously for all possible eavesdropper subset choices. On top of that, SS requires negligible mutual information between the message and the eavesdropper's observations even when maximized over all message distributions. A key tool for the achievability proof is a novel and stronger version of Wyner's soft covering lemma. Specifically, the lemma shows that a random codebook achieves the soft-covering phenomenon with high probability. The probability of failure is doubly-exponentially small in the blocklength. Since the combined number of messages and subsets grows only exponentially with the blocklength, SS for the WTC II is established by using the union bound and invoking the stronger soft-covering lemma. The direct proof shows that rates up to the weak-secrecy capacity of the classic WTC with a DM erasure channel (EC) to the eavesdropper are achievable. The converse follows by establishing the capacity of this DM wiretap EC as an upper bound for the WTC II.

A single-letter upper bound on the feedback capacity of a unifilar finite-state channel is derived. The upper bound is tight for all cases where the feedback capacity is known. Its efficiency is also demonstrated by direct application of the bound on the dicode erasure channel, which results in a new capacity result. The bound is based on a new technique, called the Q-contexts mapping, where the channel outputs are recursively quantized to a finite set, called the contexts set.

Motivated by recent developments in wireless power transfer, we study communication with a remotely powered transmitter. We propose an information-theoretic model where a charger can dynamically decide on how much power to transfer to the transmitter based on its side information regarding the communication, while the transmitter needs to dynamically adopt its coding strategy to its instantaneous energy state, which in turn depends on the actions previously taken by the charger. We characterize the capacity as n-letter mutual information rate under various levels of side information available at the charger. In some special cases, motivated by different settings of practical interest, we simplify these expressions to single-letter form, or provide an algorithm to efficiently compute capacity using dynamic programming. Our results provide some surprising insights on how side information at the charger can be used to increase the overall capacity of the system.

In this paper, we investigate problems of communication over physically degraded, state-dependent broadcast channels (BCs) with cooperating decoders. Two different setups are considered, and their capacity regions are characterized. First, we study a setting in which one decoder can use a finite capacity link to send the other decoder information regarding the messages or the channel states. In this scenario, we analyze two cases: one, where noncausal state information, is available to the encoder and the strong decoder, and the other, where state information, is available only to the encoder in a causal manner. Second, we examine a setting in which the cooperation between the decoders is limited to taking place before the outputs of the channel are given. In this case, one decoder, which is informed of the state sequence noncausally, can cooperate only to send the other decoder rate-limited information about the state sequence. The proofs of the capacity regions introduce a new idea of coding for channels with cooperation between different users, where we exploit the link between the decoders for multiple binnings. Finally, we discuss the optimality of using rate-splitting techniques when coding for cooperative BCs. In particular, we show that rate splitting is not necessarily optimal when coding for cooperative BCs by solving an example in which our method of coding outperforms rate splitting.

The secrecy capacity of the type II wiretap channel (WTC II) with a noisy main channel is currently an open problem. Herein its secrecy-capacity is derived and shown to be equal to its semantic-security (SS) capacity. In this setting, the legitimate users communicate via a discrete-memoryless (DM) channel in the presence of an eavesdropper that has perfect access to a subset of its choosing of the transmitted symbols, constrained to a fixed fraction of the blocklength. The secrecy criterion is achieved simultaneously for all possible eavesdropper subset choices. The SS criterion demands negligible mutual information between the message and the eavesdropper's observations even when maximized over all message distributions. A key tool for the achievability proof is a novel and stronger version of Wyner's soft covering lemma. Specifically, a random codebook is shown to achieve the soft-covering phenomenon with high probability. The probability of failure is doubly exponentially small in the blocklength. Since the combined number of messages and subsets grows only exponentially with the blocklength, SS for the WTC II is established by using the union bound and invoking the stronger soft-covering lemma. The direct proof shows that rates up to the weak-secrecy capacity of the classic WTC with a DM erasure channel (EC) to the eavesdropper are achievable. The converse follows by establishing the capacity of this DM wiretap EC as an upper bound for the WTC II. From a broader perspective, the stronger soft-covering lemma constitutes a tool for showing the existence of codebooks that satisfy exponentially many constraints, a beneficial ability for many other applications in information theoretic security.

The Wyner-Ahlswede-Körner (WAK) empirical-coordination problem where the encoders cooperate via a finite-capacity one-sided link is considered. The coordination-capacity region is derived by combining several source coding techniques, such as Wyner-Ziv coding, binning, and superposition coding. Furthermore, a semi-deterministic (SD) broadcast channel (BC) with one-sided decoder cooperation is considered. Duality principles relating the two problems are presented, and the capacity region for the SD-BC setting is derived. The direct part follows from an achievable region for a general BC that is tight for the SD scenario. A converse is established by using telescoping identities. The SD-BC is shown to be operationally equivalent to a class of relay-BCs, and the correspondence between their capacity regions is established. The capacity region of the SD-BC is transformed into an equivalent region that is shown to be dual to the admissible region of the WAK problem in the sense that the information measures defining the corner points of both regions coincide. Achievability and converse proofs for the equivalent region are provided. For the converse, we use a probabilistic construction of auxiliary random variables that depends on the distribution induced by the codebook. Several examples illustrate the results.

The capacity regions of semideterministic multiuser channels, such as the semideterministic relay channel and the multiple access channel with partially cribbing encoders, have been characterized using the idea of partial-decode-forward. However, the requirement to explicitly decode part of the message at intermediate nodes can be restrictive in some settings; for example, when nodes have different side information regarding the state of the channel. In this paper, we generalize this scheme to cooperative-bin-forward by building on the observation that explicit recovering of part of the message is not needed to induce cooperation. Instead, encoders can bin their received signals and cooperatively forward the bin index to the decoder. The main advantage of this new scheme is illustrated by considering state-dependent extensions of the aforementioned semideterministic setups. While partial-decode-forward is suboptimal in these new setups, cooperative-bin-forward continues to achieve capacity.

The best known inner bound for the two-user discrete memoryless interference channel is the Han-Kobayashi rate region. The coding schemes that achieve this region are based on rate-splitting and superposition coding. In this paper, we develop a multicoding scheme to achieve the same rate region. A key advantage of the multicoding nature of the proposed coding scheme is that it can be naturally extended to more general settings, such as when encoders have state information or can overhear each other. In particular, we extend our coding scheme to characterize the capacity region of the state-dependent deterministic Z-interference channel when noncausal state information is available at the interfering transmitter. We specialize our results to the case of the linear deterministic model with ON/OFF interference, which models a wireless system where a cognitive transmitter is noncausally aware of the times it interferes with a primary transmission. For this special case, we provide an explicit expression for the capacity region and discuss some interesting properties of the optimal strategy. We also extend our multicoding scheme to find the capacity region of the deterministic Z-interference channel when the signal of the interfering transmitter can be overheard at the other transmitter (also known as unidirectional partial cribbing).

The input-constrained erasure channel with feedback is considered, where the binary input sequence contains no consecutive ones, i.e., it satisfies the (1, ∞)-RLL constraint. We derive the capacity for this setting, which can be expressed as Cε= max0≤ p≤0.5((1-ε)Hb(p))/(1+(1-ε)p) , where ε is the erasure probability and Hb(·) is the binary entropy function. Moreover, we prove that a priori knowledge of the erasure at the encoder does not increase the feedback capacity. The feedback capacity was calculated using an equivalent dynamic programming (DP) formulation with an optimal average-reward that is equal to the capacity. Furthermore, we obtained an optimal encoding procedure from the solution of the DP, leading to a capacity-achieving, zero-error coding scheme for our setting. DP is, thus, shown to be a tool not only for solving optimization problems, such as capacity calculation, but also for constructing optimal coding schemes. The derived capacity expression also serves as the only non-trivial upper bound known on the capacity of the input-constrained erasure channel without feedback, a problem that is still open.

The broadcast channel (BC) with one confidential message and where the decoders cooperate via a one-sided link is considered. A pair of messages is transmitted, one message for each user. The message to the cooperative user is confidential and is kept secret from the cooperation-aided user. The secrecy level is measured by the equivocation rate. An inner bound on the secrecy-capacity region of the BC is derived. The inner bound is achieved by double-binning the codebook of the secret message. The inner bound is tight for the semi-deterministic (SD) and physically degraded (PD) cases. The secrecy results are compared to those of the corresponding BCs without a secrecy constraint. A cooperative Blackwell channel example illustrates the impact of secrecy on the rate regions.

Motivated by the cellular uplink scenario along with the increasing capabilities of radio nodes, we consider a state-dependent multiple-access channel in which the encoders can overhear other transmissions while simultaneously sending their own transmissions. In addition, the channel is state dependent and encoders have access to independent causal state information while the decoder has complete state information. We characterize the capacity region of this setup. The encoders in our achievability scheme make full use of the partial cribbing resources by jointly mapping the cribbed sequences and cooperatively forwarding the information to the decoder, without attempting to explicitly recover any part of the other encoder's message or state information.

In this paper we study the cooperative multiple access channel (MAC) with oblivious encoders and characterize its capacity region. Cooperation means that one encoder sends a message to the other encoder via a rate-limited link prior to transmission, while partial cribbing means that one encoder obtains a deterministic function of the other encoder's output. Partial cribbing can be done strictly-causally, causally, and non-causally. Prior work in this field dealt with the case where the two encoders are aware of each other's chosen codebook. In this paper we consider the case of oblivious encoding, where each user in a network is unaware of the codebook chosen by other users. Since an oblivious encoder cannot decode the message sent from another encoder, it cannot implement the Decode-and-Forward coding scheme, as is usually done in cases of partial cribbing with codebook-aware encoders. To overcome this, we introduce the method of Bin-and-Forward, which does not require decoding. Since the possible cribbed signals are not known a priori, in our new coding scheme binning is done on all typical possible cribbed sequences. Instead of sending a decoded message, the oblivious encoder sends the bin in which the cribbed sequence lies. We compare the gain achieved using cooperation and partial cribbing with and without codebook knowledge. Evidently, in the cases of causal and non-causal perfect cribbing, the capacity region is the same for oblivious and codebook-aware encoding. As an example, we consider the Gaussian MAC with cooperation and quantized cribbing. For this model, we give an achievability scheme that shows how knowing the codebooks affects the capacity region for cooperation alone, for partial cribbing alone, and for combined cooperation and partial cribbing.

The semi-deterministic (SD) broadcast channel (BC) where the decoders cooperate via a one-sided link is considered and its capacity region is derived. The direct proof relies on an achievable region for the general BC that is tight for the SD scenario. This achievable region follows by a coding scheme that combines rate-splitting and binning with Marton and superposition coding. The SD-BC is shown to be operationally equivalent to a class of relay-BCs (RBCs) and the correspondence between their capacity regions is established. Furthermore, a dual source coding problem, referred to as the Wyner-Ahlswede-Körner (WAK) problem with one-sided encoder cooperation, is proposed. Transformation principles between the problems are presented and the optimal rate region for the AK problem is stated. The SD-BC capacity and the admissible region of the AK problem are shown to be dual to one another in the sense that the information measures defining the corner points of both regions coincide. Special cases of the two problems are inspected and shown to maintain duality.

The input-constrained erasure channel with feedback is considered, where the input sequence contains no consecutive 1's, i.e. the (1, ∞)-RLL constraint. The capacity is calculated using an equivalent dynamic program, which shows that the optimal average reward is equal to the capacity. The capacity can be expressed as Hb(p) Cϵ= max0≤p≤1(Hb(p))/(p+(1/1-ε)) , where ϵ is the erasure probability and Hb(·) is the binary entropy. This capacity also serves as an upper bound on the capacity of the input-constrained erasure channel without feedback, a problem that is still open.

We investigate if feedback can increase the capacity of an energy harvesting communication channel where a transmitter powered by an exogenous energy arrival process and equipped with a finite battery communicates to a receiver over a memoryless channel. For a simple special case where the energy arrival process is deterministic and the channel is a BEC, we explicitly compute the feed-forward and feedback capacities and show that feedback can strictly increase the capacity of this channel. Building on this example, we also show that feedback can increase the capacity when the energy arrivals are i.i.d. known noncausally at the transmitter and the receiver.

The growing interest in action-dependent channels motivates us to extend the study of action-dependent settings, which until now focused on point-to-point models, to multiple-access channels (MACs). In this paper, we consider a two-user, state-dependent MAC, in which one of the encoders, called the informed (cognitive) encoder, is allowed to take an action that affects the formation of the channel states. Two independent messages are to be sent through the channel: (1) a common message known to both encoders and (2) a private message known only to the informed encoder. In addition, the informed encoder has access to the sequence of channel states in a noncausal manner. Our framework generalizes the previously evaluated settings of state-dependent point-to-point channels with actions and MACs with common messages. We derive a single letter characterization of the capacity region for this setting. Using this general result, we obtain and compute the capacity region for the Gaussian action-dependent MAC. The special methods used in solving the Gaussian case are then applied to obtain the capacity of the Gaussian action-dependent point-to-point channel, a problem left open and solved now. Finally, we establish some dualities between action-dependent channel coding and source coding problems. In particular, we obtain a duality equivalence between the considered MAC setting and the rate distortion model known as successive refinement with actions. This is done by developing a set of simple duality principles that enables us to successfully evaluate the outcome of one problem given the outcome of the other.

The Ahlswede-Körner (AK) coordination problem with one-sided encoder cooperation is considered. Encoder co-operation refers to communication between the encoders via a finite-capacity one-sided link. For this setting, the coordination capacity region is derived. The optimal coding scheme leverages the link between the encoders to optimally handle the correlation between the sources. Moreover, the scheme incorporates several source coding techniques, such as Wyner-Ziv coding, binning and superposition coding. Furthermore, a dual semi-deterministic broadcast channel (BC) with one-sided cooperative decoders is considered. Transformation principles between the two problems are presented and an achievable rate region for the BC setting is derived. The region of the BC is shown to be dual to the optimal region of the AK problem in the sense that the information measures defining the corner points in both regions coincide. Although the optimality of the achievable region for the semi-deterministic BC setting is yet to be shown, the region is optimal in the fully-deterministic case.

We consider the problem of communicating over the state-dependent Z-interference channel (S-D Z-IC), when the state is known noncausally only to the interfering transmitter. We present an achievability scheme and show that it is optimal for the injective deterministic S-D Z-IC. This scheme is simple in the sense that it does not involve rate-splitting. The idea of the scheme is that the interfering transmitter chooses its signal to be jointly typical with an auxilary coordination codebook that allows the unintended receiver to partly decode the resultant interference. We then investigate the special case of the modulo-additive S-D Z-IC in detail and show that in this case standard Gelfand-Pinsker coding for the interfering link and treating interference as noise at the second link is optimal. We also extend our main result to the deterministic state-dependent Z-channel (S-D Z-C) in which an additional message is transmitted on the cross-link.

In this paper we study the multiple access channel (MAC) with combined cooperation and partial cribbing and characterize its capacity region. Cooperation means that the two encoders send a message to one another via a rate-limited link prior to transmission, while partial cribbing means that each of the two encoders obtains a deterministic function of the other encoder's output with or without delay. Prior work in this field dealt separately with cooperation and partial cribbing. However, by combining these two methods we can achieve significantly higher rates. Remarkably, the capacity region does not require an additional auxiliary random variable (RV) since the purpose of both cooperation and partial cribbing is to generate a common message between the encoders. In the proof we combine methods of block Markov coding, backward decoding, double rate-splitting, and joint typicality decoding. Furthermore, we present the Gaussian MAC with combined one-sided cooperation and quantized cribbing. For this model, we give an achievability scheme that shows how many cooperation or quantization bits are required in order to achieve a Gaussian MAC with full cooperation/cribbing capacity region. After establishing our main results, we show that in a state-dependent MAC with cooperation, where the state is known at a partially cribbing encoder and at the decoder, only one auxiliary RV is needed to incorporate both the cribbing and the cooperation. However, there are cases where more than one auxiliary RV is needed, e.g., when the cooperation and cribbing are not used for the same purposes. We present a MAC with an action-dependent state where the action is based on the cooperation but not on the cribbing. Therefore, in this case more than one auxiliary RV is needed. We deduce a general rule for this result.

This work studies the problem of distributed compression of correlated sources with an action-dependent joint distribution. This class of problems are in fact extensions of the Slepian-Wolf model, but where cost-constrained actions affect the generation of one of the sources. A network setup is investigated for the case where actions are taken at the encoder. The first source is available at a node in the network, this node can take actions which affect the generation of the other source which is available at different node in the network. Transmission occurs over a general, acyclic, directed network and both sources are required in a set of terminal nodes. The purpose of this work is to study the implications of actions on the set of achievable rates. For this network, generalized cut-set bounds are derived, and a full characterization of the set of achievable rates using single-letter expressions is provided, showing how actions affect the achievable region in a non-trivial manner. Random linear network coding is proved to be optimal in this setup, even though this is not a classical multicast problem. As a special case of this network we study a multi-user setup with two encoders and one decoder, each source is available to one encoder and transmission occurs over rate-limited link. The optimal rate region for this case is characterized, and calculated for a binary example.

In information theory, mutual information characterizes the maximal gain in wealth growth rate due to knowledge of side information on a gambling result; the betting strategy that achieves this maximum is named the Kelly criterion. In physics, it was recently shown that mutual information characterizes the maximal amount of work that can be extracted from a single heat bath using measurement-based control protocols; extraction that is done using “information engines”. However, to the best of our knowledge, no relation between gambling and information engines has been presented before. In this paper, we briefly review the two and then show an analogy between gambling, where bits are converted into wealth, and information engines, where bits representing measurements are converted into energy. From this analogy follows an extension of gambling to the continuous-valued case, which can be useful for investments in the stock market using options. Moreover, the analogy enables us to use well-known methods and results from one field to solve problems in the other. We present three such cases: maximum work extraction when the probability distributions governing the system and measurements are unknown, work extraction when some energy is lost in each cycle, e.g., due to friction, and an analysis of systems with memory. In all three cases, the analogy enables us to use known results in order to obtain new ones.

The problem of optimal actuation for channel and source coding was recently formulated and solved in a number of relevant scenarios. In this class of models, actions are taken at encoders or decoders, either to acquire side information in an efficient way or to control or probe effectively the channel state. In this paper, the problem of embedding information on the actions is studied for both the source and the channel coding setups. In both cases, a decoder is present that observes only a function of the actions taken by an encoder or a decoder of an action-dependent point-to-point link. For the source coding model, this decoder wishes to reconstruct a lossy version of the source being transmitted over the point-to-point link, while for the channel coding problem, the decoder wishes to retrieve a portion of the message conveyed over the link. For the problem of source coding with actions taken at the decoder, a single letter characterization of the set of all achievable tuples of rate, distortions at the two decoders, and action cost is derived, under the assumption that the mentioned decoder observes a function of the actions noncausally, strictly causally or causally. A special case of the problem in which the actions are taken by the encoder is also solved. A single-letter characterization of the achievable capacity-cost region is then obtained for the channel coding setup with actions. Examples are provided that shed light into the effect of information embedding on the actions for the action-dependent source and channel coding problems.

We study communication over finite state channels (FSCs), where the encoder and the decoder can control the availability or the quality of noise-free feedback, which is fed back from the decoder to the encoder. Specifically, the instantaneous feedback is a function of an action taken by the encoder, an action taken by the decoder, and the channel output. Encoder and decoder actions take values from finite alphabet sets and may be subject to average cost constraints. We prove capacity results for such a setting by constructing a sequence of codes, using a simple scheme based on code tree, which generates channel input symbols along with encoder and decoder actions. We prove that the limit of this sequence exists, and provide an upper bound on the maximum achievable rate. Our upper and lower bounds coincide and hence yield the capacity for the case where the probability of initial state is positive for all states. Next, the capacity is given for indecomposable channels without intersymbol interference as the limit of normalized directed information between the input and output sequences, maximized over an appropriate set of causally conditioned distributions. As a special case of our framework, we characterize the capacity of coding on the backward link in FSCs, i.e., when the decoder sends limited-rate instantaneous coded noise-free feedback on the backward link. Finally, we propose an extension of the Blahut-Arimoto algorithm for evaluating the capacity when actions can be cost constrained and demonstrate its application in a few examples. Among these examples are those of to feed or not to feedback where the encoder takes binary actions that determine whether the current channel output will be fed back to the encoder, with a constraint on the fraction of channel outputs that are fed back.

The Ising channel, which was introduced in 1990, is a channel with memory that models intersymbol interference. In this paper, we consider the Ising channel with feedback and find the capacity of the channel together with a capacity-achieving coding scheme. To calculate the channel capacity, an equivalent dynamic programming (DP) problem is formulated and solved. Using the DP solution, we establish that the feedback capacity is the expression C = (2Hb(a)/3+a) ≈ 0.575522, where (a) is a particular root of a fourth-degree polynomial and Hb(x) denotes the binary entropy function. Simultaneously, a = arg max0≤x≤1(2Hb(x)/3+x). Finally, an error-free, capacity-achieving coding scheme is provided together with the outlining of a strong connection between the DP results and the coding scheme.

In this paper, we consider the finite-state multiple access channel (MAC) with partially cooperative encoders and delayed channel state information (CSI). Here, partial cooperation refers to the communication between the encoders via finite-capacity links. The channel states are assumed to be governed by a Markov process. Full CSI is assumed at the receiver, while at the transmitters, only delayed CSI is available. The capacity region of this channel model is derived by first solving the case of the finite-state MAC with a common message. Achievability for the latter case is established using the notion of strategies, however, we show that optimal codes can be constructed directly over the input alphabet. This results in a single codebook construction that is then leveraged to apply simultaneous joint decoding. Simultaneous decoding is crucial here because it circumvents the need to rely on the capacity region's corner points, a task that becomes increasingly cumbersome with the growth in the number of messages to be sent. The common message result is then used to derive the capacity region for the case with partially cooperating encoders. Next, we apply this general result to the special case of the Gaussian vector MAC with diagonal channel transfer matrices, which is suitable for modeling, e.g., orthogonal frequency division multiplexing-based communication systems. The capacity region of the Gaussian channel is presented in terms of a convex optimization problem that can be solved efficiently using numerical tools. The region is derived by first presenting an outer bound on the general capacity region and then suggesting a specific input distribution that achieves this bound. Finally, numerical results are provided that give valuable insight into the practical implications of optimally using conferencing to maximize the transmission rates.

We consider finite state channels, where the state of the channel is its previous output. We refer to these as Previous Output is the STate (POST) channels. We first focus on POST(α) channels. These channels have binary inputs and outputs, where the state determines if the channel behaves as a Z or an S channel, both with parameter α. We show that the nonfeedback capacity of the POST(α) channel equals its feedback capacity, despite the memory of the channel. The proof of this surprising result is based on showing that the induced output distribution, when maximizing the directed information in the presence of feedback, can also be achieved by an input distribution that does not utilize the feedback. We show that this is a sufficient condition for the feedback capacity to equal the nonfeedback capacity for any finite state channel. We show that the result carries over from the POST(α) channel to a binary POST channel, where the previous output determines whether the current channel will be binary with parameters (a, b) or (b, a). Finally, we show that, in general, feedback may increase the capacity of a POST channel.

The problem of optimal actuation for channel and source coding was recently formulated and solved in a number of relevant scenarios. In this class of models, actions are taken either to acquire side information in an efficient way for source coding, or to control or probe effectively the channel state for channel coding. In this paper, the problem of embedding information on the actions is introduced by considering the presence of an additional decoder that observes only a function of the actions. For the source coding model, this decoder wishes to reconstruct a lossy version of the source being transmitted over the point-to-point link, while, for the channel coding problem, the decoder wishes to retrieve a portion of the message conveyed over the link. In both cases, single-letter performance characterizations are provided for various special cases, along with specific examples.

We consider finite state channels where the state of the channel is its previous output. We refer to such channels as POST (Previous Output is the STate) channels. Our focus is on a simple binary POST channel, with binary inputs and outputs where the state determines if the channel behaves as a Z or an S channel (of equal capacities). We show that the non feedback capacity equals the feedback capacity, despite the memory in the channel. The proof of this surprising result is based on showing that the induced output distribution, when maximizing the directed information in the presence of feedback, can also be achieved by an input distribution that is ignorant of the feedback. Indeed, we show that this is a necessary and sufficient condition for the feedback capacity to equal the non feedback capacity for any finite state channel.

In this paper, we consider a multiple-access channel (MAC) with partial cribbing encoders. This means that each of the two encoders obtains a deterministic function of the output of the other encoder with or without delay. The partial cribbing scheme is especially motivated by the additive noise Gaussian MAC, where perfect cribbing results in the degenerated case of full cooperation between the encoders and requires an infinite entropy link. We derive a single-letter characterization of the capacity of the MAC with partial cribbing for the cases of causal and strictly causal cribbing. Several numerical examples, such as those of quantized cribbing, are presented. We further consider and derive the capacity region where the cribbing depends on actions that are functions of the previous cribbed observations. In particular, we consider a scenario where the action is taken to decide “to crib or not to crib” and show that a naive time-sharing strategy is not optimal.

We study cooperation in multiterminal source coding models involving successive refinement. Specifically, we study the case of a single encoder and two decoders, where the encoder provides a common description to both the decoders and a private description to only one of the decoders. The decoders cooperate via cribbing, i.e., the decoder with access only to the common description is allowed to observe, in addition, a deterministic function of the reconstruction symbols produced by the other. We characterize the fundamental performance limits in the respective settings of noncausal, strictly causal, and causal cribbing. We use a coding scheme, referred to as Forward Encoding and Block Markov Decoding, which builds on one recently used by Cuff and Zhao for coordination via implicit communication. Finally, we use the insight gained to introduce and solve some dual-channel coding scenarios involving multiple-access channels with cribbing.

Four estimators of the directed information rate between a pair of jointly stationary ergodic finite-alphabet processes are proposed, based on universal probability assignments. The first one is a Shannon–McMillan–Breiman-type estimator, similar to those used by Verdú in 2005 and Caiin 2006 for estimation of other information measures. We show the almost sure and$L_{1}$convergence properties of the estimator for any underlying universal probability assignment. The other three estimators map universal probability assignments to different functionals, each exhibiting relative merits such as smoothness, nonnegativity, and boundedness. We establish the consistency of these estimators in almost sure and$L_{1}$senses, and derive near-optimal rates of convergence in the minimax sense under mild conditions. These estimators carry over directly to estimating other information measures of stationary ergodic finite-alphabet processes, such as entropy rate and mutual information rate, with near-optimal performance and provide alternatives to classical approaches in the existing literature. Guided by these theoretical results, the proposed estimators are implemented using the context-tree weighting algorithm as the universal probability assignment. Experiments on synthetic and real data are presented, demonstrating the potential of the proposed schemes in practice and the utility of directed information estimation in detecting and measuring causal influence and delay.

In this paper, we extend the Blahut-Arimoto algorithm for maximizing Massey's directed information. The algorithm can be used for estimating the capacity of channels with delayed feedback, where the feedback is a deterministic function of the output. In order to maximize the directed information, we apply the ideas from the regular Blahut-Arimoto algorithm, i.e., the alternating maximization procedure, to our new problem. We provide both upper and lower bound sequences that converge to the optimum global value. Our main insight in this paper is that in order to find the maximum of the directed information over a causal conditioning probability mass function, one can use a backward index time maximization combined with the alternating maximization procedure. We give a detailed description of the algorithm, showing its complexity and the memory needed, and present several numerical examples.

In this paper, we consider the rate distortion problem of discrete-time, ergodic, and stationary sources with feed forward at the receiver. We derive a sequence of achievable and computable rates that converge to the feed-forward rate distortion. We show that for ergodic and stationary sources, the rate Rn(D) = 1/n min IX̂n→ Xn) is achievable for anyn, where the minimization is performed over the transition conditioning probability p(x̂n|xn) such that E [d(Xn, X̂n] ≤D. We also show that the limit of Rn(D) exists and is the feed-forward rate distortion. We follow Gallager's proof where there is no feed forward and, with appropriate modification, obtain our result. We provide an algorithm for calculating Rn(D) using the alternating minimization procedure and present several numerical examples. We also present a dual form for the optimization of Rn(D) and transform it into a geometric programming problem.

For memoryless sources, delayed side information at the decoder does not improve the rate-distortion function. However, this is not the case for sources with memory, as demonstrated by a number of works focusing on the special case of (delayed) feedforward. In this paper, a setting is studied in which the encoder is potentially uncertain about the delay with which measurements of the side information, which is available at the encoder, are acquired at the decoder. Assuming a hidden Markov model for the source sequences, at first, a single-letter characterization is given for the setup where the side information delay is arbitrary and known at the encoder, and the reconstruction at the destination is required to be asymptotically lossless. Then, with delay equal to zero or one source symbol, a single-letter characterization of the rate-distortion region is given for the case where, unbeknownst to the encoder, the side information may be delayed or not. Finally, examples for binary and Gaussian sources are provided.

A notion of directed information between two continuous-time processes is proposed. A key component in the definition is taking an infimum over all possible partitions of the time interval, which plays a role no less significant than the supremum over “space” partitions inherent in the definition of mutual information. Properties and operational interpretations in estimation and communication are then established for the proposed notion of directed information. For the continuous-time additive white Gaussian noise channel, it is shown that Duncan's classical relationship between causal estimation error and mutual information continues to hold in the presence of feedback upon replacing mutual information by directed information. A parallel result is established for the Poisson channel. The utility of this relationship is demonstrated in computing the directed information rate between the input and output processes of a continuous-time Poisson channel with feedback, where the channel input process is constrained to be constant between events at the channel output. Finally, the capacity of a wide class of continuous-time channels with feedback is established via directed information, characterizing the fundamental limit on reliable communication.

We study cooperation in multi terminal source coding models involving successive refinement. Specifically, we study the case of a single encoder and two decoders, where the encoder provides a common description to both the decoders and a private description to only one of the decoders. The decoders cooperate via cribbing, i.e., the decoder with access only to the common description is allowed to observe, in addition, a deterministic function of the reconstruction symbols produced by the other. We characterize the fundamental performance limits in the respective settings of non-causal, strictly-causal and causal cribbing. We use a new coding scheme, referred to as Forward Encoding and Block Markov Decoding, which is a variant of one recently used by Cuff and Zhao for coordination via implicit communication. Finally, we use the insight gained to introduce and solve some dual channel coding scenarios involving Multiple Access Channels with cribbing.

We consider a two-user multiple-access channel, where one of the encoders is allowed to take an action that effects the formation of the channel states. The states are know non-causally to the encoder. Two independent messages are sent: a common message and a private message transmitted by the informed encoder. We find precise characterizations of the capacity region. Our framework takes account of previously evaluated settings regarding point-to-point channels with actions and multiple-access channels with common messages. We obtain the capacity of the Gaussian action-dependent point-to-point channel.

In this paper, a single-letter characterization for the capacity region of finite-state multiple access channels (MACs) with partially cooperative encoders is derived. Partial cooperation here is in the sense that the encoders communicate with each other through finite-capacity links. The channel states are assumed to be governed by a Markov processes. Full channel state information (CSI) is assumed at the receiver, while only delayed CSI is available at transmitters. The capacity region is derived by first solving the case of finite-state multiple access channels with common message, using rate splitting, multiplexing and simultaneous decoding in order to establish the achievability. The common message result is then used to derive the capacity region of the partially cooperative encoders case. Finally, we apply this result in order to obtain the capacity region for a finite-state Gaussian MAC with partially cooperative encoders.

We propose four approaches to estimating the directed information rate between a pair of jointly stationary ergodic processes with the help of universal probability assignments. The four approaches yield estimators with different merits such as nonnegativity and boundedness. We establish consistency of these estimators in various senses and derive near-optimal rates of convergence in the minimax sense under mild conditions. The estimators carry over directly to estimating other information measures of stationary ergodic processes, such as entropy rate and mutual information rate, and provide alternatives to classical approaches in the existing literature. Guided by the theoretical results, we use context tree weighting as the vehicle for the implementations of the proposed estimators. Experiments on synthetic and real data are presented, demonstrating the potential of the proposed schemes in practice and the efficacy of directed information estimation as a tool for detecting and measuring causality and delay.

For memoryless sources, delayed side information at the decoder does not improve the rate-distortion function. However, this is not the case for more general sources with memory, as demonstrated by a number of works focusing on the special case of (delayed) feedforward. In this paper, a setting is studied in which the side information is delayed and the encoder is informed about the side information sequence. Assuming a hidden Markov model for the sources, at first, a single-letter characterization is given for the set-up where the side information delay is arbitrary and known at the encoder, and the reconstruction at the destination is required to be (near) lossless. Then, with delay equal to zero or one source symbol, a single-letter characterization is given of the rate-distortion function for the case where side information may be delayed or not, unbeknownst to the encoder. Finally, an example for a binary source is provided.

A single-letter characterization is provided for the capacity region of finite-state multiple access channels. The channel state is a Markov process, the transmitters have access to delayed state information, and channel state information is available at the receiver. The delays of the channel state information are assumed to be asymmetric at the transmitters. We apply the result to obtain the capacity region for a finite-state Gaussian MAC, and for a finite-state multiple-access fading channel. We derive power control strategies that maximize the capacity region for these channels.

In this paper, we consider the cascade and triangular rate-distortion problems where the same side information is available at the source node and user 1, and the side information available at user 2 is a degraded version of the side information at the source node and user 1. We characterize the rate-distortion region for these problems. For the cascade setup, we show that, at user 1, decoding and rebinning the codeword sent by the source node for user 2 is optimum. We then extend our results to the two-way cascade and triangular setting, where the source node is interested in lossy reconstruction of the side information at user 2 via a rate limited link from user 2 to the source node. We characterize the rate-distortion regions for these settings. Complete explicit characterizations for all settings are given in the quadratic Gaussian case. We conclude with two further extensions: a triangular source coding problem with a helper, and an extension of our two-way cascade setting in the quadratic Gaussian case.

We consider the cascade and triangular rate-distortion problem where side information is known to the source encoder and to the first user but not to the second user. We characterize the rate-distortion region for these problems, as well as some of their extensions. For the quadratic Gaussian case, we show that it is sufficient to consider jointly Gaussian distributions, which leads to an explicit solution.

In this paper we consider the multiple access channel (MAC) with partial cribbing encoders which means that each encoder obtains a deterministic function of the other encoder output, possibly with delay. The partial cribbing is especially motivated by the additive noise Gaussian MAC since perfect cribbing results in the degenerated case of full cooperation between the encoders and requires an infinite entropy link. We derive a single letter characterization of the capacity of MAC with partial cribbing for the cases of causal and strictly causal partial cribbing. Several numerical examples such as quantized cribbing are presented.We further consider and derive the capacity region where the cribbing depends on actions that are function of the previous cribbed observations. In particular, we consider a scenario where the action is “to crib or not to crib” and show that a naive time-sharing strategy is not optimal.

We establish results assessing the fundamental limits on reliable communication over Finite State Channels (FSCs), when the encoder and the decoder can control the availability or the quality of the feedback. The instantaneous feedback is a function of a cost constrained action taken by the encoder, a cost constrained action taken by the decoder, and the channel output. Achievability is through construction of a sequence of convergent achievable rates, using a simple scheme based on `code tree' generation, that generates channel input symbols along with encoder and decoder actions. For a given block length N, we give an upper bound on the maximum achievable rate. For stationary indecomposable channels without intersymbol interference (ISI), the capacity is given as the limit of normalized directed information between the input and output sequence, maximized over an appropriate set of causally conditioned distributions. As important special cases, we characterize (a) the framework of `to feed or not to feed back' where either the encoder or the decoder takes binary actions to determine whether current channel output will be fed back to the encoder, with a constraint on the fraction of channel outputs that are fed back, (b) the capacity of `coding on the backward link' in FSCs, i.e., when the decoder sends limited-rate instantaneous coded noise-free feedback on the backward link.

A single-letter characterization is provided for the capacity region of finite-state multiple access channels using directed information. The channel state is a Markov process, the transmitters have access to delayed state information, and channel state information is available at the receiver. The delays of the channel state information are assumed to be asymmetric at the transmitters. We obtain the capacity region by innovative way, using a multi-letter expression for the capacity region of finite-state MAC with time-invariant feedback.

In this paper we consider the Ising channel, which is a channel with memory. We formulate a dynamic program that characterizes the capacity of the Ising channel with feedback and solve it numerically using the value iteration algorithm. We then establish analytically that the feedback capacity is the expression C = (2H(a)/3+a) ≈ 0.575522 where a is a particular root of a fourth-degree polynomial and, simultaneously, is the value that maximizes (2H(z)/3+z) over 0 ≤ z ≤ 1, where H(z) is the binary entropy function.

THIS PAPER IS ELIGIBLE FOR THE STUDENT PAPER AWARD. Consider the rate distortion problem of discrete-time, ergodic, and stationary sources with feed forward at the receiver. We derive a sequence of achievable and computable rates that converge to the feed forward rate distortion. For ergodic and stationary sources, we show that for any n, the rate Rn(D)=1/n min I(X̂n→Xn) is achievable, where the minimization is taken over the transition conditioning probability p(x̂n|xn) such that E[d(Xn, X̂n)] ≤ D. The limit of Rn(D) exists and is the feed forward rate distortion. We follow Gallager's proof where there is no feed forward, and, with appropriate modification, obtain our result. We provide an algorithm for calculating Rn(D) using the alternating minimization procedure, and present several numerical examples.

We investigate the capacity of a multiple access channel with cooperating encoders where partial state information is known to each encoder in a non-causal way and full state information is known to the decoder. The cooperation between the encoders has a two-fold purpose: to generate empirical state coordination between the encoders, and to share information about the private messages that each encoder has. For two-way cooperation, this two-fold purpose is achieved by double-binning, where the first layer of binning is used to generate the state coordination similarly to the two-way source coding, and the second layer of binning is used to transmit information about the private messages. The complete result provides the framework and perspective for addressing a complex level of cooperation that mixes states and messages in an optimal way. We present few examples and compare the optimal coding scheme that combines the message and the state to naive cooperation schemes that are based on separate message and state coding.

The notion of directed information was recently introduced for stochastic processes in continuous time. The key idea of the definition is to consider all possible time partitions of a given interval. Unlike the definition of mutual information of discrete-time random variables with continuous alphabets where the supremum over all possible partitions of the alphabets plays an important role, here the infimum over all possible time-partition plays an important role. We show that the fundamental limit on reliable communication for a wide class of continuous-time channels with feedback are characterized using the notion of continuous-time directed information.

We consider the problem of optimal probing of states of a channel by transmitter and receiver for maximizing rate of reliable communication. The channel is discrete memoryless (DMC) with i.i.d. states. The encoder takes probing actions dependent on the message. It then uses the state information obtained from probing causally or noncausally to generate channel input symbols. The decoder may also take channel probing actions as a function of the observed channel output and use the channel state information thus acquired, along with the channel output, to estimate the message. We refer to the maximum achievable rate for reliable communication for such systems as the “Probing Capacity”. We characterize this capacity when the encoder and decoder actions are cost constrained. To motivate the problem, we begin by characterizing the trade-off between the capacity and fraction of channel states the encoder is allowed to observe, while the decoder is aware of channel states. In this setting of `to observe or not to observe' state at the encoder, we compute certain numerical examples which exhibit a pleasing phenomenon, where encoder can observe a relatively small fraction of states and yet communicate at maximum rate, i.e., rate when observing states at encoder is not cost constrained.

We investigate the role of directed information in portfolio theory, data compression, and statistics with causality constraints. In particular, we show that directed information is an upper bound on the increment in growth rates of optimal portfolios in a stock market due to causal side information. This upper bound is tight for gambling in a horse race, which is an extreme case of stock markets. Directed information also characterizes the value of causal side information in instantaneous compression and quantifies the benefit of causal inference in joint compression of two stochastic processes. In hypothesis testing, directed information evaluates the best error exponent for testing whether a random processYcausally influences another processXor not. These results lead to a natural interpretation of directed informationI(Yn→Xn) as the amount of information that a random sequenceYn= (Y1,Y2,...,Yn) causally provides about another random sequenceXn= (X1,X2,...,Xn). A new measure, directed lautum information, is also introduced and interpreted in portfolio theory, data compression, and hypothesis testing.

We investigate the capacity of a multiple access channel with cooperating encoders where partial state information is known to each encoder and full state information is known to the decoder. The cooperation between the encoders has a two-fold purpose: to generate empirical state coordination between the encoders, and to share information about the private messages that each encoder has. For two-way cooperation, this two-fold purpose is achieved by double-binning, where the first layer of binning is used to generate the state coordination similarly to the two-way source coding, and the second layer of binning is used to transmit information about the private messages. The complete result provides the framework and perspective for addressing a complex level of cooperation that mixes states and messages in an optimal way.

We study source coding in the presence of side information, when the system can take actions that affect the availability, quality, or nature of the side information. We begin by extending the Wyner-Ziv problem of source coding with decoder side information to the case where the decoder is allowed to choose actions affecting the side information. We then consider the setting where actions are taken by the encoder, based on its observation of the source. Actions may have costs that are commensurate with the quality of the side information they yield, and an overall per-symbol cost constraint may be imposed. We characterize the achievable tradeoffs between rate, distortion, and cost in some of these problem settings. Among our findings is the fact that even in the absence of a cost constraint, greedily choosing the action associated with the “best” side information is, in general, suboptimal. A few examples are worked out.

We clarify the relationship among several existing achievable multiple description rate-distortion regions by investigating the role of refinement layer in multiple description coding. Specifically, we show that the refinement layer in the El Gamal-Cover (EGC) scheme and the Venkataramani-Kramer-Goyal (VKG) scheme can be removed; as a consequence, the EGC region is equivalent to the EGC* region (an antecedent version of the EGC region) while the VKG region (when specialized to the 2-description case) is equivalent to the Zhang-Berger (ZB) region. Moreover, we prove that for multiple description coding with individual and hierarchical distortion constraints, the number of layers in the VKG scheme can be significantly reduced when only certain weighted sum rates are concerned. The role of refinement layer in scalable coding (a special case of multiple description coding) is also studied.

We consider the cascade and triangular rate-distortion problem where side information is known to the source encoder and to the first user but not to the second user. We characterize the rate-distortion region for these problems. For the quadratic Gaussian case, we show that it suffices to consider jointly Gaussian distributions, a fact that leads to an explicit solution.

In this paper, we develop a universal algorithm to estimate Massey's directed information for stationary ergodic processes. The sequential probability assignment induced by a universal source code plays the critical role in the estimation. In particular, we use context tree weighting to implement the algorithm. Some numerical results are provided to illustrate the performance of the proposed algorithm.

The theory of Markov set-chains is applied to derive upper and lower bounds on the capacity of finite-state channels that are tighter than the classic bounds by Gallager. The new bounds coincide and yield single-letter capacity characterizations for a class of channels with the state process known at the receiver, including channels whose long-term marginal state distribution is independent of the input process. Analogous results are established for finite-state multiple access channels.

We develop elements of a theory of cooperation and coordination in networks. Rather than considering a communication network as a means of distributing information, or of reconstructing random processes at remote nodes, we ask what dependence can be established among the nodes given the communication constraints. Specifically, in a network with communication rates$\{R_{i,j}\}$between the nodes, we ask what is the set of all achievable joint distributions$p(x_{1},\ldots ,x_{m})$of actions at the nodes of the network. Several networks are solved, including arbitrarily large cascade networks. Distributed cooperation can be the solution to many problems such as distributed games, distributed control, and establishing mutual information bounds on the influence of one part of a physical system on another.

Consider the two-way rate-distortion problem in which a helper sends a common limited-rate message to both users based on side information at its disposal. We characterize the region of achievable rates and distortions when the Markov relation (Helper)-(User 1)-(User 2) holds. The main insight of the result is that in order to achieve the optimal rate, the helper may use a binning scheme, as in Wyner-Ziv, where the side information at the decoder is the ¿further¿ user, namely, User 2. We derive these regions explicitly for the Gaussian sources with square error distortion, analyze a tradeoff between the rate from the helper and the rate from the source, and examine a special case where the helper has the freedom to send different messages, at different rates, to the encoder and the decoder. The converse proofs use a technique for verifying Markov relations via undirected graphs.

In this paper, we study the zero-error capacity for finite state channels with feedback when channel state information is known to both the transmitter and the receiver. We prove that the zero-error capacity in this case can be obtained through the solution of a dynamic programming problem. Each iteration of the dynamic programming provides lower and upper bounds on the zero-error capacity, and in the limit, the lower bound coincides with the zero-error feedback capacity. Furthermore, a sufficient condition for solving the dynamic programming problem is provided through a fixed-point equation. Analytical solutions for several examples are provided.

In this paper, some existing inner bounds of multiple description problem are investigated. We prove that the El Gamal-Cover region is a subset of the Zhang-Berger (ZB) region. Furthermore, the Venkataramani-Kramer-Goyal region is equivalent to the Zhang-Berger region.

The notion of directed information is introduced for stochastic processes in continuous time. Properties and operational interpretations are presented for this notion of directed information, which generalizes mutual information between stochastic processes in a similar manner as Massey's original notion of directed information generalizes Shannon's mutual information in the discrete-time setting. As a key application, Duncan's theorem is generalized to estimation problems in which the evolution of the target signal is affected by the past channel noise, and the causal minimum mean squared error estimation is related to directed information from the target signal to the observation corrupted by additive white Gaussian noise. An analogous relationship holds for the Poisson channel.

We have formalized and characterized the fundamental limits for the problem of source coding with decoder side information, where the decoder is allowed to choose actions that affect the nature and quality of the side information. In the context of the problem studied, and its motivation, it is natural to also look at the case where actions are taken at the encoder: Based on its observation of the source sequence Xn, the encoder chooses a sequence of actions An. Nature then generates the side information sequence Ynas the output of the memoryless channel PY|X,Awhose input is the pair (Xn, An). The encoder now chooses the index to be given to the decoder on the basis of both the source and the side information sequence. The reconstruction sequence X¿nis then based on the index and on the side information sequence. A challenging aspect of this scenario is that the actions chosen by the encoder not only affect the quality of the side information, but can also be used to directly convey information about the source sequence. This scenario is depicted in Figure 6. In , we characterize the achievable tradeoff between rate, distortion, and cost for this problem setting as well.

Consider the two-way rate-distortion problem in which a helper sends a common limited-rate message to both users based on side information at its disposal. We characterize the region of achievable rates and distortions where a Markov form (Helper)-(User 1)-(User 2) holds. The main insight of the result is that in order to achieve the optimal rate, the helper may use a binning scheme, as in Wyner-Ziv, where the side information at the decoder is the ¿further¿ user, namely, User 2. The converse proofs use a new technique for verifying Markov relations via undirected graphs.

In this paper, the Gray-Wyner network with a limited-rate helper is investigated. The helper sends a common message to the encoder and the decoders. We characterize the complete rate region. Successive refinement with a limited-rate helper is treated as a special case. The rate region for a Gaussian source with squared error distortions is explicitly calculated.

In this work we study source coding problems where a helper provides rate-limited side information to the involved parties. We first consider the Wyner-Ziv problem, where in addition to the memoryless side information available to the decoder, a helper sends common, rate-limited side information to the encoder and decoder. A single letter characterization of the achievable rates is derived, under certain Markov conditions on the source and side information. We then examine the problem of cascade rate distortion with a helper. Partial results are derived also for the case where the side information is not necessarily common, i.e., when the helper can send different streams of coded side information to the involved parties.

The notion of directed information is introduced for stochastic processes in continuous time. Properties and operational interpretations are presented for this notion of directed information, which generalizes mutual information between stochastic processes in a similar manner as Massey's original notion of directed information generalizes Shannon's mutual information in the discrete-time setting. As a key application, Duncan's theorem is generalized to estimation problems in which the evolution of the target signal is affected by the past channel noise, and the causal minimum mean squared error estimation is related to directed information from the target signal to the observation corrupted by additive white Gaussian noise. An analogous relationship holds for the Poisson channel. The notion of directed information as a characterizing of the fundamental limit on reliable communication for a wide class of continuous-time channels with feedback is discussed.

The capacity region of the finite-state multiple-access channel (FS-MAC) with feedback that may be an arbitrary time-invariant function of the channel output samples is considered. We characterize both an inner and an outer bound for this region, using Massey's directed information. These bounds are shown to coincide, and hence yield the capacity region, of indecomposable FS-MACs without feedback and of stationary and indecomposable FS-MACs with feedback, where the state process is not affected by the inputs. Though “multiletter” in general, our results yield explicit conclusions when applied to specific scenarios of interest. For example, our results allow us to do the following.Identify a large class of FS-MACs, that includes the additive$\bmod \,2$noise MAC where the noise may have memory, for which feedback does not enlarge the capacity region.

We consider capacity of discrete-time channels with feedback for the general case where the feedback is a time-invariant deterministic function of the output samples. Under the assumption that the channel states take values in a finite alphabet, we find a sequence of achievable rates and a sequence of upper bounds on the capacity. The achievable rates and the upper bounds are computable for any N, and the limits of the sequences exist. We show that when the probability of the initial state is positive for all the channel states, then the capacity is the limit of the achievable-rate sequence. We further show that when the channel is stationary, indecomposable, and has no intersymbol interference (ISI), its capacity is given by the limit of the maximum of the (normalized) directed information between the input XNand the output YN, i.e., C=limNrarrinfin(1/n)max I(XNrarrYN) where the maximization is taken over the causal conditioning probability Q(xNparzN-1) defined in this paper. The main idea for obtaining the results is to add causality into Gallager's results on finite state channels. The capacity results are used to show that the source-channel separation theorem holds for time-invariant determinist feedback, and if the state of the channel is known both at the encoder and the decoder, then feedback does not increase capacity.

In this work, we find the capacity of a compound finite-state channel (FSC) with time-invariant deterministic feedback. We consider the use of fixed length block codes over the compound channel. Our achievability result includes a proof of the existence of a universal decoder for the family of FSCs with feedback. As a consequence of our capacity result, we show that feedback does not increase the capacity of the compound Gilbert-Elliot channel. Additionally, we show that for a stationary and uniformly ergodic Markovian channel, if the compound channel capacity is zero without feedback then it is zero with feedback. Finally, we use our result on the FSC to show that the feedback capacity of the memoryless compound channel is given by infthetasmaxQXI(X; Y |thetas).

New upper and lower bounds on the capacity of finite-state channels are established. For a class of channels, these bounds yield a single-letter capacity formula, which is previously unknown in the literature.

We study the problem of gambling in horse races with causal side information and show that Masseypsilas directed information characterizes the increment in the maximum achievable capital growth rate due to the availability of side information. This result gives a natural interpretation of directed information I(Ynrarr Xn) as the amount of information that Yncausally provides about Xn. Extensions to stock market portfolio strategies and data compression with causal side information are also discussed.

The capacity region of the finite-state multiple access channel (FS-MAC) with feedback that may be an arbitrary time-invariant function of the channel output samples is considered. We provided a sequence of inner and outer bounds for this region. These bounds are shown to coincide, and hence yield the capacity region for two cases of FS-MACs: (1) when the state process is stationary and ergodic and not affected by the inputs; (2) an indecomposable FS-MAC without feedback. Though the capacity region is "multi-letter" in general, our results yield explicit conclusions when applied to specific scenarios of interest.

In this paper, we study the zero-error capacity for finite state channel with feedback when channel state information is known to both the transmitter and the receiver. We prove that the zero-error capacity in this case can be obtained through the solution of a dynamic programming problem. Exact answers are also given for certain cases.

We establish that the feedback capacity of the trapdoor channel is the logarithm of the golden ratio and provide a simple communication scheme that achieves capacity. As part of the analysis, we formulate a class of dynamic programs that characterize capacities of unifilar finite-state channels. The trapdoor channel is an instance that admits a simple closed-form solution.

We propose the problem of coordinating action over many nodes by distributed communication. The idea is to switch the emphasis from exchanging information to setting up cooperative action. Examples are given. We solve most 3-node problems but one remains open.

We consider a family of channels, collectively referred to as the 'chemical channel', which generalizes the trapdoor channel. We show that the feedback capacity of the chemical channel can be cast as the solution to a dynamic programming (DP) problem. We obtain numerical values for the feedback capacity of the chemical channel by approximating the solution of the DP problem using value iteration. For the special case of the trapdoor channel, by solving the DP problem analytically, we prove that the feedback capacity of the trapdoor channel is the logarithm of the golden ratio. Further, we describe a simple scheme that achieves the capacity of the trapdoor channel. The scheme has zero probability of error, which allows us to conclude that the logarithm of the golden ratio is also the zero error capacity of the chemical channel.

This work addresses the feedback capacity of compound channels with memory. We provide an upper bound on the feedback capacity of a compound finite-state channel. As a consequence, we show that for a stationary channel with memory, if the compound channel capacity is zero without feedback then it is zero with feedback. Additionally, we show that feedback does not increase the capacity of the compound Gilbert-Elliot channel.

We consider channel coding with feedback for the general case where the feedback may be an arbitrary deterministic function of the output samples. Under the assumption that the channel states take values in a finite alphabet, we find an achievable rate and an upper bound on the capacity. We conclude by showing that when the channel is indecomposable, and has no intersymbol interference, its capacity is given by the limit of the maximum of the (normalized) directed information between the input XNand the output YN, i.e. C = limNrarrinfin/1N max I(XNrarr YN), where the maximization is over the causal conditioning probability Q(xN||kN-) defined in this paper

We introduce Gaussian mixture models of 'structure' and colour features in order to classify coloured textures in images, with a view to the retrieval of textured colour images from databases. Classifications are performed separately using structure and colour and then combined using a confidence criterion. We apply the models to the VisTex database and to the classification of man-made and natural areas in aerial images. We compare these models with others in the literature, and show an overall improvement in performance.

This paper presents a parametric solution to the problem of estimating the orientation in space of a planar textured surface, from a single, noisy, observed image of it. The coordinate transformation from surface to image coordinates, due to the perspective projection, transforms each homogeneous sinusoidal component of the surface texture into a sinusoid whose frequency is a function of location. The functional dependence of the sinusoid phase in location is uniquely determined by the tilt and slant angles of the surface. Using the phase differencing algorithm we fit a polynomial phase model to a sinusoidal component of the observed texture. Assuming the estimated polynomial coefficients are the coefficients of a Taylor series expansion of the phase, we establish a linear recursive relation between the model parameters and the unknown slant and tilt. A linear least squares solution of the resulting system provides the slant and tilt estimates. To improve accuracy, an iterative refinement procedure is applied in a small neighborhood of these estimates. The performance of the proposed algorithms is evaluated by applying them to images of different planar surfaces, and by comparing their statistical performance with the Cramer-Rao bound. The combined two-stage algorithm is shown to produce estimates that are close to the bound.

This paper presents a computationally and statistically efficient parametric solution to the problem of estimating the orientation in space of a planar textured surface from a single, noisy, observed image of it. The coordinate transformation from surface to image coordinates, due to the perspective projection, transforms each homogeneous sinusoidal component of the surface texture into a sinusoid whose frequency is a function of location. The functional dependence of the sinusoid phase in location is uniquely determined by the tilt and slant angles of the surface. From the physical model of the perspective projection, we derive the Cramer-Rao lower bound on the error variance of estimating the tilt and slant of the observed surface in the presence of observation noise. It is shown in this paper that the phase of each of the sinusoids can be expressed as a linear function of some variables that are related to the surface tilt and slant angles. Using the phase differencing algorithm, we fit a polynomial phase model to a sinusoidal component of the observed texture. Substituting in the derived linear relation, the unknown phase with the one estimated using the phase differencing algorithm, we obtain a closed-form, analytic, and computationally efficient solution to the problem of estimating the tilt and slant angles. The algorithm performance is shown to be close to the Cramer-Rao bound, even for low signal-to-noise ratios, at computational complexity which is considerably lower than that of any existing algorithm.

This paper presents a parametric solution to the problem of estimating the orientation in space of a planar textured surface, from a single observed image of it. The coordinate transformation from surface to image coordinates, due to the perspective projection, transforms each homogeneous sinusoidal component of the surface texture into a sinusoid whose frequency is a function of location. Using the phase differencing algorithm we fit a polynomial phase model to a sinusoidal component of the observed texture. Assuming the estimated polynomial coefficients are the coefficients of a Taylor series expansion of the phase, we establish a linear recursive relation between the model parameters and the unknown slant and tilt. A linear least squares solution of the resulting system provides the slant and tilt estimates. To improve accuracy, an iterative refinement procedure is applied in a small neighborhood of these estimates. The combined two-stage algorithm is shown to produce estimates that are close to the Cramer-Rao bound, at a computational complexity which is considerably lower than that of any existing algorithm.