Decodificação de códigos matriciais MDS via matrizes superregulares com simplificação por matrizes de Vandermonde para aplicação em sistemas de armazenamento distribuído

Abstract

Este Trabalho de Conclusão de Curso apresenta os conceitos algébricos fundamentais para a construção de códigos matriciais MDS (Maximum Distance Separable), caracterizados por possuírem distância máxima de separação, oferecendo, assim, maior proteção contra falhas em dispositivos. Esses códigos têm despertado interesse devido à sua capacidade de corrigir erros em rajada, tornando-se altamente eficientes em sistemas sujeitos a falhas correlacionadas. O objetivo deste trabalho é apresentar o algoritmo de decodificação proposto em (CARDELL; CLIMENT; REQUENA, 2013) e (ZANITTI, 2021) para códigos matriciais MDS capazes de corrigir até duas rajadas de erro utilizando matrizes superregulares, bem como propor uma simplificação do procedimento por meio do uso de matrizes superregulares de Vandermonde, reduzindo a complexidade do processo de decodificação sem comprometer sua eficiência. Além disso, propõe-se uma generalização do algoritmo para o caso de três erros, com uma simplificação análoga baseada em matrizes superregulares de Vandermonde. Os códigos estudados são aplicáveis em sistemas de armazenamento distribuído, como os RAIDs (Redundant Array of Independent Disks), e são apresentados como alternativa ao RAID 6, cuja codificação está ligada aos códigos Reed-Solomon e permite a correção de até dois discos com falhas quando suas posições são conhecidas. O diferencial dos algoritmos apresentados neste trabalho está no fato de não ser necessário conhecer previamente a localização dos erros para realizar sua correção.

This work presents the fundamental algebraic concepts involved in the construction of MDS (Maximum Distance Separable) array codes, which are characterized by having maximum separation distance, thereby offering greater protection against device failures. These codes have attracted interest due to their ability to correct burst errors, making them highly efficient in systems subject to correlated failures. The objective of this work is to present the decoding algorithm proposed in (CARDELL; CLIMENT; REQUENA, 2013) and (ZANITTI, 2021) for MDS array codes capable of correcting up to two burst errors using superregular matrices, as well as to propose a simplification of the procedure through the use of Vandermonde superregular matrices, reducing the complexity of the decoding process without compromising its efficiency. In addition, a generalization of the algorithm is proposed for the case of three errors, with an analogous simplification based on Vandermonde superregular matrices. The codes studied are applicable to distributed storage systems, such as RAID (Redundant Array of Independent Disks) architectures, and are presented as an alternative to RAID 6, whose encoding relies on Reed–Solomon codes and enables the correction of up to two disk failures when their positions are known. The distinguishing feature of the algorithms presented in this work lies in the fact that prior knowledge of the error locations is not required for error correction.