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

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

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

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.
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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[5]

M. El-Khamy, New Approaches to the Analysis and Design of Reed-Solomon Related Codes, Ph.D thesis,, California Institute of Technology, (2007). Google Scholar

[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). Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[13]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error Correcting Codes,, North Holland Publishing Co., (1977). Google Scholar

[14]

J. Riordan, Combinatorial Identities,, Robert E. Krieger Publishing Co., (1979). Google Scholar

[15]

S. Roman, Coding and Information Theory,, Springer-Verlag, (1992). Google Scholar

[16]

W. A. Stein et al., Sage Mathematics Software (Version 5.9),, The Sage Development Team, (2012). Google Scholar

[17]

D. Torrieri, The information-bit error rate for block codes,, IEEE Trans. Commun., COM-32 (1984), 474. doi: 10.1109/TCOM.1984.1096082. Google Scholar

[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. Google Scholar

[19]

J. H. van Lint and R. M. Wilson, A Course in Combinatorics,, 2nd edition, (2001). doi: 10.1017/CBO9780511987045. Google Scholar

[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. Google Scholar

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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[5]

M. El-Khamy, New Approaches to the Analysis and Design of Reed-Solomon Related Codes, Ph.D thesis,, California Institute of Technology, (2007). Google Scholar

[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). Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[13]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error Correcting Codes,, North Holland Publishing Co., (1977). Google Scholar

[14]

J. Riordan, Combinatorial Identities,, Robert E. Krieger Publishing Co., (1979). Google Scholar

[15]

S. Roman, Coding and Information Theory,, Springer-Verlag, (1992). Google Scholar

[16]

W. A. Stein et al., Sage Mathematics Software (Version 5.9),, The Sage Development Team, (2012). Google Scholar

[17]

D. Torrieri, The information-bit error rate for block codes,, IEEE Trans. Commun., COM-32 (1984), 474. doi: 10.1109/TCOM.1984.1096082. Google Scholar

[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. Google Scholar

[19]

J. H. van Lint and R. M. Wilson, A Course in Combinatorics,, 2nd edition, (2001). doi: 10.1017/CBO9780511987045. Google Scholar

[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. Google Scholar

[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

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (4)
  • HTML views (0)
  • Cited by (1)

[Back to Top]