# American Institute of Mathematical Sciences

February  2016, 10(1): 11-28. doi: 10.3934/amc.2016.10.11

## An approach to the performance of SPC product codes on the erasure channel

 1 Instituto de Matemática, Estatística e Computação Científica, Universidade Estadual de Campinas (UNICAMP), R. Sérgio Buarque de Holanda, 651, Cidade Universitária, Campinas - SP, 13083-859, Brazil 2 Departament de Matemàtiques, Universitat d'Alacant, Ap. Correus 99, E-03080, Alacant, Spain

Received  November 2014 Revised  September 2015 Published  March 2016

Product codes can be used to correct errors or recover erasures. In this work we consider the simplest form of a product code, this is, the single parity check (SPC) product code. This code has a minimum distance of four and is thus guaranteed to recover all single, double, and triple erasure patterns. The code is actually capable of recovering a higher number of erasure patterns. We count the number of uncorrectable erasure patterns of size $n \times n$ with $t$ erasures, for $t=8$, $2n-3$, $2n-2$ and $2n-1$, using the relation between erasure patterns and bipartite graphs.
Citation: Sara D. Cardell, Joan-Josep Climent. An approach to the performance of SPC product codes on the erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 11-28. doi: 10.3934/amc.2016.10.11
##### References:
 [1] M. Z. Abu-Sbeih, On the number of spanning trees of $K_n$ and $K_{m,n}$,, Discrete Math., 84 (1990), 205. doi: 10.1016/0012-365X(90)90377-T. Google Scholar [2] R. Amutha, K. Verraraghavan and S. K. Srivatsa, Recoverability study of SPC product codes under erasure decoding,, Inf. Sci., 173 (2005), 169. doi: 10.1016/j.ins.2004.07.011. Google Scholar [3] R. Diestel, Graph Theory,, Springer-Verlag, (2000). doi: 10.1007/b100033. Google Scholar [4] P. Elias, Coding for noisy channels,, IRE International Convention Record, (1955), 37. Google Scholar [5] P. Giblin, Graphs, Surfaces and Homology, 3rd edition,, Cambridge Univ. Press, (2010). doi: 10.1017/CBO9780511779534. Google Scholar [6] N. Hartsfield and J. S. Werth, Spanning trees of the complete bipartite graph,, in Topics in Combinatorics and Graph Theory (eds. R. Bodendieck and R. Henn), (1990), 339. Google Scholar [7] M. A. Kousa, A novel approach for evaluating the performance of SPC product codes under erasure decoding,, IEEE Trans. Commun., 50 (2002), 7. Google Scholar [8] M. A. Kousa and A. H. Mugaibel, Cell loss recovery using two-dimensional erasure correction for ATM networks,, in Proc. 7th Int. Conf. Telecommun. Syst., (1999), 85. Google Scholar [9] A. Muqaibel, Enhanced upper bound for erasure recovery in SPC product codes,, ETRI J., 31 (2009), 518. Google Scholar [10] D. M. Rankin and T. A. Gulliver, Single parity check product codes,, IEEE Trans. Commun., 49 (2001), 1354. Google Scholar [11] J. M. Simmons and R. G. Gallager, Design of error detection scheme for class C service in ATM,, IEEE/ACM Trans. Netw., 2 (1994), 80. Google Scholar

show all references

##### References:
 [1] M. Z. Abu-Sbeih, On the number of spanning trees of $K_n$ and $K_{m,n}$,, Discrete Math., 84 (1990), 205. doi: 10.1016/0012-365X(90)90377-T. Google Scholar [2] R. Amutha, K. Verraraghavan and S. K. Srivatsa, Recoverability study of SPC product codes under erasure decoding,, Inf. Sci., 173 (2005), 169. doi: 10.1016/j.ins.2004.07.011. Google Scholar [3] R. Diestel, Graph Theory,, Springer-Verlag, (2000). doi: 10.1007/b100033. Google Scholar [4] P. Elias, Coding for noisy channels,, IRE International Convention Record, (1955), 37. Google Scholar [5] P. Giblin, Graphs, Surfaces and Homology, 3rd edition,, Cambridge Univ. Press, (2010). doi: 10.1017/CBO9780511779534. Google Scholar [6] N. Hartsfield and J. S. Werth, Spanning trees of the complete bipartite graph,, in Topics in Combinatorics and Graph Theory (eds. R. Bodendieck and R. Henn), (1990), 339. Google Scholar [7] M. A. Kousa, A novel approach for evaluating the performance of SPC product codes under erasure decoding,, IEEE Trans. Commun., 50 (2002), 7. Google Scholar [8] M. A. Kousa and A. H. Mugaibel, Cell loss recovery using two-dimensional erasure correction for ATM networks,, in Proc. 7th Int. Conf. Telecommun. Syst., (1999), 85. Google Scholar [9] A. Muqaibel, Enhanced upper bound for erasure recovery in SPC product codes,, ETRI J., 31 (2009), 518. Google Scholar [10] D. M. Rankin and T. A. Gulliver, Single parity check product codes,, IEEE Trans. Commun., 49 (2001), 1354. Google Scholar [11] J. M. Simmons and R. G. Gallager, Design of error detection scheme for class C service in ATM,, IEEE/ACM Trans. Netw., 2 (1994), 80. Google Scholar
 [1] Carolyn Mayer, Kathryn Haymaker, Christine A. Kelley. Channel decomposition for multilevel codes over multilevel and partial erasure channels. Advances in Mathematics of Communications, 2018, 12 (1) : 151-168. doi: 10.3934/amc.2018010 [2] Joan-Josep Climent, Diego Napp, Raquel Pinto, Rita Simões. Decoding of $2$D convolutional codes over an erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 179-193. doi: 10.3934/amc.2016.10.179 [3] JiYoon Jung, Carl Mummert, Elizabeth Niese, Michael Schroeder. On erasure combinatorial batch codes. Advances in Mathematics of Communications, 2018, 12 (1) : 49-65. doi: 10.3934/amc.2018003 [4] Daniel Roggen, Martin Wirz, Gerhard Tröster, Dirk Helbing. Recognition of crowd behavior from mobile sensors with pattern analysis and graph clustering methods. Networks & Heterogeneous Media, 2011, 6 (3) : 521-544. doi: 10.3934/nhm.2011.6.521 [5] Juan Manuel Pastor, Silvia Santamaría, Marcos Méndez, Javier Galeano. Effects of topology on robustness in ecological bipartite networks. Networks & Heterogeneous Media, 2012, 7 (3) : 429-440. doi: 10.3934/nhm.2012.7.429 [6] 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 [7] 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 [8] Serhii Dyshko. On extendability of additive code isometries. Advances in Mathematics of Communications, 2016, 10 (1) : 45-52. doi: 10.3934/amc.2016.10.45 [9] Maximiliano Fernandez, Javier Galeano, Cesar Hidalgo. Bipartite networks provide new insights on international trade markets. Networks & Heterogeneous Media, 2012, 7 (3) : 399-413. doi: 10.3934/nhm.2012.7.399 [10] Emmanuel Charbit, Irène Charon, Gérard Cohen, Olivier Hudry, Antoine Lobstein. Discriminating codes in bipartite graphs: bounds, extremal cardinalities, complexity. Advances in Mathematics of Communications, 2008, 2 (4) : 403-420. doi: 10.3934/amc.2008.2.403 [11] Hirobumi Mizuno, Iwao Sato. L-functions and the Selberg trace formulas for semiregular bipartite graphs. Conference Publications, 2003, 2003 (Special) : 638-646. doi: 10.3934/proc.2003.2003.638 [12] Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68. [13] Oded Schramm. Hyperfinite graph limits. Electronic Research Announcements, 2008, 15: 17-23. doi: 10.3934/era.2008.15.17 [14] J. William Hoffman. Remarks on the zeta function of a graph. Conference Publications, 2003, 2003 (Special) : 413-422. doi: 10.3934/proc.2003.2003.413 [15] John Kieffer and En-hui Yang. Ergodic behavior of graph entropy. Electronic Research Announcements, 1997, 3: 11-16. [16] Giuseppe Buttazzo, Filippo Santambrogio. Asymptotical compliance optimization for connected networks. Networks & Heterogeneous Media, 2007, 2 (4) : 761-777. doi: 10.3934/nhm.2007.2.761 [17] Roy H. Goodman. NLS bifurcations on the bowtie combinatorial graph and the dumbbell metric graph. Discrete & Continuous Dynamical Systems - A, 2019, 39 (4) : 2203-2232. doi: 10.3934/dcds.2019093 [18] Olof Heden. The partial order of perfect codes associated to a perfect code. Advances in Mathematics of Communications, 2007, 1 (4) : 399-412. doi: 10.3934/amc.2007.1.399 [19] 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 [20] Mario Roy, Mariusz Urbański. Random graph directed Markov systems. Discrete & Continuous Dynamical Systems - A, 2011, 30 (1) : 261-298. doi: 10.3934/dcds.2011.30.261

2018 Impact Factor: 0.879