SPC product codes, graphs with cycles and Kostka numbers

Autor(es)

Cardell, Sara D. ^[1] ; Climent, Joan-Josep ^[2] ; Martin, Alberto Lopez ^[3]

Afiliação do(s) autor(es)

^[1] Univ Estadual Campinas, Inst Matemat Estat & Comp Cient, Campinas, SP - Brazil

^[2] Univ Alacant, Dept Matemat, Alacant - Spain

^[3] Inst Nacl Matemat Pura & Aplicada, Rio De Janeiro - Brazil

• Tipo de documento: Artigo Científico
• Fonte: REVISTA DE LA REAL ACADEMIA DE CIENCIAS EXACTAS FISICAS Y NATURALES SERIE A-MATEMATICAS; v. 113, n. 4, p. 3751-3765, OCT 2019.
• Citações Web of Science: 0

Resumo

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. (AU)

• Processo FAPESP: 13/25977-7 - Segurança e confiabilidade da informação: teoria e prática
• Beneficiário: Marcelo Firer
• Modalidade de apoio: Auxílio à Pesquisa - Temático