Repository logo
 

The Error Probability of Generalized Perfect Codes via the Meta-Converse

Accepted version
Peer-reviewed

Type

Article

Change log

Authors

Vazquez-Vilar, Gonzalo 
Guillen i Fabregas, Albert  ORCID logo  https://orcid.org/0000-0003-2795-1124
Verdu, Sergio 

Abstract

We introduce a definition of perfect and quasiperfect codes for discrete symmetric channels based on the packing and covering properties of generalized spheres whose shape is tilted using an auxiliary probability measure. This notion generalizes previous definitions of perfect and quasiperfect codes and encompasses maximum distance separable codes. The error probability of these codes, whenever they exist, is shown to coincide with the estimate provided by the metaconverse lower bound. We illustrate how the proposed definition naturally extends to cover almost-lossless source-channel coding and lossy compression.

Description

Keywords

Shannon theory, perfect codes, quasi-perfect codes, maximum likelihood decoding, finite blocklength analysis, meta-converse, hypothesis testing, channel coding, joint source-channel coding, rate distortion theory

Journal Title

IEEE TRANSACTIONS ON INFORMATION THEORY

Conference Name

Journal ISSN

0018-9448
1557-9654

Volume Title

65

Publisher

Institute of Electrical and Electronics Engineers (IEEE)

Rights

All rights reserved
Sponsorship
European Research Council (725411)
ERC