Előremutató hibajavítás

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.

Működése

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. Egy bizonyos eljárás bármelyik redundáns bit értékét 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 egybites 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ásbit vagy kontroll-összeg (checksum) arra szolgál, 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 újra el kell küldeni.

Az á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 által okozott 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értetlen szimbólum is ugyanabból az adatból képződött. A használt eljárás hasonló a biztosítótársaságok és nyugdíjalapok által követett kockázatkezelési és kockázatmegosztási eljárásokhoz.

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

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 konvolú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 algebrai tulajdonságainak kihasználásán alapul.

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 konvolúciós kódokat képeznek, és ezekből blokk kódokat (többnyire Reed-Solomon kódokat) hoznak létre, hogy a (konvolúciós) dekóderek 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.

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 internetelé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).