We put forward an ample framework for coding based on upper probabilities, or more generally on normalized monotone set-measures, and model accordingly noisy transmission channels and decoding errors. Two inverse problems are considered. In the first case, a decoder is given and one looks for channels of a specified family over which that decoder would work properly. In the second and more ambitious case, it is codes which are given, and one looks for channels over which those codes would ensure the required error correction capabilities. Upper probabilities allow for a solution of the two inverse problems in the case of usual codes based on checking Hamming distances between codewords: one can equivalently check suitable upper probabilities of the decoding errors. This soon extends to “odd” codeword distances for DNA strings as used in DNA word design, where instead, as we prove, not even the first unassuming inverse problem admits of a solution if one insists on channel models based on “usual” probabilities.

Coding theory: A general framework and two inverse problems

BORTOLUSSI, LUCA;FRANZOI, LAURA;SGARRO, ANDREA
2015-01-01

Abstract

We put forward an ample framework for coding based on upper probabilities, or more generally on normalized monotone set-measures, and model accordingly noisy transmission channels and decoding errors. Two inverse problems are considered. In the first case, a decoder is given and one looks for channels of a specified family over which that decoder would work properly. In the second and more ambitious case, it is codes which are given, and one looks for channels over which those codes would ensure the required error correction capabilities. Upper probabilities allow for a solution of the two inverse problems in the case of usual codes based on checking Hamming distances between codewords: one can equivalently check suitable upper probabilities of the decoding errors. This soon extends to “odd” codeword distances for DNA strings as used in DNA word design, where instead, as we prove, not even the first unassuming inverse problem admits of a solution if one insists on channel models based on “usual” probabilities.
File in questo prodotto:
File Dimensione Formato  
FundamentaInformaticae2015.pdf

Accesso chiuso

Descrizione: pdf editoriale
Tipologia: Documento in Versione Editoriale
Licenza: Digital Rights Management non definito
Dimensione 134.89 kB
Formato Adobe PDF
134.89 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11368/2856201
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact