Coding Theory : A General Framework and Two Inverse Problems

• Autorzy: Bortolussi L. , Dinu L. P. , Franzoi L. , Sgarro A.

Identyfikatory

DOI

10.3233/FI-2015-1277

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Shannon theory; coding theory; decoding errors; upper probabilities

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 141, nr 4
• Strony: 297--310
• Opis fizyczny: Bibliogr. 8 poz.

Twórcy

autor

Bortolussi L.

• Dept. of Mathematics and Geosciences, University of Trieste, Italy

autor

Dinu L. P.

• University of Bucharest, Faculty of Mathematics and Computer Science Academiei 14, 010014, Bucharest, Romania

autor

Franzoi L.

• University of Bucharest, Faculty of Mathematics and Computer Science Academiei 14, 010014, Bucharest, Romania

autor

Sgarro A.

• Dept. of Mathematics and Geosciences, University of Trieste, Italy

Bibliografia

• [1] L. Bortolussi, A. Sgarro. Possibilistic Coding: Error Detection vs. Error Correction. in Combining Soft Computing and Statistical Methods in Data Analysis, ed. by Ch. Borgelt et alt., Advances in Intelligent and Soft Computing 77, Springer Verlag, 41-48, 2010.
• [2] A. Condon, R.M. Corn, and A. Marathe. On Combinatorial DNA Word Design. Journal of Computational Biology, 8(3), 201-220, November 2001.
• [3] I. Csiszár and J. Körner. Information Theory, 2nd ed., Cambridge University Press, 2011
• [4] L. Bortolussi, L.P. Dinu, A. Sgarro. Spearman Permutation Distances and Shannon’s Distinguishability. Fundamenta Informaticae, 118 (3) 245-252, 2012.
• [5] P. Klir, T.A. Folger. Fuzzy Sets, Uncertainty, and Information. Prentice Hall, 1988.
• [6] J. van Lint. Introduction to Coding Theory. Springer Verlag, Berlin, 1999.
• [7] A. Sgarro. Possibilistic Information Theory: a Coding-Theoretic Approach. Fuzzy Sets and Systems, 132-1, 11-32, 2002.
• [8] P. Walley. Statistical Reasoning with Imprecise Probabilities. Chapman and Hall, London, 1991.