Source-linked AI summary
Decoding Error Probability of the Random Code Ensemble over the Erasure Channel
Chin Hei Chan
TL;DR
Decoding over the q-ary erasure channel is studied for general codes, including nonlinear codes, where linear-code algebraic methods do not directly apply. The paper gives explicit average error probabilities for three decoding principles and derives asymptotic error exponents for exponentially sized random-code ensembles.
Problem
General nonlinear codes lack the algebraic structure and translation symmetry that make decoding-error distributions tractable for linear codes.
Method
The paper analyzes the ensemble of all (n, M)_q codes under unambiguous, list, and maximum-likelihood decoding, then studies (n, q^{Rn})_q codes asymptotically.
Results
Explicit average decoding error probabilities are obtained for all three decoding principles, together with error exponents for unambiguous, list, and maximum-likelihood decoding.
Takeaways & Limitations
The results characterize average decoding performance for general random code ensembles over the erasure channel, including nonlinear codes.
Takeaways & Limitations
For list decoding, the stated error-exponent result applies only when λ < R; if λ ≥ R, no decoding error occurs and the exponent is negative infinity.
Abstract
from arXiv · showhide
In this paper, we provide explicit formulas for the average decoding error probabilities of the ensemble of all $(n,M)_q$ codes over the erasure channel under unambiguous, list and maximum-likelihood decoding principles. Moreover, we derive the asymptotic error exponents for the ensemble of all $(n,q^{Rn})_q$ codes.
1 Introduction
The paper extends erasure-channel decoding analysis from linear codes to the random ensemble of all q-ary codes, deriving explicit average error probabilities and asymptotic error exponents under three decoding principles.
- Motivation: The q-ary erasure-channel setting supports unambiguous, list, and maximum-likelihood decoding, motivated by applications including Internet communication and distributed storage.
- Problem: For nonlinear codes, incorrigible-set distributions are difficult to compute because algebraic rank structure and translation symmetry are absent.
- Main results: The random ensemble of all (n, M)_q codes yields explicit average decoding-error probabilities under all three decoding principles.
- Main results: For M = q^(Rn), the paper derives asymptotic error exponents as n tends to infinity with fixed rate R.
- Main results: Average decoding is efficient when R, or adjusted rate R−λ for exponential list size, is below the erasure-channel capacity 1−ε.
- Scope: When λ ≥ R, the code size does not exceed the list size, so no decoding error occurs and the error exponent is negative infinity.
2 Preliminaries
This section defines the q-ary erasure channel, general codes, the three decoding principles, and incorrigible-set distributions used to express decoding error probabilities. It also explains why the resulting formulas extend linear-code formulations to nonlinear codes.
- Channel and codes: The q-ary erasure channel transmits each symbol correctly with probability 1−ε or erases it with probability ε, with input alphabet Fq.
- Channel and codes: An (n, M)q code is an M-subset of Fq^n, and C(r) contains the codewords compatible with received word r.
- Three decoding principles: Unambiguous decoding succeeds only when C(r) has one codeword, list decoding permits at most L codewords, and maximum likelihood selects uniformly from C(r).
- Incorrigible-set distributions: An L-incorrigible set is an erased-coordinate set E for which more than L codewords remain compatible; its distribution counts such sets by size and center codeword.
- Error probabilities: The overall unsuccessful decoding probabilities are obtained from average incorrigible-set distributions, with list size 1 reducing to unambiguous decoding.
- Scope and limitation: The general-code formulas extend linear-code formulas, but nonlinear codes lack the algebraic structure needed to compute incorrigible-set distributions directly in general.
3 Proof of Theorem 1
This section averages decoding quantities over the ensemble formed by selecting distinct codewords uniformly, then uses combinatorial counting to prove Theorem 1. The proof shows that the expected quantities are independent of the transmitted codeword and yields the three ensemble error formulas.
- Ensemble averaging: The random ensemble selects M distinct codewords x1,…,xM from Fq^n, with each (n, M)q code represented with equal multiplicity.
- Combinatorial counting: For each erased-coordinate-set size i, the proof computes expected counts of compatible codewords by counting codewords matching the transmitted word outside the erased set.
- Ensemble averaging: The relevant expectations are independent of the transmitted codeword, allowing averaging over all message indices to obtain the ensemble result.
- Proof of Theorem 1: Theorem 1 is proved separately for unambiguous decoding, list decoding, and maximum likelihood decoding by substituting the corresponding corollary statements into the general formulas.
- Proof of Theorem 1: The resulting substitutions establish the stated equations and complete the proof of Theorem 1.
4 Proof of Theorem 2
The proof defines error exponents for the random code ensemble, analyzes fixed and exponential list-size regimes through case-based asymptotics, and recovers known exponential-list exponents.
- The ensemble error probabilities are expressed as q^{-n(T+o(1))} for unambiguous, maximum-likelihood, and fixed-list-size decoding, with corresponding nonnegative exponents.
- Unambiguous decoding is handled as list decoding with list size 1, reducing the proof to fixed- and exponential-list-size analyses.
- Fixed List-Size Regime: For fixed list size, the proof partitions t into four cases and derives the governing function f(t) from the asymptotic summand expression.
- Exponential List-Size Regime: For exponential list size L=q^{λn}, the proof similarly divides the analysis into cases, with g(t)=h(t)+t logq ε+(1−t)logq(1−ε).
- Exponential List-Size Regime: The maximizer of g is t0=ε when ε lies in the relevant interval; otherwise, under λ<R<min{1−ε+λ,1}, it occurs at t=1−R+λ.
- Exponential List-Size Regime: The resulting exponential-list exponent has the divergence form min D(Ṕ_Y|X||P_Y|X|Q) subject to mutual information at most R−λ.
- Theorem 2 independently derives Merhav’s fixed- and exponential-size random-coding exponents, while Theorem 1 additionally supplies exact finite-length average error formulas.