Szerkesztő:Beginner 25/kód

Kódolás az a művelet, amely a forrásábécé betűit egy kódnak nevezett függvény segítségével leképezi egy kódábécére. Ha egy közlemény kódját az egyes forrásbetűkhöz rendelet kódszavak sorrendben egymás után való írásával kapjuk, betűnkénti kódolásról beszélünk. Ha a kódolást betűcsoportonként végezzük, akkor a betűnkénti kódolás egy kiterjesztését, a blokk-kódolást alkalmazzuk.

A kódolást azért kell alkalmazni, mert a hírközlési eszköz - a csatorna - csak meghatározott típusú jeleket képes átvinni, vagy bizonyos műszaki okok ezt szükségessé teszik. Ilyen kódolási formák pl. a Manchester-kódolás, az NRZ (nullára vissza nem térő - Non Return to Zero) kódok. Az információforrásból származó jelfolyamot kódolással kell megfeleletetni egy, a csatorna által használt jelekből álló jelfolyamnak. A felhasználó (nyelő) a csatorna kimenetén pontosan, vagy megközelítőleg pontosan visszaállítja, dekódolja az üzenetet.

Alapvetően két kódolási típust különböztethetünk meg:

  • forráskódolás
  • csatornakódolás.

A forráskódoláshoz tartoznak a különféle adattömörítési eljárások, míg a csatornakódok többnyire hibajavító kódok.

Egy ilyen hírközlési csatorna blokkdiagrammja a következő:


ForráskódolásSzerkesztés

A forráskódolás valójában egy leképezés, a szimbólumok (egy sorozata) által képviselt információt leképezzük egy ábécé (általában bitek) elemeinek sorozatára, úgy, hogy a forrás szimbólumok vagy pontosan visszaállíthatók a bináris információkból (veszteségmentes kódolás esetében), vagy a visszaállítás csak bizonyos torzulás mellett lehetséges (veszteséges kódolás esetében).

Elméleti meghatározásaSzerkesztés

Legyen

  •   egy diszkrét valószínűségi változó amely a   =   véges halmazból veszi értékeit. Ezt a halmazt nevezzük forrásábécének, elemeit pedig betűknek nevezzük.
  •   elemeiből alkotott véges sorozatok az üzenetek vagy közlemények.
  •   egy s elemű,   halmaz, amit kódábécének nevezünk.
  •   jelölje az   elemeiből álló, véges sorozatok halmazát.   elemeit kódszavaknak nevezzük.


Egy  :   függvényt, amely megfeleltetést hoz létre a forrásábécé és a kódszavak között kódnak nevezünk. Amennyiben az   kód értékkészlete különböző hosszúságú kódszavakból áll, úgy változó szóhosszúságú kódolásról beszélünk.

Egy kód esetében alapvető elvárás az egyértelmű dekódolhatóság, egy beérkező kódszóról egyértelműen el kell tudni dönteni, hogy minek kell dekódolni.

Egy kód egyértelműen dekódolható, ha minden véges kódbetűsorozat legfeljebb egy közlemény kódolásával állítható el. Az előzőek jelölései alapján, egy  :   kód egyértelműen dekódolható, ha u  , v  , u= , v= , u v, akkor  ( ) ( )... ( )    ( ) ( )... ( ). Az  ( ) ( ) művelet a két kódszó egymás után írását, azaz a egybeolvasztását jelenti.

Az egyértelmű dekódolhatóság több, mint az invertálhatóság.

Legyen például   =  ,   =   és  (a)=0,  (b)=1 és  (c)=01. Ebben az esetben ugyan a  :  ->   függvény invertálható, viszont a 01 kódszó dekódolható ab-nek, de c-nek is.


Optimális kódokSzerkesztés

Optimális kódolás alatt általában, veszteségmentes tömörítés esetében, a lehető legrövidebb kódszó elérése - az átvinni kívánt információ minimalizáslása - a cél, úgy hogy abból az eredeti információ egyértelműen visszaállítható legyen. Veszteséges tömörítés esetében az optimitás nem ilyen egyértelmű. -

Huffmann kódolásSzerkesztés

A számítógéptudományban és az információelméletben, a Huffman kódolás egy entrópiakódolási algoritmus, amit főként veszteségmentes tömörítéseknél használnak. A kifejezést általánosabb értelemben is használják egy forrás-szimbólum (mint például egy fájl egy karaktere) változó hosszúságú kódtábla segítségével végzett kódolásra, ahol a változó hosszúságú kódtábla a forrás-szimbólumok becsült előfordulási gyakorisága alapján épül fel. Az eljárást David A. Huffman dolgozta ki, amikor a MIT Ph.D hallgatója volt, és 1952-ban publikálta a "A Method for the Construction of Minimum-Redundancy Codes" (Módszer minimum redundanciájú kódok létrehozására) cikkében.

Abban az esetben, ha a halmazban lévő szimbólumok előforduási valószínűségeik azonasok, és halmaz elemeinek a száma 2 valamilyen (egész) hatványa, a Huffman kódolás ekvivalens az egyszerű blokk kódolással.

A Huffman kódolás egy széleskörben elterjed módszer prefix kódok előállításánál, és gyakran a "Huffman kód" kifejezést a "prefix kód" szinonímájaként használják, még ha a kód előállítása nem a Huffman algoritmus szerint történik is.

Annak ellenére, hogy a bináris Huffman kódolás optimális a szimbólum-szimbólum kódolásnál, ha ismert a bemenet valószínűségi eloszlása, a kód optimitása más esetekben nem feltétlenül a legjobb. Például, az aritmetikai kódolás és az LZW kódolás gyakran jobb kompressziós képeseségeket mutat. Ez utóbbi két módszer egymással kombinálható egy megadott számú szimbólum még hatékonyabb kódolására, a az aktuális bementi statisztikákhoz alakítva, míg a Huffman kódolás jobban alkalmazható, ha a szimbólumok előfordulási gyakorisága nem pontosan ismert.

Bináris Huffman-kódSzerkesztés

A feladat, hogy egy adott A halmazhoz, amely a szimbólumokat, valamint hozzásjuk tartozó súlyokat (általában előfordulási valószínűségüket) tartalmazza, keseni kell egy olyan prefix kódot (kódszavak halmazát), amelyek hossza minimális (ez ekvivalens egy minimális fával).

Formális leírásSzerkesztés

Bemenet:
Legyen az   halmaz az ábécé, amely az   számú szimbólumot tartalmaz.
A   halmaz, a szimbólumok (pozitív) súlyait tartalmazza (általában az előfordulási valószínűsége), és   az  -hoz tartozó súly.

Kimenet:
Egy   kódhalmaz, amely a (bináris) kódszavak halmaza, ahol   az   -hoz tartozó kódszó.

Cél:
Legyen   a   súlyozott úthossza. Feltétel:   bármilyen   kódra.

PéldaSzerkesztés

Bemenet Szimbólum a b c d e  
Súlyok 0.10 0.15 0.30 0.16 0.29 = 1.00
Kimenet Kódszavak 000 001 10 01 11  
Kódszó hossza (bitekben) 3 3 2 2 2  
Súlyozott úthossz 0.10 * 3 0.15 * 3 0.30 * 2 0.16 * 2 0.29 * 2 = 2.25
Optimalitás Információ tartalom (bitekben) 3.32 2.74 1.74 2.64 1.79  
Entrópia 0.332 0.411 0.521 0.423 0.518 = 2.205


Shannon definíciója alapján bármilyen ai szimbólum bitekben mért információ tartalma h

 

Az információ entrópiája H (bitekben) nem más, mint az öszes szimbólum súlyozott információ tartalma:

 

Aritmetikai kódolásSzerkesztés

Az aritmetikai kódolással a Huffman kódolás korlátait meghaladó tömörítést lehetett elérni, valós idejű működési mód mellett. A Huffman kódolással csaknem 1 bitet veszthetünk karakterenként a tömörítés elméleti korlátjához képest, ezért célszerű blokkonként kódolni. Ez viszont azt jelenti, hogy egy Huffman kódszót csak a teljes blokk beolvasása után lehetséges elküldeni, ami nagy blokkhossz esetén már jelentős késleletetést jelenthet. A kódoló-dekódoló táblák mérete, akód fejlécének hossza a blokkhossz növelésével exponenciálisan nő, ami gyakorlati szempontból jelent korlátot.

Az aritmetikai kódolást főként blokkokra alkalmazzák, valós időben történik a kódszó előállítása - és visszafejtése is - nincsen tehát jelentős késleltetés.

A kódolási eljárás alaplve, hogy a [0,1) intervallumot úgy osztjuk fel, hogy a forrásábécé minden eleméhez egy részintervallumot rendelünk úgy, hogy

  • a részintervallumok a teljes intervallumot lefedjék
  • a részintervallumok diszkjunktak legyenek
  • méretük arányos legyen a hozzá rendelt forráskarakter előfordulási valószínűségével.

Következő lépésben az első forráskaraktenek megfelelő részintervallumot osztjuk fel az előzőek szerint, és így tovább. Az így skatulyázott részintervallumok egyértelműek és visszafejthetők. További részletek az aritmetikai kódolás alatt.

Futamhossz kódolásSzerkesztés

Abban az esetben, ha fekete-fehér képek képpontjait kell kódolni (pl. faxok) akkor alkalmazzák a futamhossz kódolást, ami azon az elven alapszik, hogy jelöljük, milyen színű a kiinduló képpont (fehér vagy fekete), ezt követően pedig azoknak a képpontoknak a számát küldjük át a vevőnek, amelyek ilyen színűek, majd a következő szám az jelzi, hány ellentétes szinű képpont következik, majd ismét a másik szinű képpontok szma következik, és így tovább. Egy speciális jel jelöli a sor végét. A fenti algortmus az egydimenziós futamhossz kódolást mutaja be, amit az ITU-T (régebben: CCITT) fax szabványban használnak (Group3 és Group4). A Group1 és Group2 még analóg technolgiát használt.

Egészen pontosan, a Group3 által használt kódolás úgy működik, hogy először a fehér képpontok futamszámát - hosszát - határozza meg. Ha az adott sor fekete képponttal kezdődik, akkot egy 0 hosszúságú fehér képponttal indít az algoritmus. Mivel a különböző futamhosszak eltérő valszínűséggel frdulnak elő, ezért ezeket változó szóhosszóságú Huffman kóddal kódolják, a futamok össz hossza, vagyis egy sor 1728 képpont. Mivel túl sok lehetséges futamhossz lehetséges, ezért a tényleges h hosszt 1 vagy 2 jegyű, 64-es számrendszerben felírt számként kódolják, tehát
h=64m+t, ahol t=0,1,....,63, és m=0,1...,27.
Külön kódtáblzatot használnak az m, vagyis kiegésztő kódra (ezt nevezik make up kódnak, MUC), míg a t a lezáró kód (terminating code, TC) számra szintén külön kódtábla van. Egy futam kódját a színnek megfelelő MUC illetve TC táblázatból kiolvasott kódszavak konkatenciója - egyesítése adja. A sor végét egy speciális EOL (end of line) kódszó jelzi, ez egyben az adó és vevő közötti szinkronizációt is biztosítja.

Az 1984-ben publikált Group4 már kihasználja a függőleges irányú redundanciákat is, és felülről kompatibilis a Group3-al. A Group4 kétdimenziós futamhossz kódolással dolgozik.

Univerzális forráskódolásSzerkesztés

Ide tartoznak a ma használatos tömörítő eljárások, a különböző LZ (Lempel-Ziv) és LZW (Lempel-Ziv-Welch) kódok.

Az előző két kódolási eljárásban az átvitt bitek két csoportot alkottak:

  • blokk-kódot leíró információk
  • az üzenet kódszavai.

A LZ kódok az úgynevezett adaptív kódok közé tartoznak, ami azt jelenti, hogy a kódolás egy lépésben történik, a bejövő szimbólumról menet közben gyűjt a kódoló információkat, míg a nem adaptív kódok esetében a teljes bejövő sorozatot (blokkot) először végigelemzi, majd utána a gyűjtött információk alapján készti el a tényleges kódot (pl. Huffman kódoló, bár meg kell jegyezni, hogy létezik adaptív Huffman kódoló).

Forráskódolás betűnkénti hűségkritériummalSzerkesztés

A változó hosszúságú kódszavakkal történő kódolás esetén komoly problémát jelent a dekódolásnál, ha hiba lép fel az átvitel során, mivel ekkor nem lehet egyértelműen meghatározni azt a pontot, ahonnan a kódszó felismerés - és dekódolás - folytatható. Ennek a problémának egy lehetséges elkerülési módja, a fix hosszúságú kódszavak használata, és a kódszó kialakítás előtt úgy lecsökkenteni az átvinni kívánt információ mennyiségét, hogy az rövidebb kódszóban is átvihető legyen.

A fenti elv egyik legegyszerűbb megoldása a különbségi kódolás, amikor a források értékei helyett egy adott értékhez, vagy egymáshoz képesti eltéréseket tekintik forrásinformációnak. Például egy kép egymást követő képpontjai között - ha nem egy átmenet közelében vagyunk - a változások viszonylag kicsik, és a kódolásukra a fenti módszerrel sokkal kevesebb bit is elegendő.

Fenti csoportba tartoznak még a

  • kvantálók
  • szűrők
  • mintavételes kódolók
  • transzformációs kódolók, illetve ezen eljárások kombinációi (például a telefontechnikában a hangspektrumot először 34 kHz-es sávszűrővel szűrik, majd ezt a szűrt jelet 8 kHz-el mintavételezik, amit 8 biten dekódolnak.)

E kódolók közös jellemzője, hogy többnyire olyan információkat kódolnak, amelyeket dekódolás után érzékszerveinkkel dolgozunk fel, azaz képeket vagy hangokat, és kihasználják érzékszerveinknek azt a sajátosságát, hogy érzékenységük frekvenciafüggő, és képesek interpolálni is. Az átvinni kívánt információ jellemző részeit nagyobb hűséggel viszik át, míg a kevésbé érzékeny ferkvencia tartományban sokkal kisebb az információ hűség. Ezzel módszerrel jelentős tömörítést lehet elérni úgy, hogy - látszólag - nincsen, vagy nagyon kicsiny az információvesztés.

CsatornakódolásSzerkesztés

A csatornakódolás a zajos csatornán történő megbízható információátvitelt biztosítja. A csatornakódolás azon kívül, hogy megbízható átvtelt biztosít, még arra is törekszik, hogy a zajos csatornát a lehető legjobban kihasználja, azaz a lehető legjobb csatora- kihasználtságot érjen el. A csatorna kihasználtságára létezik elvi korlát, ez a csatornakapacitás.

A csatornakódok többnyire hibajavító kódok, azaz olyan tulajdonságokkal rendelkeznek, hogy a csatornán - ami a gyakorlatban többnyire zajos csatornát jelent, ami a kód valamilyen szintű sérülését okozhatja - való áthaladása után is képes bizonyos sérülések javítására, azaz az átvitt információ (bizonyos korlátok mellett) helyreállítható belőle.

A kódolási fogalmakat a csatornakódolás esetében a következők szerint értelmezzük: A forrás az   forrásábécéből veszi az u vektor értékét. A kódoló ezt az u vektort (az üzenetet) egy   hosszúságú c vektorba (a kódszóba) képezi le, amelynél a kódszó elemeit a   halmazból veszi. A   halmazt kódábécének, vagy csatorna bemeneti ábécének nevezik. A csatorna kimenetén a v vektort kapjuk, ami szintén a   eleme, egy   hossúságú vektor.

Blokk kódokSzerkesztés

A blokk kód a csatornakódok egyik elsődleges típusa, amit a korai mobil kommunikációs rendszerekben használtak. Egyszerűen egy redundanciát visz be a kódba azért, hogy a vevő oldalon (elméletileg) nulla hiba valószínűséggel dekódolható legyen, ezzel biztosítva, hogy az információs ráta (a másodpercenként átvitt információ bitekben mért mennyisége) ne haladhassa meg a csatornakapacitást. A blokk kód fő jellemzője, hogy egy fix hosszúságú csatorna kód (nem úgy, mint a forrás kódolásnál használt Huffmann-kód, vagy a csatorna kódolásnál használt konvolúciós kódok). Egy blokk kód általában egy k-digitből álló információs-szót átalakít egy n-digites kódszóvá.

KorlátokSzerkesztés

A csatornakódok esetében két dolog lényeges számunkra:

  • hibajelzés/hibafelismerés
  • hibajavítás

A hibajelzés a hibakorlátozó kódolás feladata, ekkor detektálni akarjuk a hibázás tényét. Hibajavítás esetében az a kérdés, ha t a hibák száma, akkor hogyan lehet a vett kódszóból a helyes kódszót visszaállítani.


Elméleti meghatározásaSzerkesztés

Az információelméletben, egy blokk kód egy kód amely az   halmazzal jelölt ábécből formált sorozatokat (stringeket) into code words by encoding each letter of   separately. Legyen   a természetes számokból alkotott sorozat (bármely eleme kisebb, mint  ). Ha   és a particular word   is written as  , then the code word corresponding to  , namely  , is

 .


Információs rátaSzerkesztés

Ha   bináris blokk kód, és n bites,   kódszavakból épül fel, akkor a   információs rátáját a következő módon defniálhatjuk:  . Ha a kódszó első k bitjei a független információ bitek, akkor az információs ráta:  .


Lineáris kódokSzerkesztés

A lneáris kódok kódszavai viszonylag egyszerűen generálhatók, és egyszerűen ellenőrizhető, hogy a kódszavak hibamentesek-e, a hibadetektáls és javítás sem bonyolult.

A bináris Hamming-kódSzerkesztés

Bináris Hamming kódok azok a kódok, amelyek 1 hibát tudnak javítani, és amelyekre igaz, hogy   hosszságú üzenethez az   hosszú kódszót rendelik, és   és   között mindig fennáll a
  összefüggés.
Ilyen számpárok a (3,1),(7,4), (15,11), (31,26), (63,57), (127,120) amelyeket most (n,k) formában adtunk meg A fenti bináris Hamming kódok egyben perfekt kódok is. A Teletext például a (7,4) Hamming kód egy paritásbittel páratlanra kiegészített (8,4) paraméterű, 1 hibát javító kódot használ. A közvetlen műholdas műsorszórás (DBS - Direct Broadcasting Satellite) digitalizált hangját a D2-MAC/PACKET szabvány egyik változatában a 14 bites hangminta felső 11 bitjét egy (16,11) paraméterű kóddal kódolják, ami a (15,11) paraméterű Hamming kód kiegészítése egy páratlan paritásbittel.

A nembináris Hamming-kódSzerkesztés

A nembináris Hamming kódok szintén 1 hibát tudnak javítani, azonban a binárs esetnél bonyolultabb a hibafelismerés: itt ugyanis nem elegendő a hibahely felismerése, hanem a hiba értékét is meg kell tudni határozni.

Golay kódokSzerkesztés

Bináris Golay kódokSzerkesztés

A bináris Golay kód egy hibajavító kód, amelyet a digitális kommunikációban használnak. A bináris Golay kód, együtt a ternáris Golay-kóddal a véges sporádikus csoportok matematikáján alapulnak. A kód a nevét Marcel J. E. Golay tiszteletére kapta.

Két, a bináris Golay kódhoz nagyon közeli kód létezik még:

  • a kiterjesztett bináris Golay kód 12 bites adatokat kódol 24 bites kódszavakká, amelyek bármilyen 3 bites hibát képesek kijavítani, és a 4 btes hibát felismerni (azaz a 24 bites kódszó brmelyik 3 bitjének sérülését javytja, 4 bit sérülését pedig jelzi).
  • a másik, a perfekt bináris Golay kód, 23 bites kódszavakat használ, has codewords of length 23 and is obtained from the extended binary Golay code by deleting one coordinate position (conversely, the extended binary Golay code is obtained from the perfect binary Golay code by adding a parity bit).

Nembináris Golay kódokSzerkesztés

here are two closely related hbajavító kóds known as ternary Golay codes. The code generally known simply as the ternary Golay code is a perfect (11, 6, 5) ternary linear code; the extended ternary Golay code is a (12, 6, 6) linear code obtained by adding a zero-sum check digit to the (11, 6, 5) code.

The complete weight enumerator of the extended ternary Golay code is

 .

The perfect ternary Golay code can be constructed as the quadratic residue code of length 11 over the finite field F3.

The automorphism group of the extended ternary Golay code is 2.M12, where M12 egy Mathieu-csoport.

Consider all codewords of the extended code which have just six nonzero digits. The sets of positions at which these nonzero digits occur form the Steiner system S(5, 6, 12).

Reed-Solomon kódokSzerkesztés

Reed–Solomon error correction is an error-correcting code that works by oversampling a polynomial constructed from the data. The polynomial is evaluated at several points, and these values are sent or recorded. By sampling the polynomial more often than is necessary, the polynomial is over-determined. As long as "many" of the points are received correctly, the receiver can recover the original polynomial even in the presence of a "few" bad points.

Reed–Solomon codes are used in a wide variety of commercial applications, most prominently in CDk és DVDk, and in data transmission technologies such as DSL, DVB and WiMAX.

Ciklikus kódokSzerkesztés

Azokat a kódokat, amelynél a kódszó ciklikus eltolása ismét kódszót eredményez, ciklikus kódoknak nevezik.

A BCH-kód (BCH = Bose-Chaudhuri-Hocquenghem)Szerkesztés

A BCH (Bose, Ray-Chaudhuri, Hocquenghem) code is a much studied code within the study of coding theory and more specifically error-correcting codes. In technical terms a BCH code is a multilevel, cyclic, error-correcting, variable-length digital code used to correct multiple random error patterns. BCH codes may also be used with multilevel phase-shift keying whenever the number of levels is a prime number or a power of a prime number. A BCH code in 11 levels has been used to represent the 10 decimal digits plus a sign digit.

ConstructionSzerkesztés

BCH codes use field theory and polynomials over finite fields. To detect errors a check polynomial can be constructed so the receiving end can detect if some errors had occurred.

The BCH code with designed distance   over the field   is constructed by first finding a polynomial over   whose roots include   consecutive powers of  , some root of unity.


KódkombinációkSzerkesztés

KódátfűzésSzerkesztés

SzorzatkódSzerkesztés

Kaszkád kódokSzerkesztés

KódmódosításokSzerkesztés

Rövidített kódSzerkesztés

Paritásbittel bővítésSzerkesztés

Konvolúciós kódokSzerkesztés

A telekomunikációban, a konvolúciós kód egy hibajavító kód amelynél

  • (a) bármilyen m-bites információs szimbólum (bármilyen m hosszúságú bit string) a kódolás folyamán egy n-bites szimbólummá transzformálódik, ahol m/n az úgynevezett kód ráta (nm) és
  • (b) the transformation is a function of the last k information symbols, where k is the constraint length of the code.


A konvolúciós kódokat gyakran használják a digitális rádiózásban, az (átviteli) teljesítmény javítására, a mobil telefonoknál, műholdas kapcsolatoknál, és Bluetooth megvalósításokban.

Turbó kódokSzerkesztés

Kódok speciális tulajdonságaiSzerkesztés

Prefix kódokSzerkesztés

Ha az   kód esetében igaz, hogy a lehetséges kódszavak közül egyik se folytatása a másiknak, vagyis bármely kódszó végéből bármekkora szegmenst levágva nem kapunk másik kódszót, akkor az   kód prefix. Egy prefix kód egyérteműen dekódolható.

Kraft és McMillen lemmái alapján kiderül, hogy minden egyértelműen dekódolható kódhoz létezik vele ekvivalens (azonos kódszóhosszú) prefix kód. Ezért célszerű, ha az egyértelmű dekódolthatóság helyett a prefix tulajdonságot követeljük meg egy kódtól, ami speciálisabb, ezért könnyebben kezelhető tulajdonság.

Perfekt kódokSzerkesztés

Olyan kódokat, ahol a Hamming-korlátban = áll, perfekt kódoknak nevezzük. Bináris Hamming-kód esetében ahol t=1:

1+n=2^(n-k)

e hibajavító C kód perfekt, ha ∀v∈Q^n-hez van olyan c∈C, amelyre d(v,c)≤e

Lineáris kódokSzerkesztés

Egy   kód lineáris, ha a   halmaza lineáris tér, azaz ha minden c,c'     -re igaz, hogy c+c'    . Általában egy   hosszúságú és   rangú lineáris kód a   lineáris altere egy   dimenziós   vektor tér, ahol   egy   elemű véges mező. A kódokat a   alapján nevezik q-áris kódnak (pl. ha  , a kód 5-áris kód). Speciálisan a   és a   estekben a kódokat bináris és ternáris kódoknak nevezik. A lineáris kód definíciója alapján a 0 eleme minden lineris kódnak.

Ciklikus kódokSzerkesztés

Azokat a kódokat, amelynél a kódszó ciklikus eltolása ismét érvényes kódszót eredményez, ciklikus kódoknak nevezik.