Codes in the NRT metric, polynomial invariant theory, and fractional decoding

Abstract

Resumo: Esta tese aborda dois aspectos distintos da Teoria de Codigos: o estudo de codigos lineares sobre metricas diferentes da metrica de Hamming e o estudo da decodificacao de codigos de Reed-Solomon. Na primeira parte desta tese, desenvolve-se a teoria de codigos lineares na metrica de Niederreiter- Rosenbloom-Tsfasman (p-metrica); tais codigos sao chamados de codigos NRT. Desenvolve-se a teoria de polinomios invariantes com o objetivo de estudar o enumerador de shape de codigos NRT auto-duais. Por fim, apresenta-se novas construcoes de codigos NRT auto-duais. Em um segundo momento, estuda-se a família de codigos Reed-Solomon (RS) e codigos Reed-Solomon intercalados (IRS), assim como um metodo para decodificacao colaborativa. Apresenta-se o conceito de decodificacao fracionada e seus principais resultados, em especial um limitante superior para o a-raio de decodificacao. Um novo metodo de decodificacao fracionada para uma classe de codigos de Reed-Solomon e apresentado. Este metodo e capaz de realizar (com alta probabilidade) decodificacao fracionada alem do a-raio de decodificacao. Por fim, uma conexao entre decodificacao fracionada e codigos na p-metrica e apresentada. Palavras-chave: Enumerador de shape. Codigos auto-duais. p-metrica. Codigos de Reed-Solomon. Decodificacao fracionada.

Abstract: This dissertation aims to study two distinct aspects of coding theory: a study of linear codes endowed with non-Hamming metrics and a study of decoding of Reed-Solomon codes. In the first part, the theory of linear codes in the Niederreiter-Rosenbloom-Tsfasman metric (p-metric) is developed. Such codes are called the NRT codes. In order to study the shape enumerator of self-dual NRT codes, we extended the classic results of invariant theory to the case of the NRT metric. Finally, new constructions of self-dual NRT codes are presented. In the second part, we study Reed-Solomon (RS) codes and interleaved Reed- Solomon (IRS) codes and their collaborative decoding. We present the concept of fractional decoding and main results related to it, including an upper bound on the a-decoding radius. We present a new method of fractional decoding of RS codes. This method can with high probability correct errors beyond the adecoding radius of the codes. Finally, we present a connection between fractional decoding and codes endowed with the p-metric. Keywords: Shape enumerator. Self-dual codes. p-metric. Reed-Solomon codes. Fractional decoding.