ITTO20120829A1 - Method and system for generating channel codes, in particular for a frame-header - Google Patents

Description

“METODO E SISTEMA PER GENERARE CODICI DI CANALE, IN PARTICOLARE PER UN FRAME-HEADERâ€

DESCRIZIONE

Campo dell’invenzione

La presente invenzione riguarda un metodo e un sistema per generare codici di canale, in particolare codici di canale per un frame-header in un sistema di comunicazione ACM (“Adaptive Coding and Modulation†).

Descrizione dell’arte nota

L’adattamento in tempo reale dei parametri di trasmissione in base alle condizioni del canale rappresenta una caratteristica altamente desiderabile in sistemi di comunicazione dove i parametri di canale possono variare nel tempo o da un ricevitore all’altro.

La variazione delle condizioni del canale nel tempo e/o tra i diversi utenti à ̈ una caratteristica importante della maggior parte dei sistemi di comunicazione, come i sistemi satellitari, di rete e di diffusione.

Secondo l’arte nota, in tali sistemi sono stati proposti schemi di codifica e modulazione adattiva per ottenere significativi incrementi di capacità mediante l’adattamento in tempo reale del tasso/lunghezza del codice FEC (“Forward Error Correction†) e della costellazione della modulazione.

L’idea principale di uno schema ACM consiste nell’incrementare la capacità di un sistema di comunicazione evitando lo spreco di risorse dovuto all’adozione di uno scenario fisso a livello fisico, con cui à ̈ necessario sacrificare l’efficienza spettrale per garantire buone prestazioni anche all’utente con le peggiori condizioni di canale.

Impiegando uno schema ACM, il trasmettitore à ̈ in grado di commutare tra diverse costellazioni e codici scegliendo una modulazione e un tasso di codifica il più elevati possibile che assicurino un DER (“Detection Error Rate†, tasso di errore di rilevamento) desiderato, garantendo in tal modo la massima efficienza spettrale per ogni utente. Al ricevitore, per poter decodificare con successo il messaggio, ogni utente deve essere in grado di decidere se il messaggio à ̈ destinato a lui e/o di riconoscere i parametri della costellazione e del codice utilizzato dal trasmettitore.

In generale, ogni pacchetto inviato dal trasmettitore à ̈ costituito da due parti principali. La prima parte à ̈ denominata frame-header, o semplicemente header, e contiene le informazioni relative alla modulazione e alla codifica, di seguito indicate con l’acronimo ACMI (“Adaptive Coding and Modulation Indicator†).

La seconda parte contiene il messaggio codificato utilizzando i corrispondenti parametri ACMI.

Ogni utente deve quindi prima decodificare le informazioni contenute nel frame-header per poter decodificare il resto del messaggio.

In applicazioni come la diffusione satellitare, la strategia di codifica non à ̈ priva di importanza, a causa dell’ampia gamma dinamica dell’SNR (“Signal to Noise Ratio†, rapporto segnale-rumore), che va tipicamente da -15 dB a 15 dB. Il semplice uso di uno schema ACM può non essere sufficiente a garantire il collegamento radio, una buona efficienza spettrale e una probabilità di errore desiderata al ricevitore.

E’ quindi importante migliorare l’efficienza spettrale mediante la generazione di un codice che consenta di ridurre al minimo la lunghezza media e massima di un frameheader.

Nella domanda di brevetto no. US 2010/0128661, la procedura di generazione del codice si basa su considerazioni euristiche, senza alcun tentativo di minimizzare la lunghezza del frame-header. Il codice a lunghezza variabile consiste nella ripetizione di un singolo e robusto codice Reed-Muller per far fronte alle diverse condizioni di rapporto segnale-rumore.

Tuttavia detta domanda di brevetto non insegna a minimizzare la lunghezza di un frameheader.

Scopo della presente invenzione à ̈ indicare un metodo e un sistema per generare codici di canale, in particolare per un frame-header, capaci di minimizzare una lunghezza media e massima di un frame-header di un pacchetto di dati.

Un ulteriore scopo della presente invenzione consiste nell’indicare un metodo e un sistema per generare codici di canale, in particolare per un frame-header, capaci di massimizzare l’efficienza spettrale di un sistema di comunicazione.

Un ulteriore scopo della presente invenzione consiste nell’indicare un metodo e un sistema per generare codici di canale, in particolare per un frame-header, capaci di migliorare la capacità di correzione del codice di canale generato.

Un ulteriore scopo della presente invenzione consiste nell’indicare un metodo e un sistema per generare codici di canale, in particolare per un frame-header, capaci di ridurre la complessità computazionale di un decodificatore.

Un ulteriore scopo della presente invenzione consiste nell’indicare un metodo e un sistema per generare codici di canale, in particolare per un frame-header, capaci di ottenere una lunghezza fissa per tutte le parole di codice in modo da avere la stessa complessità di un decodificatore a massima verosimiglianza di un codice a lunghezza variabile.

Questi e altri scopi dell’invenzione sono ottenuti attraverso un metodo e un sistema per generare codici di canale, in particolare per un frame-header, come definito nelle rivendicazioni allegate, che sono parte integrante della presente descrizione.

Descrizione dettagliata

In sintesi, si descrive un metodo per generare un codice di canale, in particolare per un frame-header, in cui almeno una parola di codice di detto codice di canale à ̈ ottenuta per mezzo di almeno una concatenazione di parole di codice di due codici costituenti, e tale concatenazione à ̈ eseguita su sottoinsiemi di parole di codice di un primo codice costituente, avente lunghezza massima, con parole di codice di un secondo codice costituente.

Gli utenti sono suddivisi, ad esempio, in un più piccolo insieme di M tipi in base alla qualità del loro collegamento radio. Ogni tipo di utente i à ̈ associato ad un rapporto segnale-rumore disponibile SNRi. Si assume che per qualsiasi due tipi di utenti k e m, se k > m, allora SNRk> SNRm.

Un insieme di modi ACM massimi, ACMi, à ̈ associato all’insieme di tipi di utenti. Ogni tipo di utente i deve essere in grado di rilevare e decodificare tutti i pacchetti codificati con modo ACM j ≤ i, corrispondenti a un rapporto segnale-rumore SNR minore o uguale a quello associato al tipo di utente i. Di conseguenza, gli utenti di tipi superiori, corrispondenti a valori SNR elevati, devono essere in grado di rilevare il modo ACM all’interno di un insieme più grande di quello degli utenti di tipo inferiore.

Ciò corrisponde alla generazione di un codice che ammette una sequenza di sottoinsiemi di parole di codice di tale codice con differenze molto ampie nelle capacità di correzione.

Ulteriori caratteristiche dell’invenzione sono definite nelle rivendicazioni allegate, che sono da intendersi parte integrante della presente descrizione.

I suddetti scopi appariranno più chiari dalla descrizione dettagliata che segue di un metodo per generare codici di canale, con particolare riferimento ai disegni allegati, in cui:

- la Figura 1 mostra uno schema a blocchi di un sistema di comunicazione;

- le Figure 2 e 3 mostrano modalità di funzionamento di un rilevatore di ACMI per un tipo di utente i;

- la Figura 4 mostra un esempio di generazione di un codice utilizzando una codifica a lunghezza variabile;

- la Figura 5 mostra parametri di codici per un codice a lunghezza variabile con trentadue modi utilizzante il metodo secondo la presente invenzione e il limite di Hamming con DER (“Detection Error Rate†) uguale a 10<-6>;

- la Figura 6 mostra parametri di codici per un codice a lunghezza variabile con trentadue modi utilizzante codici lineari secondo l’arte nota con DER uguale a 10<-6>; - la Figura 7 mostra parametri di codici per un codice a lunghezza variabile con quarantotto modi utilizzante codici ottimali lineari secondo l’arte nota con DER uguale a 10<-8>;

- le Figure 8 e 9 mostrano parametri di codici per un codice a lunghezza variabile utilizzante il metodo secondo la presente invenzione e codici ottimali lineari secondo l’arte nota con DER uguale a 10<-8>, con rispettivamente trentadue e quarantotto modi; - la Figura 10 mostra un grafico relativo ai dati di Fig.8;

- le Figure 11a e 11b mostrano parole di codice del codice di Fig.8;

- le Figure 12 e 13 mostrano rispettivamente l’andamento della lunghezza richiesta per il pacchetto header rispetto al minimo rapporto segnale-rumore SNR per alcuni valori di k bit con DER fissato a 10<-6>e dati relativi a Figura 12, corrispondente ad una costruzione lineare del caso peggiore per un un frame-header;

- le Figure 14 e 15 mostrano rispettivamente l’andamento della lunghezza richiesta per il pacchetto header rispetto al minimo rapporto segnale-rumore SNR per alcuni valori di k bit con DER fissato a 10<-8>e dati relativi a Figura 14, corrispondente ad una costruzione lineare del caso peggiore per un un frame-header.

Con riferimento a Fig.1, viene mostrato un sistema di comunicazione 10 utilizzato nella descrizione dettagliata della presente invenzione quale esempio di scenario di sistema. Una pluralità di utenti à ̈ servita da un gateway 1 attraverso un transponder satellitare 2, e il gateway 1 comprende almeno un codificatore 3 che genera almeno un codice.

Gli utenti sono suddivisi in M tipi, ad esempio M ≤ 64, in base alla qualità corrente del loro collegamento radio, e tale suddivisione à ̈ operata da un progettista durante la progettazione del sistema di comunicazione 10.

Ogni tipo di utente i à ̈ associato a un rapporto segnale-rumore disponibile SNRie si assume che, senza perdere per questo in generalità, SNRi≤ SNRi+1≤…..≤ SNRM. Quest’ultima condizione à ̈ tipica dei sistemi di comunicazione satellitari. In questo modo, il rapporto segnale-rumore risulta diverso per ciascun tipo di utente i. Inoltre ogni tipo di utente i comprende almeno un utente fisico.

Ad ogni tipo di utente i à ̈ associato un insieme di modi ACM massimi. Ciascun tipo di utente i deve essere in grado di rilevare e decodificare tutti i pacchetti codificati con modo ACMjcon j ≤ i. Un canale di feedback, non rappresentato in Fig.1, permette al gateway 1 di conoscere il tipo i di ciascun utente.

Inoltre, il gateway 1 ha la possibilità di scegliere per ciascun tipo di utente i un modo ACM con indice j ≤ i. La scelta di un valore al di sotto del valore massimo ammesso i, che in linea di principio à ̈ subottimale per la capacità totale del sistema, consente una certa flessibilità presso il gateway 1. Questa flessibilità aggiuntiva del sistema tuttavia necessita che il tipo di utente i rilevi e decodifichi tutti i modi ACMjcon j ≤ i. Questo requisito impone un’elevata complessità di rilevamento, specialmente per gli utenti associati a valori SNR elevati. In particolare, gli utenti con il tipo di utente più alto M devono rilevare e decodificare tutti i pacchetti provenienti da un satellite. Il filtraggio dei pacchetti, in accordo con la reale destinazione prevista, viene differito dopo il processo di decodifica.

Con riferimento a Fig. 2, in essa à ̈ mostrata una modalità di funzionamento di un ricevitore 23 comprendente un rilevatore di ACMI 21 per un tipo di utente i, e un segnale di ingresso y, nel sistema di comunicazione 10 descritto in Fig.1. Il rilevatore di ACMI 21 fornisce un indice nell’intervallo [1, . . . , i], che denota una stima di un indice ACM entro l’intervallo ammesso, oppure il simbolo convenzionale “0†per denotare un errore di rilevamento che blocca un successivo decodificatore 22.

In questo esempio di sistema di comunicazione 10, per un ACMI sono previsti i seguenti tipi di eventi:

- Errore di rilevamento:

Questa indica la probabilità che l’ , stimato dal rivelatore ACMI 21, venga trasmesso al decodificatore 22 dal rivelatore ACMI 21 e non sia uguale all’ACMIjricevuto dal gateway 1, assumendo che l’indice j sia minore o uguale all’indice i del tipo di utente. Un pacchetto potenzialmente destinato al tipo di utente i viene decodificato con un modo ACM non corretto e di conseguenza non viene consegnato correttamente.

- Decodifica inutile:

Questa indica la probabilità che l’ , stimato dal rilevatore di ACMI 21, venga trasmesso al decodificatore 22 dal rilevatore di ACMI 21 e non sia uguale a zero, assumendo che l’indice j sia maggiore dell’indice i del tipo di utente. Un pacchetto non destinato a utenti di tipo j viene decodificato non correttamente con un formato errato. L’unico costo consiste in un’inutile decodifica.

Da quanto sopra si deduce che à ̈ importante progettare e generare codici per ridurre al minimo la probabilità dell’errore di rilevamento , dato che il costo della decodifica inutile à ̈ solo marginale.

Con riferimento a Fig. 3, vale la pena di notare che eliminando la flessibilità per il gateway 1 di scegliere un modo j ≤ i, e quindi imponendo j = i presso il gateway 1, la sola funzione di un rilevatore di ACMI 31 consiste nell’attivare o bloccare un successivo decodificatore 32. Un errore del rilevatore di ACMI 31 causerebbe solamente un inutile evento di decodifica. Il numero di decodifiche inutili può essere in questo caso drasticamente ridotto anche per gli utenti con una buona qualità di collegamento.

In un primo esempio della presente invenzione si descrive un metodo per generare un codice di canale per ridurre al minimo la succitata probabilità di errore di rilevamento , a cui à ̈ associato un DER (“Detection Error Rate†) di valore ϵ, utilizzante parole di codice a lunghezza variabile.

L’insieme di parole di codice à ̈ generato con lunghezze variabili secondo il seguente algoritmo, mostrato in Fig.4:

1. Definire un insieme di M valori SNR ordinati SNRicorrispondenti alle soglie dei modi desiderati e un DER desiderato ϵ;

2. Impostare una distanza totale dT= 0;

3. Per tutti gli i decrescenti da M a 2;

4. Calcolare la distanza incrementale richiesta per ottenere il DER desiderato ϵ all’SNRitarget

(1)

La distanza minima o dipende da un rapporto segnale-rumore SNR e da un tasso di errore di rilevamento con valore . Inoltre, la distanza minima aumenta per ogni sottoinsieme di codice generato e viene calcolata per ogni tipo di utente i.

5. Se = 0, ripetere dal passo 3.

6. In caso contrario, generare un codice con parole di codice aventi lunghezza minimizzata ni, i parole di codice e distanza minima di

7. Impostare la distanza totale dT= dT+ di

8. Ripetere dal passo 3.

9. L’insieme di parole di codice a lunghezza variabile à ̈ infine ottenuto concatenando una parola di codice da ciascuno dei codici costituenti (v. Fig. 4). La parola di codice del modo i à ̈ quindi ottenuta concatenando parole di codice di codici costituenti in ordine decrescente da M a i, ed ha una lunghezza totale come segue:

Con riferimento a Fig.4, almeno una parola di codice di codici costituenti à ̈ incapsulata in una parola di codice del codice di canale, e almeno una parola di codice del codice di canale ha una lunghezza maggiore delle rimanenti parole di codice di tale codice di canale. Inoltre, la concatenazione viene eseguita su sottoinsiemi di parole di codice di un primo codice costituente, avente lunghezza massima, con parole di codice di un secondo codice costituente.

Nella formula (1) Ã ̈ definita la seguente funzione:

(3)

in cui Q Ã ̈ la funzione Q, ossia la funzione di distribuzione cumulativa complementare della variabile aleatoria gaussiana standard.

La formula (3) fornisce la distanza minima richiesta per un codice di canale con M parole di codice per ottenere un tasso di errore di rilevamento al rapporto segnalerumore SNR. Questa formula (3) si ottiene utilizzando il limite superiore:

(4)

che à ̈ piuttosto precisa per valori piccoli di M e codici quasi perfetti.

Per avere un limite inferiore di ciò che à ̈ possibile ottenere, si utilizza, ad esempio, il limite di Hamming

in cui t à ̈ il massimo peso dei vettori di errore sicuramente corretti dalla decodifica a minima distanza, per trovare la lunghezza minima n di un codice con M parole di codice e la distanza minima dminrichiesta al passo 6 dell’algoritmo precedente.

Con riferimento alla Fig. 5, in essa à ̈ mostrato un risultato di una generazione di un codice di canale che utilizza il precedente algoritmo per un sistema con 32 modi, rapporto segnale-rumore SNR con dinamica da 15 a -16 dB a incrementi di 1dB, per un DER desiderato = 10<−6>.

Le colonne della tabella di Fig. 5 indicano, da sinistra a destra, il numero di parole di codice i, che à ̈ anche l’indice del tipo di utente, il corrispondente rapporto segnalerumore SNRi, la lunghezza incrementale della parola di codice nidi un header con indice i, il numero di bit kidella parola di codice di un header all’indice i, la distanza minima incrementale della parola di codice didi un header all’indice i, la distanza minima totale dT, ossia la somma, all’indice i, delle precedenti di, la lunghezza totale della parola di codice Nidi un header, ossia la somma, all’indice i, delle precedenti nie, nell’ultima colonna,i xN , che indica la complessità di decodifica.

Si deve notare che in questo caso la lunghezza massima della parola di codice Nià ̈ di 464 simboli, come indicato dal riferimento 51, e la lunghezza media dell’header , assumendo che tutte i modi abbiano la stessa probabilità, à ̈ di soli 119 simboli, come indicato dal riferimento 52.

Il limite di Hamming à ̈ un limite superiore del numero di parole di codice, e sono pochi i codici in grado di raggiungerlo.

Con riferimento a Fig. 6, in essa si riporta un risultato di una generazione di un codice di canale utilizzante codici costituenti lineari ottimali noti allo stato dell’arte, ricavati da tabelle reperite in M. Grassl, “Bounds on the minimum distance of linear codes and quantum codes†, pubblicato nel 2007 e disponibile on-line all’indirizzo http://www.codetables.de.

Questi codici costituenti lineari, noti allo stato dell’arte, presentano il vincolo aggiuntivo di avere un numero di parole di codice uguale a una potenza di due, ossia 2<k>, dove k à ̈ il numero di bit di informazione. L’impiego di questi codici lineari richiede una lunghezza massima della parola di codice di 609 simboli, come indicato dal riferimento 61, e una lunghezza media dell’header di soli 149 simboli, come indicato dal riferimento 62.

Confrontando Fig. 5 e Fig. 6, risulta chiaro quindi che il codice di canale generato utilizzando il precedente algoritmo secondo la presente invenzione à ̈ in grado di minimizzare la lunghezza media e massima di un frame-header di un pacchetto di dati. Con riferimento alla Fig. 7, viene confrontato un esempio di lunghezza di un codice generato secondo la presente invenzione per 48 modi con la lunghezza richiesta dell’header per lo schema di segnalazione specificato in D. Becker, N. Velayudhan, A. Loh, J. O’Neill e V. Padmanabhan, “Efficient control signaling over shared communication channels with wide dynamic range†, descritto nella domanda di brevetto statunitense no. 12/621.203. Il DER à ̈ fissato a = 10<−8>.

Come si può notare, il metodo di generazione di un codice di canale proposto dalla presente invenzione consente nel ridurre considerevolmente la lunghezza dell’header per tutti i modi. La lunghezza media dell’header secondo la domanda di brevetto statunitense no. 12/621.203 à ̈ 750 (riferimento 71), mentre la lunghezza media dell’header (riferimento 72) si riduce a 301 secondo questo esempio della presente invenzione; allo stesso modo, la lunghezza massima dell’header si riduce da 4416 (riferimento 73) a 1285 (riferimento 74).

Pertanto, utilizzando il metodo secondo la presente invenzione, valutando la lunghezza media si ottiene un miglioramento di circa il 60%.

Il succitato algoritmo, quando applicato a codici costituenti lineari, presenta alcuni punti deboli nella lunghezza del codice di canale. Ciò à ̈ dovuto principalmente al fatto che il numero di parole di codice di un codice costituente lineare à ̈ sempre una potenza di 2.

In questo caso, ad esempio, tutti i modi da 32 a 17 in Fig. 6 condividono la stessa dimensione. In tali casi à ̈ utile generare un singolo codice costituente che garantisca una buona distanza minima anziché utilizzare un approccio completamente incrementale come quello sopra descritto.

Si propone allora il seguente esempio di algoritmo modificato per la generazione di un codice:

1. Definire un insieme di M valori ordinati corrispondenti alle soglie dei modi desiderati e un DER desiderato .

2. Impostare dT,M+1= 0 e NT,M+1= 0.

3. Per tutti gli i decrescenti da M a 2

4. Impostare

5. Calcolare la distanza minima richiesta

6. Per tutti gli (modo con la stessa dimensione del codice)

7. Calcolare la distanza incrementale

8. Generare un codice lineare ( ) con lunghezza minima .

Si noti che, quando l’incremento di distanza à ̈ zero, il codice ha lunghezza 0. In questo caso, k à ̈ il numero di bit di informazione, non il numero di parole di codice. 9. Ripetere da 6.

10. Scegliere dal precedente insieme di codici quello con lunghezza totale minima corrispondente a

11. Impostare

12. Ripetere dal passo 3.

13. L’insieme di parole di codice a lunghezza variabile à ̈ infine ottenuto concatenando parole di codice da ciascuno dei codici costituenti (v. Fig.4).

Come si può notare in questo esempio, ad ogni passo vengono considerati tutti i possibili codici costituenti con la stessa dimensione k che garantiscono la distanza minima . Questa generazione consente, ai passi i dell’iterazione, di cambiare i codici generati ai passi precedenti j ≥ i, a condizione che .

Sempre con riferimento al caso di Fig. 4, almeno una parola di codice di codici costituenti à ̈ incapsulata in una parola di codice del codice di canale, e almeno una parola di codice del codice di canale ha una lunghezza maggiore delle rimanenti parole di codice di tale codice di canale. Inoltre, la concatenazione viene eseguita su sottoinsiemi di parole di codice di un primo codice costituente, avente lunghezza massima, con parole di codice di un secondo codice costituente.

I risultati di questa nuova generazione di codici sono riportati nelle Fig. 8 e Fig. 9, e quest’ultima à ̈ confrontata con Fig. 7. E’ importante notare che questa nuova generazione di codici consente di ridurre leggermente sia la lunghezza media sia la lunghezza massima dell’header.

Infatti, la lunghezza massima dell’header di Fig. 9 à ̈ di 1239 simboli, come indicato dal riferimento 91, ed à ̈ minore della lunghezza massima di 1285 simboli dell’header di Fig. 7, indicata dal riferimento 74; mentre la lunghezza media dell’header si riduce da 301 simboli, come indicato dal riferimento 72, a 285 simboli, come indicato dal riferimento 92.

Occorre inoltre notare che si riduce il numero di codici generati. Un esempio di codice generato à ̈ rappresentato in Fig. 10, mentre Fig. 11a e Fig. 11b mostrano le relative parole di codice.

Con riferimento a Fig. 10, in essa sono riportati i risultati di una simulazione relativa a Fig. 8. L’ascissa di Fig. 10 indica il divario in dB rispetto all’SNR nominale di ciascun tipo di utente i. In questo caso molti codici effettivamente raggiungono il DER desiderato con un margine molto ampio.

Ad esempio, la curva del tipo di utente 32, indicata in Fig. 10 con il numero di riferimento 101, raggiunge il DER desiderato = 10<−6>con un margine di circa 16,3 dB. Questo à ̈ dovuto al fatto che si utilizza lo stesso codice (39,5,19) per tutti i tipi che vanno da 32 a 17, e il DER desiderato à ̈ ottenuto senza alcun margine soltanto per il tipo di utente 17, corrispondente a un SNR nominale di 0 dB.

E’ anche possibile valutare le prestazioni degli esempi sopra descritti, secondo la presente invenzione, in termini di tasso di errore di rilevamento DER rispetto a una configurazione della costruzione del caso peggiore.

La costruzione del caso peggiore prevede un esempio di codifica in cui tutti gli utenti sono in grado di decodificare tutti gli header ACMI. Viene scelta una classe di codici Reed-Muller come codice costituente, e i suoi parametri sono valutati in funzione della gamma dei rapporti segnale-rumore SNR richiesti e del numero di modi M.

Nella costruzione del caso peggiore non viene sfruttato il fatto che ogni tipo di utente i può essere associato a un codice con differenti lunghezze di parole di codice o protezione. La costruzione del codice à ̈ tale che ciascun tipo di utente i à ̈ in grado di reperire l’ACMI dall’header. Va ricordato che il tipo di utente i decide di procedere con la decodifica solo se l’ rilevato à ̈ minore o uguale al suo tipo, ossia ≤ i. In questo caso, la generazione del codice di canale à ̈ piuttosto semplice e dipende strettamente dal rapporto segnale-rumore SNR minimo ammesso nel sistema.

Considerando l’espressione asintotica del DER per un codice con distanza minima dmine il numero di vicini più vicini A e ripetendolo R volte, si ottiene:

(7) Viene considerata la classe di codici Reed-Muller quale soluzione per la costruzione del caso peggiore. I codici Reed-Muller hanno i parametri (n = 2<m>, k = m 1), con dmin= 2<m−1>e A = 2<k>− 2.

Con riferimento a Fig.12 e Fig. 13, in esse si riporta la lunghezza richiesta dell’header Rn per ottenere un DER ϵ = 10<−6>rispetto ad un SNR desiderato minimo. Le diverse curve di Fig. 12 sono riferite all’uso di codici Reed-Muller con k = 1 fino a 8. Il numero di ripetizioni necessarie può essere facilmente calcolato in base alla lunghezza del codice Reed-Muller corrispondente. La curva indicata con k = 6 à ̈ quella da considerare per un sistema con 64 modi ACM. Si può notare che, per costruire un codice di canale operante a -16 dB con 32 modi e DER ϵ = 10<−6>, con una costruzione del caso peggiore à ̈ richiesta una lunghezza dell’header di 1168 (riferimento 131), mentre la lunghezza massima dell’header degli esempi di codifica a lunghezza variabile secondo la presente invenzione sopra descritti à ̈ 464 (riferimento 51), come indicato in Fig.5, se si utilizza il limite di Hamming, e 609 (riferimento 61), come indicato in Fig.6, se si utilizzano nella presente costruzione codici lineari secondo l’arte nota.

Con riferimento a Fig.14 e Fig. 15, in esse si riporta la lunghezza richiesta dell’header Rn ottenuta impostando un DER . In quest’ultimo caso, la lunghezza massima dell’header a -16 dB con 32 modi e DER ϵ = 10<−8>à ̈ 1520 (riferimento 151), mentre la lunghezza massima dell’header negli esempi di codifica a lunghezza variabile della presente invenzione sopra descritti à ̈ 791 (riferimento 81), come indicato in Fig.8.

Appare chiaro da questo confronto che la lunghezza dell’header diminuisce quando si utilizza il metodo secondo la presente invenzione.

Con riferimento alla Fig.10, in essa sono mostrati i risultati di una simulazione eseguita utilizzando un decodificatore a massima verosimiglianza per massimizzare la probabilità . Questo si effettua calcolando la correlazione di un segnale ricevuto con tutte le parole di codice del codice e scegliendo quindi la parola di codice con la correlazione maggiore. E’ importante notare che il tipo di utente i deve calcolare la correlazione solamente tra i primi Nielementi del segnale ricevuto , e soltanto per le i parole di codice associate a SNR minori o uguali al proprio SNR nominale (SNRi).

La complessità di decodifica à ̈ quindi differente per ogni tipo di utente i ed à ̈ uguale a Ni× i somme e i confronti. La complessità media di decodifica può essere calcolata come . Nelle Figure da 5 a 9 l’ultima colonna mostra Ni× i risultati con i relativi valori medi, assumendo una distribuzione uniforme fra tutti gli utenti.

Siccome negli esempi sopra descritti i codici costituenti lineari sono scelti in modo da essere ottimali per i parametri dati e non si assume alcun’altra struttura particolare, la migliore strategia di decodifica ottimale à ̈ calcolare la correlazione del segnale ricevuto (Nisomme) con tutte le i parole di codice candidate.

La complessità di questo decodificatore esaustivo à ̈ ammissibile, in quanto tratta codici piccoli e lunghezze medie corte.

La complessità delle correlazioni à ̈ ulteriormente ridotta dall’utilizzo di codici costituenti che ammettono algoritmi di decodifica più veloci, come la trasformata di Hadarmard utilizzata per codici Reed-Muller o di lunghezza massima. In particolare, per un dato insieme di parametri (n, k, d) in cui n e k sono sufficientemente piccoli, la ripetizione di codici a lunghezza massima produce codici con prestazioni quasi ottimali. Lo scopo principale della UEP (“Unequal Error Protection†) à ̈ configurare un codice che offra una maggiore protezione contro gli errori per alcuni bit, simboli o parole di codice che ad altri. In letteratura si utilizza lo stesso nome per tutti e tre i casi.

Di seguito si descrive un esempio della presente invenzione che riguarda unicamente le parole di codice UEP e utilizza una modifica del metodo di generazione del codice di canale a lunghezza variabile sopra descritto allo scopo di generare un codice a lunghezza fissa.

Il codice a lunghezza variabile ha anche parole di codice con diverse capacità di protezione contro gli errori.

Infatti, un modo per generare un blocco di codice UEP consiste nell’estendere con zeri tutte le parole di codice del codice ottenuto per codici a lunghezza variabile in modo da ottenere una lunghezza fissa per tutte le parole di codice (equalizzare la lunghezza di tutte le parole di codice); almeno una parola di codice comprenderà quindi una sequenza di bit aventi valori uguali a zero. In questo caso tutte le parole di codice avranno una lunghezza uguale alla parola di codice più lunga nel codice di partenza.

Come si può notare, perché questa strategia possa funzionare à ̈ necessario non utilizzare parole di codice con tutti zeri nella costruzione del codice a lunghezza variabile di partenza.

E’ importante notare che nell’esempio di codifica a lunghezza variabile sopra descritto occorre considerare la lunghezza media come lunghezza effettiva del codice.

Per quanto riguarda la complessità del decodificatore correlatore a massima verosimiglianza per il codice generato mediante aggiunta di zeri, in linea di principio la complessità à ̈ la stessa della corrispondente codifica a lunghezza variabile, e quindi la precedente descrizione della complessità di codifica à ̈ valida anche per questi codici. Le caratteristiche e i vantaggi della presente invenzione appaiono chiari dalla suddetta descrizione.

Un primo vantaggio del metodo per generare codici di canale secondo la presente invenzione consiste nel fatto che la lunghezza media e massima di un frame-header di un pacchetto di dati à ̈ minimizzata.

Un secondo vantaggio del metodo della presente invenzione à ̈ dato dal fatto che risulta massimizzata l’efficienza spettrale di un sistema di comunicazione.

Un ulteriore vantaggio del metodo della presente invenzione à ̈ dato dal fatto che risulta migliorata la capacità di correzione del codice di canale generato.

Un ulteriore vantaggio del metodo della presente invenzione à ̈ dato dal fatto che si riduce la complessità computazionale di un decodificatore.

Un ulteriore vantaggio del metodo della presente invenzione à ̈ dato dal fatto che à ̈ anche possibile ottenere una lunghezza fissa per tutte le parole di codice allo scopo di avere la stessa complessità di un decodificatore a massima verosimiglianza di un codice a lunghezza variabile.

Numerose sono le varianti possibili del metodo e del sistema per generare codici di canale, in particolare per un frame-header, qui descritto a titolo di esempio, senza per questo uscire dall’ambito dei principi di novità insiti nell’idea inventiva, così come à ̈ chiaro che nella pratica attuazione dell’invenzione i dettagli illustrati potranno avere forme diverse o essere sostituiti con altri elementi tecnicamente equivalenti.

Ad esempio, il metodo e il sistema per generare codici di canale, in particolare per un frame-header, à ̈ applicabile a qualsiasi sistema di comunicazione in cui sia possibile variare l’efficienza spettrale e/o a sistemi di comunicazione non utilizzanti uno schema ACM.

E’ quindi facilmente comprensibile che la presente invenzione non à ̈ limitata a un metodo e un sistema per generare codici di canale, in particolare per un frame-header, ma à ̈ passibile di varie modificazioni, perfezionamenti o sostituzioni di parti ed elementi equivalenti senza per questo allontanarsi dall’idea inventiva, così come à ̈ meglio precisato nelle rivendicazioni seguenti.

Claims (16)

1. RIVENDICAZIONI 1. Metodo per generare un codice di canale, in particolare per un frameheader, in cui almeno una parola di codice di detto codice di canale à ̈ ottenuta mediante almeno una concatenazione di parole di codice di due codici costituenti e detta concatenazione à ̈ eseguita su sottoinsiemi di parole di codice di un primo codice costituente, avente lunghezza massima, con parole di codice di un secondo codice costituente.
2. 2. Metodo secondo la rivendicazione 1, in cui detta almeno una parola di codice di detti codici costituenti à ̈ incapsulata in una parola di codice di detto codice di canale.
3. 3. Metodo secondo la rivendicazione 1 o 2, in cui detta almeno una parola di codice di detto codice di canale ha una lunghezza maggiore di rimanenti parole di codice di detto codice di canale.
4. 4. Metodo secondo la rivendicazione 1 o 2, in cui una distanza minima di detti codici costituenti dipende da rapporti segnale-rumore associati a tipi di utenti e differenti per ciascuno di detti tipi di utenti, e dipende da un tasso di errore di rilevamento.
5. 5. Metodo secondo una o più delle rivendicazioni precedenti, in cui detta distanza minima à ̈ calcolata per ciascuno di detti tipi di utenti.
6. 6. Metodo secondo una o più delle rivendicazioni precedenti, in cui una lunghezza massima di parola codice di detto codice di canale à ̈ ottenuta con la formula , in cui M à ̈ il numero massimo di dette parole di codice di detto codice di canale corrispondenti a un massimo rapporto segnale-rumore, m à ̈ un indice intero che varia da uno a M, e à ̈ una lunghezza di detta parola di codice di detto codice costituente all’indice m.
7. 7. Metodo secondo una o più delle rivendicazioni precedenti, in cui dette parole di codice di detto codice di canale hanno lunghezza variabile.
8. 8. Metodo secondo una o più delle rivendicazioni precedenti, in cui detti codici costituenti sono codici lineari noti.
9. 9. Metodo secondo una o più delle rivendicazioni precedenti, in cui detta almeno una parola di codice di detto codice di canale comprende una sequenza di bit aventi valori uguali a zero per equalizzare la lunghezza di detta almeno una parola di codice.
10. 10. Metodo secondo la rivendicazione 9, in cui dette parole di codice di detto codice di canale hanno lunghezza fissa.
11. 11. Metodo secondo una o più delle rivendicazioni precedenti, in cui detto codice di canale à ̈ un codice UEP.
12. 12. Metodo secondo una o più delle rivendicazioni precedenti, in cui detti codici di canale sono atti ad essere utilizzati per un frame-header di un pacchetto di dati di un sistema di comunicazione.
13. 13. Sistema per generare codici di canale, comprendente almeno un codificatore atto a realizzare il metodo secondo una delle rivendicazioni da 1 a 12.
14. 14. Sistema secondo la rivendicazione 13, in cui detto codificatore à ̈ atto ad essere utilizzato in un sistema di comunicazione.
15. 15. Sistema secondo la rivendicazione 14, in cui detto sistema di comunicazione comprende una pluralità di tipi di utenti aventi rapporti segnale-rumore differenti.
16. 16. Sistema secondo la rivendicazione 14 o 15, in cui detto sistema di comunicazione à ̈ un sistema di comunicazione ACM (“Adaptive Coding and Modulation†).