Source-linked AI summary
Information Spectrum Approach to Second-Order Coding Rate in Channel Coding
Masahito Hayashi
TL;DR
The paper addresses how to evaluate channel-coding performance at second order for general channel sequences, especially near capacity where first-order evaluations are less informative. It uses the information-spectrum method to derive a general asymptotic characterization and applies it to several channel models. The resulting evaluation is optimal under a constant error constraint and is not always matched by the Gallager bound in the second-order setting.
Problem
Near capacity, exponential error evaluations may omit constant factors, making the accuracy of existing bounds unclear for finite blocklengths.
Method
The paper derives a general information-spectrum formula based on the normalized logarithm of a channel likelihood ratio, then applies its asymptotic behavior to specific channel models.
Results
The paper characterizes the optimum second-order transmission rate for general channel sequences and derives results for discrete memoryless, cost-constrained, additive Markovian, and Gaussian energy-constrained channels.
Takeaways & Limitations
Second-order coding analysis gives a better evaluation near capacity and shows that the Gallager bound is not optimal for the second-order rate in the reported setting.
Takeaways & Limitations
The paper identifies quantum extensions as difficult because of noncommutativity and leaves the order of the third-order coding rate unresolved.
Abstract
from arXiv · showhide
Second-order coding rate of channel coding is discussed for general sequence of channels. The optimum second-order transmission rate with a constant error constraint $ε$ is obtained by using the information spectrum method. We apply this result to the discrete memoryless case, the discrete memoryless case with a cost constraint, the additive Markovian case, and the Gaussian channel case with an energy constraint. We also clarify that the Gallager bound does not give the optimum evaluation in the second-order coding rate.
I. INTRODUCTION
The paper develops an information-spectrum treatment of second-order channel coding for general channel sequences and applies it to several important channel models. It also motivates second-order analysis near capacity, where first-order or exponential evaluations may be insufficient.
- Motivation: Second-order coding rates provide a finer evaluation of average error probability when the coding length is close to capacity.The paper contrasts this with first-order coding rates and notes an application to phase-error evaluation in quantum key distribution.
- Method: The information-spectrum method characterizes general channel performance through the normalized logarithm of a likelihood ratio.The method first derives a general asymptotic formula and then evaluates the stochastic behavior of this quantity for a specific channel.
- Discrete memoryless channels: For the discrete memoryless case, second-order behavior is governed by the variance of the logarithmic likelihood ratio rather than only the law-of-large-numbers behavior of the first-order rate.The direct part is described as a central-limit-theorem application, while the converse requires information-spectrum analysis for general input distributions.
- Cost and energy constraints: Cost-constrained discrete memoryless and Gaussian channels require all codewords to satisfy the constraint, creating a direct-part difficulty absent from the corresponding first-order analyses.A zero-error-limit subcode argument for average cost cannot be applied when the target average error converges to a fixed threshold.
- Scope and results: The paper obtains an optimum second-order transmission rate under a fixed error probability and applies it to discrete memoryless, cost-constrained, additive Markovian, and Gaussian energy-constrained channels.The discrete memoryless result is expressed using the Gaussian distribution, while related quantities play the same role in other cases.
III. SECOND ORDER CODING RATE IN ADDITIVE MARKOVIAN CHANNEL
The additive Markovian channel is modeled through an irreducible transition matrix, whose stationary behavior defines the channel capacity and second-order quantities. The paper then calculates these quantities for this channel.
- Channel model: The additive Markovian channel uses an irreducible transition matrix on X = {1, . . . , d}, with arithmetic based on mod d.Its n-use conditional distribution is formed from transitions of the additive noise process.
- Channel model: The marginal distribution approaches the stationary distribution determined by the eigenvector associated with eigenvalue 1.The stationary distribution is used to define the normalized entropy of the noise process.
- Capacity: The additive Markovian channel capacity is defined analogously to the discrete memoryless channel capacity.The paper denotes this capacity by C^AM_W.
- Second-order quantities: The paper defines variance and second-order information quantities for the additive Markovian case and calculates them explicitly.These quantities determine the second-order coding-rate evaluation in this channel model.
IV. SECOND ORDER CODING RATE IN GAUSSIAN CHANNEL
The Gaussian channel is studied under an energy constraint because unconstrained input power makes capacity diverge. The paper derives the corresponding second-order quantities and compares its evaluation with the Gallager bound near capacity.
- Gaussian channel model: Without an input restriction, the Gaussian channel capacity diverges, motivating the quadratic cost constraint c(x) = x^2 with maximum cost S.The constrained maximum mutual information is attained by the distribution P_M.
- Gaussian channel model: The constrained Gaussian channel uses the maximum mutual information under E_P x^2 ≤ S to characterize its capacity.The associated capacity expression is introduced after identifying the maximizing input distribution.
- Second-order rate: The paper defines Gaussian second-order quantities and states a theorem for their evaluation under the energy constraint.The theorem is introduced after noting that the finite-cardinality assumption does not apply to R.
- Comparison with the Gallager bound: When -3 ≤ R2 ≤ 2, the difference between the present evaluation and the Gallager bound is not small, so the present evaluation is better.The paper contrasts this with exponential-rate behavior and illustrates both evaluations in Fig. 2.
VI. PROPERTIES OF V +
This section constructs a five-distribution example and studies the relations among the associated information-spectrum quantities. A lemma establishes convergence properties that support the resulting set relationships.
- A. Example: The example defines five joint distributions W1, W2, W3, W4, and W5 on binary random variables A and B under specified conditions.The construction includes both dependent and independent pairs of variables.
- A. Example: The constructed distributions satisfy relationships among Z0, Z1, Z2, W1, W2, W3, W4, and W5, including Z1 ∩ Z2 = {W5}.These relationships are summarized in Fig. 3.
- A. Example: Lemma 1 uses alternating maps E_A and E_B to show that the successive distributions converge to a limiting distribution Q∞.The proof tracks decreasing divergences between successive iterates.
- A. Example: The set V is represented as the convex hull of P and P′, yielding V_{λP+(1−λ)P′,W} = λV_{P,W} + (1−λ)V_{P′,W}.The paper numerically suggests V_{P,W} ≤ V_{P′,W}; Fig. 4 compares the two quantities.
B. Additivity
The additivity results show that capacity and related second-order quantities decompose for product channels, including under additive cost constraints. The proofs use product distributions and divergence inequalities.
- B. Additivity: For product channels, the variance quantity satisfies V_{P×P′,W×W′} = V_{P1,W} + V_{P2,W′}.This decomposition is obtained from the product structure of the combined channel.
- B. Additivity: Channel capacity satisfies an additivity condition for any two channels.The result is stated as a lemma for the product-channel setting.
- B. Additivity: Under stated conditions, the maximum of V_{P,W×W′} equals V^+_{P,W} + V^+_{P′,W′}, implying the corresponding additivity relation.A similar relation is obtained for the associated lower quantity.
- B. Additivity: The same additivity fact holds with cost constraints when the combined cost is c(x) + c′(x′).Thus, constrained capacity also satisfies the additivity condition for product channels.
VII. NOTATIONS OF THE INFORMATION SPECTRUM
This section introduces information-spectrum quantities for general channel sequences by analyzing normalized logarithmic likelihood ratios and their asymptotic behavior. These quantities specialize to mutual information in stationary discrete memoryless channels and extend to additive channels.
- Information-spectrum quantities: General channel analysis uses sequences of input distributions, output distributions, and channel transition matrices.The channel is represented by a sequence W^n(y|x), with corresponding input and output probability sequences.
- Information-spectrum quantities: The information-spectrum method characterizes asymptotic performance through the normalized logarithm of likelihood ratios.The approach separates general asymptotic characterization from special-case analysis of stochastic behavior.
- Special cases: For stationary discrete memoryless channels with i.i.d. inputs, the law of large numbers makes the information-spectrum quantity equal to mutual information I(P,W).This provides the bridge from the general sequence formulation to the discrete memoryless case.
- Special cases: Additive channels are analyzed through the entropy-rate behavior of the additive-noise distribution sequence, including Markovian noise.The formulation introduces corresponding threshold quantities for additive channels.
B. Stochastic limits
This section develops stochastic-limit relations for information-spectrum quantities and uses them to express first- and second-order channel capacities. The resulting general asymptotic formulas include unconstrained and cost-constrained settings.
- Stochastic limits: Probability limit superior and inferior provide the stochastic-limit framework for relating information-spectrum quantities to channel capacities.When both limits coincide, the sequence is assigned a common asymptotic value.
- First-order capacities: The general asymptotic formulas characterize first-order capacities and related quantities for constant error constraints.Theorem 6 is attributed to Verdú–Han and Hayashi–Nagaoka, while relation (39) is identified as new in this paper.
- Second-order coding rate: Theorem 7 gives general formulas for the second-order coding rate using the information-spectrum quantities.The theorem is presented as a unified treatment rather than only a formal generalization.
- Second-order coding rate: The unified second-order formulation shortens the proof of the discrete memoryless result and extends it to cost constraints, Gaussian noise, and additive Markovian noise.These are the four merits explicitly listed by the paper.
- Cost constraint: The same capacity and second-order formulas extend to codes whose inputs satisfy a cost constraint.The constrained input support is restricted to X^n,c,K, and the resulting relations are presented as Theorem 8.
C. Additive case
This section specializes the information-spectrum framework to additive channels, including general probability spaces and additive Markovian settings. It also outlines direct coding arguments that establish the relevant rate bounds.
- Additive channel formulation: Additive channels are represented as W^n(Q^n)(y|x)=Q^n(y−x), with the analysis centered on the additive-noise distributions.The formulation first treats finite input alphabets and then describes an extension to general measurable probability spaces.
- Additive-channel results: The additive-channel second-order relations are obtained from the general formulas and yield the stated additive-case theorem.Theorem 11 provides the relations, and the paper explicitly derives Theorem 4 from them.
- Additive-channel results: The paper identifies cases beyond ε=0 as first established here for the additive-channel relations.Verdú and Han had previously proved the ε=0 case of one corresponding relation.
- Direct part: Random coding constructs codes whose asymptotic rate approaches the target while their error probability is bounded by an information-spectrum quantity.The encoder samples codewords independently according to the chosen input distribution.
- Direct part: For second-order rates, code sizes are selected with logarithm nR1+n^βR2−n^β/2, and the resulting bounds recover the corresponding second-order capacity inequality.The construction uses the same random-coding framework with the first- and second-order terms separated.
B. Converse part
This section proves converse bounds for the general and discrete memoryless cases. The converse uses empirical input distributions and information-spectrum inequalities, while finite-alphabet specialization connects the limits to Gaussian approximations.
- General converse: The converse part lower-bounds asymptotic error probabilities using auxiliary output distributions and the quantities J and J(·,R1|·).The resulting bounds produce the general first- and second-order converse inequalities.
- General converse: The converse applies Hayashi–Nagaoka’s method to an arbitrary sequence of codes and its empirical input distribution.The empirical distribution is formed from the codeword points of each code.
- Discrete memoryless specialization: In the stationary discrete memoryless case, the general second-order theorem is specialized by analyzing empirical distributions and their induced information quantities.The proof controls the number of empirical distributions and establishes uniform convergence over relevant finite-alphabet terms.
- Discrete memoryless specialization: The achievability and converse relations together establish the discrete memoryless second-order result through continuity of the relevant expressions.The paper states that the resulting continuity implication completes the proof of Theorem 2.
- Discrete memoryless specialization: The discrete memoryless converse uses variance calculations and Chebyshev-type bounds to control fluctuations of the information quantities.The variance is expressed through the quantity V′ in the finite-alphabet analysis.
B. Proof of Theorem 3
The proof establishes Theorem 3 by combining information-spectrum relations with converse and direct arguments for discrete memoryless channels, including cost constraints.
- For finite input alphabets, the proof specializes the stationary discrete memoryless channel relations needed for Theorem 3.
- Theorem 3 follows after establishing both inequalities and applying Theorem 9.
- The converse proof extends the argument by replacing empirical distributions with cost-constrained empirical distributions.
- The direct part is reduced to distributions supported on cost-constrained type classes and their uniform distributions.
C. Proof of Theorem 5
Theorem 5 is proved through a direct-part analysis using Gaussian convergence, while the paper situates the result within the general information-spectrum treatment of channel coding.
- The direct part of Theorem 5 is obtained using the discussion in Subsection X-B.
- The relevant normalized quantities converge to a normal distribution as n goes to infinity.
- This Gaussian convergence is uniform when the norm of x is bounded.
- The information-spectrum framework characterizes the optimum second-order rate through the asymptotic behavior of a logarithmic likelihood ratio.
- The channel-coding converse requires optimization over general sequences of input distributions in non-additive-noise cases.
- A quantum extension is possible in principle, but noncommutativity creates considerable difficulty.
APPENDIX
The appendix derives the discrete memoryless second-order rate by analyzing a convex function and showing convergence of the associated optimizing sequence.
- Convexity of ψP is used to select a sequence sn satisfying the relevant channel-rate relation.
- The minimum of the channel-rate expression is then evaluated through the selected sequence.
- sn approaches zero as n goes to infinity because the relevant function is continuous and bounded.
- The resulting limit yields the second-order rate R2.