The exact order of the optimal sub-exponentially decaying factor in the classical bounds on the error probability of fixed-length codes over a Gallager-symmetric discrete memoryless channel with and without ideal feedback is determined for rates above the critical rate. Regardless of the availability of feedback, it is shown that the order of the optimal sub-exponential factor exhibits a dichotomy. Moreover, the proof technique is used to establish the third-order term in the normal approximation for symmetric channels, where a similar dichotomy is shown to exist.

We introduce a novel mechanism, called timid/bold coding, by which feedback can be used to improve coding performance. For a certain class of DMCs, called compound-dispersion channels, we show that timid/bold coding allows for an improved second-order coding rate compared with coding without feedback. For DMCs that are not compound dispersion, we show that feedback does not improve the second-order coding rate. Thus we completely determine the class of DMCs for which feedback improves the second-order coding rate. An upper bound on the second-order coding rate is provided for compound-dispersion DMCs. We also show that feedback does not improve the second-order coding rate for very noisy DMCs. The main results are obtained by relating feedback codes to certain controlled diffusions.

It is shown that feedback does not improve the second-order coding rate for a class of discrete memoryless channels which complements the class of channels for which feedback is known to improve the second-order coding rate. A refined achievability scheme is presented for the second-order rate when feedback helps. Moreover, for such channels an upper bound is derived on the achievable rate with feedback utilizing a novel proof technique.

The redundancy for universal lossless compression of discrete memoryless sources in Campbell's setting is characterized as a minimax Rényi divergence, which is shown to be equal to the maximal α -mutual information via a generalized redundancy-capacity theorem. Special attention is placed on the analysis of the asymptotics of minimax Rényi divergence, which is determined up to a term vanishing in blocklength.

The redundancy for universal lossless compression in Campbell's setting is characterized as a minimax Rényi divergence, which is shown to be equal to the maximal α-mutual information via a generalized redundancy-capacity theorem. Special attention is placed on the analysis of the asymptotics of minimax Rényi divergence, which is determined up to a term vanishing in blocklength.

The fundamental tradeoff of channel coding per unit cost in the fixed-error probability regime is investigated for discrete memoryless channels in the presence of a free input symbol. The speed of convergence to the capacity per unit cost in the absence of feedback is characterized in terms of a characteristic of the channel and cost function, which is referred to as ε-dispersion per unit cost. Further, a sufficient condition for feedback to improve this convergence speed is provided.

Block coding over memoryless channels with causal and noiseless feedback is investigated in the moderate deviations regime. By means of a converse, we show that feedback does not improve the sub-exponential decay rate of the optimal error probability for a certain class of discrete memoryless channels, which includes symmetric ones, as well as the additive white Gaussian noise channel subject to an almost-sure power constraint.

For a singular and symmetric discrete memoryless channel with positive dispersion, the third-order term in the normal approximation is shown to be upper bounded by a constant. This finding completes the characterization of the third-order term for symmetric discrete memoryless channels. The proof method is extended to asymmetric and singular channels with constant composition codes, and its connection to existing results, as well as its limitation in the error exponents regime, are discussed.

For a class of discrete memoryless channels, a simple feedback scheme is shown to improve the second-order term in the normal approximation compared with coding without feedback. Conversely, we provide a new, second-moment-based condition for when feedback does not improve the second-order term.

We provide a refinement of the sphere-packing bound for constant composition codes over asymmetric discrete memoryless channels that improves the subexponential factor in front of the exponent. The order of our subexponential factor is Ω(N-0.5(1+ε+ρR*)) for any ϵ > 0, where ρR* is the left derivative of the sphere-packing exponent at rate R and N is the blocklength.

We consider block codes whose rate converges to the channel capacity with increasing blocklength at a certain speed and examine the best possible decay of the probability of error. For discrete memoryless channels, we prove that a moderate deviation principle holds for all convergence rates between the large deviation and the central limit theorem regimes.

The problem of deriving refined bounds on the sub-exponential factor in the random coding bound for discrete memoryless channels is considered. In particular, for independent identically distributed random code ensembles and for rates above the critical rate, we prove that if a regularity condition is satisfied (respectively, not satisfied), then for any ε > 0 a sub-exponential factor of O(N-0.5(1-ε+ρ̅*R(respectively, O(N-0.5)) is achievable, where N and R are the blocklength and rate, respectively. The term ρ̅*Ris related to the slope of the random coding exponent at rate R.

For the problem of lossless compression of a memoryless source, we give a detailed, precise characterization of the best achievable error probability, in the “moderate error probability” regime. This is the asymptotic setting where the probability of error decays to zero while at the same time the rate converges to the entropy at a speed no faster than 1/√N. These results combine some of the essential benefits of earlier analyses in terms of error exponents and of Gaussian approximation. Analogous results for the problem of hypothesis testing are also established.

We provide a refinement of the sphere-packing bound for constant composition codes over discrete memoryless channels that improves the pre-factor in front of the exponential term. The order of our pre-factor is O(N-1/2(1+ρ*R)), where ρ*Ris related to the slope of the sphere-packing exponent and N is the blocklength.

Necessary and sufficient conditions for approximation of a general channel by a general source are proved. For the special case of a deterministic channel input, which corresponds to source simulation, we prove a stronger necessary condition. As the approximation criteria, vanishing variational distance between the original and the approximated quantity is used for both of the problems. Both necessary and sufficient conditions for the two problems are based on some individual properties of the sources and the channel and are relatively easy to evaluate. In particular, unlike prior results for this problem, our results do not require solving an optimization problem to test simulatability. The results are illustrated with several nonergodic examples.

We describe a scheme for rate-distortion with distributed encoding in which the sources to be compressed contain a common component. We show that this scheme is optimal in some situations and that it strictly improves upon existing schemes, which do not make full use of common components. This establishes that independent quantization followed by independent binning is not optimal for the two-encoder problem with a distortion constraint on one source. We also show that independent quantization and binning is suboptimal for the three-encoder problem in which the goal is to reproduce one of the sources losslessly. This provides a counterexample that is fundamentally different from one provided earlier by Körner and Marton. The proofs rely on the binary analogue of the entropy power inequality and the existence of a rate loss for the binary symmetric Wyner-Ziv problem.

Moderate deviation behavior of coding for discrete-memoryless channels is investigated. That is, we consider block codes whose rate converges to the channel capacity from below with increasing block length with a certain rate and examine the best ‘sub-exponential’ decay in the maximal probability of error. We prove that a moderate deviation principle (M.D.P.) holds for all convergence rates between the large deviation and the central limit theorem regimes, under some mild assumptions on the channel. The rate function of the M.D.P. is explicitly characterized.

In this paper, the bit-search type irregular decimation algorithms, that are used within linear-feedback shift register (LFSR)-based stream ciphers, are investigated. In particular, bit-search generator (BSG) and and its variant ABSG are concentrated on and two different setups are considered for the analysis. In the first case, the input is assumed to be an$m$-sequence; it is shown that all possible output sequences can be classified into two sets, each of which is characterized by the equivalence of their elements up to shifts. Furthermore, it is proved that the cardinality of each of these sets is equal to the period of one of its elements and subsequently the (upper and lower) bounds on the expected output period (assuming that no subperiods exist) are derived. In the second setup, we work in a probabilistic framework and assume that the input sequence is evenly distributed (i.e., independent and identically distributed (i.i.d.) Bernoulli process with probability$1/2$). Under these assumptions, closed-form expressions are derived for the distribution of the output length and the output rate, which is shown to be asymptotically Gaussian-distributed and concentrated around the mean with exponential tightness.