American Institute of Mathematical Sciences

Advanced
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

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.  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-179. doi: 10.1016/j.ins.2004.07.011.  Google Scholar

[3]

R. Diestel, Graph Theory, Springer-Verlag, New York, 2000. doi: 10.1007/b100033.  Google Scholar

[4]

P. Elias, Coding for noisy channels, IRE International Convention Record, pt. 4, 1955, 37-46. Google Scholar

[5]

P. Giblin, Graphs, Surfaces and Homology, 3rd edition, Cambridge Univ. Press, New York, 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), Physica-Verlag, 1990, 339-346.  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-11. 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-89. Google Scholar

[9]

A. Muqaibel, Enhanced upper bound for erasure recovery in SPC product codes, ETRI J., 31 (2009), 518-524. Google Scholar

[10]

D. M. Rankin and T. A. Gulliver, Single parity check product codes, IEEE Trans. Commun., 49 (2001), 1354-1362. 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-88. 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-207. 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-179. doi: 10.1016/j.ins.2004.07.011.  Google Scholar

[3]

R. Diestel, Graph Theory, Springer-Verlag, New York, 2000. doi: 10.1007/b100033.  Google Scholar

[4]

P. Elias, Coding for noisy channels, IRE International Convention Record, pt. 4, 1955, 37-46. Google Scholar

[5]

P. Giblin, Graphs, Surfaces and Homology, 3rd edition, Cambridge Univ. Press, New York, 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), Physica-Verlag, 1990, 339-346.  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-11. 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-89. Google Scholar

[9]

A. Muqaibel, Enhanced upper bound for erasure recovery in SPC product codes, ETRI J., 31 (2009), 518-524. Google Scholar

[10]

D. M. Rankin and T. A. Gulliver, Single parity check product codes, IEEE Trans. Commun., 49 (2001), 1354-1362. 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-88. 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]

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 & Applied Analysis, , () : -. 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 & 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 & 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 & 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 & Heterogeneous Media, 2007, 2 (4) : 761-777. doi: 10.3934/nhm.2007.2.761
[16]

Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68.

[17]

Oded Schramm. Hyperfinite graph limits. Electronic Research Announcements, 2008, 15: 17-23. doi: 10.3934/era.2008.15.17
[18]

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
[19]

John Kieffer and En-hui Yang. Ergodic behavior of graph entropy. Electronic Research Announcements, 1997, 3: 11-16.

[20]

Roberto De Leo, James A. Yorke. The graph of the logistic map is a tower. Discrete & Continuous Dynamical Systems, 2021, 41 (11) : 5243-5269. doi: 10.3934/dcds.2021075

2020 Impact Factor: 0.935

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy