Előremutató hibajavítás

A Wikipédiából, a szabad lexikonból.

Az előremutató hibajavítás, angolul forward error correction – FEC a hibajavítás egy rendszere a telekommunikációban. Abban különbözik az általánosan használt hibajavító rendszerektől, eljárásoktól, hogy arra tervezték, hogy a hibajavításhoz ne legyen szükséges – ellentétben a többi hibajavító rendszerrel – az üzenet újraküldése. A tervezéskor előre meg kell határozni azt a maximális hibátlan kódméretet, amely esetben az eljárás képes a hibajavításra, de ez egyben azt is jelenti, hogy különböző átviteli körülményekhez esetleg különféle FEC kódolási eljárásokat kell használni.

Tartalomjegyzék 1 Hogyan működik 2 Átlagos zaj csökkenti a hibát 3 A FEC típusai 4 FEC kódok egyesítése a hibák további csökkentésére 5 Turbó kódok

[szerkesztés] Hogyan működik

Az FEC a redundancián alapul, azaz látszólag felesleges biteket ad az átvitt információhoz, egy előzetesen meghatározott algoritmus szerint. Bármelyik redundáns bit értét egy bizonyos eljárás az eredeti bitek értéke alapján határozza meg. Az eredeti információ vagy felismerhető vagy nem a kódolás után; ha a kód az eredeti információt módosítatlan formában tartalmazza, akkor a kódolás szisztematikus, ellenkező esetben nem-szisztematikus.

Egy nagyon egyszerű példa: minden átviendő bitet háromszor küldünk el, és a vevő oldalon feltételezzük, hogy a kapott hármas csoportokban leggyakrabban előforduló bitek értéke adja az elküldött bit értékét, az alábbi táblázat szerint:

Vett hármas(triplet)	Minek értelmezzük:
000	0
001	0
010	0
100	0
111	1
110	1
101	1
011	1

Az eljárás biztosítja, hogy bármilyen egy bites hiba helyreállítható legyen – akkor is, ha egy bit nem értelmezhető, vagy átfordult (ellenkező értéket vett fel).

A fenti kódolási példa az életben nem használatos, alacsony hatékonyságú, csak az eljárás bemutatására szolgál.

Az általánosan használt telekommunikációs eljárások esetében, a paritás bitek vagy különféle kontroll-összegek (checksum) arra szolgálnak, hogy az átvitel során keletkezett hibát kimutassa, és nem arra, hogy azt kijavítsa. A hiba megállapítása után az általános eljárás szerint a hibás üzenetet újre el kell küldeni.

[szerkesztés] Átlagos zaj csökkenti a hibát

Az FEC működésére mondhatjuk, hogy egy "átlagos zaj" mellett dolgozik; mivel minden adatbit több átvitt szimbólumként jelentkezik, néhány szimbólum zaj okozta sérülése még lehetővé teszi, hogy az eredeti adat más szimbólumok segítségével előállítható legyen, a sértetelen szimbólum is ugyanabból az adatóból képződött. A használt eljárás hasonló a biztosító társaságok és nyugdíj alapok által követett kockázatkezelési és kockázat megosztási eljárásokhoz.

• Mivel ez a "kockázati tartalék" korlátozott, a digitális kommunikációs rendszerek a FEC eljárások csak egy meghatározott jel/zaj viszony felett működőképes, az alatt nem használható.
• Ez a "mindent vagy semmit" tendenicia miatt egyre erősebb kódok jelennek meg, amelyek egyre jobban megközelítik a Shannon korlátot.

[szerkesztés] A FEC típusai

A FEC két legfontosabb kódolási típusa a blokk kódolás és a konvolúciós kódolás.

• A blokk kódok bitek vagy szimbólumok előre meghatározott, fix hosszúságú blokkjaival (csomag) dolgoznak.
• A konvolóciós kódok bit- vagy szimbólumfolyamok (sorozatok) tetszőleges hosszúságára alkalmazhatók.
• A konvulóciós kódok használhatók blokk kódként is, ha szükséges.
• A konvolúciós kódok dekódolására gyakran a Viterbi algoritmust használják, bár más dekódolási eljárások is használatosak.

A blokk kódoknak több típusa létezik; közülük nagyon fontos a Reed-Solomon kódolás, amit széles körben használnak a kompakt diszkek, a DVD-k, és a számítógépek belső tárolói. A Golay, a BCH és a Hamming kódok a blokk kódok egy másik csoportját alkotják. Az összes blokk kód a véges terek bizonyos algebarai tulajdonságainak kihasználásán alapul.

[szerkesztés] FEC kódok egyesítése a hibák további csökkentésére

A blokk- és konvolúciós kódokat gyakran kombinálják, egyesítik a kódolási sémákat, amelyekben a konvolúciós kódokat képeznek, és ezekből blokk kódokat, (többnyire Reed-Solomon kódokat) hoznak létre, hogy a dekóderek (konvolúciós) eltüntethessenek minden hibát.

• Az eljárást gyakorlatban a műholdaknál és a mély űri kommunikációnál használják, a Voyager 2 volt az első, ami először használta ezt a technológiát 1986-ban, amikor adatokat küldött az Uránuszról.

[szerkesztés] Turbó kódok

A legutóbbi (1990-es évek eleje) fejlesztés a hibajavító kódok körében a turbó kódolás, egy olyan megoldás, amely két vagy több önmagában egyszerű konvolúciós kódolást kombinál, és közbeszúr egy blokk kódot, így nagyon közel tud kerülni a Shannon korláthoz.

• A kereskedelemben megjelenő turbó kódok közül a legelső a Qualcomm által kifejlesztett, később a Verizon Wireless-nek, a Sprint-nek, és más szolgáltatóknak eladott, a CDMA2000 1x (TIA IS-2000) digitális cellás technológiában használt kódolás volt.
• A CDMA2000 1x fejlődése, különösen az Internet elérés 1xEV-DO (TIA IS-856) szintén turbó kódolást használ. Mint az 1x, az EV-DO is Qualcomm fejlesztés, és ezt is eladta a Verizon Wireless-nek valamint a Sprint-nek és több más szolgáltatónak (az 1xEV-DO-t a Verizon Broadband Access néven, a Sprint pedig Power Vision és Mobile Broadband néven forgalmazza).