\magnification=\magstep1
\input amstex
\hsize=16truecm
\parskip=2.5pt plus 1pt
\TagsOnRight

\define\A{{\bold A}}
\define\BB{{\bold B}}
\define\DD{{\bold D}}
\define\T{{\bold T}}
\define\U{{\bold U}}
\define\({\left(}
\define\){\right)}
\define\[{\left[}
\define\]{\right]}
\define\e{\varepsilon}
\define\oo{\omega}
\define\const{\text{\rm const.}\,}
\define\Var{\text{\rm Var}\,}
\define\Cov{\text{\rm Cov}\,}
\define\supp {\sup\limits}
\define\inff{\inf\limits}
\define\summ{\sum\limits}
\define\prodd{\prod\limits}
\define\limm{\lim\limits}
\define\limsupp{\limsup\limits}
\define\liminff{\liminf\limits}
\define\bigcapp{\bigcap\limits}
\define\bigcupp{\bigcup\limits}
\def\Re{\text{\rm Re}\,}
\font\script=cmcsc10


\beginsection 2. Forr\'ask\'odol\'as \'es dek\'odol\'as.

Az inform\'aci\'oelm\'elet egyik legfontosabb probl\'em\'aja
a k\"ovetkez\H{o} k\'odol\'asi probl\'em\'anak nevezett
k\'erd\'es. Legyen adva val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok
valamely $\xi_1,\xi_2,\dots$ v\'eges vagy v\'egtelen sorozata,
amelynek tagjai \'ert\'ek\"uket valamely $X$ v\'eges vagy
megsz\'aml\'alhat\'oan v\'egtelen sz\'amoss\'ag\'u halmazban 
veszik fel. A $\xi_1,\xi_2\dots$ sorozatot forr\'asnak, a 
$\xi_j$ va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi v\'altoz\'ok 
\'altal felvett \'ert\'ekek $X$ halmaz\'at pedig (forr\'as) 
ABC-nek szok\'as nevezni az irodalomban. Ennek a
$\xi_1,\xi_2\dots$ sorozatnak az \'ert\'ekeit szeretn\'enk
k\"oz\"olni valakivel, akit felhaszn\'al\'onak nevez\"unk.
E c\'el el\'er\'ese \'erdek\'eben bizonyos jeleket le\-adunk
a felhaszn\'al\'onak, aki ezeket a jeleket, esetleg
n\'emi hib\'aval, megkapja. Azt az appar\'atust, amely
ezeket a jeleket tov\'abb\'{\i}tja csa\-tor\-n\'a\-nak nevezz\"uk.
A felhaszn\'al\'o, a csatorn\'an kereszt\"ul megkapott jelek
seg\'{\i}ts\'eg\'evel megpr\'ob\'alja rekonstru\'alni az eredeti
$\xi_1,\xi_2,\dots$ \"uzenetet. Tegy\"uk fel, hogy a kiindul\'o
$\xi_1,\xi_2,\dots$ sorozat egym\'as ut\'ani jelei meg\'erkeznek
bizonyos sebess\'eggel, \'es mi le tudjuk adni a csatorn\'an a
jeleinket a felhaszn\'al\'onak bizonyos sebess\'eggel. A k\'erd\'es
az, hogy mikor tudjuk egy a felhaszn\'al\'oval kor\'abban
egyeztetett m\'odszer seg\'{\i}ts\'eg\'evel el\'erni, hogy \H{o} a
kapott jelsorozat seg\'{\i}ts\'eg\'evel viszonylag kis hib\'aval
rekonstru\'alni tudja az eredeti $\xi_1,\xi_2,\dots$ forr\'ast.

Az el\H{o}bb megfogalmazott k\'odol\'asi probl\'ema egy tipikus
esete az, ha egy sz\"oveg egym\'as ut\'ani bet\H{u}i \'erkeznek (a
sz\'ok\"ozi sz\"uneteket k\"ul\"on jelnek tekintj\"uk), \'es ezt a
folyamatosan \'erkez\H{o} sz\"oveget akarjuk k\"oz\"olni egy
t\H{o}l\"unk t\'avol lev\H{o} ismer\H{o}s\"unknek. Ennek
\'erdek\'eben le tudunk adni egym\'as ut\'an 0 \'es 1 jeleket egy
t\'av\'{\i}r\'on. Azt akarjuk el\'erni, hogy ismer\H{o}s\"unk, aki
e jeleket megkapja k\'epes legyen viszonylag pontosan
rekonstru\'alni az eredeti sz\"oveget m\'eg akkor is, ha a
jeltov\'abb\'{\i}t\'asban id\H{o}nk\'ent hib\'ak l\'epnek fel.
Azt vizsg\'aljuk, hogy ez mikor lehets\'eges. C\'elszer\H{u} az
egyes bet\H{u}knek bizonyos jelsorozatot (k\'odot) megfeleltetni.
\'Ugy k\'{\i}v\'anjuk ezt tenni, hogy ismer\H{o}s\"unk k\'epes
legyen a kapott jelsorozat seg\'{\i}ts\'eg\'evel viszonylag
pontosan rekonstru\'alni (dek\'odolni) az eredeti sorozatot m\'eg
akkor is, ha a leadott jelsorozat egyes jelei hib\'asan
\'erkeznek meg hozz\'a.

C\'elunkat el\'erhetj\"uk p\'eld\'aul \'ugy, hogy mindegyik
bet\H{u}nek ugyanolyan hossz\'u \'es egy\-m\'as\-t\'ol
k\"ul\"onb\"oz\H{o} k\'odsz\'ot feleltet\"unk meg, \'es mindegyik
k\'od\-sz\'ot egym\'as ut\'an sz\'az\-szor k\"uldj\"uk el a
csatorn\'an. Ekkor kicsi annak a val\'osz\'{\i}n\H{u}s\'ege,
hogy egy ilyen 100-szor el\-k\"ul\-d\"ott jel az esetek
t\"obbs\'eg\'eben helytelen\"ul \'erkezik, \'{\i}gy
ismer\H{o}s\"unk nagy  va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'eg\-gel
rekonstru\'alni tudja az eredeti \"uzenetet. A probl\'ema az,
hogy ilyen m\'odszerrel az \"uzenet tov\'abb\'{\i}t\'asa
t\'uls\'agosan sok id\H{o}t vesz ig\'enybe, \'es ez\'ert esetleg
nem tudjuk k\"ovetni az eredetileg \'erkez\H{o} jelsorozat
sebess\'eg\'et. C\'elunk teh\'at az, hogy egy olyan m\'odszert
dolgozzunk ki, amelynek seg\'{\i}ts\'eg\'evel az eredeti 
h\'{\i}rforr\'ast viszonylag gyorsan \'es viszonylag pontosan 
meg tudjuk ismertetni a felhaszn\'al\'oval. A m\'odszer 
kidolgoz\'as\'an\'al \'erdemes
figyelembe venni azt, hogy a (v\'eletlen) $\xi_1,\xi_2,\dots$
forr\'as milyen val\'osz\'{\i}n\H{u}s\'egi t\"orv\'enynek tesz
eleget, illetve, hogy milyen val\'osz\'{\i}n\H{u}s\'eggel
k\"ovetkeznek be bizonyos hib\'ak, amikor a jeleket leadjuk a
csatorn\'an.

Az el\H{o}bb megfogalmazott k\'odol\'asi probl\'em\'at \'erdemes
a k\"ovetkez\H{o} k\'et probl\'ema vizsg\'alat\'anak a
seg\'{\i}ts\'eg\'evel megoldani. Az els\H{o} probl\'ema a
k\"ovetkez\H{o}. Adva egy r\"ogz\'{\i}tett $n$ sz\'am, \'es
egy r\"ogz\'{\i}tett $Y=\{y_1,\dots,y_d\}$ v\'eges halmaz
tekints\"uk a
$$
\xi_{ln+1},\dots,\xi_{l(n+1)}, \qquad l=1,2,\dots,
$$
blokkokat. Egy ilyen blokk minden lehets\'eges
$(\xi_{ln+1},\dots,\xi_{l(n+1)})=(x_{p(1)},\dots,x_{p(n)})$
\'er\-t\'e\-k\'e\-nek feleltess\"unk meg egy az $Y$ halmazbeli
$f(x_{p(1)},\dots,x_{p(n)})=(y_{r(1)},\dots,y_{r(k(n))})$
ele\-mek\-b\H{o}l \'all\'o $k(n)$ hossz\'us\'ag\'u sorozatot
\'ugy, hogy a $k(n)$ hossz\'us\'ag\'u $Y$ halmazbeli sorozatokon
l\'etezz\'ek olyan $g(y_{r(1)},\dots,y_{r(k(n))})$ f\"uggv\'eny,
amelyre
$$
P(g(f(\xi_{ln+1},\dots,\xi_{(l+1)n}))
=(\xi_{ln+1},\dots,\xi_{(l+1)n}))\ge1-\e\quad\ \text{minden }
l=1,2,\dots \text{ indexre}   \tag2.1
$$
egy kis fix $\e>0$ sz\'ammal. Az $f(\cdot)$ f\"uggv\'enyt
k\'od\-f\"ugg\-v\'eny\-nek, az $f(x_{p(1)},\dots,x_{p(n)})$
sorozatot az $x_{p(1)},\dots,x_{p(n)}$ sorozat k\'odj\'anak
nevezz\"uk, a $g(\cdot)$ f\"uggv\'enyt pedig dek\'odol\'o
f\"uggv\'enynek h\'{\i}vjuk. Azt mondjuk, hogy $\e$-n\'al
kisebb hib\'aval  k\'odoltunk, ha a (2.1)~re\-l\'a\-ci\'o
teljes\"ul. C\'elunk egy a (2.1) formul\'at teljes\'{\i}t\H{o}
$f(\cdot)$, $g(\cdot)$ f\"uggv\'enyp\'ar megtal\'al\'asa az $n$
blokkhosszt\'ol f\"ugg\H{o} viszonylag kis $k(n)$ sz\'ammal. E
feladat megold\'as\'at nevezz\"uk forr\'as k\'odol\'asnak \'es
forr\'as dek\'odol\'asnak. A m\'asodik feladat arr\'ol sz\'ol,
hogy amikor a forr\'as k\'odol\'asak\'ent kapott sorozat
\'ert\'ek\'et alkalmas csatorna esetleg hib\'as
k\"ozvet\'{\i}t\'ese seg\'{\i}ts\'eg\'evel k\"oz\"olj\"uk a
felhaszn\'al\'oval, akkor \H{o} hogyan tudja viszonylag kis
hib\'aval rekonstru\'alni a csatorn\'an kereszt\"ul elk\"uld\"ott 
sorozatot. Ezt a feladatot, amelyet csatorna k\'odol\'asnak \'es
dek\'odol\'asnak neveznek a k\"ovetkez\H{o} fejezetben fogom
t\'argyalni, \'es mag\'at a feladatot is csak ott fogom
pontosan megfogalmazni.

E fejezet t\'em\'aja a forr\'as k\'odol\'as \'es dek\'odol\'as.
Csak azzal az esettel fogok fog\-lal\-koz\-ni, amikor a
$\xi_1,\xi_2,\dots$ forr\'as f\"uggetlen \'es egyforma
eloszl\'as\'u v\'eges vagy meg\-sz\'am\-l\'al\-ha\-t\'o\-an
v\'egtelen sok \'ert\'eket felvev\H{o} val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'ok sorozata. Ebben az esetben egy j\'o forr\'as
k\'odol\'as \'es dek\'odol\'as megtal\'al\'asa viszonylag
egyszer\H{u} feladat, az k\"onnyen megtehet\H{o} az el\H{o}z\H{o}
fejezet eredm\'enyeinek a seg\'{\i}ts\'eg\'evel. T\'argyalni
fogom tov\'abb\'a ennek a feladatnak egy \"on\-ma\-g\'a\-ban is
\'erdekes v\'altozat\'at, amelyben egy v\'eletlen sorozatot akarunk
viszonylag r\"ovid sorozattal \'ugy k\'odolni, hogy az hib\'atlanul
dek\'odolhat\'o legyen. A k\'odolt sorozat hossza f\"ugghet a
v\'eletlent\H{o}l, de e v\'eletlen sz\'ohossz v\'arhat\'o
\'ert\'ek\'et szeretn\'enk kicsiv\'e tenni.

Megfogalmazom ezt a m\'odos\'{\i}tott feladatot pontosabban.
Legyen adva egy $\xi$ va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi
v\'altoz\'o, amely \'ert\'ekeit egy v\'eges $X=\{x_1,\dots,x_M\}$
halmazban veszi fel,  \'es amely\-nek ismert a $P(\xi=x_i)=p(i)$,
$1\le i\le M$, eloszl\'asa. (Az egyszer\H{u}s\'eg  kedv\'e\'ert
feltettem, hogy a $\xi$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o
$X$ \'ert\'ekk\'eszlete egy v\'eges halmaz, b\'ar t\"obb al\'abb
ismertetend\H{o} eredm\'eny akkor is \'erv\'enyes, ha az $X$
halmaz sz\'amoss\'aga megsz\'aml\'alhat\'oan v\'egtelen is
lehet.) Legyen adva egy v\'eges $d$-elem\H{u}
$Y=\{y_1,\dots,y_d\}$ halmaz, amelyet a tov\'abbiakban ABC-nek
fogunk nevezni, \'es a $\xi$ val\'osz\'{\i}n\H{u}s\'egi
v\'al\-to\-z\'o\-val azonos eloszl\'as\'u $\xi_1,\dots,\xi_l$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'oknak egy sorozata. Nevezz\"uk
az $Y$ halmaz elemeib\H{o}l \'all\'o  v\'eges $y_{j_1},\dots,y_{j_n}$
sorozatokat szavaknak. Minden $x_i\in X$ elemnek meg akarunk
feleltetni egy  $u(i)=y^{(i)}_{j_1},\dots,y^{(i)}_{j_{n(i)}}$ $n(i)$
hossz\'us\'ag\'u $Y$ halmaz elemeib\H{o}l \'all\'o sorozatot,
amelyet az $x_i$ sorozat nev\'enek fogunk nevezni. \'Ugy
k\'{\i}v\'anjuk ezt a megfeleltet\'est csin\'alni, hogy ha
egym\'as ut\'an felsorolj\'ak nek\"unk egy $x_{i_1},\dots,x_{i_l}$
sorozat elemeinek $u(i_1),\dots,u(i_l)$ neveit, akkor k\'epesek
legy\"unk ennek alapj\'an az $x_{i_1},\dots,x_{i_l}$ sorozatot
egy\'ertelm\H{u}en rekonstru\'alni. Az ilyen $x_i\to u(i)$,
$x_i\in X$, lek\'epez\'eseket egy\'ertelm\H{u}en dek\'odolhat\'o
k\'odol\'asoknak fogjuk nevezni. Ennek pontos definici\'oj\'at
al\'abb ismertetem. Azzal a k\'erd\'essel fogunk foglalkozni,
hogy milyen ki\-csi\-v\'e tudjuk tenni egy egy\'ertelm\H{u}en
dek\'odolhat\'o $x_i\to u(i)$, $1\le i\le M$, k\'odol\'as $n(i)$
hossz\'anak a v\'arhat\'o \'ert\'ek\'et, azaz a
$\summ_{i=1}^M p(i)n(i)$ mennyis\'eget.

\medskip\noindent
{\bf Az egy\'ertelm\H{u}en dek\'odolhat\'o k\'odol\'as
definici\'oja.} {\it Legyen $X=\{x_1,x_2,\dots\}$ egy v\'eges vagy
megsz\'aml\'alhat\'oan v\'egtelen sz\'amoss\'ag\'u halmaz \'es
$Y=\{y_1,\dots,y_d\}$ egy m\'asik $d$ elemsz\'am\'u halmaz (ABC).
Egy az $X$ halmaz elemeit az $Y$ halmaz elemeib\H{o}l \'all\'o v\'eges
elemsz\'am\'u $u(x_i)=y^{(i)}_{j_1}\dots y^{(i)}_{j_n}$ sorozatokba
k\'epez\H{o} lek\'epez\'es\'et az $X$ halmaznak az $Y$ ABC szavaival
v\'egzett  egy\'ertelm\H{u}en dek\'odolhat\'o k\'odol\'as\'anak
nevez\"unk, ha minden $x_{i_1},\dots,x_{i_l}$, $l=1,2,\dots$,
$x_{i_j}\in X$,  $1\le j\le l$, sorozatnak az
$u(x_{i_1}),\dots,u(x_{i_l})$ sorozatot megfeleltetve teljes\"ul
az $u(x_{i_1}),\dots,u(x_{i_{l_1}})
\neq u(x'_{i_1}),\dots,u(x'_{i_{l_2}})$ rel\'aci\'o, ha
$x_{i_1},\dots,x_{i_{l_1}}\neq x'_{i_1},\dots,x'_{i_{l_2}}$.}

\medskip\noindent
El\H{o}sz\"or az eredeti k\'odol\'asi feladattal foglalkozom.
Megfogalmazom azt az eredm\'enyt, amelyik megadja, hogy milyen
$k(n)$ hossz\'us\'ag\'u \'es egy $Y=\{y_1,\dots,y_d\}$ halmaz
elemeib\H{o}l \'all\'o sorozatok  seg\'{\i}ts\'eg\'evel lehet
megadni valamely f\"uggetlen, egyforma eloszl\'as\'u
$\xi_1,\dots,\xi_n$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'okb\'ol
\'all\'o forr\'asnak egy $\e$-n\'al kisebb hib\'aj\'u, azaz
a (2.1) rel\'aci\'ot teljes\'{\i}t\H{o} $f(\cdot)$
k\'odol\'as\'at \'es $g(\cdot)$ dek\'odol\'as\'at.

\medskip\noindent
{\bf T\'etel f\"uggetlen, egyforma eloszl\'as\'u
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'okb\'ol \'all\'o forr\'as
kis hib\'aj\'u k\'odol\'as\'ar\'ol \'es dek\'odol\'as\'ar\'ol.}
{\it Legyen $\xi$ egy \'ert\'ekeit valamely v\'eges vagy
megsz\'aml\'alhat\'oan v\'egtelen sz\'amoss\'ag\'u
$X=\{x_1,x_2,\dots\}$ halmazon f\"olvev\H{o}
val\-\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi v\'altoz\'o,
$\xi_1,\dots,\xi_n$ pedig f\"uggetlen, a $\xi$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'oval azonos eloszl\'as\'u
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi v\'altoz\'ok sorozata.
Legyen ezenk\'{\i}v\"ul adva egy $Y=\{y_1,\dots,y_d\}$
$d$ elem\-sz\'a\-m\'u halmaz. Ekkor minden $\e>0$ \'es $\delta>0$
sz\'amhoz l\'etezik $n_0=n_0(\e,\delta)$ k\"usz\"obindex \'ugy,
hogy $n\ge n_0$ eset\'en minden
$k(n)\ge(1+\delta)\frac{H(\xi) n}{\log d}$
sz\'amra l\'eteznek olyan $f\colon\;X^n\to Y^{k(n)}$ \'es
$g\colon\;Y^{k(n)}\to X^n$ f\"uggv\'enyek, ahol $X^n$
az $X$ halmazbeli elemekb\H{o}l \'all\'o $n$ hossz\'us\'ag\'u,
$Y^{k(n)}$ pedig az $Y$ halmazbeli elemekb\H{o}l \'all\'o
$k(n)$ hossz\'us\'ag\'u sorozatok halmaza, amelyekre
$P(g(f(\xi_1,\dots,\xi_n))=(\xi_1,\dots,\xi_n))\ge1-\e$.
M\'asr\'eszt minden $k(n)\le(1-\delta)\frac{H(\xi) n}{\log d}$
sz\'amra \'es $f\colon\;X^n\to Y^{k(n)}$ \'es
$g\colon\;Y^{k(n)}\to X^n$ f\"uggv\'enyekre
$P(g(f(\xi_1,\dots,\xi_n))=(\xi_1,\dots,\xi_n))\le\e$.}

\medskip\noindent
{\it Bizony\'{\i}t\'as.} L\'attuk a
 f\"uggetlen val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'okb\'ol \'all\'o tipikus sorozatok sz\'am\'ar\'ol
sz\'ol\'o t\'etel bizony\'{\i}t\'as\'aban (ha megsz\'aml\'alhat\'oan
v\'egtelen sz\'amoss\'ag\'u halmazokkal aka\-runk dolgozni,
akkor e t\'etelnek a kieg\'esz\'{\i}t\'esben t\'argyalt
\'al\-ta\-l\'a\-no\-s\'{\i}\-t\'a\-s\'at kell tekinten\"unk),
hogy $n\ge n_0(\e,\delta)$ eset\'en l\'etezik olyan
$A\subset X^n$ halmaz, amelyre az $A$ halmaz kevesebb, mint
 $2^{(1+\delta)H(\xi)n}$ elemet tartalmaz, \'es
$P((\xi_1,\dots,\xi_n)\in A)\ge 1-\e$. M\'asr\'eszt az $Y^{k(n)}$
halmaz elemsz\'ama $d^{k(n)}\ge 2^{(1+\delta)H(\xi)n}$, ha
$k(n)\ge(1+\delta)\frac{H(\xi) n}{\log d}$. Ez\'ert l\'etezik egy
k\"olcs\"on\"osen egy\'ertelm\H{u} megfeleltet\'es az $A$ halmaz
\'es az $Y^{k(n)}$ valamely $B\subset Y^{k(n)}$ r\'eszhalmaza
k\"oz\"ott. Ha $x=(x_{j_1},\dots,x_{j_n})\in A$, akkor defini\'aljuk
az $f(\cdot)$ f\"uggv\'eny \'ert\'ek\'et ebben az $x$ pontban,
mint azt az $y\in B$ pontot, amely e k\"olcs\"on\"osen
egy\'ertelm\H{u} megfeleltet\'es szerint az $x$ pontnak megfelel.
Ha $x\notin A$, akkor az $f(x)$ f\"uggv\'enyt
tetsz\H{o}leges m\'odon defini\'alhatjuk. Hasonl\'oan,
ha $y=(y_1,\dots,y_{j_{k(n)}})\in B$, akkor legyen $g(y)$ az $y$
pontnak megfelel\H{o} $x\in X^n$ pont ezen k\"olcs\"on\"osen
egy\'ertelm\H{u} megfeleltet\'es szerint, \'es defini\'aljuk
a $g(y)$ f\"uggv\'enyt egy\'ebk\'ent tetsz\H{o}leges m\'odon.
Ilyen v\'alaszt\'assal $P(g(f(\xi_1,\dots,\xi_n))
=(\xi_1,\dots,\xi_n))\ge P((\xi_1,\dots,\xi_n)\in A)\ge1-\e$.

A t\'etel m\'asodik fel\'enek bizony\'{\i}t\'as\'aban haszn\'aljuk
ki, hogy $n\ge n_0$ eset\'en l\'etezik olyan $\bar A\subset X^n$
halmaz, amelyre $P((\xi_1,\dots,\xi_n)\in\bar A)\ge1-\frac\e2$,
\'es minden $(x_{j_1},\dots,x_{j_n})\in \bar A$ vektorra
$P((\xi_1,\dots,\xi_n)=(x_{j_1},\dots,x_{j_n}))
\le 2^{-(1-\frac\delta2)H(\xi)n}$. Ha
$k(n)\le(1-\delta)\frac{H(\xi) n}{\log d}$ eset\'en is lenne olyan
$f(\cdot)$, $g(\cdot)$ f\"uggv\'enyp\'ar, amelyre
$P(g(f(\xi_1,\dots,\xi_n))=(\xi_1,\dots,\xi_n))\ge\e$,
akkor l\'etezne olyan $A_0\subset X^n$ halmaz, amelyre
$P((\xi_1,\dots,\xi_n)\in A_0)\ge\e$, \'es az \"osszes
$x=(x_{j_1},\dots,x_{j_n})\in A_0$ vektor $f(x)\in Y^{k(n)}$
k\'epe k\"ul\"onb\"oz\H{o} lenne. (Az $A_0$ halmazt \'ugy
v\'alaszthatjuk, mint azon $x\in X^n$ vektorok halmaz\'at,
amelyekre $g(f(x))=x$.) Ekkor az is igaz lenne, hogy
$P((\xi_1,\dots,\xi_n)\in A_0\cap\bar A)\ge\frac\e2$, \'es minden
$x\in A_0\cap\bar A$ vektorra $P((\xi_1,\dots,\xi_n)=x)
\le 2^{-(1-\frac\delta2)H(\xi)n}$. Innen k\"ovetkezne,
hogy az $A_0\cap\bar A$ halmaz elemsz\'ama nagyobb, mint
$\frac\e2 2^{(1-\frac\delta2)H(\xi)n}\ge
2^{(1-\delta)H(\xi)n}$, ha $n\ge n_0(\e,\delta)$.
Ez ellentmond annak, hogy minden $x\in A_0\cap \bar A$
vektor $f(x)$ k\'epe k\"ul\"onb\"oz\H{o}, mert az $Y^{k(n)}$
halmaz elemsz\'ama $d^{k(n)}<2^{(1-\delta)H(\xi)n}$.

\medskip\noindent
{\it Megjegyz\'es.}\/ Mivel a tekintett $\xi_1,\xi_2,\dots$
sorozat f\"uggetlen \'es egyforma eloszl\'as\'u
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi v\'altoz\'okb\'ol \'all,
abb\'ol, hogy egy alkalmas $f(\cdot)$, $g(\cdot)$
f\"uggv\'enyp\'ar teljes\'{\i}ti a t\'etelben bizony\'{\i}tott
$P(g(f(\xi_1,\dots,\xi_n))=(\xi_1,\dots,\xi_n))\ge1-\e$.
rel\'aci\'ot, ha $k(n)\ge(1+\delta)\frac{H(\xi)n}{\log d}$,
k\"ovetkezik, hogy ebben az esetben a (2.1) formula is
\'erv\'enyes.

\medskip\noindent
R\'at\'erek az egy\'ertelm\H{u}en dek\'odolhat\'o k\'odok
vizsg\'alat\'ara. Azt vizsg\'aljuk, hogyan lehet egy $M$
elemb\H{o}l \'all\'o $X=\{x_1,\dots,x_M\}$ halmaz elemeit,
pontosabban ezen elemekb\H{o}l \'all\'o sorozatokat
hib\'atlanul k\'odolni \'es dek\'odolni viszonylag
r\"ovid k\'odokkal egy $d$ elem\H{u} $Y=\{y_1,\dots,y_d\}$
ABC seg\'{\i}s\'eg\'evel. Az \'altal\'anoss\'ag
megszor\'{\i}t\'asa n\'elk\"ul feltehetj\"uk,
hogy $Y=\{1,\dots,d\}$. \'Erdemes bevezetni a
k\"o\-vet\-ke\-z\H{o} fogalmat.

\medskip\noindent
{\bf Prefix k\'odok definici\'oja.} {\it Legyen adva egy
$X=\{x_1,\dots,x_M\}$ halmaz, \'es egy $Y=\{1,\dots,d\}$
ABC. Feleltess\"unk meg minden $x_i\in X$ elemnek egy
$u(x_i)=j^{(i)}_1,\dots j^{(i)}_{n(i)}$, $1\le j^{(i)}_s\le d$,
$1\le s\le n(i)$, sorozatot. Azt mondjuk, hogy ez a
megfeleltet\'es az $X$ halmaz elemeinek prefix k\'odja,
ha nincs olyan $x_p\in X$, $x_q\in X$ p\'ar, amelyre
az $u(x_p)$ sorozat az $u(x_q)$ sorozat megszor\'{\i}t\'asa
annak elej\'ere, azaz semmilyen $x_p$, $x_q$ p\'arra
nem lehet megkapni az $u(x_p)$ sorozatot \'ugy, hogy alkalmas
sz\'am\'u jelet let\"orl\"unk az $u(x_q)$ sorozat
v\'eg\'er\H{o}l.}

\medskip
Fontos lesz sz\'amunkra az al\'abbi lemm\'aban megfogalmazott
egyszer\H{u} \'esz\-re\-v\'e\-tel.

\medskip\noindent
{\bf Lemma a prefix k\'odok egy tulajdons\'ag\'ar\'ol.}
{\it Minden prefix k\'od egy\'ertelm\H{u}en
de\-k\'o\-dol\-ha\-t\'o k\'od.}

\medskip\noindent
{\it Bizony\'{\i}t\'as.}\/ Ha egy $x_1,\dots,x_n$ sorozatnak
egy $u(x_1),u(x_2),\dots,u(x_n)$ prefix k\'od felel meg, akkor
a prefix tulajdons\'ag alapj\'an meg tudjuk \'allap\'{\i}tani,
hol fejez\H{o}dik be e sorozatban az $u(x_1)$, sorozat, \'es \'{\i}gy
azonos\'{\i}that\'o az $x_1$ jel. Ezut\'an rekurz\'{\i}v m\'odon
meg tudjuk hat\'arozni egym\'as ut\'an az $x_2$, $x_3$,\dots
\'ert\'eketet is.

\medskip
L\'eteznek nem prefix, de egy\'ertelm\H{u}en dek\'odolhat\'o
k\'odok. P\'eld\'aul, ha $X$ k\'et elem\H{u} halmaz, \'es $D=\{1,2\}$
v\'alaszthatjuk $x_1$ k\'odj\'anak az 1, $x_2$ k\'odj\'anak az 1,2
sorozatot. Vagy $x_1$ k\'odj\'anak az 1, $x_2$ k\'odj\'anak az
$1,\dots,1,2$ sorozatot, ahol az 1 jeleknek egy $n$ hossz\'us\'ag\'u
sorozat\'at vett\"uk a 2 jel el\H{o}tt egy
tetsz\H{o}leges (ismert) pozit\'{\i}v eg\'esz $n$ sz\'ammal.
Ezek egy\'ertelm\H{u}en dek\'odolhat\'o, de nem prefix k\'odok.
Viszont, mint l\'atni fogjuk, minden egy\'ertelm\H{u}en
dek\'odolhat\'o k\'odhoz lehet tal\'alni egy legal\'abb ugyanolyan
j\'o prefix k\'odot, ez\'ert figyelm\"unket koncentr\'alhatjuk a
prefix k\'odokra. Ezeknek megvan az az
el\H{o}ny\"uk is, hogy gyorsan dek\'odolhat\'oak. Ha egym\'as ut\'an
meg\'erkeznek az $x_{j_1}$, $x_{j_2},\dots$, jelek prefix k\'odjai,
akkor mihelyt meg\'erkezett egy jel k\'odja, azonnal dek\'odolhatjuk
azt. Nem prefix, de egy\'ertelm\H{u}en dek\'odolhat\'o k\'odok
eset\'eben a helyzet bonyolultabb. P\'eld\'aul, ha a k\'et elem\H{u}
$X$ halmaz $x_1$ elem\'enek a k\'odszava 1, az  $x_2$ elem k\'odszava
$1,\dots,1,2$, ($n$ darab 1 jellel), akkor egy 1 jel meg\'erkez\'ese
ut\'an lehet, hogy m\'eg $n$ jel meg\'erkez\'es\'et is meg kell
v\'arni, \'es csak azut\'an tudjuk eld\"onteni, hogy ez az 1-es jel
az $x_1$ k\'odszava vagy az $x_2$ k\'odszav\'anak az els\H{o} eleme
volt-e. Egy\'ebk\'ent l\'etezik egy m\'odszer annak
eld\"ont\'es\'ere, hogy mikor dek\'odolhat\'o egy k\'od
egy\'ertelm\H{u}en, (l\'asd (Robert Ash: Information theory,
Theorem 2.2.1), de erre a meglehet\H{o}sen bonyolultan
bizony\'{\i}that\'o  eredm\'enyre nem lesz sz\"uks\'eg\"unk. Ez\'ert
azt nem t\'argyalom.

A k\"ovetkez\H{o} eredm\'enyben, amelyet
Kraft--egyenl\H{o}tlens\'egnek is h\'{\i}vnak az irodalomban,
megadjuk, hogy milyen hossz\'uak lehetnek egy prefix k\'od
k\'odszavai.

\medskip\noindent
{\bf T\'etel egy prefix k\'od szavainak lehets\'eges hossz\'ar\'ol.}
{\it Legyen $X=\{x_1,\dots,x_M\}$ egy $M$ elem\H{u} halmaz,
\'es legyen $u(x_i)$, $1\le i\le M$, e halmaz egy prefix k\'odja az
$Y=\{1,\dots,d\}$ $d$-elem\H{u} ABC-vel. Jel\"olje $n(i)$ az
$u(x_i)$ sz\'o k\'odhossz\'at. Ekkor teljes\"ul a
$\summ_{i=1}^M d^{-n(i)}\le1$ egyenl\H{o}tlens\'eg.
Megford\'{\i}tva, ha az $n(i)$, $1\le i\le M$, pozit\'{\i}v eg\'esz
sz\'amok sorozata teljes\'{\i}ti a $\summ_{i=1}^M d^{-n(i)}\le1$
egyenl\H{o}tlens\'eget, akkor l\'etezik az $X$ halmaz elemeinek
olyan $u(x_i)$, $1\le i\le M$, prefix k\'odja az $Y=\{1,\dots,d\}$
$d$-elem\H{u} ABC-vel, amelyre az $u(x_i)$ sz\'o k\'odhossza $n(i)$.}

\medskip\noindent
{\it Bizony\'{\i}t\'as.}\/ Feltehetj\"uk, hogy az $x_i\in X$
elemek \'ugy vannak indexelve, hogy $n(1)\le n(2)\le\cdots\le n(M)$.
Ha adva van egy $u(x_i)$, $1\le i\le M$, prefix k\'od, akkor
minden egyes $u(x_i)$ k\'odsz\'onak feleltess\"uk meg az \"osszes
olyan $n(M)$ hossz\'us\'ag\'u, az $Y=\{1,\dots,d\}$ halmaz
elemeib\H{o}l \'all\'o sorozatok halmaz\'at, amely sorozatok az
$u(x_i)$ k\'odsz\'o folytat\'asai. Az $u(x_i)$ k\'odsz\'onak
$d^{n(M)-n(i)}$ ilyen folytat\'asa van, \'es az $u(\cdot)$ k\'od
prefix tulajdons\'aga miatt \'{\i}ly m\'odon csupa
k\"ul\"onb\"oz\H{o} $n(M)$ hossz\'us\'ag\'u az $\{1,\dots,d\}$
halmaz elemeib\H{o}l \'all\'o sorozatot kapunk. Mivel \"osszesen
$d^{n(M)}$ ilyen sorozat van, ez\'ert
$\summ_{i=1}^M d^{n(M)-n(i)}\le d^{n(M)}$. Innen $d^{n(M)}$-mel
osztva megkapjuk a $\summ_{i=1}^M d^{-n(i)}\le1$
egyen\-l\H{o}t\-len\-s\'e\-get.

Ha adva van egy $1\le n(1)\le n(2)\le\cdots\le n(M)$ a
$\summ_{i=1}^M d^{-n(i)}\le1$ egyenl\H{o}tlens\'eget
teljes\'{\i}t\H{o} sorozat, akkor a k\"ovetkez\H{o} m\'odon tudunk
a k\'{\i}v\'ant hossz\'us\'ag\'u k\'odszavakb\'ol \'all\'o prefix
k\'odot konstru\'alni. Legyen $u(x_1)$ tetsz\H{o}leges $n(1)$
hossz\'us\'ag\'u az $Y=\{1,\dots,d\}$ halmaz elemeib\H{o}l \'all\'o
sorozat. Az $i$ v\'altoz\'o szerinti indukci\'oval defini\'aljuk
az $u(x_i)$ k\'odszavakat \'ugy, hogy az $u(x_1),\dots,u(x_i)$
k\'odszavak az $X_i=\{x_1,x_2,\dots,x_i\}$ halmaz prefix
k\'odj\'at alkoss\'ak. Ha az $i-1$ indexre tal\'altunk ilyen
k\'odszavakat, akkor a prefix tulajdons\'ag meg\H{o}rz\'es\'ehez
az indukci\'o $i$-ik l\'ep\'es\'eben el\'eg olyan $n(i)$
hossz\'us\'ag\'u $u(x_i)$ k\'odsz\'ot tal\'alni, amely nem
folytat\'asa egyik $u(x_j)$, $1\le j\le i-1$, k\'odsz\'onak sem.
Ez azt jelenti, hogy az $d^{n(i)}$ darab $n(i)$ hossz\'us\'ag\'u,
az $Y=\{1,\dots,d\}$ halmaz elemeib\H{o}l \'all\'o sorozat
k\"oz\"ul $\summ_{j=1}^{i-1} d^{n(i)-n(j)}$ sorozat
v\'alaszt\'asa van tiltva. Akkor tudunk egy k\'{\i}v\'ant
tulajdons\'ag\'u $u(x_i)$ sorozatot (k\'odsz\'ot) v\'alasztani,
ha $\summ_{j=1}^{i-1} d^{n(i)-n(j)}<d^{n(i)}$, azaz, ha
$\summ_{j=1}^{i-1} d^{-n(j)}<1$. Az adott felt\'etel mellett ez
a tulajdons\'ag minden $2\le i\le M$ indexre teljes\"ul. Ezzel
bel\'attuk a t\'etel m\'asodik \'all\'{\i}t\'as\'at is.

\medskip
A k\"ovetkez\H{o} eredm\'eny azt \'all\'{\i}tja, hogy adott
sz\'ohossz\'us\'ag\'u k\'odszavakkal rendelkez\H{o} prefix
k\'odok l\'etez\'es\'enek sz\"uks\'eges felt\'etele
egyben annak is sz\"uks\'eges felt\'etele, hogy l\'etezzen
ilyen hossz\'us\'ag\'u k\'odszavakkal rendelkez\H{o}
egy\-\'er\-tel\-m\H{u}en de\-k\'o\-dol\-ha\-t\'o k\'od.

\medskip\noindent
{\bf T\'etel egy\'ertelm\H{u}en dek\'odolhat\'o k\'odok
l\'etez\'es\'enek sz\"uks\'eges felt\'etel\'er\H{o}l.} {\it Legyen
$X=\{x_1,\dots,x_M\}$ egy $M$ elem\H{u} halmaz, \'es legyen
$u(x_i)$ e halmaz egy egy\-\'er\-tel\-m\H{u}\-en dek\'odolhat\'o
k\'odja az $Y=\{1,\dots,d\}$ $d$-elem\H{u} ABC-vel. Ekkor az
$u(x_i)$ k\'odszavak $n(i)$ k\'odhosszai teljes\'{\i}tik a
$\summ_{i=1}^M d^{-n(i)}\le1$ egyenl\H{o}tlens\'eget.}

\medskip\noindent
{\it Bizony\'{\i}t\'as.}\/ Jel\"olje $\oo_j$ azon $x_i\in X$,
$1\le i\le M$, pontok sz\'am\'at, amelyek $u(x_i)$  k\'odszav\'anak
a hossza $n(i)=j$, \'es legyen $r=\supp_{1\le i\le M}n(i)$.
Ezzel a jel\"ol\'essel
$\summ_{i=1}^M d^{-n(i)}=\summ_{j=1}^r\oo_j d^{-j}$,
\'es a bizony\'{\i}tand\'o egyenl\H{o}tlens\'eg
$\summ_{j=1}^r\oo_j d^{-j}\le1$ alakban is \'{\i}rhat\'o.
Ezen egyenl\H{o}tlens\'eg igazol\'asa \'erdek\'eben vegy\"unk egy
pozit\'{\i}v eg\'esz $p$ sz\'amot, \'es \'{\i}rjuk fel a
$$
\(\summ_{j=1}^r\oo_j d^{-j}\)^p=(\oo_1d^{-1}+\cdots+\oo_rd^{-r})^p
=\sum_{k=p}^{pr} N_kd^{-k}
$$
azonoss\'agot, ahol
$$
N_k=\sum_{(i_1,\dots,i_p),\colon i_1+\cdots+i_p=k}
\oo_{i_1}\dots\oo_{i_p}, \quad p\le k\le pr.
$$
Azt \'all\'{\i}tom, hogy teljes\"ul az $N_k\le d^k$
egyenl\H{o}tlens\'eg minden $p\le k\le pr$ indexre. Val\'oban, az
$\oo_{i_1}\dots\oo_{i_p}$ szorzat azon
$u(x_{l_1}),\dots, u(x_{l_p})$ k\'odsz\'osorozatok sz\'am\'aval
egyenl\H{o}, amelyekre $n(l_1)=i_1$,\dots, $n(l_p)=i_p$. Ez\'ert
$N_k$ egyenl\H{o} azon $u(x_{l_1}),\dots, u(x_{l_p})$
k\'od\-sz\'o\-so\-ro\-za\-tok sz\'am\'aval, amelyek \"osszhossza
$k$-val egyenl\H{o}. Az egy\'ertelm\H{u} dek\'odolhat\'os\'ag miatt
az \"osszes el\H{o}bb felsorolt k\'odsz\'osorozat k\"ul\"onb\"oz\H{o},
ez\'ert sz\'amuk kisebb, mint az \"osszes lehets\'eges $k$
hossz\'us\'ag\'u az $Y=\{1,\dots,d\}$ halmaz elemeit tartalmaz\'o
sorozat sz\'ama. Ez\'ert $N_k\le d^k$, amint \'all\'{\i}tottuk.

A fenti \"osszef\"ugg\'esekb\H{o}l k\"ovetkezik, hogy
$$
\(\summ_{j=1}^r\oo_j d^{-j}\)^p\le
\sum_{k=p}^{pr} d^k\cdot d^{-k}=(p(r-1)+1)\le pr,
$$
\'es $p$-ik gy\"ok\"ot vonva, majd $p\to\infty$ hat\'ar\'atmenetet
v\'eve kapjuk, hogy
$$
\summ_{j=1}^r\oo_j d^{-j}\le\lim_{p\to\infty} (pr)^{1/p}=1,
$$
ahonnan k\"ovetkezik a bizony\'{\i}tani k\'{\i}v\'ant
$\summ_{j=1}^r\oo_j d^{-j}\le1$ egyenl\H{o}tlens\'eg.

A bizony\'{\i}t\'as gondolat\'anak jobb meg\'ert\'ese \'erdek\'eben
\'erdemes megjegyezni, hogy a vizsg\'alt
$\(\summ_{j=1}^r\oo_j d^{-j}\)^p$ kifejez\'es egyenl\H{o} az
\"osszes $u(x_{l_1}),\dots, u(x_{l_p})$ sorozat sz\'am\'aval. A
$p\to\infty$ hat\'ar\'atmenet alkalmaz\'asakor haszn\'altuk ki azt,
hogy a hossz\'u $x_{l_1},\dots,x_{l_p}$ sorozatok k\'odjai is
egy\'ertelm\H{u}en dek\'odolhat\'ok.

\medskip\noindent
Legyen adva egy $\xi$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o,
amely \'ert\'ekeit egy $X=\{x_1,\dots,x_M\}$ halmazon veszi
fel, \'es $P(\xi=x_i)=p(i)$, $1\le i\le M$. Legyen $u(x_i)$,
$x_i\in X$, az $X$ halmaz elemeinek egy olyan k\'odja,  amelyre
$u(x_i)$ egy $n(i)$ hossz\'us\'ag\'u az $Y=\{1,\dots,d\}$
halmaz elemeib\H{o}l \'all\'o sorozat. Jel\"olje $|u(\xi)|$ a
$\xi$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o $u(\xi)$
k\'odj\'anak a hossz\'at, azaz, ha $\xi=x_i$, akkor bevezetve
az $|u(x_i)|=n(i)$ jel\"ol\'est azt \'{\i}rhatjuk, hogy
$u(\xi)=u(x_i)$, \'es $|u(\xi)|=n(i)$. Az $u(\xi)$
v\'eletlen k\'odsz\'o $|u(\xi)|$ hossz\'anak a v\'arhat\'o
\'ert\'eke $E|u(\xi)|=\summ_{i=1}^M p(i)n(i)$. Az $u(\xi)$
v\'eletlen k\'odsz\'o hossz\'anak a v\'arhat\'o \'ert\'ek\'ere
k\'{\i}v\'anunk j\'o als\'o becsl\'est adni, ha $u(x_i)$,
$x_i\in X$ prefix, illetve \'altal\'anosabban, ha az egy\'ertelm\H{u}en
dek\'odolhat\'o k\'od. Ezenk\'{\i}v\"ul j\'o fels\H{o} becsl\'est
is akarunk adni egy j\'ol v\'alasztott prefix k\'od
hossz\'anak a v\'arhat\'o \'ert\'ek\'ere. 

Tudjuk, hogy akkor \'es csak akkor l\'etezik $n(i)$, $1\le i\le M$, 
hossz\'u, az $Y=\{1,\dots,d\}$ ABC-t haszn\'al\'o k\'odszavakkal 
rendelkez\H{o} prefix, illetve  \'altal\'anosabban 
egy\'ertelm\H{u}en dek\'odolhat\'o k\'od, ha teljes\"ul a 
$\summ_{i=1}^M d^{-n(i)}\le1$ egyenl\H{o}tlens\'eg. Ez\'ert 
probl\'em\'ank ahhoz az eg\'esz\'ert\'ek\H{u} sz\'els\H{o}\'ert\'ek 
fel\-adat\-hoz vezet, hogy keress\"uk meg a 
$\summ_{i=1}^M p(i)n(i)$ kifejez\'es (majdnem) optimum\'at a 
$\summ_{i=1}^M d^{-n(i)}\le1$ felt\'etel mellett. Ezen 
optimaliz\'aci\'os probl\'ema vizsg\'alat\'aban hasznos az al\'abbi 
becsl\'es, amelyet $I$-divergencia tipus\'u becsl\'esnek fogok 
h\'{\i}vni. Ugyanis, mint egy megjegyz\'esben el\-ma\-gya\-r\'a\-zom, 
ez a becsl\'es tekinthet\H{o}, \'ugy mint az inform\'aci\'oelm\'elet 
egyik fontos, a k\'es\H{o}bb bevezetend\H{o} $I$-divergenci\'ar\'ol
sz\'ol\'o becsl\'es\'enek a speci\'alis esete.

\medskip\noindent
{\bf Egy $I$-divergencia tipus\'u becsl\'est megfogalmaz\'o lemma.}
{\it Legyen $a_1,a_2,\dots$ \'es $b_1,b_2,\dots$ k\'et v\'eges vagy
v\'egtelen, ugyanannyi elemet tartalmaz\'o sorozat, amelyekre
$a_i\ge0$, $b_i\ge0$ minden $i$ indexre, \'es $a=\summ_ia_i<\infty$,
$b=\summ_ib_i<\infty$. Ekkor
$$
\sum_i a_i\log \frac{a_i}{b_i}\ge a\log \frac ab.
$$
(Ezen egyen\H{o}tlens\'egben az $x\cdot\log\frac0x=0$, ha $x\ge0$,
\'es $x\cdot\log\frac x0=\infty$, ha $x>0$ konvenci\'ot alkalmazzuk.)}

\medskip\noindent
{\it Bizony\'{\i}t\'as.}\/ Fel fogjuk haszn\'alni, hogy az els\H{o}
fejezetben bevezetett \'es vizsg\'alt $g(x)=x\log x$, $x\ge0$,
f\"uggv\'eny konvex. A $g(x)$ f\"uggv\'eny a konvexit\'as\'at az
$u_i=\frac{a_i}{b_i}$ koordin\'at\'ak, \'es
$p_i=\frac{b_i}{\summ_i b_i}=\frac{b_i}b$ s\'ulyok
v\'alaszt\'as\'aval fogom alkalmazni. (Ny\'{\i}lv\'an $p_i\ge0$,
\'es $\summ_i p(i)=1$.) A $g(x)$ f\"uggv\'eny konvexit\'as\'at
felhaszn\'alva azt kapjuk, hogy
$$
\sum_i a_i\log \frac{a_i}{b_i}=b\sum_i p_i g(u_i)\ge bg\(\sum_i p_iu_i\)
=bg\(\frac ab\)=a\log \frac ab.
$$

\medskip\noindent
{\it Megjegyz\'es.} A fenti lemm\'at k\"onnyen reduk\'alni lehet
arra a speci\'alis esetre, amikor $\sum_i a_i=\sum_i b_i=1$.
Ebben az esetben az egyenl\H{o}tlens\'eg jobboldal\'an 0 \'all.
Ez a reduk\'alt egyenl\H{o}tlens\'eg felfoghat\'o az al\'abbi
egyenl\H{o}tlens\'eg speci\'alis eset\'enek. Legyen $\mu$ \'es
$\nu$ k\'et olyan val\'osz\'{\i}n\H{u}s\'egi m\'ert\'ek
ugyanazon az $(X,\Cal X)$ m\'erhet\H{o} t\'eren, amelyekre a
$\nu$ m\'ert\'ek abszolut folytonos a $\mu$ m\'ert\'ekre
n\'ezve. Jel\"olje $\frac{d\nu}{d\mu}$ a $\nu$ m\'ert\'eknekek
a $\mu$ m\'ert\'ek szerinti Radon--Nikodym deriv\'altj\'at.
Ekkor $\int_X\frac{d\nu}{d\mu}(x)\,d\nu(x)\ge0$. Ez az
egyenl\H{o}tlens\'eg tekinthat\H{o} \'ugy, mint a k\'es\H{o}bb
bevezetend\H{o} $I$-divergencia egy fontos tulajdons\'aga.
Egy\'ebk\'ent ez az egyenl\H{o}tlens\'eg a lemm\'ahoz hasonl\'oan
bizony\'{\i}that\'o.

\medskip
A most ismertetett  lemma seg\'{\i}t az al\'abbi eredm\'eny
bizony\'{\i}t\'as\'aban.

\medskip\noindent
{\bf T\'etel egy\'ertelm\H{u}en dek\'odolhat\'o \'es
prefix k\'odok hossz\'anak v\'arhat\'o \'er\-t\'e\-k\'e\-r\H{o}l.}
{\it Vegye fel egy $\xi$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o
\'ert\'ekeit egy $X=\{x_1,\dots,x_M\}$ halmazon, amely\-nek
 az eloszl\'as\'at a  $P(\xi=x_i)=p(i)$, $1\le i\le M$, k\'eplet
adja meg. Legyen $u(x_i)$, $x_i\in X$, az  $X$ halmaznak
egy az $Y=\{1,\dots,d\}$ halmaz seg\'{\i}ts\'eg\'evel
defini\'alt prefix, vagy \'al\-ta\-l\'a\-no\-sab\-ban,
egy\'ertelm\H{u}en dek\'odolhat\'o k\'odja, \'es jel\"olje $n(i)$
az $u(x_i)$ k\'od\-sz\'o sz\'ohossz\'at. Ekkor az $u(\xi)$
v\'eletlen k\'odsz\'o $|u(\xi)|$ hossz\'anak a v\'arhat\'o
\'ert\'eke teljes\'{\i}ti az
$$
E|u(\xi)|=\summ_{i=1}^M p(i)n(i)\ge \frac{H(\xi)}{\log d}
$$
egyenl\H{o}tlens\'eget. Megford\'{\i}tva, l\'etezik az
$X$ halmaznak olyan prefix k\'odja, amelyre
$$
E|u(\xi)|=\summ_{i=1}^M p(i)n(i)\le \frac{H(\xi)}{\log d}+1.
$$
}

\medskip\noindent
{\it Bizony\'{\i}t\'as.}\/ Legyen $u(x_i)$, $1\le i\le M$, az $X$
halmaznak az $Y=\{1,\dots,d\}$ ABC seg\'{\i}ts\'eg\'evel defini\'alt
egy\'ertelm\H{u}en dek\'odolhat\'o k\'odja, \'es legyen $n(i)$ az
$u(x_i)$ k\'odsz\'o k\'odhossza. Tudjuk, hogy ekkor
$\summ_{i=1}^M d^{-n(i)}\le1$. Alkalmazzuk az el\H{o}z\H{o}
lemm\'aban bizony\'{\i}tott egyenl\H{o}tlens\'eget $a_i=p(i)$
\'es $b_i=d^{-n(i)}$, $1\le i\le M$, v\'alaszt\'assal. Ekkor
$a=\summ_{i=1}^M a_i=1$, \'es $b=\summ_{i=1}^M b_i\le1$, ahonnan
$$
\sum_{i=1}^M p(i)\log (p(i)d^{n(i)})
=\sum_{i=1}^M a_i\log\frac{a_i}{b_i}\ge a\log\frac ab\ge0.
$$
Teh\'at $\log d\cdot\summ_{i=1}^M n(i)p(i)\ge
-\summ_{i=1}^M p(i)\log p(i)$, azaz
$\log d\cdot Eu|(\xi)|\ge H(\xi)$, \'es ezt kellett be\-l\'at\-ni.

L\'attuk, hogy a t\'etel m\'asodik fel\'enek igazol\'asa
\'erdek\'eben olyan $n(i)$, $1\le i\le M$, pozit\'{\i}v eg\'esz 
sz\'amokat  kell tal\'alnunk, amelyekre 
$\summ_{i=1}^M d^{-n(i)}\le 1$, \'es az
$E|u(\xi)|=\summ_{i=1}^M p(i) n(i)$ v\'arhat\'o \'ert\'ek 
vi\-szony\-lag kicsi. Term\'eszetes olyan $n(i)$ sz\'amokat 
v\'alasztani, amelyekre az $E|u(\xi)|$ v\'arhat\'o \'ert\'ekre 
adott als\'o becsl\'es bizony\'{\i}t\'as\'aban felhaszn\'alt 
$I$-divergencia tipus\'u becsl\'est megfogalmaz\'o lemm\'aban 
sze\-rep\-l\H{o} egyenl\H{o}tlens\'eg majdnem egyenl\H{o}s\'eggel 
teljes\"ul. Ez\'ert v\'alasszunk olyan $n(i)$ eg\'esz sz\'amokat, 
amelyekre $d^{-n(i)}\le p(i)$, \'es a
$d^{-n(i)}$ sz\'am olyan k\"ozel van a $p(i)$ sz\'amhoz, amennyire
ez a felt\'etel megengedi. Ennek alapj\'an a k\"ovetkez\H{o}
v\'alaszt\'ast tessz\"uk. Legyen minden $1\le i\le M$ indexre 
$n(i)$ az az eg\'esz sz\'am, amelyre 
$\frac{p(i)}d\le d^{-n(i)}\le p(i)$. Ekkor
$\summ_{i=1}^M d^{-n(i)}\le\summ_{i=1}^Mp(i)=1$, azaz l\'etezik
a k\'{\i}v\'ant hossz\'us\'ag\'u k\'odszavakkal rendelkez\H{o}
prefix k\'od. M\'asr\'eszt $n(i)\le-\frac{\log p(i)}{\log d}+1$,
\'es ez\'ert $E|u(\xi)|=\summ_{i=1}^M p(i) n(i)
\le -\summ_{i=1}^M \frac{p(i)\log p(i)}{\log d}+\summ_{i=1}^Mp(i)
=\frac{H(\xi)}{\log d}+1$, teh\'at e prefix k\'od hossz\'anak
a v\'arhat\'o \'ert\'eke teljes\'{\i}ti a k\'{\i}v\'ant
egyenl\H{o}tlens\'eget.

\medskip
Az egy\'ertelm\H{u}en dek\'odolhat\'o \'es
prefix k\'odok hossz\'anak v\'arhat\'o \'er\-t\'e\-k\'e\-r\H{o}l
sz\'ol\'o t\'etel fels\H{o} becsl\'es\'enek bizony\'{\i}t\'as\'aban
defini\'alt prefix k\'od hossza k\"ozel van az optimumhoz, de nem
felt\'etlen\"ul egyenl\H{o} vele. Ugyanakkor ismert az optim\'alis,
\'ugy\-ne\-ve\-zett Huffman k\'od konstrukci\'oja is. (L\'asd 
Robert Ash: Information Theory, Lemma 2.6.2), amely el\'egg\'e
bonyolult.  Ez\'ert e k\'od tulajdons\'agai nehezen 
vizs\-g\'al\-ha\-t\'o\-ak, \'es jelent\H{o}s\'ege 
korl\'atozott. Emiatt mi a Huffman k\'odot nem t\'argyaljuk.

Hasonl\'o jelens\'eggel tal\'alkoztunk, amikor f\"uggetlen
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok $n$ hossz\'u\-s\'a\-g\'u
sorozataib\'ol \'all\'o viszonylag kis elem\-sz\'a\-m\'u majdnem 1 
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-g\H{u}, alkalmasan defi\-ni\-\'alt 
halmazok elem\-sz\'a\-m\'at becs\"ult\"uk.  Ott sem az optim\'alis  
halmaz elemsz\'am\'at becs\"ult\"uk. Ez a 
leg\-va\-l\'o\-sz\'{\i}\-n\H{u}bb sorozatok alkalmas elemsz\'am\'u 
halmaza lett volna. Ehelyett egy olyan csak aszimptotikusan 
optim\'alis halmazt tekintett\"unk, amelynek elem\-sz\'a\-m\'at a 
nagy sz\'amok t\"or\-v\'e\-nye seg\'{\i}ts\'eg\'evel j\'ol tudtuk 
becs\"ulni.



\bye


\medskip
Legyen adva egy $\xi$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o, \'es
legyen $\xi_1,\dots,\xi_n$ a $\xi$ val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'oval azonos eloszl\'as\'u, nem felt\'etlen\"ul
f\"uggetlen val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok sorozata, \'es
keress\"uk e sorozatnak egy viszonylag r\"ovid,  egy $d$ elem\H{u}
ABC seg\'{\i}ts\'eg\'evel defini\'alt, egy\'ertelm\H{u}en
dek\'odolhat\'o k\'odol\'as\'at. Ha egy $n$ hossz\'us\'ag\'u
$\xi_1,\dots,\xi_n$ sorozatot k\'o\-do\-lunk, \'es a v\'eletlen
hossz\'us\'ag\'u k\'od hossz\'anak v\'arhat\'o \'ert\'eke $L(n)$,
akkor nevezz\"uk az $\frac{L(n)}n$ t\"ortet a k\'odszavak
\'atlaghossz\'anak. Az el\H{o}z\H{o} t\'etel al\'abbi
k\"ovetkezm\'eny\'eben megmutatom, hogy minden $\e>0$ sz\'amra
l\'etezik olyan $n_0=n_0(\e)$ k\"usz\"obindex, hogy minden
$n\ge n_0$ hossz\'us\'ag\'u sorozatra ez az \'atlaghossz
kisebb\'e tehet\H{o}, mint $\frac{H(\xi)}{\log d}+\e$. Tov\'abb\'a,
ha a $\xi_1,\dots,\xi_n$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok
f\"uggetlenek, akkor ez az eredm\'eny nem jav\'{\i}that\'o.

\medskip\noindent
{\bf K\"ovetkezm\'eny.} {\it Legyen $\xi$ egy v\'eges sok
\'ert\'eket felvev\H{o} val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o,
\'es legyen $\xi_1,\dots,\xi_n$ a $\xi$ val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'oval azonos eloszl\'as\'u, nem felt\'etlen\"ul
f\"uggetlen va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi v\'altoz\'ok sorozata.
R\"ogz\'{\i}ts\"unk egy $\e>0$ sz\'amot. L\'etezik olyan
$n_0=n_0(\e)$ k\"usz\"obindex, hogy $n\ge n_0$ eset\'en a
$\xi_1,\dots,\xi_n$ sorozatnak l\'etezik olyan egy\'ertelm\H{u}en
dek\'odolhat\'o, az $Y=\{1,\dots,d\}$ $d$ elem\H{u} ABC
seg\'{\i}ts\'eg\'evel defini\'alt k\'odja, amely k\'od hossz\'anak
$L_n$ v\'arhat\'o \'ert\'eke teljes\'{\i}ti az
$\frac {L_n}n\le\frac{H(\xi)}{\log d}+\e$ egyenl\H{o}tlens\'eget. Ha
a $\xi_1$,\dots, $\xi_n$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok
f\"uggetlenek, akkor az $\frac {L_n}n\ge\frac{H(\xi)}{\log d}$
egyenl\H{o}tlens\'eg is teljes\"ul minden egy\'ertelm\H{u}en
dek\'odolhat\'o k\'odra.}

\medskip\noindent
{\it Bizony\'{\i}t\'as.}\/ Egy kiss\'e er\H{o}sebb \'all\'{\i}t\'ast
bizony\'{\i}tok. Olyan a {\it K\"ovetkezm\'eny} becsl\'es\'et
teljes\'{\i}t\H{o}, egy\'ertelm\H{u}en dek\'odolhat\'o k\'odot adok
meg, amelynek megval\'os\'{\i}t\'as\'ahoz csak olyan sorozatokkal
kell dolgozni, amelyek hossza korl\'atozhat\'o egy a
$\xi_1,\dots,\xi_n$ sorozat $n$ hossz\'at\'ol nem f\"ugg\H{o}
sz\'ammal. Az ilyen k\'odok az\'ert \'erdekesek a gyakorlatban,
mert v\'egrehajt\'asukhoz csak v\'eges mem\'oria sz\"uks\'eges.

V\'alasszunk egy r\"ogz\'{\i}tett $n_0\ge\frac2\e$ eg\'esz sz\'amot,
\'{\i}rjuk az $n$ sz\'amot $n=kn_0+l$, $0\le l<n_0$, alakban, \'es
tekints\"uk az $\eta_j=(\xi_{(j-1)n_0+1},\xi_{(j-1)n_0+2},\dots,
\xi_{jn_0})$, $1\le j\le k$, valamint az
$\eta_{k+1}=(\xi_{kn_0+1},\dots,\xi_{kn_0+l})$ vektorokat.
Az entr\'opi\'aval \'es felt\'eteles entr\'opi\'aval
kap\-cso\-la\-tos fontos egyen\-l\H{o}t\-len\-s\'e\-gek\-r\H{o}l
sz\'ol\'o t\'etel b) pontja alapj\'an
$H(\eta_j)\le H(\xi_{(j-1)n_0+1})+H(\xi_{(j-1)n_0+2})+\dots+
H(\xi_{jn_0}))=n_0H(\xi)$, ha $1\le j\le k$, \'es hasonl\'oan
l\'athat\'o, hogy $H(\eta_{k+1})\le l H(\xi)$. Ez\'ert az
el\H{o}z\H{o} t\'etel alapj\'an az $\eta_j$ vektornak minden
$1\le j\le k$ indexre meg lehet adni egy az $Y=\{1,\dots,d\}$
ABC seg\'{\i}ts\'eg\'evel defini\'alt prefix k\'odj\'at \'ugy,
hogy e k\'od hossz\'anak a v\'arhat\'o \'ert\'eke kisebb legyen,
mint $\frac{n_0H(\xi)}{\log d}+1$. Hasonl\'oan, az $\eta_{k+1}$
vektornak is l\'etezik egy olyan ezen ABC seg\'{\i}ts\'eg\'evel
defini\'alt prefix k\'odja, amely k\'od hossz\'anak a v\'arhat\'o
\'ert\'eke kisebb, mint $\frac{lH(\xi)}{\log d}+1$. Egym\'as
ut\'an felsorolva az $\eta_1,\dots,\eta_{k+1}$ vektorok ilyen
hossz\'us\'ag\'u prefix k\'odjait, a $\xi_1,\dots,\xi_n$ sorozat
egy olyan  egy\'ertelm\H{u}en dek\'odolhat\'o k\'odj\'at kapjuk,
amely k\'od hossz\'anak a v\'arhat\'o \'ert\'eke kisebb, mint
$\frac{nH(\xi)}{\log d}+k+1\le n(\frac{H(\xi)}{\log d}+\e)$,
ha $n\ge n_0$, azaz ezen k\'od hossz\'anak a v\'arhat\'o
\'ert\'eke teljes\'{\i}ti a k\'{\i}v\'ant egyenl\H{o}tlens\'eget.
(Az utols\'o becsl\'esben kihaszn\'altuk, hogy
$k+1\le 2k\le \frac{2n}{n_0}\le\e n$.)

Ha $\xi_1,\dots,\xi_n$ f\"uggetlen val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'ok, akkor
$H(\xi_1,\dots,\xi_n)=H(\xi_1)+\cdots+H(\xi_n)=nH(\xi)$.
Ez\'ert az el\H{o}z\H{o} t\'etel eredm\'enye alapj\'an e sorozat
tetsz\H{o}leges az $Y=\{1,\dots,d\}$ ABC seg\'{\i}ts\'eg\'evel
defini\'alt egy\'ertelm\H{u}en dek\'odolhat\'o k\'odj\'ara igaz,
hogy hossz\'anak v\'arhat\'o \'ert\'eke nagyobb, vagy egyenl\H{o},
mint $\frac{H(\xi_1,\dots,\xi_n)}{\log d}=
n\frac{H(\xi)}{\log d}$, \'es ezt kellett bel\'atni.

\medskip\noindent
{\it Megjegyz\'es.}\/ A fenti k\"ovetkezm\'eny, illetve annak
indokl\'asa  --- n\'emileg pongyol\'an fogalmazva --- azt 
sugallja. hogy $\frac{H(\xi_1,\dots,\xi_n)}n$ inform\'aci\'o 
sz\"uks\'eges egy $\xi_1,\dots,\xi_n$ sorozat egyes tagjainak
a meg\-is\-me\-r\'e\-s\'e\-hez. K\'es\H{o}bb defin\'alni fogom 
az entr\'opia fogalm\'at \'al\-ta\-l\'a\-nos v\'eletlen sorozatok 
eset\'eben is, illetve t\'argyalni fogok olyan probl\'em\'akat, 
amelyek vizs\-g\'a\-la\-ta ig\'enyli e fogalom bevezet\'es\'et. Az 
ott bizony\'{\i}tott eredm\'enyek \"osszhangban vannak az e
megjegyz\'esben csak k\"orulbel\"ul megfogalmazott
\'all\'{\i}t\'assal.



