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

Sara D.  Cardell; Joan-Josep  Climent

doi:10.3934/amc.2016.10.11

Article Contents

2016, Volume 10, Issue 1: 11-28. Doi: 10.3934/amc.2016.10.11

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

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
2.
Departament de Matemàtiques, Universitat d'Alacant, Ap. Correus 99, E-03080, Alacant

Received: November 2014

Revised: September 2015

Published: February 2016

Abstract Related Papers Cited by

Abstract

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:

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

Citation:

Related Papers

Cited by

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.