Codificação e decodificação de códigos matriciais MDS via matrizes superregulares para correção de erros em rajada

Abstract

Este trabalho de conclusão de curso apresenta uma construção de códigos matriciais MDS (Maximum Distance Separable) com o objetivo de abordar uma estratégia de correção de erros em rajada nestes códigos. Para obter um código com esta propriedade, a matriz de verificação de paridade é construída utilizando matrizes superregulares, em especial as matrizes de Vandermonde e as matrizes de Cauchy, e a matriz companheira de Frobenius obtida através de um polinômio primitivo sobre Fq[x]. A partir desta construção, apresenta-se um algoritmo de decodificação para correção de uma rajada de erros em códigos matriciais MDS com parâmetros [m + k, k, m + 1] sobre Fb , do qual b refere-se ao comprimento da rajada de erro, para todo m ≥ 2 e de até duas rajadas de erros em códigos matriciais MDS com parâmetros [m + k, k, m + 1] sobre Fb , para todo m ≥ 4. Além disso são apresentados alguns exemplos para correção de três rajadas de erros. Os códigos matriciais são códigos corretores de erros bidimensionais que possuem como principal característica a habilidade de corrigir erros em rajada (burst of errors), ou seja, erros que ocorrem em bits consecutivos. Já os códigos de máxima distância de separação, MDS, são códigos em que a distância mínima é a máxima possível. Essa característica é importante pois na teoria da codificação a distância mínima está relacionada com a capacidade de correção de erros do código, além de fornecer proteção máxima contra falhas de um dispositivo para uma dada quantidade de redundância. O algoritmo proposto é uma generalização do algoritmo apresentado por CARDELL, CLIMENT e REQUENA 2013.

This work presents a construction of MDS Array Codes (Maximum Distance Separable Array Codes) in order to approach a burst correction strategy in these codes. To obtain a code with this property, the parity check matrix is constructed using superregular matrices, in particular Vandermonde matrices and Cauchy matrices, and the Frobenius companion matrix obtained through a primitive polynomial over Fq[x]. Based on this construction, a decoding algorithm is presented to correct a burst of errors in MDS array codes with parameters [m + k, k, m + 1] over Fb , where b refers to the length of the error burst, for all m ≥ 2 and up to two bursts of errors in MDS array codes with parameters [m + k, k, m + 1] over Fb , for all m ≥ 4. In addition, some examples are presented to correct three bursts of errors. Array codes are two-dimensional error correction codes whose main characteristic is the ability to correct burst errors, that is, errors that occur in consecutive bits. The Maximum Distance Separable codes, MDS, are codes in which the minimum distance is the maximum possible. This characteristic is important because, in coding theory, the minimum distance is related to the error correction capacity of the code in addition to providing maximum protection against failures of a device for a given amount of redundancy. The proposed algorithm is a generalization of the algorithm presented by CARDELL, CLIMENT e REQUENA 2013.