Information--bit error rate and false positives in an MDS code

Previous Article
Close values of shifted modular inversions and the decisional modular inversion hidden number problem
AMC Home
This Issue
Next Article
Identifying codes of degree 4 Cayley graphs over Abelian groups

May 2015, 9(2): 149-168. doi: 10.3934/amc.2015.9.149

Information--bit error rate and false positives in an MDS code

José Gómez-Torrecillas ^1, , F. J. Lobillo ^1, and Gabriel Navarro ^2,

1.	Department of Algebra and CITIC-UGR, University of Granada, E18071 Granada, Spain, Spain
2.	Department of Computer Sciences and AI, and CITIC-UGR, University of Granada, E18071 Granada, Spain

Received July 2013 Published May 2015

Abstract
Related Papers

In this paper, a computation of the input-redundancy weight enumerator is presented. This is used to improve the theoretical approximation of the information--bit error rate, in terms of the channel bit--error rate, in a block transmission through a discrete memoryless channel. Since a bounded distance reproducing encoder is assumed, we introduce the here-called false positive, a decoding failure with no information-symbol error, and we estimate the probability that this event occurs. As a consequence, a new performance analysis of an MDS code is proposed.

Keywords: block error--correcting code, information--bit error rate (iBER), bit--error rate (BER), MDS code, false positive..

Mathematics Subject Classification: Primary: 94B70, 94B0.

Citation: José Gómez-Torrecillas, F. J. Lobillo, Gabriel Navarro. Information--bit error rate and false positives in an MDS code. Advances in Mathematics of Communications, 2015, 9 (2) : 149-168. doi: 10.3934/amc.2015.9.149

References:

[1]	C. Desset, B. Macq and L. Vandendorpe, Computing the word-, symbol-, and bit-error rates for block error-correcting codes, IEEE Trans. Commun., 52 (2004), 910-921. doi: 10.1109/TCOMM.2004.829509.
[2]	R. Dodunekova and S. M. Dodunekov, Sufficient conditions for good and proper error-detecting codes, IEEE Trans. Inf. Theory, 43 (1997), 2023-2026. doi: 10.1109/18.641570.
[3]	R. Dodunekova and S. M. Dodunekov, The MMD codes are proper for error detection, IEEE Trans. Inf. Theory, 48 (2002), 3109-3111. doi: 10.1109/TIT.2002.805082.
[4]	R. Dodunekova, S. M. Dodunekov and E. Nikolova, A survey on proper codes, Discrete Appl. Math., 156 (2008), 1499-1509. doi: 10.1016/j.dam.2005.06.014.
[5]	M. El-Khamy, New Approaches to the Analysis and Design of Reed-Solomon Related Codes, Ph.D thesis, California Institute of Technology, 2007.
[6]	M. El-Khamy and R. J. McEliece, Bounds on the average binary minimum distance and the maximum likelihood performance of Reed Solomon codes, in 42nd Allerton Conf. Commun. Control Comput., 2004.
[7]	M. El-Khamy and R. J. McEliece, The partition weight enumerator of MDS codes and its applications, in Int. Symp. Inf. Theory, 2005, 926-930. doi: 10.1109/ISIT.2005.1523473.
[8]	A. Faldum, J. Lafuente, G. Ochoa and W. Willems, Error probabilities for bounded distance decoding, Des. Codes Crypt., 40 (2006), 237-252. doi: 10.1007/s10623-006-0010-x.
[9]	M. P. C. Fossorier, Critical point for maximum likelihood decoding of linear block codes, IEEE Commun. Letters, 9 (2005), 817-819. doi: 10.1109/LCOMM.2005.1506713.
[10]	J. Han, P. H. Siegel and P. Lee, On the probability of undetected error for overextended Reed-Solomon codes, IEEE Trans. Inf. Theory, 52 (2006), 3662-3669. doi: 10.1109/ITW.2006.1633800.
[11]	T. Kasami and S. Lin, On the probability of undetected error for the maximum distance separable codes, IEEE Trans. Commun., COM-32 (1984), 998-1006. doi: 10.1109/TCOM.1984.1096175.
[12]	J. MacWilliams, A theorem on the distribution of weights in a systematic code, Bell System Tech. J., 42 (1963), 79-94. doi: 10.1002/j.1538-7305.1963.tb04003.x.
[13]	F. J. MacWilliams and N. J. A. Sloane, The Theory of Error Correcting Codes, North Holland Publishing Co., 1977.
[14]	J. Riordan, Combinatorial Identities, Robert E. Krieger Publishing Co., Huntington, New York, 1979.
[15]	S. Roman, Coding and Information Theory, Springer-Verlag, New York, 1992.
[16]	W. A. Stein et al., Sage Mathematics Software (Version 5.9), The Sage Development Team, 2012, available at http://www.sagemath.org
[17]	D. Torrieri, The information-bit error rate for block codes, IEEE Trans. Commun., COM-32 (1984), 474-476. doi: 10.1109/TCOM.1984.1096082.
[18]	D. Torrieri, Information-bit, information-symbol, and decoded-symbol error rates for linear block codes, IEEE Trans. Commun., 36 (1988), 613-617. doi: 10.1109/26.1477.
[19]	J. H. van Lint and R. M. Wilson, A Course in Combinatorics, 2nd edition, Cambridge University Press, 2001. doi: 10.1017/CBO9780511987045.
[20]	K.-P. Yar, D.-S. Yoo and W. Stark, Performance of RS coded $M$-ary modulation with and without symbol overlapping, IEEE Trans. Commun., 56 (2008), 445-453. doi: 10.1109/TCOMM.2008.050229.

show all references

References:

[1]	C. Desset, B. Macq and L. Vandendorpe, Computing the word-, symbol-, and bit-error rates for block error-correcting codes, IEEE Trans. Commun., 52 (2004), 910-921. doi: 10.1109/TCOMM.2004.829509.
[2]	R. Dodunekova and S. M. Dodunekov, Sufficient conditions for good and proper error-detecting codes, IEEE Trans. Inf. Theory, 43 (1997), 2023-2026. doi: 10.1109/18.641570.
[3]	R. Dodunekova and S. M. Dodunekov, The MMD codes are proper for error detection, IEEE Trans. Inf. Theory, 48 (2002), 3109-3111. doi: 10.1109/TIT.2002.805082.
[4]	R. Dodunekova, S. M. Dodunekov and E. Nikolova, A survey on proper codes, Discrete Appl. Math., 156 (2008), 1499-1509. doi: 10.1016/j.dam.2005.06.014.
[5]	M. El-Khamy, New Approaches to the Analysis and Design of Reed-Solomon Related Codes, Ph.D thesis, California Institute of Technology, 2007.
[6]	M. El-Khamy and R. J. McEliece, Bounds on the average binary minimum distance and the maximum likelihood performance of Reed Solomon codes, in 42nd Allerton Conf. Commun. Control Comput., 2004.
[7]	M. El-Khamy and R. J. McEliece, The partition weight enumerator of MDS codes and its applications, in Int. Symp. Inf. Theory, 2005, 926-930. doi: 10.1109/ISIT.2005.1523473.
[8]	A. Faldum, J. Lafuente, G. Ochoa and W. Willems, Error probabilities for bounded distance decoding, Des. Codes Crypt., 40 (2006), 237-252. doi: 10.1007/s10623-006-0010-x.
[9]	M. P. C. Fossorier, Critical point for maximum likelihood decoding of linear block codes, IEEE Commun. Letters, 9 (2005), 817-819. doi: 10.1109/LCOMM.2005.1506713.
[10]	J. Han, P. H. Siegel and P. Lee, On the probability of undetected error for overextended Reed-Solomon codes, IEEE Trans. Inf. Theory, 52 (2006), 3662-3669. doi: 10.1109/ITW.2006.1633800.
[11]	T. Kasami and S. Lin, On the probability of undetected error for the maximum distance separable codes, IEEE Trans. Commun., COM-32 (1984), 998-1006. doi: 10.1109/TCOM.1984.1096175.
[12]	J. MacWilliams, A theorem on the distribution of weights in a systematic code, Bell System Tech. J., 42 (1963), 79-94. doi: 10.1002/j.1538-7305.1963.tb04003.x.
[13]	F. J. MacWilliams and N. J. A. Sloane, The Theory of Error Correcting Codes, North Holland Publishing Co., 1977.
[14]	J. Riordan, Combinatorial Identities, Robert E. Krieger Publishing Co., Huntington, New York, 1979.
[15]	S. Roman, Coding and Information Theory, Springer-Verlag, New York, 1992.
[16]	W. A. Stein et al., Sage Mathematics Software (Version 5.9), The Sage Development Team, 2012, available at http://www.sagemath.org
[17]	D. Torrieri, The information-bit error rate for block codes, IEEE Trans. Commun., COM-32 (1984), 474-476. doi: 10.1109/TCOM.1984.1096082.
[18]	D. Torrieri, Information-bit, information-symbol, and decoded-symbol error rates for linear block codes, IEEE Trans. Commun., 36 (1988), 613-617. doi: 10.1109/26.1477.
[19]	J. H. van Lint and R. M. Wilson, A Course in Combinatorics, 2nd edition, Cambridge University Press, 2001. doi: 10.1017/CBO9780511987045.
[20]	K.-P. Yar, D.-S. Yoo and W. Stark, Performance of RS coded $M$-ary modulation with and without symbol overlapping, IEEE Trans. Commun., 56 (2008), 445-453. doi: 10.1109/TCOMM.2008.050229.

[1]	Andrew Klapper, Andrew Mertz. The two covering radius of the two error correcting BCH code. Advances in Mathematics of Communications, 2009, 3 (1) : 83-95. doi: 10.3934/amc.2009.3.83
[2]	Selim Esedoḡlu, Fadil Santosa. Error estimates for a bar code reconstruction method. Discrete and Continuous Dynamical Systems - B, 2012, 17 (6) : 1889-1902. doi: 10.3934/dcdsb.2012.17.1889
[3]	Sanghoon Kwon, Seonhee Lim. Equidistribution with an error rate and Diophantine approximation over a local field of positive characteristic. Discrete and Continuous Dynamical Systems, 2018, 38 (1) : 169-186. doi: 10.3934/dcds.2018008
[4]	Marcelo Muniz S. Alves, Luciano Panek, Marcelo Firer. Error-block codes and poset metrics. Advances in Mathematics of Communications, 2008, 2 (1) : 95-111. doi: 10.3934/amc.2008.2.95
[5]	Yanyan Gao, Qin Yue, Xinmei Huang, Yun Yang. Two classes of cyclic extended double-error-correcting Goppa codes. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022003
[6]	Muhammad Ajmal, Xiande Zhang. New optimal error-correcting codes for crosstalk avoidance in on-chip data buses. Advances in Mathematics of Communications, 2021, 15 (3) : 487-506. doi: 10.3934/amc.2020078
[7]	René B. Christensen, Carlos Munuera, Francisco R. F. Pereira, Diego Ruano. An algorithmic approach to entanglement-assisted quantum error-correcting codes from the Hermitian curve. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2021072
[8]	Ben A. Vanderlei, Matthew M. Hopkins, Lisa J. Fauci. Error estimation for immersed interface solutions. Discrete and Continuous Dynamical Systems - B, 2012, 17 (4) : 1185-1203. doi: 10.3934/dcdsb.2012.17.1185
[9]	Rua Murray. Approximation error for invariant density calculations. Discrete and Continuous Dynamical Systems, 1998, 4 (3) : 535-557. doi: 10.3934/dcds.1998.4.535
[10]	El Miloud Zaoui, Marc Laforest. Stability and modeling error for the Boltzmann equation. Kinetic and Related Models, 2014, 7 (2) : 401-414. doi: 10.3934/krm.2014.7.401
[11]	Robert S. Strichartz. Average error for spectral asymptotics on surfaces. Communications on Pure and Applied Analysis, 2016, 15 (1) : 9-39. doi: 10.3934/cpaa.2016.15.9
[12]	María Chara, Ricardo A. Podestá, Ricardo Toledano. The conorm code of an AG-code. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021018
[13]	Qichun Wang, Chik How Tan, Pantelimon Stănică. Concatenations of the hidden weighted bit function and their cryptographic properties. Advances in Mathematics of Communications, 2014, 8 (2) : 153-165. doi: 10.3934/amc.2014.8.153
[14]	Yujuan Li, Guizhen Zhu. On the error distance of extended Reed-Solomon codes. Advances in Mathematics of Communications, 2016, 10 (2) : 413-427. doi: 10.3934/amc.2016015
[15]	Zhongliang Deng, Enwen Hu. Error minimization with global optimization for difference of convex functions. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1027-1033. doi: 10.3934/dcdss.2019070
[16]	Xiaoying Han, Jinglai Li, Dongbin Xiu. Error analysis for numerical formulation of particle filter. Discrete and Continuous Dynamical Systems - B, 2015, 20 (5) : 1337-1354. doi: 10.3934/dcdsb.2015.20.1337
[17]	Xin-He Miao, Jein-Shan Chen. Error bounds for symmetric cone complementarity problems. Numerical Algebra, Control and Optimization, 2013, 3 (4) : 627-641. doi: 10.3934/naco.2013.3.627
[18]	Benedict Geihe, Martin Rumpf. A posteriori error estimates for sequential laminates in shape optimization. Discrete and Continuous Dynamical Systems - S, 2016, 9 (5) : 1377-1392. doi: 10.3934/dcdss.2016055
[19]	Anders C. Hansen. A theoretical framework for backward error analysis on manifolds. Journal of Geometric Mechanics, 2011, 3 (1) : 81-111. doi: 10.3934/jgm.2011.3.81
[20]	Ye Sun, Daniel B. Work. Error bounds for Kalman filters on traffic networks. Networks and Heterogeneous Media, 2018, 13 (2) : 261-295. doi: 10.3934/nhm.2018012

2021 Impact Factor: 1.015

Tools

Metrics

Other articles
by authors

on AIMS
José Gómez-Torrecillas F. J. Lobillo Gabriel Navarro
on Google Scholar
José Gómez-Torrecillas F. J. Lobillo Gabriel Navarro

[Back to Top]