CZ407397A3

CZ407397A3 - Paralelní zřetězené konvoluční kódy s koncovými bity a jejich dekodéry

Info

Publication number: CZ407397A3
Application number: CZ974073A
Authority: CZ
Inventors: Stephen Michael Hladik; John Bailey Anderson
Original assignee: General Electric Company
Priority date: 1996-04-19
Filing date: 1997-04-14
Publication date: 1998-06-17
Also published as: DE69736881T2; EP0834222B1; PL183537B1; UA44779C2; PL323524A1; ID16464A; AU2459197A; HUP9901440A3; HUP9901440A2; ZA973217B; NO975966L; CN1111962C; CA2221295A1; JP3857320B2; AU716645B2; RU2187196C2; HU220815B1; CN1189935A; WO1997040582A1; NO975966D0

Description

Vynález se týká paralelních zřetězených (konkatenovaných) konvolučních kódů s koncovými bity (tail-biting) a jejich, dekodérů a obecně samoopravných kódů pro přenášení krátkých zpráv po sdělovacích kanálech nízké kvality.

Dosavadní stav techniky

Jedna z forem paralelních zřetězených (konkatenovaných) kódů, označovaná jako paralelní zřetězené konvoluční kódování (parallel concatenated convolution coding - PCCC) nebo ”turbo kódování” (turbo coding) byla předmětem současného výzkumu v oblasti kódování především vzhledem ke svému impresivnímu přínosu pro kódování bloků obsahujících 10000 nebo více bitů. (Viz např. C. Berrou, A. Glavieux a P. Thitimajshima, ”Near Shannon Limit Error-Correcting Coding and Decoding: Turbo Codes”, Proceedings of the IEEE International Conference on Communications, 1993, str. 1064-1070, dále J.D. Andersen ”The TURBO Coding Scheme”, Report IT-146 ISSN 0105-854, Institute of Telecommunication, Technical University of Denmark, prosinec 1994 a P. Robertson, ”Illuminating the Structure of Code and Decoder of Parallel Concatenated Recursive Systematic (Turbo) Codes”, 1994 IEEE Globecom Conference, str. 1298-1303). .

• ·· ·

Bylo však ukázáno, že výkonnost turbo kódů podstatně ubývá, pokud délka kódovaných datových bloků klesá. Tento efekt je způsoben silnou závislostí váhové struktury složkových rekurzivních systematických konvolučních kódů na délce bloku. Druhou otázkou je správné ukončení bloků zpráv, předložených turbo kodéru. Jak popsali O. Joersson a H. Meyr v ”Terminating the Trellis of Turbo-Codes”, IEE Electronics Letters, svazek 30, č. 16, 4. srpen 1994, str. 1285-1286, prokládané (interleaving) použit í turbo kodérů může znemožnit, ukončení vstupních posloup-----ností jak v prokládaných tak i neprokládaných kodérech jediným souborem koncových bitů. I když je možno použít druhou posloupnost koncových bitů, vnořenou do struktury zprávy tak, že kodér pracující na prokládané datové posloupnosti správně ukončí, zdvojnásobí se tím činnost spojená se správným ukončením a tím se redukuje účinnost kódu. Alternativou je neukončovat jednu z kódovaných posloupností, ale to snižuje účinnost systému kódování a dekódování, obzvláště když je tato možnost použita na krátké zprávy. V ”Terminating the Trellis of Turbo-Codes in the Same Statě”, IEE Electronics Letters, 1995, svazek 31, č. 1, 5. ledna, str. 22-23 A.S. Barbulescu a S.S. Pietrobon popisují metodu, která omezuje návrh prokládaného kodéru s cílem ukončit činnost složkových rekurzivních systemetických konvolučních (recursive systematic convolutional - RSC) kodérů jedinou ukončující posloupností bitů. Jejich výsledky, týkající se výkonnnosti, ukazují jisté zhoršení ve srovnání s výkonem získaným při ukončení obou kodérů, pokud je použito optimalizované prokládání. Navíc publikovaná data o poměru počtu bitových chyb (bit-error rate - BER) a veličiny, udávající energii na bit vzhledem k šumové výkonové spektrální hustotě (energy-perbit-to-noise-power-spectral-density), označovaný E^/Nq ukazují zploštění hodnoty BER ve velkém rozsahu hodnot E^/Nq, pokud jsou v turbo kodéru použity RSC.

Je proto žádoucí podat zlepšenou paralelní zřetězenou kódovací techniku pro krátké bloky dat.

Podstata vynálezu

Podle předkládaného vynálezu paralelní zřetězená konvoluění kódovací schémata používají nerekurzivní systematické konvoluční kódy (nonrecursive systematic convolutional - NSC) s koncovými bity (tail-biting). Příslušný kodér používá cirkulární maximální a posteriori (MAP) dekódování pro vytváření silných a slabých rozhodnutí, použití kódů s koncovými bity řeší problém ukončení datové sekvence v turbo kódování, čímž se předchází snížení výkonnosti příslušného kodéru pro krátké zprávy. I když NSC kódy jsou v obecnosti asymptoticky slabší než rekurzivní systematické konvoluění (RSC) kódy využívající téže paměti při rostoucí délce bloku, volná vzdálenost NSC kódu je méně citlivá na délku bloku. Z tohoto důvodu je paralelní zřetězené (konkatenované) kódování s NSC kódy výkonnější než při použití RSC kódů se stejnou velikostí paměti pro zprávy, které jsou kratší než je jistá prahová délka datového bloku.

Přehled obrázků na výkrese

Různé vlastnosti a výhody předkládaného vynálezu se stanou zřejmými z podrobného vysvětlení podaného níže, které využívá přiložených obrázků, ve kterých obr. 1 je zjednodušené blokové schéma znázorňující paralelní zřetězený kodér, ·· · obr. 2 je zjednodušené blokové schéma znázorňující dekodér pro paralelní zřetězené kódy, obr. 3 je zjednodušené blokové schéma znázorňující nerekurzivní systematický konvoluční kodér, užívající koncových bitů, pro použití v kódovacím schématu podle předloženého vynálezu, obr. 4 je zjednodušené blokové schéma znázorňující cirkulární MAP dekodér použitelný jako složkový dekodér pro paralelní ------zřetězené konvoluční kódovací schéma podlé předkládaného vynálezu a obr. 5 je zjednodušené blokové schéma znázorňující alternativní provedení cirkulárního MAP dekodéru použitelného jako složkový dekodér pro paralelní zřetězené konvoluční kódovací schéma podle předkládaného vynálezu.

Příklady provedení vynálezu

Obr. 1 je obecné blokové schéma zpracování 10 signálu v kodéru pro paralelní kódovací schéma, které zahrnuje složkové kodéry 12 v celkovém počtu N a operuje na blocích dat, přicházejících ze zdroje. Datové bloky jsou permutovány podle prokládacího algoritmu v prokládacích zařízeních 14. Jak vyplývá z obrázku, pro N kodérů 12 je použito N — 1 překrývacích zařízení. Nakonec výstupy složkových kodérů jsou spojeny do jediného složeného zakódovaného slova formátovacím zařízením 16 složeného kódového slova. Formátovací zařízení složeného kódového slova je zvoleno tak, aby odpovídalo vlastnostem přenosového kanálu a může být následováno rámcovým formátovacím zařízením; které je zvoleno tak, aby odpovídalo přístupovým techni4 kám použitým v přenosovém kanálu a komunikačním systému.

plňková data jako jsou ovládací bity a synchronizační symboly.

Významné zlepšení výkonu kódování může být při paralelním zřetězeném (konkatenovaném) kódování dosaženo v případě, že složkové kódy jsou systematické kódy. Kódové slovo (výstup) vytvořené systematickým kodérem obsahuje původní datové bity, přivedené na vstup kodéru a doplňkové paritní bity. (Reduncláhce, přinášená vloženými paritními bity, je základ pro schopnost kódu provádět opravu chyb). Jestliže tedy jsou systemetické kodéry používány v paralelním. zřetězeném kodéru znázorněném na obr. 1, kódové slovo, vytvářené všemi složkovými kodéry 12 obsahují vstupní datové bity. Jestliže formátovací zařízení 16 vytváří datový paket nebo složené kódové slovo zahrnující pouze paritní bity, vytvořené jednotlivými složkovými kodéry 12 a blokem informačních bitů, které mají být kódovány, je možno dosáhnout významného zlepšení ve výkonu složeného paralelního zřetězeného kódu tím, že se eliminují opakování informačních bitů v přenášeném složeném kódovém slově. Tak například jestliže složkový kodér 1 a složkový kodér 2 v kodéru používajícím paralelní zřetězený konvoluční kód (PCCC) sestávajícím ze dvou složkových kódů využívají oba kód o poměru 1/2, pak poměr složeného paralelního zřetězeného kódu vzroste z 1/4 pro nesystematické složkové kódy na 1/3, pokud jsou použity systematické složkové kódy.

Paralelní zřetězená kódovací schémata která používají rekurzivní systematické konvoluční (RSC) kódy byly v nedávné době předmětem intenzivního výzkumu. Tyto paralelní zřetězené konvoluční kódy (PCCC) jsou také v literatuře známy jako ”turbo” kódy. Jak bylo uvedeno výše, bylo ukázáno, že tyto PCCC mohou dosáhnout impresivních výkonů ve smyslu poměru počtu bitových chyb (BET) k energii na bit vzhledem k šumové výkonové spektrální hustotě (E^/lVo) pro relativně dlouhé zprávy, což znamená pro zprávy o deseti tisících nebo více bitech. Na druhé straně bylo ukázáno, že kódovací zisk spojený s použitím turbo kódů významně klesá s klesající velikostí bloku neboť síla rekurzivních systematických konvolučních složkových kódů je velmi citlivá k délce bloku. Na druhé straně výkonnost nerekurzivních systematických konvolučních kódů s koncovými bity je nezávislá pro většinu praktických použití na délce bloku a získatelná vý--------konnost klesá pouze jestliže blok zakódovaných datových bitů je menší než minimální velikost, kterou je možno určit na základě vlastností rozhodovací hloubky NSG kódů. ^J

Obr. 2 znázorňuje obecný dekodér 20 pro paralelné zřetězené kódy ve formě blokového schématu. Dekodér 20 sestává z následujících částí: konvertor 22 rozkládající složené kódové slovo na složková slova, který konvertuje složené kódové slovo, přijmuté z přenosového kanálu na individuální přijatá kódová slova pro každý složkový dekodér 24; N složkových dekodérů 24 odpovídajících N složkovým kodérům z obr. 1’ prokládacích zařízení 14 shodného typu (nebo shodných) s prokládacími zařízeními použitými v paralelním zřetězeném kodéru (obr. 1); a první a druhé zařízení pro odstranění prokládání 28 a 29, které mají obě přerovnávací charakteristiky ekvivalentní se sériovým zřetězením N — 1 zařízení 30 pro odstranění prokládání odpovídajících N — 1 prokládacím zařízením, používaným pro kódování. Požadované uspořádání zařízení pro odstranění prokládání je znázorněno na obr. 2 a je opačné než je uspořádání prokládacích zařízení. Výstupy složkových dekodérů 24 představují nějaký typ slabé rozhodovací informace o odhadované hodnotě každého bitu v přijatém kódovém slově. Například výstupy složkových dekodérů mohou být představovány první funkcí prav6

děpodobnosti, že dekódované bity jsou 0 nebo 1 v závislosti na posloupnosti symbolů, přijatých z přenosového kanálu. Příklad takové první funkce odstraňuje vliv podmíněné pravděpodobnosti P{d³ = 0|Y/} na slabé výstupní rozhodnutí složkového dekodéru, které je po vhodné permutaci přenášeno na následující sekvenční složkový dekodér, přičemž P{d³t = 0|Yř^J} je pravděpodobnost, že j-tý informační bit v okamžiku t je 0 za předpokladu o hodnotě ý-tého (systematického) bitu přijatého kanálového výstupního symbolu Yt. .Alternativně-informace o slabém-------------------rozhodnutí, vydaném složkovým dekodérem 24 může být funkce pravděpodobnostního poměru _Λ , ₌ P{4 = W} ₌ 1 - P{di = o|yf} ^ = 01^} P{d{ = nebo jako funkce logaritmu pravděpodobnostního poměru log[A(ď|ř)].

Jak bylo ukázáno, N-tý složkový dekodér má druhý výstup, to jest druhou funkci podmíněné pravděpodobnosti pro hodnoty dekódovaných bitových hodnot nebo výše uvedených pravděpodobnostních poměrů. Jako příklad takové druhé funkce lze podat součin podmíněné pravděpodobnosti P{d³t — OlYj¹'} a a priori pravděpodobnosti, že d³t = 0 získané z předchozího složkového dekodéru.

Dekodér pro paralelní zřetězené kódy pracuje iterativně následujícím způsobem: První složkový dekodér (dekodér 1) vypočte množinu hodnot slabých rozhodnutí pro posloupnost informačních bitů, zakódovaných prvním složkovým kodérem na základě přijatého kódového slova a jakékoliv a priori informace o vyslaných informačních bitech. V první iteraci, jestliže nejsou žádné a priori informace o zdrojových statistikách, předpokládá se, že je stejná pravděpodobnost, že bity jsou 0 nebo 1 (to jest • ·· · ·♦ ♦

P{bit = 0} = P{bit = 1} = 1/2). Hodnoty slabých rozhodnutí, vypočtené dekodérem 1 jsou potom překryty použitím stejného typu (nebo stejných) prokládacích zařízení které byly použity v kodéru k permutování bloků datových bitů pro druhý kodér. Tyto permutované hodnoty slabých rozhodnutí a odpovídající přijaté kódové slovo zahrnují vstupy pro následující složkový dekodér (dekodér 2). Permutované hodnoty slabých rozhodnutí přijaté z předchozího složkového dekodéru a prokládacího zařízení jsou použita v následujícím složkovém dekodéru jako a------------------priori informace o datových bitů, určených k dekódování. Složkové dekodéry pracují sekvenčně tímto způsobem, dokud 7V-tý dekodér neurčí množinu výstupních slabých rozhodnutí pro blok datových bitů, které byly kódovány kodérem. Následující krok je odstranění překrytí hodnot slabých rozhodnutí 7V-tého dekodéru, jak bylo popsáno výše. První dekodér potom operuje opět na přijatém kódovém slově používajíce používajíce nové hodnoty slabých rozhodnutí z 7V-tého dekodéru jako jeho a priori informace. Práce dekodéru postupuje tímto způsobem po požadovaný počet informací. Jako výsledek závěrečné operace je posloupnost hodnot, které jsou druhou funkcí výstupních slabých rozhodnutí vypočtených 7V-tým dekodérem, vyjmuta z překrytí s cílem získat datave tvaru, ve ktrém byla přijata PCCC kodérem. Počet iterací může být dán předem danou hodnotou a nebo může být určen dynamicky na základě určování konvergence dekodéru.

Dekodér poskytuje informaci o slabých rozhodnutích která jsou funkcí pravděpodobnosti P{d^J _t = OlY/'}; to jest podmíněné pravděpodobnosti, že ý-tý datový bit v fc-bitovém vstupním symbolu pro kodér v čase t je 0, za předpokladu, že je přijat soubor výstupů kanálu Yf = {?/i,..., yi}. Navíc dekodér může poskytovat informaci o silných rozhodnutích jako funkci svých slabých výstupních rozhodnutí prostřednictvím rozhodovacího

zařízení, které implementuje rozhodovací pravidlo, jako je $ =0 >

P{4=0| ΥΛ <

....____________Ít____= ¹________L

To jest jestliže P{d³t — llY/⁷} > pak d³t = 0 a jestliže P{d³t = ÍIY^} < |, pak d³ = 1, jinak náhodně přiřaďd³t hodnotu 0 nebo 1.

Typické turbo dekodéry používají buď maximální a posteriori (MAP) dekodéry, jako například popsali L.R. Bahl, J. Cocke, F. Jelínek a J. Raviv v ”Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate”, IEEE Transactions on Information Theory, březen 1974, str. 284-287 nebo dekodéry používající ”soft output Viterbi” algoritmus (SOVA), jako například popsali J. Hagenauer a P. Hoeher v ”A Viterbi Algórithm with Soft-Decision Outputs and its Applications”, 1989 IEEE Globecom Conference, str. 1680-1686. MAP dekodér produkuje pravděpodobnost, že dekódovaný bit je 0 nebo 1. Na druhé straně SOVA dekodér typicky vypočítává pravděpodobnostní poměr

P{dek’odovaný bit je 1}

P{dek’odovaný bit je 0} pro každý dekódovaný bit. Je zřejmé, že tento pravděpodobnostní poměr můža být získán z P{dek’odovaný bit je 0} a nebo na druhé straně použitím P{dek’odovaný bit je 0} = • · · log1 — P{dek’odovaný bit je 1}. Bylo zjištěno, že jistá výpočetní výhoda nastává, když buď MAP nebo SOVA dekodér pracuje s logaritmem výpočetních poměrů, to jest s

P{dek’odovaný bit je 1} P{dek’odovaný bit je 0}

Bylo dokázáno, že kódovací zisk (schopnost opravy chyb), získaný s turbo kódy“významně klesá s 'klesající velikosti datového ’ bloku. Několik autorů přikládá toto chování primárně vlastnostem RSC kódů. Bylo ukázáno, že vlastnost vzdálenosti v RSC kódu roste s rostoucí délkou datového bloku. Naopak, minimální vzdálenost v RSC kódu klesá s klesající délou datového bloku. Druhý problém je potíž s ukončením všech RSC kódů, obsahujících turbo kódovací schéma díky prokládání. Je nevýhodné, že nepříznivé efekty, vznikající z chybějícího zakončení posloupnosti nebo z restrikcí týkajících se návrhu prokládacího zařízaní jsou významné a stávají se ještě významnějšími s klesající délkou datového bloku.

Podle předkládaného vynálezu složkové kódy v paralelním zřetězeném konvolučním kódu zahrnují nerekurzivní systematické konvoluční kódy s koncovými bity. Použití takových kódů s koncovými bity řeší problém ukončení vstupní datové posloupnosti při turbo kódování, čímž je možné se vyhnout problému snižování výkonnosti dekodéru pro krátké zprávy. I když jsou NSC kódy v obecnosti slabší než RSC kódy mající téže množství paměti, volná vzdálenost v NSC kódech je méně citlivá na délku datového bloku. Proto se paralelní zřetězené kódování s NSC kódy chová lépe než RSC kódování se stejným množstvím paměti pro zprávy, které jsou kratší než předem daná prahová velikost datového bloku. Bod, kdy se výkonnosti kódovacích schémat se tkávají je funkcí požadovaného poměru bitových chyb (BET) dekodéru, množství chyb a kódovací paměti.

Obr. 3 ukazuje příklad nerekurzivního systematického konvolučního kodéru s koncovými bity pro použití v paralelním zřetězeném konvolucním schématu s kódovacím s poměrem =1/2 a pamětí velikosti m podle předkládaného vynálezu. Pro potřeby definice výraz (n, k, m) kodér označuje kodér ve kterém vstupní symboly obsahují k bitů, výstupní symboly obsahují_n_bitů__a m = paměť kodéru v počtu A)-bitových symbolů. Pro ilustraci je obr. 3 nakreslen pro binární vstupní symboly, to jest k — 1. Předkládaný vynález však umožňuje pracovat s libovolnými hodnotami fc, n a m.

Na počátku je přepínač 50 ve spodní poloze a L vstupních bitů je přeneseno do posuvného registru (shift register) 52, k najednou (jeden vstupní symbol najednou pro tento příklad). Po uložení L=tého bitu do kodéru se přepínač přesune do horní polohy a kódování započně posunem prvního bitu z druhého posuvného registru 54 do nerekurzivního systematického kodéru, přičemž stav kodéru v tento okamžik je {&£,, ...,

V tomto příkladě zahrnuje výstup kodéru zpracovávaný vstupní bit a paritní bit, vytvořený v bloku 56 (znázorněn v tomto příkladě jako sčítání modulo 2) jako funkce stavu kodéru a zpracovávaného vstupního symbolu. Kódování končí když je zakódován L-tý bit.

Další předmět předkládaného vynálezu je představován dekodérem, odpovídajícím výše popsanému paralelnímu zřetězenému kodéru, který zahrnuje cirkulární MAP dekodér, tak jak je popsán přihlašovateli v současně podané U.S. patentové přihlášce č. (RD-24,923), která je zde zahrnuta jako reference. U.S. patentová přihláška ě. (RD-24,923) obvzláště zahrnuje cirkulární

MAP kodér použitelný pro dekódování konvolučních kódů s koncovými bity. Cirkulární MAP dekodér může poskytovat jak odhad zakódovaného datového bloku, tak i informaci o spolehlivosti dat pro zařízení, které je spotřebovává, například pro signální procesor pro syntézu řeči, který tuto informaci může použít pro ?concealment přenosových chyb a nebo pro protokolový procesor pro datové pakety, který ji využívá jako míru pravděpodobnosti blokové chyby při rozhodování o opakovaných požaSpeciálně, jak je popsáno v U.S. patentové přihlášce č. (RD24,923), cirkulární MAP dekodér pro samoopravné trellis (mřížové) kódy, používající koncových bitů, vytváří slabá výstupní rozhodnutí. Cirkulární MAP dekodér poskytuje odhady pravděpodobností stavů v první etapě mříže (trellis), a tyto pravděpodobnosti nahrazují a priori znalost výchozího stavu v konvenčním MAP dekodéru. Cirkulární MAP dekodér poskytuje pravděpodobnostní rozdělení počátečního stavu v jednom ze dvou tvarů. První zahrnuje řešení problému vlastních hodnot pro které odpovídající vlastní vektor představuje požadované pravděpodobnostní rozdělení počátečního stavu a se znalostí počátečního stavu cirkulární MAP dekodér provede zbytek dekódování podle obvyklého MAP dekódovacího algoritmu. Druhé je založeno na rekurzi, jejíž iterace konvergují k pravděpodobnostnímu rozdělení počátečního stavu. Po dostatečném počtu iterací je stav cirkulární posloupnosti stavů znám s vysokou pravděpodobností a cirkulární MAP dekodér provede zbytek dekódování podle ob* vyklého MAP dekódovacího algoritmu.

Cílem konvenčního MAP dekódovacího algoritmu je nalezení podmíněných pravděpodobností • · · · · ·

P{stav m v čase t | přijaty kanálové výstupy yi,..., y^}

Výraz L v tomto výrazu představuje délku datového bloku vyjádřenou v počtu kódovaných symbolů. (Kodér pro (n, k) kód pracuje s A;-bitovými vstupními symboly a generuje n-bitové výstupní symboly. Výraz y_t představuje kanálový výstup (výstupní symbol) v čase t.______________________________________________

MAP dekódovací algoritmus nejprve nalezne pravděpodobnosti:

A(m) = P{S_t = m; Y,¹}; (1) to jest sloučenou pravděpodobnost, že stav kodéru S_t v čase t je m a je přijat soubor Yf = {yi,..., kanálových výstupů. To jsou požadované pravděpodobnosti vynásobené konstantou P{yj^L}, která je rovná pravděpodobnosti přijetí souboru {yi, · · ·, Ul} kanálových výstupů.

Definujme nyní prvky matice jako r_ř(z, j) = P{stav j v čase t; y_t | stav i v čase t - 1}.

Matice r_ř je vypočtena jako funkce kanálové přechodové pravděpodobnosti R(Y_t,X), pravděpodobnosti p_t(m/m'), že kodér provede přechod ze stavu m' do stavu m v čase t a pravděpodobnosti q_t(X/m', m), že výstupní symbol kodéru je X za předpokladu, že předchozí stav kodéru byl m¹ a jeho současný stav je • ·· ·

m. Speciálně, každý prvek T_ř je vypočten sečtením přes všechny možné výstupy X kodéru podle následujícího vzorce:

7_ř(m', m) = ^p^m/m^q^X/m', m)R(Y_t, X). (2) x

\ MAP dekodér vypočítává L těchto matic, jednu pro každou mřížovou etapu. Matice jsou vytvořeny z přijatých výstupních . __________________________symbolů v závislosti na povaze, mřížových .větví daného kódu_____

Nyní definujme M společných pravděpodobnostních prvků řádkového vektoru at jako &t(j) = P{stav j v čase t; yi,...,y_t} (3) a M podmíněných pravděpodobnostních prvků sloupcového vektoru jako = P{yt+1, .yL | stav j v čase t} (4) pro j = 0,1,..., (Μ — 1), kde M j epočet kódovaných stavů. (Povšimněme si, ža matice a vektory jsou zde označeny s využitím tučného písma.

Kroky MAP dekódovacího algoritmu jsou následující:

(i) Vypočtou se «i,..., «£ následující přímou rekurzí:

= <*ί-1Γ_ί? t= 1,..., L. (5) (ii) Vypočtou se β_γ,... ,β^γ následující zpětnou rekurzí:

fit — ^t+lfit+P

(iii) Vypočtou se prvky X_t jako:

A_ř (z) = pro všechna z, t = 1,..., L. (7) (iv)· Naleznouse Odpovrdaj ícr hledané“hOdnotyrNapříklaTl^”chť A³t je množina stavů St = {S}, St²,..., S^^m} taková, že ý-tý prvek St, označený S³t, je roven nule. Pro konvenční nerekurzivní trellis kód platí, že S³ = d³, j-tý datový bit v čase t.

Slabé výstupní rozhodnutí dekodéru je proto

P{dl = ο|κ/} = —* ς λ,Η.

f SteAi kde P{yj^L} = Σ,πι Az,(m) a m je index, ktrý odpovídá stavu s_t.

Silné rozhodnutí dekodéru neboli dekódovaný výstupní bit je získán použitím P{d³ _t = OlV^} na následující rozhodovací pravidlo d^J _t =0 >

ΡΜ=0|^} 1;

<

> d³ _t ' = 1 • «··· * ·· 4····· ·· · ·····> · « e e e e ®* • 9 ♦ · ······ · · · ®·

4·· · ··· ···· ··9 to jest jestliže P{d^Jt — 0|Yi^L} > potom di' = 0 a jestliže P{d^]t = OjYf} < |, potom d^]t = 1, jinak se do d^]t náhodně dosadí hodnota 0 nebo 1.

Jako jiný příklad pro související hodnotu v kroku (iv) uvedeném výše je možno definovat matici pravděpodobností at, jejíž prvky jsou definovány následujícím předpisem:

«^(m) = P{S_t_i = i; S_t = j; = ¢^-1(2)7,(2,7¾ (7)

Tyto pravděpodobnosti jsou užitečné v případě, kdy je požadováno určit a posteriori pravděpodobnosti výstupních bitů kodéru.

Ve standardní aplikaci MAP dekódovacího algoritmu je přímá rekurze inicializována vektorem «o = (1,0,..., 0) a zpětná rekurze je inicializována vektorem β_Ε = (1,0,..., 0)^T Sq = 0 Sl = 0. Tyto výchozí podmínky jsou založeny na předpokladu, že výchozí stav kodéru je Sq = 0 a jeho koncový stav je Sl = 0.

Jedno provedení cirkulárního MAP dekodéru určuje pravděpodobnostní rozdělení výchozího stavu řešením problému vlastní hodnoty následujícím způsobem: Nechť a_t, P_t, Γ, a X_t představují totéž jako bylo uvedeno výše s tím rozdílem, že výchozí hodnoty ao /^zjsou určeny takto:

P_L je rovno sloupcovému vektoru (111... 1)^T.

otQ je neznámá proměnná (vektor).

Potom, (i) Vypočte se Γ, pro t = 1,2,... ,L podle rovnice (2).

• · · ·

Najde se největší vlastní hodnota maticového součinu Γ1Γ2 ... Γχ. Odpovídající vlastní vektor se normalizuje ta, aby součet jeho složek byl roven jedné. Tento vektor je řešení pro oq. Vlastní hodnota je P{Yj^L}.

(ii) Po sobě jdoucí a_t se vypočítají přímou rekurzí, která je definována rovnicí (5).

(iv) Vycházejíce z inicializovaného způsobem popsaným výše se vypočítají zpětnou rekurzí, která je definována rovnicí (6)^-. “

Způsobem popsaným rovnicí (7) se vypočítají A_ř stejně tak jako další požadované veličiny jako jsou například slabá výstupní rozhodnutí P{d³ _t = 0^} nebo matice pravděpodobností a_t popsané výše.

Přihlašovatelé ukázali, že neznámá proměnná «o vyhovuje maticové rovnici _ 00Γ1Γ2 . ·. Γχ ” P {h^L}

Z faktu, že tento vzorec vyjadřuje vztah mezi pravděpodobnostmi vyplývá, že součin matic na pravé straně rovnosti má svou největší vlastní hodnotu rovnou P a odpovídající vlastní vektor musí být vektor pravděpodobností.

Vycházejíce z počátečního = (111... l)^r, rovnice (6) dává Pl-i· Opakované použití této zpětné rekurze tedy dává všechny βι· Jakmile je známo ao a je dosazeno do všechnay výpočty cirkulárního MAP dekodéru podle předkládaného vynálezu se provádějí v souladu s konvenčním MAP dekódovacím algoritmem.

Obr. 4 je zjednodušené blokové schéma znázorňující cirku17 • · · · • · ···· lární MAP dekodér 110 pro dokódování samoopravných trellis kódů s koncovými bity podle metody vlastního vektoru, která byla popsána výše. Dekodér 110 zahrnuje zařízení 112 pro výpočet r_t, které vypočítává jakožto funkci kanálového výstupu y_t. Zařízení pro výpočet dostává jako vstup z paměti 130 následující hodnoty: přechodovou kanálovou pravděpodobnost R(Y_t,X), pravděpodobnost že kodér provede přechod ze stavu m' do stavu m v čase t a pravděpodobnost g_ť(Xj, m', m), že výstupní symbol kodéru je X za předpokladu, že předchozí stav kod=ru byl m! a jeho současný stav je m. Zařízaní pro výpočet r_ř vypočítává každý prvek sčítáním přes všechny možné výstupy X kodéru na základě rovnice (2).

Vypočtené hodnoty se převedou do zařízení 114 pro násobení matic ΓχΓ₂ ... Γχ, s využitím jednotlkové matice 116, například získané z paměti, přepínače 118 a zpožďovacího obvodu 120. V čase t = 1 se jednotková matice přivede jako jeden ze vstupů zařízení pro výpočet maticového součinu. V následujících okamžicích t = 2 až t = L je maticový součin Π_ζ·Ζι Γϊ převáděn zpět přes zpožďovací obvod do zařízení pro výpočet maticového součinu. Potom, v čase t = L je výsledná matice převedena prostřednictvím přepínače 121 do zařízení 122 pro výpočet normalizovaného vlastního vektoru, které provádí výpočet normalizovaného vlastního vektoru, odpovídajícího největšímu vlastnímu číslu maticového součinu, který byl tomuto zařízení přiveden jako vstup. Pokud je takto inicializováno a₀, to jest je rovno vypočtenému vlastnímu vektoru, následující vektory a_t se určí rekurzivně na základě rovnice (5) v zařízení 124 pro výpočet maticového součinu s využitím zpožďovacího obvodu 126 a přepínacího obvodu 128, jak je ukázáno na obrázku. Odpovídající hodnoty r_ř jsou při tom získávány z paměti 130 a výsledné hodnoty a_t jsou zpětně uchovávány v paměti 130. .....

4» • · · ·

44

4 4444 ··

44444 444

Hodnoty jsou určeny v zařízení 132 pro výpočet maticového součinu s využitím přepínače 134 a zpožďovacího obvodu 136 na základě rovnice (6). Potom jsou vypočteny pravděpodobnosti A_ť, vycházejíce při tom z hodnot a_t a v zařízení 140 pro výpočet součinu po složkách na základě rovnice (7). Hodnoty A/ jsou převedeny do zařízení 150 pro výpočet pravděpodobnosti hodnoty dekódovaného bitu, které určuje pravděpodobnost, že j-tý dekódovaný bit v čase t, to jest d³, je roven nule. Tato pravděpodobnost je předána do zařízení 152 pro provádění prahových rozhodnutí, které implementuje následující rozhodovací pravidlo: jestliže pravděpodobnost, určená zařízením 150 pro výpočet pravděpodobnosti hodnoty dekódovaného bitu je větší než pak je rozhodnuto, že dekódovaný bit je roven nule, jestliže pravděpodobnost je menší než |, pak je rozhodnuto, že dekódovaný bit je jedna a nakonec v případě, že určená pravděpodobnost je rovna hodnota dekódovaného bitu je náhodně zvolena z hodnot 0 a 1. Výstup zařízení pro provádění prahových rozhodnutí dává výstupní bit dekodéru v čase i.

Na obr. 4 je také znázorněno, že pravděpodobnost, že dekódovaný bit se rovná nule, to jest P{d{ = 0|V/}., je poskytována jako slabý výstup funkčnímu bloku 154 k výpočtu funkce této pravděpodobnosti, to jest hodnoty f(P{d³ _t = 0|Κ/}), jako je například hodnota . !--P{4 = (W} poměr pravděpodobnosti =-----1-----C—L

P(dž=0|l·?} která představuje slabé výstupní rozhodnutí dekodéru. Jinou užitečnou funkcí pravděpodobnosti P{d³ _t = 0|Κ/} je

log poměr pravděpodobností = log i-p{dí = o|y?}]

P{4 = 0|Y/} j'

Alternativně může být užitečnou funkcí pro blok 154 prostě identická funkce, takže slabý výstup je přímo P{d³ _t =

Alternativní provedení cirkulárního MAP dekodéru určuje stavové pravděpodobnostní rozložení rekurzivní metodou. Speciálně v jednom provedení (dynamická konvergenční metoda), rekurze pokračuje dokud není zjištěna koncergence dokodéru. V této rekurzivní metodě (nebo dynamické rekurzivní metodě) jsou kroky (ii) a (iii) výše uvedené metody založené na vlastním vektoru nahrazeny následujícím způsobem:

(ii.a) Vycházejíce z počátečního ao rovného (1/M,..., 1/M), kde M je počet stavů v mříži (trellis), se počítá přímá rekurze Λ-krát. Výsledek se normalizuje tak aby součet prvků každého nového a_t byl roven jedné. Výsledkem je všech L vektorů a_t.

(ii.b) Nechť a₀ se rovná αχ, z předchozího kroku a, začínajíce v t = 1, vypočítá se prvních L_Wmina_t pravděpodobnostních vektorů znova.

To znamená, že se vypočte

M~1 i=0 pro m = 0,1,..., Μ - 1 a t = 1, 2,..., L_Wmin, kde L_Wmin je vhodný minimální počet mřížových etap. Normalizuje se jako předtím. Uchová se pouze nejnovější množina L hodnot a nale20 • · · · • ·· ·· ···· e e « # e ς e » ® · • · · · · · · • · · · ·♦···· zených rekurzí v krocích (ii.a) a (ii.b) a az,_Wm. nalezené předtím v kroku (ii.a).

(ii.c) Porovnají se <*L_Wmin z kroku (ii.b) s předtím nalezenou množinou z kroku (ii.a). Jestliže M odpovídajících prvků nového a starého ar se nachází v jistém tolerančním rozmezí, pak se pokračuje krokem (iv), tak jak byl popsán výše, zatímco v opač ném případě se pokračuje krokem (ii.d).

, - -----------(ii.d) Položí se t — t + 1 a vy p o čte' se a_t~= _ i Γ_ζ, který se normalizuje stejným způsobem jako výše. Ponechá se pouze nejnovější množina L vypočtených hodnot a a at nalezené dříve v kroku (ii.a).

(ii.e) Nové hodnoty a_t se porovnají s množinou nalezenou dříve. Jestliže M nových a starých se nachází v jistém tolerančním rozmezí, pokračuje se krokem (iv). V opačném případě se pokračuje krokem (ii.d) pokud dva nejnovější vektory nesouhlasí vzhledem k dané toleranční oblasti a jestliže počet rekurzí nepřekročil stanovené maximum (typicky 2L), zatímco jinak se pokračuje v kroku (iv).

Tato metoda potom pokračuje kroky (iv) a (v), popsanými výše při popisu metody využívající vlastní vektor a vytvoří slabá výstupní rozhodnutí a dekódované výstupní bity cirkulárního MAP dekodéru.

. V jiném alternativním provedení cirkulárního MAP dekodéru, které je popsáno v U.S. patentové přihlášce č. (RD-24,923), je rekurzivní metoda, popsaná výše, modifikována tak, že dekodér musí provést pouze předem daný, pevný počet mřížových etap podruhé, to jest s předem danou hloubkou opakování. To je výhodné z implementačních důvodů^ neboť počet výpočtů, • · · · potřebných pro dekódování je tentýž jako je týž pro každý zakódovaný blok zprávy. Z toho pak vyplývá, že složitost hardwaru i softwaru je snížena.

Jednou z metod, jak odhadnout požadovanou hloubku opakování pro MAP dekódování u konvolučních kódu s koncovými bity je určit ji z experimentů s hardwarem a softwarem tak, že se implementuje cirkulární MAP dekodér s proměnnou hloubkou opakování a jsou prováděny experimenty, ve kterých se_měn poměr bitových chyb (BET) u dekódovaných bitů ve srovnání s hodnotou Eb/No pro postupně se zmenšující hodnoty hloubky opakování. Tím se určí minimální hloubka opakování dekodéru, která poskytuje minimální pravděpodobnost bitových chyb dekódovaných bitů pro určenou hodnotu Eb/No a to tak, že je to hodnota, u níž další vzrůst hloubky opakování již nesnižuje pravděpodobnost chyb.

Jestliže poměr bitových chyb dekódovaných bitů, který je větší než minimum dosažitelné při specifikovaném Eb/No, je přípustný, je možno redukovat počet mřížových etap provedených cirkulárním MAP dekodérem. Speciálně hledání hloubky opakování, tak jak bylo popsáno výše, může být prostě ukončeno jestliže je dosaženo požadované střední pravděpodobnosti chyb.

Jiný způsob určení hloubky opakování pro daný kód je na základě používání distančních vlastností kódu. Za tímto účelem je třeba definovat dvě odlišné rozhodovací hloubky dekodéru. Výraz správná cesta” zde bude používán pro posloupnost stavů nebo cestu skrz mříž, ktrá vychází z kódování bloku datových bitů. Výraz ”nesprávná podmnožina uzlu” znamená množinu všech nesprávných (mřížových) větví, vycházejících z uzlu na správné cestě a nebo z jeho následníků. Obě rozhodovací délky definované níže závisí na konvolučním kodéru.

• ·· ·

Rozhodovací hloubka je definována následujícím způsobím (i) Přímá rozhodovací hloubka pro e-chybovou korekci, označená jako LF(e), je definována jako první hloubka v mříži, ve které jsou všechny cesty v nesprávné podmnožině výchozího vrcholu na správné cestě, bez ohledu na to, zda se stýká se správnou cestou nebo ne, leží ve více než v Hammingově vzdálenosti 2e od správné cesty. Význam LF(e) je v tom, že jestliže existuje e nebo méňě čhýb před iniciáíním vrcholem a je známo, že zde začíná kó- dování, pak dekodér musí dekódovat správně. Formální tabelace přímých rozhodovacích hloubek pro konvoluční kódy podali J.B. Anderson a K. Balachandran v ”Decision Depths of Convolutional Codes”, IEEE Transactions on Information Theory, svazek. IT-35, str. 455-459, březen 1989. Množství vlastností LF(e) bylo popsáno v uvedené referenci a také v článku J.B. Anderson a S.

Mohan v Source and Channel Coding - An Algorithmic Approach, Kluwer Academie Publishers, Norwell, MA, 1991. Hlavní mezi těmito vlastnostmi je pozorování, že existuje jednoducá lineární relace mezi LF a e. Například pro kódy s poměrem 1/2 je LF rovno přibližně 9,08e.

(ii) V následujícím kroku se definuje nesloučená rozhodovací hloubka pro e-chybovou korekci, LU(e), která je rovna první hloubce v mříži, ve které všechny cesty v mříži ve které všechny cesty v mříži, které se nikdy nedotkly správné cesty, leží ve více než v Hammingově vzdálenosti 2e vzdáleny od správné cesty.

Význam LU(é) pro cirkulární MAP dekódování se slabými rozhodnutími je v tom, že pravděpodobnost identifikace stavu na skutečně vyslané cestě je vysoká poté, co dekodér provede LU(e) mřížových etap. Proto je minimální hloubka opakování pro cirkulární MAP dekódování rovna LU(e). Výpočty hloibky LU(e) • ···· ukazují, že je vždy větší než LF(e), ale vyhovuje stejným aproximačním zákonům. Z toho plyne, že minimální hloubka opakování může být určena jako přímá rozhodovací hloubka LF(e), pokud pro kód není známa nesloučená rozhodovací hloubka.

Nalezením minimální nesloučené rozhodovací hloubky pro daný kodér se nalezne nejmenší počet mřížových etap, které musí být provedeny praktickým cirkulárním dekodérem, který generuje slabá výstupní rozhodnutí. Algoritmus pro nalezení LF(e),. přímé rozhodovací hloubky, podali J.B. Anderson a K. Balachandran v Decision Depths of Convolutional Codes”, citovaném výše. Pro nalezení LU(e) je třeba provést:

(i) Rozšířit mříž kódu zleva doprava, začínajíce ze všech uzlů mříže součacně s výjimkou nulového stavu.

(ii) V každé úrovni vynechat každou cestu, která se spojuje se správnou (výhradně nulovou) cestou, ale nerozšiřovat žádnou cestu, vycházející ze správného (nulového) stavového uzlu.

(iii) V úrovni k se nalezne nejmenší Hammingova vzdálenost nebo váha mezi cestami, končícími v uzlech této úrovně.

(iv) Jestliže tato nejmenší vzdálenost překračuje 2e, ukonči výpočet, jinak je LU(e) — k.

Jak bylo popsáno v U.S. patentové přihlášce č. (RD-29,923), experimenty provedené pomocí počítačové simulace vedly ke dvěma neočekávaným výsledkům:

(1) opakované zpracování zlepšuje výkonnost dekodéru a (2) použití hloubky opakování LU(e) 4- LF(e) = 2LF(e) zlepšuje výkonnost dekodéru významným způsobem.

Proto výhodné provedení cirkulárního MAP dekódovacího algoritmu založeného na rekurzi zahrnuje následující kroky:

(i) Vypočtení Γ< pro t = 1, 2,..., A vycházejíce z rovnice (2).

(ii) Vycházejíce z počátečního «o rovného (1/M,... ,1/M, kde M je počet stavů v mříži, provést přímou rekurzi podle rovnice (5) (L + L_w)-krát pro u = 1, 2,..., (L + L_w), kde L_w je hloubka opakování dekodéru. Index t v mříži má hodnoty ((w — l)modL) +1. Jestliže dekodér provádí opakování okolo posloupnosti symbolů přijaté z kanálu, a/, je zpracováno jako ao- Výsledky se normalizují tak, že prvky každého nového a_t dávají v součtu jednotku. Ponechá se L nej novějších vektorů a, nalezených touto rekurzí.

(iii) Počínajíce od výchozího rovného (1,..., 1)^T, provede se zpětná rekurze podle rovnice (6) (L + Lw)-krát pro u = 1,2,...,(/, + Lyj). Index t úrovně v mříži má hodnoty L — (wmodL). Jestliže dekodér provádí opakování kolem přijaté posloupnosti, je použito jako β^Ε+γ a Γι je použito jako Γ£+ι při výpočtu nového Výsledky se normalizují tak, že prvky každého nového a_t dávají v součtu jednotku. Opět se ponechá L nejnovějších vektorů a, nalezených touto rekurzí.

Následující krok této výhodné rekurzivní metody je stejný jako krok (v) popsaný výše při popisu metody s vlastním vektorem a vytváží slabá rozhodnutí a dekódované bity, představující výstup cirkulárního MAP dekodéru.

Obr. 5 je zjednodušené blokové schéma znázorňující cirkulární MAP dekodér 180 podle výhodného provedení předkládaného vynálezu. Dekodér 180 zahrnuje zařízení 182 pro výpočet hodnoty T_ř, které vypočítává T_ť jako funkci kanálových výstupů y_t- Kanálové výstupy yi,... ,yL jsou předány zařízení pro výpočet Γ\ prostřednictvím přepínače 184. Pokud je přepínač v dolní poloze, L kanálových výstupních symbolů je přivedeno do za25

• · řízení 182 pro výpočet hodnoty a posuvného registru 186 v týž okamžik. Potom je přepínač 184 přepnut do horní polohy, což umožní, aby posuvný registr přesunul prvních L_w přijatých symbolů znovu do zařízení pro výpočet I\, to jest provede cirkulární zpracování. Zařízení pro výpočet dostává jako vstupy z paměti 130 kanálové přechodové pravděpodobnosti R(Y_tyX)_ypravděpodobnosti p_t(m\m'), že kodér provede přechod ze stavu m' do stavu m v čase t apravděpodobnosti q_t(X\m'že výstupní symbol kodéru je X za předpokladu, že předchozí stav je. m' a současný stav je m. Zařízení pro výpočet určuje každý prvek Γ\ sečtením přes všechny možné hodnoty X výstupu kodéru na základě rovnice (2).

Vypočtené hodnoty T_ř se předají zařízení 190 pro výpočet maticového součinu, které násobí matici Γ\ s maticí a_ť_i, kteroé dostane rekurzivně přes zpožďovací zařízení 192 a demultiplexor 194. Ovládací signál CNTRL1 způsobí, že demultiplexor 194 zvolí v čase t = 1 αθ z paměti 196 jako jeden ze vstupů pro zařízení 190 pro výpočet maticového součinu. Pokud je 2 < t < L, pak ovládací signál CNTRL1 způsobí, že demultiplexor 194 zvolí a_t_i ze zpožďovacího zařízení 192 jako jeden ze vstupů pro zařízení 190 pro výpočet maticového součinu. Hodnoty T_ť a ajsou uchovávány v paměti 196 požadovaným způsobem.

Vektory fi_t jsou vypočítávány rekurzivně pro zařízení 200 pro výpočet maticového součinu přes zpožďovací zařízení 202 a demultiplexor 204. Ovládací signál CNTRL2 způsobí, že demultiplexor 204 zvolí v čase t = L — 1 @_L z paměti 196 jako jeden ze vstupů pro zařízení 200 pro výpočet maticového součinu. Pokud je L — 2 > t > 1, pak ovládací signál CNTRL2 způsobí, že demultiplexor 204 zvolí fi_t+1 ze zpožďovacího zařízení 102 jako jeden ze vstupů pro zařízení 200 pro výpočet maticového součinu. Výsledné hodnoty fi_t jsou násobeny hodnotami a_t, získanými «9 β

z paměti 196, v zařízení 206 pro násobení vektorů po prvcích, čímž se vypočtou pravděpodobnosti A_t, jak bylo popsáno výše. Stejným způsobem jako bylo popsáno výše při popisu obr. 4 se hodnoty blambdat použijí v zařízení 150 pro výpočet pravděpodobnosti hodnoty dekódovaného bitu, jehož výstup se přivádí do zařízení 152 pro provádění prahového rozhodnutí, které vytvoří výsledné výstupní bity dekodéru.

Na obr. 5 je také znázorněno, že podmíněná pravděpodobnost’ze dekódovaný bit je roven nule (P{ďi = 0|^}) je předávána slabému výstupnímu funkčnímu bloku 154, který vypočítává funkci této pravděpodobnosti, to jest hodnotu f(P{dÍ = 0|y/}) takovou, jako je například poměr pravděpodobností = i - P{di = o|Y,Ň p{4 = o|y/} jako slabé výstupní rozhodnutí dekodéru. Jiná užitečná funkce P{d³ _t = 0|l?} je log poměr pravděpodobností = log fi-PK = o|y?}] I p{dž = (W} J

Jiná užitečná funkce, kterou může vapočítávat blok 154, je identická funkce, takže slabým výstupem je pak přímo P{d{ = o|Ů}·

Podle předkládaného vynálezu je možno zvýšit poměr paralelního zřetězeného kódovacího schématu využívajícího nerekurzivní systematický kód s koncovými bity vynecháním zvolených bitů ve složeném kódovém slově, vytvořeném zařízením pro for27 ···· ·· ···· mátování složeného kódového slova podle vzoru výhodně zvoleného před přenášením bitů složeného kódového slova přenosovým kanálem. Tato technika je známa jako puncturing. Tento vzor je také znám dekodéru. Následující jednoduchý krok, prováděný převodníkem přijatého složeného kódového slova na složkové kódové slovo provádí požadovanou operaci dekodéru: převodník přijatého složeného kódového slova na složkové kódové slovo pouze vkládá neurtální hodnoty za každý známý ” punkturovaný” bit v průběhu vytváření přijatého složkového kódového________ slova. Například neutrální hodnota je v případě antipodálního signalizování nad aditivním bílým Gaussovským čumovým kanálem. Zbytek činnosti dekodéru probíhá tak, jak bylo popsáno výše.

Rozšířenou představou bylo, že nerekurzivní systematické konvoluční kódy by nebyly užitečné jako složkové kódy v paralelních zřetězených kódovacích schématech, a to vzhledem k lepším distančním vlastnostem RSC kódů pro relativně velké datové bloky, jak bylo popsáno například v S. Benedetto a G. Montorsi, ” Design of Parallel Concatenated Convolutional Codes”, IEEE Transactions on Communications, vyjde. Avšak, jak bylo popsáno výše, přihlašovatelé zjistili, že minimální vzdálenost v NSC je méně citlivá na délku datového bloku a proto mohou být tyto kódy výhodně používány v komunikačních systémech, ktré přenášejí krátké bloky dat v přenosových kanálech s vysokou úrovní šumu. Navíc přihlašovatelé zjistili, že použití kódů s koncovými bity řeší problém ukončení posloupností vstupních dat v turbo kódech. Použití konvolučních kódů s koncovými bity jako složkových kódů v paralelních zřetězených kódovacích schématech nebylo dosud navrženo. Proto předkládaný vynález podává paralelní zřetězené nerekurzivní systematické konvoluční schéma s koncovými bity, ve kterém dekodér zahrnuje cirkulární MAP dekodér pro dekódování složkových konvolučních kódů s koncovými bity pro dosažení lepší výkonnosti než v konvenčních turbo kódovacích schématech v případě krátkých bloků dat, pokud je měřena v poměru bitových chyb (BET) vzhledem k poměru signál/šum.

Zatímco bylo ukázáno a popsáno výhodné provedení předkládaného vynálezu, je zřejmé, že takové provedení bylo podáno pouze jako příklad. Odborníkovi je zřejmé, že mohou být provedenypočetné změny, obměny a nahrazení, aniž by se řešení odchýlilo od předmětu zde předkládaného vynálezu. V souladu s tím je předmět předkládaného vynálezu omezen pouze duchem a rozsahem přiložených patentových nároků.

Zastupuje:

JUDr. Otakar Švorčík

Claims

PATENTOVÉ NÁROKY

1. Způsob paralelního zřetězeného konvolučního kódování, zahrnující následující kroky:

přivedení bloku datových bitů do paralelního zřetězeného kodéru, zahrnujícího N složkových kodérů a N — 1 prokládacích zařízení spojených do paralelního zřetězení;

zakódování bloku datových bitů v prvním složkovém kodéru použitím nerekurzivního systematického konvolučního kódu s koncovými bity na uvedený blok datových bitů a z toho vyplývající vytvoření odpovídajícího prvního složkového kódového slova, zahrnujícího datové bity a paritní bity;

vytvoření permutovaného bloku datových bitů překrytím uvedeného bloku datových bitů;

zakódování výsledného permutovaného bloku datových bitů v následujícím složkovém kodéru použitím nerekurzivního systematického konvolučního kódu na uvedený permutovaný blok datových bitů a z toho vyplývající vytvoření odpovídajícího druhého složkového kódového slova zahrnujícího datové bity a paritní bity;

opakování kroků prokládání a kódování výsledného permutovaného bloku datových bitů ve zbývajících N — 2 prokládacích zařízeních a zbývajících N — 2 složkových kodérech a z toho vyplývající vytvoření odpovídajících složkových kódových slov zahrnujících datové bity a paritní bity; a formátování bitů složkových kódových slov do výsledného složeného kódového slova.

I • ·
2. Způsob podle nároku 1 ve kterém formátovací krok je proveden tak, že složené kódové slovo zahrnuje pouze jeden výskyt každého bitu z bloku datových bitů.
3. Způsob podle nároku 1 ve kterém je formátovací krok proveden tak, že složené kódové slovo obsahuje pouze vybrané bity z bitů obsažených ve složkových kódových slovech a výběr je * proveden podle předem zvoleného vzoru.

- -------- --------------------4. Způsob dekódování -paralelních zřetězených konvolučních kódů, zahrnující následující kroky:

příjem z přenosového kanálu složeného kódového slova, které zahrnuje formátovaný soubot bitů z množiny (N) složkových kódových slov, které byly generovány použitím nerekurzivního systematického konvolučního kódu s koncovými bity na blok datových bitů v paralelním zřetězeném kodéru, vytvoření přijatých složkových kódových slov z přijatého složeného kódového slova, přičemž jednotlivá přijatá složková kódová slova jsou přijata jim odpovídajícími složkovými dekodéry z množiny N složkových dekodérů složeného dekodéru a každý složkový dekodér zároveň přijímá množinu hodnot a priori slabých rozhodnutí pro hodnoty datových bitů;

dekódování přijatých složkových kódových slov v iteračním procesu pomocí N složkových dekodérů a N — 1 prokládacích zařízení pro vytvoření slabých výstupních rozhodnutí ze složeného dekodéru, kde každý z N složkových dekodérů vytváří slabá rozhodnutí pro každý datový bit v datovém bloku v pořadí zakódovaném odpovídajícím složkovým kodérem, kde každé z N — 1 prokládacích zařízení prokládá slabá rozhodnutí z předchozího složkového dekodéru a na základě toho poskytuje permutovaný blok slabé informace následujícímu složkovému dekodéru, kde « φφφφ • 99 9 • « φ Φ » φ Φ Φ Φ Φ

Φ Φ · Φ · Φ φφφ φ ΦΦΦΦΦΦΦ Φ Φ ·' množina a priori slabých rozhodnutí pro první z N složkových dekodérů je vypočtena za předpokladu, že hodnoty datových bitů jsou stejně pravděpodobné v první iteraci a poté zahrnuje první funkci informace o slabých rozhodnutích, kde první funkce informace o slabých rozhodnutích je přivedena zpět z 7V-tého složkového dekodéru přes první zařízení pro odstranění prokládání, které zahrnuje N — 1 zařízení pro odstranění prokládání, odpovídající N — l zařízením pro prokládám a kde N — 1 zařízení pro odstranění prokládání z nichž se skládá první zařízení- pro odstranění prokládání je aplikováno v opačném pořadí vzhledem k pořadí aplikace N — l prokládacích zařízení, kde množina a priori slabých rozhodnutí pro každý další složkový dekodér zahrnuje první funkci slabých rozhodnutí z předcházejícího sekvenčního složkového dekodéru; a odstranění prokládání v druhém zařízení pro odstranění prokládání pro vytvoření druhé funkce slabých výstupních rozhodnutí z TV-tého složkového dekodéru jako slabé výstupní rozhodnutí složeného dekodéru za použití N — 1 zařízení k odstranění prokládání odpovídajících N — l prokládacím zařízením, přičemž TV — 1 zařízení k odstranění prokládání druhého zařízení k odstranění prokládání je použito v opačném pořadí vzhledem k pořadí aplikace N — 1 prokládacích zařízení.

5. Způsob podle nároku 4, ve kterém počet iterací použití složkových dekodérů, prokládacích zařízení a zařízení k odstranění prokládání je roven předem danému číslu.

6. Způsob podle nároku 4 ve kterém iterace použití složkových dekodérů, prokládacích zařízení a zařízení k odstranění prokládání pokračuje tak dlouho, dokud není zjištěna konvergence dekodéru, pakliže počet uvedených iterací je menší než maximální počet; v opačném případě se dekódování ukončí po maximálním počtu iterací, a ve kterém složený dekodér dává sruhou funkci slabých výstupních rozhodnutí z /V-tého složkového dekodéru jako své slabé výstupní rozhodnutí přes druhé zařízení k odstranění prokládání.

7. Způsob podle nároku 4, zahrnující dále krok, implementující rozhodovací pravidlo, kterým se vytváří silné výstupní rozhodnutí jako funkce slabého výstupního rozhodnutí složeného dekodéru.

8. Způsob podle nároku 4, ve kterém některé bity formátovaného souboru bitů jsou vyjmuty podle předem daného vzoru a způsob dekódování dále zahrnuje krok vsunutí neutrálních hodnot na místo vyjmutých bitů při vytváření přijatých složkových kódových slov.

9. Způsob podle nároku 4 ve ktereém dekódovací krok je prováděn N složkovými dekodéry, zahrnujícími cirkulární MAP dekodéry a dekódovací krok zahrnuje řešení problému vlastního vektoru.

10. Způsob podle nároku 4, ve kterém dekódovací krok je prováděn N složkovými dekodéry, zahrnujícími cirkulární MAP dekodéry a dekódovací krok zahrnuje rekurzivní metodu.

11. Způsob pro kódování a dekódování paralelních zřetězených konvolučních kódů, zahrnující následující kroky:

přivedení bloku datových bitů do paralelního zřetězeného kodéru, zahrnujícího N složkových kodérů a N - 1 prokládacích zařízení spojených do paralelního zřetězení;

zakódování bloku datových bitů v prvním složkovém kodéru použitím nerekurzivního systematického konvolučního kódu s • · · ···« ♦ · · • · · · · · · « · · · ·····♦ koncovými bity na uvedený blok datových bitů a z toho vyplývající vytvoření odpovídajícího prvního složkového kódového slova, zahrnujícího datové bity a paritní bity;

vytvoření permutovaného bloku datových bitů překrytím uvedeného bloku datových bitů;

zakódování výsledného permutovaného bloku datových bitů v následujícím složkovém kodéru použitím nerekurzivního systematického konvolučního kódu na uvedený permutovaný blok datových bitů a z toho vyplývající vytvoření odpovídajícího druhého složkového kódového slova zahrnujícího datové bity a paritní bity;

opakování kroků prokládání a kódování výsledného permutovaného bloku datových bitů ve zbývajících N — 2 prokládacích zařízeních a zbývajících N — 2 složkových kodérech a z toho vyplývající vytvoření odpovídajících složkových kódových slov zahrnujících datové bity a paritní bity;

formátování bitů složkových kódových slov do výsledného složeného kódového slova;

vstup složeného kódového slova do přenosového kanálu;

přijetí přijatého složeného kódového slova z přenosového kanálu;

vytvoření přijatých složkových kódových slov z přijatého složeného kódového slova;

přivedením každého z přijatých složkových kódových slov odpovídajícímu z množiny N složkových dekodérů složeného dekodéru, přičemž každý složkový dekodér zároveň přijímá množinu a priori pravděpodobností pro hodnoty datových bitů;

dekódování přijatých složkových kódových slov v iteračním procesu pomocí N složkových dekodérů a N — 1 prokládacích zařízení pro vytvoření slabých výstupních rozhodnutí ze složeného dekodéru, kde každý z N složkových dekodérů vytváří slabá rozhodnutí pro každý datový bit v datovém bloku v pořadí zakódovaném odpovídajícím složkovým kodérem, kde každé z N — 1 prokládacích zařízení prokládá slabá rozhodnutí z předchozího složkového dekodéru a na základě toho poskytuje permutovaný blok slabé informace následujícímu složkovému dekodéru, kde množina a priori slabých rozhodnutí pro první z N složkových dekodérů je vypočtena za předpokladu, že hodnoty datových bitů jsou stejně pravděpodobné v první iteraci a poté zahrnuje první funkci informace o slabých rozhodnutích, kde první funkce informace o slabých rozhodnutích je přivedena zpět z A-tého dekodéru přes první zařízení pro odstranění prokládání, které zahrnuje N — 1 zařízení pro odstranění prokládání, odpovídající N — 1 zařízením pro prokládání a kde N — 1 zařízení pro odstranění prokládání z nichž se skládá první zařízení pro odstranění prokládání je aplikováno v opačném pořadí vzhledem k pořadí aplikace N — 1 prokládacích zařízení, kde množina a priori slabých rozhodnutí pro každý další složkový dekodér zahrnuje první funkci slabých rozhodnutí z předcházejícího sekvenčního složkového dekodéru; a odstranění prokládání v druhém zařízení pro odstranění prokládání pro vytvoření druhé funkce slabých výstupních rozhodnutí z TV-tého složkového dekodéru jako slabé výstupní rozhodnutí složeného dekodéru za použití N — 1 zařízení k odstranění prokládání odpovídajících TV —1 prokládacím zařízením, přičemž N — 1 zařízení k odstranění prokládání druhého zařízení k odstranění prokládání je použito v opačném pořadí vzhledem k pořadí aplikace N — 1 prokládacích zařízení.

12. Způsob podle nároku 11 ve kterém formátovací krok je proveden tak, že složené kódové slovo zahrnuje pouze jeden výskyt každého bitu z bloku datových bitů.

13. Způsob podle nároku 11 ve kterém je formátovací krok proveden tak, že složené kódové slovo obsahuje pouze vybrané bity z bitů obsažených ve složkových kódových slovech a výběr je proveden podle předem zvoleného vzoru.

14. Způsob podle nároku 11, ve kterém počet iterací použití složkových dekodérů, prokládacích zařízení a zařízení k odstranění prokládání je roven předem danému číslu.

15. Způsob podle nároku 11 ve kterém iterace použití složkových dekodérů, prokládacích zařízení a zařízení k odstranění prokládání pokračuje tak· dlouho, dokud není zjištěna konvergence dekodéru, pakliže počet uvedených iterací je menší než maximální počet; v opačném případě se dekódování ukončí po maximálním počtu iterací, a ve kterém složený dekodér dává sruhou funkci slabých výstupních rozhodnutí z TV-tého složkového dekodéru jako své slabé výstupní rozhodnutí přes druhé zařízení k odstranění prokládání.

16. Způsob podle nároku 11, zahrnující dále krok, implementující rozhodovací pravidlo, kterým se vytváří silné výstupní rozhodnutí jako funkce slabého výstupního rozhodnutí složeného dekodéru.

17. Způsob podle nároku 11 ve ktereém dekódovací krok je prováděn N složkovými dekodéry, zahrnujícími cirkulární MAP dekodéry a dekódovací krok zahrnuje řešení problému vlastního vektoru.

• · · *

18. Způsob podle nároku 11, ve kterém dekódovací krok je prováděn N složkovými dekodéry, zahrnujícími cirkulární MAP dekodéry a dekódovací krok zahrnuje rekurzivní metodu.

19. Způsob podle nároku 11, ve kterém formátovací krok dále zahrnuje vyjmutí vybraných bitů z bitů složkových kódových slov, obsažených ve složeném kódovém slově, podle předem daného vzoru a způsob dekódování dále zahrnuje krok vsunutí neutrálních hodnot na místo vyjmutých bitů při vytváření přijatých složkových kódových slov.

20. Paralelní zřetězený kodér, zahrnující:

množinu N složkových kodérů a množinu N — 1 zařízení pro prokládání spojených do paralelního zřetězení a systematicky používajících nerekurzivní systematické konvoluční kódy s koncovými bity na blok datových bitů a vytvářejících tím složková kódová slovo zahrnující datové bity a paritní bity; a formátovací zařízení složeného slova pro formátování souboru bitů složkových kódových slov a následné vytvoření složeného kódového slova.

21. Kodér podle nároku 20, ve kterém formátovací zařízení složeného slova vytváří složené slovo, které zahrnuje pouze jeden výskyt každého bitu z bloku datových bitů.

22. Kodér podle nároku 20, ve kterém složené slovo vytváří složené slovo, které obsahuje pouze vybrané bity z bitů obsažených ve složkových kódových slovech a výběr je proveden podle předem zvoleného vzoru.

23. Složený dekodér pro dekódování paralelních zřetězených konvolučních kódů, obsahující:

• 99 9 ··

9 9 9 zařízení pro konverzi složeného kódového slova na složková kódová slova, které přijímá z přenosového kanálu složené kódové slovo, které zahrnuje zvolené bity z množiny N složkových kódových slov, které byly generovány použitím nerekurzivního systematického konvolučního kódu s koncovými bity na blok datových bitů v paralelním zřetězeném kodéru, a vytváří z něho N odpovídajících přijatých složkových kódových slov;

_____množinu (JN)L složkových dekodérů, zPlUí^á· ze zařízení pro konverzi složeného kódového slova na složková kódová slova odpovídající přijaté složkové kódové slovo a každý dekodér zároveň přijímá množinu hodnot a priori slabých rozhodnutí pro hodnoty datových bitů a každý z N složkových dekodérů vytváří slabá rozhodnutí pro každý datový bit v datovém bloku v pořadí zakódovaném odpovídajícím složkovým kodérem paralelního zřetězeného kodéru;

množinu N — 1 prokládacích zařízení, z nichž každé provádí prokládání slabých rozhodnutí z předchozího složkového dekodéru a na základě toho poskytuje permutovaný blok slabé informace následujícímu složkovému dekodéru, a přijatá kódová slova jsou dekódována v iteračním procesu, procázejíce přes N složkových dekodérů a N — 1 prokládacích zařízení, čímž se vytvoří slabá výstupní rozhodnutí složeného dekodéru;

první zařízení pro odstranění prokládání, které zahrnuje TV — 1 zařízení pro odstranění prokládání, odpovídajících N — 1 zařízením pro prokládání a kde N — 1 zařízení pro odstranění prokládání, z nichž se skládá první zařízení pro odstranění prokládání, je aplikováno v opačném pořadí vzhledem k pořadí aplikace N — 1 prokládání zařízení, přičemž množina a priori slabých rozhodnutí pro první z N složkových dekodérů je vypočtena na základě předpokladu, že hodnoty datových bitů jsou stejně ···· pravděpodobné v první iteraci a poté zahrnuje první funkci informace o slabých rozhodnutích, kde první funkce informace o slabých rozhodnutích je přivedena zpět z 7V-tého dekodéru přes první zařízení pro odstranění prokládání, kde množina a priori slabých rozhodnutí pro každý další složkový dekodér zahrnuje první funkci slabých rozhodnutí z předcházejícího sekvenčního složkového dekodéru; a druhé zařízení pro odstranění prokládány zahrnuj ícý_N — 1 zařízení pro odstranění prokládání, odpovídajících N — 1 zařízením pro prokládání, a N — 1 zařízení k odstranění prokládání druhého zařízení k odstranění prokládání je použito v opačném pořadí vzhledem k pořadí aplikace N — 1 prokládacích zařízení a druhé zařízení pro odstranění prokládání užívá druhou funkci slabých výstupních rozhodnutí 7V-tého složkového dekodéru k vytvoření slabého výstupního rozhodnutí složeného dekodéru.

24. Dekodér podle nároku 23, ve kterém počet iterací použití složkových dekodérů, prokládacích zařízení a zařízení k odstranění prokládání je roven předem danému číslu.

25. Dekodér podle nároku 23 ve kterém iterace použití složkových dekodérů, prokládacích zařízení a zařízení k odstranění prokládání pokračuje tak dlouho, dokud není zjištěna konvergence dekodéru, pakliže počet uvedených iterací je menší než maximální počet; v opačném případě se dekódování ukončí po maximálním počtu iterací, a ve kterém složený dekodér dává druhou funkci slabých výstupních rozhodnutí z 7V-tého složkového dekodéru jako své slabé výstupní rozhodnutí přes druhé zařízení k odstranění prokládání.

26. Dekodér podle nároku 23, zahrnující dále rozhodovací zařízení, implementující rozhodovací pravidlo, kterým se vytváří • · 4 · 4 «' ·· 4 4· 4 • 4 · 4 4 4 44 β · 4 · ·· • 4 4 4 41 · 4444
4 · 4 4 44 silné výstupní rozhodnutí jako funkce slabého výstupního rozhodnutí složeného dekodéru.

27. Způsob podle nároku 23 ve kterém N složkových dekodérů zahrnuje cirkulární MAP dekodéry, které dekódují řešením problému vlastního vektoru.

28. Způsob podle nároku 23 ve kterém N složkových dekodérů zahrnuje cirkulární MAP dekodéry, které dekódují použitím rekurzivní metody.

29. Kódovací a dekódovací systém pro kódování a dekódování paralelních zřetězených konvolučních kódů, zahrnující:

paralelní zřetězený kodér zahrnující množinu N složkových kodérů a množinu N — 1 zařízení pro prokládání spojených do paralelního zřetězení a systematicky používajících nerekurživní systematické konvoluční kódy s koncovými bity— na blok datových bitů a na různé permutace bloku datových bitů a vytvářejících tím složková kódová slovo zahrnující datové bita a paritní bity;

formátovací zařízení složeného slova pro formátování souboru bitů složkových kódových slov a následné vytvoření složeného kódového slova;

zařízení pro konverzi složeného kódového slova na složková kódová slova, které přijímá z přenosového kanálu složené kódové slovo a vytváří z něho N odpovídajících přijatých složkových kódových slov;

množinu (A) složkových dekodérů, z nichž každý přijímá ze zařízení pro konverzi složeného kódového slova na složková kódová slova odpovídající přijaté složkové kódové slovo a každý dekodér zároveň přijímá množinu hodnot a priori slabých rozhodnutí pro hodnoty datových bitů a každý z N složkových dekodérů vytváří slabá rozhodnutí pro každý datový bit v datovém bloku v pořadí zakódovaném odpovídajícím složkovým kodérem paralelního zřetězeného kodéru;

množinu N — 1 prokládacích zařízení, z nichž každé provádí prokládání slabých rozhodnutí z předchozího složkového dekodéru a na základě toho poskytuje permutovaný blok slabé informace následujícímu složkovému dekodéru, a přijatá kódová slova jsou dekódována v iteračním procesu, procázejíce přes N složkových dekodérů a N — 1 prokládacích zařízení, čímž se vytvoří slabá výstupní rozhodnutí složeného dekodéru;

první zařízení pro odstranění prokládání, které zahrnuje N — 1 zařízení pro odstranění prokládání, odpovídajících N — 1 zařízením pro prokládání a kde N — 1 zařízení pro odstranění prokládání, z nichž se skládá první zařízení pro odstranění prokládání, je aplikováno v opačném pořadí vzhledem k pořadí aplikace N — 1 prokládání zařízení, přičemž množina a priori slabých rozhodnutí pro první z N složkových dekodérů je vypočtena na základě předpokladu, že hodnoty datových bitů jsou stejně pravděpodobné v první iteraci a poté zahrnuje první funkci informace o slabých rozhodnutích, kde první funkce informace o slabých rozhodnutích je přivedena zpět z TV-tého dekodéru přes první zařízení pro odstranění prokládání, kde množina a priori slabých rozhodnutí pro každý další složkový dekodér zahrnuje první funkci slabých rozhodnutí z předcházejícího sekvenčního složkového dekodéru; a druhé zařízení pro odstranění prokládání, zahrnující N — 1 zařízení pro odstranění prokládání, odpovídajících N — 1 zařízením pro prokládání, a N — 1 zařízení k odstranění prokládání ·· druhého zařízení k odstranění prokládání je použito v opačném pořadí vzhledem k pořadí aplikace N — 1 prokládacích zařízení a druhé zařízení pro odstranění prokládání užívá druhou funkci slabých výstupních rozhodnutí TV-tého složkového dekodéru k vytvoření slabého výstupního rozhodnutí složeného dekodéru.

30. Kódovací a dekódovací systém podle nároku 29, ve kterém formátovací zařízení složeného slova vytváří složené slovo, které zahrnuje pouze jeden výskyt každého bitu z bloku datových bitů.

31. Kódovací a dekódovací systém podle nároku 29, ve kterém složené slovo vytváří složené slovo, které obsahuje pouze vybrané bity z bitů obsažených ve složkových kódových slovech a výběr je proveden podle předem zvoleného vzoru.

32. Kódovací a dekódovací systém podle nároku 29, ve kterém počet iterací použití složkových dekodérů, prokládacích zařízení a zařízení k odstranění prokládání je roven předem danému číslu.

33. Kódovací a dekódovací systém podle nároku 29 ve kterém iterace použití složkových dekodérů, prokládacích zařízení a zařízení k odstranění prokládání pokračuje tak dlouho, dokud není zjištěna konvergence dekodéru, pakliže počet uvedených iterací je menší než maximální počet; v opačném případě se dekódování ukončí po maximálním počtu iterací, a ve kterém složený dekodér dává druhou funkci slabých výstupních rozhodnutí z TV-tého složkového dekodéru jako své slabé výstupní rozhodnutí přes druhé zařízení k odstranění prokládání.

34. Kódovací a dekódovací systém podle nároku 29, zahrnující dále rozhodovací zařízení, implementující rozhodovací pravidlo, kterým se vytváří silné výstupní rozhodnutí jako funkce slabého výstupního rozhodnutí složeného dekodéru. , • ·

35. Způsob podle nároku 29 ve kterém N složkových dekodérů zahrnuje cirkulární MAP dekodéry, které dekódují řešením problému vlastního vektoru.

36. Způsob podle nároku 29 ve kterém N složkových dekodérů zahrnuje cirkulární MAP dekodéry, které dekódují použitím rekurzivní metody.