Name
Title | ||
|---|---|---|
The Log-Volume of Optimal Codes for Memoryless Channels, Asymptotically Within A Few Nats |
Abstract | ||
|---|---|---|
Shannon’s analysis of the fundamental capacity limits for memoryless communication channels has been refined over time. In this paper, the maximum volume $M_ \\mathrm {avg}^{*}(n,\\epsilon )$ of length- $n$ codes subject to an average decoding error probability $\\epsilon $ is shown to satisfy the following tight asymptotic lower and upper bounds as $n \\to \\infty $ : $\\underline {A}_\\epsilon + o(1) \\le \\log M_ \\mathrm {avg}^{*}(n,\\epsilon ) - [nC - \\sqrt {nV_\\epsilon } \\,Q^{-1}(\\epsilon ) + ({1}/{2}) \\log n] \\le \\overline {A}_\\epsilon + o(1)$ , where $C$ is the Shannon capacity, $V_\\epsilon $ is the $\\epsilon $ -channel dispersion, or second-order coding rate, $Q$ is the tail probability of the normal distribution, and the constants $\\underline {A}_\\epsilon $ and $\\overline {A}_\\epsilon $ are explicitly identified. This expression holds under mild regularity assumptions on the channel, including nonsingularity. The gap $\\overline {A}_\\epsilon - \\underline {A}_\\epsilon $ is one nat for weakly symmetric channels in the Cover–Thomas sense, and typically a few nats for other symmetric channels, for the binary symmetric channel, and for the $Z$ channel. The derivation is based on strong large-deviations analysis and refined central limit asymptotics. A random coding scheme that achieves the lower bound is presented. The codewords are drawn from a capacity-achieving input distribution modified by an $O(1/\\sqrt {n})$ correction term. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1109/TIT.2016.2643681 | IEEE Trans. Information Theory |
Keywords | Field | DocType |
Upper bound,Error probability,Monte Carlo methods,Random variables,Channel coding,Dispersion | Binary logarithm,Discrete mathematics,Central limit theorem,Binary symmetric channel,Normal distribution,Combinatorics,Decoding error probability,Upper and lower bounds,Channel capacity,Asymptotic analysis,Mathematics | Journal |
Volume | Issue | ISSN |
63 | 4 | 0018-9448 |
Citations | PageRank | References |
2 | 0.39 | 0 |
Authors | ||
1 | ||