Minimax Universal Decoding With an Erasure Option

DOI10.1109/TIT.2007.894695MaRDI QIDQ3548849zbMATHOpenAlexFDO

Authors Neri Merhav, Meir Feder

Publication date 21 December 2008

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0604069

Mathematics Subject Classification ID

Decoding (94B35) Rate-distortion theory in information and communication theory (94A34)

Abstract: Motivated by applications of rateless coding, decision feedback, and ARQ, we study the problem of universal decoding for unknown channels, in the presence of an erasure option. Specifically, we harness the competitive minimax methodology developed in earlier studies, in order to derive a universal version of Forney's classical erasure/list decoder, which in the erasure case, optimally trades off between the probability of erasure and the probability of undetected error. The proposed universal erasure decoder guarantees universal achievability of a certain fraction $xi$ of the optimum error exponents of these probabilities (in a sense to be made precise in the sequel). A single--letter expression for $xi$, which depends solely on the coding rate and the threshold, is provided. The example of the binary symmetric channel is studied in full detail, and some conclusions are drawn.

Recommendations

• Minimax optimal universal codeword sets
• A Neyman–Pearson Approach to Universal Erasure and List Decoding
• Minimax noiseless universal coding for Markov sources
• Decoding of Convolutional Codes Over the Erasure Channel
• scientific article; zbMATH DE number 7561729
• Exact Characterization of the Minimax Loss in Error Exponents of Universal Decoders
• Universal decoding for finite-state channels
• Exact Random Coding Exponents for Erasure Decoding
• scientific article; zbMATH DE number 4104869
• Minimax nonredundant channel coding

This page was built for publication: Minimax Universal Decoding With an Erasure Option

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3548849)