An Ordered-Reliability-Bits Chase Decoding Algorithm for BCH Codes

Résumé Technique : Algorithme de Décodage Chase à Bits d'Ordre de Fiabilité pour les Codes BCH

Énoncé du Problème
Le codage de canal à faible longueur de bloc est critique pour des applications telles que les communications ultra-fiables et à faible latence (URLLC) et les réseaux de transport optique (OTN). Les codes de Bose-Chaudhuri-Hocquenghem (BCH) sont largement utilisés dans ces scénarios en raison de leur forte structure algébrique et de leur grande distance minimale. Bien que les algorithmes de décodage à décision dure comme Berlekamp-Massey (BM) soient efficaces, ils sont limités par la capacité de correction d'erreurs intrinsèque du code et ne peuvent pas pleinement réaliser le potentiel de performance de celui-ci. Le décodage à décision douce (SDD) offre des performances améliorées mais entraîne souvent une complexité de calcul élevée. Les approches de SDD existantes, telles que l'algorithme de Chase et le décodage par supposition de bruit additif aléatoire (GRAND), font face à un compromis : atteindre une performance proche du maximum de vraisemblance (ML) nécessite généralement une augmentation exponentielle de la complexité de décage (par exemple, traverser $2^p$ motifs de test dans le décodage Chase). L'article traite du défi de réduire cette complexité tout en maintenant une haute performance de décodage.

Méthodologie
Les auteurs proposent un algorithme de décodage Ordered-Reliability-Bits Chase (ORB-Chase) à faible complexité. Cette méthode modifie l'algorithme de Chase traditionnel de deux manières principales :

1. Génération de Motifs d'Erreur de Test (TEP) basée sur le Poids Logique :
   Au lieu de générer des motifs de test basés uniquement sur les bits les moins fiables (LRB) ou des combinaisons fixes, l'algorithme utilise le poids logique comme métrique pour ordonner les TEP.

   • Les bits sont triés par fiabilité (ordre croissant de la magnitude LLR).
   • Le poids logique $w_L(e_n)$ d'un motif de test est défini comme la somme des positions des bits inversés dans cette séquence triée ($w_L(e_n) = \sum i \cdot e_i$).
   • Les TEP sont générés dans l'ordre croissant de leurs poids logiques. Pour les motifs ayant des poids logiques identiques, un générateur de partitions d'entiers garantit qu'ils sont triés par ordre croissant de poids de Hamming. Cet ordonnancement approxime la vraisemblance des séquences de bruit, privilégiant les motifs d'erreur les plus probables.

2. Critère de Terminaison Précoce à Base d'Entiers :
   L'algorithme introduit un critère pour déterminer si un mot de code candidat généré est le mot de code ML, permettant de terminer le processus de décodage de manière précoce sans générer la liste complète des candidats.

   • La méthode adapte le « Critère d'Optimalité » issu de la littérature antérieure, qui compare l'écart de corrélation d'un mot de code contre une borne inférieure dérivée des bits les plus fiables.
   • Pour réduire la surcharge de calcul, les auteurs remplacent les valeurs de fiabilité à virgule flottante par des représentations de fiabilité entières. Ceci est réalisé en ajustant une courbe linéaire par morceaux aux valeurs de fiabilité triées et en quantifiant la pente à 1.
   • La condition de terminaison vérifie si la somme des fiabilités entières des bits inversés est inférieure ou égale à la somme des fiabilités entières des bits les plus fiables qui pourraient potentiellement être inversés pour améliorer la métrique. Si la condition est satisfaite, le mot de code actuel est accepté comme ML, et le décodage s'arrête.

Contributions Clés

• Conception d'Algorithme : La proposition de l'algorithme ORB-Chase, qui intègre l'ordonnancement par poids logique pour la génération de TEP et un mécanisme de terminaison précoce à base d'entiers.
• Réduction de la Complexité : L'introduction d'une limite flexible sur le nombre maximum de motifs de test ($\ell_{max}$) et d'un critère de terminaison précoce qui réduit considérablement le nombre d'appels de décodage Berlekamp-Massey (BM) par rapport à l'algorithme de Chase traditionnel.
• Validation de l'Approximation : La démonstration que le critère basé sur les entiers fournit une approximation pratique précise du processus d'identification ML, avec une perte de performance négligeable par rapport au Critère d'Optimalité à virgule flottante.

Résultats
Des simulations ont été menées pour des codes BCH (127, 113, 5) et des codes BCH étendus (eBCH) (256, 239, 6) sur un canal AWGN avec modulation BPSK.

• Performance vs ORBGRAND : Pour le code (127, 113, 5), l'algorithme ORB-Chase avec $\ell_{max}=16$ a surpassé l'algorithme ORBGRAND avec $\ell_{max}=16$ d'environ 1,5 dB à un taux d'erreur de bloc (BLER) de $10^{-3}$. L'algorithme ORB-Chase avec $\ell_{max}=200$ s'est approché de la borne inférieure ML, tandis qu'ORBGRAND nécessitait beaucoup plus de requêtes ($\ell_{max}=10^5$) pour atteindre une performance similaire.
• Comparaison de Complexité avec Chase :
  • Le nombre moyen d'appels de décodage BM a été utilisé comme principale métrique de complexité.
  • Pour le code (127, 113, 5), à $E_b/N_0 = 6$ dB, l'algorithme ORB-Chase a réduit le nombre moyen d'appels BM de 92,3 % (pour $\ell_{max}=16$) et de 98,0 % (pour $\ell_{max}=200$) par rapport à l'algorithme de Chase atteignant la même performance de BLER.
  • Des tendances similaires ont été observées pour le code eBCH (256, 239, 6), avec des réductions de complexité allant jusqu'à 98,1 % à haut SNR.
• Efficacité de la Terminaison : Il a été démontré que le critère de terminaison précoce basé sur les entiers prend les mêmes décisions de terminaison précoce que le Critère d'Optimalité à virgule flottante dans presque tous les cas simulés, validant ainsi sa précision.

Signification et Revendications
L'article affirme que l'algorithme ORB-Chase offre un excellent compromis entre la performance de correction d'erreurs et la complexité de calcul. En atteignant une performance proche du ML avec nettement moins de motifs de test et d'appels BM, l'algorithme est présenté comme un candidat prometteur pour les applications pratiques nécessitant un décodage à décision douce efficace des codes BCH courts. Les auteurs notent que l'efficacité de l'algorithme augmente avec un $E_b/N_0$ plus élevé, où le nombre moyen de tentatives de décodage chute rapidement. Un travail futur est identifié comme étant potentiellement l'optimisation supplémentaire de l'ordre de génération des motifs d'erreur de test, mais la contribution actuelle se concentre sur l'efficacité de l'ordonnancement par poids logique et de la terminaison basée sur les entiers.