Adversarial Network Coding Ravagnani, Alberto; Kschischang, Frank R.
IEEE transactions on information theory,
2019-Jan., 2019-1-00, 20190101, Letnik:
65, Številka:
1
Journal Article
Recenzirano
Odprti dostop
A combinatorial framework for adversarial network coding is presented. Channels are described by specifying the possible actions that one or more (possibly coordinated) adversaries may take. Upper ...bounds on three notions of capacity-the one-shot capacity, the zero-error capacity, and the compound zero-error capacity-are obtained for point-to-point channels, and generalized to corresponding capacity regions appropriate for multi-source networks. A key result of this paper is a general method by which bounds on these capacities in point-to-point channels may be ported to networks. This technique is illustrated in detail for Hamming-type channels with multiple adversaries operating on specific coordinates, which correspond, in the context of networks, to multiple adversaries acting on specific network edges. Capacity-achieving coding schemes are described for some of the considered adversarial models.
Implications of information theory in optical fibre communications Agrell, Erik; Alvarado, Alex; Kschischang, Frank R.
Philosophical transactions of the Royal Society of London. Series A: Mathematical, physical, and engineering sciences,
03/2016, Letnik:
374, Številka:
2062
Journal Article
Recenzirano
Odprti dostop
Recent decades have witnessed steady improvements in our ability to harness the information-carrying capability of optical fibres. Will this process continue, or will progress eventually stall? ...Information theory predicts that all channels have a limited capacity depending on the available transmission resources, and thus it is inevitable that the pace of improvements will slow. However, information theory also provides insights into how transmission resources should, in principle, best be exploited, and thus may serve as a guide for where to look for better ways to squeeze more out of a precious resource. This tutorial paper reviews the basic concepts of information theory and their application in fibre-optic communications.
A conditionally Gaussian channel is a vector channel in which the channel output, given the channel input, has a Gaussian distribution with (well-behaved) input-dependent mean and covariance. We ...study the capacity-achieving probability measure for conditionally Gaussian channels subject to bounded-input constraints and average cost constraints. Many practical communication systems, including additive Gaussian noise channels, certain optical channels, fading channels, and interference channels fall within this framework. Subject to bounded-input constraint (and average cost constraints), we show that the channel capacity is achievable and we derive a necessary and sufficient condition for a probability measure to be capacity achieving. Under certain conditions, the capacity-achieving measure is proved to be discrete.
Locally repairable codes (LRCs) are considered with equal or unequal localities, local distances, and local field sizes. An explicit two-layer architecture with a sum-rank outer code is obtained, ...having disjoint local groups and achieving maximal recoverability (MR) for all families of local linear codes (MDS or not) simultaneously, up to a specified maximum locality <inline-formula> <tex-math notation="LaTeX">r </tex-math></inline-formula>. Furthermore, the local linear codes (thus the localities, local distances, and local fields) can be efficiently and dynamically modified without global recoding or changes in architecture or outer code, while preserving the MR property, easily adapting to new configurations in storage or new hot and cold data. In addition, local groups and file components can be added, removed or updated without global recoding. The construction requires global fields of size roughly <inline-formula> <tex-math notation="LaTeX">g^{r} </tex-math></inline-formula>, for <inline-formula> <tex-math notation="LaTeX">g </tex-math></inline-formula> local groups and maximum or specified locality <inline-formula> <tex-math notation="LaTeX">r </tex-math></inline-formula>. For equal localities, these global fields are smaller than those of previous MR-LRCs when <inline-formula> <tex-math notation="LaTeX">r \leq h </tex-math></inline-formula> (global parities). For unequal localities, they provide an exponential field size reduction on all previous best known MR-LRCs. For bounded localities and a large number of local groups, the global erasure-correction complexity of the given construction is comparable to that of Tamo-Barg codes or Reed-Solomon codes with local replication, while local repair is as efficient as for the Cartesian product of the local codes. Reed-Solomon codes with local replication and Cartesian products are recovered from the given construction when <inline-formula> <tex-math notation="LaTeX">r=1 </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">h = 0 </tex-math></inline-formula>, respectively. The given construction can also be adapted to provide hierarchical MR-LRCs for all types of hierarchies and parameters. Finally, subextension subcodes and sum-rank alternant codes are introduced to obtain further exponential field size reductions, at the expense of lower information rates.
A concatenated soft-decision forward error correction (FEC) scheme consisting of an inner low-density generatormatrix (LDGM) code and an outer staircase code is proposed. The soft-decision LDGM code ...is used for error reduction, while the majority of bit errors are corrected by the low-complexity harddecision staircase code. Decoding complexity of the concatenated code is quantified by a score based on the number of edges in the LDGM code Tanner graph, the number of decoding iterations, and the number of staircase code decoding operations. The inner LDGM ensemble is designed by solving an optimization problem, which minimizes the product of the average node degree and an estimate of the required number of decoding iterations. A search procedure is used to find the inner and outer code pair with lowest complexity. The design procedure results in a Pareto-frontier characterization of the tradeoff between net coding gain and complexity for the concatenated code. Simulations of code designs at 20% overhead showed that the proposed scheme achieves net coding gains equivalent to existing soft-decision FEC solutions, with up to 57% reduction in complexity.
Recent work by Zhang and Kschischang demonstrates how soliton amplitude estimation can be improved by using a nonlinear Fourier transform to separate the solitonic and non-solitonic components of a ...noisy soliton allowing for the exploitation of correlated noise. We follow up on this work providing simpler nonlinear amplitude estimation schemes which achieve the same performance at a significantly reduced computational cost.
The maximum likelihood detection rule for a four-dimensional direct-detection optical front-end is derived. The four dimensions are two intensities and two differential phases. Three different signal ...processing algorithms, composed of symbol-by-symbol, sequence, and successive detection, are discussed. To remedy dealing with special functions in the detection rules, an approximation for high signal-to-noise ratios (SNRs) is provided. Simulation results show that, despite the simpler structure of the successive algorithm, the resulting performance loss, in comparison with the other two algorithms, is negligible. For example, for an 8-ring/8-ary phase constellation, the complexity of detection reduces by a factor of 8, while the performance, in terms of the symbol error rate, degrades by 0.5 dB. It is shown that the high-SNR approximation is very accurate, even at low SNRs. The achievable rates for different constellations are computed and compared by the Monte Carlo method. For example, for a 4-ring/8-ary phase constellation, the achievable rate is 10 bits per channel use at an SNR of 25 dB, while by using an 8-ring/8-ary phase constellation and an error correcting code of rate 5/6, this rate is achieved at an SNR of 20 dB.
In this paper, the outage performance of wireless networks with unstructured topologies is investigated. The network reliability perspective of graph theory is used to obtain the network outage ...polynomial of generalized wireless networks for both uncorrelated and correlated wireless channels. A relationship is established between the max-flow min-cut theorem and key communication performance indicators. The diversity order is equal to the size of the minimum cut-set between source and destination, and the coding gain is the number of cut-sets with size equal to the minimum cut. An ergodic capacity analysis of arbitrary network topologies based on the network outage polynomial is also presented. Numerical results are used to illustrate the technical definitions and verify the derivations.
The capacity of the channel defined by the stochastic nonlinear Schrödinger equation, which includes the effects of the Kerr nonlinearity and amplified spontaneous emission noise, is considered in ...the case of zero dispersion. In the absence of dispersion, this channel behaves as a collection of parallel per-sample channels. The conditional probability density function of the nonlinear per-sample channels is derived using both a sum-product and a Fokker-Planck differential equation approach. It is shown that, for a fixed noise power, the per-sample capacity grows unboundedly with input signal. The channel can be partitioned into amplitude and phase subchannels, and it is shown that the contribution to the total capacity of the phase channel declines for large input powers. It is found that a 2-D distribution with a half-Gaussian profile on the amplitude and uniform phase provides a lower bound for the zero-dispersion optical fiber channel, which is simple and asymptotically capacity-achieving at high signal-to-noise ratios (SNRs). A lower bound on the capacity is also derived in the medium-SNR region. The exact capacity subject to peak and average power constraints is numerically quantified using dense multiple ring modulation formats. The differential model underlying the zero-dispersion channel is reduced to an algebraic model, which is more tractable for digital communication studies, and, in particular, it provides a relation between the zero-dispersion optical channel and a 2 × 2 multiple-input multiple-output Rician fading channel. It appears that the structure of the capacity-achieving input distribution resembles that of the Rician fading channel, i.e., it is discrete in amplitude with a finite number of mass points, while continuous and uniform in phase.