Samoopravné kódy () se ve výpočetní technice, telekomunikacích, teorii informace a v teorii kódování používají pro detekci a opravu chyb v datech přenesených nespolehlivými nebo zarušenými komunikačními kanály. Ústřední myšlenkou je, že ke zprávě se přidají nadbytečné informace ve formě samoopravného kódu. Tato redundance umožňuje příjemci detekovat omezený počet chyb kdekoli ve zprávě, a obvykle tyto chyby i opravit bez opakování přenosu. Průkopníkem v tomto oboru byl ve 40. letech 20. století americký matematik Richard Hamming, který v roce 1950 sestrojil první samoopravný kód Hammingův kód (7,4).
Samoopravné kódy se od kódů samodetekčních liší tím, že chyby, ke kterým dochází při přenosu, umějí nejen detekovat, ale i opravit. Díky tomu není nutný zpětný kanál, kterým se v případě chyby zasílají požadavky na opakování přenosu. Nevýhodou je nutnost přidávat ke zprávě další informace, takže je nutné přenášet větší objem dat. Samoopravné kódy se proto používají v situacích, kdy by opakované vysílání bylo drahé nebo nemožné, jako jsou jednosměrné komunikační spoje a při přenosu na více přijímačů při multicastu. Jsou také vhodné u spojení s velkou latencí; v případě sondy obíhající planetu Uran může opakování přenosu kvůli chybě způsobit zpoždění pěti hodin. Samoopravné kódy se obvykle používají v modemech, ale i ve velkokapacitních úložištích a v systémech s ECC pamětí.
Zpracování samoopravného kódu v přijímači může být aplikováno až na digitální bitový proud nebo již při demodulaci digitálně modulované nosné. Ve druhém případě jsou samoopravné kódy nedílnou součástí vstupního A/D převodníku v přijímači. Pro demodulaci digitálních dat z analogového signálu poškozeného šumem se obvykle používá Viterbiho dekodér, který implementuje algoritmus s měkkým rozhodováním. Mnoho kodérů/dekodérů samoopravných kódů také generuje BER signál, který je možné použít pro doladění analogové přijímací elektroniky.
Maximální podíl chyb nebo chybějících bitů, které lze opravit, je určen návrhem samoopravného kódu, v různých podmínkách jsou tedy vhodné různé samoopravné kódy. Silnější kódy mají obecně větší redundanci, kterou je potřeba přenést dostupnou přenosovou kapacitou, což snižuje efektivní přenosovou rychlost při zlepšování efektivního poměru signál/šum přijímaného signálu. Pro výpočet maximální dosažitelné komunikační rychlosti pro danou maximální přijatelnou pravděpodobnost chyby lze použít Shannonovu větu o kanálu, která určuje meze teoretické maximální rychlosti přenosu kanálem s určitou úrovní základního šumu. Důkaz však není konstruktivní, tedy neposkytuje návod, jak vytvořit kód blížící se kapacitě kanálu. Po letech výzkumu se některé pokročilé systémy samoopravných kódů od roku 2016 přibližují teoretickému maximu.
Dopředná oprava chyb náhled|Oprava chyb Reed-Solomon Dopředná oprava chyb (FEC, ) nebo kanálové kódování je v telekomunikacích, teorii informace, a teorii kódování technika používaná pro detekci a opravu chyb při přenosu dat přes nespolehlivé nebo zarušené komunikační kanály. Ústřední myšlenkou je, že odesilatel kóduje zprávu nadbytečným způsobem, nejčastěji pomocí samoopravných kódů.
Redundance umožňuje příjemci detekovat omezený počet chyb, které se mohou objevit kdekoli ve zprávě, a často tyto chyby i opravit bez opakování přenosu. FEC dává příjemci schopnost opravit chyby bez potřeby zpětného kanálu, pomocí kterého by si vyžádal opakování přenosu dat, ale za cenu potřeby větší šířky pásma dopředného kanálu. FEC se proto používá v situacích, kdy opakované přenosy jsou drahé nebo nemožné, například na jednosměrných komunikačních spojích, při přenosu na více přijímačů při multicastu nebo když by opakování přenos způsobilo významnou latenci. Například při příjmu ze sondy obíhající kolem planety Uran by opakování přenosu kvůli chybám způsobilo zpoždění nejméně 5 hodin. FEC informace se používá také v modemech, kde opakování přenosu je možné, ale často neefektivní. Dalším použitím jsou paměti a velkokapacitní úložiště (s magnetickým, optickým nebo polovodičovým médiem) pro zotavení z poškozených dat.
Zpracování samoopravného kódu v přijímači může být aplikováno na digitální proud bitů nebo na demodulaci digitálně modulované nosné. Ve druhém případě je FEC nedílnou součástí počáteční A/D převodníku v přijímači. Viterbiho dekodér implementuje algoritmus s měkkým rozhodováním pro demodulaci digitálních dat z analogového signálu poškozeného šumem. Mnoho FEC kodérů také generuje BER signál, který může být používán jako zpětná vazba pro doladění analogové přijímací elektroniky.
Maximální podíl chyb nebo chybějících bitů, které lze opravit, je dán návrhem samoopravného kódu, proto jsou pro různé podmínky vhodné různé dopředné samoopravné kódy. Silnější kódy mají obecně větší redundanci, kterou je potřeba přenést dostupnou přenosovou kapacitou, což snižuje efektivní přenosovou rychlost při zlepšování efektivního poměru signál/šum přijímaného signálu. Pro výpočet maximální dosažitelné komunikační rychlosti pro danou maximální přijatelnou pravděpodobnost chyby lze použít Shannonovu větu o kapacitě kanálu, která určuje meze teoretické maximální rychlosti přenosu kanálem s určitou úrovní základního šumu. Důkaz však není konstruktivní, tedy neposkytuje návod, jak vytvořit kód blížící se kapacitě kanálu. Po letech výzkumu se některé pokročilé systémy samoopravných kódů od roku 2016 přibližují teoretickému maximu za předpokladu nekonečné délky rámce.
Princip fungování Pro opravu chyb se využívají redundantní informace přidané k přenášeným datům užitím nějakého algoritmu. Nadbytečné bity mohou být složitou funkcí mnoha původních informačních bitů. Původní informace se v zakódovaném výstupu může ale nemusí vyskytovat doslovně; kódy, u nichž je součástí výstupu neupravený vstup, jsou systematické; kódy, kde tomu tak není, jsou nesystematické.
Triviálním příkladem samoopravných kódů je vysílat každý datový bit třikrát, což se nazývá (3,1) opakovací kód. Na výstupu zarušeného kanálu se může objevit 8 verzí výstupu, viz tabulka níže.
Přijatá trojice Interpretováno jako0000 (bezchybný)0010010010001111 (bezchybný)110110110111 To umožňuje opravit chybu v jakémkoli ze tří vzorků „většinovým“ nebo „demokratickým hlasováním“. Opravná schopnost tohoto samoopravného kódu je: až 1 chybný bit v trojici nebo až 2 vynechané bity v trojici (případy nejsou uvedené v tabulce). Přestože že tento kód jednoduché implementovat a je široce používaný, tato trojitá modulární redundance je poměrně neefektivní samoopravný kód. Lepší samoopravné kódy obvykle kontrolují posledních několik desítek nebo dokonce stovek přijatých bitů pro určení, jak dekódovat několik málo současných bitů (obvykle ve skupinách 2 až 8 bitů).
Průměrování šumu pro omezení chyb Je možné říci, že samoopravné kódy využívají „průměrování šumu“; protože každý datový bit ovlivňuje mnoho přenášených symbolů, poškození některých symbolů šumem obvykle umožňuje získat původní uživatelská data z jiných přijatých, nepoškozených symbolů, které závisejí také na stejných uživatelských datech. Kvůli tomuto efektu „hromadění rizika“ digitální komunikační systémy, které používají samoopravné kódy, inklinují k tomu, že fungují dobře nad určitým minimálním poměrem signálu a šumu a nefungují vůbec pod ním. Tento sklon k výsledkům všechno nebo nic – efekt útesu – se projevuje tím silněji, čím silnější je kód, tedy především u kódů, které se blíží teoretickému Shannonovu limitu. Tuto vlastnost všechno nebo nic může omezovat prokládání dat v případech, kdy mají kanálové chyby tendenci objevovat se ve shlucích. Ale i tato metoda má své limity; nejlépe funguje pro úzkopásmová data.
Většina telekomunikačních systémů používá pevný kanálový kód navržený tak, aby fungoval v očekávaném nejhorším případě BER, ale pokud je bitová chybovost horší, zcela selžou. Určité systémy se však mohou přizpůsobit podmínkám kanálových chyb: některé druhy hybridní zpětné vazby s automatickým opakováním používají metodu pevných samoopravných kódů, pokud samoopravné kódy stačí pro danou četnost chyb, a když četnost chyb začne být příliš vysoká, přepínají na zpětnou vazbu s automatickým opakováním; adaptivní modulace a kódování používá několik poměrů samoopravného kódu, při vyšší četnosti chyb v kanálu přidávají do paketu více opravných bitů; a méně, když nejsou potřebné.
Typy samoopravných kódů
náhled|upright=1.3|Blokový kód (konkrétně Hammingův kód), v němž se redundantní bity přidávají na konec původní zprávy. náhled|Spojitý kód konvoluční kód, kde se redundantní bity přidávají do struktury kódového slova průběžně. vpravo|upright=2.25|náhled|Stručná klasifikace samoopravných kódů
Samoopravné kódy lze rozdělit na kódy blokové a konvoluční. Blokové kódy pracují na blocích (paketech) bitů nebo symbolů pevné, předem určené, velikosti. Praktické blokové kódy obecně mohou být pevně dekódovány v čase úměrném délce bloku. Konvoluční kódy pracují na proudech bitů nebo symbolů libovolné délky. Obvykle používají měkký přístup k dekódování s použitím Viterbiho algoritmu, někdy se však používají i jiné algoritmy. Viterbiho dekódování umožňuje asymptoticky optimální dekódovací efektivitu s rostoucím omezením délky konvolučního kódu, ale na úkor exponenciálně rostoucí složitosti. Konvoluční kód, který je ukončený, je také 'blokový kód' v tom, že kóduje blok vstupních dat, ale velikost bloku konvolučního kódu je obecně libovolná, zatímco blokové kódy mají pevnou velikost vynucenou jejich algebraickou charakteristikou. Typy ukončení pro konvoluční kódy zahrnuje „useknutí konce“ a „bitový výplach“.
Existuje mnoho typů blokových kódů; Reedovy–Solomonovy kódy jsou významné pro své velké rozšíření na kompaktních discích, DVD, a pevných discích. Příkladem klasických blokových kódů jsou Golayův kód, BCH kód, vícerozměrný kód s kontrolou parity, a Hammingovy kódy.
Hammingův samoopravný kód se často používá pro opravu chyb ve flash pamětech.“Hamming codes for NAND flash memory devices“ . EE Krát-Asia. Zdánlivě založený na “Micron Technical Note TN-29-08: Hamming Codes for NAND Flash Memory Devices“ . 2005. Oba říkají: „Hammingův algoritmus je průmyslově přijatá metoda detekce a opravy chyb v mnoha SLC NAND vycházející z flash aplikace.“ To poskytuje opravu jednobitových chyb a detekci dvoubitových chyb. Hammingovy kódy jsou vhodné pouze pro spolehlivější (SLC) NAND s víceúrovňovými buňkami. hustější NAND s víceúrovňovými buňkami (MLC) mohou používat vícebitové samoopravné kódy, jako například BCH nebo Reed–Solomon. Flash paměti NOR obvykle nepoužívají žádnou opravu chyb.
Klasické blokové kódy se obvykle dekódují pomocí algoritmů s pevným rozhodováním, což znamená, že pro každý vstupní a výstupní signál se provede pevné rozhodnutí, zda odpovídá jedničkovému nebo nulovému bitu. Naproti tomu konvoluční kódy se obvykle dekódují pomocí algoritmů s měkkým rozhodováním jako je Viterbiho algoritmus, MAP nebo algoritmus BCJR, které zpracovávají (diskretizované) analogové signály, a které poskytují mnohem vyšší výkonnost při opravách chyb než dekódování s pevným rozhodováním.
Téměř všechny klasické blokové kódy využívají algebraické vlastnosti konečných těles. Proto jsou klasické blokové kódy často označovány jako algebraické kódy.
V protikladu ke klasickým blokovým kódům, u nichž se často udává schopnost detekce nebo opravy chyb, mnoho moderních blokových kódů jako například Nízkohustotní kód s kontrolou parity takovou záruku postrádá. Místo toho se moderní kódy hodnotí podle jejich četnosti bitových chyb.
Většina kódů pro dopřednou opravu chyb opravuje pouze změny hodnot jednotlivých bitů, ne však vložení nebo výpadek bitu. V tomto případě je Hammingova vzdálenost vhodným způsobem, jak měřit BER. Několik málo dopředných samoopravných kódů, jako například Marker Kódy a Watermark kódy, je navrženo tak, aby byly schopné opravit vložení nebo vypouštění bitu. Při použití takových kódů je pro měření bitové chybovosti vhodnější Levenštejnova vzdálenost.