KreditVadász - Kódelmélet

Kódelmélet

Országok listája Hungary Nyíregyházi Főiskola Természettudományi Főiskolai Kar Programozó matematikus ZáróvizsgaKódelmélet

2009.02.01 19:32:32

(10)

Szerző: pulfix
Cimkék: kódelmélet

A dokumentum letöltéséhez be kell jelentkezned!

Az alábbi szöveg egy formázás és képek nélküli előnézete a dokumentumnak. A tökéletes megjelenítéshez jelentkezz be, majd töltsd le a dokumentumot.

17. Kódelmélet
(kódolási alapfogalmak; prefix kódok, felbontható kódok, teljes kódok; McMillan egyenlQtlenség; Shannon-féle entrópia és összefüggése a kód költségével, optimális kódok; Huffmann-féle kód; hibafelismerés, hibajavítás, lineáris kódok, generátor- és ellenQrzQmátrix, Hamming kódok)
Kódelmélet alapfogalmak
Betq szerinti kódolás: az elsQdleges közléshez tartozó ábécé minden egyes betqjéhez megfeleltetünk egy-egy jelsorozatot
A halmaz az elsQdleges közléshez tartozó ábécének nevezzük, elemei szimbólumok, n db van belQle. Véges nemüres halmaz.
Szimbólum sorozat ot alkotunk, hossza: ahány elembQl áll, jele: l.
Kódszó: A jelkészlet elemeibQl meghatározott szabályok szerint képzett értelmes üzenetet jelentQ egybefüggQ szimbólumsorozat (Jele: (. Annyi kódszó van ahány betq.)
Kódszó sorozat, kódolt közlés
Kódszó sorozat hossza a benne lévQ szimbólumok számával egyenlQ. Jele: li. Az i-edik kódszó hossza.
A jelsorozat hosszát ||-al (abszolútértékkel) szokták jelölni, vagy l után alsóindexbe, hogy melyik jelsorozatról van szó.
Kódolás: az elsQdleges közlés jeleit átalakítjuk Q-adikus alakra
Dekódolás: a q-adikus alakból visszakapjuk az elsQdleges közlést
Modulálás: a logikai jeleket fizikai jellé alakítjuk
Demodulálás: a fizikai jelekbQl megkapjuk a logikai jeleket

Kód: Két szimbólumhalmaz egyértelmq egymáshoz rendelése
Kódolás: Az egymáshoz rendelési mqvelet meghatározott szempontok szerinti végrehajtása
Dekódolás: A kódolás ellentétes mqvelete,-visszatérés a kiinduló halmazra-
Jelkészlet: Azon jelek összessége, melyeket meghatározott szabályok szerint a kódolási mqvelet során a kódszó alkotására felhasználtunk
Kódszó készlet: Azon kódszavak összessége melyek az adott rendszeren belül kódolásra felhasználhatók
Tiltott kódszavak: Olyan kódszavak, melyek nem elemei a kódszókészletnek
Két kódszó HAMMING távolsága (D): Hány kódelemet kell az ellenkezQjére változtatni hogy a másik kódszót kapjuk
Egy kód HAMMING távolsága: A kódszó készletelemei közötti legkisebb Hamming távolság
Titkosítás:
Rejtjelezés
Megfejtés
Tömörítés
Hibafelismerés

Nem nyilvános kulcsú titkosítás:

Adó VevQ
f(u) f(g(u))
f -1(g(f(u)))
(
g(u)
(
g ( g(u) ( u

Függvénnyel áttranszformáljuk az üzenetet, és elküldjük.
g(f(u)) = f(g(u)) ( f -1(f(g(u))) = g(u) (ismerjük u-t, így megkapjuk a g függvényt)
Ha valaki elkapja az üzenetet, akkor hibásat kaphatunk vissza.
Védekezés: egy megbeszélt idQpontban kell küldeni az üzenetet.
f(u) ( f -1(f(u)) = u (a függvény inverzét ismeri)

Kódolás:
Egy függvény: A* ( K* (reflexív lezárt)
Bináris esetben: A* ( {0,1}*
A: elsQdleges közlés ábécéje, pl. (a, b, c)
K: kódszimbólumok ábécéje, pl. (0, 1)
Függvény lehet K({ab,01};{ba,1};{aaa,1001};...) sajnos végtelen eleme van
K= {(1, (2,& , (n} EMBED Equation.3 K*
A= {a1, a2,& ., an}
K: ai ( (i

Definíció: Egy kódolást dekódolhatónak nevezzünk, ha létezik a kódolási függvény inverze (K-1).

Tétel: Egy kódolás akkor dekódolható, ha K kölcsönösen egyértelmq függvény.
Ellenpélda: A={a, b} K={100100,100}
a
100100
bb (nem tudjuk, hogy mi lett küldve)
Perfix kód
Definíció:Egy K kódot prefixnek nevezzük, ha egyetlen kódszó sem valódi kezdQszelete egy másiknak.
Tétel: Bármely prefix kód felbontható.
Példa nem prefix, de felbontható kódra: K={1, 10}
Tétel: Bármely felbontható kódhoz létezik vele ekvivalens prefix kód.
Definíció: Két felbontható kódot ekvivalensnek nevezzünk, ha kódszavai páronként azonos hosszúságúak.
Felbontható kód
Definíció: Egy bináris kódot felbonthatónak nevezzünk, ha bármely ( (szigma) bináris jelsorozat legfeljebb egyféleképpen bontható kódszavak szorzatára. (A szorzat konkatenációt, egymás után fqzöttséget jelent.)
MegfejthetQnek nevezünk egy kódot, ha az elQállít kódszó-sorozat minden esetben egyértelmqen meghatároz egy forrásszimbólum-sorozatot.
Tétel: ha egy kód minden kódszava ugyanolyan hosszú, akkor a kód felbontható.
Bizonyítás: Mivel minden kódszó azonos hosszú, egyik sem lehet kezdQszelete egy másiknak, tehát prefix, akkor pedig felbontható.

(3
1. K: {0, 1, 101} 101
(1 (2 (3 (2 (1 (2
Nem lesz felbontható!

2. K: {0, 1} 0 1 1 0 0 0 1 0
(1 (2 (2 (1 (1 (1 (2 (1
Felbontható!

Teljes kód
Def.: Egy K kódot teljesnek nevezzünk, ha bármely ( (szigma) bináris jelsorozat esetén vagy valamely kódszó kezdQ szelete (-nak, vagy ( kezdQszelete valamely kódszónak.
Pl. {0,1}illetve Huffmann-fÎ J
L
N
~
ª
l
n
p
~

Z

\

~

ìÙÆµ§µyrhYLF hCJh[Jh5>*CJ\h[Jh56>*CJ\hhCJ\
hCJ\h5>*CJ\%h©,ìhu[,B*CJOJQJaJphO½ h©,ìhu[,CJOJPJQJaJh. ºCJOJPJQJaJ h©,ìh2"-CJOJPJQJaJ%h©,ìhu[,B*CJOJQJaJph6_%h©,ìh$B*CJOJQJaJph6_%h©,ìh2"-B*CJOJQJaJph6_N
~
n
\

ä

0 l 4*¬.0ÆÖ 2ôçÙÔÏÔÔÔÔÔÊÊÊÊÔÔÂÂÂÂÔ½gdÍb $a$gd8&~gd[Jgdgd+ $$d ¤Èa$gd©,ì

$d ¤Èa$gd©,ì
$d ¤xgdÝh×

Î

â

ä

ò

ô

"
$
Þ
î
ð
. 0 ü þ *:ª¬ÂÄ,D²´ 0DFÆÜÞúôúêÝúÔÈÔú¿úôúµú¬ú¢¬ú¬¬ú¬ysjysjysjysh+ h+ CJ
h. ºCJh+ h+ 5>*CJ\h[J5>*CJ\h2Ah[JCJh0 ðh[JCJh[JOJQJ^J h[J5>*CJh[Jh[JCJH* jaðh[JCJh+ h[J5CJ\h+ h[JCJh+ h[J5>*CJ\h5>*CJ\
hCJ
h[JCJ)ÞÖ ô ö ÄÆ2rtvDF¸º¼
024vxzÚäæ÷êä÷êä÷×Ë¿¶×¶×£~xg`x`PxPxjh83ûCJUmHnHu
h83û5CJ!jh83û5CJUmHnHu
h83ûCJh83û6>*CJ
h83û>*CJh Téh83û5>*CJh83û5>*CJhÍb5>*CJ\h. º5CJ\hÍbhÍbCJh. ºh. º5CJ\h. ºhÍb5CJ\hÍbhÍb5>*CJ\
h. ºCJh+ h+ 5>*CJ\h+ h+ CJ¼Ôì 24vxä6Rn¼¾0äbàLN`°úõííõõõõõääõõõõõõõõõõõõÜÜ $a$gdg
ôÄ`Ägd83û
&
Fgd83ûgd83ûgdÍb"NP¦¨´¶TV\`êìòöN`~ÔÖØÚæè,.0468@BDHJprtvz~øòéòéòàòàò×òøòàòøòÎÈÁÈ¸ÈÁÈÁÈ¸ÈÁÈ¯¨È¯¨È¯¨ÈÈÈÁÈ¨È¨jhg
ôCJEHüÿUj
ØkB
hg
ôCJUVjhg
ôCJU
hg
ôCJH* jaðhg
ôCJ j¦ðhg
ôCJ
hg
ôCJH*
hg
ôCJhg
ô6>*CJ j»ðh83ûCJ j¦ðh83ûCJ j$ðh83ûCJ
h83ûCJ
h83ûCJH*4°êD$~¤¼¾~-- ` r ¨ þ !Ú! "F""÷çççççç÷÷÷÷Ý÷÷÷ÏÇ½Ç³ $¤xa$gdÏLz $¤xa$gd. º $a$gd. º $$d ¤Èa$gd. º $¤xa$gdg
ô$n7^n`7a$gdg
ô $a$gdg
ô ¬®°²´¶¸¼Ôî-t-x-~--` d r t ¦ ¨ þ !(!@!R!Ú!è!" "F"M"úóúóúêúáóúØúÏúÈú¾ú®ú®ú§ú|re[hÏLz56>*CJh

|h. º56>*CJh. º56>*CJh. º5>*CJ
h. ºCJh. º6>*CJ%h©,ìh. ºB*CJOJQJaJphO½
hg
ô>*
CJjhg
ôCJUmHnHuhg
ô56>*CJ
hg
ôCJH*hg
ô5>*CJhg
ô6>*CJ jaðhg
ôCJ j¦ðhg
ôCJ
hg
ôCJH*
hg
ôCJ"M"N"""§"º"ò"#
#
##-#D#E#R$`%j%l%ü% &þ&'''' '''X'Z'^'`'h'j'v'x'|'~'''÷ñèñßñÌ¿¶°§°°¿°ñ°u°le°u°lelelelelel
h. ºCJH* jaðh. ºCJjh. ºCJUmHnHu
hÏLz>*
CJh&\nh. º6>*CJ
h&\nCJ jdðh. ºCJh. º5>*CJ
h. ºCJh. º6>*CJhÏLzh. º56>*CJ%h©,ìh. ºB*CJOJQJaJphO½hÏLz5>*CJhÏLz6>*CJ
hÏLzCJh<æhÏLzCJ'"ò"#R$`%ü%þ&''H''¶'¸'

(D(`(b(x(Ê)@d@AA@AõçßßÕÍßÍÍÍÍÍÍÍÍÍçÈÈÕÈÈçgd. º $a$gdÏLz $¤xa$gdÑGñ $a$gd. º $$d ¤Èa$gd. º $¤xa$gdÏLz'' (((( ("(&(((,(.(2(4(8(:(>(@(F(b(x(~((°(Ü(Þ(l)n)))*@@ @@d@n@r@@@¾@À@Â@Ä@AAøòéøéøéøéøéøéøéøéøòÖÉòÀò·ò·ò·òµòÉÀòÉÀò«ò«òx.jh©,ìh. ºB*CJOJQJUaJphO½jh. ºCJEHäÿUj÷pB
h. ºCJUVaJ jh. ºCJUU jdðh. ºCJh. º5>*CJhÏLzh. º56>*CJ%h. ºh. ºB*CJOJQJaJphO½ jaðh. ºCJ
h. ºCJ
h. ºCJH*-a
Tétel: TetszQleges prefix optimális kód teljes.
Tétel: Teljes kódra igaz EMBED Equation.3 =1 Pl. {00,101,100,11,010,011}

McMillan egyenlQtlenség
Tétel: Bármely felbontható kódra teljesül a EMBED Equation.3 , ahol li az i. kódszó hossza. Ezzel csak azt tudom bizonyítani, ha nem felbontható egy kód.

Alkalmazása:
K={01,10,11,000,001,0010}
EMBED Equation.3 2-2+2-2+2-2+2-3+2-3+2-4= EMBED Equation.3 Nem felbontható, mert nagyobb mint 1!
Kivétel: Teljesül a McMillan egyenlQtlenség, mégse felbontható:
K={0,00} EMBED Equation.3 2-1+2-2= EMBED Equation.3
Tétel: Ha az l1, & , ln számokra igaz, hogy EMBED Equation.3 , akkor létezik prefix kód, hogy benne a kódszavak hosszai l1, & , ln
Shannon féle entrópia, és összefüggése a költséggel
Definíció: H(F)= EMBED Equation.3 számok az F jelforrás entrópiájának nevezzük.
Definíció: Egy K={(1,& , (n } (L={ l1,& ,ln}) kód H(F)={ p1,& ,pn } jelforrás melletti költségén az
L(K)= EMBED Equation.3 számot értjük.

Pl.
K={10,111,1001}
H(F)=P={0.2,0.3,0.5}

L(K)= EMBED Equation.3 =0.2*2+0.3*3+0.5*4=0.2+0.4+0.9+2=3.3

Optimális kód költsége és az entrópia összefüggése
Tétel: L(Ko) ( H(F)+1
Tétel: H(F) ( L(Ko) ( H(F)+1
Tétel: Bármely kódra és jelforrásra igaz H(F) ( L(K)
Definíció: Információ minden olyan dolog, amely bizonytalanságot szünetet meg. I(x) az x esemény információ tartalma.
I(x)= EMBED Equation.3
Optimális kód
Optimális kód létesítése
Minél rövidebb legyen a kódolt üzenet.
Az optimális kódok a kódolt közlés átlagos hosszát minimalizálják.

Definíció: Egy K kódot egy adott jelforrásra nézve optimális kódnak nevezzük és Ko-val jelöljük, ha bármely K esetén L(Ko) ( L(K )

Tétel: Bármely jelforráshoz létezik optimális kód.

Kódolás egyértelmqsége, optimuma (tömörítés)
Létezik tökéletes tömörítQ. A tömörítQk vizsgálják az adatállományon belül az összefüggéseket.
Huffmann-féle kód

Hibajavítás, hibafelismerés, lineáris kódok
Cél: védekezni az információs csatorna zajai ellen.
Hiba: mekkora hosszon, hány bit változik meg. (9 biten 1 hiba)

Hibafelismerés:
Az egyik legjobb módszer a hiba felismerésére a paritásbit. Ha van egy hosszú adatfolyamom, egészítsük ki 1 bittel úgy, hogy páros legyen benne az 1-esek száma. Ha páratlan volt 1-est kell hozzáírni, ha páros, akkor 0-át. Tehát ha az egészben egyetlen bit értéke megváltozik, biztos észre fogom venni.

101001001 páros az egyesek száma 29=512, a fele 256

A kód sqrqssége: mennyire sqrqn helyezkednek el a kódszavak.
EMBED Equation.3

m: kódszó hossz (blokk méret)

Hibajavítás:
Ott alkalmazzuk, ahol nem oldható meg, hogy újból küldjék az adatokat. Egy biztos módszer a triplázás. 3x küldöm el az adatot, pl.:101, azt mondom, hogy 9 biten max 1 bit változhat meg, elküldöm még 2x: 101101101. Akárhol változik meg az 1 bit, három felé vágom, és választom a két egyformát. Nem túl gazdaságos, viszont biztos.
Csak azon a vonalon nem tudok adatot küldeni, ahol 50% a hiba lehetQsége. A kevesebb, vagy több, akkor tudok.
3 bitenként megismétlQdnek: 110110110 EMBED Equation.3

Definíció: Két kódszó Hamming távolságán a különbözQ pozíciók számát értjük.
(1 10110 d((1, (2)=3
(2 11000

Definíció: Egy K kód távolságán kódszavai távolságának minimumát értjük.
K={101,000,110,011}
D(k)=? Meg kell határozni az összes kódszó távolságot, és abból venni kell a legkisebbet.

Tétel: A Hamming távolság metrikát indukál.
f(a,a)=0
f(a,b)=f(b,a)
f(a,b)( 0
f(a,b)+f(b,c) ( f(a,c)

Pl.
( ( ( h: hiba max. h db bitje fog megváltozni
d((,( ) ( h

Tétel:
Egy K kóddal, akkor tudunk t hibát felismerni, ha d(K) ( t.

Tétel:
Egy K kóddal, akkor tudunk t hibát javítani, ha d(K) > 2t

PAGE \* MERGEFORMAT 5

h

Hasonló témájú dokumentumok

Egyelőre még egyetlen hasonló témájú file sincs feltöltve a rendszerbe

A mások által feltöltött dokumentumokat értékelheted. Ha úgy ítéled meg, hogy a vizsgára való felkészülés szempontjából hasznos volt egy dokumentum, akkor adj rá sokcsillagos értékelést.
Ha hibákat tartalmaz, vagy egyéb probléma van vele, akkor keveset.
A dokumentumok sorrendje az értékelések alapján adódik. Ami fentebb van a listában, azt hasznosabbnak ítélték társaid. Az új dokumentumok pedig (értékelések hiányában) szintén a lista tetején kezdenek.

Hozzászólások

Ha észrevételed van egy dokumentummal kapcsolatban (például hibát találtál benne), akkor a Hozzászólások részben jelezheted. Az olyan jellegű kérdéseket mint pl.: A 2. feladat 4. sorából milyen átalakítással jutottunk az 5. sorban szereplő képlethez? - szintén ide érdemes írni

Egy tipp az oldalhoz! - Töltsétek ki a Tantárgyi adatlapokat a tantárgyak oldalain. Fontos lehet a tantárggyal kapcsolatos információ vagy az előadóval való egyszerű kapcsolattartás végett. Az adatlapot csak akkor módosíthatod ha az adott tárgyat a saját tárgyaidhoz adtad.

Kódelmélet

Hasonló témájú dokumentumok

Egyelőre még egyetlen hasonló témájú file sincs feltöltve a rendszerbe

Hozzászólások

Cimkefelhő