Turbo-code zorgt voor verbeterde draadloze dataoverdracht

Bij Spectrum Online is een uitgebreid verhaal verschenen over Turbo-code; de manier om meer gegevens foutloos door een zendkanaal te persen. Ruim een halve eeuw geleden toonde Shannon aan dat het in theorie mogelijk is om data foutloos door een kanaal te verzenden met een snelheid praktisch gelijk aan de maximale theoretische bandbreedte. Het bleek echter lastig om deze snelheid te halen aangezien hiervoor met de huidige codeer- en decodeertechnieken een astronomische hoeveelheid rekenkracht nodig is. Hierdoor bleef het verschil tussen de praktijk en de theorie, in decibels uitgedrukt, rond de 3,5dB. Met behulp van Turbo-code kan dit gat flink verkleind worden tot slechts 0,5dB met een bit-error rate van één op honderdduizend.

De werking van Turbo-codes is te complex om hier beknopt uit te leggen. Daarom zullen we alleen kort aanwijzen welke eigenschappen de Turbo-codes zijn kracht geven ten opzichte van klassieke coderingsmechanismen. De kracht van de Turbo-code zit in het feit dat de data tweemaal gecodeerd wordt en ook tweemaal gedecodeerd. De verschillende decoders converteren de analoge data niet alleen naar simpelweg nul en één, maar geven ook aan hoe waarschijnlijk het is dat dit correct is. Dankzij deze informatie en de gegevens van de tweede decoder kan de eerste decoder met relatief weinig rekenwerk foutgecorrigeerde gegevens ontvangen. Momenteel wordt gewerkt om Turbo-codes te gebruiken in verschillende apparaten. Onder andere de Mars Reconnaissance Orbiter and Messenger van de NASA zal gebruik maken van Turbo-code voor de communicatie. Dichter bij huis zullen de nieuwste generatie telefoons er ook gebruik van maken.

Klik op het plaatje voor een (sterk) vergrootte versie

Reacties (28)

[Madcat]

Dit moet me denken aan iets wat ik laatst had gelezen:

In de toekomst zullen er meerdere zenders worden gebruikt om dezelfde data over te sturen.
Als je dan bijvoorbeeld 4 zenders hebt dan kan je deze data 4 keer ontvangen en de ruis die je dan ontvangt is dan een stuk minder. omdat je de ontvangen signalen gewoon bij elkaar op kan tellen, maar de ruis zelf mag de log van genomen worden.

maar word het hier nu maar 1 keer verstuurd en door 2 verschillende decoders gestuurd? of 2 keer verstuurd maar de ene keer door de ene en de andere keer door de ander.

in beide gevallen werkt het niet goed als je veel omgevings ruis hebt namelijk. zeker als je het hebt over interplaneraire signalen waarbij grote rotsblokken het signaal kunnen onderbreken.

edit:
net effe die PDF bekeken, en ik hoop niet dat de data op schaal getekend is anders je hebt een overhead van 200%, is error correcting bits niet gewoon genoeg? dan heb je aan 50% overhead al genoeg. en dan kan je achteraf als je foute data hebt ontvangen nog berekenen wat de juiste waarde moest zijn (het zelfde wat in raid wordt gebruikt)
maar als ik het goed heb dan wordt het maar 1 keer verzonden.

reactie op PuzzleSolver
hehe, nee zo werkt het niet, het is iets ingewikkelder. omdat er overal ruis is zal bij draadloos communiceren een signaal/ruis verhouding zijn.maar omdat er minder ruis is dan dat er signaal is kan je iets een aantal keren via verschillende wegen versturen, en dan bij elkaar op tellen. het gaat hier dus om digitale signalen, zoals je bij voorbeeld bij WLAN ziet.

[Unicron]

Nee het wordt 2x gecodeerd en gewoon 1 keer verstuurd.
Jij hebt het meer over stochastische signaaltheorie, terwijl dit over Informatietheorie gaat

Het is helaas erg jammer dat Shannon niet liet zien hoe je de optimale codes kon maken.

[Verwijderd]

Nee hoor. Bekijk het plaatje maar eens goed. Ik zie 5 bits data, 15 bits welke verstuurd worden en aan ontvangstkant zie ik ook 15 bits. Er zijn dus wel degelijk 15 bits verstuurd, oftewel idd. een 200% overhead.

//edit nev mind, zie nu pas dat je heel iets anders bedoeld; nl. het al dan niet dubbel versturen. Excuses.

[0rbit]

Bij meerdere antennes is natuurlijk het ruisvermogen lager omdat die ruis veelal ongecorreleerd is. Daarnaast heb je, en dat vertel je niet in jouw verhaal, het voordeel dat je met meerdere antennes richtingsgevoeligheid in je ontvanger kunt inbouwen. Op die manier kun je directe paden en paden die via reflecties verlopen optellen om zo met nog minder vermogen nog betere signaal-ruisverhoudingen te bereiken. Meer antennes betekent wel meer zendvermogen, dus je kunt het niet ongestraft toepassen...

[Bl@ckbird]

In GSM gebruiken ze een trainings sequence. Dit zijn 26 vooraf bekend bitpatroon. Door dit af en toe te verzenden kan de ontvanger een wiskundig model berekenen van het radiopad. (incl reflecties) Aan de hand van dit model worden, op binnenkomende signalen, correctie pulsen toegevoegd. Deze gaan de reflecties, en andere storingen, tegen.

offtopic:
Ander detail:
Wist je dat bij GSM expres ruis gegenereerd wordt?
De spraak en de achtergrond geluiden worden appart gesampled. "Achtergrond-ruis-bits" worden veel minder vaak gestuurd dan "spraak-bits."
Het bleek, dat wanneer mensen niks zeggen (en ze horen geen ruis) ze dit irritant vinden.
Dus wordt er van de weinige "ruis-bits" die verstuurd worden een ruispatroon gegenereerd.

Uit: GSM in detail
ISBN: 90-5576-115-x

[PuzzleSolver]

In de toekomst zullen er meerdere zenders worden gebruikt om dezelfde data over te sturen.
Als je dan bijvoorbeeld 4 zenders hebt dan kan je deze data 4 keer ontvangen en de ruis die je dan ontvangt is dan een stuk minder. omdat je de ontvangen signalen gewoon bij elkaar op kan tellen, maar de ruis zelf mag de log van genomen worden.

En dan zend je 2 signalen uit (stereo) en dan zet je bij slechte ontvangst je radio op mono zodat het hierboven beschrevene gebeurt. Dat principe is dus niet in de toekomst maar is al heeeeeel erg oud.

[eit]
Reactie op eenmadcat's reactie op puzzlesolver:

Je hebt inderdaad gelijk dat het iets ingewikkelder is, maar uit je posting bleek dit niet vandaar mijn reactie. Vanaf drie of meer signalen geld er dat het verschil tussen de signalen opzich een factor meespeelt en beter bepaald kan worden dan het verschil tussen 2 signalen. Als 2 mensen zeggen "waar" en één zegt "niet waar" en waar is 1 en niet waar is 0 kun je bepalen dat de uitkomst 1 zou moeten zijn ipv 0.66 op basis van het meest voorkomende antwoord. Maar mischien moet ik me nog wat verder verdiepen in deze materie.
[/edit]

[Molybdenum]

interplaneraire signalen waarbij grote rotsblokken het signaal kunnen onderbreken.

maak je daar maar geen zorgen over. het totale oppervlak aan rostblokken wat je tegenkomt op een interplanetaire afstand is nihil vergelijken met het oppervlak aan lege ruimte.

zelfs een rechte lijn heeft een hele grote kans van slagen om ongestoord door de planetoidengordel te komen. de dichteid van dat soort astronomische systemen lijkt groot, maar stelt werkelijk niks voor.

het zonnestelsel is ongelofelijk ijl, ongeacht de grote objecten die er in voorkomen.

[Verwijderd]

Turbo-code; de manier om meer gegevens foutloos door een zendkanaal te persen. Ruim een halve eeuw geleden toonde Shannon aan dat het in theorie mogelijk is om data foutloos door een kanaal te verzenden met een snelheid praktisch gelijk aan de maximale theoretische bandbreedte

Weten jullie wel zeker dat het hier om gaat? Of jullie verhaal klopt niet, of het gebruikte plaatje klopt niet.

De techniek op het plaatje maakt het namelijk niet sneller, alleen betrouwbaarder. Waar het om gaat is dat men twee verschillende 'checksums' gebruikt om de originele waarde terug te vinden. Men verstuurt niet meer informatie, alleen meer checksums om de informatie correct te laten zijn.

Dit is het best te zien op de (3) bij het plaatje, daar staat wat verstuurd zou gaan worden. Naast de oorspronkelijke oorspronkelijke 5 bits, worden er ook nog eens 10 checksumbits meegestuurd (2x5), oftewel 3x zoveel bits als de eigenlijke informatie.

Het is dus nooit zo dat met deze techniek informatie verstuurd kan worden op een snelheid dicht bij het theoretische maximum van het gebruikte medium, hooguit op 1/3 van het theoretische maximum.

Ik geloof best dat de totale snelheid (inclusief checksums) dicht bij dit maximum komt, maar de snelheid van de daadwerkelijke dataoverdracht (dus) niet.

Wel kan ik me voorstellen dat hiermee een snellere communicatie mogelijk is. Het probleem met de communicatie waar het hier over gaat, is de hoeveelheid 'noise'. Dit wordt erger naarmate de snelheden hoger worden. Doordat de hier gebruikte techniek meer checksums gebruikt kan ik me voorstellen dat het toch mogelijk is met hogere snelheden te werken dan dat nu mogelijk is, echter de stelling dat de dataoverdracht de max. bandbreedte zou benaderen is gewoon niet waar.

//edit de term checksum oneigenlijk gebruikt, weet ik

[justice strike]

in de informatica worden we altijd geleerd dat de rekenkracht vele male kleiner is dan de bandbreedte. Dit klopt overigens wel, kijk maar naar de toename van netwerkbandbreedte en processor kracht.

Het is dus efficienter om de gegevens opnieuw op te vragen ipv de data te corrigeren. Dit wordt dan ook vrijwel altijd gedaan. Foutdetectie is dan wel een must, foutcorrigeren is eigenlijk overbodig aangezien je het beter opnieuw kan opvragen(in dit opzicht)

[Verwijderd]

in de informatica worden we altijd geleerd dat de rekenkracht vele male kleiner is dan de bandbreedte.

Beetje eenzijdig standpunt, zeker tegenwoordig. De verbinding met mars is een mooi voorbeeld, die bandbreedte is uiteraard belabberd (om nog maar te zwijgen over de latency, valt echt niet te gamen op Mars). In zo'n geval is een goede compressie/foutcorrectie onontbeerlijk (alleen al vanwege de latency).

Het is dus efficienter om de gegevens opnieuw op te vragen ipv de data te corrigeren. Dit wordt dan ook vrijwel altijd gedaan. Foutdetectie is dan wel een must, foutcorrigeren is eigenlijk overbodig aangezien je het beter opnieuw kan opvragen(in dit opzicht)

opnieuw opvragen is ook foutcorrectie. Er is een fout, en die wordt gecorrigeerd. (door het geheel opnieuw te zenden). Zolang dit sporadisch voorkomt is dit waarsch. efficient, maar naarmate de verbinding slechter wordt (en alle draadloze verbindingen mogen zich aangesproken voelen, dus ook die van bv. de mobiele telefonie en wifi), of er sprake is van meer overspraak (druk verkeer), kan dit erg inefficient worden.

//edit
zie het nu pas staan:

Dichter bij huis zullen de nieuwste generatie telefoons er ook gebruik van maken.

[justice strike]

Beetje eenzijdig standpunt, zeker tegenwoordig. De verbinding met mars is een mooi voorbeeld, die bandbreedte is uiteraard belabberd (om nog maar te zwijgen over de latency, valt echt niet te gamen op Mars). In zo'n geval is een goede compressie/foutcorrectie onontbeerlijk (alleen al vanwege de latency).

natuurlijk heb ik het over alledaags gebruik van netwerken en niet een uitzonderlijk geval als data overdracht naar mars.

opnieuw opvragen is ook foutcorrectie. Er is een fout, en die wordt gecorrigeerd. (door het geheel opnieuw te zenden). Zolang dit sporadisch voorkomt is dit waarsch. efficient, maar naarmate de verbinding slechter wordt (en alle draadloze verbindingen mogen zich aangesproken voelen, dus ook die van bv. de mobiele telefonie en wifi), of er sprake is van meer overspraak (druk verkeer), kan dit erg inefficient worden

wat jij noemt is geen fout correctie. je corrigeerd de fout namelijk niet. je gooit het hele pakketje weg en vraagt het opnieuw op. Als je het in de literatuur over error correction hebt is dat altijd het berekenen en corrigeren ervan.

overigens zijn draadloze verbindingen sinds de komst van cdma veel minder gevoelig voor overspraak en ruis. dus wat dat betreft verschilt het weinig van het voorbeeld wat ik genoemd heb.

[Verwijderd]

wat jij noemt is geen fout correctie. je corrigeerd de fout namelijk niet. je gooit het hele pakketje weg en vraagt het opnieuw op.

Het is maar op welk niveau je het bekijkt,

1) je constateert dat het pakketje fout is. Het geheel van de transmissie klopt niet meer.

2) je vraagt het pakketje opnieuw op

3) je ontvangt het pakketje nogmaals, nu goed. Het geheel van de transmissie klopt weer.

er was dus een fout, en die is nu opgelost. Dit is gedaan door het opnieuw opvragen van het pakketje. Daarmee classificeert die actie zich als foutcorrectie imo.

Dat de term in de literatuur oneigenlijk gebruikt wordt (vergelijk het met het feit dat de term ADSL als merknaam wordt gezien) doet daar niets aan af.

[Verwijderd]

Dit is het verschil tussen een ruime en enge definitie van het begrip foutcorrectie.

Hoewel beide gebruiken correct zijn levert dit soort problemen altijd leuke welles nietes spelletjes op.

Uiteindelijk gaat het erom dat men weet wat iemand anders met het begrip bedoelt.

[Verwijderd]

In de informatica worden we altijd geleerd dat de rekenkracht vele male kleiner is dan de bandbreedte.

Da's dan dom... want elke kleuter kan zien dat rekenkracht met Moore's law exponentieel omhoog gaat, en bandbreedte zowat constant blijft (of eventueel matig lineair stijgt)

[ajvdvegt]

Een kleuter kan zien dat de bandbreedte 'matig lineair stijgt'?

1Mb/s --> 10Mb/s --> 100Mb/s --> 1000Mb/s

Hoewel het lang niet zo hard stijgt als de processor snelheden is dit toch echt exponentieel hoor!

[Wekkel]

Is dit iets dat softwarematig gaat of moeten we wachten op een nieuw rondje hardware voordat we hier profijt van kunnen trekken? Altijd goed om te zien dat er nog mooie ontwikkelingen zijn die eigenlijk vrij simpel dingen beter maken.

[Bl@ckbird]

Astu:
http://www.eccpage.com
Onderaan bij: TURBO decoder archive: BCJR_turbo.tar

Mag u zelf klussen
Lees ook de bijbehorende PostScript file met wiskundige onderbouwing.

Is dit iets dat softwarematig gaat
of moeten we wachten op een nieuw rondje hardware [...]

Wat is software en wat is hardware?
Bij embedded systemen vervaagt die grens een beetje erg.

Dit zijn bewerkingen die in dedicated hardware (Lees: DSP's)
veel sneller/efficienter draaien dan op een PC. Voor DSP wordt code geschreven... Maar het wordt gezien als een hardwarematige oplossing.

[Verwijderd]

Een DSP is een pure software oplossing hoor! Een hardware-oplossing is een ASIC. Met echte transistoren en echte NAND-poortjes die maar 1 funktie hebben. Geschreven in VHDL dus, en niet in C.

[Bl@ckbird]

Met dedicated hardware bedoel ik dat er DSP geprogrameerd wordt voor dat doel. Ik denk dat Wekkel het meer in richting van de PC processors zoekt.

In DSP en microcontrollers draait gewoon software, maar voor een leek kan het allemaal overkomen als standaard hardwarematige IC's.

[HDoc]

De kans op een foute bit van 1 op 100.000 toch wel hoog. Volgens mij heeft Hezik hierboven gelijk. Het is een manier om signalen met een hoge snelheid met veel ruis toch redelijk goed over te brengen. Voor een foutloze overdracht van gegevens moet er nog wel een post-processing errorcontrole op een niveau hoger aanwezig zijn.

Al met al denk ik toch wel een techniek die de moeite waard kan zijn. Ook bij vaste lijnverbindingen is er altijd een bepaalde mate van ruis aanwezig. Middels deze techniek kan de basis-snelheid van gegevens-overdracht wellicht veel hoger zijn, doordat de maximale bandbreedte veel breder wordt.

[MAX3400]

Ik kijk even op mijn eigen PC... Afgelopen dagen ongeveer 50 miljoen packets ontvangen/verzonden... Nou heb ik even niet mijn boekjes bij de hand, maar dat komt neer op een goede 50 miljard bits, dacht ik. Dat zou dan betekenen dat ik ongeveer 500.000 bits = 125Kbytes aan rotte date heb??

Goh, wat zal trans-atlantisch internet daar ineens betrouwbaarder door worden??

[Hielko]

Hoezo? Foutieve bits kan je toch gewoon opnieuw verzenden? Hoe denk je dat, dat tegenwoordig gebeurd? Echt niet alle packets komen foutloos aan hoor.

[Unicron]

Dat is ook waarom veel mensen Shannon in het begin niet geloofden toen hij zei dat zolang je maar onder de max. capaciteit van het kanaal blijft dat je dan de foutenkans oneindig klein kan krijgen.

[ledog]

Hij heeft vast gezegd dat je de kans op fouten willekeurig klein kunt krijgen. Je kan de kans op fouten dus oneindig maal verkleinen.

[Verwijderd]

De kans van 1 op 100.000 is hier alleen als voorbeeld neergezet, die mag je als ontwerper van de ontvanger en verzender zelf kiezen. Het bijzondere van deze 'Turbo codes' is dat je met hele lange codewoorden kunt werken, zonder gigantische processorcappaciteit nodig te hebben, en dat daardoor de capaciteit van het kanaal veel beter gebruikt kan worden.
Dat de cappaciteit beter benut kan worden komt doordat in ieder codewoord ongeveer evenveel fouten voorkomen. Hierdoor is het gemiddelde aantal foute bits in een codewoord dus het bijna het maximale aantal bits dat gecorrigeerd kan worden, wat bepaald wordt door het coderings algoritme. (Als er meer foute bits in het codewoord zitten als gecorrigeerd kan worden blijven de fouten zitten, mogelijk wel gedetecteerd)

[boner]

Dit lijkt mij geen nieuw bedenksel. Een tijdje geleden is een ex-collega vijn mij gepromoveerd op deze problematiek. Hij ontwikkelde een wiskundige metode om een combinatie te maken tussen error-correctie en compressie. Hij maake het zo dat je ondanks compressie toch enorm goede compressie kon behalen.

Naam van het proefschrift is: Packing Density of Codes. Autheur: Eric van Os.

[TiG]

ondanks compressie toch enorm goede compressie

Wat bedoel je met die zin?

[hamsteg]

Hoezo is dit geen winst? Bovengenoemde techniek maakt het mogelijk om, ondanks de hoge overhead, data in een keer over te sturen. Bij "normale" transmissies is er ook overhead alleen noemen we dat opnieuw zenden.

Ik vraag me af wat efficienter is als je bijvoorbeeld kijkt naar een glasvezel tussen Europa en Amerika. Bij Turbo-code wordt de bandbreedte groter en het aantal re-transmissies neemt exponetieel af ... alleen de effieciente data stroom wordt minder door de overhead maar ook de belasting van coders en decoders (zeker bij re-transmissies). Het kon bij dit soort enorme data stromen nog wel eens heel wat schelen.

Zeker als er gebruik gemaakt moet worden van een licht beschadigde kabel kon dit nog wel eens een zeer goede oplossing zijn. Een glasvezel die ergens op de oceaan bodem ligt ga je niet zomaar even vervangen.