SPC product codes, graphs with cycles and Kostka numbers
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10045/95531
Title: | SPC product codes, graphs with cycles and Kostka numbers |
---|---|
Authors: | Cardell, Sara D. | Climent, Joan-Josep | López Martín, Alberto |
Research Group/s: | Grupo de Álgebra y Geometría (GAG) |
Center, Department or Service: | Universidad de Alicante. Departamento de Matemáticas |
Keywords: | SPC code | Erasure channel | Erasure pattern | Bipartite graph | Kostka number |
Knowledge Area: | Álgebra |
Issue Date: | Oct-2019 |
Publisher: | Springer International Publishing |
Citation: | Revista de la Real Academia de Ciencias Exactas, Físicas y Naturales. Serie A. Matemáticas. 2019, 113(4): 3751-3765. doi:10.1007/s13398-019-00698-1 |
Abstract: | The SPC product code is a very popular error correction code with four as its minimum distance. Over the erasure channel, it is supposed to correct up to three erasures. However, this code can correct a higher number of erasures under certain conditions. A codeword of the SPC product code can be represented either by an erasure pattern or by a bipartite graph, where the erasures are represented by an edge. When the erasure contains erasures that cannot be corrected, the corresponding graph contains cycles. In this work we determine the number of strict uncorrectable erasure patterns (bipartite graphs with cycles) for a given size with a fixed number of erasures (edges). Since a bipartite graph can be unequivocally represented by its biadjacency matrix, it is enough to determine the number of non-zero binary matrices whose row and column sum vectors are different from one. At the same time, the number of matrices with prescribed row and column sum vectors can be evaluated in terms of the Kostka numbers associated with Young tableaux. |
Sponsor: | The first author was supported by CAPES (Brazil) and FAPESP by Grant 2013/25977-7. The second author was partially supported by Spanish Grants AICO/2017/128 of the Generalitat Valenciana and VIGROB-287 of the Universitat d’Alacant. The third author would also like to thank the Max-Planck Institut für Mathematik in Bonn for the wonderful working conditions and stimulating environment over the duration of his visit when this work was developed. The third author was supported by CAPES-Brazil. |
URI: | http://hdl.handle.net/10045/95531 |
ISSN: | 1578-7303 (Print) | 1579-1505 (Online) |
DOI: | 10.1007/s13398-019-00698-1 |
Language: | eng |
Type: | info:eu-repo/semantics/article |
Rights: | © The Royal Academy of Sciences, Madrid 2019 |
Peer Review: | si |
Publisher version: | https://doi.org/10.1007/s13398-019-00698-1 |
Appears in Collections: | INV - GAG - Artículos de Revistas |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
2019_Cardell_etal_RACSAM_final.pdf | Versión final (acceso restringido) | 575,77 kB | Adobe PDF | Open Request a copy |
2019_Cardell_etal_RACSAM_preprint.pdf | Preprint (acceso abierto) | 319,34 kB | Adobe PDF | Open Preview |
Items in RUA are protected by copyright, with all rights reserved, unless otherwise indicated.