Sur les codes induits par les matrices de Hadamard

Informations fondamentales

• ID de l'article: 2410.24027
• Titre: On codes induced from Hadamard matrices
• Auteur: Ted Hurley (University of Galway)
• Classification: cs.IT math.IT (Théorie de l'information)
• Date de publication: Octobre 2024 (v2: 17 novembre 2025)
• Lien de l'article: https://arxiv.org/abs/2410.24027

Résumé

Cet article applique les schémas dérivés d'unités (unit derived schemes) aux matrices de Hadamard pour construire et analyser les codes linéaires en bloc et les codes convolutifs. L'article construit des codages avec des types, longueurs et débits spécifiés, et dérive plusieurs familles de codes auto-duaux, codes contenant leur dual, codes linéaires complémentaires duaux ainsi que des codes correcteurs d'erreurs quantiques, couvrant à la fois les codes linéaires en bloc et les codes convolutifs.

Contexte et motivation de la recherche

Problèmes de recherche

1. Absence de méthode algébrique pour la construction de codes convolutifs: Comme l'ont souligné McEliece et al., les codes convolutifs manquent de méthodes générales de construction et de conception algébriques, ce qui limite considérablement leur portée et leur disponibilité.
2. Construction systématisée de types de codes spécifiques: Nécessité de construire des codages satisfaisant des propriétés spécifiques (auto-duaux, contenant leur dual, codes LCD, etc.), tout en contrôlant leur longueur, distance et débit.
3. Construction de codes correcteurs d'erreurs quantiques: Nécessité de construire des codes correcteurs d'erreurs quantiques via la théorie classique du codage (comme la méthode CSS).

Importance de la recherche

• Signification théorique: Fournir un cadre de construction algébrique unifié pour la théorie du codage
• Applications pratiques:
  • Les codes LCD peuvent être utilisés pour résister aux attaques par canaux auxiliaires et aux attaques par défaut
  • Les codes auto-duaux et les codes contenant leur dual peuvent construire des codes correcteurs d'erreurs quantiques
  • Les codes convolutifs sont largement utilisés dans les systèmes de communication (par exemple, décodage par algorithme de Viterbi)

Limitations des méthodes existantes

• Bien que les codes de Walsh-Hadamard aient de bonnes propriétés de distance, leur débit est extrêmement faible (1/2^k)
• Absence de méthode générale pour construire systématiquement différents types de codes à partir de matrices de Hadamard
• La construction de codes convolutifs dépend depuis longtemps de la génération informatique, manquant de support théorique algébrique

Motivation de la recherche

Cet article étend la méthode dérivée d'unités proposée par l'auteur dans 27, en l'appliquant aux matrices de Hadamard, pour réaliser:

• La construction simultanée de codes linéaires en bloc et de codes convolutifs
• La construction jusqu'à des types, longueurs et débits spécifiés
• L'obtention de bornes de distance calculables
• La génération de multiples codages à partir d'une seule matrice de Hadamard

Contributions principales

1. Cadre théorique: Établissement d'une théorie de construction de codage dérivée d'unités basée sur les matrices de Hadamard, avec preuve de 5 propositions fondamentales (Propositions 2.1-2.5)
2. Conception algorithmique: Proposition de 4 algorithmes de construction généraux:
   • Algorithme 1: Construction de codes LCD linéaires en bloc de débit arbitraire r/n
   • Algorithme 2: Construction de codes linéaires en bloc auto-duaux de longueur 2n
   • Algorithme 3: Construction de codes convolutifs auto-duaux de longueur n
   • Algorithme 4: Construction de codes convolutifs contenant leur dual de débit r/n (r≥n/2)
3. Construction unifiée de codes multitypes: À partir d'une même matrice de Hadamard, on peut construire des codes LCD, auto-duaux, DC et des codes correcteurs d'erreurs quantiques
4. Analyse de distance: Fourniture d'une méthode de calcul algébrique de la distance, la distance des codes convolutifs pouvant atteindre le double de celle des codes linéaires en bloc
5. Applications concrètes: Présentation de cas concrets avec H(20), H(28), etc., construisant un grand nombre de nouveaux codages

Détails de la méthode

Définition de la tâche

Entrée: Matrice de Hadamard n×n H, satisfaisant HH^T = nI_n, avec éléments ±1 Sortie:

• Code linéaire en bloc: code n,r,d_q (longueur n, dimension r, distance minimale d, corps GF(q))
• Code convolutif: code (n,k,δ;μ,d_f)_q (longueur n, rang k, degré δ, mémoire μ, distance libre d_f)

Conditions de contrainte:

• La caractéristique p du corps satisfait p∤n (pour la plupart des constructions)
• Pour les codes convolutifs auto-duaux, i=√(-1) doit exister dans le corps
• Conditions de rang de la matrice

Architecture de la méthode principale

1. Construction de codes linéaires en bloc (méthode de base)

Partitionnement de la matrice de Hadamard: H = (A/B), où A est une matrice r×n

Propriété clé:

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

Dans le corps GF(p) (p∤n), cela devient:

AA^T + BB^T = 0 (mod p)
c'est-à-dire AB^T = 0

Résultat:

• A génère un code n,r
• B^T est la matrice de parité
• B génère le code dual

2. Construction de codes LCD (Proposition 2.1)

Théorème: Pour H = (A/B), si p∤n, alors A génère un code LCD

Points clés de la preuve:

• AB^T = 0 ⟹ B génère le code dual de A
• H inversible ⟹ Les lignes de A ne peuvent pas être des combinaisons non triviales des lignes de B
• Par conséquent C∩C^⊥ = 0 (propriété LCD)

3. Codes linéaires en bloc auto-duaux (Proposition 2.2)

Construction: G = (I_n, αH), où α satisfait 1+α²n=0

Calcul clé:

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

Quand 1+α²n=0:

• (I_n / αH^T) est une matrice de parité de rang n
• K = (I_n, αH) génère le code dual
• Par conséquent le code est auto-dual

Détails d'implémentation:

• α peut exister dans GF(p) ou son extension quadratique GF(p²)
• La matrice génératrice est directement donnée sous forme systématique

4. Codes convolutifs auto-duaux (Proposition 2.3)

Construction: H = (A/B), n=2m, A et B chacun m×n

Définition de la matrice génératrice:

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

Vérification de l'auto-dualité:

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

Par conséquent H^T(z) = iB^T + A^Tz est la matrice de parité, et H(z^(-1))z = A+iB génère le code dual

Vérification de non-catastrophalité:

(A+iBz)A^T = nI_m

Par conséquent G(z) possède un inverse polynomial à droite, et le code est non-catastrophal

Calcul de distance:

d_f = d(A) + d(B)

5. Codes convolutifs contenant leur dual (Proposition 2.4)

Construction: H = (A/B), A est r×n, B est (n-r)×n, r>n-r

Définition:

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

Vérification de la propriété DC:

• Construction de la matrice de parité H^T(z) = iB^T + C_1z
• Générateur du code dual: C_1^T + iB
• Vérification que le code dual est contenu dans le code original

Points d'innovation technique

1. Stratégie de partitionnement matriciel: Obtention de différents types de codes à partir d'une même matrice de Hadamard par différents modes de partitionnement
2. Contrôle des paramètres: Réalisation du contrôle du débit (r/n) par sélection du nombre de lignes r
3. Technique d'extension de corps: Utilisation de l'existence de √(-1) pour construire des codes convolutifs
4. Calculabilité de la distance: Calcul algébrique de la distance en utilisant l'orthogonalité de la matrice de Hadamard
5. Cadre unifié: Unification des méthodes de construction pour les codes linéaires en bloc et les codes convolutifs

Configuration expérimentale

Ensemble de données (matrices de Hadamard)

Cet article utilise plusieurs matrices de Hadamard de différentes tailles:

• Petites tailles: H(12), H(20), H(24), H(28)
• Tailles moyennes: H(36), H(40), H(72)
• Grandes tailles: H(144)

Types de matrices:

• Matrices de Hadamard de Paley (utilisées pour les tailles 12k)
• Matrices de Hadamard non-séparables (utilisation préférentielle)

Indicateurs d'évaluation

1. Longueur du code n: Longueur du codage
2. Dimension/Rang r ou k: Nombre de bits d'information
3. Débit: r/n (codes linéaires en bloc) ou k/n (codes convolutifs)
4. Distance minimale d: Mesure de la capacité de correction d'erreurs
5. Mémoire μ: Longueur de mémoire du code convolutif
6. Distance libre d_f: Mesure de distance du code convolutif

Outils de calcul

• Système d'algèbre informatique GAP et ses packages:
  • Package Guava: Calculs de théorie du codage
  • Package Gauss: Opérations matricielles sur corps finis
• Utilisés pour: Opérations sur sous-matrices, calculs sur corps finis, vérification de distance

Détails d'implémentation

• Choix du corps: Utilisation principalement de GF(3), GF(5), GF(7) et leurs extensions GF(3²), GF(5²)
• Calcul de rang: Calcul du rang matriciel au sens modulo p
• Calcul de distance:
  • Petites longueurs (≤100): Calcul direct par ordinateur
  • Grandes longueurs: Utilisation de méthodes algébriques (Proposition 2.6, Lemme 2.18)

Résultats expérimentaux

Résultats principaux

1. Codes construits à partir de H(20)

2. Codes construits à partir de H(28)

3. Propriétés extrémales des codes ternaires

Pour les matrices de Hadamard de Paley de H(12k):

• Construction de codes auto-duaux 12k, 6k, d₃
• Résultats de vérification: Pour k=1,2,3,4,5 (c'est-à-dire n=12,24,36,48,60), les codes construits atteignent la distance optimale
• Borne théorique: d ≤ ⌊n/12⌋+3
• Pour n=72 et au-delà, aucun code extrémal n'existe

Découvertes clés

1. Performance de distance

Codes convolutifs vs codes linéaires en bloc:

• Par exemple H(12):
  • Code linéaire en bloc A: 12,6,6
  • Code convolutif G(z)=A+iBz: distance d_f=12
  • La distance du code convolutif est le double de celle du code linéaire en bloc

2. Flexibilité du débit

• Possibilité de construire des codes LCD de débit arbitraire r/n (0<r<n)
• Codes auto-duaux: débit fixé à 1/2
• Codes convolutifs DC: débit r/n, r≥n/2

3. Propriété de rang (Lemme 2.7)

Pour un nombre premier p|n (p≠2):

rang(H) ≤ n/2 dans GF(p)

Vérification: La matrice de Hadamard de Paley H(12k) a exactement le rang 6k dans GF(3)

Analyse de cas concrets

Exemple prototype 2.9: H(12) détaillé

Décomposition matricielle: H = (A/B), A et B chacun 6×12

Application 1: Code linéaire en bloc auto-dual (GF(3))

• Dans GF(3): AA^T = 0 (car 3|12)
• A génère le code auto-dual 12,6,6₃
• Optimalité: Atteint la distance théorique optimale
• Capacité de correction: Peut corriger 2 erreurs

Application 2: Code LCD (GF(5))

• A génère le code LCD 12,6,6₅
• B génère le code dual, également 12,6,6₅

Application 3: Code convolutif auto-dual (GF(5))

• G(z) = A + 2Bz (2=√(-1) dans GF(5))
• Paramètres: (12,6,6;1,12)₅
• Distance: d_f = d(A) + d(B) = 6+6 = 12
• Non-catastrophalité: (A+2Bz)A^T = 6I₆ = I₆

Application 4: Code auto-dual de longueur 24 (GF(5²))

• Nécessite α²=2, x²-2 irréductible sur GF(5)
• Dans GF(5²): (I₁₂, αH) génère le code auto-dual 24,12,8₅₂

Application 5: Code auto-dual de longueur 24 (GF(7))

• α=2 satisfait 1+12α²=0 dans GF(7)
• (I₁₂, 2H) génère le code auto-dual 24,12,8₇

Exemple 2.10: Code convolutif à mémoire élevée

Construction d'un code convolutif de mémoire 3 à 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³

Paramètres: (12,3,9;3,24) Distance: 24 (car toutes les sous-matrices ont une distance de 6)

Applications à grande échelle

Exemple 2.11: Codes de grande longueur

• H(72): Code auto-dual 72,36,18₃
• H(144): Code 144,72,d₃

Exemple 2.15: H(36)

• Code auto-dual 36,18,12₃ (GF(3))
• Code convolutif auto-dual (36,18,18;1,d)₅ (GF(5))
• Code correcteur d'erreurs quantique: longueur 36, distance d

Travaux connexes

Fondamentaux de la théorie du codage

1. Manuels classiques:
   • Blahut 1: Codes algébriques pour la transmission de données
   • MacWilliams & Sloane 4: Théorie des codes correcteurs d'erreurs
   • McEliece 3: Théorie de l'information et du codage
2. Théorie des codes convolutifs:
   • Johannesson & Zigangirov 2: Fondamentaux du codage convolutif
   • Rosenthal et al. 35,36,38: Codes convolutifs MDS
   • Bocharova et al. 12: Codes convolutifs duaux

Types de codes spéciaux

1. Codes LCD:
   • Massey 30,31: Introduction initiale du concept de code LCD
   • Carlet et al. 15-17: Recherche moderne sur les codes LCD
   • Applications: Défense contre les attaques par canaux auxiliaires 18,19
2. Codes auto-duaux:
   • Mallows & Sloane 29: Bornes supérieures pour les codes auto-duaux
   • Pless 33: Codes symétriques sur GF(3)
   • Mallows et al. 37: Codes auto-duaux sur GF(3)
3. Codes correcteurs d'erreurs quantiques:
   • Calderbank & Shor 14: Construction CSS
   • Calderbank et al. 13: Codes quantiques sur GF(4)
   • Steane 39: Codes correcteurs d'erreurs quantiques simples

Matrices de Hadamard

• van Lint & Wilson 5: Fondamentaux combinatoires
• Horadam 6: Matrices de Hadamard et leurs applications (monographie)

Méthode dérivée d'unités (travaux antérieurs de l'auteur)

• Hurley & Hurley 8,9,22-25: Développement de la méthode dérivée d'unités
• Hurley 27: Codes linéaires en bloc et convolutifs finaux (base de cet article)
• Hurley 26,28: Construction de codes MDS

Avantages de cet article par rapport aux travaux connexes

1. Cadre unifié: Première approche unifiée des codes linéaires en bloc et des codes convolutifs
2. Construction algébrique: Résolution du problème de manque de construction algébrique des codes convolutifs soulevé par McEliece
3. Codes multitypes: Construction de plusieurs types de codes à partir d'une seule matrice
4. Distance calculable: Fourniture de méthodes de calcul algébrique de distance
5. Faisabilité à grande échelle: Possibilité de construire des codes de grande longueur et de débit élevé

Conclusion et discussion

Conclusions principales

1. Contributions théoriques:
   • Établissement d'un cadre théorique complet de construction de codage basé sur les matrices de Hadamard
   • Preuve de 5 propositions fondamentales, fourniture de 4 algorithmes généraux
   • Unification des méthodes de construction pour les codes linéaires en bloc et les codes convolutifs
2. Capacité de construction:
   • Possibilité de construire des codes LCD de débit arbitraire
   • Possibilité de construire des codes auto-duaux, DC et des codes correcteurs d'erreurs quantiques
   • Obtention de multiples types de codes différents à partir d'une seule matrice de Hadamard
3. Avantages de performance:
   • La distance des codes convolutifs peut atteindre le double de celle des codes linéaires en bloc
   • Les codes ternaires atteignent des propriétés extrémales pour les petites longueurs
   • Grande longueur et débit élevé réalisables

Limitations

1. Restrictions du corps:
   • La plupart des constructions nécessitent p∤n
   • Les codes convolutifs auto-duaux nécessitent l'existence de √(-1)
   • Certaines constructions nécessitent une extension de corps
2. Calcul de distance:
   • Difficile de calculer précisément la distance pour les grandes longueurs
   • Dépendance des méthodes algébriques et de la vérification informatique
   • Certains cas ne permettent que des estimations
3. Dépendance à la matrice de Hadamard:
   • Nécessité de connaître préalablement l'expression explicite de la matrice de Hadamard
   • Les matrices de Hadamard non-séparables ont de meilleures performances mais sont difficiles à construire
   • La conjecture de Hadamard non résolue limite les tailles disponibles
4. Codes convolutifs à mémoire élevée:
   • L'article se concentre principalement sur le cas de mémoire 1
   • Les cas de mémoire élevée sont laissés pour des recherches ultérieures (seul l'Exemple 2.10 est donné)
5. Vérification d'application pratique:
   • Absence de tests de performance dans les systèmes de communication réels
   • Analyse insuffisante de la complexité de décodage

Directions futures

1. Extensions théoriques:
   • Construction systématisée de codes convolutifs à mémoire élevée
   • Application d'autres types de matrices orthogonales
   • Recherche approfondie sur les corps non-binaires
2. Amélioration de distance:
   • Bornes de distance plus précises
   • Construction de codes MDS atteignant la borne de Singleton
   • Analyse des propriétés asymptotiques
3. Extensions d'application:
   • Implémentation dans les systèmes de communication réels
   • Applications en informatique quantique
   • Applications en cryptographie
4. Optimisation computationnelle:
   • Algorithmes de décodage efficaces
   • Implémentation parallèle
   • Conception conviviale pour le matériel

Évaluation approfondie

Points forts

1. Forte innovativité théorique:
   • Première approche systématique de l'utilisation des matrices de Hadamard pour construire des codes multitypes
   • Résolution du problème de longue date de la construction algébrique des codes convolutifs
   • Application innovante de la méthode dérivée d'unités
2. Bonne uniformité de la méthode:
   • Traitement unifié des codes linéaires en bloc et des codes convolutifs
   • Cadre unifié pour différents types de codes (LCD, auto-duaux, DC)
   • Chaîne complète de la théorie à l'algorithme à l'application
3. Valeur pratique élevée:
   • Fourniture d'algorithmes de construction explicites
   • Réalisabilité de débits et longueurs arbitraires
   • Facilité d'implémentation avec le système GAP
4. Expérimentation suffisante:
   • Matrices de Hadamard de plusieurs tailles
   • Plusieurs corps finis (GF(3), GF(5), GF(7) et extensions)
   • Exemples prototypes détaillés (Exemple 2.9)
5. Rédaction claire:
   • Structure hiérarchique bien organisée
   • Logique claire entre définitions, propositions, algorithmes et applications
   • Dérivations mathématiques rigoureuses

Insuffisances

1. Complétude théorique:
   • Traitement insuffisamment systématique du cas p|n
   • Théorie incomplète pour les codes convolutifs à mémoire élevée
   • Certaines preuves de propositions trop brèves (par exemple, preuve de distance dans la Proposition 2.3)
2. Limitations expérimentales:
   • Absence de comparaison systématique avec les codes optimaux existants
   • Calcul de distance dépendant principalement de l'ordinateur (longueur ≤100)
   • Absence d'expériences de performance de décodage
3. Orientation insuffisante pour l'application:
   • Comment choisir une matrice de Hadamard appropriée?
   • Stratégies de sélection de paramètres pour différents scénarios d'application?
   • Analyse insuffisante de la complexité de décodage
4. Reproductibilité:
   • Absence de code ou d'implémentation concrète
   • Construction de certaines matrices de Hadamard non expliquée
   • Détails insuffisants de l'implémentation GAP
5. Analyse comparative:
   • Comparaison insuffisante avec les codes de Walsh-Hadamard
   • Absence de comparaison avec d'autres méthodes de construction algébrique
   • Analyse insuffisante du compromis performance-complexité

Influence

1. Contribution académique:
   • Fourniture d'un nouvel outil de construction pour la théorie du codage
   • Promotion de l'application des matrices de Hadamard en codage
   • Susceptible de susciter une série de recherches ultérieures
2. Valeur pratique:
   • Construction de codes correcteurs d'erreurs quantiques avec potentiel d'application réelle
   • Codes LCD avec valeur d'application dans le domaine de la sécurité
   • Construction de codes de grande longueur satisfaisant les besoins de communication moderne
3. Reproductibilité:
   • Méthode théorique claire et reproductible
   • Nécessite le support du système GAP
   • L'implémentation concrète nécessite un travail supplémentaire
4. Limitations:
   • Dépendance à l'existence de matrices de Hadamard
   • Certaines constructions nécessitent une extension de corps
   • L'application dans les systèmes réels nécessite une vérification supplémentaire

Scénarios applicables

1. Recherche théorique:
   • Recherche sur les méthodes de construction algébrique en théorie du codage
   • Recherche sur l'application des matrices de Hadamard
   • Théorie de l'information quantique
2. Applications pratiques:
   • Communication quantique: Construction de codes correcteurs d'erreurs quantiques
   • Communication sécurisée: Codes LCD résistant aux attaques par canaux auxiliaires
   • Stockage de données: Codes de correction d'erreurs de débit élevé
   • Communication sans fil: Application de codes convolutifs
3. Fins pédagogiques:
   • Cas d'étude pour les cours de théorie du codage
   • Exemples d'application de méthodes algébriques en codage
   • Enseignement de l'application des matrices de Hadamard
4. Scénarios non applicables:
   • Applications nécessitant un débit extrêmement élevé (>0,9)
   • Scénarios extrêmement sensibles à la complexité de décodage
   • Applications nécessitant un décodage à décision souple

Références bibliographiques (références clés)

1. 3 McEliece: Manuel classique de théorie de l'information et du codage, soulevant le problème du manque de construction algébrique des codes convolutifs
2. 6 Horadam: Monographie d'autorité sur les matrices de Hadamard et leurs applications
3. 13,14 Calderbank & Shor: Travaux fondateurs de la construction CSS de codes correcteurs d'erreurs quantiques
4. 27 Hurley: Base théorique de cet article, codes linéaires en bloc et convolutifs finaux
5. 31 Massey: Travail fondateur sur les codes LCD
6. 35,38 Rosenthal et al.: Recherche importante sur les codes convolutifs MDS

Évaluation générale: Cet article est un excellent travail avec une forte innovativité théorique et une méthode systématique et complète. L'auteur a réussi à combiner les matrices de Hadamard avec la méthode dérivée d'unités, établissant un cadre unifié pour la construction de codages multitypes, en particulier en résolvant le problème difficile de la construction algébrique des codes convolutifs. La valeur principale de l'article réside dans la fourniture d'une méthodologie complète allant de la théorie à l'algorithme à l'application, avec une signification académique et un potentiel d'application considérables. Les principales insuffisances résident dans l'incomplétude de la théorie des codes convolutifs à mémoire élevée et l'insuffisance de la vérification d'application pratique. Il est recommandé que les travaux ultérieurs renforcent l'implémentation dans les systèmes réels et les tests de performance.