Analytic combinatorics in several variables refers to a suite of tools that provide sharp asymptotic estimates for certain combinatorial quantities. In this paper, we apply these tools to determine the Gilbert-Varshamov lower bound on the rate of optimal codes in$L_{1}$metric. Several different code spaces are analyzed, including the simplex and the hypercube in${\mathbb {Z}}^{n}$, all of which are inspired by concrete data storage and transmission models such as the permutation channel, the repetition channel, the adjacent transposition (bit-shift) channel, the multilevel flash memory channel, etc.

The idea of balancing the side-channel leakage in software was proposed more than a decade ago. Just like with other hiding-based countermeasures, the goal is not to hide the leakage completely but to significantly increase the effort required for the attack. Previous approaches focused on two directions: either balancing the Hamming weight of the processed data or deriving the code by using stochastic leakage profiling. In this brief, we build upon these results by proposing a novel approach that combines the two directions. We provide the theory behind our encoding scheme backed by experimental results on a 32-bit ARM Cortex-M4 microcontroller. Our results show that such a combination gives better side-channel resistance properties than each of the two methods separately.

Analytic combinatorics in several variables refers to a suite of tools that provide sharp asymptotic estimates for certain combinatorial quantities. In this paper, we apply these tools to determine the Gilbert–Varshamov (GV) bound for the sticky insertion and the constrained-synthesis channel.

Several communication models that are of relevance in practice are asymmetric in the way they act on the transmitted "objects". Examples include channels in which the amplitudes of the transmitted pulses can only be decreased, channels in which the symbols can only be deleted, channels in which non-zero symbols can only be shifted to the right (e.g., timing channels), subspace channels in which the dimension of the transmitted vector space can only be reduced, unordered storage channels in which the cardinality of the stored (multi)set can only be reduced, etc. We introduce a formal definition of an asymmetric channel as a channel whose action induces a partial order on the set of all possible inputs, and show that this definition captures all the above examples. Such a general approach allows one to treat all these different models in a unified way, and to obtain a characterization of optimal error-detecting codes for many interesting asymmetric channels by using Sperner theory.

This paper studies properties of binary runlength-limited sequences with additional constraints on their Hamming weight and/or their number of runs of identical symbols. An algebraic and a probabilistic (entropic) characterization of the exponential growth rate of the number of such sequences, i.e., their information capacity, are obtained by using the methods of multivariate analytic combinatorics, and properties of the capacity as a function of its parameters are stated. The second-order term in the asymptotic expansion of the rate of these sequences is also given, and the typical values of the relevant quantities are derived. Several applications of the results are illustrated, including bounds on codes for weight-preserving and run-preserving channels (e.g., the run-preserving insertion-deletion channel), a sphere-packing bound for channels with sparse error patterns, and the asymptotics of constant-weight sub-block constrained sequences. In addition, the asymptotics of a closely related notion—$q$-ary sequences with fixed Manhattan weight—is briefly discussed, and an application in coding for molecular timing channels is illustrated.

We study properties of binary runlength-limited sequences with additional constraints on their weight and/or the number of runs of identical symbols they contain. An algebraic and a probabilistic (entropic) characterization of the exponential growth rate of the number of such sequences, i.e., their information capacity, are obtained, and properties of the capacity as a function of its parameters are stated. The second-order term in the asymptotic expansion of the rate of these sequences is also given, and the typical values of the relevant quantities are derived. Several applications of the results are illustrated, including bounds on codes for the run-preserving insertion-deletion channel, a sphere-packing bound for channels with sparse error patterns, and the asymptotics of constant-weight sub-block constrained sequences. A full version of this paper, containing the proofs of all the statements, as well as some additional material, is accessible at: https://arxiv.org/abs/2105.04617.

The paper derives the optimal second-order coding rate for the continuous-time Poisson channel. We also obtain bounds on the third-order coding rate. This is the first instance of a second-order result for a continuous-time channel. The converse proof hinges on a novel construction of an output distribution induced by Wyner's discretized channel and the construction of an appropriate ϵ-net of the input probability simplex. While the achievability proof follows the general program to prove the third-order term for non-singular discrete memoryless channels put forth by Polyanskiy, several non-standard techniques-such as new definitions and bounds on the probabilities of typical sets using logarithmic Sobolev inequalities-are employed to handle the continuous nature of the channel.

Tandem-duplication-random-loss (TDRL) is an important genome rearrangement operation studied in evolutionary biology. This paper investigates some of the formal properties of TDRL operations on the symmetric group (the space of permutations over an n-set). In particular, the cardinality of "balls" of radius one in the TDRL metric, as well as the cardinality of the maximum intersection of two such balls, are determined. The corresponding problems for the so-called mirror (or palindromic) TDRL rearrangement operations are also solved. The results represent an initial step in the study of error correction and reconstruction problems in this context, and are of potential interest in DNA-based data storage applications.

This paper studies the error correction problem for bit-shift channels with the so-called (d,k) input constraints (where successive 1's are required to be separated by at least d and at most k zeros). Bounds on the size of optimal (d,k)-constrained codes correcting any given number of bit-shifts are derived, with a focus on their asymptotic form in the large block-length limit. The upper bound is obtained by a packing argument, while the lower bound follows from a construction based on a family of integer lattices. Several properties of (d,k)-constrained sequences that may be of independent interest are established as well; in particular, the exponential growth rate of the number of (d,k)-constrained constant-weight sequences is characterized.

The paper derives the optimal second-order coding rate for the continuous-time Poisson channel. This is the first instance of a second-order result for a continuous-time channel. The converse proof hinges on a novel construction of an output distribution induced by Wyner's discretized channel and the construction of an appropriate ε-net of the input probability simplex. An extended version of this paper is accessible at [1].

This paper is concerned with the problem of error-free communication over the i.i.d. duplication channel which acts on a transmitted sequence x1· · · xnby inserting a random number of copies of each symbol x next to the original symbol. The random variables representing the numbers of inserted copies at each position i are independent and take values in {0, 1, . . . , r}, where r is a fixed parameter. A more general model in which blocks of ℓ consecutive symbols are being duplicated, and which is inspired by DNA-based data storage systems wherein the stored molecules are subject to tandem-duplication mutations, is also analyzed. A construction of optimal codes correcting all patterns of errors of this type is described, and the zero-error capacity of the duplication channel-the largest rate at which information can be transmitted through it in an error-free manner-is determined for each ℓ and r.

The fundamental limits of communication over state-dependent discrete memoryless channels with noiseless feedback are studied, under the assumption that the communicating parties are allowed to use variable-length coding schemes. Various cases are analyzed, with the employed coding schemes having either bounded or unbounded codeword lengths, and with state information revealed to the encoder and/or decoder in a strictly causal, causal, or non-causal manner. In each of these settings, necessary and sufficient conditions for positivity of the zero-error capacity are obtained and it is shown that, whenever the zero-error capacity is positive, it equals the conventional vanishing-error capacity. Moreover, it is shown that the vanishing-error capacity of state-dependent channels is not increased by the use of feedback and variable-length coding. Both these kinds of capacities of state-dependent channels with feedback are thus fully characterized.

This work is motivated by the problem of error correction in bit-shift channels with the so-called (d, k) input constraints (where successive 1's are required to be separated by at least d and at most k zeros, 0 <; d <; k <; ∞). Bounds on the size of optimal (d, k)-constrained codes correcting a fixed number of bit-shifts are derived, with a focus on their asymptotic behavior in the large block-length limit. The upper bound is obtained by a packing argument, while the lower bound follows from a construction based on a family of integer lattices. Several properties of (d, k)-constrained sequences that may be of independent interest are established as well; in particular, the exponential growth rate of the number of (d, k)-constrained constant-weight sequences is characterized. The results are relevant for magnetic and optical information storage systems, reader-to-tag RFID channels, and other communication models where bit-shift errors are dominant and where (d, k)-constrained sequences are used for modulation.

The zero-error capacity of state-dependent channels with noiseless feedback is determined, under the assumption that the transmitter and the receiver are allowed to use variable-length coding schemes. Various cases are analyzed, with the employed coding schemes having either bounded or unbounded codeword lengths and with state information revealed to the encoder and/or decoder in a strictly causal, causal, or noncausal manner. In each of these settings, necessary and sufficient conditions for positivity of the zero-error capacity are obtained and it is shown that, whenever the zero-error capacity is positive, it equals the conventional vanishing-error capacity. A comparison of the results with the recently solved fixed-length case is given.

Motivated by communication channels in which the transmitted sequences are subjected to random permutations, as well as by certain DNA storage systems, we study the error control problem in settings where the information is stored/transmitted in the form of multisets of symbols from a given finite alphabet. A general channel model is assumed in which the transmitted multisets are potentially impaired by insertions, deletions, substitutions, and erasures of symbols. Several constructions of error-correcting codes for this channel are described, and bounds on the size of optimal codes correcting any given number of errors are derived. The construction based on the notion of Sidon sets in finite Abelian groups is shown to be optimal, in the sense of the asymptotic scaling of code redundancy, for any error radius and alphabet size. It is also shown to be optimal in the stronger sense of maximal code cardinality in various cases.

This paper is motivated by the error-control problem in communication channels in which the transmitted sequences are subjected to random permutations, in addition to being impaired with insertions, deletions, substitutions, and erasures of symbols. Bounds on the size of optimal codes in this setting are derived, and their asymptotic behavior examined in the fixed-minimum-distance regime. A family of codes correcting these types of errors is described and is shown to be asymptotically optimal for some sets of parameters. The corresponding error-detection problem is also analyzed.

A $ B_h $ set (or Sidon set of order $ h $) in an Abelian group $ G $ is any subset $ \{b_0, b_1, \ldots,b_{n}\} $ of $ G $ with the property that all the sums $ b_{i_1} + \cdots + b_{i_h} $ are different up to the order of the summands. Let $ \phi(h,n) $ denote the order of the smallest Abelian group containing a $ B_h $ set of cardinality $ n + 1 $. It is shown that ${\scriptstyle\lim_{h \to \infty} \frac{ \phi(h,n) }{ h^n } = \frac{1}{n! \ \delta_{\sc l}(\triangle^n)}},$ where $ \delta_{\sc l}(\triangle^n) $ is the lattice packing density of an $ n $-simplex in Euclidean space. This determines the asymptotics exactly in cases where this density is known ($ n \leq 3 $) and gives improved bounds on $ \phi(h,n) $ in the remaining cases. The corresponding geometric characterization of bases of order $ h $ in finite Abelian groups in terms of lattice coverings by simplices is also given.

A zero-error coding scheme of asymptotic rate log2(1 + √5) - 1 was recently described for a communication channel composed of parallel asynchronous lines satisfying the so-called no switch assumption. We prove that this is in fact the highest rate attainable, i.e., the zero-error capacity of this channel.

The objects of study of this paper are communication channels in which the dominant type of noise are symbol shifts, the main motivating examples being timing and bit-shift channels. Two channel models are introduced and their zeroerror capacities and zero-error-detection capacities determined by explicit constructions of optimal codes. Model A can be informally described as follows: 1) The information is stored in an n-cell register, where each cell is either empty or contains a particle of one of P possible types and 2) due to the imperfections of the device each of the particles may be shifted several cells away from its original position over time. Model B is an abstraction of a single-server queue: 1) The transmitter sends packets from a P-ary alphabet through a queuing system with an infinite buffer and a first-in-first-out service procedure and 2) each packet is being processed by the server for a random number of time slots. More general models including additional types of noise that the particles/packets can experience are also studied, as are the continuous-time versions of these problems.

We analyze the problem of zero-error communication through timing channels that can be interpreted as discrete-time queues with bounded waiting times. The channel model includes the following assumptions: 1) time is slotted; 2) at most N particles are sent in each time slot; 3) every particle is delayed in the channel for a number of slots chosen randomly from the set {0, 1, ... , K}; and 4) the particles are identical. It is shown that the zero-error capacity of this channel is log r, where r is the unique positive real root of the polynomial xK+1-xK-N. Capacity-achieving codes are explicitly constructed, and a linear-time decoding algorithm for these codes devised. In the particular case N = 1, K = 1, the capacity is equal to φ, where φ = (1 + √5)/2 is the golden ratio, and constructed codes give another interpretation of the Fibonacci sequence.

We investigate certain optimization problems for Shannon information measures, namely, minimization of joint and conditional entropies H(X, Y), H(X|Y), H(Y|X), and maximization of mutual information I(X; Y), over convex regions. When restricted to the so-called transportation polytopes (sets of distributions with fixed marginals), very simple proofs of NP-hardness are obtained for these problems because in that case they are all equivalent, and their connection to the well-known SUBSET SUM and PARTITION problems is revealed. The computational intractability of the more general problems over arbitrary polytopes is then a simple consequence. Further, a simple class of polytopes is shown over which the above problems are not equivalent and their complexity differs sharply, namely, minimization of H(X, Y) and H(Y|X) is trivial, while minimization of H(X|Y) and maximization of I(X; Y) are strongly NP-hard problems. Finally, two new (pseudo)metrics on the space of discrete probability distributions are introduced, based on the so-called variation of information quantity, and NP-hardness of their computation is shown.