We study reliable communication over finite-state channels (FSCs) using Reed--Muller (RM) codes. Building on recent symmetry-based analyses for memoryless channels, we show that a sequence of binary RM codes (with some random scrambling) can achieve the symmetric capacity (or uniform-input information rate) of a binary-input indecomposable FSC. Our approach has three components. First, we establish a capacity-via-symmetry theorem for doubly-transitive group codes on discrete memoryless channels (DMCs) with non-binary inputs, under some symmetry and puncturing conditions. Then, we reduce a binary-input FSC to an almost memoryless non-binary channel by grouping adjacent input bits into blocks and interleaving non-binary codes onto the channel. Finally, we show that the interleaved non-binary codes can be constructed from a single binary RM code.

We study the problem of estimating the mutation rate between two sequences from noisy sequencing reads. Existing alignment-free methods typically assume direct access to the full sequences. We extend these methods to the sequencing framework, where only noisy reads from the sequences are observed. We use a simple model in which both mutations and sequencing errors are substitutions. We propose multiple estimators, provide theoretical guarantees for one of them, and evaluate the others through simulations.

We study recoverable systems on the 2D lattice using tools from statistical mechanics. For a particular recovery rule that we consider as an example, we compute lower and upper bounds on the topological entropy of the system (the case of zero temperature). We also show that at low positive temperature, typical configurations are local perturbations of the ground states. For the case of high temperature, we show uniqueness of the Gibbs measure and find the mixing rate of Glauber dynamics for the system in a finite domain.

The repeat content and heterozygosity rate of a target genome are important factors in determining the feasibility of achieving a complete telomere-to-telomere assembly. The mathematical relationship between the required coverage and read length for the purpose of unique reconstruction remains unexplored for diploid genomes. We investigate the information-theoretic conditions that the given set of sequencing reads must satisfy to achieve the complete reconstruction of the true sequence of a diploid genome up to switch errors. We also analyze the standard greedy and de-Bruijn graph-based assembly algorithms. Our results show that the coverage and read length requirements of the assembly algorithms are considerably higher than the lower bound because both algorithms require the double repeats in the genome to be bridged. Finally, we derive necessary conditions for the overlap graph-based assembly paradigm.

This paper develops an algorithmic approach for obtaining estimates of the weight enumerators of Reed-Muller (RM) codes. Our algorithm is based on a technique for estimating the partition functions of spin systems, which in turn employs a sampler that produces codewords according to a suitably defined Gibbs distribution. We apply our method to moderate-blocklength RM RM) codes. Our algorithm is based on a technique for estimating the partition functions of spin systems, which in turn employs a sampler that produces codewords according to a suitably defined Gibbs distribution. We apply our method to moderate-blocklength RM codes and derive approximate values of their weight enumerators. We observe that the rates of the weight enumerator estimates returned by our method are close to the true rates when these rates are either known or computable by brute-force search; in other cases, our computations provide provably robust estimates. As a by-product, our sampling algorithm also allows us to put together the weight spectrum, i.e., the weights at which the enumerators are non-zero, of an RM code, by providing witnesses in the form of codewords at each weight in the spectrum. We illustrate our method by providing estimates of the hitherto unknown weight enumerators of the RM(11, 5) code for weights that are multiples of 4 between 512 and 1024. We also obtain the exact weight spectrum of the RM(10, 4) code.

This paper develops an algorithmic approach for obtaining estimates of the weight enumerators of Reed-Muller (RM) codes. Our algorithm is based on a technique for estimating the partition functions of spin systems, which in turn employs a sampler that produces codewords according to a suitably defined Gibbs distribution. We apply our method to moderate-blocklength RM codes and derive approximate values of their weight enumerators. We observe that the rates of the weight enumerator estimates returned by our method are close to the true rates when these rates are either known or computable by brute-force search; in other cases, our computations provide provably robust estimates. As a byproduct, our sampling algorithm also allows us to obtain estimates of the weight spectra of RM codes. We illustrate our methods by providing estimates of the hitherto unknown weight enumerators of the RM(11,5) code and the exact weight spectra of the RM(10, 3) and RM(10, 4) codes.

We investigate the information-theoretic conditions to achieve the complete reconstruction of a diploid genome. We also analyze the standard greedy and de-Bruijn graph-based algorithms and compare the coverage depth and read length requirements with the information-theoretic lower bound. Our results show that the gap between the two is considerable because both algorithms require the double repeats in the genome to be bridged.

A weakly constrained code is a collection of finite-length strings over a finite alphabet in which certain substrings or patterns occur according to some prescribed frequencies. Buzaglo and Siegel (ITW 2017) gave a construction of weakly constrained codes based on row-by-row coding, that achieved the capacity of the weak constraint. In this paper, we propose a method to make this row-by-row coding scheme resilient to errors.

The permanent of a non-negative square matrix can be well approximated by finding the minimum of the Bethe free energy function associated with some suitably defined factor graph; the resulting approximation to the permanent is called the Bethe permanent. Vontobel gave a combinatorial characterization of the Bethe permanent via degree-MBethe permanents, which is based on degree-Mcovers of the underlying factor graph. In this paper, we prove a degree-M-Bethe-permanent-based lower bound on the permanent of a non-negative matrix, which solves a conjecture proposed by Vontobel in [IEEE Trans. Inf. Theory, Mar. 2013]. We also prove a degree-M-Bethe-permanent-based upper bound on the permanent of a non-negative matrix. In the limitM→ ∞, these lower and upper bounds yield known Bethe-permanent-based lower and upper bounds on the permanent of a non-negative matrix. Moreover, we prove similar results for an approximation to the permanent known as the (scaled) Sinkhorn permanent.

In this paper, we present numerical upper bounds on the sizes of constrained codes with a prescribed minimum distance. We accomplish this by extending Delsarte's linear program (LP) (Delsarte (1973)) to the setting of constrained codes, with the value of optimal solutions to this LP giving us the desired upper bound, for a fixed constraint. We also describe an equivalent LP, with fewer variables and LP constraints, obtained by symmetrizing our LP. We observe that for different constraints of interest, our upper bounds beat the generalized sphere packing upper bounds of Fazeli, Vardy, and Yaakobi (2015).

In this paper, we consider the problem of computing the sizes of subcodes of binary linear codes, all of whose codewords need to satisfy an additional property, which we call a constraint. Using a simple identity from the Fourier analysis of Boolean functions, we transform our counting problem into a question about the structure of the dual code. We illustrate the utility of our method in providing explicit values or numerical algorithms for our counting problem, from the somewhat surprising observation that for different constraints of interest, the Fourier transform of the indicator function of the constraint is efficiently computable.

The paper considers coding schemes derived from Reed-Muller (RM) codes, for transmission over input-constrained memoryless channels. Our focus is on the$(d,\infty)$-runlength limited (RLL) constraint, which mandates that any pair of successive 1s be separated by at least$d~0\text{s}$. In our study, we first consider$(d,\infty)$-RLL subcodes of RM codes, taking the coordinates of the RM codes to be in the standard lexicographic ordering. We show, via a simple construction, that RM codes of rate$R$have linear$(d,\infty)$-RLL subcodes of rate$R\cdot {2^{-\left \lceil{ \log _{2}(d+1)}\right \rceil }}$. We then show that our construction is essentially rate-optimal, by deriving an upper bound on the rates of linear$(d,\infty)$-RLL subcodes of RM codes of rate$R$. Next, for the special case when$d=1$, we prove the existence of potentially non-linear$(1,\infty)$-RLL subcodes that achieve a rate of$\max \left ({0,R-\frac {3}8}\right)$. This, for$R > 3/4$, beats the$R/2$rate obtainable from linear subcodes. We further derive upper bounds on the rates of$(1,\infty)$-RLL subcodes, not necessarily linear, of a certain canonical sequence of RM codes of rate$R$. We then shift our attention to settings where the coordinates of the RM code are not ordered according to the lexicographic ordering, and derive rate upper bounds for linear$(d,\infty)$-RLL subcodes in these cases as well. Finally, we present a new two-stage constrained coding scheme, again using RM codes of rate$R$, which outperforms any linear coding scheme using$(d,\infty)$-RLL subcodes, for values of$R$close to 1.

In this paper, we explore the connection between secret key agreement and secure omniscience within the setting of the multiterminal source model with an eavesdropper having side information. While the secret key agreement problem considers the generation of a maximum-rate secret key through public discussion, the secure omniscience problem is concerned with communication protocols for omniscience that minimize the rate of information leakage to the eavesdropper. The starting point of our work is a lower bound on the minimum leakage rate for omniscience,$R_{ \text {L}}$, in terms of the wiretap secret key capacity,$C_{ \text {W}}$. Our interest is in identifying broad classes of sources for which this lower bound is met with equality, in which case we say that there is a duality between secure omniscience and secret key agreement. We show that this duality holds in the case of certain finite linear source (FLS) models, such as two-terminal FLS models and pairwise independent network models on trees with a linear eavesdropper. Duality also holds for any FLS model in which$C_{ \text {W}}$is achieved by a perfect linear secret key agreement scheme. We conjecture that the duality in fact holds unconditionally for any FLS model. On the negative side, we give an example of a (non-FLS) source model for which duality does not hold if we limit ourselves to communication-for-omniscience protocols with at most two (interactive) communications. We also address the secure function computation problem and explore the connection between the minimum leakage rate for computing a function and the wiretap secret key capacity.

In this paper, we propose a strategy for making DNA-based data storage information-theoretically secure through the use of wiretap channel coding. This motivates us to extend the shuffling-sampling channel model of Shomorony and Heckel (2021) to include a wiretapper. Our main result is a characterization of the secure storage capacity of our DNA wiretap channel model, which is the maximum rate at which data can be stored within a pool of DNA molecules so as to be reliably retrieved by an authorized party (Bob), while ensuring that an unauthorized party (Eve) gets almost no information from her observations. Furthermore, our proof of achievability shows that index-based wiretap channel coding schemes are optimal.

This paper considers the input-constrained binary memoryless symmetric (BMS) channel, without feedback. The channel input sequence respects the (d, ∞)-runlength limited (RLL) constraint, which mandates that any pair of successive 1s be separated by at least d 0s. We consider the problem of designing explicit codes for such channels. In particular, we work with the Reed-Muller (RM) family of codes, which were shown by Reeves and Pfister (2021) to achieve the capacity of any unconstrained BMS channel, under bit-MAP decoding. We show that it is possible to pick (d, ∞)-RLL subcodes of a capacity-achieving (over the unconstrained BMS channel) sequence of RM codes such that the subcodes achieve, under bit-MAP decoding, rates of $C \cdot {2^{ - \left\lceil {{{\log }_2}(d + 1)} \right\rceil }}$, where C is the capacity of the BMS channel. Finally, we also introduce techniques for upper bounding the rate of any (1, ∞)-RLL subcode of a specific capacity-achieving sequence of RM codes.

In this paper, we provide a framework for constructing entanglement-assisted quantum error-correcting codes (EAQECCs) from classical additive codes over a finite commutative local Frobenius ring. We give a formula for the minimum number of entanglement qudits required to construct an EAQECC from an additive code over a finite Galois ring. This significantly extends known results for EAQECCs over finite fields.

In this paper, we propose a strategy for making DNA-based data storage information-theoretically secure through the use of wiretap channel coding. This motivates us to extend the shuffling-sampling channel model of Shomorony and Heckel (2021) to include a wiretapper. Our main result is a characterization of the secure storage capacity of our DNA wiretap channel model, which is the maximum rate at which data can be stored within a pool of DNA molecules so as to be reliably retrieved by an authorized party (Bob), while ensuring that an unauthorized party (Eve) gets almost no information from her observations. Furthermore, our proof of achievability shows that index-based wiretap channel coding schemes are optimal.

In this work, we address the question of the largest rate of linear subcodes of Reed-Muller (RM) codes, all of whose codewords respect a runlength-limited (RLL) constraint. Our interest is in the (d, ∞)-RLL constraint, which mandates that every pair of successive 1s be separated by at least d 0s. Consider any sequence ${\left\{ {{\mathcal{C}_m}} \right\}_{m \geq 1}}$ of RM codes with increasing blocklength, whose rates approach R, in the limit as the blocklength goes to infinity. We show that for any linear (d, ∞)-RLL subcode, ${\hat {\mathcal{C}}_m}$, of the code ${\mathcal{C}_m}$, it holds that the rate of ${\hat {\mathcal{C}}_m}$ is at most $\frac{R}{{d + 1}}$, in the limit as the blocklength goes to infinity. We also consider scenarios where the coordinates of the RM codes are not ordered according to the standard lexicographic ordering, and derive rate upper bounds for linear (d, ∞)-RLL subcodes, in those cases as well. Next, for the setting of a (d, ∞)-RLL input-constrained binary memoryless symmetric (BMS) channel, we devise a new coding scheme, based on cosets of RM codes. Again, in the limit of blocklength going to infinity, this code outperforms any linear subcode of an RM code, in terms of rate, for low noise regimes of the channel.

The characterization of the secret key capacity with wiretapper side information is a challenging open problem. In this paper, we give a necessary and sufficient condition for the positivity of wiretap secret key capacity for the multiterminal source model. This result extends the existing works for two-terminal sources. However, in the case of hypergraphical source models with a linear wiretapper, we derive a simpler equivalent condition for the positivity. We also show that blocklength need not be larger than the logarithm of the number of edges in order to generate a positive rate key. The proofs of these results involve a subclass called minimally connected hypergraphical sources with a linear wiretapper, for which we obtain a single-letter characterization of wiretap secret key capacity.

We introduce a Markov Chain Monte Carlo (MCMC) algorithm to generate samples from probability distributions supported on a d-dimensional lattice$\Lambda=\text{BZ}^{d}$, where B is a full-rank matrix. Specifically, we consider lattice distributions$P_{\Lambda}$in which the probability at a lattice point is proportional to a given probability density function,$f$, evaluated at that point. To generate samples from$P_{\Lambda}$, it suffices to draw samples from a pullback measure$P_{\mathbb{Z}^{\mathbb{d}}}$defined on the integer lattice. The probability of an integer lattice point under$P_{\mathrm{Z}^{\mathrm{d}}}$is proportional to the density function$\pi=\vert \det(\mathrm{B})\vert f\mathrm{o}$B. The algorithm we present in this paper for sampling from$P_{\mathbb{Z}^{d}}$is based on the Metropolis-Hastings framework. In particular, we use$\pi$as the proposal distribution and calculate the Metropolis-Hastings acceptance ratio for a well-chosen target distribution. We can use any method, denoted by ALG, that ideally draws samples from the probability density$\pi$, to generate a proposed state. The target distribution is a piecewise sigmoidal distribution, chosen such that the coordinate-wise rounding of a sample drawn from the target distribution gives a sample from$P_{\mathbb{Z}^{\mathrm{d}}}$. When ALG is ideal, we show that our algorithm is uniformly ergodic if$-\log(\pi)$satisfies a gradient Lipschitz condition. A full version of this paper is accessible at: https://arxiv.org/pdf/2101.06453.pdf

The paper considers the input-constrained binary erasure channel (BEC) with causal, noiseless feedback. The channel input sequence respects the ($d, \infty$)-runlength limited (RLL) constraint, i.e., any pair of successive 1s must be separated by at least$d$0s. We derive upper and lower bounds on the feedback capacity of this channel, given by single parameter maximization problems that differ exclusively in the domain of maximization. The results of Sabag et al. (2016) show that our bounds are tight for the case when$d=1$. For the case when$d=2$, our lower bound implies that the feedback capacity is equal to the capacity with non-causal knowledge of erasures, for$\epsilon\in [0,1-\frac{1}{2\log_{2}(3/2)}]$. The approach in this paper follows Sabag et al. (2017), by deriving single-letter bounds on the feedback capacity, based on output distributions supported on a finite$Q$-graph, which is a directed graph with edges labelled by output symbols.

In this paper, we obtain a single-letter characterization of the wiretap secret key capacity for a large class of multiterminal source models (namely, tree-PIN models) with a linear wiretapper that can observe arbitrary linear combinations of the source. For this class of sources, we also show a duality between the problems of wiretap secret key agreement and secure omniscience, which suggests that such duality potentially holds for more general sources.

We consider the problem of energy-efficient broadcasting on dense ad-hoc networks. Ad-hoc networks are generally modeled using random geometric graphs (RGGs). Here, nodes are deployed uniformly in a square area around the origin, and any two nodes which are within Euclidean distance of 1 are assumed to be able to receive each other’s broadcast. A source node at the origin encodes k data packets of information into n (> k) coded packets and transmits them to all its one-hop neighbors. The encoding is such that, any node that receives at least k out of the n coded packets can retrieve the original k data packets. Every other node in the network follows a probabilistic forwarding protocol; upon reception of a previously unreceived packet, the node forwards it with probability p and does nothing with probability 1 − p. We are interested in the minimum forwarding probability which ensures that a large fraction of nodes can decode the information from the source. We deem this a near-broadcast. The performance metric of interest is the expected total number of transmissions at this minimum forwarding probability, where the expectation is over both the forwarding protocol as well as the realization of the RGG. In comparison to probabilistic forwarding with no coding, our treatment of the problem indicates that, with a judicious choice of n, it is possible to reduce the expected total number of transmissions while ensuring a near-broadcast.

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

We consider a scenario of broadcasting information over a network of nodes connected by noiseless communication links. A source node in the network has some data packets to broadcast. It encodes these data packets into $n$ coded packets in such a way that any node in the network that receives any $k$ out of the $n$ coded packets will be able to retrieve all the original data packets. The source transmits the $n$ coded packets to its one-hop neighbours. Every other node in the network follows a probabilistic forwarding protocol, in which it forwards a previously unreceived packet to all its neighbours with a certain probability $p$ . We say that the information from the source undergoes a “near-broadcast” if the expected fraction of nodes that receive at least $k$ of the $n$ coded packets is close to 1. The forwarding probability $p$ is chosen so as to minimize the expected total number of transmissions needed for a near-broadcast. We study how, for a given $k$ , this minimum forwarding probability and the associated expected total number of packet transmissions varies with $n$ . We specifically analyze the probabilistic forwarding of coded packets on two network topologies: binary trees and square grids. For trees, our analysis shows that for fixed $k$ , the expected total number of transmissions increases with $n$ . On the other hand, on grids, a judicious choice of $n$ significantly reduces the expected total number of transmissions needed for a near-broadcast. Behaviour similar to that of the grid is also observed in other well-connected network topologies such as random geometric graphs and random regular graphs.

We consider the problem of exchanging sensitive information in public and provide a general formulation that can unify and extend various existing scenarios of information exchange, such as the problems of private information extraction and information bottleneck. The formulation also gives rise to a new scenario called secure omniscience (SO), where users want to exchange all their private information with minimum leakage to a wiretapper with side information. Single-letter lower and upper bounds are obtained for the minimum leakage, and the bounds are shown to be tight under the finite linear source model with two users. The bounds are derived in terms of the solutions of the closely related problems of communication for omniscience (CO) and secret key agreement (SKA). However, we find examples where the bounds are not tight, and so the connections to CO and SKA are not precise. In particular, it is possible that any optimal CO scheme that minimizes communication does not minimize leakage, and any optimal SO scheme that minimizes leakage does not attain the capacity for SKA. Nevertheless, we identify a useful notion of information alignment that can modify an optimal CO scheme to reduce leakage for SO.

This paper studies the capacities of input-driven finite-state channels, i.e., channels whose current state is a time-invariant deterministic function of the previous state and the current input. We lower bound the capacity of such a channel using a dynamic programming formulation of a bound on the maximum reverse directed information rate. We show that the dynamic programming-based bounds can be simplified by solving the corresponding Bellman equation explicitly. In particular, we provide analytical lower bounds on the capacities of (d, k)-runlength-limited input-constrained binary symmetric and binary erasure channels.

We consider a non-asymptotic (one-shot) version of the multiterminal secret key agreement problem on a finite linear source model. In this model, the observation of each terminal is a linear function of an underlying random vector composed of finitely many i.i.d. uniform random variables. By restricting the public discussion to be a linear function of the terminals' observations, we obtain a characterization of the communication complexity (minimum number of symbols of public discussion) of generating a secret key of maximum length. More precisely, we show that the minimum discussion can be achieved by a non-interactive protocol in which each terminal first does a linear processing of its own private observations, following which the terminals all execute a discussion-optimal communication-for-omniscience protocol. The secret key can be chosen to be a linear function of the vector of all observations.

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

A Markov chain approach is applied to determine the capacity of a general class of q-ary ICI-free constrained systems that satisfy an arbitrary count constraint.

We consider a scenario of broadcasting information over a network of nodes connected by noiseless communication links. A source node in the network has k data packets to broadcast, and it suffices that a large fraction of the network nodes receives the broadcast. The source encodes the k data packets into n≥k coded packets using a maximum distance separable (MDS) code, and transmits them to its one-hop neighbours. Every other node in the network follows a probabilistic forwarding protocol, in which it forwards a previously unreceived packet to all its neighbours with a certain probability p. A "near-broadcast" is when the expected fraction of nodes that receive at least k of the n coded packets is close to 1. The forwarding probability p is chosen so as to minimize the expected total number of transmissions needed for a near-broadcast. In this paper, we analyze the probabilistic forwarding of coded packets on two specific network topologies: binary trees and square grids. For trees, our analysis shows that for fixed k, the expected total number of transmissions increases with n. On the other hand, on grids, we use ideas from percolation theory to show that a judicious choice of n will significantly reduce the expected total number of transmissions needed for a near-broadcast.

Hypergraphical sources are a natural class of sources for secret key generation, within which different subsets of terminals sharing secrets are allowed to discuss publicly in order to agree upon a global secret key. While their secrecy capacity, i.e., the maximum rate of a secret key that can be agreed upon by the entire set of terminals, is well-understood, what remains open is the maximum rate of a secret key that can be generated when there is a restriction on the overall rate of public discussion allowed. In this paper, we obtain a family of explicitly computable upper bounds on the number of bits of secret key that can be generated per bit of public discussion. These upper bounds are derived using a lamination technique based on the submodularity of the entropy function. In particular, a specific instance of these upper bounds, called the edge-partition bound, is shown to be tight for the pairwise independent network model, a special case of the hypergraphical source when the hypergraph is a graph. The secret key generation scheme achieving this upper bound is the tree-packing protocol of Nitinawarat et al., thereby resolving in the affirmative the discussion rate optimality of the tree-packing protocol.

In the multiterminal secret key agreement problem, a set of users want to discuss with each other until they share a common secret key independent of their discussion. We want to characterize the maximum secret key rate, called the secrecy capacity, asymptotically when the total discussion rate goes to zero. In the case of only two users, the capacity is equal to the Gács-Körner common information. However, when there are more than two users, the capacity is unknown. It is plausible that a multivariate extension of the Gács-Kömer common information is the capacity, however, proving the converse is challenging. We resolved this for the hypergraphical sources and finite linear sources, and provide efficiently computable characterizations. We also give some ideas of extending the techniques to more general source models.

A prefix code X is said to satisfy the (d, k) runlength-limited (RLL) constraint if all the possible concatenations of the codewords of X satisfy the (d, k) RLL constraint. In this paper, the problem of constructing a minimum expected length prefix code satisfying the (d, k) RLL constraint is studied for certain (d, k) pairs. The question of maximality, with maximality defined relative to the RLL constraint, of these optimal prefix codes is also taken up and answered for some cases.

For the multiterminal secret key agreement problem under a private source model, it is known that the maximum key rate, i.e., the secrecy capacity, can be achieved through communication for omniscience, but the omniscience strategy can be strictly suboptimal in terms of minimizing the public discussion rate. While a single-letter characterization is not known for the minimum discussion rate needed for achieving the secrecy capacity, we derive single-letter lower bounds that yield some simple conditions for omniscience to be discussion-rate optimal. These conditions turn out to be enough to deduce the optimality of omniscience for a large class of sources, including the hypergraphical sources. We also extend our results to more general class of multiterminal sources with helpers and silent users.

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

For the multiterminal secret key agreement problem, new single-letter lower bounds are obtained on the minimum public discussion rate required to achieve any given secret key rate below the secrecy capacity. The results apply to the general source model without helpers or wiretapper's side information, but can be strengthened for hypergraphical sources. In particular, for the pairwise independent network, our results yield a complete characterization of the maximum secret key rate achievable under a constraint on the total discussion rate.

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

The pattern maximum likelihood (PML) estimate, introduced by Orlitsky et al., is an estimate of the multiset of probabilities in an unknown probability distribution $\mathbf{p}$, the estimate being obtained from $n$ independent and identically distributed samples drawn from $\mathbf{p}$. The PML estimate involves solving a difficult optimization problem over the set of all probability mass functions of finite support. In this paper, we describe an interesting phase transition phenomenon in the PML estimate: at a certain sharp threshold, the uniform distribution goes from being a local maximum to being a local minimum for the optimization problem in the estimate. We go on to consider the question of whether a similar phase transition phenomenon also exists in the Bethe approximation of the PML estimate, the latter being an approximation method with origins in statistical physics. We show that the answer to this question is a qualified “yes.” Our analysis involves the computation of the mean and variance of the $(i,j)$th entry, $a_{i,j}$, in a random $k \times k$ nonnegative integer matrix $A$ with row and column sums all equal to $M$, drawn according to a distribution that assigns to $A$ a probability proportional to $\Pi_{i,j} \frac{(M-a_{i,j})!}{a_{i,j}!}$.

In the multiterminal source model of Csiszár and Narayan, the communication complexity, RSK, for secret key (SK) generation is the minimum rate of communication required to achieve SK capacity. An obvious upper bound to RSKis given by RCO, which is the minimum rate of communication required for omniscience. In this paper we derive a better upper bound to RSKfor the hypergraphical source model, which is a special instance of the multiterminal source model. The upper bound is based on the idea of fractional removal of hyperedges. It is further shown that this upper bound can be computed in polynomial time. We conjecture that our upper bound is tight. For the special case of a graphical source model, we also give an explicit lower bound on RSK. This bound, however, is not tight, as demonstrated by a counterexample.

In this article, we study the problem of secret key generation in the multiterminal source model, where the terminals have access to correlated Gaussian sources. We assume that the sources form a Markov chain on a tree. We give a nested lattice-based key generation scheme whose computational complexity is polynomial in the number, N, of independent and identically distributed samples observed by each source. We also compute the achievable secret key rate and give a class of examples where our scheme is optimal in the fine quantization limit. However, we also give examples that show that our scheme is not always optimal in the limit of fine quantization.

For the multiterminal secret key agreement problem under a private source model, it is known that the communication complexity required to achieve the capacity can be strictly smaller than the minimum rate of communication for omniscience, but a single-letter characterization is not known. We obtain a single-letter lower bound on the communication complexity as well as some conditions for the communication complexity to be maximal (equal to the smallest rate of communication for omniscience). The results are are stated and derived using a meaningful multivariate mutual information measure. They are stronger than existing ones because 1) they apply to a general discrete memoryless multiple source rather than a special source model, 2) the problem formulation allows private randomization by individual users, 3) the bound is single-letter and the condition can be checked easily, and so 4) more scenarios in which the communication complexity is maximal are discovered. We conjecture that the lower bound can be further improved by giving a concrete example.

The discrete-grains model is a simple model for the distribution of “grains” on a magnetic medium. In this model, grains on the medium are taken to be one of four basic rectangular shapes (“tiles”)-1 × 1, 1 × 2, 2 × 1, and 2 × 2. The magnetic medium is then modeled as an N × N square tiled by these four basic tiles. In this paper, we present Markov chain Monte Carlo (MCMC) methods for generating random tilings of an N × N square consisting only of the four basic tiles. To be precise, given a target probability distribution, e.g., the uniform distribution, on the space, SN, of all possible such tilings, we make use of the Metropolis-Hastings algorithm to design an MCMC method for sampling from a probability distribution arbitrarily close, in total variation distance, to the target distribution. We further extend this approach to enable sampling from probability distributions on certain subsets of SN, namely, those consisting of tilings, in which each kind of tile occurs a fixed number of times. We finally present some bounds and conjectures on the mixing times of the underlying Markov chains, which provide estimates of the amount of time taken by the MCMC methods to generate a random tiling sampled from the target probability distribution.

The focus of this paper is on the public communication required for generating a maximal-rate secret key (SK) within the multiterminal source model of Csiszár and Narayan. Building on the prior work of Tyagi for the two-terminal scenario, we derive a lower bound on the communication complexity, RSK, defined to be the minimum rate of public communication needed to generate a maximal-rate SK. It is well known that the minimum rate of communication for omniscience, denoted by RCO, is an upper bound on RSK. For the class of pairwise independent network (PIN) models defined on uniform hypergraphs, we show that a certain Type S condition, which is verifiable in polynomial time, guarantees that our lower bound on RSKmeets the RCOupper bound. Thus, the PIN models satisfying our condition are RSK-maximal, indicating that the upper bound RSK≤ RCOholds with equality. This allows us to explicitly evaluate RSKfor such PIN models. We also give several examples of PIN models that satisfy our Type S condition. Finally, we prove that for an arbitrary multiterminal source model, a stricter version of our Type S condition implies that communication from all terminals (omnivocality) is needed for establishing an SK of maximum rate. For three-terminal source models, the converse is also true: omnivocality is needed for generating a maximal-rate SK only if the strict Type S condition is satisfied. However, for the source models with four or more terminals, counterexamples exist showing that the converse does not hold in general.

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

Recent empirical results have demonstrated that generalized belief propagation (GBP) can be used to closely estimate the capacity of certain 2D runlength-limited constraints. We provide a partial analytical validation of these observations by showing that GBP yields a lower bound on the partition function of 2D Ising models with restricted grid size. While previous papers have proved that belief propagation (BP) can be used to obtain a lower bound on the partition function of 2D Ising models, this paper is the first work that analyzes GBP-based partition function approximations of 2D Ising models.

The communication complexity of achieving secret key (SK) capacity in the multiterminal source model of Csiszár and Narayan is the minimum rate of public communication required to generate a maximal-rate SK. It is well known that the minimum rate of communication for omniscience, denoted by RCO, is an upper bound on the communication complexity, denoted by RSK. A source model for which this upper bound is tight is called RSK-maximal. In this paper, we establish a sufficient condition for RSK-maximality within the class of pairwise independent network (PIN) models defined on hypergraphs. This allows us to compute RSKexactly within the class of PIN models satisfying this condition. On the other hand, we also provide a counterexample that shows that our condition does not in general guarantee RSK-maximality for sources beyond PIN models.

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

We study some structural properties of Construction-A lattices obtained from low-density parity-check (LDPC) codes over prime fields. Such lattices are called low-density Construction-A (LDA) lattices, and have been shown to achieve the capacity of the AWGN channel under closest lattice-point decoding. Also, simulations suggest that they perform well under belief propagation decoding. In this work, we prove that LDA lattices are good for packing and mean squared error (MSE) quantization, and that their duals are good for packing. With this, we can conclude that codes constructed using nested LDA lattices can achieve the capacities of the AWGN channel and the dirty paper channel, the rates guaranteed by the compute-and-forward protocol, and the best known rates for bidirectional relaying with perfect secrecy.

The basic problem of secure bidirectional relaying involves two users who want to exchange messages via an intermediate “honest-but-curious” relay node. There is no direct link between the users; all communication must take place via the relay node. The links between the user nodes and the relay are wireless links with Gaussian noise. It is required that the users' messages be kept secure from the relay. In prior work, we proposed coding schemes based on nested lattices for this problem, assuming that the channel gains from the two user nodes to the relay are identical. We also analyzed the power-rate tradeoff for secure and reliable message exchange using our coding schemes. In this paper, we extend our prior work to the case when the channel gains are not necessarily identical, and are known to the relay node but perhaps not to the users. We show that using our scheme, perfect secrecy can be obtained only for certain values of the channel gains, and analyze the power-rate tradeoff in these cases. We also make similar observations for our strongly-secure scheme.

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.

Communication complexity refers to the minimum rate of public communication required for generating a maximal-rate secret key (SK) in the multiterminal source model of Csiszár and Narayan. Tyagi recently characterized this communication complexity for a two-terminal system. We extend the ideas in Tyagi's work to derive a lower bound on communication complexity in the general multiterminal setting. In the important special case of the complete graph pairwise independent network (PIN) model, our bound allows us to determine the exact linear communication complexity, i.e., the communication complexity when the communication and SK are restricted to be linear functions of the randomness available at the terminals.

In this paper, we address the problem of characterizing the instances of the multiterminal source model of Csiszár and Narayan in which communication from all terminals is needed for establishing a secret key of maximum rate. We give an information-theoretic sufficient condition for identifying such instances. We believe that our sufficient condition is in fact an exact characterization, but we are only able to prove this in the case of the three-terminal source model.

In this paper, we revisit the combinatorial error model of Mazumdar et al. that models errors in high-density magnetic recording caused by lack of knowledge of grain boundaries in the recording medium. We present new upper bounds on the cardinality/rate of binary block codes that correct errors within this model. All our bounds, except for one, are obtained using combinatorial arguments based on hypergraph fractional coverings. The exception is a bound derived via an information-theoretic argument. Our bounds significantly improve upon existing bounds from the prior literature.

In this paper, we re-visit the combinatorial error model of Mazumdar et al. [3] that models errors in high-density magnetic recording caused by lack of knowledge of grain boundaries in the recording medium. We present new upper bounds on the cardinality/rate of binary block codes that correct errors within this model.

We study the problem of secure bidirectional relaying in the presence of an “honest but curious” relay. We consider the setting where all links between nodes are additive white Gaussian noise (AWGN) channels, and show that using nested lattice codes, it is possible to obtain strong secrecy. A randomized encoder based on probability mass functions obtained by sampling the Gaussian function is used, and we show that the mutual information between the secret messages and the vector received by the relay is arbitrarily small for large block lengths. We determine sufficient conditions for secure and reliable communication, and find achievable rates. We then extend the results to the case of secure relaying in a multi-hop network with K +1 hops.

In this paper, we consider the setting of the pattern maximum likelihood (PML) problem studied by Orlitsky et al. We present a well-motivated heuristic algorithm for deciding the question of when the PML distribution of a given pattern is uniform. The algorithm is based on the concept of a “uniform threshold”. This is a threshold at which the uniform distribution exhibits an interesting phase transition in the PML problem, going from being a local maximum to being a local minimum.

In this work, we consider two-dimensional (2-D) binary channels in which the 2-D error patterns are constrained so that errors cannot occur in adjacent horizontal or vertical positions. We consider probabilistic and combinatorial models for such channels. A probabilistic model is obtained from a 2-D random field defined by Roth, Siegel and Wolf (2001). Based on the conjectured ergodicity of this random field, we obtain an expression for the capacity of the 2-D non-adjacent-errors channel. We also derive an upper bound for the asymptotic coding rate in the combinatorial model.

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.

Mobile nodes observing correlated data communicate using an insecure bidirectional switch to generate a secret key, which must remain concealed from the switch. We are interested in fault-tolerant secret key rates, i.e., the rates of secret key generated even if a subset of nodes drop out before the completion of the communication protocol. We formulate a new notion of fault-tolerant secret key capacity, and present an upper bound on it. This upper bound is shown to be tight when the random variables corresponding to the observations of nodes are exchangeable. Further, it is shown that one round of interaction achieves the fault-tolerant secret key capacity in this case. The upper bound is also tight for the case of a pairwise independent network model consisting of a complete graph, and can be attained by a noninteractive protocol.

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 terabit-density magnetic recording, several bits of data can be replaced by the values of their neighbors in the storage medium. As a result, errors in the medium are dependent on each other and also on the data written. We consider a simple 1-D combinatorial model of this medium. In our model, we assume a setting where binary data is sequentially written on the medium and a bit can erroneously change to the immediately preceding value. We derive several properties of codes that correct this type of errors, focusing on bounds on their cardinality. We also define a probabilistic finite-state channel model of the storage medium, and derive lower and upper estimates of its capacity. A lower bound is derived by evaluating the symmetric capacity of the channel, i.e., the maximum transmission rate under the assumption of the uniform input distribution of the channel. An upper bound is found by showing that the original channel is a stochastic degradation of another, related channel model whose capacity we can compute explicitly.

We study a model of errors in binary data that arises in terabit-density magnetic recording. Under this model, several bits of the data are replaced by the values of their neighbors on the medium. We consider a simple one-dimensional version of this model, and derive several properties of codes that correct this type of error.

We address the problem of finding the minimum decomposition of a permutation in terms of transpositions with non-uniform cost. For metric-path costs, we describe exact polynomial-time decomposition algorithms. For extended-metric-path cost functions, we describe polynomial-time constant-approximation decomposition algorithms. Our algorithms rely on graphical representations of permutations and graph-search techniques for minimizing the permutation decomposition cost. The presented algorithms have applications in information theory, bioinformatics, and algebra.

The class of periodic-finite-type shifts (PFT's) is a class of sofic shifts that strictly includes the class of shifts of finite type (SFT's), and the zeta function of a PFT is a generating function for the number of periodic sequences in the shift. In this paper, we derive a useful formula for the zeta function of a PFT. This formula allows the zeta function of a PFT to be computed more efficiently than the specialization of a formula known for a generic sofic shift.

Periodic-finite-type shifts (PFTs) form a class of sofic shifts that strictly contains the class of shifts of finite type (SFTs). In this paper, we study PFTs from the viewpoint of certain “periods” that can be associated with them. We define three kinds of periods (descriptive, sequential, and graphical) for PFTs and investigate the relationships between them. The results of our investigation indicate that there are no specific relationships between these periods, except for the fact that the descriptive period of an irreducible PFT always divides its graphical period. Furthermore, we compute the number of periodic sequences in PFTs of a certain type, from which we obtain expressions for their zeta functions.

A tree decomposition of the coordinates of a code is a mapping from the coordinate set to the set of vertices of a tree. A tree decomposition can be extended to a tree realization, i.e., a cycle-free realization of the code on the underlying tree, by specifying a state space at each edge of the tree, and a local constraint code at each vertex of the tree. The constraint complexity of a tree realization is the maximum dimension of any of its local constraint codes. A measure of the complexity of maximum-likelihood (ML) decoding for a code is its treewidth, which is the least constraint complexity of any of its tree realizations.It is known that among all tree realizations of a linear code that extends a given tree decomposition, there exists a unique minimal realization that minimizes the state-space dimension at each vertex of the underlying tree. In this paper, we give two new constructions of these minimal realizations. As a by-product of the first construction, a generalization of the state-merging procedure for trellis realizations, we obtain the fact that the minimal tree realization also minimizes the local constraint code dimension at each vertex of the underlying tree. The second construction relies on certain code decomposition techniques that we develop. We further observe that the treewidth of a code is related to a measure of graph complexity, also called treewidth. We exploit this connection to resolve a conjecture of Forney's regarding the gap between the minimum trellis constraint complexity and the treewidth of a code. We present a family of codes for which this gap can be arbitrarily large.

A graphical realization of a linear code C consists of an assignment of the coordinates of C to the vertices of a graph, along with a specification of linear state spaces and linear "local constraint" codes to be associated with the edges and vertices, respectively, of the graph. The kappa-complexity of a graphical realization is defined to be the largest dimension of any of its local constraint codes, kappa -complexity is a reasonable measure of the computational complexity of a sum-product decoding algorithm specified by a graphical realization. The main focus of this paper is on the following problem: given a linear code C and a graph G, how small can the kappa-complexity of a realization of C on G be? As useful tools for attacking this problem, we introduce the vertex-cut bound, and the notion of "vc-treewidth" for a graph, which is closely related to the well-known graph-theoretic notion of treewidth. Using these tools, we derive tight lower bounds on the kappa-complexity of any realization of C on G. Our bounds enable us to conclude that good error-correcting codes can have low-complexity realizations only on graphs with large vc-treewidth. Along the way, we also prove the interesting result that the ratio of the kappa-complexity of the best conventional trellis realization of a length-n code C to the kappa-complexity of the best cycle-free realization of C grows at most logarithmically with code length n. Such a logarithmic growth rate is, in fact, achievable.

This paper extends the theory of data synchronization with timing for fixed-rate codes, previously developed by the authors, to the variable-rate case. Given a source code, a class of sync-timing codes called variable-rate cascaded (VRC) codes is considered that ldquowrap aroundrdquo the source code in such a way as to enable the decoder to not only resynchronize rapidly when the encoded bits are corrupted by insertion, deletion, or substitution errors, but also produce estimates of the time indices of the data symbols encoded by the source code. The estimates of the time indices are modulo-Treductions of the actual time indices, for some integerTcalled the timing span of the code. These sync-timing codes are analyzed on the basis of the maximum timing span achievable for a given coding rateRand permissible resynchronization delayD. It is shown that the timing span of VRC codes is upper-bounded by 2D(1-R)+o(D), and that this upper bound is achievable asymptotically in D. This exponential rate of growth of timing span with delay is the same as that found previously for certain fixed-rate sync-timing codes, e.g., (fixed-rate) cascaded codes.

Periodic-finite-type shifts (PFTpsilas) form a class of sofic shifts that strictly contains the class of shifts of finite type (SFTpsilas). In this paper, we investigate how the notion of ldquoperiodrdquo inherent in the definition of a PFT causes it to differ from an SFT, and how the period influences the properties of a PFT.

We relate the notion of matroid pathwidth to the minimum trellis state-complexity (which we term trellis-width) of a linear code and to the pathwidth of a graph. By reducing from the problem of computing the pathwidth of a graph, we show that the problem of determining the pathwidth of a representable matroid is NP-hard. Consequently, the problem of computing the trellis-width of a linear code is also NP-hard. For a finite field $\F$, we also consider the class of $\F$-representable matroids of pathwidth at most w, and correspondingly, the family of linear codes over $\F$ with trellis-width at most w. These are easily seen to be minor-closed. Since these matroids (and codes) have branchwidth at most w, a result of Geelen and Whittle shows that such matroids (and the corresponding codes) are characterized by finitely many excluded minors. We provide the complete list of excluded minors for $w=1$ and give a partial list for $w=2$.

The decomposition theory of matroids initiated by Paul Seymour in the 1980s has had an enormous impact on research in matroid theory. This theory, when applied to matrices over the binary field, yields a powerful decomposition theory for binary linear codes. In this paper, we give an overview of this code decomposition theory, and discuss some of its implications in the context of the recently discovered formulation of maximum-likelihood (ML) decoding of a binary linear code over a binary-input discrete memoryless channel as a linear programming problem. We translate matroid-theoretic results of Grotschel and Truemper from the combinatorial optimization literature to give examples of nontrivial families of codes for which the ML decoding problem can be solved in time polynomial in the length of the code. One such family is that consisting of codes for which the codeword polytope is identical to the Koetter-Vontobel fundamental polytope derived from the entire dual code Cperp. However, we also show that such families of codes are not good in a coding-theoretic sense-either their dimension or their minimum distance must grow sublinearly with code length. As a consequence, we have that decoding by linear programming, when applied to good codes, cannot avoid failing occasionally due to the presence of pseudocode words.

In this paper, we give an overview of Seymour's matroid decomposition theory in the context of binary linear codes, and discuss some of its implications for linear programming (LP) decoding of a binary linear code. As shown by Feldman et al. maximum-likelihood (ML) decoding over a discrete memoryless channel can be formulated as an LP problem. Using this formulation, we translate matroid-theoretic results of Grotschel and Truemper from the combinatorial optimization literature as examples of non-trivial families of codes for which ML decoding can be implemented in time polynomial in the length of the code. However, we also show that such families of codes are not good in a coding-theoretic sense - either their dimension or their minimum distance must grow sub-linearly with codelength.

A construction of Crocheniore, Mignosi and Restivo in the automata theory literature gives a presentation of a finite-type constrained system (FTCS) that is deterministic and has a relatively small number of states. This construction is thus a good starting point for determining the minimal deterministic presentation, known as the Shannon cover, of an FTCS. We analyze in detail the Crochemore-Mignosi-Restivo (CMR) construction in the case when the list of forbidden words defining the FTCS is of size at most two. We show that if the FTCS is irreducible, then an irreducible presentation for the system can be easily obtained from the CMR presentation. By studying the follower sets of the states in this irreducible presentation, we are able to explicitly determine the Shannon cover in some cases. In particular, our results show that the CMR construction directly yields the Shannon cover in the case of an irreducible FTCS with exactly one forbidden word, but this is not in general the case for FTCS's with two forbidden words

A generating function method is developed in order to select synchronization markers that maximize the timing span of period-2 periodic prefix-synchronized (PPS) sync-timing coding with small delay. Sync-timing codes are used in situations where conventional data synchronization is required, and data time stamps or time indices are also needed. A PPS code is a sync-timing code in which each encoded block of data is preceded by a synchronization marker, with the markers preceding successive blocks forming a periodic sequence with some period p. Since only PPS codes with small periods can have good rates at small delays, and since codes with p=1 are simply Gilbert's prefix-synchronized codes which have been studied previously in the literature, this paper focuses on p=2 codes. The generating function method, which extends that used by Guibas and Odlyzko to analyze p=1 codes, enables one to find PPS codes with the largest possible timing span among codes with a given delay and rate. It is found that at low delays such optimized PPS codes offer significant advantages over cascaded and natural marker PPS codes. They also compare favorably with embedded-index codes. Finally, for asymptotically large delays, it is shown that the best p=2 PPS codes operate at approximately the same rate and delay, but twice the timing span, of the best p=1 codes.

We consider a number of constrained coding techniques that can be used to mitigate a nonlinear effect in the optical fiber channel that causes the formation of spurious pulses, called "ghost pulses". Specifically, if b/sub 1/b/sub 2/...b/sub n/ is a sequence of bits sent across an optical channel, such that b/sub k/=b/sub l/=b/sub m/=1 for some k,l,m (not necessarily all distinct) but b/sub k+l-m/=0, then the ghost-pulse effect causes b/sub k+l-m/ to change to 1, thereby creating an error. Such errors do not occur if the sequence of bits satisfies the following constraint: for all integers k,l,m such that b/sub k/=b/sub l/=b/sub m/=1, we have b/sub k+l-m/=1. We call this the binary ghost-pulse (BGP) constraint. We will show, however, that the BGP constraint has zero capacity, implying that sequences satisfying this constraint cannot carry much information. Consequently, we consider a more sophisticated coding scheme, which uses ternary sequences satisfying a certain ternary ghost-pulse (TGP) constraint. We further relax these constraints by ignoring interactions between symbols that are more than a certain distance t apart in the transmitted sequence. Analysis of the resulting BGP(t) and TGP(t) constraints shows that these have nonzero capacities, and furthermore, the TGP(t)-constrained codes can achieve rates that are significantly higher than those for the corresponding BGP(t) codes. We also discuss the design of encoders and decoders for coding into the BGP, BGP(t), and TGP(t) constraints.

One approach to designing structured low-density parity-check (LDPC) codes with large girth is to shorten codes with small girth in such a manner that the deleted columns of the parity-check matrix contain all the variables involved in short cycles. This approach is especially effective if the parity-check matrix of a code is a matrix composed of blocks of circulant permutation matrices, as is the case for the class of codes known as array codes. We show how to shorten array codes by deleting certain columns of their parity-check matrices so as to increase their girth. The shortening approach is based on the observation that for array codes, and in fact for a slightly more general class of LDPC codes, the cycles in the corresponding Tanner graph are governed by certain homogeneous linear equations with integer coefficients. Consequently, we can selectively eliminate cycles from an array code by only retaining those columns from the parity-check matrix of the original code that are indexed by integer sequences that do not contain solutions to the equations governing those cycles. We provide Ramsey-theoretic estimates for the maximum number of columns that can be retained from the original parity-check matrix with the property that the sequence of their indices avoid solutions to various types of cycle-governing equations. This translates to estimates of the rate penalty incurred in shortening a code to eliminate cycles. Simulation results show that for the codes considered, shortening them to increase the girth can lead to significant gains in signal-to-noise ratio (SNR) in the case of communication over an additive white Gaussian noise (AWGN) channel.

In this paper, we consider the problem of designing codewords for DNA storage systems and DNA computers that are unlikely to fold back onto themselves to form undesirable secondary structures. Secondary structure formation causes a DNA codeword to become less active chemically, thus rendering it useless for the purpose of DNA computing. It also defeats the read-back mechanism in a DNA storage system, so that information stored in such a folded DNA codeword cannot be retrieved. Based on some simple properties of a dynamic-programming algorithm, known as Nussinov's method, which is an effective predictor of secondary structure given the sequence of bases in a DNA codeword, we identify some design criteria that reduce the possibility of secondary structure formation in a codeword. These design criteria can be formulated in terms of the requirement that the Watson-Crick distance between a DNA codeword and a number of its shifts be larger than a given threshold. This paper addresses both the issue of enumerating DNA sequences with such properties and the problem of practical DNA code construction

In this paper, we analyze bi-infinite sequences over the alphabet $\{0,1,\ldots,q-1\}$, for an arbitrary $q \geq 2$, that satisfy the q-ary ghost pulse (qGP) constraint. A sequence $\x = {(x_k)}_{k \in \Z} \in \{0,1,\ldots,q-1\}^{\Z}$ satisfies the qGP constraint if for all $k,l,m \in \Z$ such that $x_k$, $x_l$ and $x_m$ are nonzero and equal, $x_{k+l-m}$ is also nonzero. This constraint arises in the context of coding for communication over a fiber optic medium. We show, using techniques from Ramsey theory, that if $\x$ satisfies the qGP constraint, then the set $\supp(\x) = \{l \in \Z:\ x_l \neq 0\}$ is the disjoint union of cosets of some subgroup, $k\Z$, of $\Z$, and a set of zero density. We provide much sharper results in the special cases of $q = 2$ and $q=3$. In the former case, we show that the corresponding binary ghost pulse constraint has zero capacity, and based on our results for the latter case, we conjecture that the capacity of the ternary ghost pulse constraint is also zero.

We determine the pairs of (d, k)-constrained systems, S(d,k) and S(d,k), of equal capacity, for which there exists a rate 1:1 sliding-block decodable encoder from S(d,k) to S(d,k). Whenever such an encoder exists, we explicitly describe one such encoder and its corresponding sliding-block decoder.

Biinfinite sequences X=(x/sub k/)/sub k/spl isin//spl Zopf// over the alphabet {0,1,...,q-1}, for an arbitrary q/spl ges/2, that satisfy the following q-ary ghost pulse (qGP) constraint: for all k,l,m/spl isin//spl Zopf/ such that x/sub k/,x/sub l/,x/sub m/ are nonzero and equal, x/sub k+l-m/ is also nonzero is studied in this paper. This constraint arises in the context of coding to combat the formation of spurious "ghost" pulses in high data-rate communication over an optical fiber. We show using techniques from Ramsey theory that if x satisfies the /sub q/GP constraint, then the support of x is a disjoint union of cosets of a subgroup k/spl Zopf/ of /spl Zopf/ and a set of zero density.

We determine the pairs of (d,k)-constrained systems, S(d,k) and S(d/spl circ/,k/spl circ/), of equal capacity, for which there exists a rate 1:1 sliding-block-decodable encoder from S(d,k) to S(d/spl circ/,k/spl circ/). In all cases where there exists such an encoder, we explicitly describe the encoder and its corresponding sliding-block decoder.

In this paper, we consider the problem of finding the set $\{A,B\} \subset {0,1} m that maximizes, among all 2-subsets of ${\{0,1\}}^m$, the Shannon capacity, H(A,B), of a constrained system of binary sequences that do not contain A or B as a contiguous subsequence. This problem is motivated by the problem of finding a pair of length-m binary sequences, called markers, that achieves the maximum rate, R(2,m,n), of a (2,m,n) periodic prefix-synchronized (PPS) code. A (2,m,n) PPS code is a binary block code with two length-m markers, A,B, and codewords of length n that inserts A and B alternately at regular intervals in the encoded bitstream, with the additional constraint that A and B may not appear anywhere in the encoded bitstream other than where inserted. We show that for any $m \geq 2$, $\lim_{n \rightarrow \infty} R(2,m,n) = \max\{H(A,B): \{A,B\} \subset {\{0,1\}}^m\} = \log_2\rho_{m-1}$, where $\rho_{m-1}$ is the largest-magnitude zero of the polynomial $z^{m-1} - z^{m-2} - \cdots - 1$. Moreover, we completely characterize the sequences A and B that achieve $\max H(A,B), as well as those that achieve R(2,m,n) for all sufficiently large n.

In this paper, we consider the problem of determining when the capacities of distinct (d,k)-constrained systems can be equal. A (d,k)-constrained system consists of binary sequences which have at least d zeros and at most k zeros between any two successive ones. If we let C(d,k) denote the capacity of a (d,k)-constrained system, then it is known that C(d,2d) = C(d+1,3d+1) and C(d,2d+1) = C(d+1,\infty)$. Repeated application of these two identities also yields the chain of equalities C(1,2) = C(2,4) = C(3,7) = C(4,\infty)$. We show that these are the only equalities possible among the capacities of (d,k)-constrained systems. In the process, we also provide useful factorizations of the characteristic polynomials for these constraints.

This paper proposes and analyzes data synchronization techniques that not only resynchronize after encoded bits are corrupted by insertion, deletion, or substitution errors, but also produce estimates of the time indexes of the decoded data symbols, in order to determine their positions in the original source sequence. The techniques are based on block codes, and the estimates are of the time indexes modulo some integer T, called the timing span, which is desired to be large. Several types of block codes that encode binary data are analyzed on the basis of the maximum attainable timing span for a given coding rate R (or, equivalently, redundancy /spl rho/=1-R) and permissible resynchronization delay D. It is found that relatively simple codes can asymptotically attain the maximum timing span among such block codes, which grows exponentially with delay, with exponent D(1-R)+o(D). Thus, large timing span can be attained with little redundancy and only moderate values of delay.

Until recently, the solution to the Kelvin problem of finding a partition of R/sup 3/ into equal-volume cells with the least surface area was believed to be tessellation by the truncated octahedron. In 1994, D. Weaire and R. Phelan described a partition that outperformed the truncated octahedron partition in this respect. This raises the question of whether the Weaire-Phelan (WP) partition can outperform the truncated octahedron partition in terms of normalized moment of inertia (NMI), thus providing a counterexample to Gersho's conjecture that the truncated octahedron partition has the least NMI among all partitions of R/sup 3/. In this correspondence, we show that the effective NMI of the WP partition is larger than that of the truncated octahedron partition. We also show that if the WP partition is used as the partition of a three-dimensional (3-D) vector quantizer (VQ), with the corresponding codebook consisting of the centroids of the cells, then the resulting quantization error is white. We then show that the effective NMI of the WP partition cannot he reduced by passing it through an invertible linear transformation. Another contribution of this correspondence is a proof of the fact that the quantization error corresponding to an optimal periodic partition is white, which generalizes a result of Zamir and Feder (1996).

This paper investigates the design and analysis of data synchronization codes whose decoders have the property that, in addition to reestablishing correct decoding after encoded data is lost or afflicted with errors, they produce the original time index of each decoded data symbol modulo some integer T. The motivation for such data synchronization with timing is that in many situations where data must be encoded, it is not sufficient for the decoder to present a sequence of correct data symbols. Instead, the user also needs to know the position in the original source sequence of the symbols being presented. With this goal in mind, periodic prefix-synchronized (PPS) codes are introduced and analyzed on the basis of their synchronization delay D, rate R, and timing span T. Introduced are two specific PPS designs called natural marker and cascaded codes. A principal result is that when coding binary data with rate R, the largest possible timing span attainable with PPS codes grows exponentially with delay D, with exponent D(1-R). Thus, a large timing span can be attained with little redundancy and moderate values of delay.