Zero-error coding encompasses a variety of source and channel problems where the probability of error must be exactly zero. This condition is stricter than that of the vanishing error regime, where the error probability goes to zero as the code blocklength goes to infinity. In general, zero-error coding is an open combinatorial question. We investigate two unsolved zero-error problems: the source coding problem with side information and the channel coding problem. We focus our attention on families of independent problems for which the probability distribution decomposes into a product of probability distributions. A crucial step is the additivity property of the optimal rate, which does not always hold in the zero-error regime, unlike in the vanishing error regime. When the additivity holds, the concatenation of optimal codes is optimal. We derive a condition under which the additivity of the complementary graph entropyHfor the AND product of graphs and for the disjoint union of graphs are equivalent. Then we establish the connection with a recent result obtained by Wigderson and Zuiddam and by Schrijver, for the zero-error capacityC0. As a consequence, we provide new single-letter characterizations ofHandC0, for example when the graph is a product of perfect graphs, which is not perfect in general, and for the class of graphs obtained by the product of a perfect graphGwith the pentagon graphC5. By building on Haemers result forC0, we also show that the additivity ofHdoes not hold for the product of the Schläfli graph with its complementary graph.

We propose a zero estimation cost (ZEC) scheme for causal-encoding noncausal-decoding vector-valued Witsenhausen counterexample based on the coordination coding result. In contrast to source coding, our goal is to communicate a controlled system state. The introduced ZEC scheme is a joint controlcommunication approach that transforms the system state into a sequence that can be efficiently communicated using block coding. The noncausal decoder receives sufficient information for reconstructing the system state perfectly, enabling the achievable estimation cost to be zero. Numerical results show that our approach significantly reduces the power budget required for achieving zero-estimation-cost state reconstruction at the decoder. In the second part, we introduce a more general non-zero estimation cost (Non-ZEC) scheme. We observe numerically that the Non-ZEC scheme operates as a time-sharing mechanism between Witsenhausen's original two-point strategy and the ZEC scheme. Overall, by leveraging block-coding gain, our proposed methods substantially improve the power-estimation trade-off for Witsenhausen counterexample.

We investigate the mismatched distortion-rate problem formulated by Lapidoth in 1997. The single-letter characterization of the distortion-rate tradeoff is an open problem. When the rate is large enough, the mismatched distortion-rate problem is deeply related to the mechanism design problem formulated by Jackson and Sonnenschein in 2007. Inspired by this solution, we formulate a new converse bound that matches the achievability bound in four special cases: 1) when the rate is large enough, 2) when the source is binary and uniform and the decoder output is binary, 3) when the encoder distortion measure does not depend on the source symbols, 4) when the sum of the two distortion measures is zero. An important feature of the model is the stochastic post-processing of the codewords. By carefully selecting the randomness of the decoding function, it is optimal for the encoder to correctly transmit the source.

We investigate the Witsenhausen counterexample in a continuous vector-valued context with a causal encoder and noncausal decoder. Our main result is the optimal single-letter condition that characterizes the set of achievable Witsenhausen power costs and estimation costs, leveraging a modified weak typicality approach. In particular, we accommodate our power analysis to the causal encoder constraint, and provide an improved distortion error analysis for the challenging estimation of the interim state. Interestingly, the idea of dual role of control is explicitly captured by the two auxiliary random variables.

We study the continuous vector-valued Witsen-hausen counterexample with Gaussian states through the lens of empirical coordination coding. We characterize the region of achievable pairs of costs in three scenarios: (i) causal encoding and causal decoding, (ii) causal encoding and causal decoding with channel feedback, and (iii) causal encoding and noncausal decoding with channel feedback. In these vector-valued versions of the problem, the optimal coding schemes must rely on a time-sharing strategy, since the region of achievable pairs of costs might not be convex in the scalar version of the problem. We examine the role of the channel feedback when the encoder is causal and the decoder is either causal or non-causal, and we show that feedback improves the performance, only when the decoder is non-causal.

Network slicing is a key component of 5G-and-beyond networks but induces many questions related to an associated business model and its need to be regulated due to its difficult co-existence with the network neutrality debate. We propose in this paper a slicing model in the case of heterogeneous users/applications where a service provider may purchase a slice in a wireless network and offer a “premium” service where the improved quality stems from higher prices leading to less demand and less congestion than the basic service offered by the network owner, a scheme known as Paris Metro Pricing. We obtain thanks to game theory the economically-optimal slice size and prices charged by all actors. We also compare with the case of a unique “pipe” (no premium service) corresponding to a fully-neutral scenario and with the case of vertical integration to evaluate the impact of slicing on all actors and identify the “best” economic scenario and the eventual need for regulation.

The vector-valued extension of the famous Witsenhausen counterexample setup is studied where the encoder, i.e. the first decision maker, non-causally knows and encodes the i.i.d. state sequence and the decoder, i.e. the second decision maker, causally estimates the interim state. The coding scheme is transferred from the finite alphabet coordination problem, for which it is proved to be optimal. The extension to the Gaussian setup is based on a non-standard weak typicality approach and requires a careful average estimation error analysis since the interim state is estimated by the decoder. We provide a single-letter expression that characterizes the optimal trade-off between the Witsenhausen power cost and estimation cost. The two auxiliary random variables improve the communication with the decoder, while performing the dual role of the channel input, which also controls the state of the system. Interestingly, we show that a pair of discrete and continuous auxiliary random variables, outperforms both Witsenhausen two-point strategy and the best affine policies. The optimal choice of random variables remains unknown.

In the zero-error Slepian-Wolf source coding problem, the optimal rate is given by the complementary graph entropy $\bar H$ of the characteristic graph. It has no single-letter formula, except for perfect graphs, for the pentagon graph with uniform distribution G5, and for their disjoint union. We consider two particular instances, where the characteristic graphs respectively write as an AND product ∧, and as a disjoint union ⊔. We derive a structural result that equates $\bar H( \wedge )$ and $\bar H( \sqcup )$ up to a multiplicative constant, which has two consequences. First, we prove that the cases where $\bar H( \wedge )$ and $\bar H( \sqcup )$ can be linearized coincide. Second, we determine $\bar H$ in cases where it was unknown: products of perfect graphs; and G5∧ G when G is a perfect graph, using Tuncel et al.’s result for $\bar H({G_5} \sqcup G)$. The graphs in these cases are not perfect in general.

We study the zero-error source coding problem in which an encoder with Side Information (SI) g(Y) transmits source symbols X to a decoder. The decoder has SI Y and wants to recover f(X,Y) where f,g are deterministic. We exhibit a condition on the source distribution and g that we call "pairwise shared side information", such that the optimal rate has a single-letter expression. This condition is satisfied if every pair of source symbols "share" at least one SI symbol for all output of g; in the case f(X,Y) = X, the PX,Yand g that satisfy it, induce the worst optimal rate. More generally for all f, it has a practical interpretation, as Y models a request made by the encoder on an image X, and g(Y) corresponds to the type of request. It also has a graph-theoretical interpretation: under "pairwise shared side information" the characteristic graph can be written as a disjoint union of OR products. In the case where the source distribution is full-support, we provide an analytic expression for the optimal rate. We develop an example under "pairwise shared side information", and we show that the optimal coding scheme outperforms several strategies from the literature.

Network slicing is a key component of 5G-and-beyond networks, requiring to define a business model for resource allocation. We consider a model with a Service Provider (SP) that may purchase a slice in a wireless network, in order to offer a “premium” service where the improved quality stems from higher prices leading to less demand and less congestion than the basic service offered by the network owner, a scheme known as Paris Metro Pricing. One optimization problem for the SP is the choice of how much resource to allocate to that slice. We also compare with the case of a unique “pipe” (no premium service) and with the case of vertical integration to evaluate the impact of slicing on all actors and identify the “best” economic scenario.

In decentralized decision-making problems, communicating agents choose their actions based on locally available information and knowledge about decision rules or strategies of other agents. In this work, we consider a strategic communication game between an informed encoder and two decoders communicating via a Gray-Wyner network. All three agents are assumed to be rational and endowed with distinct objectives captured by non-aligned cost functions. The encoder selects and announces beforehand the compression scheme to be implemented. Then, it transmits three signals: a public signal, and a private signal to each decoder inducing a Bayesian game among the decoders. We are interested in designing an achievable coding scheme that minimizes the encoder’s long run cost function subject to the challenges imposed by the Gray-Wyner network.

Optimal design of distributed decision policies can be a difficult task, illustrated by the famous Witsenhausen counterexample. In this paper we characterize the optimal control designs for the vector-valued setting assuming that it results in an interim state, i.e. the result of the first decision maker action, that can be described by a continuous random variable which has a probability density function. More specifically, we provide a genie-aided outer bound that relies on our previous results for empirical coordination problems. This solution turns out to be not optimal in general, since it consists of a time-sharing strategy between two linear schemes of specific power. It follows that the optimal decision strategy for the original scalar Witsenhausen problem must lead to an interim state that cannot be described by a continuous random variable which has a probability density function.

The strategic communication problem consists of a joint source-channel coding problem in which the encoder and the decoder optimize two arbitrary distinct distortion functions. This problem lies on the bridge between Information Theory and Game Theory. As in the persuasion game of Kamenica and Gentzkow, we consider that the encoder commits to an encoding strategy, then the decoder selects the optimal output symbol based on its Bayesian posterior belief. The informational content of the source affects differently the two distinct distortion functions, therefore each symbol is encoded in a specific way. In this work, we consider that the decoder has side information. Accordingly, we reformulate the Bayesian update of the decoder posterior beliefs and the optimal information disclosure policy of the encoder. We provide four different expressions of the solution, in terms of the expected encoder distortion optimized under an information constraint, and it in terms of convex closures of auxiliary distortion functions. We compute the encoder optimal distortion for the doubly symmetric binary source example.

We study the multi-user Bayesian persuasion game between one encoder and two decoders, where the first decoder is better informed than the second decoder. We consider two perfect links, one to the first decoder only, and the other to both decoders. We consider that the encoder and both decoders are endowed with distinct and arbitrary distortion functions. We investigate the strategic source coding problem in which the encoder commits to an encoding while the decoders select the sequences of symbols that minimize their long-run respective distortion functions. We characterize the optimal encoder distortion value by considering successive refinement coding with respect to a specific probability distribution which involves two auxiliary random variables, and captures the incentive constraints of both decoders.

We revisit the problems of state masking and state amplification through the lens of empirical coordination. Specifically, we characterize the rate-equivocation-coordination trade-offs regions of a state-dependent channel in which the encoder has causal and strictly causal state knowledge. We also extend this characterization to the cases of two-sided state information and noisy channel feedback. Our approach is based on the notion of core of the receiver’s knowledge, which we introduce to capture what the decoder can infer about all the signals involved in the model. Finally, we exploit the aforementioned results to solve a channel state estimation zero-sum game in which the encoder prevents the decoder to estimate the channel state accurately.

We propose a new approach to construct optimal zero-error codes, based on the concatenation of words of variable length, taken from a generator set. Two zero-error variable-length coding algorithms, referred to as "variable-length coding" and "intermingled coding" are under study. We characterize their asymptotic performances via linear difference equations, in terms of simple properties of the generator set, e.g. the roots of the characteristic polynomial or the spectral radius of an adjacency matrix. For a specific example, we construct an "intermingled" coding scheme that achieves asymptotically the zero-error capacity of a specific channel graph.A full version of this paper is accessible on ArXiv at: https://arxiv.org/abs/2001.03523.

We investigate a strategic formulation of the joint source-channel coding problem in which the encoder and the decoder are endowed with distinct distortion functions. We provide the solutions in four different scenarios. First, we assume that the encoder and the decoder cooperate in order to achieve a certain pair of distortion values. Second, we suppose that the encoder commits to a strategy whereas the decoder implements a best response, as in the persuasion game where the encoder is the Stackelberg leader. Third, we consider that the decoder commits to a strategy, as in the mismatched rate-distortion problem or as in the mechanism design framework. Fourth, we study the cheap talk game in which the encoding and the decoding strategies form a Nash equilibrium.

We consider a network of two nodes separated by a noisy channel with two-sided state information, in which the input and output signals have to be coordinated with the source and its reconstruction. In the case of non-causal encoding and decoding, we propose a joint source-channel coding scheme and we develop inner and outer bounds for the strong coordination region. While the inner and outer bounds do not match in general, we provide a complete characterization of the strong coordination region in three particular cases: i) when the channel is perfect; ii) when the decoder is lossless; and iii) when the random variables of the channel are independent from the random variables of the source. Through the study of these special cases, we prove that the separation principle does not hold for the joint source-channel strong coordination. Finally, in the absence of state information, we show that polar codes achieve a subset of the best known inner bound for the strong coordination region, therefore offering a constructive alternative to random binning and coding proofs.

The vector-valued extension of the famous Witsenhausen counter-example setup is studied where the first decision maker (DM1) non-causally knows and encodes the iid state sequence and the second decision maker (DM2) causally estimates the interim state. The coding scheme is transferred from the finite alphabet coordination problem for which it is proved to be optimal. The extension to the Gaussian setup is based on a non-standard weak typicality approach and requires a careful average estimation error analysis since the interim state is estimated by the decoder. Next, we provide a choice of auxiliary random variables that outperforms any linear scheme. The optimal scheme remains unknown.

This paper investigates the incremental-redundancy hybrid-automatic repeat request (IR-HARQ) transmission over independent block-fading channels in the presence of an eavesdropper, where the secrecy of the transmission is ensured via introduction of dummy messages. Since the encoder only knows the statistics of the channel state, the secrecy and the reliability are defined in a probabilistic framework. Unlike previous works on this subject, we design a coding strategy tailored to IR-HARQ by splitting the dummy-message rate over several rate parameters. These additional degrees of freedom improve the match between the dummy-message rates and the realizations of the eavesdropper channels. We evaluate the performance in terms of secrecy outage probability, connection outage probability, and throughput and compare it with the benchmark paper by Tang et al. Numerical examples illustrate that, comparing to existing alternatives, splitting of the dummy-message rate provides higher throughput and lower expected duration/average delay.

We develop a random binning scheme for strong coordination in a network of two nodes separated by a noisy channel, in which the input and output signals have to be coordinated with the source and its reconstruction. In the case of non-causal encoding and decoding, we propose a joint source-channel coding scheme and develop inner and outer bounds for the strong coordination region. While the set of achievable target distributions is the same as for empirical coordination, we characterize the rate of common randomness required for strong coordination.

In this paper, we investigate a coding strategy devised to increase the throughput in hybrid ARQ (HARQ) transmission over a block fading channel. In our approach, the transmitter jointly encodes a variable number of bits for the each round of HARQ. The parameters (rates) of this joint coding can vary and may be based on the negative acknowledgment provided by the receiver or, on the past (outdated) information about the channel states. These new degrees of freedom allow us to improve the match between the codebook and the channel states experienced by the receiver. The results indicate that gains obtained using the proposed cross-packet coding strategy are particularly notable for the large values of the throughput. In this region, the conventional HARQ fails to offer throughput improvement even if the number of transmission rounds is increased. We implement the proposed cross-packet HARQ using turbo codes, where we show that the theoretically predicted throughput gains materialize in practice; the implementation challenges are also discussed.

In a decentralized and self-configuring network, the communication devices are considered as autonomous decision makers that sense their environment and that implement optimal transmission schemes. It is essential that these autonomous devices cooperate and coordinate their actions, to ensure the reliability of the transmissions and the stability of the network. We study a point-to-point scenario in which the encoder and the decoder implement decentralized policies that are coordinated. The coordination is measured in terms of empirical frequency of symbols of source and channel. The encoder and the decoder perform a coding scheme, such that the empirical distribution of the symbols is close to a target joint probability distribution. We characterize the set of achievable target probability distributions for a point-to-point source-channel model, in which the encoder is non-causal and the decoder is strictly causal, i.e., it returns an action based on the observation of the past channel outputs. The objectives of the encoder and of the decoder are captured by some utility function, evaluated with respect to the set of achievable target probability distributions. In this paper, we investigate the maximization problem of a utility function that is common to both encoder and decoder. We show that the compression and the transmission of information are particular cases of the empirical coordination.

We revisit the problem of state masking and state amplification for state-dependent channel with causal state information at the encoder from the point of view of empirical coordination. Empirical coordination, which requires all sequences of symbols to be jointly typical for a target joint probability distribution, provides a unified perspective to simultaneously study state masking, state amplification, and capacity-distortion trade-off. Our main result is a characterization of the set of achievable rates, information leakages and joint distributions. We also discuss several specializations and extensions of the result, including the cases of zero message rate, without empirical coordination, strictly causal encoding, two-sided state information and noisy channel feedback. We introduce the notion of “core of the decoder's knowledge,” to capture what the decoder can infer about all the signals involved in the model.

We develop a polar coding scheme for empirical coordination in a two-node network with a noisy link in which the input and output signals have to be coordinated with the source and the reconstruction. In the case of non-causal encoding and decoding, we show that polar codes achieve the best known inner bound for the empirical coordination region, provided that a vanishing rate of common randomness is available. This scheme provides a constructive alternative to random binning and coding proofs.

In this work, we propose and investigate a new coding strategy devised to increase the throughput of hybrid ARQ (HARQ) transmission over block fading channel. In our proposition, the transmitter jointly encodes a variable number of bits for each round of HARQ. The parameters (rates) of this joint coding can vary and may be based on the negative acknowledgment (NACK) signals provided by the receiver or, on the past (outdated) information about the channel states. The results indicate that significant gains can be obtained using the proposed coding strategy especially where the conventional HARQ fails to offer throughput improvement even if the number of transmission rounds is increased.

This paper studies secure communication based on incremental redundancy (INR) secure hybrid automatic retransmission request (HARQ) protocol over block-fading wiretap channels. The transmitter has no instantaneous channel state information (CSI) available from either main channel or the eavesdropper channel, hence the coding rates cannot be adapted to instantaneous channel conditions. We investigate the outage performance for two schemes of INR secure HARQ protocols: case 1) when there exists two reliable multibit feedback channels from both legitimate receiver and eavesdropper to the transmitter carrying a function of outdated CSI, and case 2) when there is a multibit feedback channel only from legitimate receiver. In both cases, we demonstrate that using the information carried via multibit feedback channels, the transmitter can adapt the coding rates in order to achieve a better secrecy throughput using a smaller number of transmissions comparing to the ACK/NACK feedback channel model. For some parameters, our rate adaptation protocol achieves a strictly positive secrecy throughput whereas it is equal to zero for the protocol with ACK/NACK feedback. We show that for some set of parameters, the loss of secrecy throughput between case 1 and case 2 is very small compared to the gain provided by both protocols.

The coordination of autonomous agents is a critical issue for decentralized communication networks. Instead of transmitting information, the agents interact in a coordinated manner in order to optimize a general objective function. A target joint probability distribution is achievable if there exists a code such that the sequences of symbols are jointly typical. The empirical coordination is strongly related to the joint source-channel coding with two-sided state information and correlated source and state. This problem is also connected to state communication and is open for non-causal encoder and decoder. We characterize the optimal solutions for perfect channel, for lossless decoding, for independent source and channel, for causal encoding and for causal decoding.

In multi-terminal networks, feedback increases the capacity region and helps communication devices to coordinate. In this article, we deepen the relationship between coordination and feedback by considering a point-to-point scenario with an information source and a noisy channel. Empirical coordination is achievable if the encoder and the decoder can implement sequences of symbols that are jointly typical for a target probability distribution. We investigate the impact of feedback when the encoder has strictly causal or causal observation of the source symbols. For both cases, we characterize the optimal information constraints and we show that feedback improves coordination possibilities. Surprisingly, feedback also reduces the number of auxiliary random variables and simplifies the information constraints. For empirical coordination with strictly causal encoding and feedback, the information constraint does not involve auxiliary random variable anymore.

Correlation between channel state and source symbol is under investigation for a joint source-channel coding problem. We investigate simultaneously the lossless transmission of information and the empirical coordination of channel inputs with the symbols of source and states. Empirical coordination is achievable if the sequences of source symbols, channel states, channel inputs and channel outputs are jointly typical for a target joint probability distribution. We characterize the joint distributions that are achievable under lossless decoding constraint. The performance of the coordination is evaluated by an objective function. For example, we determine the minimal distortion between symbols of source and channel inputs for lossless decoding. We show that the correlation source/channel state improves the feasibility of the transmission.

This paper is dedicated to the study of HARQ protocols under a secrecy constraint. An encoder sends information to a legitimate decoder while keeping it secret from the eavesdropper. Our objective is to provide a coding scheme that satisfies both reliability and confidentiality conditions. This problem has been investigated in the literature using a coding scheme that involves a unique secrecy parameter. The uniqueness of this parameter is sub-optimal for the throughput criteria and we propose a new coding scheme that introduces additional degrees of freedom. Our code involves Secrecy Adaptation and Rate Adaptation and we called it SARA-code. The first contribution is to prove that the SARA-code has small error probability and small information leakage rate. The second contribution is to show, over a numerical example, that the SARA-code improves the secrecy throughput.

Decentralized multiple access channels where each transmitter wants to selfishly maximize this transmission energy-efficiency are considered. Transmitters are assumed to choose freely their power control policy and interact (through multiuser interference) several times. It is shown that the corresponding conflict of interest can have a predictable outcome, namely a finitely or discounted repeated game equilibrium. Remarkably, it is shown that this equilibrium is Pareto-efficient under reasonable sufficient conditions and the corresponding decentralized power control policies can be implemented under realistic information assumptions: only individual channel state information and a public signal are required to implement the equilibrium strategies. Explicit equilibrium conditions are derived in terms of minimum number of game stages or maximum discount factor. Both analytical and simulation results are provided to compare the performance of the proposed power control policies with those already existing and exploiting the same information assumptions namely, those derived for the one-shot and Stackelberg games.