We consider the classical problem of discrete distribution estimation using i.i.d. samples in a novel scenario where additional side information is available on the distribution. In large alphabet datasets such as text corpora, such side information arises naturally through word semantics/similarities that can be inferred by closeness of vector word embeddings, for instance. We consider two specific models for side information--a local model where the unknown distribution is in the neighborhood of a known distribution, and a partial ordering model where the alphabet is partitioned into known higher and lower probability sets. In both models, we theoretically characterize the improvement in a suitable squared-error risk because of the available side information. Simulations over natural language and synthetic data illustrate these gains.

Given the ease of creating synthetic data from machine learning models, new models can be potentially trained on synthetic data generated by previous models. This recursive training process raises concerns about the long-term impact on model quality. As models are recursively trained on generated data from previous rounds, their ability to capture the nuances of the original human-generated data may degrade. This is often referred to as model collapse. In this work, we ask how fast model collapse occurs for some well-studied distribution families under maximum likelihood (ML or near ML) estimation during recursive training. Surprisingly, even for fundamental distributions such as discrete and Gaussian distributions, the exact rate of model collapse is unknown. In this work, we theoretically characterize the rate of collapse in these fundamental settings and complement it with experimental evaluations. Our results show that for discrete distributions, the time to forget a symbol is approximately linearly dependent on the number of times it occurred in the original corpus, and for Gaussian models, the standard deviation reduces to zero roughly at $n$ iterations, where $n$ is the number of samples at each iteration. Both of these findings imply that model forgetting, at least in these simple distributions under near ML estimation with many samples, takes a long time.

Learning a distribution from error-prone or non-ideal sampling modeled as “duplication” or “sticky” channels has been of interest recently inspired by applications such as DNA computing. Missing mass, the total probability of missing letters, is an important quantity that plays a crucial role in distribution estimation, specifically in the large alphabet setting. I$n$this work, we consider the problem of estimation of missing mass, which has been well-understood under independent and identically distributed (i.i.d) sampling, in the case when the samples involve duplications. Precisely, we consider the setting where each sample from an unknown distribution gets repeated a Bernoulli-distributed number of times creating a hidden Markov memory in the samples. We characterize the minimax rate of Mean Squared Error (MSE) of estimating missing mass from such elementary duplication sampling channels. An upper bound on the minimax rate is obtained by bounding the risk of a proposed estimator. We derive a matching lower bound by reduction to the i.i.d setting.

We study the problem of estimating the stationary mass---also called the unigram mass---that is missing from a single trajectory of a discrete-time, ergodic Markov chain. This problem has several applications---for example, estimating the stationary missing mass is critical for accurately smoothing probability estimates in sequence models. While the classical Good--Turing estimator from the 1950s has appealing properties for i.i.d. data, it is known to be biased in the Markovian setting, and other heuristic estimators do not come equipped with guarantees. Operating in the general setting in which the size of the state space may be much larger than the length $n$ of the trajectory, we develop a linear-runtime estimator called Windowed Good--Turing (WingIt) and show that its risk decays as $\widetilde{O}(\mathsf{T_{mix}}/n)$, where $\mathsf{T_{mix}}$ denotes the mixing time of the chain in total variation distance. Notably, this rate is independent of the size of the state space and minimax-optimal up to a logarithmic factor in $n / \mathsf{T_{mix}}$. We also present an upper bound on the variance of the missing mass random variable, which may be of independent interest. We extend our estimator to approximate the stationary mass placed on elements occurring with small frequency in the trajectory. Finally, we demonstrate the efficacy of our estimators both in simulations on canonical chains and on sequences constructed from natural language text.

We consider a queue-channel model that captures the waiting time-dependent degradation of information bits as they wait to be transmitted. Such a scenario arises naturally in quantum communications, where information bits become useless after a certain time. Trailing the capacity results obtained recently for certain queue-channels, this paper aims to construct practical channel codes for the erasure queue-channel (EQC)—a channel characterized by highly correlated erasures, governed by the underlying queuing dynamics. Our main contributions in this paper are twofold: (i) We propose a generic ‘wrapper’ based on interleaving across renewal blocks of the queue to convert any capacity-achieving code for a memoryless erasure channel to a capacity-achieving code for the EQC. Next, due to the complexity involved in implementing interleaved systems, (ii) we study the performance of LDPC and Polar codes without any interleaving. Motivated by the empirical performance, we show that standard Arıkan’s Polar transform polarizes the M/M/1 EQC.

Estimating the underlying distribution from iid samples is a classical and important problem in statistics. When the alphabet size is large compared to number of samples, a portion of the distribution is highly likely to be unobserved or sparsely observed. The missing mass, defined as the sum of probabilities$\Pr (x)$over the missing letters x, and the Good-Turing estimator for missing mass have been important tools in large-alphabet distribution estimation. In this article, given a positive function g from$[{0,1}]$to the reals, the missing g-mass, defined as the sum of$g(\Pr (x))$over the missing letters x, is introduced and studied. The missing g-mass can be used to investigate the structure of the missing part of the distribution. Specific applications for special cases such as order-$\alpha $missing mass ($g(p)=p^{\alpha }$) and the missing Shannon entropy ($g(p)=-p\log p$) include estimating distance from uniformity of the missing distribution and its partial estimation. Minimax estimation is studied for order-$\alpha $missing mass for integer values of$\alpha $and exact minimax convergence rates are obtained. Concentration is studied for a class of functions g and specific results are derived for order-$\alpha $missing mass and missing Shannon entropy. Sub-Gaussian tail bounds with near-optimal worst-case variance factors are derived. Two new notions of concentration, named strongly sub-Gamma and filtered sub-Gaussian concentration, are introduced and shown to result in right tail bounds that are better than those obtained from sub-Gaussian concentration.

We consider a queue-channel model that captures the waiting time-dependent degradation of information bits as they wait to be transmitted. Such a scenario arises naturally in quantum communications, where quantum bits tend to decohere rapidly. Trailing the capacity results obtained recently for certain queue-channels, this paper aims to construct practical channel codes for the erasure queue-channel (EQC)—a channel characterized by highly correlated erasures, governed by the underlying queuing dynamics. Our main contributions in this paper are twofold: (i) We propose a generic ‘wrapper’ based on interleaving across renewal blocks of the queue to convert any capacity-achieving block code for a memoryless erasure channel to a capacity-achieving code for the EQC. Next, due to the complexity involved in implementing interleaved systems, (ii) we study the performance of LDPC and Polar codes without any interleaving. We show that standard Arıkan’s Polar transform polarizes the EQC for certain restricted class of erasure probability functions. We also highlight some possible approaches and the corresponding challenges involved in proving the polarization of a general EQC.

Coded caching is a technique for achieving increased throughput in cached networks during peak hours. Placement delivery arrays (PDAs) capture both placement and delivery scheme requirements in coded caching in a single array. Lifting is a method of constructing PDAs, where entries in a small base PDA are replaced with constituent PDAs that satisfy a property called Blackburn-compatibility. We propose two new constructions for Blackburn-compatible PDAs including a novel method for lifting Blackburn-compatible PDAs to obtain new sets of Blackburn-compatible PDAs. Both of these constructions improve upon previous tradeoffs between rate, memory and subpacketization. We generalize lifting constructions by defining partial Blackburn-compatibility between two PDAs w.r.t. a third PDA. This is a wider notion of Blackburn-compatibility making the original definition a special case. We show that some popular coded caching schemes can be defined as lifting constructions in terms of this extended notion.

Distribution estimation under error-prone or non-ideal sampling modelled as "sticky" channels have been studied recently motivated by applications such as DNA computing. Missing mass, the sum of probabilities of missing letters, is an important quantity that plays a crucial role in distribution estimation, particularly in the large alphabet regime. In this work, we consider the problem of estimation of missing mass, which has been well-studied under independent and identically distributed (i.i.d) sampling, in the case when sampling is "sticky". Precisely, we consider the scenario where each sample from an unknown distribution gets repeated a geometrically-distributed number of times. We characterise the minimax rate of Mean Squared Error (MSE) of estimating missing mass from such sticky sampling channels. An upper bound on the minimax rate is obtained by bounding the risk of a modified Good-Turing estimator. We derive a matching lower bound on the minimax rate by extending the Le Cam method.

Coded caching is a technique where multicasting and coding opportunities are utilized to achieve better rate-memory tradeoff in cached networks. A crucial parameter in coded caching is subpacketization, which is the number of parts a file is to be split into for coding purposes. The Maddah-Ali-Niesen scheme has order-optimal rate, but the subpacketization is exponential in the number of users for certain memory regimes. In contrast, coded caching schemes designed using placement delivery arrays (PDAs) can have linear subpacketization with a penalty in rate. In this work, we propose several constructions of efficient PDAs through lifting, where a base PDA is expanded by replacing each entry by another PDA. By proposing and using the notion of Blackburn-compatibility of PDAs, we provide multiple lifting constructions with increasing coding gains. We compare the constructed coded caching schemes with other existing schemes for moderately high number of users and show that the proposed constructions are versatile and achieve a good rate-memory tradeoff at low subpacketizations.

Estimation of missing mass or the total probability of unseen letters in a random sample is an important problem with several applications. The Good-Turing (GT) estimator is one of the most popular estimators for missing mass. The bias of the GT estimator is known to fall inversely with the number of samples when they are independent and identically distributed. When the samples form a Markov chain, very little is known about the convergence of the GT estimator even though it is widely used for smoothing in language models that are mostly Markovian. In this work, we initiate and make progress towards characterizing bias of the GT estimator for missing mass in Markov chains. We develop a useful `multi-letter' characterization of the bias, which leads to sufficient conditions on the transition probability matrix for convergence of the bias of the GT estimator to zero.

Reed-Muller (RM) codes, a classical family of codes known for their elegant algebraic structure, have recently been shown to achieve capacity under maximum-likelihood (ML) decoding on the binary erasure channel and this has rekindled interest in their efficient decoding. We consider the code family RM(m-3,m) and develop a new ML decoder, for transmission over the binary symmetric channel, that exploits their large symmetry group. The new decoder has lower complexity than an earlier method introduced by Seroussi and Lempel in 1983.

The missing mass of a sequence is defined as the total probability of the elements that have not appeared or occurred in the sequence. Estimation of missing mass is an important ingredient in many practical applications in language modeling and ecology. Exponential tail bounds have been known for missing mass, and improving them results in better confidence in estimation. In this work, we improve upon the best-known left and right tail bounds for missing mass. For the left tail, our proof method is arguably simpler than prior methods and provides a better bound for small sample sizes. For the right tail, we provide a new bounding method for the moment generating function of a generalized version of missing mass that results in a noticeable improvement in the tail bound.

Support size estimation and the related problem of unseen species estimation have wide applications in ecology and database analysis. Perhaps the most used support size estimator is the Chao estimator. Despite its widespread use, little is known about its theoretical properties. We analyze the Chao estimator and show that its worst case mean squared error (MSE) is smaller than the MSE of the plug-in estimator by a factor of ${\mathcal{O}}\left( {{{\left( {k/n} \right)}^2}} \right)$. Our main technical contribution is a new method to analyze rational estimators for discrete distribution properties, which may be of independent interest.

The capacity of noisy channels with memory and finite input has been difficult to characterize explicitly in many cases. In this paper, we consider single-tap binary-input Gaussian channels with inter-symbol interference (ISI). The dual capacity method is used to obtain upper bounds using Markov test distributions. The bound, expressed as a single-letter optimization problem, is solved numerically. For higher memory, the notion of cycle basis is used to provide an exponential reduction in the computational complexity of the optimization problem. Bounds were obtained for the important case of the dicode channel, and these are better than the previously known upper bounds and are close to achievable rates over a wide range of SNRs.

The capacity of noisy channels with memory and finite input has been difficult to characterize explicitly in many cases. In this work, we consider two such channels - (1) binary-input Gaussian channels with Inter-Symbol Interference (ISI), and (2) a general Binary-Input Binary-Output (BIBO) channel with the runlength constraint of no repeated 1s at the input. The dual method is used to obtain tight upper bounds for both channels. For the ISI channel, the bound is expressed as an optimization problem that is solved numerically. For the BIBO channel, analytic expressions for upper bounds are obtained. In both cases, the derived new bounds are shown to improve upon previously known bounds.

The Learning with Errors (LWE) problem has been extensively studied in cryptography due to its strong hardness guarantees, efficiency and expressiveness in constructing advanced cryptographic primitives. In this work, we show that using polar codes in conjunction with LWE-based encryption yields several advantages. To begin, we demonstrate the obvious improvements in the efficiency or rate of information transmission in the LWE-based scheme by leveraging polar coding (with no change in the cryptographic security guarantee). Next, we integrate wiretap polar coding with LWE-based encryption to ensure provable semantic security over a wiretap channel in addition to cryptographic security based on the hardness of LWE. To the best of our knowledge this is the first wiretap code to have cryptographic security guarantees as well. Finally, we study the security of the private key used in LWE-based encryption with wiretap polar coding, and propose a key refresh method using random bits used in wiretap coding. Under a known-plaintext attack, we show that non-vanishing information-theoretic secrecy can be achieved for the key. We believe our approach is at least as interesting as our final results: our work combines cryptography and coding theory in a novel “non blackbox-way” which may be relevant to other scenarios as well.

Block-error threshold analysis of protographs in 5G standard are considered over binary erasure channel (BEC) and binary additive white Gaussian noise (BIAWGN) channel. For protographs with degree-one variable nodes, conditions are derived to ensure equality of bit-error threshold and block-error threshold. Using this condition, it is shown that block-error threshold and bit-error threshold for protographs in in 5G standard are the same. Protographs with block-error threshold close to capacity are designed and shown to have better error rate performance than the protographs in 5G standard.

Protograph low-density-parity-check (LDPC) codes are considered to design near-capacity low-rate codes over the binary erasure channel and the binary additive white Gaussian noise channel. For protographs with degree-one variable nodes and doubly-generalized LDPC (DGLDPC) codes, conditions are derived to ensure the equality of bit-error threshold and block-error threshold. Using this condition, low-rate codes with block-error threshold close to capacity are designed and shown to have better error rate performance than other existing codes.

The problem of estimating the missing mass or total probability of unseen elements in a sequence of n random samples is considered under the squared error loss function. The worst-case risk of the popular Good-Turing estimator is shown to be between 0.6080/n and 0.6179/n. The minimax risk is shown to be lower bounded by 0.25/n. This appears to be the first such published result on minimax risk for estimation of missing mass, which has several practical and theoretical applications.

We consider a large class of bidirectional relaying scenarios with physical layer network coding, and analytically characterize the relay's error performance in decoding the network-coded combination at high signal-to-noise ratio (SNR). Our analysis applies to scenarios with 1) binary or higher order real/complex modulation, 2) real or complex channel coefficients, and 3) linear or non-linear network maps for network coding at the relay. We consider block fading and allow the relay to choose from a set of network maps based on the channel coefficients of the source to relay links in every block. We derive expressions for pairwise error probability and approximate expected overall error probability. We also derive lower bounds for these error probabilities. We validate these expressions using simulations and show that our approximations are tight in the high SNR regime.

Binary-input memoryless channels with a run length constrained input are considered. Upper bounds to the capacity of such noisy run length constrained channels are derived using the dual capacity method with Markov test distributions satisfying the Karush-Kuhn-Tucker conditions for the capacity-achieving output distribution. Simplified algebraic characterizations of the bounds are presented for the binary erasure channel and the binary symmetric channel. These upper bounds are very close to achievable rates, and improve upon previously known feedback-based bounds for a large range of channel parameters. For the binary-input additive white Gaussian noise channel, the upper bound is simplified to a small-scale numerical optimization problem. These results provide some of the simplest upper bounds for an open capacity problem that has theoretical and practical relevance.

The capacity-achieving input distribution of the discrete-time, additive white Gaussian noise (AWGN) channel with an amplitude constraint is discrete and seems difficult to characterize explicitly. A dual capacity expression is used to derive analytic capacity upper bounds for scalar and vector AWGN channels. The scalar bound improves on McKellips' bound and is within 0.1 bit of capacity for all signal-to-noise ratios (SNRs). The 2-D bound is within 0.15 bits of capacity provably up to 4.5 dB; numerical evidence suggests a similar gap for all SNRs. As the SNR tends to infinity, these bounds are accurate and match with a volume-based lower bound. For the 2-D complex case, an analytic lower bound is derived by using a concentric constellation and is shown to be within 1 bit of capacity.

Protograph doubly-generalized low-density parity-check (DGLDPC) codes, which allow for arbitrary component codes at the variable and check nodes of a protograph, are considered. Exact density evolution is derived over the binary erasure channel. Conditions on the protograph and component codes to ensure equality of block-error threshold and density evolution threshold for large-girth ensembles are established. Conditions for stability of density evolution are derived, and block-error threshold property is extended to binary-input symmetric channels. Optimized low-rate protographs for DGLDPC codes over the erasure channel are presented.

The problem of three-party secure computation, where a function of private data of two parties is to be computed by a third party without revealing information beyond respective inputs or outputs is considered. New and better lower bounds on the amount of communication required between the parties to guarantee zero probability of error in the computation and achieve information-theoretic security are derived. Protocols are presented and proved to be optimal in some cases by showing that they achieve the improved lower bounds.

Binary-input memoryless channels with a runlength constrained input, where an input of one is necessarily followed by a fixed number of zeros, are considered. Computable upper bounds to the capacity of such noisy runlength constrained channels are derived using the dual capacity method. Simplified versions of the bounds are presented for the binary erasure channel (BEC) and the binary symmetric channel (BSC). These bounds improve upon previously known computable bounds and show that feedback strictly improves the capacity of the runlength constrained BEC and BSC for all parameters.

Density evolution for protograph low-density parity-check (LDPC) codes is considered, and it is shown that the message-error rate falls double-exponentially with iterations whenever the degree-2 subgraph of the protograph is cycle-free and noise level is below threshold. Conditions for stability of protograph density evolution are established and related to the structure of the protograph. Using large-girth graphs, sequences of protograph LDPC codes with block-error threshold equal to bit-error threshold and block-error rate falling near-exponentially with blocklength are constructed deterministically. Small-sized protographs are optimized to obtain thresholds near capacity for binary erasure and binary-input Gaussian channels.

We show that the maximum mutual information (capacity) of parallel Gaussian channels obtained by the optimal water-filling algorithm for power allocation under a sum-power constraint is submodular. For a given power allocation, mutual information is known to be submodular. However, establishing the submodularity of the capacity, which additionally involves maximization of the mutual information over the power allocation, is challenging. Capacity of parallel Gaussian channels is equivalent to the maximum log-utility function used in resource allocation problems. Using this correspondence and the submodularity of the capacity, we find provable guarantees on multiple combinatorial resource allocation problems in wireless networks. In particular, we show that greedy algorithms give a 2-approximation for uplink OFDMA power and subcarrier allocation, FDMA capacity, downlink base-station association, with honest as well as strategic users who may or may not report their channel gains truthfully.

Motivated by recent high bandwidth communication systems, Inter-Symbol Interference (ISI) channels with 1-bit quantized output are considered under an average-power-constrained continuous input. While the exact capacity is difficult to characterize, an approximation that matches with the exact channel output up to a probability of error is provided. The approximation does not have additive noise, but constrains the channel output (without noise) to be above a threshold in absolute value. The capacity under the approximation is computed using methods involving standard Gibbs distributions. Markovian achievable schemes approaching the approximate capacity are provided. The methods used over the approximate ISI channel result in ideas for practical coding schemes for ISI channels with 1-bit output quantization.

The capacity-achieving input distribution of the discrete-time additive white Gaussian noise (AWGN) channel with an amplitude constraint is discrete and seems difficult to characterize explicitly. A dual capacity expression is used to derive analytic capacity upper bounds for scalar and vector AWGN channels. The scalar bound improves on McKellips' bound and is within 0.1 bits of capacity for all signal-to-noise ratios (SNRs). The two-dimensional bound is within 0.15 bits of capacity provably up to 4.5 dB, and numerical evidence suggests a similar gap for all SNRs.

The renewed interest for physical-layer security techniques has put forward a new role for error-control codes. In addition to ensuring reliability, carefully designed codes have been shown to provide a level of information-theoretic secrecy, by which the amount of information leaked to an adversary may be controlled. The ability to achieve information-theoretic secrecy relies on the study of alternative coding mechanisms, such as channel resolvability and privacy amplification, in which error-control codes are exploited as a means to shape the distribution of stochastic processes. This use of error-control codes, which goes much beyond that of correcting errors, creates numerous new design challenges. The objective of this paper is threefold. First, the paper aims at providing system engineers with explicit tools to build simple secrecy codes in order to stimulate interest and foster their integration in communication system prototypes. Second, it aims at providing coding and information theorists with a synthetic overview of the theoretical concepts and techniques for secrecy. Finally, it aims at highlighting the open challenges and opportunities faced for the integration of these codes in practical systems.

We study the use of Low-Density Parity-Check (LDPC) codes for two-phase, network-coded bidirectional relaying with higher-order modulation. In the multiple-access phase, the sum of transmitted symbols scaled by the channel gains is the received relay constellation, which is network-mapped (clustered) to a transmit constellation for the ensuing broadcast phase. This operation at the relay is termed Clustered-Scaled-Sum (CSS) decoding. We propose a CSS coding scheme for bidirectional relaying using a single LDPC code over a ring with higher-order PAM or QAM alphabets. We design a message-passing decoder for CSS decoding with trade-offs possible between complexity and performance. We suggest a method for completing a Constrained Partially-filled Latin Square (CPLS) to a latin square, which is used in the construction of network maps at the relay for any channel fading state. The performance of the CSS coding scheme with LDPC codes over rings is shown to be very close to information-theoretic outer bounds.

We consider the basic bidirectional relaying problem, in which two users in a wireless network wish to exchange messages through an intermediate relay node. In the compute-and-forward strategy, the relay computes a function of the two messages using the naturally occurring sum of symbols simultaneously transmitted by user nodes in a Gaussian multiple-access channel (MAC), and the computed function value is forwarded to the user nodes in an ensuing broadcast phase. In this paper, we study the problem under an additional security constraint, which requires that each user's message be kept secure from the relay. We consider two types of security constraints: 1) perfect secrecy, in which the MAC channel output seen by the relay is independent of each user's message and 2) strong secrecy, which is a form of asymptotic independence. We propose a coding scheme based on nested lattices, the main feature of which is that given a pair of nested lattices that satisfy certain goodness properties, we can explicitly specify probability distributions for randomization at the encoders to achieve the desired security criteria. In particular, our coding scheme guarantees perfect or strong secrecy even in the absence of channel noise. The noise in the channel only affects reliability of computation at the relay, and for Gaussian noise, we derive achievable rates for reliable and secure computation. We also present an application of our methods to the multihop line network in which a source needs to transmit messages to a destination through a series of intermediate relays.

Wiretap channels form the most basic building block of physical-layer and information-theoretic security. Considerable research work has gone into the information-theoretic, cryptographic and coding aspects of wiretap channels in the last few years. The main goal of this tutorial article is to provide a self-contained presentation of two recent results - one is a new and simplified proof for secrecy capacity using channel resolvability, and the other is the connection between semantic security and information-theoretic strong secrecy.

Physical layer security protocols exploit inviolable physical laws at the signal level for providing guarantees on secrecy of communications. These protocols invariably involve randomized encoding at the transmitter, for which an ideal random number generator is typically assumed in the literature. In this work, we study the impact of using weak Pseudo Random Number Generators (PRNGs) in physical layer security protocols for coding and forward key distribution over Binary Symmetric and Gaussian wiretap channels. In the case of wiretap channel coding, we study fast correlation attacks that aim to retrieve the initial seed used in the PRNGs. Our results show that randomized coset encoding, which forms an important part of wiretap channel coding, provides useful robustness against fast correlation attacks. In the case of single-round or forward key distribution over a Gaussian wiretap channel, the bits from a PRNG are nonlinearly transformed to generate Gaussian-distributed pseudo random numbers at the transmitter. In such cases, we design modified versions of the fast correlation attacks accounting for the effects of the nonlinear transformation and soft input. We observe that, even for moderately high memory, the success probability of the modified fast correlation attacks become the same as that of a random guess in many cases.

Design of online algorithms for assigning mobile users to basestations is considered with the objective of maximizing the sum-rate, when all users associated to any one basestation equally share each basestation's resources. Each user on its arrival reveals the rates it can obtain if connected to each of the basestations, and the problem is to assign each user to any one basestation irrevocably and without delay so that the sum-rate is maximized at the end of all user arrivals. In online algorithms, at each user arrival, the rates of future users are assumed to be unknown, and no assumptions are made about their statistics. Online algorithms with constant factor loss in comparison to offline algorithms (that know both the user arrival and user rates profile in advance) are derived. The proposed online algorithms are motivated from the famous online k-secretary problem and online maximum weight matching problem.

For certain degree-distribution pairs with non-zero fraction of degree-two bit nodes, the bit-error threshold of the standard ensemble of Low Density Parity Check (LDPC) codes is known to be close to capacity. However, the degree-two bit nodes preclude the possibility of a block-error threshold. Interestingly, LDPC codes constructed using protographs allow the possibility of having both degree-two bit nodes and a block-error threshold. In this paper, we analyze density evolution for protograph LDPC codes over the binary erasure channel and show that their bit-error probability decreases double exponentially with the number of iterations when the erasure probability is below the bit-error threshold and long chain of degree-two variable nodes are avoided in the protograph. We present deterministic constructions of such protograph LDPC codes with girth logarithmic in blocklength, resulting in an exponential fall in bit-error probability below the threshold. We provide optimized protographs, whose block-error thresholds are better than that of the standard ensemble with minimum bit-node degree three. These protograph LDPC codes are theoretically of great interest, and have applications, for instance, in coding with strong secrecy over wiretap channels.

Regenerating codes for distributed storage systems promise significant improvements in the cost and maintenance requirements of large-scale data centers. Research in this area continues to define important new parameters and requirements that have the biggest impact in practice. One of the simplest requirements for a regenerating code is the so-called MSR property, which minimizes the number of bits downloaded during repair. Quasi-cyclic MSR codes are of particular interest, mainly for reducing the encoding and decoding complexity. However, quasi-cyclic MSR codes have not been studied in detail in the existing literature. In this work, we prove the negative result that quasi-cyclic MSR codes with no symbol extension do not exist if the number of systematic nodes is greater than or equal to 4. We provide several examples of quasi-cyclic near-MSR codes, which could be useful for reducing implementation complexity. We point out some interesting connections between zeros of quasi-cyclic codes and the MSR requirement, which are useful in the study of quasi-cyclic regenerating codes with symbol extension.

Bidirectional relaying, where a relay helps two user nodes to exchange equal length binary messages, has been an active area of recent research. A popular strategy involves a modified Gaussian MAC, where the relay decodes the XOR of the two messages using the naturally-occurring sum of symbols simultaneously transmitted by user nodes. In this work, we consider the Gaussian MAC in bidirectional relaying with an additional secrecy constraint for protection against a honest but curious relay. The constraint is that, while the relay should decode the XOR, it should be fully ignorant of the individual messages of the users. We exploit the symbol addition that occurs in a Gaussian MAC to design explicit strategies that achieve perfect independence between the received symbols and individual transmitted messages. Our results actually hold for a more general scenario where the messages at the two user nodes come from a finite Abelian group G, and the relay must decode the sum within G of the two messages. We provide a lattice coding strategy and study optimal rate versus average power trade-offs for asymptotically large dimensions.

We propose a multihopping decode and forward relaying protocol for two-stage Gaussian relay networks with half-duplex nodes. We analytically show that the achievable rates in suitably defined strong and weak interference regimes are close to the cut-set bound.

The constraint complexity of a graphical realization of a linear code is the maximum dimension of the local constraint codes in the realization. The treewidth of a linear code is the least constraint complexity of any of its cycle-free graphical realizations. This notion provides a useful parameterization of the maximum-likelihood decoding complexity for linear codes. In this paper, we show the surprising fact that for maximum distance separable codes and Reed-Muller codes, treewidth equals trelliswidth, which, for a code, is defined to be the least constraint complexity (or branch complexity) of any of its trellis realizations. From this, we obtain exact expressions for the treewidth of these codes, which constitute the only known explicit expressions for the treewidth of algebraic codes.

The treewidth of a linear code is the least constraint complexity of any of its cycle-free graphical realizations. This notion provides a useful parametrization of the maximum-likelihood decoding complexity for linear codes. In this paper, we compute exact expressions for the treewidth of maximum distance separable codes, and first- and second-order Reed-Muller codes. These results constitute the only known explicit expressions for the treewidth of algebraic codes.

In a distributed storage system, codes for efficient repair of failed nodes has attracted significant recent research attention. Ideas from network coding and interference alignment have been used successfully to show bounds and construct coding schemes for efficient repair. In this article, we use ideas from classical algebraic codes to interpret the requirements of efficient repair as existence of certain specific types of codewords in the dual code. Since the construction is quasicyclic and works over small fields, it appears to be a promising method for reducing the computational complexity of efficient repair codes.

For an arbitrary degree distribution pair (DDP), we construct a sequence of low-density parity-check (LDPC) code ensembles with girth growing logarithmically in block-length using Ramanujan graphs. When the DDP has minimum left degree at least three, we show using density evolution analysis that the expected bit-error probability of these ensembles, when passed through a binary erasure channel with erasure probability ϵ, decays asO(exp(-(c1)n(c2))) with the block-lengthnfor positive constantsc1andc2, as long as ϵ is less than the erasure threshold ϵthof the DDP. This guarantees that the coset coding scheme using the dual sequence provides strong secrecy over the binary erasure wiretap channel for erasure probabilities greater than 1-ϵth.

The Hopper-Blum (HB) protocol, which uses noised linear parities of a shared key for authentication, has been proposed for light-weight applications such as RFID. Recently, algorithms for decoding linear codes have been specially designed for use in passive attacks on the HB protocol. These linear coding attacks have resulted in the need for long keys in the HB protocol, making the protocol too complex for RFID in some cases. In this work, we propose the NLHB protocol, which is a non-linear variant of the HB protocol. The non-linearity is such that passive attacks on the NLHB protocol continue to be provably hard by reduction. However, the linear coding attacks cannot be directly adapted to the proposed NLHB protocol because of the non-linearity. Hence, smaller key sizes appear to be sufficient in the NLHB protocol for the same level of security as the HB protocol. We construct specific instances of the NLHB protocol and show that they can be significantly less complex for implementation than the HB protocol, in spite of the non-linearity. Further, we propose an extension, called the NLHB+ protocol, that is provably secure against a class of active attack models.

Dirty paper coding (DPC) refers to methods for pre-subtraction of known interference at the transmitter of a multiuser communication system. There are numerous applications for DPC, including coding for broadcast channels. Recently, lattice-based coding techniques have provided several designs for DPC. In lattice-based DPC, there are two codes - a convolutional code that defines a lattice used for shaping and an error correction code used for channel coding. Several specific designs have been reported in the recent literature using convolutional and graph-based codes for capacity-approaching shaping and coding gains. In most of the reported designs, either the encoder works on a joint trellis of shaping and channel codes or the decoder requires iterations between the shaping and channel decoders. This results in high complexity of implementation. In this work, we present a lattice-based DPC scheme that provides good shaping and coding gains with moderate complexity at both the encoder and the decoder. We use a convolutional code for sign-bit shaping, and a low-density parity check (LDPC) code for channel coding. The crucial idea is the introduction of a one-codeword delay and careful parsing of the bits at the transmitter, which enables an LDPC decoder to be run first at the receiver. This provides gains without the need for iterations between the shaping and channel decoders. Simulation results confirm that at high rates the proposed DPC method performs close to capacity with moderate complexity. As an application of the proposed DPC method, we show a design for superposition coding that provides rates better than time-sharing over a Gaussian broadcast channel.

We show that duals of certain low-density parity-check (LDPC) codes, when used in a standard coset coding scheme, provide strong secrecy over the binary erasure wiretap channel (BEWC). This result hinges on a stopping set analysis of ensembles of LDPC codes with block length n and girth ≥ 2k for some k ≥ 2. We show that if the minimum left degree of the ensemble is lmin, the expected probability of block error is O(1/n⌈lmink/2⌉ -k) when the erasure probability ϵef, where ϵefdepends on the degree distribution of the ensemble. As long as lminand k > 2, the dual of this LDPC code provides strong secrecy over a BEWC of erasure probability greater than 1-ϵef.

In the algebraic view, the solution to a network coding problem is seen as a variety specified by a system of polynomial equations typically derived by using edge-to-edge gains as variables. The output from each sink is equated to its demand to obtain polynomial equations. In this paper, we propose a method to derive the polynomial equations using source-to-sink path gains as the variables. In the path gain formulation, we show that linear and quadratic equations suffice; therefore, network coding becomes equivalent to a system of polynomial equations of maximum degree 2. We present algorithms for generating the equations in the path gains and for converting path gain solutions to edge-to-edge gain solutions. Because of the low degree, simplification is readily possible for the system of equations obtained using path gains. Using small-sized network coding problems, we show that the path gain approach results in simpler equations and determines solvability of the problem in certain cases. On a larger network (with 87 nodes and 161 edges), we show how the path gain approach continues to provide deterministic solutions to some network coding problems.

Algebraic criteria for existence of scalar linear network codes to satisfy a set of connection requirements has been discussed extensively by Koetter and Meacutedard. Solving for a network code is now known to be equivalent to solving a system of polynomial equations obtained by assigning variables to edges in the line graph of the network and computing a suitable transfer function. An alternative formulation for arriving at an equivalent system of polynomial equations is given in this paper based on the decomposition of the original network into trees, which we call ldquoinformation flow treesrdquo. The basic idea is to exploit the graph structure and assign variables suitably. Interestingly, the information flow tree approach results in only linear and degree-2 equations that can be simplified considerably in directed acyclic networks as shown in prior work. In this article, we provide an alternative derivation of the information flow tree approach that results in two further extensions to networks with cycles. The first extension is to flow acyclic solutions on any directed cyclic network. The second extension is to cyclic networks where all strongly connected components are simple cycles. Here the degree of the equations we are left to solve is limited to 4.

We prove that the Arimoto-Blahut like algorithm provided by Yasui et al [6] to solve for the Secrecy Capacity of a less-noisy Discrete Memoryless Channel (DMC) pair can be extended to a more-capable DMC pair subject to the availability of a suitable initial guess. In particular, we show that if a cut parallel to the input hyperplane removes a convex piece from the graph of the multi-input function f(q)=I(X;Y) - I(X; Z)rfloorq(x), where q is the input probablity distribution, then for any initial guess chosen within that convex piece, Yasui's algorithm will converge to the optimal value in that convex piece. We then introduce a new characterization called quasiconcavity of a DMC pair and show that it lies between the less-noisy and more-capable characterizations. We also show that in the binary case, quasiconcavity is equivalent to the more-capable characterization. We then show that we can choose from a wider range of initial guesses by looking at regions around the optimal point where the function is quasiconcave. Finally we establish that the algorithm of Yasui et al can be used for more-capable channel pairs with binary alphabets.

The performance of iterative decoding of low density parity check (LDPC) codes over binary erasure channels can be completely characterized by the study of stopping sets. Therefore, the burst erasure correction capability of a given LDPC code can be readily quantified by searching for stopping sets within consecutive bit nodes. In this work we study the optimal permutation of the bit nodes that will result in the maximum possible burst erasure correction capability for a given LDPC code. Noting that this is essentially a combinatorial optimization problem that is highly likely to be NP-hard, we adopt a simulated annealing based approach for finding the optimal permutation. We present bounds based on stopping sets that limit the burst erasure correction capability. As part of our results, we provide interleavers that greatly improve the burst erasure correction capability of protograph quasi-cyclic LDPC codes used in the WiMax standard.

We extend the broadcast channel with confidential messages to the situation where the receiver of the secret message also serves as a relay. We analyze the fundamental cooperation versus secrecy trade-offs for discrete memoryless channels and obtain the exact rate-equivocation region in this case. For the Gaussian channel, we consider various strategies leading to different levels of secrecy. Our study highlights the fundamental role of jamming as a means to increase secrecy rates, but also emphasizes the importance of carefully designed relaying strategies.

A code over GF(qm) can be imaged or expanded into a code over GF(q) using a basis for the extension field over the base field. In this work, a generalized version of the problem of self-orthogonality of the q-ary image of a qm-ary code has been considered. Given an inner product (more generally, a biadditive form), necessary and sufficient conditions have been derived for a code over a field extension and an expansion basis so that an image of that code is self-orthogonal. The conditions require that the original code be self-orthogonal with respect to several related biadditive forms whenever certain power sums of the dual basis elements do not vanish. The conditions are particularly simple to state and apply for cyclic codes. As a possible application, new quantum error-correcting codes have been constructed with larger minimum distance than previously known.

It is well-known that a Gaussian source distribution is required for maximum information transfer across a Gaussian channel. In a coded modulation system an equiprobable symbol constellation loses at most 1.53 dB when compared to a Gaussian source. To bridge this shaping gap, a code can be used to make the source distribution more Gaussian over an expanded constellation that results in lower average transmitted energy. Trellis shaping uses convolutional codes and the Viterbi algorithm for minimizing the transmitted energy. In this work, we propose trellis shaping using low-density parity-check codes as the shaping codes. We show that the 2-state min-sum algorithm over the Tanner graph can be used to efficiently implement the energy minimization. This is a more than 4-fold decrease in complexity over 4-state convolutional code-based trellis shaping. Using one of our simple shaping codes, we have observed a shaping gain of up to 0.65 dB (with CER = 1.26; PAPR = 3.86) (as compared with CER=1.41 and PAPR=3.3 for convolutional-code based trellis shaping with similar shaping gain). This encouraging result indicates that more complex LDPC-based approaches will do even better. We also present simulation results to show that constellation shaping provides similar gains over wireless channels under slow fading conditions.

In this paper, we present rate-compatible systematic repeat-accumulate (RA) codes for the additive white Gaussian noise (AWGN) channel. The systematic form is used because of the higher degree parity checks we require in the code. We show that very high code rates can be attained with good performance through our puncturing schemes. Although RA codes are very simple in terms of complexity compared to other codes such as turbo codes or low density parity check (LDPC) codes, the performance of these codes is quite competitive. Codes with rates up to 9/10 are obtained from a single rate 1/3 systematic regular RA code. Performance results show that our puncturing provides superior performance at high code rates compared to just puncturing parity bits.

A code over GF can be imaged or expanded into a code over GF using a basis for the extension field over the base field. The properties of such an image depend on the original code and the basis chosen for imaging. Problems relating the properties of a code and its image with respect to a basis have been of great interest in the field of coding theory. In this work, a generalized version of the problem of self-orthogonality of the q-ary image of a qm-ary code has been considered. Given an inner product (more generally, a bi-additive form), necessary and sufficient conditions have been derived for a code over a field extension and an expansion basis so that an image of that code is self-orthogonal. The conditions require that the original code be self-orthogonal with respect to several related bi-additive forms whenever certain power sums of the dual basis elements do not vanish. Numerous interesting corollaries have been derived by specializing the general conditions. An interesting result for the canonical or regular inner product in fields of characteristic two is that only self-orthogonal codes result in self-orthogonal images. Another result is that image of a code is self-orthogonal for all bases if and only if trace of the code is self-orthogonal, except for the case of binary images of 4-ary codes. The conditions are particularly simple to state and apply for cyclic codes. To illustrate a possible application, new quantum error-correcting codes have been constructed with larger minimum distance than previously known.

With the advent of quantum key distribution (QKD) systems, perfect (i.e., information-theoretic) security can now be achieved for distribution of a cryptographic key. QKD systems and similar protocols use classical error-correcting codes for both error correction (for the honest parties to correct errors) and privacy amplification (to make an eavesdropper fully ignorant). From a coding perspective, a good model that corresponds to such a setting is the wire tap channel introduced by Wyner in 1975. In this correspondence, we study fundamental limits and coding methods for wire tap channels. We provide an alternative view of the proof for secrecy capacity of wire tap channels and show how capacity achieving codes can be used to achieve the secrecy capacity for any wiretap channel. We also consider binary erasure channel and binary symmetric channel special cases for the wiretap channel and propose specific practical codes. In some cases our designs achieve the secrecy capacity and in others the codes provide security at rates below secrecy capacity. For the special case of a noiseless main channel and binary erasure channel, we consider encoder and decoder design for codes achieving secrecy on the wiretap channel; we show that it is possible to construct linear-time decodable secrecy codes based on low-density parity-check (LDPC) codes that achieve secrecy.

This paper investigates a practical secret key agreement protocol over the Gaussian wire-tap channel. The protocol is based on an efficient information reconciliation method which allows two parties having access to correlated continuous random variables to agree on a common bit string. We describe an explicit reconciliation method based on LDPC codes optimized with EXIT charts and density evolution. When used in conjunction with existing privacy amplification techniques our method allows secret key agreement over the Gaussian wire-tap channel close to the secrecy capacity

Soft decision decoding of block codes has traditionally and in recent times been a problem of great research interest. Though several sub-optimal soft decoders are becoming increasingly popular today, optimal soft decoders such as bitwise maximum a posteriori (MAP) decoders are of great value both for theoretical and practical purposes. In this work, we present a simple implementation of the MAP decoder for binary cyclic codes. The implementation is particularly easy and efficient for codes whose check polynomial is either an irreducible polynomial or a product of two irreducible polynomials. We illustrate the efficiency of the method by simulating the MAP decoder for the length 255 2-error-correcting binary BCH code. We also propose a suboptimal soft decision decoder based on the MAP decoder and present comparisons

We propose a new information reconciliation method which allows two parties sharing continuous random variables to agree on a common bit string. We show that existing coded modulation techniques can be adapted for reconciliation and give an explicit code construction based on LDPC codes in the case of Gaussian variables. Simulations show that our method achieves higher efficiency than previously reported results.

We investigate the use of capacity and near-capacity achieving LDPC codes on the wire tap channel, where the dual conditions of reliable communications and security are required. We show that good codes for conventional channels (like BSC and BEC) also have interesting and useful security properties. In this paper we show the connection between the decoding threshold of the code and its security against eavesdropping. We also give practical code constructions for some special cases of the wire tap channel and show that security (in the Shannon sense) is a function of the decoding threshold. Some of these constructions achieve the secrecy capacity as defined by Wyner. These codes provide secure communications without conventional key distribution and provide a physical-layer approach for either secure communications or key distribution

Soft-decision decoding of algebraic codes has been an area of active research interest for a long time. In this paper, we present sub-optimal, soft decoders for extended binary BCH codes and certain subcodes of extended RS codes. Our proposed decoders consist of a soft-information processing block followed by a traditional, hard-decision, bounded-distance decoder for the underlying BCH or RS codes. The soft-processor in both cases consists of SISO decoders for extended Hamming codes, which can be implemented with low complexity. The coding gains obtained are comparable with other soft decoders proposed in the literature

We provide a construction for quantum codes (Hermitian-self-orthogonal codes over GF(4)) starting from cyclic codes over GF(4/sup m/). We also provide examples of these codes some of which meet the known bounds for quantum codes.