6. fejezet KódeImélet

6. fejezet KódeImélet l. Információs csatorna.

Betű

szerinti kódolás

Az információcsere folyamatának három fő komponense az adó- és a dezés, valamint az őket összekötő ún. információs csatorna (6.1. ábra).

adóberendez.és

vevőberen­

f----------~----------_i vevő berendezés

információs csatorna

6.1. ábra

Az adókészülék általában valamilyen A = {al> a2 , ••• , an} kimeneti ábécé jeleit küldi ki, és a vevőkészülék ezeket a jeleket fogja fel. Az A ábécé jeleiből alkotott a j1 a j2 • •• ajk sorozatokat elsődleges köz/éseknek nevezzük. Vegyük például egy távirat továbbítás ának az esetét. Itt az adó- és a vevőberende­ zést egy-egy telexgép jelenti, az információs csatorna pedig az a távíróvonal, amely ezeket a gépeket összeköti. A kimeneti ábécét a latin betűs ábécé jelei, a számjegyek és az írásjelek alkotják, az elsődleges közlések pedig maguk a táviratszövegek, melyeket pl. magyarul fogalmaztunk meg. Az információs csatorna fizikai jellemzői általában csak bizonyos rögzített számú különböző jeltípus továbbítását és biztos felismerését teszik lehetővé - jelöljük ezt a számot a továbbiakban q-val -, s ez a q szám rendszerint sokkal kisebb, mint ahány betűje az A kimeneti ábécé nek van. Rendeljük hozzá a q darab különböző jeihez a 0, 1, ... , q-l számokat. Ekkor az információcserének az alábbi fázisait különböztethetjük meg: l. 2. 3. 4. 5. 6.

az elsődleges közlés átalakítása "q-adikus" alakra; a q-adikus alak átalakítása fizikai jelekké; a jelek kiküldése az információs csatornába; a jelek felfogása a vevőberendezésen; a fizikai jelek visszatranszformálása q-adikus jelekké; az elsődleges közlés előállítása a q-adikus alakból.

256

Az első és a hatodik fázist nevezzük kódolásnak, ill. dekódoJásnak, a másodikat és az ötödiket pedig modulálásnak, ill. demodulálásnak. Az információtovábbítás gyakorlati megvalósulásainál igen gyakran fordul elő, hogya fentiekben felsorolt hat fázis műveletei közül többet is (esetleg mind a hatot) ugyanaz a berendezés végez el. Azelektronikus számítástechnikai eszközöknél alkalmazzák pl. az ún. modemeket (a szó a modulátor-demodulátor rövidítéséből származik), melyek mind a hat funkció ellátására képesek. Az információtovábbítás folyamatát tehát a 6.2. ábra szerinti, részletesebb sémával ábrázolhatjuk. r-

'"

r--L-

0'0

'0

~~ Q)

o

'Oc

.D

'---

-

L-

' Q)

.o~

adóberendezés

o

informóciós csatorna

....o

~~

'3 'o o

'o 'o .>l C

'0

::l 'o

E ol

E

-

'---

fiz.ikoi jelek

ü

.g

ol

vevőberendez.és

",Ol

'O~

-

.o

,

q- adikus alak elsődleges

közlés

6.2. ábra

A most következő ~zet tárgyát a kódolási-dekódolási folyamat képezi. A modulálás, ill. demodulálás elsosorban technikai jellegű probléma, ezért itt nem foglalkozunk vele. A gyakorlatban az információs csatorna rendszerint csak kétféle jel továbbítására alkalmas (azaz q = 2); ezekhez a jelekhez a Oés az 1 számokat rendelhetjük hozzá. A továbbiakban mi is ennek a legfontosabb esetnek a vizsgálatára szorítkozunk, bár megjegyezzük, hogy az eredmények jelentős része általánosítható 2-nél nagyobb q esetére is. Legyen A ;::: {ab a2 , ••• , an} tetszőleges kimeneti ábécé, és legyen K = {OCb OC2 , •• " OCn } véges hosszúságú bináris sorozatoknak valamilyen n-elemű halmaza. A sorozatokról nem tesszük fel, hogy mind azonos hosszúságúak. Rendeljük most hozzá az aj E A betűk mindegyikéhez a K halmaz egy-egy OC j elemét úgy, hogy különböző betűkhöz különböző bináris sorozatok tartozzanak. Ekkor tetszőleges ahaj• ... ajk elsődleges közléshez egy oci,oc j • • • • ocjk bináris sorozatot tudunk hozzárendelni. 6.1. DEFINÍCIÓ. A kódolásnak azt a formáját, melynél a kimeneti ábécé minden egy-egy oc j E K bináris sorozatot feleltetünk meg, betű szerinti kódolásnak nevezzük.

aj betűjének

257

6.2. DEFINÍCIÓ. A K halmazt kódnak, az (lb (l2, .. '. (ln elemeket kódszavaknak, a kódszavak tetszőleges sorozatát pedig kódolt közlésnek mondjuk. 6.1. PÉLDA. Legyen A = {a, b, c, d} a kimeneti ábécé, a {OO, 01 , 100,1O1} halmaz pedig a kód. Ekkor a dac sorozatnak mint elsődleges közlésnek az 101O0l00 sorozat lesz a betű szerinti kódolása. (Itt persze feltettük, hogy az ábécé betűi, ill. a kódszavak a megfeleltetés szerint, ugyanabban a sorrendben vannak felsorolva .) Kódolásnak tehát azt az eljárást nevezzük, amikor minden elsődleges közléshez hozzárendelünk egy-egy kódolt közlést. Éppen ezért úgy is tekinthetünk erre a folyamatra, mint egy ?ú: A* - {O, 1}* függvényre . (Emlékeztetőül megjegyezzük, hogy M* -gal jelöltük az M-beli elemek összes véges sorozatából álló halmazt.) Hogy az eredeti elsődleges közlést a kódolt formából visszakaphassuk, azaz hogya dekódolás legalább elvben megvalósítható legyen, léteznie kell egy ?ú-l: {O, 1 c_ A* inverz függvénynek. Ilyen ?Ú-l nyilván pontosan akkor létezik, ha a ?ú függvény egyegyértelmű, azaz ha különböző A* -beli szavakhoz különböző {O, 1}* -beli elemeket rendel. így tehát a ?Ú-l nem létezhet, ha vannak olyan ai,ai• ... ai, és aj,aj, ... aj, egymástól különböző elsődleges közlések, amelyeket a ?ú ugyanúgy kódol, azaz

r

?ú(ai1ai• ... ai,) = ?ú(aj,aj, ... aj~ Betű szerinti kódolásnál ez azt jelenti, hogy van olyan bináris sorozat, amelyet legalább kétféleképpen tudunk kódszavakra bontani. Ha ilyen sorozat nem létezik, a ?ú egy-egyértelmű.

6.2. PÉLDA. Legyen A = {a, b, c, d} a kimeneti ábécé, a kód pedig K = {OO, 01, ll, 0001}. Ez a kódolás nem egy-egyértelmű, mivel az ab, ill. a d sorozatoknak egyaránt a 0001 bináris sorozat felel meg. 6.3. DEFINÍCIÓ. A K = {lXl. 1X2, ... , IX,,} kódot felbonthatónak nevezzük, ha leges bináris sorozat legfeljebb egyféleképpen bontható kódszavak szorzatára.

tetsző­

Nyilvánvaló, hogy tetszőleges felbontható kód minden olyan kimeneti ábécé esetén kódolást és dekódolást tesz lehetővé, melynek a számossága megegyezik a kód számosságával (vagyis a dekódolás megvalósíthatósága nem függ a kimeneti ábécétől, hanem csak akódtól). egyértelmű

258

2. Felbonthatósági feltételek Ha a K-beli kódszavak hossza mind egyenlő, akkor a K kód nyilvánvalóan felbontható lesz. Adhatunk azonban egy ennél általánosabb feltételt is a felbonthatóságra.

6.4. DEFINÍCiÓ. A K kódot prefix kódnak nevezzük, ha egyetlen kódszó sem valódi (prefixuma) egy másik kódszónak.

kezdőszelete

Ezen definíció alapján azok a kódok, amelyek egyenlő hosszúságú kódszavakból állnak, természetesen valamennyien prefix kódok lesznek. Prefix kód a 6.1. példában szereplő kód is.

6.1. TÉTEL. Minden prefix kódfelbontható. BIZONYÍTÁS. Tegyük fel, hogya K = {1Xl> 1X2 , ••• , IX,J prefix kód nem felbontható. Ez azt jelenti, hogy létezik olyan a bináris sorozat, amelyet legalább két különböző módon tudtunk kód szavak szorzatára felbontani. Legyen a = 1X;,lXi , . .. lX i , és a = = IX). l.;::; IX;••• • IX).• Jelöljük l-lel azt a legkisebb számot, melyre IX,' ~ IX).• Ilyen l az indit l l rekt feltevésünk szerint létezik. A

valamint az

egyenlőségből

azt kapjuk, hogy

és itt lXi , ~ 1Xj,' De ekkor az lXi , és IXh szavak közül a nem hosszabbik kezdőszeletc lesz a másiknak, ami ellentmond a prefix tulajdonságnak. / A bizonyításban felhasznált bináris szavak struktúráját mutatja a 6.3. ábra. O

I,

,-

0(.

0(.

6

\

ol

\

0(.

1,

0(.

)/

f

6.3. ábra

Jelölje

ll>

12 ,

••• ,

l" rendre az 1X1 ,

1X 2 , . • . , IXn

K-beli kódszavak hosszát.

6.2. TÉTEL (McMILLAN-EGYENLŐTLENSÉG). Ha a K ható, akkor

=

{lXI' 1X 2 , •• • ,

IXn} kódfe/bont-

n

L

2- I ,

;:§

l.

i=l

259

BIZONYÍTÁS.

Legyen I tetszőleges természetes szám. Emeljük a

n

L 2- l; összeget a

1=1

t-edik hatványra : --

"I..J

2-(1, l +1, 2 + . .. +1;, ) -

(it. i•• . ..• it )

Az utolsó kifejezésben mindazokra az (li, i2, .. . , it) t-esekre kell összegeznünk, melyekre 1 :§ íj :§ n és j = 1, 2, ... , t. Az li, + li. + .... + li, szám azonban éppen az OCi,OCi • ••• oc;, bináris sorozatnak a hossza, ez pedig nem más, mint az a;,a;• ... ai, elsődleges közlés kódolása. Jelöljük L(a;,ai2 •• • a;)-vel ezt a hosszat. Akkor

L

2-(/;,+1;.+ .. . +1,,)

(ih i 2.. . 0' i, )

L

= Qi

Q

1

i

2

2- L (o" Oi,··Oi,).

•.•

ai,

Ebben az összegben tehát az összes t hosszúságú a;Pi 2 • • • ai, elsődleges közlésre kell összegeznünk. Jelöljük most N(t, r)-rel azoknak az ai,ai• ... ai, elsődleges közléseknek a számát, melyekre L(ai,ai• ... ai,) = r és legyen M a K-beli kódszavak hoszszának a maximuma. Ekkor világos, hogy t :;§ Ebből

L(a;,ai• ... al,)

:§

M· t.

azt kapjuk, hogy

L ail a ie '"

2- L (a i ,oi,

M ·t

. .. ai,) =

ai,

L N(t, r) ·2-'.

r=t

Másfelől tudjuk, hogy N(t, r) :§ 2'; ha ugyanis 2'-nél több elsődleges közlést kódolnánk r hosszúságú bináris sorozatokkal, akkor a kódolás nem lehetne felbontható. Így tehát

M.,

M.,

M.,

L N(t,r)·2-':§ r=t 1: 2'·2-' = rLI = =t

(M-I)·t+1.

,=1

Vagyis azt kaptuk, hogy tetszőleges t természetes számra teljesül az alábbi egyenlőt­ lenség:

(t 2-/i)t

:§

(M -I)t+ l.

1=1

n

Ha

L 2- Ii :>

I Jenne igaz, akkor elég nagy t-re nem teljesülne az előbbi egyenJőtlen-

i=l

ség.

D n

A

L 2-I; :§

l.egyenlőtlenség csak szükséges feltétele a felbonthatóságnak. Könnyű

i=l

megadni olyan nem felbontható kódot, amely szintén eleget tesz az lenségnek.

260

előbbi egyenlőt-

n

6.3. TÉTEL. Ha

I

2- I, ;§ J, akkor létezik olyan K

= {<Xl, (;(2'

.•. , <Xn}

prefix kód,

;=1

melyben a kódszavak hossza ll' 12 ,

•• "

ln'

BIZONYÍTÁS. Az általánosság megszorítása nélkül feltehető, hogy II ;§ /2 ;§ ... ;§ Vizsgáljuk meg most az alábbi számsorozatot :

'n'

ql = O; q2

= 2- I,;

q3

= 2- /'+2- 12 ;

Nyilvánvaló, hogy O;§ qi -< 1 minden i = 1, 2, .. " n-re. Válasszuk lXi-nek a qi ketted es tört alakban való leírásánál a törtrész első li darab számjegyét. Ekkor h >- i esetén

Így a qh és q; kettedes leírásában már az első li helyen eltérést tapasztalhatunk, azaz az IX i kód szó nem lehet kezdőszelete IX,,-nak. D Két kódot ekvivalensnek nevezünk, ha ugyanannyi kódszót tartalmaznak, és kódszavaik megfeleltethetők úgy egymásnak, hogyahosszuk páronként megegyezzék. A 6.2. és a 6.3. tételből így az alábbi állítást kapjuk. 6.4. TÉTEL. dot. D

Tetszőleges

felbontható kódhoz találhatunk vele ekvivalens prefix kó- .

3. Optimális kódok Tegyük fel, hogy egy magyar nyelvű szöveget kell kódolva továbbítanunk. Ebben a szövegben az egyes betűk különböző gyakorisággal fordulhatnak elő : magyar szövegben igen sok az a, e stb. betű, míg pl. az ö, c,fstb. betűk sokkal ritkábban szerepelnek. Ahhoz, hogy a kódolt szövegek általában minél rövidebbek legyenek, tehát hogy minél gyorsabban tudjuk az információt továbbítani, a leggyakrabban előforduló betűkhöz célszerű a legrövidebb kód szavakat hozzárendelni, míg a ritkábbakhoz esetleg hosszabb kódszavak is tartozhatnak. Tegyük fel, hogy adva van egy F jelforrás, amely az A = {ab a2, .. " an} ábécé betűit véletlenszerűen bocsátja ki, méghozzá az egymás utáni jeleket egymástól füg261

getlenül. JelöljePi annak valószínűségét, hogy az F által kibocsátott jel aj' A továbbiakban feltesszük, hogy ezekre a valószínűségekre teljesülnek a Pi;> O (i = 1,2, "', n) n

feltételek, továbbá a

L Pi

= l egyenlőségnek is fenn kell állnia.

j=1

Apj valószínűség tehát azt mutatja meg, hogy elég hosszú, pl. M számú jeiből álló jelsorozatot véve a benne előforduló aj-k száma közelítőleg pj' M. Tegyük fel, hogy az F jelforrás által kibocsátott jelek A ábécéjét a K = {iX b iX 2 , . . • , iXn } felbontható kóddal kódoltuk, és fl, 12 , ••• , fn jelentse az iXb iX 2, ••• ,iXn kódszavak hoszszá t. Miként az előbb megállapítottuk, az aj E A betű egy M hosszúságú aj,aj, ... ajM jelsorozatban átlagosan Pi ·M-szer fordul elő. Mivel az iX j kódszó hossza lj, ezért az előbbi jelsorozatnak megfelelő iXj,iX j , • • • iX jM kódolt közlésben az iX j kódszavakból adódó összhossz éppen lj 'Pi' M. Ha most i-re összegezünk, akkor az iXj,iX i, ... iXj~/ közlés átlagos hosszát nyerjük: n

11 ·Pl·M+/2 ·P2· M + ... +11l·Pn·M= M·L,Pi·/j. j=1 /I

Világos tehát. hogy ha a

L

pJj

összeg értéke csökken, akkor csökken az iXj,iX i ,

••• iX ib!

1=1

kódolt közlések átlagos hossza is. Az eddigiekből már világos lesz az alábbi definíció jelentése és fontossága. II

6.5.

DEFINÍCiÓ.

A

L Pj ·/

j

számot a K kód F forrás melletti

költségéne~

nevezzük.

j=1

Rögzítsük most az F jelforrást (azaz az A ábécé betű ihez tartozó Pi ket). A K kód F forrás melletti költségét L(K)-val fogjuk jelölni.

valószínűsége­

6.6. PEFINÍCIÓ. A KO felbontható kódot az F jelforrásra nézve optimálisnqlf mondjuk, ha tetszőleges K felbontható kód nak az F mellett számított L(K) költsége nem kisebb L(KO)-nál.

Az optimális kódok tehát a kódolt közlések átlagos hosszát minimalizálják . ~

6.5.

TÉTEL. Tetszőleges

F forráshoz létezik optimális prefix kód.

BIZONYÍTÁS. Legyen K~ tetszőleges felbontható kód, melynek a~ F jelforrás mellett számított költsége L(K'). (Az eléggé nyilvánvaló, hogy valamilyen K' felbontható kód mindig létezik.) Legyen továbbá K olyan felbontható kód, amelynek F-hez tartozó költsége kisebb L(K')-nél, és jelölje lb /2, ...• l" a K-beli kódszavak hosszát. Ekkor teljesülnie kell az alábbi egyenlőtlenségeknek minden i = l, 2, ... , n-re:

262

Ha ugya nis ez valamilyen i-re nem lenne igaz, akkor az adódna, hogy I

L(K)

~

Pj ·lj

>-

pj' [

L(K ----p;-+ 1

) ]

~

ez pedig ellentmondana a K kiválasztásának. Másfelől, lj Tekintsük tehát az alábbi egyenlőtlenségrendszert:

[L~/) + 1

1

[L~~/) + 1] ,

12

~

1 nyilvánvalóan teljesül.

J.

l :2 II :2 :2

I

L(K ),

:2

n

L

2-It :2 1.

i= l

E rendszernek van megoldása, hiszen a K'-höz tartozó I~, I~, .. . , I~ számok kielégítik az előbbi egyenlőt1enségeket. Másrészt viszont a természetes számok körében csak véges sok megoldás létezhet. Van tehát a megoldások között egy olyan If, 19, ... , I~ n

megoldás is, melynél a

L Pilr kifejezés értéke minimális. Ha ehhez a

sorozathoz meg-

i=1

szereplő

konstruáljuk a 6.3. tétel bizonyításában nézve optimális lesz. O

6.7. DEFINÍCIÓ. A H(F)

n

1

i=1

Pi

= L Pi ·log 2 -

prefix kódot, akkor ez az F forrásra

számot az F forrás entrópiájának nevezzük.

6.6. TÉTEL (SHANNON TÉTELE AZ ÚN. ZAJMENTES CSATORNÁKRA). Egy F jelforráshoz tartozó tetszőleges Kfelbontható kódra L(K) ~ H(F) teljesül. BIZONYÍTÁS. Tekintsük a

H(F)-L(K) =

következő

különbséget:

1 (1) log2--ft Pj L P; (1 log2 --log 2 ) = L Pj log2 -2-li). P; Pi Ln -Pi· lo g2- - Ln p;·li = Ln P; Pi ; = 1 ;=1

=

i=1

=

n

;=1

2

1

i

n

(

;=1

263

~

6--

Jól ismert összefüggés, hogy tetszőleges pozitív x-re lnx ;§ x- l; l ;§ ln 2 ·(x-l) adódik, és így már könnyen kapjuk az állítást: n 1: Pi' ( log2 -2-Ii) i=1 Pi

H(F)-L(K) =

;§

ebből

log2 x

n p. (2-Ii) 1 'n ) 1: -' . - - 1 = -.1 L (2- ;)-1 i=1 ln 2 Pi ln 2 V=1 1

(A levezetés végén a már igazolt McMillan-féle egyenlőtlenséget használtuk.) .---...

6.7. ;§

;§

;§

O.

D

TÉTEL. Az F jelforráshoz tartozó KO optimális kód költségére teljesül az L(KO) H(F)+ 1 egyenlőtlenség.

;§

Jelölje ral az a szám" fölső egész rész"-ét, azaz a legkisebb olyan egész

BIZONYfTÁS.

szám0t, amely nem kisebb, mint a. Legyen li

r

= lOg2

;J

Ekkor:

n

Mivel a fentiek szerint az Ih 12 ,

••• ,

ln számokra teljesül a

L 2-

li

;§

1 egyenlőtlenség,

i=l

ezért a 6.3. tétel szerint megadható egy olyan K = {lXh .. " IXn} prefix kód, melyben a kódszavak hossza éppen ll' 12 , ••• , ln' Jelölje K' az így adódó kódot, KO pedig az optimális kódot. Akkor

A 6.6. és a 6.7. tételek összekapcsolásával tehát azt kapjuk, hogy az F forráshoz tartozó KO optimális kód költségére igazak az alábbi becslések: H(F)

;§

L(Ko)

;§

H(F)+ l.

6.8. DEFINÍCIÓ. A K felbontható kódot teliesnek nevezzük, ha tetszőleges a véges bináris sorozatot véve a vagy kezdőszelete valamely kódszónak, vagy valamely kódszó kezdőszelete a-nak. ---""

6.8.

TÉTEL.

A K kód pontosan akkor teljes, ha K prefix kód, és a K-beli kódszavak n

Ih 12 ,

•• "

ln hosszára

L 2-

l

,

= 1 teljesül.

i=l

BIZONYÍTÁS.

Legyen N

tetszőleges

természetes szám, melyre N

~

max li' Könnyen

látható, hogya K kód pontosan akkor teljes, ha az N hosszúságú bináris sorozatok mindegyike kódszóval kezdődik, tetszőleges ilyen N esetén. Tegyük fel, hogya K =

264

= {CX}> CX2 ,

••• , CXn }

kód teljes. Jelöljük Sj-vel azoknak az N hosszúságú bináris sorozan

toknak a halmazát, melyeknek kezdőszelete CX i. A teljesség következtében n

L ISj I ~. 2N .

és így

Mivel az

CXi

i=1 n

L2

N

-

h ~

kódszó hossza lj, ezért ISj I = 2N "

L 2-

2N , ebből pedig azt kapjuk, hogy

~1

I

,

U Sj = B

N

, .. -

i=1

h.

Így tehát

~ L Felhasználva a McMillan-

~1

n

féle egyenlőtlenséget, az adódik, hogy

L 2- Ii

= I. ;=1 Ha a K kód nem lenne prefix kód, akkor léteznének olyan rxp és rxq kód szavak, hogy n

rxp kezdőszelete lenne rxq-nak. Ez azt jelentené, hogy Sp ~ Sq, és így

U S; = B

N

;=1

.

Ebből

;;i'q

n

L lSd ~ 2

n

N

azaz

,

i=l i;i'q

L

i=l

lSd

>-

2 N adódna. Az előbbi gondolatmenettel tehát azt kap-

n

nánk, hogy

L 2- l ; >-

;=1

l, ami nem lehetséges, mivel a K kód felbontható . n

Megfordítva, legyen K olyan prefix kód , melyre

= 2N és SpnSq

L 2- I; =

n

I teljesül. Ekkor

;=1

=

L 2N - li = ;=1

0. Azt kapjuk tehát, hogy

n

Ez éppen azt mutatja, hogy azaz a K kód teljes. 6.9.

U Si minden N hosszúságú bináris sorozatot

;=1

tartalmaz,

O

TÉTEL. Tetszőleges

optimális prefix kód teljes.

Legyen KO optimális prefix kód, és tegyük fel, hogy KO nem teljes. Ez azt jelenti, hogy van olyan a bináris sorozat, amely nem kódszóval kezdődik. Jelölje M a K~beli kódszavak hosszának maximumát. Ekkor feltehető , hogy a-t a = Pr alakban írhatjuk, ahol {J hossza éppen M. Legyen {J = {J' x, melyben x = Ovagy x = l. Tegyük fel, hogy {J' kezdőszelete az rxq kódszónak. Ekkor csakis rxq = {J'X lehetséges, és {J' nem kezdőszelete egyetlen más KO-beli kódszónak sem. Cseréljük ki cxq-t {J'-vel. Ilyen módon olyan prefix kódhoz jutnánk, melynek költsége kisebb lenne, mint a KO optimális kódé. {J' tehát nem lehet kezdőszelete egyetlen KO-beli kódszónak sem. Cseréljük ki ekkor a KO-beli maximális hosszúságú kódszót {J'-re. Így ismét prefix kódot kapnánk, melynek a költsége kisebb lenne, mint az optimális kódé. Újra ellentmondáshoz jutottunk, következésképpen a KO optimális prefix kód teljes. O BIZONYÍTÁS.

265

FELADATOK

6.1. Állapítsuk meg az alábbi kódokról, hogy felbonthatók-e vagy sem:

,

{OO, 01,10,11,110, lll}; {OO, Ol, :1 0, 110, 1110, 1111}.

6.2. Adjunk meg olyan prefix kódot, melyben a kódszavak hossza: 3, 3, 3, 3, 3, 3, 3, 4,4. 6.3. Legyen megadva egy F jelforrás, amely az {a, b, c, d, eJ} ábécé betűit az alábbi valószínűséggel bocsátja ki: 0,3; 0,2; 0,2; 0,15; 0,1 ; 0,05. ~\'o,b aj Számítsuk ki az F forrás H(F) entrópiáját. b J Keressünk olyan prefix kódot, melynek F-hez tartozó költsége nem nagyobb H(F) + l-nél. 6.4. Adjunk meg egy teljes kódot, melynél a kódszavak hossza: 2, 2, 2, 3, 3. 6.5. Vizsgáljuk meg, hogy az előző rész eredményei igazak maradnak-e olyan F forrásokra is, melyek egyes jeleket esetleg Pj = O valószínűséggel bocsátanak ki magukból.

4. Az optimális kód Huffmann-féle konstrukciója Az előzŐ. részben a 6.5. tétellel megmutattuk, hogy tetszőleges F jelforráshoz, azaz {pj: i = l, ... , n} valószínűségi eloszláshoz létezik optimális kód. Most egy olyan algoritmust ismertetünk, amellyel ezt az optimális kódot meg is tudjuk konstruálni. Tegyük fel, hogy az F jelforrás kimenő ábécéje A = {al' a 2 , •• " an}, az egyes betűkhöz tartozó valószÍnűségek pedig rendre Pb P2, .. . , Pm ahol Pl ~ P2 ~ ... ~ Pn' 6.10. TÉTEL. Az F jelforráshoz létezik legalább egy K = {<Xl' <x 2 , • • • , <Xn} optimális prefix kód, amelyre II ;§ 12 ~ .•• ;§ ln_l = lm és az utolsó két kódszó <xO és <xl alakú.

KO optimális prefix kód. Tegyük fel, hogy lj

lj valamely i -< j párra. Ekkor tudjuk, hogy Pj ~ Pj' Ha Pj = Pj' akkor az <Xi és <Xj kódszavakat kicserélhetjük : rendeljük hozzá ezentúl aj-hez <xj-t, aj-hez pedig <Xrt. így egy olyan prefix kódhoz jutunk, melynek költsége ugyanannyi, mint a KO kód költsége, tehát ez a kód is optimális, másrészt legalább eggyel csökkent az olyan i -< j pároknak a száma, melyekre l; >- ~. Az ilyen eseteket tehát lépésenkénti cserékkel kiküszöbölhetjük. Ha viszont Pj >- Pj lenne igaz, akkor az lj-lj >egyenlőtlenségből azt kapnánk, hogy Pj'(!j-Ij ) >- Pj·(lj-~), vagyis: Pj·/i+Pj·~ >- Pi · lj+Pj·/j. Ebből viszont az adódna, BIZONYÍTÁS. Legyen

°

266

>-

hogy az rt. i és az rt.j kódszavak felcserélésével az optimálisnál alacsonyabb költségű kódot kapnánk, ami nem lehetséges. Tegyük most fel , hogy 1"_1 <: l". Jelölje {J az {J,Jl kódszó ln_l hosszúságú kezdőszeletét. Az világos, hogy {J nem lehet kezdőszelete egyetlen másik kódszónak sem, mivel hossza . nem kisebb az (J.b (J.2, . . " (J.n_l hosszánál. Másrészt az is nyilvánvaló, hogy az előbbi kódszavak egyike sem lehet kezdőszelete {J-nak, mivel ekkor (J.ll-nek is kezdőszelete lenne. Cseréljük ki tehát (J.n -et {J-ra. Így egy olyan prefix kódot kapnánk, melynek a költsége kisebb lenne az optimális kód költségénél. Ily módon tehát csakis ln_l = l" állhat fönn. Tegyük fel végül, hogy a két utolsó szó nem (J.O és (J.l alakú. Ez aztjelenti, hogy nemcsak az utolsó jegyükben térnek el egymástól, azaz: IXn_ l = {J'x', (J." = {J"x", és itt {J' ;;: {J". Tekintsük most a {J' i' sorozatot. Ha ez kódszó, akkor cseréljük ki egymással {J'i'-t és (J.n-t . Ilyen módonkódunk éppen a kivánt alakban áll elő. Ha {J 'X' nem kódszó, akkor a p' sorozat az (J.n_l-et kivéve nem kezdőszelete semelyik másik kódszónak sem, s {J' -nek sem kezdőszelete az (J.h (J.2, ... , (J.Jl_2, (J.1l szavak egyike sem. (J.Jl_l-et {J' -re cserélve tehát ismét prefix kódhoz jutnánk, ennek viszont alacsonyabb lenne a költsége, mint a KO optimális kódé. O 6.11. TÉTEL. Legyen megadva egy F jelforrás az A = {aba~, ... , an} kimenő ábécéveI és a betűkhöz tartozó Pl ~ P2 ~ ... ~ Pn valószínűségekkel. Legyen továbbá K = {CI.I , ::1. 2 , • • • , (J.n} az F forráshoz tartozó optimális prefix kód. Tegyük fel, hogy Pi = ql +qt, és Pl ~ P2 ~ . . . ~ Pi-l ~ Pi+! ~ ... ~ Pn ~ ql ~ Q2' Ekkor a K' = = {Otb (f.z, . .. , (J.i_l, OtHI , .. " (J.m (J.iO, Ot)} kód optimális prefix kód lesz arra az F' forrásra nézre, melynek kimenő ábécéje A' = {ab a2 , • •• , an+!}, a betűkhöz tartozó valószínűségek pedig rendre Pb P2, ... , Pi-l, Pi+l' ... ,P", qb q2' BIZONYÍTÁS. Mivel K prefix kód, ezért K' is nyilván rendelkezni fog a prefix tulajdonsággal. Világos továbbá az is, hogy L(K') = L(K)+ Pi' A tétel igazolásához tehát elegendő azt megmutatnunk, hogy F-höz létezik olyan K* optimális kód, melynek költségére L(K*) ~ L(K) + Pi teljesül. A 6.10. tételből adódik, hogy P-höz létezik olyan K" optimális prefix kód, amelyre K* = {,8h P2' .. " ,8/l-1, ,80, ,8l}. Vizsgáljuk most meg az F jelforráshoz tartozó K" = = {{JI>"" Pi-h{J,,8i'" ·,,8n-l} kódot. A,8h,82, .. ·,,8n_Ikódszavaknemkezdószeletei ,8-nak, s nem is egyeznek meg vele, mivel K * prefix kód volt. Másrészt {J sem lehet kezdőszelete ezen kódszavak egyikének sem. Így tehát KU is prefix kód . A K* és KU kódok F -re, ill. F-re vonatkoztatott költségei között az L(K*) = L(K )+ Pi összefüggés érvényes. Mivel K optimális kód F-re nézve, ezértL(K) ;§ L(K"), és így L(K*) ~ U

~L(K)+p;'

O

A 6.11. tétel módot ad arra, hogy az n + l betűt kibocsátó jelforráshoz tartozó optimális kód keresését visszavezessük az n betűs jelforrás esetére.

267

Legyen ugyanis az F jelforráshoz tartozó ábécé A = {al, a2, ... , a", an+1}' és a Pl ~ P2 ~ ... ~ Pn ~ Pn+l' Tekintsük ekkor azt az F' jelforrást, melynek kimenő ábécéje B = {bb b2 , ••• , bn }, a valószÍnűségek pedig PI ~ P2 ~ .. . ~ Pi-l ~ Pn+Pn+l ~ Pi ~ .. . ~ Pn-l' Ha K' = {cxb CX2, ••• , CXn } @ptimális az F'-re nézve, akkor a K = {CXb CX 2 , •• " CX i_ b CXi+b •• " CX'" cxiO, cx il} kód P-re nézve lesz optimális. Az ábécé betűszámának fokozatos csökkentésével tehát végül ahhoz a feladathoz jutunk el, melynél kétbetűs ábécéhez kell optimális kódot megadnunk. Ebben az esetben viszont a {O, l} kód nyilván optimális lesz. A fent ismertetett, az optimális kód előállítására vonatkozó eljárást felfedezőjéről, az amerikai Huffmannr61 nevezték el Huffmann-féle módszernek. Az eljárás demonstrálására nézzünk meg egy konkrét . példát. Legyen A = = {al, a2, a3, a4, as, aG, a7}, a valószÍnűségek pedig 0,20; 0,20 ; 0,19; 0,12; 0,11; 0,09; 0,09. Az algoritmus egyes lépéseit a 6.1. és a 6.2. táblázatokban ábrázoltuk. betűknek megfelelő valószÍnűségek

J

6.1. táblázat. Az ábécé redukálása 0,20 0,20 0,19 0,12

0,11 0,09 0,09

J J

0,20 J~ 0,23 0,20 0,20 0,19 0,20 0,18 0,19 O,12J 0,18 0,11

0,37 0,23 0,20 0,20

J

J

J

Jl fl

6.2. táblázat. A kódok 10 11 OOO

10 J

11 OOO

010 f001 011 OlOl OOIOJ 0110011

-01 10 11 OOO 001

01 IOJ

J

r

0,40 0,37 J~ 0,23

0,60 0,40

előállítása

00 01

Jj

1

0 1

11

A 6.1. táblázatban az ábécé betűszámának csökkentését követhetjük nyomon, amíg el nem jutunk a kételemű ábécéhez. Az ehhez tartozó optimális kód a {O, l} halmaz. Visszafelé haladva ugyanezen az úton, az egyre növő ábécékhez tartozó optimális kódokat kapjuk meg (6.2. táblázat).

268

5. Hibajavító kódolás A gyakorlati esetek többségében az információs csatorna korántsem működik mindig a kellő biztonsággal. A csatorna alapzajának nevezett hibák következtében a vevőkészülékhez érkező üzenet lényegesen különbözhet attól, ami az adókészülékből kiindult (6.4. ábra).

rVI

' Ol

'o ...

odóberendezés f-

r-

r-

... o

...

+'

ol

.g "o

'0

'0 C

"o

-

.:t~

::>

o

6.4. ábra

A most

l

'0

::>

ir,forrnóciós csatorna

J

o

r-

'"

' 0 ' 41 -N OQl

"0"0

'o

C .:L 41

l

ev

"041

'--

'--

ké>do-'t koz-Ies

-

vevőberende:tés

OlI..

.o

-o

'--

kódolt kÖz.lés

"o

E

E

ol

..o

'---

...

o

+

zaj

következő

két részben olyan módszereket vizsgálunk, melyekkel azonos hOSS~Ú. kódszavakból álló bináris kódok esetén védekezni tudunk a zaj okozta ~z ilyen típusú kódolásoknál a kódszavakat a továbbiakban blokkoknak hibá is fogjuk nevezni, a kódszavak hosszát pedig blokkméretnek. Ezek a kódok mind felbonthatók lesznek (hiszen rendelkeznek a prefix tulajdonsággal). Ilyen esetekben egy kódolt közlés hossza mindig osztható lesz a blokkmérettel. Legyen a K = {tXt. tX 2 , ••• , tXm} kódhoz tartozó blokkméret n, s legyen t tetszőleges olyan természetes szám, amely nem nagyobb n-nél. 6.9. DEFINÍCIÓ. Azt mondjuk, hogy az információs csatorna legfeljebb t egyedi hibát okoz, ha a csatorna alapzajának hatására tetszőleges blokkban ,legfeljebb t jel értéke változik meg. (A megváltozott jelek a blokkon belül bármilyen elrendező désben előfordulhatnak.) A zajból eredő hibák mérésének másik formája az ún. t hosszúságú kötegek módszere. Ilyenkor az a követelmény, hogy egyazon blokkon belül t darab egymás mellett álló jel ne változhassék meg. Mi a továbbiakban az egyedi hibák esetére szorítkozunk, s általában csak hibáról fogunk beszélni. Könnyen megadhatunk olyan kódokat, amelyekkel 1 hibát fel tudunk ismerni, sőt esetleg ki is tudjuk javítani azt. Ha a kódszavak mindegyike olyan, hogy a szó első és második fele megegyezik, akkor az 1 hibát okozó zaj a "félszavaknak" legfeljebb az egyikét tudja elrontani. Így a dekódolásnál észrevehetővé válik, ha a szavak első, ill. második fele különbözik egymástól. Hasonlóan ehhez, ha minden kódszónak első,

269

második és harmadik harmada megegyezik, akkor dekódolásnáll hibát még ki tudunk javítani, ugyanis azt a sorozatot fogadjuk el igazinak, amely legalább kétszer szerepel. 6.3. PÉLDA. Tegyük fel, hogy adva van egy előbbi típus ú " l-hibajavító" kód, s ennek egyetlen kódszavát, a 010010010 szót küldtük el üzenetként. Tegyük fel továbbá, hogy a vevőkészülékhez a 010110010 sorozat érkezett. Hasonlítsuk ebben össze .az egyes harmadokat : 010, 110,010. A kétszer előforduló 010 sorozatot igazinak véve ki tudjuk következtetni az eredetileg elküldött 010010010 kód szót. Az azonos hosszúságú kódszavakból álló kódok fontos fogalma. 6.10. DEFINÍCIÓ. Legyen megadva a K

jellemzője

az ún.

sűrűség

= {O:l' OG2, ... , OGm } kód, melyben a kódszavak

száma m, a blokkméret pedig n. Ekkor a kód

sűrűsége alatt a log2 m számot értjük. n

A sűrűség tehát lényegében azt méri, hogy milyen a K-beli kódszavak számának aránya a B n halmaz számosságához, azaz az összes n hosszúságú bináris sorozatok számához viszonyítva. Az előbbiekben ismertetett kód sűrűsége pl., amellyel l hibát n 2 / )

n le l tud tun k'Ismerni,. log2(2

l"

. ,log2(2n / 3 ) ezt a hibat, n

= 2'1 ' a

, 'k k o'd'e ped'19, ameIIyel 'Javltam , ..IS tu d tuk masl

1

= 3'

A hibajavító kódok elméletében alapveíŐen fontos az ún. Hamming-távolság fogalma. (A továbbiakban általában csak távolságnak fogjuk nevezni.)

6.11. DEFINÍCIÓ. Az o: és {3 E B n vektorok e«(X,{3)-val jelölt (Hamming-) távolsága alatt azoknak a pozícióknak a számát értjük, amelyeken a vektorok eltérnek egymástól. 6.4.

PÉLDA.

e(OOl, 111) = 2, e(1001, 0000) = 2.

A e( 0:, {3) távolságfüggvény rendelkezik az alábbi tulajdonságokkal : 1. eCo:, {3) ~ O;

2. e( 0:, {3) = O akkor és csakis akkor teljesül, ha o: = {3; 3. e(o:,{3) = e({3, 0:); 4. eCo:, {3)

:§

eCo:, y)+ e(y, {3) (ez az ún.

háromszög-egyenlőtlenség).

Az első három tulajdonság nyilvánvaló. Igazoljuk most a negyediket. Jelölje P(o:, {3) azoknak a pozícióknak a halmazát, amelyeken rx és {3 eltérnek egymástól. A definíció értelmében tehát: e(OG, {3) = 1P( rx, {3) I. Így a negyedik tulajdonság következik abból, hogy P(rx, {3) <:;;; P(rx, y) U P(y, {3). Ez az utóbbi összefüggés pedig szintén nyilvánvaló, 270

hiszen ha egy pozíció nincs benne sem a P( IX, y), sem a P(y, f3) halmazban, akkor ezen a helyen az IX, f3 és y vektorok megegyeznek, és így a kiválasztott pozíció nem lehet eleme a P( 17., f3) halmaznak sem. Ax olyan függvényt, amely kielégíti az 1- 4. feltételeket, metrikának nevezzük. Az elmondottak szerint tehát a Hamming-távolság metrikát ad meg a Bn alaphalmazon. Ha az információs csatorna zaja legfeljebb t hibát okoz, akkor ez azt jelenti, hogy tetszőleges 17. kódszóból olyan f3 vektort kapunk, melyre Q(IX, f3) :§ t. 6.12. a

DEFINÍCIÓ. Tetszőleges

kylönböző

K kódra kódtávolságnak nevezzük és d(K)-val jelöljük K-beli szavak egymás közti távolságainak minimumát.

6.5. pÉLDA. A fejezet elején ismertetett, l hibát hibát javító kód é pedig 3.

felismerő

kód kódtávolsága 2, az l

6.12. TÉTEL. Tetszőleges K kód pontosan akkor alkalmas t darab hiba felismerésére, ha d(K) ~ 1+ 1. Elégségesség. Tegyük fel, hogy az 17. E K kódszóban legfeljebb t hiba keletkezik, és így egy f3 vektort kapunk. Mivel Q(rx, f3) :§ t, továbbá a K-beli kódszavak távolságának minimuma nagyobb, mint t, ezért f3 ~ K. Így tehát a hibákat arról ismerhetjük fel, hogy a beérkezett vektor eleme-e a K kódnak vagy sem. Szükségesség. Ha d(K) :§ t, akkor ez azt jelenti, hogy vannak olyan 17. és f3 kódszavak, melyek távolsága Q(rx, f3) = r :§ t. Ekkor azonban egy legfeljebb t hibát okozó csatornában előfordulhat, hogy az 17. szó éppen f3-ra változik. Így f3 vételénél nem lehet eldönteni, hogy az adóból kiinduló kódszó 17. volt-e, s csak a csatorna zaja "torzította" f3-vá, vagy pedig f3 volt a kiinduló kódszó, és változás nélkül érkezett meg a vevőberendezéshez. O BIZONYÍTÁS.

1 hiba felismerésére egyszerű módszert ad az alábbi B~ kód. B~ álljon mindazokból az n hosszúságú bináris vektorokból, amelyekben páros számú egyes szerepel. Könynyen látható, hogy d(B~) = 2, így az előző tétel szerint B~ alkalmas lesz l hiba felismerésére. Itt a felismerés algoritmusa is igen egyszerű: dekódoJáskor számolnunk kell a blokkonként beérkező egyesek számát. Ha ez a szám páros, akkor a blokk hibátlan, ha pedig páratlan, akkor hibás blokkot kaptunk. Ezért is nevezik ezeket a B~ kódokat paritásellenőrző kódoknak. Egyszerűségük miatt a gyakorlatban is igen széles körben nyernek alkalmazást. Mivel IB~ I = 2n - l , ezért a B~ kódok sűrűsége igen magas: n-l = 1- ..!... Ez a szám különösen akkor

n

elején

n

szereplő, ~ sűrűségű 1 hibát felismerő

tűnik nagynak, ha egybevetjük a fejezet kóddal. 271

6.13. DEFINÍCIÓ. Tetszőleges o( E B n esetén S,(O() jelölje azoknak a fJ E B n vektoroknak a halmazát, melyekre e(fJ, O() :§ t. Ezt a halmazt o( középpontú, t sugarú gömbnek nevezzük. 6.6. PÉLDA. Sl«ool» = {(OOO), (011), (101), (001)}. Vegyük észre, hogy ha sXO() és S,(fJ) metszete nem üres, akkor eCO(, fJ) :§ 2t. Legyen ugyanis y E S,(O()nS,(fJ). Ez aztjelenti, hogy e(O(, y):§ t, e(fJ, y):§ t. A háromszögegyenlőtlenségből így azt kapjuk, hogy

eCO(, fJ)

:§

eCO(, y)+ e(fJ, y)

:§

21.

A fenti észrevételnek igaz a megfordítása is. Ha eCO(, fJ) :§ 21, akkor S,(O() és S,(fJ) metszete nem üres. Tegyük fel ugyanis először, hogy eCO(, fJ) :§ t. Ekkor nyilván fJ E S,(IX), és így S,(fJ) nS,(O() nem üres. Legyen most t -< eCO(, fJ) :§ 2t. Ekkor azoknak a pozÍcióknak a száma, amelyeken o( eltér fJ-tól, nagyobb, mint t. Válasszunk ki ezek közül t darabot, és változtassuk meg fJ-t ezeken a helyeken. Így olyan y vektort kapunk, melyre e(fJ, y) = t, tehát y E S/(fJ), másrészt eCO(, y) = eCO(, fJ)- t :§ 21- t = t, vagyis y E S/(O().

6.13. TÉTEL. A K kóddal pontosan akkor lehet t hibát javítani, ha d(K) teljesül.

~

2t+ l

BIZONYÍTÁS. Elégségesség. Rajzoljunk a kódszavak köré egy-egy t sugarú gömböt. A d(K) ~ 2t+ l feltétel ből következik, hogy ezek a gömbök nem metszhetik egymást. Másrészt y legyen olyan vektor, amelyet az o( vektorból kaptunk, legfeljebb t helyen megváltoztatva azt. Mivel eCO(, y) :§ t, ezért y E S,(O(), s a kódszavak köré rajzolt t sugarú gömbök diszjunktsága miatt y nem tartozhat egyetlen másik gömbhöz sem. Dekódoláskor tehát mindössze annyi a feladatunk, hogy meghatározzuk annak az egyetlen gömbnek a középpontját (jelen esetben O(-t), amelybe a kapott y vektor tartozik. Szükségesség. Tegyük fel, hogy d(K) :§ 2t. Ekkor vannak olyan o( és fJ kódszavak K-ban, melyekre az S/CO() és az S/(fJ) gömbök metszete nem üres, pl. tartalmaz egy y vektort. Mivel eCO(, y) :§ t és e(fJ, y) :§ t, ezért a y vektort O(-ból is, fJ-ból is megkaphatjuk egy legfeljebb t hibát okozó csatornán. Így a y dekódolásánál nem tudhatj uk, hogya kiinduló kódszó o( volt-e vagy fJ, vagyis a hibát nem tudjuk egyértelműen korrigálni. D FELADATOK 6.6. Számítsuk ki a K = {OOlI, 1100, 1111, OOOO} kódhoz tartozó kódtávolságot. Milyen hibafelismerési, ill. hibajavítási lehetőségeink vannak ennél akódnál ? 6.7. A négy hosszúságú vektorok B4 halmazába hány diszjunkt l sugarú gömböt tudunk beírni?

272

VV4.-,.J,,' _I -

'
..-(..,(J~:\f

6. Lineáris kódok. Hamming-kódok Legyenek IX = (al, a2, ... , ali? és {J = (bh b 2 , • • • , bn) bináris n-esek. Az IX és {J vektorok IX+ {J összege alatt a y = (al + bh a2+ b2 , ••• , an + bn) n-est értjük, melyben az a j b j összegek modulo 2 értendők. Az IX és {J vektorok (IX, (J) skaláris szorzata alatt az albI +a2 b2 + ... +anbn összeget értjük, ahol ajb j az a; 'es b j elemek konjunkciója, és az összeget ismét modul o 2 kell venni. Ha q bináris konstans (azaz vagy 1), akkor az IX vektornak q-val vett szorzata: q'lX = (q . ar. q 'a 2 , •• • , q ·an), azaz 1·1X = IX és O' IX = O. (Itt az utóbbi egyenlőség jobb oldalán álló a csupa O-ból álló vektort jelenti.)

+

°

°

6.14. DEFINÍCIÓ. Az IX vektor W(IX) súlya alatt az IX = (al' a2 , nem nulla komponensek számát értjük.

6.7.

-

PÉLDA.

.

w{(O, 0, 1,0, l»

= 2,

Könnyen meggondolható, hogy az ságra igaz a következő összefüggés:

an) vektorban levő

= 3.

w«l, l, 1,0, O» előző

••• ,

részben definiált e(lX, (J) Hamming-távol-

e(lX, (J) = W(IX+{J). 6.15. DEFINÍCIÓ. Azt mondjuk, hogya K kód lineáris, ha következik.

IX,

{J E K-ból (oc+ (J) E K

6.16. DEFÍNICIÓ. A K kód w(K) súlya alatt a K-beli nem nulla szavak súlyának minimumát értjük. 6.14.

TÉTEL.

BIZONYÍTÁS.

Ha K lineáris kód, akkor d(K) = w(K). Legyenek IX és (J olyan kódszavak, melyekre d(K) = e( IX, (J). Ekkor:

d(K) = e(lX, (J) = w(oc+{J)

~

w(K).

Másrészt, legyen y E K olyan, melyre w(K) = w(y). Ekkor, mivel a nulla vektor minden lineáris kódnak eleme, azt kapjuk, hogy

w(K) Végső

= w(y) = w(y+O) = e(y, O)

soron tehát az adódott, hogy d(K)

~

d(K).

= w(K). O

.Azok számára, akik rendelkeznek lineáris algebrai ismeretekkel, nyilván világos, hogy a lineáris kódok valójában nem mások, mint a B n n-dimenziós vektortér alterei a 273

.c...'-eI I'...

kételemű test felett. A valós vektorterektől eltérően itt az összeadást modulo 2 kell végezni, és a skalárral való szorzásnak a konjunkció felel meg. (Műveleti jélekként azonban a szokásos jelöléseket fogjuk használni.) Nem nehéz igazolni, hogy egy sor lineáris algebrai eredmény, amit általában valós vektorterekre szoktak kimondani, érvényes marad a B" vektortérre is. Mivel ezeknek a bizonyítása jól ismert, bizonyítás nélkül közlünk közülük néhányat.

....

6.15. TÉTEL. Ha K ~ Bn lineáris kód, akkor megadható egy k ~ n szám, továbbá léteznek olyan IXI , 1X 2 , ••• , IXk E K vektorok, hogy tetszőleges K-beli IX kódszó egyérteltnŰen felirható mint az lX i vektorok lineáris kombinációja, azaz IX = AIIXI + A21X 2 + .,. + AklXk valamilyen Ai bináris konstansokkal. Az is igaz, hogy másképpen választva egy fll' fl2' ... , fll E K vektorrendszert, amely ugyanezekkel a tulajdonságokkal rendelkezik, annak a számossága szintén k, azaz l = k. O

Az IXh 1X 2, ••• , IXk vektorok a K kód egy bázisát alkotják, k-t pedig a K dimenziójának nevezzük. Mivel az lXi-k lineáris kombinációinak felírása egyértelmű (ilyenkor k

'

azt mondjuk, hogy az lXi-k függetlenek), ezért IKI = 2 . IgyaK kód Legyenek az lX i bázisvektorok a következők: IX j = (an, a j2 , • most azt a mátrixot, amelynek sorai éppen az előbbi lX i vektorok:

lXI) (alI al2 .. . aIn)

G

= ( ~~ = ~2.1 .• ~~2. : : : .~2:' IXk

6.17.

DEFINÍCIÓ.

akI

• • ,

sűrűsége

k

- . n ain)' Tekintsük

.

ak2 .. . akn /

A G mátrixot a K kód generátormátrixának nevezzük.

k-n kM

A K kód tetszőleges kódszava tehát megkapható a kód generátormátrixa sorainak alkalmas lineáris kombinációjaként. Ha két vektor skaláris szorzata 0, akkor azt mondjuk, hogy azok .merőlegesek (ortogonálisak) egymásra .

.--.

6.16. TÉTEL. Legyen K m-dimenziós lineáris kód. Ekkor léteznek flh fl2 ' .. " PII-m lineárisan független vektorok úgy, hogy egy IX E B n vektor pontosan akkor lesz benne K-ban, ha (IX, fl;) = O minden i-re, azaz IX merőleges minden fli vektorra. [J

Jelöljük K J.-sel azt a kódot, amelynek bázisa fll' fl2' . .. ,fln-m' Ezt a kódot a K duálisának nevezzük. KJ. dimenziója tehát n-mo Igazolható, hogya KJ. kó.d független a fll' fl2' . . . , fln-m bázis konkrét megválasztásától. Legyen fli = (bjl, bi2 , . . . , bin ) (i = 1, 2, ... , n-m). Vegyük azt a H mátrixot,

274

amelynek sorai a {Jl> {J'/., ... , {J,,-m vektorok:

A H mátrix tehát a K kód duálisának, KL-nek a generátormátrixa. Ezt a mátrixot a K kód ellenőrző mátrixának is szokták nevezni. A 6.16. tétel értelmében ugyanis az rt. vektor pontosan akkor eleme K-nak, ha

e} írjuk ki a fenti egyenlőséget részletesebben is:

Ez azt mutatja, hogy ha az rt. E K, rt. "" O kódszó súlya t, akkor a H mátrixban van t számú lineárisan összefüggő oszlopvektor. Megfordítva, ha a H-ban van t számú lineárisan összefü ő oszlopvektor, akkor van olyan rt. E K kód szó, melynek súlya t. így tehát K):> t pontosan akkor teljesül, ha a K kód H ellenőrző mátrixából tetszőlegesen kiválasztvai!"?arab oszlopot, ezek Imeansan függetlene8 .~ A 6.13. és a 6.14. tételek alapján a következőket kapjuk: 6.17. TÉTEL. A K lineáris kóddal pontosan akkor lehet t hibát javítani, ha K ellenőrző mátrixában tetszőlegesen kiválasztva 2t számú oszlopot, ezek lineárisan .függetlenek lesznek. O A 6.17. tétel alapján könnyen megadhatjuk lineáris kódoknak egy l hibát javító családját, az ún. Hamming-kódokat. Legyen a blokkméret n = 2/-1 alakú. Ha az ellenőrző mátri x oszlopai közé az összes l hosszúságú nem nulla vektort bevesszük, akkor könnyen látható, hogy semelyik két oszlop sem lesz lineárisan összefüggő. Így az ily módon definiált kód kódtávolsága legalább 3, vagyis 1 hibát tudunk vele javítani. A fentiekben definiált Hamming-kód ~imenziója n-L = 2/ -l-l, sűrűsége pedig

(2/-L-l) _ 1 1+ l

--"2-/ -- - -21-

~

1 logz n --n275

4--

Ez már lényegesen nagyobb sűrűség, mint amilyen a 6.5. példában megadott kódé volt. A Hamming-kódoknál igen könnyen tudunk hibát javítani. Nézzük ezt meg egy konkrét példán. ~

6.8. PÉLDA. Legyen 1= 3. Ekkor a blokkméret 2/-1 = 23 -1 = 7. Az ellenőrző mátrix oszlopaiként tehát a 7 darab 3 hosszúságú nem nulla vektort kell vennünk. Tekintsünk most az oszlopokra mint kettes számrendszerben felírt hároQljegyű. számokra, és rendezzük őket sorba nagyság szerint növő sorrendben. Az alábbi ellenőrző mátrixot kapjuk:

°°°°°

O l 1 l l) H= ( 1 1 1 l 1010101 Itt az i-edik oszlopban éppen az i szám kettes számrendszerbeli alakja áll. Legyen IX eleme a Hamming-kódnak, azaz legyen H .a.T = 0, és tegyük fel, hogy fl olyan vektor, amelyet az a. vektorból kapunk, megváltoztatva annak valamelyik komponensét. Ekkor fl = a.+ e, ahol e olyan vektor, melynek egyedül az előbb kiválasztott pozÍcióján v'a n l, a többi komponense O. Szorozzuk meg H-t {3T-vel. Az alábbiakat kapjuk:

Itt H ·eT a H mátrixnak annyiadik oszlopa, ahányadik komponensét megváltoztattuk IX-nak; ez az oszlop pedig mint kettes számrendszerben felírt szám épp a kiválasztott pozíció sorszámát mondja meg. Ha pl. a. = (0,0,0, l, l, l, l), és ezt a negyedik pozícióban megváltoztatjuk, akkor az így adódó fl vektor: {3 = (O, 0, 0, 0, l, l, l). Erre

{3 = (O, O, O, l, l, l, 1)+(0, O, O, l, O, O, O), és

H·{3T=H·

° °°1

o +H·

l l

1

ez pedig épp 4-nek a bináris alakja.

276

°O °° 1

o

FELADATOK

6.8. Két kódot kombinatorikusan ekvivalensnek nevezünk, ha ellenőrző mátrixaik megkaphatók egymásból pusztán az oszlopaik átrendezésével. Legyen a K lineáris kód dimenziója m. Mutassuk meg, hogy létezik olyan K' kód, amely kombinatorikusan ekvivalens K-val, és amelynek generátormátrixa (lm, Mm, n-tn) alakú, ahol Im az mXm-es egységmátrix, Mm, n-tn pedig valamilyen mX(n-m)-es mátrix. 6.9. Ha a K' kód ellenőrző mátrixa

alakú, akkor a duális kód

ellenőrző

mátrixa:

-H -~ ~~,'.Q...I.~.: ~

j-..L.~.

6.10. Adjuk meg a 6.8. példában szereplő Hamming-kód (vagy egy vele kombinatorikusan ekvivalens kód) generátormátrixát. 6.11. Adjuk meg annak a Hamming-kódnak a generátormátrixát és ellenőrző mátrixát, melynek blokkmérete 15. 6.12. Adjuk meg általánosan a Hamming-kódok generátormátrixát.

7. Standard dekódolási eljárások. A Hamming-korlát Legyen megadva egy K lineáris kód. 1. A lineáris kódok definíciója alapján oc E K és fl E K esetén oc+ fl E K. 2. Tetszőleges oc és fl vektorokra oc+fl = fl+oc. 3. A nulla vektor eleme K-nak, hiszen oc+ oc = Otetszőleges oc-ra igaz. Nyilván oc+ O= oc is mindig teljesül. 4. Általában (-oc)-val jelöljük azt a fl vektort, melyre oc+ fl = O. Esetünkben most (-oc) = oc, így ha oc E K, akkor (-oc) E K. Ez a négy tulajdonság azt mutatja, hogya K kód a vektorok összeadására nézve kommutatív csoportot alkot. De az egész B n is lineáris kódnak, tehát kommutatív csoportnak tekinthető, következésképpen K részcsoportja Bn-nek. Egy jól ismert algebrai tétel pedig azt mondja ki, hogy tetszőleges csoportot egy részcsoportja ún.

277

~O c

b€~K (~

I. 1\.

o...~=bK

~k

~

mellékosztályok diszjunkt uniójára bontja, éS,ezeknek a mellékosztályoknak a számossága megegyezik a részcsoportéval. A továbbiakban nemcsak az előbbi eredményre lesz szükségünk, hanem magára a konstrukcióra is, amellyel ezeket amellékosztályokat megkaphatjuk. Éppen ezért talán nem lesz fölösleges, ha részletesen ismertetjük az eljárást. Legyen K = {O, IX!> IX2, ... , IX 2k_1} ~ B n az adott k-dimenziós lineáris kód. Válasz-. szunk ki egy {Jl ~ K vektort, és képezzük az alábbi halmazt:

Ezek után vegyünk egy {Jz ~ KU (K+ {Ih}) vektort, és most ezzel a vektorral képezzünk egy halmazt az előbbi módon:

K+ {{J2}

=

{{J 2+ 0, {J2+ IX l, {J2+ IX 2,

.•• ,

{J2+IX2k-t}.

Most ismét keressünk egy {J3 ~ KU (K + {{JI}) U (K + {{Jz}) vektort, és képezzük a K+ {{J3} halmazt; stb. Az eljárást addig folytassuk, amíg B n minden eleme be nem kerül valamelyik halmazba! Ezt a folyamatot szemlélteti a 6.3. táblázat. (A baloldalon szereplő első oszloppal, amelyben a H ellenőrző mátri x és a vektorok szorzata áll, egyelőre ne foglalkozzunk.)

(J:

6.3. táblázat

o

IXI 01:2 IX2k_1 H{J[ {JI {JI +01:1 {JI +IXz ... {JI + IX2k-1 H{J{ {Jz {JZ+OI:I f!2+ IX Z ... {JZ+0I:2k_1 O

.

~p~ I p~ .'P;~~l' p~~~~ .:::'p;~~~~'l A konstrukció ból világosak az alábbiak: 1. Egyetlen {JI sem eleme egyetlen fölötte levő sornak sem. \ 2. B n minden vektora szerepel a táblázatban. --9-

6.18.

TÉTEL.

A 6.3. táblázatban B n minden eleme pontosan egyszer szerepel.

Tegyük fel, hogy valamely a E B n vektor kétszer is előfordul a táblázatban. Az nem lehetséges, hogya ugyanabban a sorban szerepeljen kétszer, hiszen a = {J.+ 01:. és a = {J+ IX· esetén azt kapnánk " hogy {J.+ IX.JI = {J.+ 01:.72' azaz IX·JI = 01:.J2 , ami 'll 'J2 I ellentmondás. Tegyük most fel, hogy a két különböző sorban szerepel, vagyis: CI = {Ji, + OI:h , és CI = {Ji. + IXj,' il < i2 • Ekkor azt kapnánk, hogy {Ji, + 0I:j, = {Ji. + IXh , amiből {Ji. = = {Ji, + (0I:j, + IXh ) adódik. Mivel K lineáris, ezért 0I:j, + IXj, = IXh E K. így tehát {Ji. = BIZONYÍTÁS.

278

= fJj! + 1Xj" vagyis a fJj, vektor eleme a fJi! sorának, amj a konstrukció miatt szintén nem lehetséges. O

A fenti K = K + {O}, K + {fJl}, ... , K + {fJp} halmazokat K szerinti mellékosztályoknak nevezzük, a {O, fJ1. .. . , fJp} vektorrendszert pedig a mellékosztályok egy reprezentánsrendszerének. A 6.18. tétel alapján amellékosztályok diszjunktak egymástól, és mindegyik mellékosztály ik darab vektort tartalmaz, ezért a táblázat sorainak száma 2n-k. A K-tól különböző mellékosztályok száma tehát p = 2n- k -1. Nem nehéz megmutatni, hogy ha a konstrukció során a fJj-k helyett más fJ; vektorokat választottunk volna, a belőlük kapott mellékosztályok ugyanazok lettek volna, mint amelyeket a fJrkből kaptunk. Éppen ezért megtehetjük, hogy egy olyan reprezentánsrendszert választunk, amelyben minden vektor a saját mellékosztályának egy minimális súlyú eleme, azáz egy ún. osztályelső. Erre a reprezentánsrendszerre igaz lesz az alábbi tétel: 6.19. TÉTEL. A K lineáris kóddal pontosan akkor lehet t hibát javítani, ha minden legfeljebb t súlyú vektor szerepel az osztályelsőkből álló reprezentánsrendszerben. BIZONyíTÁS. Elégségesség. Az IX j E K középpontú, t sugarú SilX j ) gömb tetszőleges elem ét fölírhatjuk lX i + fJ alakban, ahol w(fJ) ;:§ t. Mivel a feltétel szerint minden legföljebb t súlyú vektor eleme a reprezentánsrendszemek, ezért ez azt jelenti, hogy az S,( IX j) gömb minden eleme benne van a 6.3. táblázat IX j, IX j + fJl' ... , IX j + fJp vektorokból álló oszlopában. A 6.18. tétel szerint különböző oszlopoknak nincs közös elemük, így az S,(IX;) (IX j E K) gömbök is diszjunktak egymástól. Szükségesség. Tegyük föl, hogy a K kóddal t hibát tudunk javítani, és legyen a olyan t-nél nem nagyobb súlyú vektor, amely nem eleme a fenti reprezentánsrendszemek. Legyen a E K + (f3J. Ekkor a = fJj + 1Xj, ahol lXi E K, lXi ,,= O, továbbá a reprezentánsrendszer kiválasztása folytán w(fJj );:§ w( a). A a kifejezéséből azt kapjuk, hogy IX j = a+fJj , ebből pedig W(IX;);:§ w(a)+w(fJj);:§ 2·w(a);:§ 21 következik. Ez azonban IX j ,,= O miatt ellentmond annak, hogy w(K) ;;;: 2t+ 1. O

6.18. DEFINÍCIÓ. A H ·aT szorzatot a a E B n vektor szindrómájának nevezzük. (H a K kód ellenőrző mátrixa.)

A definíció szerint tehát egy vektor pontosan akkor lesz eleme K-nak, ha szindrómája a nulla vektor. 6.20. TÉTEL. Két vektor pontosan akkor tartozik ugyanahhoz a mellékosztályhoz, ha szindrómájuk megegyezik.

279

~

BZONYÍTÁS. Tegyük fel, hogy (11 és (12 ugyanannak a mellékosztálynak az elemei, és legyen {Jj az ebből az osztályból kiválasztott reprezentáns. Ekkor (11 = Pj+rJ.1t és (12 = {Jj+ rJ. i2 ' ahol rJ.i" rJ.i• E K. Képezve a H ·(1I szindrómát, az alábbiakat kapjuk:

H·(1I = H·({Jj+rJ./,)T = H·{JI+H.rJ.~ = H·{J] = H·fJJ+H.rJ.~ = = H·({Jj+rJ./.l

= H'(1r,

vagyis (11 és (12 szindrómája megegyezik a kiválasztott Pj reprezentánséval. Tegyük most fel, hogy H·(1i =H'(1r Ekkor H'«(11+(12l =0, azaz (11+(12 eleme a K kódnak. Legyen rJ./ = (11 +(12, és tegyük fel indirekt módon, hogy (11 és (12 különböző mellékosztályokhoz tartoznak, azaz (11 E K+ {Ph}' (12 E K+ {{Ji.} és A -< j2' Ekkor (11 = Ph + rJ.i" (12 = {Jjz + rJ.i.' Adjuk össze az előbbi két egyenlőséget. Azt kapjuk, hogy (11 + (12 = {Jh + rJ.h + Pjz + rJ.i.' Tudjuk viszont, hogy (11 + (12 = rJ.i • Így

Mivel K zárt az összeadásra nézve, ezért rJ. i + rJ.i, + rJ.i• E K, tehát Ph E K + {{Jj,} , ami ellentmond {Jh választásának. Következésképpen (11 és (12 ugyanazon mellékosztálynak az elemei. O A 6.20. tételből egy jól ismert hibajavító algoritmushozjuthatunk, lineáris kódokra. Legyen rJ.i a kimeneti vektor, és (1 E B n az a vektor, amelyet az rJ.;-ből kaptunk oly módon, hogy legfeljebb t helyen megváltoztattuk az értékét. A e(rJ.i , (1) ~ t összefüggésből azt kapjuk, hogy (1 = rJ./+ e, ahol W(e) ~ t. Az e vektor az ún. hibavektor; pontosan azok a komponensei nem nullák, ahol az rJ.i vektort megváltoztattuk. Így ha ismerjük a (1 és az e vektorok at, az eredeti rJ. i már kiszámolható. Számítsuk ki most a (1 vektor szindrómáját :

Mivel W(e) ~ t, ezért e osztályelső, azaz eleme a kiválasztott reprezeI\tánsrendszernek. Így tehát csak annyit kell tennünk, hogy (1 beérkezésekor kiszámítjuk a H .(1T szindrómavektort, majd kikeressük a 6.3. táblázatban, és vesszük a mellette levő vektort, ami éppen az e hibavektor lesz.

--+

6.21. TÉTEL (HAMMING-KORLÁT). Ha az m-dimenziós K ~ Bn kóddal t hibát tudunk javítani, akkor teljesülnie kell az alábbi egyenlőtlenségnek :

280

Tudjuk, hogy ebben az esetben minden legfeljebb t súlyú vektornak szerepelnie kell az osztályelső kből álló reprezentánsrendszerben. Összesen 2 n - m darab mellékosztályunk van (a K-t magát is beleértve), másrészt a nulla súlyú vektorok száBIZONYÍTÁS.

ma

(~)

6.22.

= 1, az egy súlyúaké

TÉTEL.

G), a kettő súlyúaké (;) stb. Így tehát

Ha az n, m és t számok olyanok, hogy teljesül rájuk az n-l) ( 1 +

(n-l) (n-l) 2 + ... + 2t-l

-<

2n - m -l

egyenlőtlenség,

akkor létezik olyan K lineáris kód, melynek blokkmérete n, dimenziója m, és t hibát lehet vele javítani. A K kóddal pontosan akkör tudunk t hibát javítani, ha K ellenőrző mátrixában bármely 2t darab oszlop lineárisan független. A H ellenőrző mátrix oszlopvektorainak hossza n- m, azaz ezek elemei a B n - m vektortérnek. Kezdjünk el Bn-m-ből kiválogatni vektorok at úgy, hogy ezek közül bármely 2t darab lineárisan független legyen. Tegyük fel, hogy P- 1 oszlopot már sikerült kiválasztanunk. A pedik nek olyan vektort kell bevennünk, amely nem áll elő legfeljebb 2t-l darab már BIZONYÍTÁS.

kiválasztott oszlop összegeként. Mivel

p-l oszlopból i-nek az összege éppen (P ~ 1)_

féleképpen képezhető, s Bn-nr-ben a nem nulla vektorok száma 2n-nr - 1, ezért a p-edik vektort biztosan jól ki tudjuk választani, ha 1 + (P-l) 2 + ... + (P-l) 2t-l (P-l)

-<

2

n

-

no

-1.

A tétel feltétele éppen azt biztosítja, hogy a fenti egyenlőtlenség teljesüljön P = 1, 2, ... , n esetén. Ez azt jelenti, hogy ki tudunk választani n darab oszlopot a követelményeknek megfelelően. O FELADATOK

6.13. Keressük ki a mellékosztályokból az Hamming-kódnál.

osztályelsőket

a hetes

blokkméretű

281

8. Reed - MulIer-kódok A Reed- Muller-kódok a kódoknak viszonylag széles osztályát alkotják, s jó hibajavítási lehetőségekkel rendelkeznek. Ezeknek a kódoknak a blokkmérete mindig kettőnek valamilyen hatványa,azaz n = 21. Ekkor az n hosszúságú oc = (ao, ah .. " a 2 /_ 1 ) vektomak megfeleltethetünk egy l-változó s h(Xh X 2 , ••• , Xl) Boole-függvényt úgy, hogy itt az oc vektor az h függvény értékeinek sorozatát adja, a 6.4. táblázat szerint. 6.4. táblázat

I fa.(Xl,

Xl

X2

Xl

O

O

O

ao

O

O

1

al

-,"

.......... 1 ... 1

6.9. PÉLDA. A háromváltozós (O, O, O, O, O, O, 0, l) E B 23 •

XIX2Xa

X2 • ... , Xl)

a2/_l

Boole-függvénynek

megfelelő

vektor:

Ez a megfeleltetés azért is szerencsés, mert a függvényekkel ugyanúgy végezhetjük el a műveleteket, mintha a nekik megfelelő vektorokkal számolnánk. Példáulh+/p = =h+fJ és c'h =fc.a.· Éppen ezért a továbbiakban gyakran nem is teszünk különbséget a függvények és a nekik megfelelő vektorok között. 6.19. DEFINÍCIÓ. Az R(I, i) ~ B 2/ (i;§ I) lineáris kódot Reed-Mul/er-kódnak nevezzük, ha az XhX j , • • • x/J (j ;§ i) típusú szorzatfuggvények generálják. Úgy is mondhatjuk tehát, hogy R(I, i) az összes legfeljebb j-edfokú Zsegalkin-polinomból áll. 6.23.

TÉTEL.

Az R(I, i) kód dimenziója l +

G) + G) + ... + G) .

BIZONYÍTÁS. Csak azt kell igazolnunk, hogyadefinícióban megadott generátorrendszer elemei lineárisan függetlenek. Ez azonban következik abból, hogy minden Boole-függvény egyetlen Zsegalkin-polinommal reprezentálható. így, mivel a ~282

t~~:fokÚegytagÚak száma G) minden j szege adja a bázis számosságát.

= 0, l,

... , i-re, ezért ezeknek az ösz-

O

6.10. PÉLDA. Adjuk meg az R(4, 2) kód generátormátrixát. Ennek a mátrixnak a sorait az l, Xl> X 2 , Xa, X 4 , X1 X 2' xlxa, XIX4, X 2Xa, X 2 X 4 ' XaX4 egytagúaknak megfelelő vektorok alkotják. Ha tehát azt a megfeleltetést vesszük, amit az előbb is, az R(4, 2) kód generátormátrixa a következő lesz: 6.5. táblázat

Xa

1.111111111111111 OOOOO OOO l 1 l 1 1 1 1 l OOOO l 1 1 l OOO O 1 l l l OO l l O O l l OO l l OO l l

X4

0101010101010101

XIX2

OOOOO OOOOO OOOOO OOOOO OOOOO OOO l O

Xl X2

XIXa XIX4

X2Xa X2X4

X3X4

6.24.

TÉTEL.

OOOOOO OOOOO l OOOO l O O l l OOO l O l OOO OO l OOO

Az R(l, i) kód súlya w(R(l, i»)

Ol l l l OO l l O l O OOO l OO l O l OOO

l 1 l l l l

= i-i.

A w(R(l, i») ~ i-i egyenlőtlenség következik abból, hogy pl. az xi-nek megfelelő bázisvektor nem nulla elemeinek a száma 21-i. A másik irányú egyenlőtlenséget, tehát azt, hogy w(R(l, i») ~ 21- i , l-re vonatkozó indukcióval bizonyítjuk. Az R(I, l) kód bázisának elemei az l és az Xl függvények, generátormátrixa pedig BIZONYÍTÁS.

XIX2 •••

(~

!).

Itt a w(R(I, l») ~ l összefüggés nyilvánvaló. Tegyük fel, hogy már bizonyítottuk a

w(R(I-I, i»)

~ 2(1-1)-i

minden i = 1,2, ... , (l-I)-re. Vizsgáljuk meg most az R(/, i) kódokat. Mivel a w(R(l, l») ~ i-l = l egyenlőtlenség ismét triviálisan teljesül, elegendő az i = 1,2, ... , l-l esetekre szorítkoznunk. Ha Ia.(Xb X 2 , •• . , Xl) E R(l, i) tetszőle-

egyenlőtlenséget

283

ges nem nulla függvény, akkor xrt kiemelve a Zsegalkin-polinomnak mindazon tagjaiból, amelyekben szerepel, a következő előállítás hoz jutunk:

A kapott előállításban I~' E R(/-l, i-l),

A fenti

I:'

foka legfeljebb i-l, I: foka pedig legfeljebb i. Így

ill.J: E R(l-l, i).

egyenlőségből

azt kapjuk, hogy

h(Xl, X2, .. • , Xl-l, h(Xl, X2, ..• , Xl-l,

= I: (Xl, X2, ... , Xl-l); 1) = I:' (Xl, X2, ... , Xl-l)+I: (Xl,

O)

X2, ... , Xl-l).

Három esetet különböztetünk meg a továbbiakban. 1. I: == O. Ez azt jelenti, hogy fa.(Xl> ... , Xl_l, 1) = I~' (Xl> . . . , XI_l). Mivel I:' E R(/-I, i-l), ezért az indukciós feltevés alapjánl:', és így lIT. is legalább 2'-i helyen nem nulla. 2. O. Ekkor E R(l-l, i-l) miatti: E R(l-l, i-l), így az első esethez hasonló szituáció állt elő itt is. 3. 0,/: ~ I~'. Az indukciós feltevés szerint az fa. legalább 2(/-l)-i olyan vektoron nem nulla, amelynek az utolsó komponense O. Továbbá I~+ I:' E R(l-l, i), I~ +I:' ~ Omiatt az olyan vektorok on is lesz legalább 2(/-1)- i nem nulla behelyettesítése, melyeknek az utolsó komponense l. Ez pedig azt jelenti, hogy fa. összesen legalább 2 ·2(/-l)-i = 2'-i helyen nem nulla. O

I: =-1:' ..

I:'

i:'-

6.25.

TÉTEL.

Az R(l, i) és az R(l, 1-

(H l») kádok egymás duálisai.

BIZONyíTÁS. Vizsgáljuk meg először a fenti kódok dimenzióját. Ha m2 pedig az R(l, I-(i+ l») dimenziója, akkor

ml

az R(I, i),

l+G) +... +(~) ; m2= 1+(:)+ ... +(/-(:+1») = (~)+(/~l)+ ... +(i~I)· ml =

Így:

Azt kaptuk tehát, hogy R( l, 1- (i + l») dimenziója megegyezik R(l, i) duálisának a dimenziójával, és viszont. Elegendő tehát azt megmutatnunk, hogy az egyik kód bázisának minden eleme merőleges a másik kód minden bázisvektorára. Ha azfi,J;, ... ,fml egytagúak alkotják R(l, i) bázisát, akkor fokuk legfeljebb i; az R(l, I-(H l») bázis át alkotó gl, g2, ... , gm, egytagúak foka viszont nem nagyobb 1- (i+ 1)-nél.

284

Ha valamelyik fa egytagút összeszorozzuk valamelyik gb-vel, akkor egy legfeljebb (l-I)-edfokú egytagút kapunk. Egy ilyen szorzat azonban páros sok helyen vesz fel nem nulla értéket, ez pedig éppen azt mutatja, hogy az fa és gb függvények skaláris szorzata O. O Növeli a Reed- Muller-kódok gyakorlati alkalmazhatóságát, hogy viszonylag egyszerű hibakereső algoritmus adható hozzájuk. Ezt az eljárást is egy példán, az R(4, 2) példáján ismertetjük. Ennek a kódnak a 6.5. táblázatban már megadtuk a generátormátrixát. Legyen a kimeneti vektor oc =
la. =

,1,1. 1+A2· Xl+

A3 ·X2+ A4·X3+ A5 ·X4+Aa ·XIX2+ A7 ·XlX3+ AS ·XIX4+ A9 ·X2X3+

+ }'10 • X2X4 + Au . X3X4. Egy olyan információs csatornán, melynek zaja legfeljebb 1 hibát okoz (d(R(4, 2») = = 24- 2 = 4, tehát R(4,2)-vel legfeljebb 1 hibát lehet javítani), az oc-ból egy (J = ~, a~6") vektort kapunk, s ez legfeljebb 1 pozícióban térhet el oc-tól. Ahhoz, hogy visszakapjuk oc-t, elegendő a Al, A2, ... , An együtthatókat ismernünk. A generátormátrixból viszont könnyen kaphatunk összefüggéseket ezekre az együtthatókra. Így pl.

<",

... ,

AU

="-

aG+~+a2.+a,;

A11 = ak+alí+tlé+aa.;

Au = a8+ a19+ al1)+ al!; A11 = ala..+al\+allj+al,.

Írjunk az előbbi egyenletekben ai helyett mindenhova a;-1. Mivel (J legfeljebb 1 komponensében különbözik oc-tól, ezért ezen egyenlőségek közül is legfeljebb egy nem teljesül; három összeg tehát biztosan Au valódi értékét adja. Így Au értéke az az érték, amely a fenti összegek között többször előfordul. Az ilyen típusú dekódolást nevezik többségi dekódolásnak. Ezt az elvet alkalmazhatjuk azután a többi együtthatóra is, azaz Al-re, A2-re, ... , AlO-re. FELADATOK

6.14. Adjuk meg az R(3, l) kód generátormátrixát. Mi a kapcsolat az R(3, l) és a 7-es blokkméretű Hamming-kód között? 6.15. Általában mi az összefüggés a Reed-Muller- és a Hamming-kódok között? 6.16. Írjuk le részletesen a többségi elven való dekódolás t az R(4, 2) kód esetén, melIyel 1 hibát tudunk javítani. 285

-

322

5.

KRIPTOGRÁFIA

5.3. definíció. Egy titkosítá.si algoritmust gyakorlati titkosságat nyújtónak nevezünk, Illi feltijrése irreálisan nagy számítási / tárolási kapacitiÍ.5t kíván. 5.4. definíció. A feltétel nélküli titkosság azt jelenti, hogy a megszerezhető információ (pl. rejtett üzenetek SOl'O%ata rejtett üzenetíí támadást tekintve) mennyisége elvileg sem elegendő a feltöréshez bármekkora. számí(;ási kapaci tá.5 is állna rendelkezésünkre. Az 5.1. definíció szerinti tökéletes t itkosító feltétel nélküli titkosságot biztosít. Adott algoritmusok számítás igényének elméleti meghatározását egy rohamosan fejlődő tudományág, az " Igori tmusok komplexitáselmélete tlizte ki célul. E zen eredmények alapján egyes nyilvános kulcsú t itkosító algoritmusok feltörh e tőségét bebizonyították. Az "lábbiakban be ve%etésrc kerülő nyilvános kulcsú titkosítá.si algoritmusok gyakorlati titkosságot kívánna k nyújta ni. Az algori t musok alapja tipikusan egy közismerten igen nehéz matematikai probléma., a tárgyalandó RSA-algoritmus például az igen nagy ('" 10 30 °) egészek prímfaktorokra bontásának nagy szá.rnításigényére a lapoz .

5.3.

Nyilvános kulcsú titkosítás

A nyilvános kulcsú titkosítás alapgondolata, hogy gyakorlati titkosságat t ud nyújtani anélkül, hogy a titkos ii ~ellet küldést rnegelő~őe n a kommunikáló partnerek bárrnifele titkos kulcsot cseréltek volna egymással, mint ahogy ez az elő"etes kooperAció előfeltétel a konvencionális titkos ítás esetén. Az A nyilvános kulcsú !;itkosító két kul ccsal dolgozik, egy ny.ilvános ( k~) és egy titkos (k~l) kulccsal. A nyilvános kuksot a kódoláshoz, a titkos kulcsot a dekódoláshoz használjuk. Ha A és B titkosítók ldhasznátásával történik t.itkos üzcnetváltás, akkor B a7. y = Ek'A (x)

rejtett üzenetet küldi A-nak , amit k~ nyilvánossága mi "tt megtehet, s ebbő l a rejtett üzen et ből x = Dk'A (y) dekódolással nyeri vissza A a nyilt üzenetet. A kódolás a nyilvános kulcs ismeretében "könnyű" felad at, míg a dekódolás a rejtett kulcs ismeretének hiányában gyakorla tilag nem végl'ehaj tható ("nehéz feladat") .

5.3 NYILVÁNOS KULCSÚ TITKO s íT ÁS

323

Egy A, B, C, ... t itkosÍl.ókat (felhasználókat) tartalmazó rendszerben a k~, k~ , ... nyilvános kulcsokat egy nyilvános kukstárba tesszük le, ahonnan bármelyik felhasználó kiolvashatja a nnak a felhasznál6nak a nyilvárlOS kulcsát, akinek rejtett üzenetet kíván küldeni . Az egyes felhasználók helyben generálhatják a (k{j, kt-) kulcspárt, s ebből a nyilvános részt közzéteszik, míg a másikat titokban tartják. Nagyon fontos észrevennünk azt a kitételt, m iszerint a nyilvános kulcs t ár ból cs"k olvasni szab"d, s védeni kell azt a ny il vános kulcsokkal történő manipulációktóI (pl. cserétől) . Ez azt jelenti, hogy ugyan" kommunikáci6t megelőzően nem kell titkos kulcscserét végemi, hiszen a nyilvános kulcstárból olvasás egy nyílt előzetes információcserének felel meg, de megmar ad az a fe ladat, hogy ezen nyílt előze tes információ hitelességét biztosít"ni kell. Hitelesítési fel"d"tb"n jól "lkalmazható a D dekódoló transzformáció. Tegyük fel, hogy A az x üzenetet kívánja B-nek elkülden i olyan módon, hogy egyúttal "aláírását" is elhelyezze a rejtett üzenetben. Ezt úgy teheti meg, hogy az y = EH(DA(X)) a lakú üzenetet küldi el. y a l"pján a DA(X) tartalmat esak B tudja dekódolni , s ny ilván DA(X) az a leképezés, amelyegyértel műen kapcsolódik a küldő személyéhez, A-hoz, PB a küldött üzenethez, x-hez. A dekódoló tl'anszformációnak a nyílt üzenetre történő alkalmazásával digitális aláírást generálhat unk. Hasonló aláírások hitelesíthetik a nyilvános kulcstár elemeit. Ezen alkalma"ásokra a krip tográfiai protokollok kapcsán még visszatérünk. A. Shamirtól származik az a rendkívül érdekes eljá rás, amelynek a felhasználásával mindennem,í el őzetes kulcscsere nélkiil titkos üzenetváltás történhet partnerek között, feltéve az esetleges behatolóról, hogy passzív, azaz a csatornán folyó üzenetváltás lehallgatására képes csak . Ez az elj árás elvi továbblépést jelent a nyilvános kulcsú algoritmusükkal szemben is , hiszen még nyilvános információt sem ken előzetesen a partnerek t.udomására hozni.

A felha.sználók mindegyike egy titkos kulccsal rendelkezzen, s t.egyiik fel, hogy a rendszerben a lka lmazott Ek(X) kódoló tra nszformáció kommut.aÚv , azaz tetszőleges x nyílt üzenet, kl! és kB kulcspál' esetén

(5.10) azaz a kétszeres kódolás eredménye független legyen a kulcsválasztás sorrendjétől. Ekkor az ún. "háromlépéses" eljárás alkalrnazásával .4 felhaszná ló B-nek a következőképp küldhet,i el xii zenetét:

324

5. KRIPT OGRÁFIA

2. B -+ A:

Y2

= Ek .

(EkA(X) ) = Ek, (EkR(x ))

3. A -+ B:

Y3

= D kA (EkB (EkA (x))) = EkE (X)

E, a természet,f" ötlet még szemlélet.esebben is leirbató. Nevezet.esen képzeljük el, hogy egy lelakatolható ládáha helyezi el A az x üzeneteI., s lelakatolja kA kulcsával (1. lépés), majd elküldi B-nek. B nem próbálkozik a nyitás számára is lehetetlen feladatával, hanem inkáhb még a saját k a kulcsával is lelakatolja a ládát (2. lépés), majd viss7.ak üldi azt A-nak. A leveszi a saját lakatját, s a ládá t , amelyen már csak B lakatja maradt , viss,aküldi B-nek (3. lépés), aki ezután már könnyen kinyithatja a7.t.. A fcntiekhől úgy tűnhet, hogy megtaláltuk a tökéletes megold ást, hiszen valóban nem kellett előzet es kulcscsere a partnerek között (sem nyilvános, sem titkos). De mint említettük , ezen protokoll praktikus alkalma.zhatóságát a.z gátolja, hogy teljesen ki van szolgáltatva az aktív támadás nak, hiszen az üzenet küldés nyilvános hálózat.on történik. A fenti szemléletes leírásmód szóhasználatával gondoljunk csak arra, hogy pl. a p ostás, akivel a ládát kívántuk B-hez eljuttatni a saját lakat.ját. tes ú a ládára a 2. lépésben, s így adja azt viss7.a A-nak. Az (5 .10) kornrrllltativit.á.~i t.ulajdonságnak eleget tesz az egyszerű

Ek(X) = x + k (mod 2) bit.en kénti rnodlllo 2 vektorösszeadást a lka lma.zó kódolás, ugyanis

mivel a mod 2 összeadás asszociatív. Könnyen beláthatjuk azonban, hogy ezen kódol á.~ alkalmazása a háromlépéses eljárásban még a legegyszerűb b passzív támadásnak, a puszt.án rejtett szövegre alapozó t.ámadásnak sem áll ellen. Ugyanis az elj árás 1., 2. , 3. lépése során a támadó megfigyelve az Y3 = x

+ kt!

rejtett üzeneteket, és képezve azok mod 2 összegét, YI + Y2 + Y3 = x ,

az x nyílt üzenethez jutunk, sőt a kulcsok is kinyerhetők: kB = Yl + Y2 és k A = Y2 + Y3. Vegyük észre, hogy az alkalmazott kódolás nem véletlen átklllcsolás, hiszen kétszer is alkalmaztuk llgyanazon kulcsot.

5.3

325

NYILVÁNOS KULCSÚ TITKOsíT,ÁS

Kommutatívegy,1;' mod n alakú kódolás (modnlo hatványo7.ás) is, a.hol .T-~. f.', n tennészetes szálnok, azaz

(:1;<' )e 2 = (:l;c'r'

mod

'1)..

Ilyen I.Ípnstí mÍÍveletel héLs7.nál éL7. 5.4. sZéLk"'S7,ban rés7.letcscn ki rej tel!. RSAkódolás.

Elemi számelméleti eredmények Ahhoz, hogy megérthessük a Rivest-Sharnir-Adleman (RSA) a.lgüritIIlUS müködését, néhány elenü s;"ánlehnéleti eredmény felidézése szükséges.

5.3. tétel (A maradékos osztás tétele). Tetszőleges a. és b, b> O egészeb'e egyértclmíícn létezik q és r' egész, hogy

() s: r < b.

a = bq -I- )',

'lb s: CL < (g -I- l)b egyenlőtlenségnek eleget tevő egészet vá.las7.thatjuk, s ekkor T = CL - qb. Az egyértelmÍÍség igazolásához tegyük fel, hogy q, r páron kívül létezik q', "J pár is, amelyre a. = q'b -I- r', () s: r' < b. Mivel ekkor qlJ -1-1' = q'b -1-.,.' állna fenn, ezért r - r' = bCg' - q) átrendezéséből ellentmondásra jntnnk, hiszen O s: r, r' < b miatt r - r' < b, s ugyanakkor teljesülnie kell a l, r - r-' oszthatóságnak, ami csak 'f' = T' csetén lehetséges. Az 7' = )" egyenlőRégből viszont q = q' is követkeúk. • BIZONyíTÁS:

A létezés könnyen látható, hiszen a

I

5.5. definíció. Az a szánlot II b és c sz/ün kö7,öS os;.;(;óJá,nak nevezáik) hu a. I b és a. I c te!iesli1. Ha b és c kőzlillegalább az egyik nem IlulIa, akkor a közös osztóik legnagyobbikit b és c legnagyobb kőzös osztójának n8vezúik és (b, cl-vel je1őljíík.

5.6. definíció. Azt: mondjuk, hogy

(J.

és b relatív prímek, lIa (a, b) = l.

5.4. tétel (Az euklidészi algoritmus). Adott b és ro > () egészekre egymás után többször alkalmazzuk amaradékos osztá.st, s ezzel az egyenletek kővetkező sorozatát kapjuk: b = cql -IC 7'1

=

T'IQ2

= "2Q:l

T n -2 = Tn-lqn 'r n -1

0<1'1


7'2

O<

<

1'3

() < 7'3 < 1'2

TI

-I-I-

= T'nqn+l

+ Tn +O

1'2

rI

o < Tn < rn-l 0=

7'n+l

326

5. KRIPTOGRÁFIA

A h és c számok legnagyobb közös osztója n€ln nulla IIw.radéka, azaz (b, c) = l'n'

Tn ,

az osz tási eljárás legutolsó

BIZONYÍTÁS:

a)

pozitív egészek S7.igOl·úan monoton csökkenő sorozata, ezért léteznie kell olyan egésznek, amelyre Tn+! = O.

" ] ,1'2, . . .

b) A b = cq, + T] egyenletre tekintve láthatjuk, bogy ha x I b és x I c fennáll, akkor x I r] is fenn kell álljon, S viszont, ha y I c és y I r], akkor ebből y I h is következik . Ez pedig az t. jelenti , hogy b, c közös osztóinak halmaza megegyezik c, közös osztóinak halrnazával, ezért (b, c) = (c , rIl is igaz . A7. euklidészi algorit mus további egyenleteit is t eki ntve a

r,

egyen lőség i

láncot kapjuk , tehát (b, c) =

Tn

•

valóban igaz.

5.1. következmé ny. Tetszőleges b és e egészekre, am elyek köz ül lega.Jább

az egyik nem nulla, léteznek s és t egészek, hogy

(b, c) = " b + tc.

(5.1l)

Az euklidészi algorit mus egye nletei ből egymásba helyettesítésekkel a követ. kező eb'Ycnletsort kaphatjuk:

BIZONY ÍTÁS:

ri

-

b - glc = b+ (-q,)e

1'2

C-

'12"[

"n

sb + tc,

= (-q2)b

+ (1 + '1]'12)C

.

tehát az összes ri, így "n is felírható a b és c számok lineáris kombinációja~~.

5.5. példa. Határozzuk meg a 8387 és 1243 legnagyobb közös oS7.tóját!

Az euklidészi algoritmus alapján: 8387 1243

+ 929 929· 1 + 314 1243 · fi

-

5.3

327

NYILVÁNOS KULCSÚ TITKOSÍTÁS

929

-

314·2 + 301

314

301 . 1 + 13

301

13·23 + 2

13 2

-

2·6+ 1 1·2 + O,

így (8387,1243) = 1, azaz relat.ív prímek. Ezen 8zárnolást felhaswálva az (5.11) előállítás a következőképp kapható b = 8347, c = 1243 jelölésekkel:

929

b - 6e

314

-b+7c

301

3b - 20c

13

-4b + 27c

2

95b - 641c

1

-574b + 3873c,

azaz (8387,1243) = -574·8387 + 3873·1243. 5.7. definíció. Ha az m nemnul1a egész osztja 8.Z Q. - b kiilönbséget, akkor azt mondjuk, hogy az a kongruens b-vel modulo m, és ezt a következöképpen jelöljiik: a = b (mod ml. 5.8. definíció. Azt mondjuk, hogy b IIlodulo m inverze a-nak ha ab = 1 (mod rn).

5.6. példa. Az 5.5. példa alapján a 3873 az 1243 rnodulo 8387 illverze, hiszen 3873 . 1243 = 1 mod 8387. 5.5. tétel. Az a modulo m inverze akkOT és csak akkor lét;ezik, ba (a, m) = 1. Ha létezik inverz, akkor az egyértelmű az m-nél kisebb pozitív egészek között. BIZONYÍTÁS: Ha létezik b, amelyre ab = 1 (mod ml, akkor az ezzel ekvivalens ab - qm = 1 alakból (a, m) I 1, azaz (a, m) = 1 következik. Megfordítva, ha (a, m) = 1, akkor az (5.11) felhasználásával sa + tm = 1 kapható, ahol b = s választással ba. = -tm + 1, azaz ba. = 1 (mod m) következik.

5. KRIPTOGRÁFIA

328

A7, egyértelműséget a következőképp biwnyíthatjllk . Ha a b' of b, O < b, b' < megészekre ab = ab' = l (mod ml, akkor a(b - ú') = O (mod ml, ami aztjelent.ené, hogy ml a(b-b'). De mivel (a.,m) = l , ezért ebből 771. I b-h' következik, am i viszont lb - b'l < m miatt lehetet.len. •

5.6. tétel (Fermat-tétel). Ha a e egész nem osz tlwtó a p prímmel, akkor

eP- l = 1 (mod p).

(5.12)

Tetszőleges

c egés7,re a c, 2c, 3e, ... , (p - l)e számok külön· böznek modulo p. Ha ugyanis i c = j e (mod p) , i ol j , O < i, j < p fermállna, akkor az (i - j)e = qp és Ii-JI < ]J, p t e összefüggések ből ellentmondásra jutnánk. Így tehát a c, 2c, ... , (p - I)e számok modlllo p az 1,2, ... ,p - 1 számok egy perrnutációját adj ák. A kongruencia. definíciójából következik, hogy ha a.i = !Ji (mod p), i = 1,2, ... , n, akkor 0.,0.2 .. · an = b,b2'" bn (mod p) is fennáll. Tehát 1·2·3· ... · (p - 1) = c· 2c· ac· ... · (p - l )e, azaz BIZONYÍTÁS:

p-l

TI 'i =

p- l

l LP -

TI i

(mod p)

i=1

i =l

Jimnáll, ahonnan l = eP -

'

•

(mod p).

5.7. tétel (Fermat-tétel általánosítása). Ha 1' 1 és 1'2 mek, és (a,p,p2) = l , akkor

különhöző

pd-

Az (0.,P1P2) = l a Pl t a és P2 t a állításokat jelenti, így prím, Pl t aP,-l és 1'2 t a P 1 - 1 is teljesül. A Fermat-tétel felhru;ználásával t.ehát. BIZONYÍTÁS: mivel Pl és 1'2

(o. ( -l») P,

(p 2-

1)-_ 1

(mod P2)

következnek. De ha. valamely c egés7.re c = l (mod p il, c = l (mod 1'2) , akkor az ekvivalens P, I e-l és P2 I c-l á llításokból 1'17'2 I c - l következik. • A c = a (pl - l) (pz - l ) megfeleltetéssel a tétel bizonyítlisát kaptuk.

329

5.4 RSA-ALGORITMUS

Az 5.6. és 5.7. tételek az alábbi tétel speciális esetd: 5.8. tétel. Ha. l i (a, m) = 1, a.kkor

-

PIP2'" p" , alJol PI, P2, .. · ,P" különböző prím ek és a4>(m)

(mod m) ,

= l

(5.14)

alJo/(m) = (Pl - 1)(p2 - l) ··· (Pn - l ) az Eu/er-függvény. (Ez Euler-tétel speciális esete.)

il.

tétel az

A továbbiakban csak az 5.7. tét.el általánosságára les" súikségünk, ezért az 5.8. tét.el bizonyítását (lásd [30]) , amely az 5.7. tételéhez hasonlóan t.örténhet, elhagyjuk, s csak a q'(PlP'2) = (Pl - 1)(1)2 -l) rövidített jelölést használjuk. Az eddigiekben bevezetett számelmélet.i alapok birtokában megérthetjük az RSA-algoritmust.

5.4.

RSA-algoritmus

Az algoritmus lépései a

követke,ők:

l. Válasszunk véletlens,erűen két nagy prírnszámot pl-et. és P2-t.

2. Kiszámítva az m = P,P2 és (p(m)

válasszunk

véletlenszerűen

= (Pl

egy e, l < "

- 1)(p2 - l ) paramétereket, < (m) egészet úgy, hogy

((rn) , c) = l

(5.15)

teljesüljön. 3. Számít.suk ki e inverzét modlllo (m): d = e- l

(mod (m))

(5.16)

(az 5.5. tétel miatt létezik). 4. Az m, e egészeket nyilvánosságra hozzuk, míg a d,PI ,P2 értékeit titokban tartjuk (azaz k P = (m, e), kS = (d,PI ,p2 ))' 5. A titkosító kódolás az l ::; x

< m nyílt üzenetre egy

l ::; Y < m rejt.ett

üzenete t ad, ahol

ml,

(5.17)

x = yd (mod m )

(5.18)

y=

.T

e

(mod

míg a dekódolás az inverz

művel et .

330

5. KRIPTOGRÁFIA

(Az x és y skalár jelölést alkalmazzuk a nyíl t ill. a rejtett üzenetre az RSA csctén , kihangsúlyozandó, hogy oernnegatív egész számok ként vége7.7.ük velük a mod m müvelet ekct.) 5.1. lemma. Az (5. 17) és (5.18) formu/ákka/ mcgadott i11 ver:tei.

műveletek

egymás

BIZONyíTÁS: Mivel (5. 16) a de = qq,(m.) + l állítáBsai ekvivalens valamely q egészre, ezért <:17.

kongruencia láncolatot kapjuk. Külön vizsgáljuk az (.r., m) = l és (1:, m) l cseteket. a) (x , m)

>

= lesetén (5.13 ) l.'elhru;ználáBával x(m) +l = x(x(m» )1 = x (mod m.)

azaz ez esetb en a kívánt ercdményt kaptuk. b) (x , m) > l esetén mivel ln = PIP2 és x < m, ezért vagy PI I x vagy P2 I x. Az á ltalánosság korlátozása nélkül feltehetjiik, hogy Pl I x, ezért x = WPI felbontás kapható, ahol (w, m) = 1. Ennek felhas7,llálásával (5. 19)

Mivel (w,m) = 1, ezért (5.19) jobb oldali e lső tényezőjérc az 5.7. tétel felhasználásával ",q4>(m)+1 = w (mod m) (5.20) adódik. A Fcrmat-tétel felhasználásával: p;",C",)+1

= Pl

(pj
= PI

(p\P2- I )r(PI -I)

= Pl

(mod P2) (5.21)

illetve nyilvánvalóan: p;4>(m) +1 = O = PI

(mod PI)

(5.22)

Í.gy mivel Pl I pj
331

5.4 RSA-ALGORITMUS Az (5.20) és (5.23) eredményeket (5.1D)-ben felhasználva

(rnod 'tn)

xifd>(rn)+l = W])l =:1:

adódik, amit bizonyítani szerettünk volna.

•

Az alábbiakban egy számpéldával szernléltetjük az RSA-algoritmus paraméterszámítását (l-4. lépések), majd a kódolás és a dekódolás müveletét, amclyben a számok nagyságrendjét a lépések s/'emléllel.ésébez kicsire választottuk.

5.7. példa. Legyen Pl = 73,P2 = 151, így Tn = 73 . 151 = 11023, q,(m) = (73 - 1)(151 - l) = 10800 = 24 . 3 . 52 . 9. Az e paramétert választhatjuk például ll-Ie, mivel (10880, ll) = l. Az e inverzét modulo (p(m) az (5.11) alak segítségével állíthatjuk elő, azaz az 5.5. példában látott számításmenetet követve kaphat juk meg az e8 + (P( m)l = 1 előállítást:

10ROO

11·981

+9

II

9·1 + 2

9

2·4+ 1

2

l . 2 + O,

ahonnan

9

10800 - 981 . II

2

II - 9 = II - (10800 - 981· ll) = -10800 + 982· II 9 - 2 . 4 = 10800 - 981 . II - 4 . (-10800 + 982 . ll) =

1 -

5· 10800 - 4909 . 11, így -4909·11 = l (mod 10800), ezért ri = 10800-4909 = 5891 (mod 10800), tehát ri = 5891. Nyilvánosságra hozzuk az e = ll, m = 11023 egészeket, s titokban tartjuk a Pl = 73, P2 = 151, d = 5891 egészeket. Tegyük fel, hogy az "' = 17 nyílt iizenetet kívánjuk kódolni, ekkor

y = 17 11 (mod 11(23), ahonnan 11 = 1782. A dekódolás az

x = 17825891

(mod 11023)

(5.24)

332

5.

KRIPTOGRÁFIA

művelettel

történik. Az (5.24) modulo hatvány kiszámítását egyszeríísít.i a gyorshatványozás (llnégyzetre ernclés és ~7,or:(,ás!)) módszere. A kitcvőt az

összegre bonthatj uk a bináris ábrázolá.sa alapján. Ennek alapján az (5.24) hatvány t az alábbi alakba célszerű átírni: 1782

212

=

210

1782 . 17822' . 1782 28 . 1782 2 ' . 1782 = (( ... (1782)2 )2 1782)21782)21782)2 )2)2)2?)2)21782)21782 •

A kiértékelést a néhány lépés:

legbelső

rnodulo négp,etre emeléssel ke7.dj ük, azaz az

első

1782 2 = 900 (mod 11023) 9002 = 5321 (mod 11023) (5321 . 1782)

= (2242)2 = 76

(mod 11023) ,

s az utolsó lépés eredményéiil a 17-et kapjuk vissza. Így a helyett, hogy (5.24) mechanikus kiszámításához, azaz a (( ... (1789·1789) . 1789)·1789) · .. ,)· 1789 szorzáshoz súikséges 5890 darab modulo szorzást végeztük volna el, megúszt. uk 17 darab rnodulo szorzással. (Könnyen ellenőrizhető , hogy ezzel a mód szerrel legfeljebb a kitevő kettes alapú logaritmusának kétszerese számú modulo szorzásra van szükség.)

Az egyirányú függvény

f

Mai ismereteink szerint e és m nyilvános adatok birtokában az : {I, 2, ... , m - l} -7 {l , 2, ... , m - l} ,

f(x) = x' (mod m)

(5.25)

inverzének kiszámítása (azaz egy y értékhez egy, az y = f(x) (mod m) összefüggésnek megfelelő x meghatározása) számításigényét tekintve gyakorlatilag megoldhatatlan feladat, ha a Pl és P2 prímeket elegendöcn nagyra

5.4

RSA- AI,GOltlTMUS

333

választj uk. Erős sejtés, hogy ezen inverzképzés nehézsége ekvivalens az ra prímfaktorokra bontásának nehézségével. További sejtés, hogy egész számok faktorizálására szolgáló algoritmusok felhasznál ásával ma számításigényét tekintve megoldhatatlan feladat a loglo m '" 300 nagyságrendű egészek felbontása. Mai ismeretek és technológia alapján többszáz év nagyságrendű idő lenne szükséges a számításhoz. Ezen időtartambecslést természetesen elsősorban úgy kell tekintenünk mint egy irreálisan nagy értéket, amely szemlélteti a gyakorlatilag biztos védettség eléréséhez szükséges erős túlméretezést a kriptográfiai kódtervezésben. A gyakorlati titkosságra visszatérve, elvileg nyilván mód lenne e, m nyilvános adatok birtokában az összes {nyílt üzenet, rejtett üzenet} pár előzetes kiszámítására, amelyeket tfu'olva és a rejtett üzenetek valamilyen sorrendjében felsorolva, tetszőleges rejtett üzenet vételekor kiolvashatnánk a nyílt párját. A feltétel nélküli titkosság így nyilván nem állhat fenn, hiszen az megengedné akár az összes ilyen pár tfu'olását és mégsem juthatnánk közelebb a titok (kulcs) megfejtéséhez. Az (5.25) modulo hatványozás a fentebb már említett megfelelő paraméter-nagyságrendek mellett egy példája az úgynevezett egyirányú függvényeknek.

5.9. definíció. Az invertálható f fiiggvényt egyirlinyúnak nevezzük, ha értelmezési tartományának tetszőleges x elemére f (x) értéket könnyű kiszámítani, míg gyakorlatilag irreális feladat tetszőleges y értékkészletbeli elemhez az y = f(x)-nek megfelelő x kiszámítása. Az RSA-kódolás esetén könnyű feladatnak szánút az (5.25) kódolás, míg a dekódolás csak a titkos dekódoló kulcs, d ismeretében könnyíí. Azon egyirányú függvényeket, amelyeket egy információ birtokában könnyű, de annak hiányában gyakorlatilag lehetetlen invertálni csapda típusú egyirányú függvényeknek nevezzük. Ezzel a szóhasználattal élve csapda típusú egyirányú függvény birtokában elvileg tervezhetünk nyilvános kulcsú titkosító algoritmust. Megjegyezzük, hogya '70-es évek től kezdődően rengeteg erőfeszítés történt ilyen függvények konstruálására, amelyek közül eddig csak a modulo hatványozáson alapuló RSA-kódolás maradt feltöretlen.

Prímek

előállítása

Visszatérve az R.SA-algoritmus első lépésére, nézzük meg röviden a véletlen prímválasztás kérdését. Bizonyítás nélkül ntalunk a számelmélet Csebisev-tételére [öJ, amely kimondja, hogy D(n)-re, az n pozitívegésznél

5. KRIPTOG RÁFIA

334

kisebb prímek számára a

következő

b ecslés adható, ha n elég nagy: n (5.26) ll en) "" ln n

Említettük, hogy ma telj esen biztonságos a, m = PIP2 10 300 nagyságrend, amelyhez Pi "" 10 150 ('" 2.50 °), i = 1, 2 nagyságrendű prímeket választottunk. Így annak a valószínűsége, hogy egy véletlenszerűe n választott 250 l < s < 2502 (502 bites) szám prím, a7. (5 .26) alapján közelíthető:

II (2 502 )

-

II (2 501 )

_-'--:=;;---::"",,---'- .......

2502 -

2501

-

2501

l 1 . 501 ln 2 "-' _ 501 - 350 ' 2

s mivel az adott szám tartomány fele páros szám, amelyek nem prímck, elég csak a páratlanok közül válogatnunk, s e"el megduplázzuk a találási valószínííséget '" 1~5 -re. Így tehát átlagosan 175 próbálkozá.sonként jutunk prímszám hoz a 10 ' 50 nagyságrendíí számok között. Felmerül a kérdés, hogyan dönth etjűk el, hogy a véletlenül kisorsolt egész szám prírn-e vagy sem. Véletlenül sorsolt "ámok közül a prímek valósz ínűségi alapon történő kiszűré,ére több algoritmus is létezik , ameIyeknek az alapelvét kívánjuk itt elmondani. Tegyük fcl, hogy az s egészről szeretnénk eldönteni , ~gy prím-e. V álasszunk egy úgynevezett bázist , egy b egészet a 2 ::; b < s tartományban. A Fermat-tétel alapján tudjuk , hogy ha " prím , akkor b, - l = l

(mod s) .

(5 .27)

b,, - l "Il

(mod s),

(5.28)

Így, ha akkor s biztosan nem prím, és h az S összetettségének ún . Ferrnat-tanúja . Azonban ha (5.27) igaz, akkor csak annyit mondhatullk , hogy lehetséges, hogy s prím. Ha a fenti tes"tet r-szer egymás után megi smételjűk , és a függetlenül sorsolt 2 ::; b .. . , bT < S bázisok mindegyikére (5 .27) t.elj es űl , akkor az s " egészet kis tévedés i valószínűséggel prírnnek nyilvánítjuk. Az elleoőrzések r számát nyilván úgy szeretnénk beállítani, hogy a tévedés valószínűsége (nern prím elfogadása) minél kisebb legyen ([28], [29]) .

Közös modulus választásának hibája Tegyük fel, hogy az RSA-kódolást alkalmazzuk egy sokfelhil.5ználós rendszerben, és egy Pl , P2 prímpárt válas,tunk vélet len szelekci6val a teljes rendszer számára a kulcskiosztó központban. Ekkor az m = Pl . P2 modulus is

5.4

335

RSA-ALGORITMUS

közös a rendszerben. Az egyes felhasználóknak a központ függetlenül sorsolja az eA, eB, ee, . .. nyilvános kódoló paramétereket, majd kiszámolja a megfelelő dA, dB, de, ... titkos dekódoló paramétereket. A nyilvános paramétereket nyilvános, olvasható kulcstárban helyezzük el. Amikor egy új felhasználó a rendszerhez kíván csatlakozni, ezen igényével - a rendszeren kívül - egy kulcskiosztó központhoz fordul, ahol egyrészt bejegyzésre kerül, másrészt megkapja a titkos kulcsát. A közös modulus (m) választásának előnye lehetne, hogy a nyilvános kulcstárban kevesebb adatot kell tárolni (azaz nem kell a különböző mA, mB, me, ... modulusokat tárolni), továbbá elképzelhető, hogy azonos modulus az aritmetika hardver megvalósításában is egyszerűsítést eredményez a felhasználói eszközben. Az alábbiakban egy példán keresztül megmutatj uk, hogy közös modulus választásával súlyos rendszertervezési .hibát követnénk el, amelyre egy példát mutatunk. További példa található [29]-ben. Relatív prím kódoló kulcspár esete Abban az esetben, ha A és B felhasználók eA és eB kódoló kulcsa relatív prím és azonos nyílt tartalmú üzenet érkezik mindkét felhasználóhoz (pl. egy C felhasználót ól egy kör levél), akkor ezen üzenetet a támadó dekódolni képes anélkül, hogy ez egyben az RSA-kódolás megtörését (azaz m faktorizálását) jelentené. Legyenek YA = x eA (mod m) és YB = x eB (mod m) a támadó által megfigyelt, azonos nyílt üzenethez tartozó rejtett üzenetek. Ha (eA, eB) = 1, akkor az 5.4. tétel következménye alapján léteznek olyan t, s egészek, és eB > 0, ezért t és hogy t . eA + s . eB = 1 fennáll. Mivel eA > s egyike negatív. Legyen t < 0, azaz t = -1 . Iti. Feltehetjük, hogy (YA, m) = (YB, m) = 1, hiszen ellenkező esetben YA és m (illetve YB és m) legnagyobb közös osztója a Pl vagy P2, aminek megismerése a titkosító transzformáció (RSA-kód) feltörését jelentené. Ha pedig (YA, m) = 1, akkor YA (mod m) inverze (YA: I ) létezik, ahonnan

°

azaz anélkül, hogy feltörte volna a támadó az RSA-kódot, képes volt kiszámítani a rejtett üzenet nyílt tartalmát. A fentiekben elmondott algoritmikus támadás konklúziója az, hogy közös modulus választását mindenképpen el kell kerülni RSA-kódra alapuló rendszerekben.

336

5. KRIPTOGRÁFIA

A kicsi kódoló kulcsok problémája Az RSA-algoritmus paramétereinek megválasztásánál a kódoló e kitevőjére az 1 :::; e < cp( m), és (cp( m), e) = 1 megkötéseket tettük. Kisebb számításigényű a kódolás, ha e értékét kicsire választjuk, és ezt megtehetjük, mivel ezen választás - a mai ismeretek szerint - nem könnyíti meg az RSA-algoritmus feltörhetőségét. Ha azonban egy sokfelhasználós rendszerben kicsire (például tíznél kisebbre) választjuk valamely felhasználó e paraméterét, az bizonyos körülmények között nyílt üzenet kiszámítására adhat lehetőséget a támadó számára anélkül, hogy feltörné a titkosító kódot. Itt felelevenít jük a kínai maradéktételt, amely a kódoláselméletben széleskörben alkalmazható.

5.9. tétel (kínai maradéktétel). Ha az ml, m2, ... , mr pozitív egészek páronként relatív prímek, és al, a2, ... , ar tetszőleges egész számok, akkor az i=1,2, ... ,T kongruenciarendszernek van közös megoldása. Bármely két megoldás kongruens modulo ml . m2··· mr. Ha m = ml . m2··· mr, akkor ~ egész és (~, mj) = l. Ezért az 5.5. tétel értelmében léteznek olyan bj egészek, hogy ;:::. bj = 1 J (mod mj). Mivel mi I ;:::., ezért ;:::. bj = O (mod mi), ha i :f=. j. Ha az Xl J J egészet a következőképpen definiáljuk: BIZONYÍTÁS:

(5.29) azt kapjuk, hogy

azaz Xl közös megoldása a kongruenciáknak. Ha Xl és X2 mindketten megoldásai az X = ai (mod mi), i = 1,2, ... , T kongruenciáknak, akkor nyilván Xl = X2 (mod mi), i = 1,2, ... ,T. Azaz mi I (Xl - X2), i = 1,2, ... ,T, amiből az (mi, mj) = 1, i :f=. j feltétel miatt m I (Xl - X2) következik, így Xl = X2 (mod m). •

5.5

337

KRIPTOGRÁFIAI PROTOKOLLOK

Ha egy sokfelhasználós rendszerben kicsi az a tartomány, amelyből az e kitevőket választj uk, akkor előfordulhat, hogy több felhasználó ugyanazt az e kitevőt kapja, de természetesen függetlenül választják a prímpárt, így különböző dekódoló kulcsok és modulusok tartoznak hozzájuk (pl. okulva a közös modulus választásának következményeiből). Tegyük fel ekkor, hogy egy felhasználó az (e, ml), (e, m2), ... , (e, mr) nyilvános kódolás i paraméterekkel rendelkező r (r ~ e) számú különböző felhasználónak ugyanazt az x üzenetet küldi, s a támadó rendelkezésére állnak a megfelelő: Yl

xe (mod ml)

Y2

xe (mod m2)

(5.30)

rejtett üzenetek. Ha ml, m2, ... ,mr relatív prímek, akkor a kínai maradéktétel felhasználásával kiszámíthatja az xe (mod mlm2 ... mr) hatványt. Mivel x < min{ mi} miatt

ezért magát az xe hatvány t (és nem csak modulo ekvivalensét) ismeri, így innen már x értékét is kiszámíthatja. Ha azonban az üzenetküldő az üzenet küldési időpontját is elhelyezi az üzenetben (időpecsét), akkor az azonos x üzenetet a tl, t2, . .. ,tr küldési időpontok módosítják, s különböző kódolandó nyílt üzenetekké válnak.

5.5.

Kriptográfiai protokollok

Algoritmikus szempontból egy titkosító rendszer két fő komponenst tartalmaz: egyrészt a titkosító kódoló és dekódoló transzformációkat, másrészt kriptográfiai protokollokat. A protokoll algoritmikus lépések sorozata két vagy több résztvevő partner között valamely feladat végrehajtása céljából. Szükségesek olyan szabályok, amelyek biztosítják, hogy a titkosító transzformációk egy adott alkalmazásban a megkívánt titkosságot vagy hitelességet nyújtsák. A transzformáció többnyire egy kulcsot használ, de a transzformációt végrehajtó algoritmus nem gondoskodik e kulcs védett célbajuttatásáról (kulcskiosztás ), a tárolás ideje alatti algoritmikus védelméről (pl. hitelességének biztosítása). Aktív támadások ellen egy titkosító transzformáció önmagá~an nem véd, így megfelelő szabályokkal kell gondoskodni