Codeword Distinguishability in Minimum Diversity Decoding

TitleCodeword Distinguishability in Minimum Diversity Decoding
Publication TypeJournal Article
Year of Publication2006
AuthorsSgarro A, Bortolussi L
JournalJournal Of Discrete Mathematical Sciences And Cryptography
Volume9
Pages487–502
Keywordscodeword distinguishability, Coding theory, possibility theory
Abstract

We re-take a coding theoretic notion which goes back to Cl. Shannon: codeword distinguishability. This notion is standard in zero-error information theory, but its bearing is definitely wider and it may help to better understand new forms of coding, e.g. DNA word design. In our approach, the underlying decoding principle is very simple and very general: one decodes by trying to minimise the diversity (in the simplest case the Hamming distance) between a codeword and the output sequence observed at the end of the noisy transmission channel. Symmetrically and equivalently, one may use maximum-similarity decoders and and codeword confusabilities. The operational meaning of codewoord distinguishability is made clear by a reliability criterion, which generalises the well-known criterion on minimum Hamming distance for error-correcting codes. We investigate the formal properties of distinguishabilities versus diversities; these two notions are deeply related, and yet essentially different. An encoding theorem is put forward; as a case study we examine a channel of cryptographic interest.