# 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-207. doi: 10.1016/0012-365X(90)90377-T. [2] R. Amutha, K. Verraraghavan and S. K. Srivatsa, Recoverability study of SPC product codes under erasure decoding, Inf. Sci., 173 (2005), 169-179. doi: 10.1016/j.ins.2004.07.011. [3] R. Diestel, Graph Theory, Springer-Verlag, New York, 2000. doi: 10.1007/b100033. [4] P. Elias, Coding for noisy channels, IRE International Convention Record, pt. 4, 1955, 37-46. [5] P. Giblin, Graphs, Surfaces and Homology, 3rd edition, Cambridge Univ. Press, New York, 2010. doi: 10.1017/CBO9780511779534. [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), Physica-Verlag, 1990, 339-346. [7] M. A. Kousa, A novel approach for evaluating the performance of SPC product codes under erasure decoding, IEEE Trans. Commun., 50 (2002), 7-11. [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-89. [9] A. Muqaibel, Enhanced upper bound for erasure recovery in SPC product codes, ETRI J., 31 (2009), 518-524. [10] D. M. Rankin and T. A. Gulliver, Single parity check product codes, IEEE Trans. Commun., 49 (2001), 1354-1362. [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-88.

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-207. doi: 10.1016/0012-365X(90)90377-T. [2] R. Amutha, K. Verraraghavan and S. K. Srivatsa, Recoverability study of SPC product codes under erasure decoding, Inf. Sci., 173 (2005), 169-179. doi: 10.1016/j.ins.2004.07.011. [3] R. Diestel, Graph Theory, Springer-Verlag, New York, 2000. doi: 10.1007/b100033. [4] P. Elias, Coding for noisy channels, IRE International Convention Record, pt. 4, 1955, 37-46. [5] P. Giblin, Graphs, Surfaces and Homology, 3rd edition, Cambridge Univ. Press, New York, 2010. doi: 10.1017/CBO9780511779534. [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), Physica-Verlag, 1990, 339-346. [7] M. A. Kousa, A novel approach for evaluating the performance of SPC product codes under erasure decoding, IEEE Trans. Commun., 50 (2002), 7-11. [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-89. [9] A. Muqaibel, Enhanced upper bound for erasure recovery in SPC product codes, ETRI J., 31 (2009), 518-524. [10] D. M. Rankin and T. A. Gulliver, Single parity check product codes, IEEE Trans. Commun., 49 (2001), 1354-1362. [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-88.
 [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] Julia Lieb, Raquel Pinto. A decoding algorithm for 2D convolutional codes over the erasure channel. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021031 [4] 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 [5] Ting Chen, Fusheng Lv, Wenchang Sun. Uniform Approximation Property of Frames with Applications to Erasure Recovery. Communications on Pure and Applied Analysis, 2022, 21 (3) : 1093-1107. doi: 10.3934/cpaa.2022011 [6] Daniel Roggen, Martin Wirz, Gerhard Tröster, Dirk Helbing. Recognition of crowd behavior from mobile sensors with pattern analysis and graph clustering methods. Networks and Heterogeneous Media, 2011, 6 (3) : 521-544. doi: 10.3934/nhm.2011.6.521 [7] 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 [8] Juan Manuel Pastor, Silvia Santamaría, Marcos Méndez, Javier Galeano. Effects of topology on robustness in ecological bipartite networks. Networks and Heterogeneous Media, 2012, 7 (3) : 429-440. doi: 10.3934/nhm.2012.7.429 [9] 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 [10] 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 [11] 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 [12] Maximiliano Fernandez, Javier Galeano, Cesar Hidalgo. Bipartite networks provide new insights on international trade markets. Networks and Heterogeneous Media, 2012, 7 (3) : 399-413. doi: 10.3934/nhm.2012.7.399 [13] 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 [14] 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 [15] Giuseppe Buttazzo, Filippo Santambrogio. Asymptotical compliance optimization for connected networks. Networks and Heterogeneous Media, 2007, 2 (4) : 761-777. doi: 10.3934/nhm.2007.2.761 [16] Andrea Seidl, Stefan Wrzaczek. Opening the source code: The threat of forking. Journal of Dynamics and Games, 2022  doi: 10.3934/jdg.2022010 [17] Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68. [18] Oded Schramm. Hyperfinite graph limits. Electronic Research Announcements, 2008, 15: 17-23. doi: 10.3934/era.2008.15.17 [19] 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 [20] John Kieffer and En-hui Yang. Ergodic behavior of graph entropy. Electronic Research Announcements, 1997, 3: 11-16.

2021 Impact Factor: 1.015