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

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

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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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., (1979).
[15]	S. Roman, Coding and Information Theory,, Springer-Verlag, (1992).
[16]	W. A. Stein et al., Sage Mathematics Software (Version 5.9),, The Sage Development Team, (2012).
[17]	D. Torrieri, The information-bit error rate for block codes,, IEEE Trans. Commun., COM-32 (1984), 474. 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. doi: 10.1109/26.1477.
[19]	J. H. van Lint and R. M. Wilson, A Course in Combinatorics,, 2nd edition, (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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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., (1979).
[15]	S. Roman, Coding and Information Theory,, Springer-Verlag, (1992).
[16]	W. A. Stein et al., Sage Mathematics Software (Version 5.9),, The Sage Development Team, (2012).
[17]	D. Torrieri, The information-bit error rate for block codes,, IEEE Trans. Commun., COM-32 (1984), 474. 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. doi: 10.1109/26.1477.
[19]	J. H. van Lint and R. M. Wilson, A Course in Combinatorics,, 2nd edition, (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. 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 & 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 & Continuous Dynamical Systems - A, 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]	Ben A. Vanderlei, Matthew M. Hopkins, Lisa J. Fauci. Error estimation for immersed interface solutions. Discrete & Continuous Dynamical Systems - B, 2012, 17 (4) : 1185-1203. doi: 10.3934/dcdsb.2012.17.1185
[6]	Rua Murray. Approximation error for invariant density calculations. Discrete & Continuous Dynamical Systems - A, 1998, 4 (3) : 535-557. doi: 10.3934/dcds.1998.4.535
[7]	El Miloud Zaoui, Marc Laforest. Stability and modeling error for the Boltzmann equation. Kinetic & Related Models, 2014, 7 (2) : 401-414. doi: 10.3934/krm.2014.7.401
[8]	Robert S. Strichartz. Average error for spectral asymptotics on surfaces. Communications on Pure & Applied Analysis, 2016, 15 (1) : 9-39. doi: 10.3934/cpaa.2016.15.9
[9]	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
[10]	Xiaoying Han, Jinglai Li, Dongbin Xiu. Error analysis for numerical formulation of particle filter. Discrete & Continuous Dynamical Systems - B, 2015, 20 (5) : 1337-1354. doi: 10.3934/dcdsb.2015.20.1337
[11]	Xin-He Miao, Jein-Shan Chen. Error bounds for symmetric cone complementarity problems. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 627-641. doi: 10.3934/naco.2013.3.627
[12]	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
[13]	Benedict Geihe, Martin Rumpf. A posteriori error estimates for sequential laminates in shape optimization. Discrete & Continuous Dynamical Systems - S, 2016, 9 (5) : 1377-1392. doi: 10.3934/dcdss.2016055
[14]	Ye Sun, Daniel B. Work. Error bounds for Kalman filters on traffic networks. Networks & Heterogeneous Media, 2018, 13 (2) : 261-295. doi: 10.3934/nhm.2018012
[15]	John B. Little. The ubiquity of order domains for the construction of error control codes. Advances in Mathematics of Communications, 2007, 1 (1) : 151-171. doi: 10.3934/amc.2007.1.151
[16]	Walter Allegretto, Yanping Lin, Ningning Yan. A posteriori error analysis for FEM of American options. Discrete & Continuous Dynamical Systems - B, 2006, 6 (5) : 957-978. doi: 10.3934/dcdsb.2006.6.957
[17]	Zhongliang Deng, Enwen Hu. Error minimization with global optimization for difference of convex functions. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1027-1033. doi: 10.3934/dcdss.2019070
[18]	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
[19]	Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1
[20]	Irene Márquez-Corbella, Edgar Martínez-Moro, Emilio Suárez-Canedo. On the ideal associated to a linear code. Advances in Mathematics of Communications, 2016, 10 (2) : 229-254. doi: 10.3934/amc.2016003

2017 Impact Factor: 0.564

American Institute of Mathematical Sciences