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

Previous Article
Convolutional codes with a matrix-algebra word-ambient
AMC Home
This Issue
Next Article
New examples of non-abelian group codes

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

Sara D. Cardell ^1, and Joan-Josep Climent ^2,

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

Abstract
Related Papers

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.

Keywords: connected component., SPC code, Erasure channel, bipartite graph, erasure pattern.

Mathematics Subject Classification: Primary: 14G50; Secondary: 97K3.

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

Tools

Metrics

Other articles
by authors

on AIMS
Sara D. Cardell Joan-Josep Climent
on Google Scholar
Sara D. Cardell Joan-Josep Climent

[Back to Top]