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

Metrics

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

Other articles
by authors

[Back to Top]