Construction of cyclic codes with large minimum distance from power functions over odd characteristic finite fields

Resumo Técnico: Construção de Códigos Cíclicos com Grande Distância Mínima a partir de Funções de Potência sobre Campos Finitos de Característica Ímpar

Enunciado do Problema
Códigos cíclicos com dimensões excedendo a metade do comprimento do código ($k > v/2$) e distâncias mínimas superiores à raiz quadrada do comprimento do código ($d > \sqrt{v}$) são altamente desejáveis para aplicações que exigem alta eficiência de transmissão e forte correção de erros, como sistemas de comunicação, criptografia pós-quântica e radar. Embora progressos significativos tenham sido feitos na construção de tais códigos sobre campos binários (característica 2), a construção de códigos cíclicos não binários usando funções de potência com uniformidade diferencial conhecida sobre campos de característica ímpar tem recebido comparativamente menos atenção. Este artigo aborda a lacuna na construção de famílias infinitas de códigos $q$-ários (onde $q$ é uma potência de um primo ímpar) que alcançam parâmetros favoráveis, especificamente visando dimensões $k > (q^m - 1)/2$ e distâncias mínimas $d > \sqrt{q^m - 1}$.

Metodologia
Os autores empregam a abordagem de sequência de traço para construir códigos cíclicos. A metodologia envolve as seguintes etapas:

1. Definição da Sequência: Para um dado campo finito $\mathbb{F}_{q^m}$ e um elemento primitivo $\alpha$, uma sequência $s_\infty = (s_t)_{t \ge 0}$ é definida via a função de traço: $s_t = \text{Tr}_{q^m}^q(F(\alpha^t + 1))$, onde $F(x)$ é uma função de potência selecionada sobre $\mathbb{F}_{q^m}$.
2. Determinação do Polinômio Gerador: O código cíclico $C_F$ é gerado pelo polinômio minimal $M_s(x)$ da sequência $s_\infty$. A dimensão do código é determinada pelo span linear ($L_s$) da sequência, que corresponde ao número de coeficientes não nulos na expansão do traço da sequência.
3. Seleção da Função de Potência: O artigo seleciona monômios específicos $F(x) = x^d$ com uniformidade diferencial conhecida sobre $\mathbb{F}_{q^m}$ (onde $q$ é ímpar). Os critérios de seleção dependem da paridade de $m$ e da estrutura específica do expoente $d$.
4. Análise Algébrica:
   • Span Linear: Os autores utilizam expansões $q$-ádicas, o Teorema de Lucas e propriedades de cossetes ciclotômicos para expandir a função de traço e identificar os termos não nulos. Isso permite o cálculo exato do span linear $L_s$ e a construção do polinômio gerador $M_s(x)$.
   • Limites de Distância Mínima: Os limites inferiores para a distância mínima $d$ são estabelecidos usando o limite BCH e o limite de Hartmann-Tzeng. Isso envolve a identificação de inteiros consecutivos ou conjuntos específicos dentro do conjunto definidor (as raízes do polinômio gerador).
   • Distâncias Exatas: Para casos específicos, os autores constroem palavras-código explícitas de pesos específicos para determinar a distância mínima exata, frequentemente relacionando os códigos construídos a códigos BCH primitivos conhecidos.

Principais Contribuições e Resultados
O artigo apresenta várias famílias infinitas de códigos cíclicos $q$-ários de comprimento $v = q^m - 1$ com dimensões excedendo $v/2$. As construções e resultados específicos são categorizados pelos usos das funções de potência:

1. Códigos Ternários a partir de $x^{2 \cdot 3^{(m-1)/2} + 1}$ ($m$ ímpar):

   • Construídos sobre $\mathbb{F}_{3^m}$.
   • O span linear é $3m + N_3(m)$, resultando em dimensão $3^m - 1 - 3m - N_3(m)$.
   • A distância mínima $d$ satisfaz $3 \le d \le 8$.
   • Exemplo: Para $m=5$, obtém-se um código $[242, 226, 5]$, que é quase ótimo.

2. Códigos $p$-ários a partir de $x^{p^{m/2} + 2}$ ($m$ par, $p$ ímpar):

   • Construídos sobre $\mathbb{F}_{p^m}$.
   • O span linear depende de $p$ e $m$ (ex: $N_p(m) + 5m/2$ para $p=3$).
   • Limites de distância mínima são estabelecidos: $d \ge 3$ (para $p=3$), $d \ge 5$ (para $p \ge 5, p \nmid m$), e $d \ge 4$ (para $p \ge 5, p \mid m$).
   • Distâncias exatas são determinadas para casos específicos (ex: $d=5$ para $p=5, p \nmid m$).

3. Códigos a partir de $x^{(q^{(m+1)/2} - 1)/(q-1)}$ ($m$ ímpar):

   • Esta construção aborda um caso específico onde o expoente é a soma de uma série geométrica.
   • O artigo deriva uma fórmula geral para o span linear envolvendo somas de termos $N_p(k)$.
   • Significância: Esta construção resolve parcialmente o Problema Aberto 5.31 proposto por Ding [35], que tratava da dimensão e do polinômio gerador de códigos cíclicos para $t = (m+1)/2$ com $m$ ímpar.
   • Limites inferiores para $d$ são fornecidos, variando de 2 a $2^{t-2} + 2$ dependendo de $q$ e $t$.

4. Códigos Ternários a partir de $x^{(3^{(m+1)/2} + 1)/2}$ ($m$ ímpar):

   • Utiliza um monômio que é uma função Não Linear Perfeita (PN) ou 4-uniforme dependendo de $m$.
   • O span linear é calculado como $N_3(m) + (N_3(t+1) + \sum N_3(k)2^{t-k})m$.
   • Limites de distância mínima são estabelecidos, com $d \ge 8$ sob condições específicas de divisibilidade.

5. Códigos $p$-ários a partir de $x^{p^h - 1}$ ($1 \le h \le \lceil m/2 \rceil$):

   • Generaliza resultados binários anteriores para característica ímpar.
   • O span linear é derivado usando expansões $p$-ádicas e definições de conjuntos específicos ($\hat{\Gamma}(t)$).
   • Os limites inferiores da distância mínima mostram-se significativamente melhores do que a raiz quadrada do comprimento do código em muitos casos (ex: $d \ge p^h + 2$).
   • Distâncias exatas são determinadas para casos onde $h \mid m$, mostrando que o código é equivalente a um código BCH primitivo de sentido estreito com distância projetada $p^h + 1$.

6. Códigos a partir de $x^{2 \cdot p^{m/2} - 1}$ e $x^{p^{2h} - p^h + 1}$:

   • Estas seções lidam com $m$ par e ímpar, respectivamente, com expoentes específicos.
   • Os autores derivam expressões complexas para o span linear e polinômios minimais.
   • O Teorema 11 e o Teorema 13 demonstram que os limites inferiores para a distância mínima destas famílias são frequentemente muito superiores ao limite da raiz quadrada ($\sqrt{v}$).

Significância e Alegações
O artigo alega estender o framework binário de Ding e Zhou [14] para um cenário não binário. A principal significância reside em:

• Melhoria de Parâmetros: Os códigos construídos alcançam dimensões $k > (q^m - 1)/2$ e distâncias mínimas $d > \sqrt{q^m - 1}$, equilibrando efetivamente a taxa do código e a capacidade de correção de erros.
• Resolução de Problemas Abertos: O trabalho resolve parcialmente o Problema Aberto 5.31 de Ding [35] referente ao código cíclico ternário definido por $F(x) = x^{(3^{(m+1)/2}-1)/(3-1)}$ com $m$ ímpar.
• Otimalidade: Vários códigos construídos (e seus duais) são identificados como ótimos ou quase ótimos quando comparados com o Banco de Dados de melhores códigos lineares conhecidos [47].
• Avanço Teórico: O artigo fornece fórmulas explícitas para o span linear e polinômios geradores para famílias infinitas de códigos, utilizando ferramentas de teoria dos números avançadas (cossetes ciclotômicas, expansões $p$-ádicas, Teorema de Lucas) para lidar com as complexidades de campos de característica ímpar.

Os autores concluem que estas construções fornecem uma fonte rica de códigos adequados para aplicações exigentes e sugerem que a exploração adicional de funções de potência sobre campos de característica ímpar pode gerar famílias mais ótimas. Eles também observam o potencial para que estes códigos sejam usados na construção de códigos de correção de erros quânticos via construção CSS.