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

Sintesi Tecnica: Algoritmo di Decodifica Chase a Bit di Affidabilità Ordinati per Codici BCH

Definizione del Problema
La codifica di canale a breve lunghezza di blocco è critica per applicazioni quali le comunicazioni ultra-affidabili a bassa latenza (URLLC) e le reti di trasporto ottico (OTN). I codici Bose-Chaudhuri-Hocquenghem (BCH) sono ampiamente utilizzati in questi scenari grazie alla loro forte struttura algebrica e al grande distanza minima. Sebbene gli algoritmi di decodifica a decisione hard come il Berlekamp-Massey (BM) siano efficienti, essi sono limitati dalla capacità intrinseca di correzione degli errori del codice e non possono realizzare appieno il potenziale del codice stesso. La decodifica a decisione soft (SDD) offre prestazioni migliorate, ma spesso comporta un'elevata complessità computazionale. Gli approcci SDD esistenti, come l'algoritmo Chase e il Guessing Random Additive Noise Decoding (GRAND), affrontano un compromesso: raggiungere prestazioni vicine alla massima verosimiglianza (ML) richiede tipicamente un aumento esponenziale della complessità di decodifica (ad esempio, attraversando $2^p$ pattern di test nel decoding Chase). Il documento affronta la sfida di ridurre tale complessità mantenendo un'elevata prestazione di decodifica.

Metodologia
Gli autori propongono un algoritmo di decodifica Chase a bit di affidabilità ordinati (ORB-Chase) a bassa complessità. Questo metodo modifica l'algoritmo Chase tradizionale in due modi primari:

1. Generazione di Pattern di Errore di Test (TEP) basata sul Peso Logico:
   Invece di generare pattern di test basandosi esclusivamente sui bit meno affidabili (LRB) o su combinazioni fisse, l'algoritmo utilizza il peso logico come metrica per ordinare i TEP.

   • I bit sono ordinati per affidabilità (ordine crescente del modulo LLR).
   • Il peso logico $w_L(e_n)$ di un pattern di test è definito come la somma delle posizioni dei bit invertiti in questa sequenza ordinata ($w_L(e_n) = \sum i \cdot e_i$).
   • I TEP sono generati in ordine crescente dei loro pesi logici. Per i pattern con pesi logici identici, un generatore di partizioni intere assicura che siano ordinati per peso di Hamming crescente. Questo ordinamento approssima la verosimiglianza delle sequenze di rumore, dando priorità ai pattern di errore più probabili.

2. Criterio di Terminazione Anticipata Basato su Interi:
   L'algoritmo introduce un criterio per determinare se un codeword candidato generato è il codeword ML, consentendo al processo di decodifica di terminare anticipatamente senza generare l'elenco completo dei candidati.

   • Il metodo adatta il "Criterio di Ottimalità" dalla letteratura precedente, che confronta la discrepanza di correlazione di un codeword contro un limite inferiore derivato dai bit più affidabili.
   • Per ridurre l'overhead computazionale, gli autori sostituiscono i valori di affidabilità in virgola mobile con rappresentazioni di affidabilità intere. Ciò viene ottenuto adattando una curva lineare a tratti ai valori di affidabilità ordinati e quantizzando la pendenza a 1.
   • La condizione di terminazione verifica se la somma delle affidabilità intere dei bit invertiti è minore o uguale alla somma delle affidabilità intere dei bit più affidabili che potrebbero potenzialmente essere invertiti per migliorare la metrica. Se soddisfatta, il codeword corrente è accettato come ML e la decodifica si interrompe.

Contributi Chiave

• Design dell'Algoritmo: La proposta dell'algoritmo ORB-Chase, che integra l'ordinamento del peso logico per la generazione dei TEP e un meccanismo di terminazione anticipata basato su interi.
• Riduzione della Complessità: L'introduzione di un limite flessibile sul numero massimo di pattern di test ($\ell_{max}$) e di un criterio di terminazione anticipata che riduce significativamente il numero di chiamate al decoding Berlekamp-Massey (BM) rispetto al tradizionale algoritmo Chase.
• Validazione dell'Approssimazione: La dimostrazione che il criterio basato su interi fornisce un'approssimazione pratica accurata del processo di identificazione ML, con una perdita di prestazioni trascurabile rispetto al Criterio di Ottimalità in virgola mobile.

Risultati
Le simulazioni sono state condotte per codici BCH (127, 113, 5) e codici BCH estesi (eBCH) (256, 239, 6) su un canale AWGN con modulazione BPSK.

• Performance vs ORBGRAND: Per il codice (127, 113, 5), l'algoritmo ORB-Chase con $\ell_{max}=16$ ha superato l'algoritmo ORBGRAND con $\ell_{max}=16$ di circa 1,5 dB a un Block Error Rate (BLER) di $10^{-3}$. L'algoritmo ORB-Chase con $\ell_{max}=200$ si è avvicinato al limite inferiore ML, mentre ORBGRAND richiedeva significativamente più query ($\ell_{max}=10^5$) per ottenere prestazioni simili.
• Confronto della Complessità con Chase:
  • Il numero medio di chiamate al decoding BM è stato utilizzato come metrica primaria di complessità.
  • Per il codice (127, 113, 5), a $E_b/N_0 = 6$ dB, l'algoritmo ORB-Chase ha ridotto il numero medio di chiamate BM del 92,3% (per $\ell_{max}=16$) e del 98,0% (per $\ell_{max}=200$) rispetto all'algoritmo Chase che raggiungeva lo stesso BLER.
  • Simili tendenze sono state osservate per il codice eBCH (256, 239, 6), con riduzioni della complessità fino al 98,1% ad alto SNR.
• Efficacia della Terminazione: È stato dimostrato che il criterio di terminazione anticipata basato su interi compie le stesse decisioni di terminazione anticipata del Criterio di Ottimalità in virgola mobile in quasi tutti i casi simulati, validandone l'accuratezza.

Significatività e Rivendicazioni
Il documento afferma che l'algoritmo ORB-Chase offre un eccellente compromesso tra prestazioni di correzione degli errori e complessità computazionale. Raggiungendo prestazioni vicine alla ML con significativamente meno pattern di test e chiamate BM, l'algoritmo si presenta come un candidato promettente per applicazioni pratiche che richiedono una decodifica soft efficiente di codici BCH brevi. Gli autori osservano che l'efficienza dell'algoritmo aumenta con un $E_b/N_0$ più elevato, dove il numero medio di tentativi di decodifica scende rapidamente. Il lavoro futuro è identificato come l'ottimizzazione ulteriore dell'ordine di generazione dei pattern di errore di test, ma il contributo attuale si concentra sull'efficacia dell'ordinamento del peso logico e della terminazione basata su interi.