Sobre códigos inducidos de matrices de Hadamard

Información Básica

• ID del Artículo: 2410.24027
• Título: On codes induced from Hadamard matrices
• Autor: Ted Hurley (University of Galway)
• Clasificación: cs.IT math.IT (Teoría de la Información)
• Fecha de Publicación: Octubre de 2024 (v2: 17 de noviembre de 2025)
• Enlace del Artículo: https://arxiv.org/abs/2410.24027

Resumen

Este artículo aplica esquemas derivados de unidades (unit derived schemes) a matrices de Hadamard para construir y analizar códigos lineales de bloque y códigos convolucionales. El artículo construye códigos con tipos, longitudes y tasas especificadas, y deriva múltiples familias de códigos autodualos, códigos que contienen su dual, códigos duales lineales complementarios, así como códigos de corrección de errores cuánticos, abarcando tanto códigos lineales de bloque como códigos convolucionales.

Antecedentes de Investigación y Motivación

Problemas de Investigación

1. Ausencia de métodos algebraicos para construcción de códigos convolucionales: Como señalaron McEliece y otros, los códigos convolucionales carecen de métodos algebraicos universales de construcción y diseño, lo que limita enormemente su escala y disponibilidad.
2. Construcción sistematizada de tipos específicos de códigos: Se requiere construir códigos que satisfagan propiedades específicas (autodualos, que contienen su dual, códigos LCD, etc.), con capacidad de controlar su longitud, distancia y tasa de código.
3. Construcción de códigos de corrección de errores cuánticos: Se necesita construir códigos de corrección de errores cuánticos mediante teoría de codificación clásica (como el método CSS).

Importancia de la Investigación

• Significado Teórico: Proporciona un marco algebraico unificado de construcción para la teoría de códigos
• Aplicaciones Prácticas:
  • Los códigos LCD pueden utilizarse para resistir ataques de canal lateral y ataques de fallos
  • Los códigos autodualos y códigos que contienen su dual pueden construir códigos de corrección de errores cuánticos
  • Los códigos convolucionales se aplican ampliamente en sistemas de comunicación (como decodificación con algoritmo de Viterbi)

Limitaciones de Métodos Existentes

• Aunque los códigos Walsh-Hadamard tienen buenas propiedades de distancia, su tasa de código es extremadamente baja (1/2^k)
• Falta un método universal sistematizado para construir diferentes tipos de códigos a partir de matrices de Hadamard
• La construcción de códigos convolucionales ha dependido históricamente de generación por computadora, careciendo de apoyo teórico algebraico

Motivación de la Investigación

Este artículo extiende el método derivado de unidades propuesto por el autor en 27, aplicándolo a matrices de Hadamard para lograr:

• Construcción simultánea de códigos lineales de bloque y códigos convolucionales
• Construcción hasta tipos, longitudes y tasas especificadas
• Obtención de límites de distancia computables
• Generación de múltiples códigos a partir de una única matriz de Hadamard

Contribuciones Principales

1. Marco Teórico: Establece la teoría de construcción de códigos derivados de unidades basada en matrices de Hadamard, probando cinco proposiciones centrales (Proposiciones 2.1-2.5)
2. Diseño de Algoritmos: Propone cuatro algoritmos de construcción universal:
   • Algoritmo 1: Construcción de códigos LCD lineales de bloque con tasa arbitraria r/n
   • Algoritmo 2: Construcción de códigos lineales de bloque autodualos de longitud 2n
   • Algoritmo 3: Construcción de códigos convolucionales autodualos de longitud n
   • Algoritmo 4: Construcción de códigos convolucionales que contienen su dual con tasa r/n (r≥n/2)
3. Construcción Unificada de Múltiples Tipos de Códigos: A partir de una única matriz de Hadamard se pueden construir códigos LCD, autodualos, DC y códigos de corrección de errores cuánticos
4. Análisis de Distancia: Proporciona métodos algebraicos de cálculo de distancia; la distancia de códigos convolucionales puede alcanzar el doble de la de códigos lineales de bloque
5. Aplicaciones Concretas: Proporciona casos específicos con H(20), H(28) y otras matrices, construyendo una gran cantidad de nuevos códigos

Explicación Detallada del Método

Definición de Tareas

Entrada: Matriz de Hadamard n×n H, satisfaciendo HH^T = nI_n, con elementos ±1 Salida:

• Código lineal de bloque: código n,r,d_q (longitud n, dimensión r, distancia mínima d, campo GF(q))
• Código convolucional: código (n,k,δ;μ,d_f)_q (longitud n, rango k, grado δ, memoria μ, distancia libre d_f)

Restricciones:

• La característica p del campo satisface p∤n (para la mayoría de construcciones)
• Para códigos convolucionales autodualos se requiere que i=√(-1) exista en el campo
• Condiciones de rango de matriz

Arquitectura del Método Principal

1. Construcción de Códigos Lineales de Bloque (Método Base)

Particionar la matriz de Hadamard: H = (A/B), donde A es una matriz r×n

Propiedades Clave:

(A/B)(A^T  B^T) = nI_n

En el campo GF(p) (p∤n), esto se convierte en:

AA^T + BB^T = 0 (mod p)
es decir, AB^T = 0

Resultados:

• A genera un código n,r
• B^T es la matriz de verificación de paridad
• B genera el código dual

2. Construcción de Códigos LCD (Proposición 2.1)

Teorema: Para H = (A/B), si p∤n, entonces A genera un código LCD

Puntos Clave de la Prueba:

• AB^T = 0 ⟹ B genera el código dual de A
• H invertible ⟹ Las filas de A no pueden ser combinaciones no triviales de filas de B
• Por lo tanto C∩C^⊥ = 0 (propiedad LCD)

3. Códigos Lineales de Bloque Autodualos (Proposición 2.2)

Construcción: G = (I_n, αH), donde α satisface 1+α²n=0

Cálculo Clave:

(I_n, αH)(I_n / αH^T) = I_n + α²nI_n = (1+α²n)I_n

Cuando 1+α²n=0:

• (I_n / αH^T) es una matriz de verificación de rango n
• K = (I_n, αH) genera el código dual
• Por lo tanto el código es autodual

Detalles de Implementación:

• α puede estar en GF(p) o en su extensión cuadrática GF(p²)
• La matriz generadora se proporciona directamente en forma sistemática

4. Códigos Convolucionales Autodualos (Proposición 2.3)

Construcción: H = (A/B), n=2m, A y B cada uno m×n

Definir la matriz generadora:

G(z) = A + iBz, donde i=√(-1)

Verificación de Autodualidad:

G(z)(iB^T + A^Tz) = (A+iBz)(iB^T+A^Tz)
                   = 0 + nI_m·z - nI_m·z + 0 = 0

Por lo tanto H^T(z) = iB^T + A^Tz es la matriz de verificación, y A+iB genera el código dual

Verificación de No-Catastroficidad:

(A+iBz)A^T = nI_m

Por lo tanto G(z) tiene inversa polinomial derecha, y el código es no-catastrófico

Cálculo de Distancia:

d_f = d(A) + d(B)

5. Códigos Convolucionales que Contienen su Dual (Proposición 2.4)

Construcción: H = (A/B), A es r×n, B es (n-r)×n, r>n-r

Definir:

B_1 = (0_{t×n} / B), donde t=2r-n
G(z) = A + iB_1z

Verificación de Propiedad DC:

• Construir matriz de verificación H^T(z) = iB^T + C_1z
• Generador del código dual: C_1^T + iB
• Verificar que el código dual está contenido en el código original

Puntos de Innovación Técnica

1. Estrategia de Partición de Matriz: Obtener diferentes tipos de códigos a partir de la misma matriz de Hadamard mediante diferentes formas de partición
2. Control de Parámetros: Lograr control de tasa de código (r/n) mediante selección del número de filas r
3. Técnica de Extensión de Campo: Utilizar la existencia de √(-1) para construir códigos convolucionales
4. Computabilidad de Distancia: Utilizar la ortogonalidad de la matriz de Hadamard para cálculo algebraico de distancia
5. Marco Unificado: Los métodos de construcción de códigos lineales de bloque y códigos convolucionales están unificados

Configuración Experimental

Conjunto de Datos (Matrices de Hadamard)

Este artículo utiliza matrices de Hadamard de múltiples tamaños:

• Tamaños Pequeños: H(12), H(20), H(24), H(28)
• Tamaños Medianos: H(36), H(40), H(72)
• Tamaños Grandes: H(144)

Tipos de Matriz:

• Matrices Paley-Hadamard (para tamaños 12k)
• Matrices Hadamard no separables (preferidas por mejor rendimiento)

Métricas de Evaluación

1. Longitud de Código n: Longitud de la codificación
2. Dimensión/Rango r o k: Cantidad de bits de información
3. Tasa de Código: r/n (códigos lineales de bloque) o k/n (códigos convolucionales)
4. Distancia Mínima d: Medida de capacidad de corrección de errores
5. Memoria μ: Longitud de memoria del código convolucional
6. Distancia Libre d_f: Medida de distancia del código convolucional

Herramientas Computacionales

• Sistema de Álgebra Computacional GAP y sus paquetes:
  • Paquete Guava: Cálculos de teoría de códigos
  • Paquete Gauss: Operaciones de matriz sobre campos finitos
• Utilizados para: Operaciones de submatriz, cálculos en campos finitos, verificación de distancia

Detalles de Implementación

• Selección de Campo: Principalmente GF(3), GF(5), GF(7) y sus extensiones GF(3²), GF(5²)
• Cálculo de Rango: Calcular rango de matriz en el sentido módulo p
• Cálculo de Distancia:
  • Longitudes pequeñas (≤100): Cálculo directo por computadora
  • Longitudes grandes: Utilizar métodos algebraicos (Proposición 2.6, Lema 2.18)

Resultados Experimentales

Resultados Principales

1. Códigos Construidos a partir de H(20)

2. Códigos Construidos a partir de H(28)

3. Propiedades Extremales de Códigos Ternarios

Para matrices Paley-Hadamard de H(12k):

• Construcción de códigos autodualos 12k, 6k, d₃
• Resultados de Verificación: Para k=1,2,3,4,5 (es decir, n=12,24,36,48,60), los códigos construidos alcanzan distancia óptima
• Límite teórico: d ≤ ⌊n/12⌋+3
• Para n=72 y superiores no existen códigos extremales

Hallazgos Clave

1. Rendimiento de Distancia

Códigos Convolucionales vs Códigos Lineales de Bloque:

• Por ejemplo H(12):
  • Código lineal de bloque A: 12,6,6
  • Código convolucional G(z)=A+iBz: distancia d_f=12
  • La distancia del código convolucional es el doble de la del código lineal de bloque

2. Flexibilidad de Tasa de Código

• Se pueden construir códigos LCD con tasa arbitraria r/n (0<r<n)
• Códigos autodualos: tasa fija de 1/2
• Códigos convolucionales DC: tasa r/n, r≥n/2

3. Propiedades de Rango (Lema 2.7)

Para un número primo p|n (p≠2):

rank(H) ≤ n/2 en GF(p)

Verificación: Matrices Paley-Hadamard H(12k) tienen rango exactamente 6k en GF(3)

Análisis de Casos Específicos

Ejemplo Prototipo 2.9: H(12) Explicación Detallada

Descomposición de Matriz: H = (A/B), A y B cada uno 6×12

Aplicación 1: Código Lineal de Bloque Autodual (GF(3))

• En GF(3): AA^T = 0 (porque 3|12)
• A genera código autodual 12,6,6₃
• Optimalidad: Alcanza distancia teórica óptima
• Capacidad de Corrección: Puede corregir 2 errores

Aplicación 2: Código LCD (GF(5))

• A genera código LCD 12,6,6₅
• B genera código dual, también 12,6,6₅

Aplicación 3: Código Convolucional Autodual (GF(5))

• G(z) = A + 2Bz (2=√(-1) en GF(5))
• Parámetros: (12,6,6;1,12)₅
• Distancia: d_f = d(A) + d(B) = 6+6 = 12
• No-catastroficidad: (A+2Bz)A^T = 6I₆ = I₆

Aplicación 4: Código Autodual de Longitud 24 (GF(5²))

• Se requiere α²=2, x²-2 es irreducible sobre GF(5)
• En GF(5²): (I₁₂, αH) genera código autodual 24,12,8₅₂

Aplicación 5: Código Autodual de Longitud 24 (GF(7))

• α=2 satisface 1+12α²=0 en GF(7)
• (I₁₂, 2H) genera código autodual 24,12,8₇

Ejemplo 2.10: Código Convolucional de Memoria Alta

Construcción de código convolucional con memoria 3 a partir de H(12):

A = H[1..3][1..12]
B = H[4..6][1..12]
C = H[7..9][1..12]
D = H[10..12][1..12]
G(z) = A + Bz + Cz² + Dz³

Parámetros: (12,3,9;3,24) Distancia: 24 (porque todas las submatrices tienen distancia 6)

Aplicaciones a Gran Escala

Ejemplo 2.11: Códigos de Longitud Grande

• H(72): Código autodual 72,36,18₃
• H(144): Código 144,72,d₃

Ejemplo 2.15: H(36)

• Código autodual 36,18,12₃ (GF(3))
• Código convolucional autodual (36,18,18;1,d)₅ (GF(5))
• Código de corrección de errores cuántico: longitud 36, distancia d

Trabajo Relacionado

Fundamentos de Teoría de Códigos

1. Textos Clásicos:
   • Blahut 1: Códigos algebraicos para transmisión de datos
   • MacWilliams & Sloane 4: Teoría de códigos de corrección de errores
   • McEliece 3: Teoría de información y codificación
2. Teoría de Códigos Convolucionales:
   • Johannesson & Zigangirov 2: Fundamentos de codificación convolucional
   • Rosenthal et al. 35,36,38: Códigos convolucionales MDS
   • Bocharova et al. 12: Códigos convolucionales duales

Tipos Especiales de Códigos

1. Códigos LCD:
   • Massey 30,31: Introducción inicial del concepto de código LCD
   • Carlet et al. 15-17: Investigación moderna de códigos LCD
   • Aplicaciones: Defensa contra ataques de canal lateral 18,19
2. Códigos Autodualos:
   • Mallows & Sloane 29: Límites superiores para códigos autodualos
   • Pless 33: Códigos simétricos sobre GF(3)
   • Mallows et al. 37: Códigos autodualos sobre GF(3)
3. Códigos de Corrección de Errores Cuánticos:
   • Calderbank & Shor 14: Construcción CSS
   • Calderbank et al. 13: Códigos cuánticos sobre GF(4)
   • Steane 39: Códigos de corrección de errores cuánticos simples

Matrices de Hadamard

• van Lint & Wilson 5: Fundamentos combinatorios
• Horadam 6: Matrices de Hadamard y sus aplicaciones (monografía)

Método Derivado de Unidades (Trabajo Previo del Autor)

• Hurley & Hurley 8,9,22-25: Desarrollo del método derivado de unidades
• Hurley 27: Códigos lineales de bloque y convolucionales finales (base de este artículo)
• Hurley 26,28: Construcción de códigos MDS

Ventajas de Este Artículo Comparado con Trabajo Relacionado

1. Marco Unificado: Primera vez que se tratan uniformemente códigos lineales de bloque y códigos convolucionales
2. Construcción Algebraica: Resuelve el problema de construcción algebraica de códigos convolucionales planteado por McEliece
3. Códigos de Múltiples Tipos: Construcción de múltiples tipos de códigos a partir de una única matriz
4. Distancia Computable: Proporciona método algebraico de cálculo de distancia
5. Viabilidad a Gran Escala: Puede construir códigos de longitud grande y tasa alta

Conclusiones y Discusión

Conclusiones Principales

1. Contribuciones Teóricas:
   • Establece marco teórico completo para construcción de códigos basada en matrices de Hadamard
   • Prueba cinco proposiciones centrales, proporciona cuatro algoritmos universales
   • Unifica métodos de construcción de códigos lineales de bloque y códigos convolucionales
2. Capacidad de Construcción:
   • Se pueden construir códigos LCD con tasa arbitraria
   • Se pueden construir códigos autodualos, DC, códigos de corrección de errores cuánticos
   • Se obtienen múltiples códigos de diferentes tipos a partir de una única matriz de Hadamard
3. Ventajas de Rendimiento:
   • La distancia del código convolucional puede alcanzar el doble de la del código lineal de bloque
   • Los códigos ternarios alcanzan propiedades extremales en longitudes pequeñas
   • Se logran longitudes grandes y tasas altas

Limitaciones

1. Restricciones de Campo:
   • La mayoría de construcciones requieren p∤n
   • Los códigos convolucionales autodualos requieren que √(-1) exista
   • Algunas construcciones requieren extensión de campo
2. Cálculo de Distancia:
   • Para longitudes grandes es difícil calcular distancia exacta
   • Depende de métodos algebraicos y verificación por computadora
   • En algunos casos solo se pueden dar estimaciones
3. Dependencia de Matriz de Hadamard:
   • Se requiere conocer la expresión explícita de la matriz de Hadamard
   • Las matrices Hadamard no separables tienen mejor rendimiento pero construcción difícil
   • La conjetura de Hadamard sin resolver limita tamaños disponibles
4. Códigos Convolucionales de Memoria Alta:
   • El artículo se enfoca principalmente en el caso de memoria 1
   • El caso de memoria alta se deja para investigación futura (solo se proporciona Ejemplo 2.10)
5. Verificación de Aplicación Práctica:
   • Falta pruebas de rendimiento en sistemas de comunicación reales
   • Análisis de complejidad de decodificación insuficiente

Direcciones Futuras

1. Extensión Teórica:
   • Construcción sistematizada de códigos convolucionales de memoria alta
   • Aplicación de otros tipos de matrices ortogonales
   • Investigación profunda en campos no binarios
2. Mejora de Distancia:
   • Límites de distancia más precisos
   • Construcción de códigos MDS que alcancen límite de Singleton
   • Análisis de propiedades asintóticas
3. Extensión de Aplicaciones:
   • Implementación en sistemas de comunicación reales
   • Aplicaciones en computación cuántica
   • Aplicaciones criptográficas
4. Optimización Computacional:
   • Algoritmos de decodificación eficientes
   • Implementación paralela
   • Diseño amigable con hardware

Evaluación Profunda

Fortalezas

1. Fuerte Innovación Teórica:
   • Primera sistematización del uso de matrices de Hadamard para construcción de múltiples tipos de códigos
   • Resuelve el problema de larga data de construcción algebraica de códigos convolucionales
   • Aplicación innovadora del método derivado de unidades
2. Buena Uniformidad de Método:
   • Tratamiento unificado de códigos lineales de bloque y códigos convolucionales
   • Marco unificado para diferentes tipos de códigos (LCD, autodualos, DC)
   • Cadena completa de teoría a algoritmo a aplicación
3. Alto Valor Práctico:
   • Proporciona algoritmos de construcción explícitos
   • Permite realizar tasa arbitraria y longitud
   • Fácil de implementar en sistema GAP
4. Experimentos Suficientes:
   • Múltiples tamaños de matrices de Hadamard
   • Múltiples campos finitos (GF(3), GF(5), GF(7) y extensiones)
   • Ejemplos prototipo detallados (Ejemplo 2.9)
5. Escritura Clara:
   • Estructura jerárquica clara
   • Lógica clara de definiciones, proposiciones, algoritmos y aplicaciones
   • Derivaciones matemáticas rigurosas

Insuficiencias

1. Completitud Teórica:
   • El tratamiento del caso p|n no es suficientemente sistemático
   • La teoría de códigos convolucionales de memoria alta está incompleta
   • Algunas pruebas de proposiciones son demasiado breves (como la prueba de distancia de Proposición 2.3)
2. Limitaciones Experimentales:
   • Falta comparación sistemática con códigos óptimos existentes
   • El cálculo de distancia depende principalmente de computadora (longitud ≤100)
   • Falta experimentos de rendimiento de decodificación
3. Orientación de Aplicación Insuficiente:
   • ¿Cómo elegir la matriz de Hadamard apropiada?
   • ¿Estrategia de selección de parámetros para diferentes escenarios de aplicación?
   • Análisis de complejidad de decodificación ausente
4. Reproducibilidad:
   • No se proporciona código o implementación específica
   • La construcción de algunas matrices de Hadamard no se especifica
   • Detalles de implementación en GAP insuficientes
5. Análisis Comparativo:
   • Comparación detallada con códigos Walsh-Hadamard insuficiente
   • Falta comparación con otros métodos de construcción algebraica
   • Análisis de compensación rendimiento-complejidad insuficiente

Impacto

1. Contribución Académica:
   • Proporciona nueva herramienta de construcción para teoría de códigos
   • Impulsa aplicación de matrices de Hadamard en codificación
   • Puede inspirar investigación en serie posterior
2. Valor Práctico:
   • La construcción de códigos de corrección de errores cuánticos tiene potencial de aplicación práctica
   • Los códigos LCD tienen valor de aplicación en seguridad
   • La construcción de códigos de longitud grande satisface demandas de comunicación moderna
3. Reproducibilidad:
   • Los métodos teóricos son claros y reproducibles
   • Se requiere soporte del sistema GAP
   • La implementación específica requiere cierto trabajo
4. Limitaciones:
   • Depende de la existencia de matrices de Hadamard
   • Algunas construcciones requieren extensión de campo
   • La aplicación en sistemas reales requiere verificación adicional

Escenarios Aplicables

1. Investigación Teórica:
   • Investigación de métodos de construcción algebraica en teoría de códigos
   • Investigación de aplicaciones de matrices de Hadamard
   • Teoría de información cuántica
2. Aplicaciones Prácticas:
   • Comunicación Cuántica: Construcción de códigos de corrección de errores cuánticos
   • Comunicación Segura: Códigos LCD resistentes a ataques de canal lateral
   • Almacenamiento de Datos: Códigos de corrección de errores de tasa alta
   • Comunicación Inalámbrica: Aplicación de códigos convolucionales
3. Propósitos Educativos:
   • Casos de estudio para cursos de teoría de códigos
   • Ejemplos de aplicación de métodos algebraicos en codificación
   • Enseñanza de aplicaciones de matrices de Hadamard
4. Escenarios No Aplicables:
   • Aplicaciones que requieren tasa extremadamente alta (>0.9)
   • Escenarios extremadamente sensibles a complejidad de decodificación
   • Aplicaciones que requieren decodificación de decisión suave

Referencias Bibliográficas (Referencias Clave)

1. 3 McEliece: Texto clásico de teoría de información y codificación, señala el problema de construcción algebraica de códigos convolucionales
2. 6 Horadam: Monografía autorizada sobre matrices de Hadamard y sus aplicaciones
3. 13,14 Calderbank & Shor: Trabajo pionero en construcción de códigos de corrección de errores cuánticos CSS
4. 27 Hurley: Base teórica de este artículo, códigos lineales de bloque y convolucionales finales
5. 31 Massey: Trabajo pionero en códigos LCD
6. 35,38 Rosenthal et al.: Investigación importante en códigos convolucionales MDS

Evaluación General: Este es un artículo excelente con fuerte innovación teórica y métodos sistemáticos completos. El autor combina exitosamente matrices de Hadamard con el método derivado de unidades, estableciendo un marco unificado para construcción de múltiples tipos de códigos, particularmente resolviendo el problema de larga data de construcción algebraica de códigos convolucionales. El valor principal del artículo radica en proporcionar una metodología completa desde teoría hasta algoritmo hasta aplicación, con significativo valor académico y potencial de aplicación. Las principales insuficiencias están en la incompletitud de la teoría de códigos convolucionales de memoria alta y verificación de aplicación práctica insuficiente. Se recomienda que trabajo futuro fortalezca la implementación en sistemas reales y pruebas de rendimiento.