Zřetězený kód opravy chyb - Concatenated error correction code

v teorie kódování, zřetězené kódy tvoří třídu kódy opravující chyby které jsou odvozeny kombinací vnitřní kód a vnější kód. Byly vytvořeny v roce 1966 Dave Forney jako řešení problému nalezení kódu, který má exponenciálně klesající pravděpodobnost chyby s rostoucí délkou bloku a polynomiální čas dekódování složitost.^[1]V 70. letech se v kosmické komunikaci široce používaly zřetězené kódy.

Pozadí

Pole kódování kanálu se zabývá odesíláním proudu dat nejvyšší možnou rychlostí za danou dobu komunikační kanál a poté spolehlivě dekódovat původní data v přijímači pomocí kódovacích a dekódovacích algoritmů, které je možné v dané technologii implementovat.

Shannonova věta o kódování kanálu ukazuje, že na mnoha běžných kanálech existují schémata kódování kanálů, která jsou schopna spolehlivě přenášet data při všech rychlostech ${displaystyle R}$ menší než určitá prahová hodnota ${displaystyle C}$, volal kapacita kanálu daného kanálu. Pravděpodobnost chyby dekódování lze ve skutečnosti exponenciálně snižovat s délkou bloku ${displaystyle N}$ schématu kódování jde do nekonečna. Složitost naivního optimálního dekódovacího schématu, které jednoduše spočítá pravděpodobnost každého možného přenášeného kódového slova, se však exponenciálně zvyšuje s ${displaystyle N}$, takže takový optimální dekodér se rychle stává neproveditelným.

V jeho disertační práce, Dave Forney ukázaly, že zřetězené kódy lze použít k dosažení exponenciálně klesajících pravděpodobností chyb při všech rychlostech dat nižších, než je kapacita, se složitostí dekódování, která se zvyšuje pouze polynomiálně s délkou bloku kódu.

Popis

Schematické zobrazení zřetězeného kódu postaveného na vnitřním kódu a vnějším kódu.

Toto je obrazové znázornění zřetězení kódu, a zejména Reed-Solomonův kód s n = q = 4 ak = 2 se používá jako vnější kód a Hadamardův kód s n = q ak = log q se používá jako vnitřní kód. Celkově je zřetězený kód a ${displaystyle [q ^ {2}, klog q]}$-kód.

Nechat C_v být [n, k, d] kód, tj. a blokovat kód délky n, dimenze k, minimum Hammingova vzdálenost d, a hodnotit r = k/n, nad abecedou A:

${displaystyle C_ {in}: A ^ {k} ightarrow A ^ {n}}$

Nechat C_ven být [N, K., D] kód přes abecedu B s |B| = |A|^k symboly:

${displaystyle C_ {out}: B ^ {K} ightarrow B ^ {N}}$

Vnitřní kód C_v bere jeden z |A|^k = |B| možné vstupy, kóduje do n-tuple přes A, vysílá a dekóduje do jednoho z |B| možné výstupy. Považujeme to za (super) kanál, který může přenášet jeden symbol z abecedy B. Používáme tento kanál N časy přenosu každého z N symboly v kódovém slově o C_ven. The zřetězení z C_ven (jako vnější kód) s C_v (jako vnitřní kód), označeno C_ven∘C_v, je tedy kód délky Nn přes abecedu A:^[1]

${displaystyle C_ {out} circle C_ {in}: A ^ {kK} ightarrow A ^ {nN}}$

Mapuje každou vstupní zprávu m = (m₁, m₂, ..., m_K.) na kódové slovo (C_v(m'₁), C_v(m'₂), ..., C_v(m'_N)), kde (m'₁, m'₂, ..., m'_N) = C_ven(m₁, m₂, ..., m_K.).

The klíčový vhled v tomto přístupu je, že pokud C_v je dekódován pomocí a přístup s maximální pravděpodobností (tedy ukazuje exponenciálně klesající pravděpodobnost chyby s rostoucí délkou), a C_ven je kód s délkou N = 2^č které lze dekódovat v polynomiálním čase N, potom může být zřetězený kód dekódován v polynomiálním čase jeho kombinované délky n2^č = Ó (N⋅log (N)) a ukazuje exponenciálně klesající pravděpodobnost chyby, i když C_v má exponenciální složitost dekódování.^[1] To je podrobněji popsáno v části Dekódování zřetězených kódů.

V generalizaci výše uvedeného zřetězení existují N možné vnitřní kódy C_v,i a i-tý symbol v kódovém slově C_ven se přenáší přes vnitřní kanál pomocí i-tý vnitřní kód. The Justesenovy kódy jsou příklady zobecněných zřetězených kódů, kde vnější kód je a Reed-Solomonův kód.

Vlastnosti

1. Vzdálenost zřetězeného kódu C_ven∘C_v je alespoň dD, to znamená, že je [nN, kK, D'] kód s D' ≥ dD.

Důkaz:Zvažte dvě různé zprávy m¹ ≠ m² ∈ B^K.. Nechť Δ označuje vzdálenost mezi dvěma kódovými slovy. Pak

${displaystyle Delta (C_ {out} (m ^ {1}), C_ {out} (m ^ {2})) geq D.}$

Existují tedy přinejmenším D pozice, ve kterých je posloupnost N symboly kódových slov C_ven(m¹) a C_ven(m²) lišit. Pro tyto pozice označeno i, my máme

${displaystyle Delta (C_ {in} (C_ {out} (m ^ {1}) _ {i}), C_ {in} (C_ {out} (m ^ {2}) _ {i})) geq d .}$

V důsledku toho existují alespoň d⋅D pozice v pořadí n⋅N symboly převzaté z abecedy A ve kterém se obě kódová slova liší, a tedy

${displaystyle Delta (C_ {in} (C_ {out} (m ^ {1})), C_ {in} (C_ {out} (m ^ {2}))) geq dD.}$

2. Li C_ven a C_v jsou lineární blokové kódy, pak C_ven∘C_v je také lineární blokový kód.

Tuto vlastnost lze snadno zobrazit na základě myšlenky definování a matice generátoru pro zřetězený kód, pokud jde o matice generátoru C_ven a C_v.

Dekódování zřetězených kódů

Přirozeným konceptem dekódovacího algoritmu pro zřetězené kódy je nejprve dekódování vnitřního kódu a poté vnějšího kódu. Aby byl algoritmus praktický, musí být polynomiální čas v konečné délce bloku. Vezměte v úvahu, že pro vnější kód existuje jedinečný dekódovací algoritmus v polynomiálním čase. Nyní musíme pro vnitřní kód najít algoritmus dekódování v polynomiálním čase. Rozumí se, že doba běhu polynomu zde znamená, že doba běhu je polynom v konečné délce bloku. Hlavní myšlenkou je, že pokud je délka vnitřního bloku zvolena jako logaritmická ve velikosti vnějšího kódu, pak může běžet dekódovací algoritmus pro vnitřní kód v exponenciální čas délky vnitřního bloku a můžeme tedy použít exponenciální čas, ale optimální dekodér maximální věrohodnosti (MLD) pro vnitřní kód.

Podrobně nechte vstup do dekodéru vektor y = (y₁, ..., y_N) ∈ (Aⁿ)^N. Dekódovací algoritmus je pak dvoustupňový proces:

1. Použijte MLD vnitřního kódu C_v rekonstruovat sadu slov vnitřního kódu y' = (y'₁, ..., y'_N), s y'_i = MLD_Cv(y_i), 1 ≤ i ≤ N.
2. Spusťte jedinečný dekódovací algoritmus pro C_ven na y'.

Nyní je časová složitost prvního kroku Ó (N⋅exp (n)), kde n = Ó(log (N)) je délka vnitřního bloku. Jinými slovy, je N^Ó(1) (tj. polynomiální čas), pokud jde o délku vnějšího bloku N. Protože se předpokládá, že vnější dekódovací algoritmus v kroku dva běží v polynomiálním čase, je složitost celkového dekódovacího algoritmu také v polynomiálním čase.

Poznámky

Výše popsaný dekódovací algoritmus lze použít k opravě všech chyb až do hodnoty menší než dD/ 4 v počtu. Použitím dekódování minimální vzdálenosti, vnější dekodér může opravit všechny vstupy y„s méně než D/ 2 symboly y'_i omylem. Podobně může vnitřní kód spolehlivě opravit vstup y_i pokud je menší než d/ 2 vnitřní symboly jsou chybné. Tedy pro vnější symbol y'_i nesprávné alespoň po vnitřním dekódování d/ 2 vnitřní symboly musely být omylem a pro selhání vnějšího kódu k tomu muselo dojít minimálně D/ 2 vnější symboly. V důsledku toho musí být alespoň celkový počet vnitřních symbolů, které musí být nesprávně přijaty, aby zřetězený kód selhal d/2⋅D/2 = dD/4.

Algoritmus také funguje, pokud jsou vnitřní kódy odlišné, např. Pro Justesenovy kódy. The zobecněný algoritmus minimální vzdálenosti, vyvinutý společností Forney, lze použít k opravě až dD/ 2 chyby.^[2]Využívá to výmaz informace z vnitřního kódu ke zlepšení výkonu vnějšího kódu a byl prvním příkladem použití algoritmu dekódování soft-decision.^[3][4]

Aplikace

Ačkoli jednoduché schéma zřetězení bylo zavedeno již pro rok 1971 Námořník Mars orbiter mise,^[5] zřetězené kódy se začaly pravidelně používat hluboký vesmír komunikace s Program Voyager, který zahájil dva vesmírné sondy v roce 1977.^[6] Od té doby se zřetězené kódy staly tahounem pro efektivní kódování korekce chyb a zůstaly jimi alespoň do doby, než turbo kódy a Kódy LDPC.^[5][6]

Vnitřní kód obvykle není blokový kód, ale měkké rozhodnutí konvoluční Viterbiho dekódováno kód s krátkou délkou omezení.^[7]U vnějšího kódu delší blokový kód s pevným rozhodnutím, často a Reed-Solomonův kód s osmibitovými symboly.^[1][5]Díky větší velikosti symbolu je vnější kód robustnější chybové záblesky k tomu může dojít v důsledku narušení kanálu a také proto, že chybný výstup samotného konvolučního kódu je prudký.^[1][5] An prokládací vrstva se obvykle přidává mezi dva kódy, aby se šíření chybových hlášení rozšířilo do širšího rozsahu.^[5]

Kombinace vnitřního Viterbiho konvolučního kódu s vnějším Reed-Solomonův kód (známý jako kód RSV) byl poprvé použit v Voyager 2,^[5][8] a stala se populární konstrukcí uvnitř i vně vesmírného sektoru. Stále se pozoruhodně používá dodnes satelitní komunikace, tak jako DVB-S digitální televize vysílací standard.^[9]

Ve volnějším smyslu může být jakákoli (sériová) kombinace dvou nebo více kódů označována jako zřetězený kód. Například v rámci DVB-S2 standardní, vysoce efektivní Kód LDPC je kombinován s algebraickým vnějším kódem, aby se odstranily všechny odolné chyby, které zbyly z vnitřního kódu LDPC kvůli jeho inherentní chybová podlaha.^[10]

Jednoduché schéma zřetězení se používá také na kompaktním disku (CD), kde prokládací vrstva mezi dvěma kódy Reed-Solomon různých velikostí šíří chyby napříč různými bloky.

Turbo kódy: Přístup paralelního zřetězení

Výše uvedený popis je uveden pro takzvaný sériově zřetězený kód. Turbo kódy, jak bylo popsáno poprvé v roce 1993, implementovalo paralelní zřetězení dvou konvolučních kódů s prokládačem mezi těmito dvěma kódy a iteračním dekodérem, který předává informace tam a zpět mezi kódy.^[6] Tento design má lepší výkon než jakékoli dříve koncipované zřetězené kódy.

Klíčovým aspektem turbo kódů je však jejich iterovaný přístup k dekódování. Iterované dekódování se nyní také aplikuje na sériová zřetězení, aby se dosáhlo vyšších zisků kódování, například v sériově zřetězených konvolučních kódech (SCCC). Raná forma iterovaného dekódování byla implementována dvěma až pěti iteracemi v „kódu Galileo“ Kosmická sonda Galileo.^[5]

Viz také

• Justesenův kód
• Zyablov vázán
• Singleton vázán
• Gilbert – Varshamov vázán

Reference

Další čtení

• Shu Lin; Daniel J. Costello Jr. (1983). Kódování kontroly chyb: Základy a aplikace. Prentice Hall. str.278 –280. ISBN  978-0-13-283796-5.
• FJ MacWilliams; N.J.A. Sloane (1977). Teorie kódů pro opravu chyb. Severní Holandsko. str.307–316. ISBN  978-0-444-85193-2.

externí odkazy

• Dave Forney (vyd.). "Zřetězené kódy". Scholarpedia.
• University at Buffalo Přednášky o teorii kódování - Dr. Atri Rudra