Shortest LCD embeddings of binary, ternary and quaternary linear codes

Problema de Pesquisa
Códigos lineares com complementos ortogonais (códigos LCD) são uma área significativa de pesquisa em teoria de códigos e criptografia, particularmente devido à sua resistência a ataques de canal lateral e de injeção de falhas. Embora se saiba que todo código linear sobre $\mathbb{F}_q$ ($q \ge 4$) é equivalente a um código LCD, e resultados semelhantes existem para $\mathbb{F}_{q^2}$, os limites para as distâncias mínimas de códigos LCD sobre $\mathbb{F}_2$, $\mathbb{F}_3$ e códigos LCD Hermitianos sobre $\mathbb{F}_4$ permanecem desconhecidos para muitos comprimentos e dimensões. Um desafio central na teoria de códigos é determinar a maior distância mínima para um dado comprimento e dimensão. Este artigo aborda o problema específico de incorporar códigos lineares arbitrários em códigos LCD, visando encontrar a "menor" tal incorporação (aumento mínimo de comprimento) e utilizar este método para construir novos códigos LCD de distância ótima.

Metodologia
Os autores introduzem uma abordagem sistemática para incorporar um dado código linear $C$ em um código LCD $\tilde{C}$ adicionando o número mínimo de colunas à sua matriz geradora. A metodologia procede da seguinte forma:

1. Fundamentação Teórica: O artigo estabelece que o número mínimo de colunas ($m$) necessário para incorporar um código $[n, k]$ $C$ em um código LCD é exatamente igual à dimensão $\ell$ do casco (hull) de $C$ (onde $\text{Hull}(C) = C \cap C^\perp$). Consequentemente, o comprimento da menor incorporação LCD é $n + \ell$.
2. Caracterização Estrutural: Os autores caracterizam a matriz geradora de uma incorporação LCD mais curta. Se $G$ é uma matriz geradora de um código $C$ decomposta em uma parte que gera o casco, $G(\text{Hull}(C))$, e uma parte restante $A$, então uma incorporação LCD mais curta é gerada por uma matriz da forma:
   $$\tilde{G} = \begin{bmatrix} G(\text{Hull}(C)) & D \\ A & C \end{bmatrix}$$
   onde $D$ é uma matriz $\ell \times \ell$ invertível e $C$ é uma matriz $\ell \times (k-\ell)$ arbitrária. O artigo prova que anexar uma matriz invertível às linhas correspondentes ao casco e uma matriz arbitrária às demais linhas sempre resulta em uma incorporação LCD mais curta.
3. Estratégia de Construção: Os autores aplicam este método de incorporação a códigos lineares de distância ótima conhecidos (especificamente códigos ternários e quaternários) que não são, eles próprios, LCD. Ao calcular a dimensão do casco desses códigos existentes e anexar as colunas necessárias de acordo com a estrutura derivada, eles geram novos códigos LCD.

Contribuições Principais e Resultados
O artigo fornece tanto limites teóricos quanto construções concretas:

• Resultados Teóricos:

  • Prova que o comprimento da menor incorporação LCD de um código $[n, k]$ com dimensão de casco $\ell$ é $n + \ell$.
  • Caracteriza todas as formas possíveis de matrizes geradoras para essas incorporações mais curtas, mostrando que elas são equivalentes a anexar uma matriz invertível às linhas que geram o casco.
  • Demonstra que o comprimento da menor incorporação LCD de um código $C$ é idêntico ao de seu casco, $\text{Hull}(C)$.

• Novas Construções de Códigos:
  Utilizando o método de menor incorporação LCD em códigos lineares existentes, os autores construíram vários novos códigos LCD com parâmetros que melhoram as distâncias mínimas conhecidas:

  • Códigos LCD Ternários:
    • $[23, 4, 14]$: Melhora a distância mínima conhecida de 13 para 14.
    • $[23, 5, 12]$: Melhora a distância mínima conhecida de 11 para 12.
    • $[24, 6, 12]$: Melhora a distância mínima conhecida de 11 para 12.
    • $[25, 5, 14]$: Melhora a distância mínima conhecida de 13 para 14.
  • Código LCD Hermitiano Quaternário:
    • $[21, 10, 8]$: Melhora a distância mínima conhecida de 7 para 8.

Os autores observam que, para os novos parâmetros $[23, 4, 14]$ e $[23, 5, 12]$, encontraram 226 e 38 códigos inequivalentes, respectivamente. Estes códigos são de distância ótima e inequivalentes aos atualmente presentes no banco de dados BKLC (Best Known Linear Codes).

Significância
O artigo afirma que o método de menor incorporação LCD é uma ferramenta útil para encontrar códigos LCD de distância ótima sobre vários corpos. Ao determinar o número preciso de colunas necessárias e caracterizar sua estrutura, o método oferece um caminho construtivo para melhorar a distância mínima de códigos lineares conhecidos quando convertidos em LCD. Os resultados demonstram que esta abordagem produz com sucesso novos códigos com distâncias mínimas uma unidade superiores às dos códigos anteriormente conhecidos para parâmetros ternários e quaternários específicos.

Limitações e Direções Futuras
Os autores reconhecem uma limitação em sua abordagem: como o espaço de busca para as matrizes invertíveis e arbitrárias anexadas é excessivamente grande, é difícil garantir a descoberta da incorporação específica que resulte na maior distância mínima absoluta para um determinado código. Eles sugerem que pesquisas futuras devem focar no desenvolvimento de métodos para selecionar as matrizes anexadas de forma mais estratégica para maximizar a distância mínima resultante ou para determinar se as matrizes anexadas podem ser ainda mais restringidas até a equivalência para reduzir o espaço de busca.