Construction of MRD Codes Based on Circular-Shift Operations

Título: Construção de Códigos MRD Baseada em Operações de Deslocamento Circular

1. Problema

Os códigos de distância máxima em posto (MRD - Maximum Rank Distance) são fundamentais para aplicações em criptografia, armazenamento distribuído e códigos de subespaço. A construção clássica de códigos MRD, como os códigos de Gabidulin e os códigos de Gabidulin torcidos (twisted), depende fortemente da aritmética sobre campos de extensão $\mathbb{F}_{q^N}$.

• Desafio Principal: À medida que o parâmetro $N$ (dimensão do código) aumenta, o campo de extensão $\mathbb{F}_{q^N}$ torna-se significativamente maior, resultando em uma complexidade computacional elevada para a implementação prática.
• Limitação de Seleção de Parâmetros: A necessidade de operar em $\mathbb{F}_{q^N}$ restringe a flexibilidade na escolha dos parâmetros do código e dificulta a transformação eficiente de vetores sobre $\mathbb{F}_{q^N}$ em matrizes sobre $\mathbb{F}_q$ (o corpo base), especialmente na seleção de bases adequadas.

2. Metodologia

Os autores propõem uma nova construção de códigos MRD, denominados códigos MRD baseados em deslocamento circular (circular-shift-based MRD codes), que opera inteiramente sobre o corpo base $\mathbb{F}_q$, eliminando a necessidade de aritmética em campos de extensão.

• Parâmetros Definidos:
  • $q$: Um número primo.
  • $L$: Um inteiro positivo tal que $\text{mdc}(q, L) = 1$.
  • $m_L$: A ordem multiplicativa de $q$ módulo $L$ (menor inteiro tal que $q^{m_L} \equiv 1 \pmod L$).
  • $J$: A função totiente de Euler de $L$ (número de inteiros positivos menores que $L$ e coprimos a $L$).
• Construção do Código:
  • O código é definido como um conjunto de matrizes $J \times n$ geradas a partir de um vetor de mensagem $m \in \mathbb{F}_q^{Jk}$.
  • A geração do código envolve:
    1. Matrizes de permutação cíclica $C_L$ de tamanho $L \times L$.
    2. Matrizes de bloco $\Psi_{k \times n}$ compostas por potências de $C_L$.
    3. Matrizes de transformação $P$ e $Q$ (construídas a partir de matrizes de Vandermonde e raízes primitivas da unidade em $\mathbb{F}_{q^{m_L}}$, mas projetadas para terem entradas em $\mathbb{F}_q$).
  • A fórmula central é: $C = \{ \Delta(m(I_k \otimes P)\Psi_{k \times n}(I_n \otimes Q)) : m \in \mathbb{F}_q^{Jk} \}$, onde $\Delta$ mapeia vetores para matrizes e $\otimes$ é o produto de Kronecker.
• Caracterização Polinomial: Os autores caracterizam tanto os novos códigos quanto os códigos de Gabidulin usando um conjunto de polinômios $q$-linearizados definidos sobre o espaço vetorial de linhas $\mathbb{F}_q^N$, permitindo uma comparação direta e unificada.

3. Contribuições Principais

1. Nova Construção Eficiente: Apresentação de uma família de códigos MRD $(J \times n, q^{Jk}, d)$ que evita completamente a aritmética de $\mathbb{F}_{q^J}$, operando apenas com adições, multiplicações em $\mathbb{F}_q$ e operações de deslocamento circular de colunas.
2. Análise de Diferença e Conexão:
   • Caso $J \neq m_L$: Demonstrou-se que, sob certas configurações de parâmetros, os códigos propostos são diferentes de qualquer código de Gabidulin ou código de Gabidulin torcido (com $h=0$).
   • Caso $J = m_L$: Provou-se que os códigos propostos coincidem com códigos de Gabidulin. No entanto, a construção proposta oferece uma nova abordagem para gerar códigos de Gabidulin puramente sobre $\mathbb{F}_q$, evitando a complexidade de $\mathbb{F}_{q^J}$.
3. Generalização de Gabidulin: Os autores mostram que os códigos propostos são equivalentes a uma generalização de códigos de Gabidulin obtida pela soma e concatenação de vários códigos de Gabidulin menores $(m_L \times n, q^{m_L k}, d)$, uma generalização não explorada anteriormente na literatura.
4. Análise de Complexidade Computacional:
   • Para $q=2$, $L$ primo e $n \leq m_L$, a geração de um código do código proposto requer $O(nkL)$ operações XOR.
   • Em contraste, a geração de um código de Gabidulin equivalente, baseada na construção tradicional sobre $\mathbb{F}_{2^{L-1}}$, requer $O(nkL^2)$ operações XOR (devido à multiplicação no campo de extensão).

4. Resultados

• Propriedade MRD: Foi provado que a construção satisfaz a propriedade de distância máxima em posto ($d = n - k + 1$) sob condições específicas de seleção das matrizes $P$ e $Q$.
• Exemplos Numéricos: O artigo fornece exemplos explícitos (para $q=2$ e $L=7$) demonstrando a construção dos códigos e verificando a equivalência ou diferença com códigos de Gabidulin e Gabidulin torcidos.
• Redução de Complexidade: A análise teórica confirma que a eliminação da aritmética de campos de extensão reduz a complexidade de codificação de ordem quadrática em relação a $L$ para ordem linear, tornando a implementação muito mais eficiente para parâmetros grandes.

5. Significado e Impacto

• Praticidade: A proposta resolve um gargalo prático na implementação de códigos MRD, permitindo a seleção de parâmetros mais flexíveis e uma implementação de hardware/software mais simples e rápida, especialmente em sistemas binários ($q=2$).
• Novo Paradigma: Introduz operações de deslocamento circular (comumente usadas em códigos de rede e códigos cíclicos) no contexto de códigos de distância em posto, abrindo novas linhas de pesquisa.
• Fundamentação Teórica: A caracterização unificada via polinômios $q$-linearizados sobre $\mathbb{F}_q^N$ esclarece a relação intrínseca entre diferentes famílias de códigos MRD, distinguindo quando são equivalentes e quando representam estruturas matemáticas distintas.
• Aplicações Futuras: A eficiência computacional torna esses códigos candidatos ideais para aplicações em armazenamento distribuído e criptografia pós-quântica, onde a velocidade de codificação e a baixa complexidade são críticas. O trabalho também aponta para futuras pesquisas sobre algoritmos de decodificação e aplicações em códigos de subespaço.