The Random Coding Bound Is Tight for the Average Linear Code or Lattice

In 1973, Gallager proved that the random-coding bound is exponentially tight for the random code ensemble at all rates, even below expurgation. This result explained that the random-coding exponent does not achieve the expurgation exponent due to the properties of the random ensemble, irrespective of the utilized bounding technique. It has been conjectured that this same behavior holds true for a random ensemble of linear codes. This conjecture is proved in this paper. In addition, it is shown that this property extends to Poltyrev's random-coding exponent for a random ensemble of lattices.

• Publication year

  2013

• Venue

  IEEE Transactions on Information Theory

• Publication date

  2013-07-21

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/TIT.2015.2496308arXiv 1307.5524
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Lattice Coding for Signals and Networks: Lattice shaping

  2014cited by this paper
• Lattice Coding for Signals and Networks: References

  2014cited by this paper
• A Simple Proof for the Existence of “Good” Pairs of Nested Lattices

  2012cited by this paper
• Lower bounds on the error probability of block codes based on improvements on de Caen's inequality

  2004cited by this paper
• On the asymptotic accuracy of the union bound

  2004cited by this paper
• Random codes: minimum distances and error exponents

  2002cited by this paper
• A lower bound on the probability of a union

  1997influential reference
• Averaging bounds for lattices and linear codes

  1997cited by this paper
• On coding without restrictions for the AWGN channel

  1993cited by this paper
• Sphere Packings, Lattices and Groups

  1990cited by this paper
• The random coding bound is tight for the average code (Corresp.)

  1973cited by this paper
• Information Theory and Reliable Communication

  1969influential reference
• A modified form of Siegel's mean-value theorem

  1955cited by this paper
• A Mean Value Theorem in Geometry of Numbers

  1945cited by this paper
• IEEE TRANSACTIONS ON INFORMATION THEORY, to appear 1 Finite Dimensional Infinite Constellations

  year unknowncited by this paper

• Broadcast Approach Meets Network Coding for Ultra-Reliable and Low-Latency Data Streaming

  2026cites this paper
• Concatenated Codes for Short-Molecule DNA Storage with Sequencing Channels of Positive Zero-Undetected-Error Capacity

  2026cites this paper
• Leveraging AES Padding: dBs for Nothing and FEC for Free in IoT Systems

  2024cites this paper
• Broadcast Approach Meets Network Coding for Data Streaming

  2022cites this paper
• Dual Coding Concatenation for Burst-Error Correction in Probabilistic Amplitude Shaping

  2022cites this paper
• Codebook Mismatch can be Fully Compensated by Mismatched Decoding

  2022cites this paper
• Arikan meets Shannon: Polar codes with near-optimal convergence to channel capacity

  2020cites this paper
• Polar Codes’ Simplicity, Random Codes’ Durability

  2019cites this paper
• Lattice-Based Coding to Enhance Error Performance of the Hidden Direct Sequence Spread Spectrum

  2019cites this paper
• Guessing Random Additive Noise Decoding With Symbol Reliability Information (SRGRAND)

  2019cites this paper
• Capacity-achieving decoding by guessing noise

  2018cites this paper
• A Joint Typicality Approach to Compute–Forward

  2018cites this paper
• Capacity-Achieving Guessing Random Additive Noise Decoding

  2018cites this paper
• Rate-Energy Tradeoff and Decoding Error Probability-Energy Tradeoff for SWIPT in Finite Code Length

  2017influential citation
• Non-Random Coding Error Bounds for Lattices

  2016cites this paper
• A Joint Typicality Approach to Algebraic Network Information Theory

  2016cites this paper
• Exact evaluation of the Random coding Error probability and Error Exponent

  2014cites this paper
• Lattice Coding for Signals and Networks: A Structured Coding Approach to Quantization, Modulation and Multiuser Information Theory

  2014cites this paper