Turbo codici: differenze tra le versioni

Versione delle 12:49, 1 feb 2018

Versione attuale delle 00:36, 4 lug 2025

(20 versioni intermedie di 13 utenti non mostrate)

Riga 1:

{{S|telecomunicazioni}}

I '''turbo codici''' sono una classe di [[codifica di canale|codici di correzione degli errori]] ad alte prestazioni, che trovano impiego nelle [[Rete satellitare|comunicazioni satellitari]] nello spazio profondo ed in altre applicazioni in cui i progettisti puntano ad avere il massimo trasferimento di informazione su una [[Banda (informatica)|banda]] limitata in presenza di un [[Segnale elettrico|segnale]] ricevuto affetto da [[Rumore (elettronica)|rumore]].

I codici turbo sono stati teorizzati da [[Claude Berrou]], [[Alain Glavieux]] e [[Punya Thitimajshima]] presentati nel [[1993]] ad una conferenza dell'[[IEEE]]<ref>Berrou C., A. Glavieux e P. Thitmajshima; "''Near Shannon Limit Error-Correcting Coding and Decoding: Turbo Codes''", Proceeding of the IEEE International Conference on Communications, 1993, [[Ginevra]], [[Svizzera]]. [http://www-elec.enst-bretagne.fr/equipe/berrou/Near%20Shannon%20Limit%20Error.pdf]</ref>.

{{citazioneSenza necessariafonte|I ricercatori di più atenei verificarono i risultati di Berrou, accorgendosi solo in un secondo momento che i risultati mostrati dal francese non andavano al di sotto di probabilità di errore di 10^-5, scoprendo poi che le curve di errore non decrescevano rapidamente dopo questo valore}}.

{{citazioneSenza necessariafonte|Bisogna ricordare che l'algoritmo di Berrou non è completamente originale. Infatti [[Robert Gallager]], geniale studente e ora insegnante del [[Massachusetts Institute of Technology]], propose già con la sua tesi di dottorato un algoritmo di decodifica, chiamato ''[[belief propagation]]'', per lungo tempo passato inosservato e successivamente ripreso da Berrou. Inoltre la stessa idea dei codici turbo è riconducubilericonducibile ad alcuni lavori di Robert Gallager, sebbene Berrou abbia il merito di avere scelto la soluzione parallela anziché quella seriale, poiché per sua stessa ammissione la prima forma risultava di più semplice implementazione}}.

I codici turbo sono ancora ad oggi oggetto di ricerche in numerose università del mondo, allo scopo di raffinarli e di ottenere implementazioni più efficienti.

Nella [[teoria dell'informazione]], i turbo codici (originariamente ''Turbocodes'', in francese) sono una classe di codici [[Forward Error Correction]] (FEC) ad alte prestazioni sviluppati intorno al 1990-91 (ma pubblicati per la prima volta nel 1993), le prime codifiche capaci di avvicinarsi al massimo teorico della capacità del canale [[teorema di Shannon]]–Hartley, il massimo teorico per la velocità alla quale è ancora possibile una comunicazione affidabile dato un livello di rumore specifico. I turbo codici sono utilizzati nelle comunicazioni mobili [[3G]]/[[4G]] (ad es. In [[UMTS]] e [[LTE (telefonia)|LTE]]) e nelle comunicazioni satellitari (nello spazio profondo) così come altre applicazioni dove i progettisti cercano di ottenere un trasferimento affidabile delle informazioni tramite collegamenti di comunicazione, dati i limiti di larghezza di banda o di latenza e la presenza di rumore dannoso per i dati. I turbo codici sono attualmente in competizione con i codici ''[[Lightweight Directory Access ProtocolLDPC]] (''Low-Density-Parity-Check-Code'' (LDPC) che offrono prestazioni comparabili.

Il nome "turbo code" deriva dal ciclo di feedback in decodifica, perciò è stato associato alla retro-alimentazione dai gas di scarico utilizzata per la sovralimentazione dei motori turbo, Hagenauer ha sostenuto che il termine turbo in tal senso è improprio poiché non vi è alcun feedback nelverso il processo di codifica nell'encoder,<ref>{{Cita web |url=http://www.ima.umn.edu/csg/bib/bib16.0429hage.pdf |titolo=Archived copy |accesso=20 marzo 2014 |urlmorto=sì |urlarchivio=https://web.archive.org/web/20130611235418/http://www.ima.umn.edu/csg/bib/bib16.0429hage.pdf |dataarchivio=11 giugno 2013 |df=dmy }}</ref>. In ogni caso, il termine turbo, nell'uso popolare, rende bene l'idea di un sistema ingegnoso, veloce e potente.

==Storia==

Riga 25 ⟶ 23:

Oltre all'invenzione dei turbo codici, Claude Berrou ha anche sviluppato i [[codici ricorsivi sistematici convoluzionali]] (RSC), utilizzati nell'esempio di implementazione dei turbo codici descritti nel brevetto (i turbo codici che usano i codici RSC sembrano funzionare meglio di quelli che non li usano).

Prima dei codici turbo, le migliori implementazioni FEC erano costituite da codifiche seriali concatenaticoncatenate basate su un codice di correzione degli errori esterno [[Reed-Solomon]] combinato con un codice interno convoluzionale a lunghezza corta [[algoritmo di Viterbi]], noto anche come codice [[RSV]].

In un saggio successivo, Berrou ha generosamente riconosciuto l'intuizione di "G. Battail, J. Hagenauer e P. Hoeher, che, alla fine degli anni '80, hanno acceso l'interesse per l'elaborazione probabilistica". Aggiungendo che " R. Gallager e M. Tanner avevano già immaginato tecniche di codifica e decodifica i cui principi generali erano strettamente correlati," anche se i calcoli necessari erano impraticabili a quel tempo.<ref>{{Cita pubblicazione|nome=Claude|cognome=Berrou|titolo=The ten-year-old turbo codes are entering into service|città=Bretagne, France|accesso=11 febbraio 2010|url=http://www-elec.enst-bretagne.fr/equipe/berrou/com_mag_berrou.pdf}}</ref>

==Un esempio di encoder==

Esistono molti casi diversi di turbo codici, che utilizzano diversi componenti di codificatori, rapporti di [[input/output]], interleaver e pattern di foratura. Questo esempio di implementazione dell'encoder descrive un classico codificatore turbo e mostra la progettazione generale dei turbo codici paralleli.

Questa implementazione dell'encoder invia tre sotto-blocchi di bit. Il primo sottoblocco è il blocco ''m''-bit dei dati del payload o carico utile che è spedito senza modifiche (codifica ''sistematica''). Il secondo sottoblocco è costituito da ''n/2'' [[bit di parità]] calcolati dai dati del payload utilizzando un codice convoluzionale sistematico ricorsivo (codice RSC). Il terzo sottoblocco è costituito da ''n/2'' bit di parità calcolati su una permutazione nota dei bit del payload, ancora utilizzando un codice RSC. Pertanto due sottogruppi ridondanti ma diversi di bit di controllo di parità sono inviati insieme al carico utile. Il blocco completo è composto da ''m + n'' bit di dati, con rapporto D/C (Dati/Controllo) ''m / ( m + n )''.

La permutazione dei bit del payload tra le i due RSC in parallelo viene eseguito da un dispositivo chiamato interleaver. L'interleaver installato tra i due codificatori (e i decodificatori) è utilizzato per diffondere e sfumare i picchi di errore prodotti sull'output dal rumore che affligge il [[mezzo trasmissivo]].

Dal punto di vista dell'hardware, il codificatore complessivo consiste di due codificatori RSC in parallelo, ''C''₁ e ''C''₂, come illustrato in figura, che sono collegati tra loro usando uno schema di concatenazione parallela:

Riga 47 ⟶ 45:

==Il decoder==

Il decodificatore è costruito in modo simile all'encoder. Due decodificatori elementari sono interconnessi tra loro ma in modo seriale non in parallelo. Il decodificatore <math>\scriptstyle DEC_1</math> funziona a bassa velocità (es. <math>\scriptstyle R_1</math>) quindi è riferito al codificatore <math>\scriptstyle C_1</math> e corrispondentemente <math>\scriptstyle DEC_2</math> sta per il <math>\scriptstyle C_2</math>. <math>\scriptstyle DEC_1</math> produce una decisione di tipo ''soft decision'' che causa un ritardo <math>\scriptstyle L_1</math>. Lo stesso ritardo prodotto dalla linea di ritardo nell'encoder. L'operazione <math>\scriptstyle DEC_2</math> causa un ritardo <math>\scriptstyle L_2</math>.

[[File:turbo decoder.svg]]

Riga 68 ⟶ 66:

:<math>\Lambda(d_k) = \log\frac{p(d_k = 1)}{p(d_k = 0)}</math>

e la consegna a <math>\scriptstyle DEC_2</math>. <math>\scriptstyle \Lambda(d_k)</math> è il codiddettocosiddetto ''logaritmo del rapporto di verosimiglianza'' (LLR). <math>\scriptstyle p(d_k \;=\; i),\, i \,\in\, \{0,\, 1\}</math> è la ''è la probabilità a posteriori'' (APP) del <math>\scriptstyle d_k</math> bit di dati, cioè la probabilità nell'interpretare un bit ricevuto <math>\scriptstyle d_k</math> come <math>\scriptstyle i</math>. Prendendo in considerazione l'''LLR'', <math>\scriptstyle DEC_2</math> produce una decisione ''hard''; cioè un bit decodificato.

L'[[Algoritmo di Viterbi ]] non è in grado di calcolare l'APP, quindi non può essere utilizzato in <math>\scriptstyle DEC_1</math>. Qui può essere usato utilizzato un algoritmo BCJR modificato [[BCJR algorithm]]. Per <math>\scriptstyle DEC_2</math> invece l' algoritmo di Viterbi è appropriato.

Tuttavia, la struttura rappresentata non è ottimale, perché <math>\scriptstyle DEC_1</math> utilizza solo una parte delle informazioni ridondanti disponibili. Per migliorare la struttura, viene utilizzato un ciclo di feedback (linea tratteggiata in figura).

Riga 88 ⟶ 86:

Ad esempio, per ciascun bit, il front end di un ricevitore tradizionale deve decidere se una tensione analogica interna è al di sopra o al di sotto di un determinato livello di tensione di soglia. Per un decodificatore di turbo-codice, il front-end fornirebbe una misura di quanto è distante la tensione interna dalla soglia data.

Per decodificare il blocco di dati {{nowrapTutto attaccato|''m'' + ''n''}}, il front-end del decoder crea un blocco di probabilità, con una misura di verosimiglianza per ogni bit nel flusso di dati. Ci sono due decodificatori paralleli, uno per ciascuno dei {{frac|''n''|2}} sottoblocchi di bit di parità. Ciascun decodificatore usa un sottoblocco di probabilità per i dati del payload ''m'' (il decodificatore che lavora sul secondo sotto-blocco di parità conosce la permutazione di bit che ha usato il secondo codificatore).

==Risoluzione delle ipotesi per trovare i bit==

Riga 102 ⟶ 100:

* I turbo codici sono ampiamente utilizzati in standard di telefonia mobile [[3G]] and [[4G]]; es., in [[High Speed Packet Access|HSPA]], [[EV-DO]] e [[3GPP Long Term Evolution|LTE]].

* [[MediaFLO]], sistema televisivo mobile terrestre da [[Qualcomm]].

* Nel canale di interazione dei sistemi di comunicazione satellitare, come [[DVB-RCS]]<ref>[http://www.etsi.org/deliver/etsi_en/301700_301799/301790/01.05.01_60/en_301790v010501p.pdf Digital Video Broadcasting (DVB); Interaction channel for Satellite Distribution Systems], ETSI EN 301 790, V1.5.1, May 2009.</ref> and [httphttps://web.archive.org/web/20170624210148/https://www.dvb.org/standards/dvb-rcs2 DVB-RCS2].

* Nelle missioni [[NASA]] come [[Mars Reconnaissance Orbiter]] che ora usano turbo codici, in alternativa ai codici RS- Viterbi [[Viterbi decoder|Viterbi]].

* La turbo codifica, come la turbo codifica a blocchi e la turbo codifica convoluzionale, è utilizzata in [[IEEE 802.16]] ([[WiMAX]]), uno standard di rete metropolitana senza fili.

==Formulazione bayesiana==

Dal punto di vista dell'intelligenza artificiale , i turbo codici possono essere considerati come un'istanza di propagazione delle credenze fiduciarie ad anello nelle reti bayesiane [[Rete bayesiana]].<ref>{{Cita pubblicazione|autore1autore=McEliece, Robert J. McEliece |wkautore1wkautore=Robert McEliece

|autore2=MacKay, David J. C. |wkautore2=David J. C. MacKay

|autore3=Cheng, Jung-Fu Cheng

|titolo=Turbo decoding as an instance of Pearl's "belief propagation" algorithm

|rivista=IEEE Journal on Selected Areas in Communications

|volume=16

|numero=2

|pp=140–152140-152

|anno=1998

| issn=0733-8716

Riga 120 ⟶ 118:

| postscript=.

}}</ref>

== Note ==

<references />

==Voci correlate==

* [[Codice convoluzionale]]

* [[algoritmoAlgoritmo di Viterbi]]

* [[Soft-decision decoder]]

* [[Interleaving]]

* [[BCJR algorithm]]

* [[Low-density parity-check code]]

* [[Serial concatenated convolutional codes]]

* [[Turbo equalizer]]

* [[Forward error correction]]

==References==

{{reflist}}

==Collegamenti esterni==

* [httphttps://web.archive.org/web/20180113202924/https://www.spectrum.ieee.org/computing/software/closing-in-on-the-perfect-code "Closing In On The Perfect Code"], IEEE Spectrum, March 2004

* [http://www.csee.wvu.edu/~mvalenti/documents/valenti01.pdf "The UMTS Turbo Code and an Efficient Decoder Implementation Suitable for Software-Defined Radios"] {{Webarchive|url=https://web.archive.org/web/20161020193559/http://www.csee.wvu.edu/~mvalenti/documents/valenti01.pdf |date=20 ottobre 2016 }} (''International Journal of Wireless Information Networks'')

* {{Cita pubblicazione|autore=Dana Mackenzie |titolo=Take it to the limit |url=https://archive.org/details/sim_new-scientist_2005-07-09_187_2507/page/n39 |rivista=New Scientist |volume=187 |numero=2507 |anno=2005 |pp=38–4138-41 | postscript=. | issn=0262-4079 }} ([https://www.newscientist.com/article.ns?id=mg18725071.400 preview], [https://web.archive.org/web/20060902150939/http://geilenkotten.homeunix.org/TC_NS_09072005.pdf copy])

* [httphttps://www.sciencenews.org/articles/20051105/bob8.asp "Pushing the Limit"] {{Webarchive|url=https://web.archive.org/web/20080423213747/http://www.sciencenews.org/articles/20051105/bob8.asp |date=23 aprile 2008 }}, a ''[[Science News]]'' feature about the development and genesis of turbo codes

* [http://www-turbo.enst-bretagne.fr/ International Symposium On Turbo Codes]

* [http://www.iterativesolutions.com/Matlab.htm Coded Modulation Library], an open source library for simulating turbo codes in matlab

* [http://www.ifp.uiuc.edu/~singer/journalpapers/tuchler_2002a.pdf "Turbo Equalization: Principles and New Results"] {{Webarchive|url=https://web.archive.org/web/20090227062216/http://www.ifp.uiuc.edu/~singer/journalpapers/tuchler_2002a.pdf |date=27 febbraio 2009 }}, an ''[[IEEE Transactions on Communications]]'' article about using convolutional codes jointly with channel equalization.

* [http://itpp.sourceforge.net IT++ Home Page] The [[IT++]] is a powerful C++ library which in particular supports turbo codes

* [http://www.inference.phy.cam.ac.uk/mackay/CodesTurbo.html Turbo codes publications by David MacKay]

* [https://aff3ct.github.io AFF3CT Home Page] ([[AFF3CT|A Fast Forward Error Correction Tool]]) for high speed turbo codes simulations in software

{{CCSDS|state=collapsed}}

{{Use dmy dates|date=September 2010}}

{{DEFAULTSORT:Turbo Code}}

{{Controllo di autorità}}

== Note ==

<references/>

{{Portale|ingegneria}}