\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\VV{\tilde V}
\define\vv{\tilde v}
\define\eeta{\tilde\eta}
\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 3. Csatorna k\'odol\'as \'es dek\'odol\'as.

E fejezet f\H{o} t\'em\'aja az a k\'erd\'es, hogy hogyan lehet
egy a jeleket esetleg hib\'aval k\"ozvet\'{\i}t\H{o} csatorn\'an
kereszt\"ul viszonylag biztosan \'es gyorsan \"uzeneteket
\'atadni. K\'es\H{o}bb azt a k\'erd\'est is t\'argyalom,
hogy az ebben \'es az el\H{o}z\H{o} fejezetekben bizony\'{\i}tott
ered\-m\'e\-nyek seg\'{\i}ts\'eg\'evel hogyan lehet egy
h\'{\i}rforr\'as k\"ozvet\'{\i}t\'es\'et egy csatorn\'an
kereszt\"ul j\'ol to\-v\'ab\-b\'{\i}\-ta\-ni.

Egy \"uzenetnek egy (h\'{\i}rk\"ozl\'esi) csatorna
seg\'{\i}ts\'eg\'evel v\'egrehajtott tov\'abbad\'asa azt
jelenti szem\-l\'e\-le\-te\-sen, hogy a csatorna bemeneti
v\'eg\'en leadnak egy jelet, \'es ennek ha\-t\'a\-s\'a\-ra
valamilyen m\'asik jel jelenik meg a csatorna m\'asik,
kimeneti v\'eg\'en. A kimeneti  jel \'ert\'eke f\"ugghet a
v\'eletlent\H{o}l, \'es az, hogy a kimeneti oldalon milyen
val\'osz\'{\i}n\H{u}s\'eggel milyen jel jelenik meg, att\'ol
f\"ugg, hogy mi volt a bemeneti jel. Egy felhaszn\'al\'o, aki
a kimeneti jelet megismeri, megpr\'ob\'al ennek alapj\'an
visszak\"ovetkeztetni a leadott bemeneti jelre. Olyan
elj\'ar\'ast akarunk kidolgozni a csatorna tulajdons\'againak
az ismeret\'eben, amely lehet\H{o}v\'e teszi, hogy a
felhaszn\'al\'o viszonylag nagy val\'osz\'{\i}n\H{u}s\'eggel
helyesen k\"ovetkeztessen a leadott bemeneti jelre.
Fogalmazzuk meg ezt a v\'azlatosan le\'{\i}rt probl\'em\'at
pontosabban. Ennek \'erdek\'eben bevezetem el\H{o}sz\"or a
(h\'{\i}rk\"ozl\'esi) csatorna fogalm\'at.

\medskip\noindent
{\bf (H\'{\i}rk\"ozl\'esi) csatorna \'es a csatorna \'altal
\"osszekapcsolt val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok
definici\'oja.} {\it Legyen adva k\'et $V=\{v_1,v_2,\dots\}$
\'es $\tilde V=\{\vv_1,\vv_2,\dots\}$ v\'eges vagy
meg\-sz\'am\-l\'al\-ha\-t\'o\-an v\'egtelen halmaz. Egy
$p(\vv_j|v_i)$, $v_i\in V$, $\vv_j\in\VV$
\'atmenetval\'osz\'{\i}n\H{u}s\'eg f\"uggv\'enyt a $V$ \'es $\VV$
halmaz k\"oz\"otti csatorn\'anak nevez\"unk. Az, hogy a
$p(\vv_j|v_i)$, $v_i\in V$, $\vv_j\in\VV$ f\"uggv\'eny
\'atmenetval\'osz\'{\i}n\H{u}s\'eg f\"uggv\'eny azt jelenti, hogy
$p(\vv_j|v_i)\ge0$ minden $v_i\in V$ \'es $\vv_j\in\VV$ p\'arra,
\'es $\summ_{\vv_j\in\VV} p(\vv_j|v_i)=1$ minden $v_i\in V$
elemre. A $V$ halmazt a csatorna bemeneti, a $\VV$ halmazt a
csatorna kimeneti oldal\'anak fogjuk h\'{\i}vni,
a $v_i\in V$ pontokat bemeneti, a $\vv_j\in\VV$ pontokat pedig
kimeneti jeleknek fogjuk nevezni. Azt mondjuk hogy k\'et $\eta$
\'es $\tilde\eta$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o
\"ossze van kapcsolva a $p(\vv_j|v_i)$, $v_i\in V$, $\vv_j\in\VV$,
csatorn\'aval ha $\eta(\oo)\in V$, $\eeta(\oo)\in\VV$ minden $\oo$
elemi esem\'enyre, \'es $P(\eeta=\vv_j|\eta=v_i)=p(\vv_j|v_i)$
minden $v_i\in V$ \'es $\vv_j\in\VV$ elemp\'arra.}

\medskip
Ha egy csatorn\'an leadunk valamely $v_i\in V$ bemeneti jelet, akkor
a felhaszn\'al\'o $p(\vv_j|v_i)$ val\'osz\'{\i}n\H{u}s\'eggel kapja
a $\vv_j$ kimeneti jelet. Ezen kimeneti jel seg\'{\i}ts\'eg\'evel
pr\'ob\'alja megtal\'alni a bemeneti jel \'ert\'ek\'et.
Ennek \'erdek\'eben term\'eszetes a k\"ovetkez\H{o} tipus\'u
elj\'ar\'as alkalmaz\'asa. A bemeneti oldalon alkalmas m\'odon
kiv\'alasztunk n\'eh\'any $v_{i_1}\in V$,\dots, $v_{i_N}\in V$
elemet bizonyos $N$ elemsz\'ammal, \'es ezen jelek valamelyik\'et
adjuk le a csatorn\'an. Ezeknek a bemeneti jeleknek a
kiv\'alaszt\'as\'at nevezz\"uk csatorna k\'odol\'asnak. \'Ugy
k\'{\i}v\'anjuk ezt a kiv\'alaszt\'ast v\'egrehajtani, hogy az
egyes kiv\'alasztott elemeket a csatorn\'an leadva, azok nagy
val\'osz\'{\i}n\H{u}s\'eggel k\"ul\"onb\"oz\H{o} halmazokba
essenek. Ez a k\"ovetkez\H{o}t jelenti. Ha egy $v_i\in V$ jelet
leadunk a csatorn\'an, akkor jel\"olje az $\eeta(v_i)$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o a kimen\H{o} jel
\'ert\'ek\'et. Olyan $v_{i_1}\in V$,\dots, $v_{i_N}\in V$ elemeket
akarunk a k\'odol\'asban v\'alasztani, amelyekhez tal\'alhat\'oak
olyan diszjunt $B_1\subset \VV$,\dots, $B_N\subset\VV$ diszjunkt
halmazok, amelyekre a $P(\eeta(v_{i_k})\in B_k)$
val\'osz\'{\i}n\H{u}s\'egek minden $1\le k\le N$ indexre viszonylag
nagyok. Ha a kimeneti oldalon egy olyan $\vv_j$ jel jelent meg,
amelyre $\vv_j\in B_k$, akkor tekintse a felhaszn\'al\'o a
$v_{i_k}$ jelet a  bemeneti jelnek. A $B_k$, $1\le k\le N$,
halmazok kiv\'alaszt\'as\'at \'es a $B_k\to v_{i_k}$
lek\'epez\'es megad\'as\'at csatorna dek\'ododol\'asnak
nevezz\"uk. E definici\'ot \'ugy adtam meg,
hogy amennyiben $\vv_j\notin\bigcupp_{i=k}^N B_k$ akkor az
itt ismertetett elj\'ar\'as szerint nem dek\'odoljuk a $\vv_j$
kimenetet. Az azonban, hogy ezt az elvet k\"ovetj\"uk-e, vagy olyan
elj\'ar\'ast adunk, amelyikben mindig tudunk dek\'odolni csak apr\'o
\'{\i}zl\'esbeli k\'erd\'es. A $B_k$ halmazok kiterjeszt\'es\'evel
ugyanis azt is el\'erhetj\"uk, hogy ezek a halmazok ne csak
diszjunktak legyenek, hanem egyben a $\VV$ halmaz egy partici\'oj\'at
is szolg\'altass\'ak. Ilyen v\'alaszt\'assal minden kimenetet tudunk
dek\'odolni, \'es az elj\'ar\'asban a j\'o dek\'odol\'as
val\'osz\'{\i}n\H{u}s\'ege a $B_k$ halmazok kiterjeszt\'ese
\'altal nem cs\"okkent. C\'elunk viszonylag sok k\'odsz\'o
kiv\'alaszt\'asa \'ugy, hogy a dek\'odol\'as nagy
val\'osz\'{\i}n\H{u}s\'eggel j\'o legyen. A k\'es\H{o}bbi
eredm\'enyek pontos megfogalmaz\'as\'anak az \'erdek\'eben
vezess\"uk be a k\"ovetkez\H{o} definici\'ot.

\medskip\noindent
{\bf Egy csatorna \'altal $\lambda$ megk\"ul\"onb\"oztethet\H{o}
elemekb\H{o}l \'all\'o halmaz definici\'oja.} {\it Legyen adva
k\'et $V=\{v_1,v_2,\dots\}$ \'es $\tilde V=\{\vv_1,\vv_2,\dots\}$
v\'eges vagy megsz\'aml\'alhat\'oan v\'egtelen halmaz, \'es
k\"ozt\"uk egy $p(\vv_j|v_i)$, $v_i\in V$, $\vv_j\in\VV$ csatorna.
Ha egy $v_{i_1}\in V$,\dots, $v_{i_N}\in V$ sorozat elemeihez
l\'eteznek olyan $B_1\subset\VV$,\dots $B_N\subset\VV$
halmazok, amelyekre
$$
P(B_k|v_{i_k})=\summ_{j\in B_k}p(\vv_j|v_{i_k})\ge1-\lambda \quad
\text{minden $1\le k\le N$ indexre},
$$
 akkor azt mondjuk, hogy az
$A=\{v_{i_1},\dots,v_{i_N}\}$ halmaz elemei $\lambda$
megk\"ul\"onb\"oztethet\H{o}ek.}

\medskip\noindent
{\it Megjegyz\'es.}\/ Az el\H{o}bbi definic\'oban fel\'{\i}rt
egyenl\H{o}tlens\'eget \'ugy is megfogalmazhatjuk, hogy
amennyiben $\eta$ \'es $\eeta$ k\'et a csatorn\'aval
\"osszekapcsolt val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o, akkor
$$
P(\eeta\in B_k|\eta=v_{i_k})\ge 1-\lambda \quad
\text{minden $1\le k\le N$ indexre}.
$$
A k\'es\H{o}bbiekben t\"obbsz\"or ezt a jellemz\'es\'et fogjuk
haszn\'alni az egy csatorna \'altal $\lambda$
megk\"ul\"onb\"oztethet\H{o} elemekb\H{o}l \'all\'o halmazoknak.

\medskip
Egy az el\H{o}bb le\'{\i}rt m\'odon defini\'alt j\'o, azaz kis
hib\'aj\'u csatorna k\'odol\'as, dek\'odol\'as definici\'oja egy
$\lambda$ megk\"ul\"onb\"oztethet\H{o} elemekb\H{o}l \'all\'o
$v_{i_1}\in V$,\dots, $v_{i_N}\in V$ sorozat megad\'as\'at
jelenti kis $\lambda>0$ param\'eterrel az e sorozatokhoz tartoz\'o
$B_1\subset\VV$,\dots, $B_N\subset\VV$ halmazokkal egy\"utt.
A minket \'erdekl\H{o} feladatokban val\'oj\'aban nem egy jelet,
hanem egy jelsorozat elemeit adjuk le egym\'as ut\'an a csatorn\'an,
\'es c\'elunk ennek a jelsorozatnak a min\'el pontosabb
azonos\'{\i}t\'asa. Minket az az eset \'erdekel els\H{o}sorban,
amikor a jelsorozat egyes jelei egym\'ast\'ol f\"uggetlen\"ul,
\'es ugyanolyan t\"orv\'enyszer\H{u}s\'egek szerint mennek \'at
a csatorn\'an. E fejezetben csak ezt az esetet fogom t\'argyalni.
A probl\'ema pontos megfogalmaz\'asa \'erdek\'eben bevezetem az
eml\'ekezet n\'elk\"uli csatorna fogalm\'at.

\medskip\noindent
{\bf Eml\'ekezet n\'elk\"uli csatorna definici\'oja.}  {\it Legyen
adva k\'et $V=\{v_1,v_2,\dots\}$ \'es
$\tilde V=\{\vv_1,\vv_2,\dots\}$ v\'eges vagy megsz\'aml\'alhat\'o
halmaz, \'es k\"oz\"ott\"uk egy $p(\vv_j|v_i)$, $v_i\in V$,
$\vv_j\in\VV$, \'atmenetval\'osz\'{\i}n\H{u}s\'egekkel defini\'alt
csatorna. Az e csatorna \'altal defini\'alt $n$~hossz\'us\'ag\'u
eml\'ekezet n\'elk\"uli csatorna olyan csatorna, amelynek  bemeneti
jelei a $V^n$, kimeneti jelei a $\VV^n$ halmaz elemei, azaz $n$
elem\H{u} $v_{i_k}$ illetve $\vv_{j_k}$, $1\le k\le n$,
elemekb\H{o}l \'all\'o sorozatok, \'atmenetval\'oszin\H{u}s\'ege
pedig $p((\vv_{j_1},\dots,\vv_{j_n})|(v_{i_1},\dots,v_{j_n}))
=\prodd_{k=1}^n p(\vv_{j_k}|v_{i_k})$ tetsz\H{o}leges
$v=(v_{i_1},\dots,v_{i_n})\in V^n$, \'es
$\vv=(\vv_{j_1},\dots,\vv_{j_n})\in \VV^n$ sorozatokra.}

\medskip
Az eml\'ekezet n\'elk\"uli csatorna term\'eszetes
megfelel\H{o}je a f\"uggetlen, egyforma el\-osz\-l\'a\-s\'u
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok sorozatainak. Azt a
k\'erd\'est fogjuk vizsg\'alni, hogy egy $n$ hossz\'us\'ag\'u
eml\'ekezet n\'elk\"uli csatorna bemeneti
oldal\'an aszimptotikusan h\'any a csatorna \'altal $\lambda$
megk\"ul\"onb\"oztethet\H{o} elemet tartalmaz\'o halmazt lehet
kiv\'alasztani nagy $n$ \'es r\"ogz\'{\i}tett $0<\lambda<1$
sz\'am eset\'en. Be fogjuk l\'atni, hogy nagyon \'altal\'anos
felt\'etelek mellett ez a sz\'am $2^{Cn(1+o(1))}$, ahol a $C$
sz\'am, amelyet csatorna kapacit\'asnak fogunk h\'{\i}vni, a
csatorna tulajdons\'agait\'ol f\"ugg. Ahhoz, hogy az eredm\'enyt
pontosan megfogalmazzam defini\'alni kell a csatorna
kapacit\'ast. Ennek \'erdek\'eben bevezetem el\H{o}sz\"or
k\'et val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o k\"olcs\"on\"os
inform\'aci\'oj\'anak a fogalm\'at.

\medskip\noindent
{\bf A k\"olcs\"on\"os inform\'aci\'o fogalma.} {\it Legyen $\eta$
\'es $\eeta$ k\'et \'ert\'ekeiket egy $V=\{v_1,v_2,\dots\}$ illetve
$\tilde V=\{\vv_1,\vv_2,\dots\}$ v\'eges vagy megsz\'aml\'alhat\'o
halmazon felvev\H{o} val\'osz\'{\i}n\H{u}s\'egi v\'al\-to\-z\'o,
\'es jel\"olje $r(v_i,\vv_j)=P(\eta=v_i,\eeta=v_j)$, $v_i\in V$,
$\vv_j\in\VV$, az egy\"uttes eloszl\'asukat. Vezess\"uk be a
$p(v_i)=P(\eta=v_i)=\summ_{\vv_j\VV} r(v_i,\vv_j)$ \'es
$q(\vv_j)=P(\eeta=\vv_j)=\summ_{v_i\in V} r(v_i,v_j)$, $v_i\in V$,
$\vv_j\in\VV$, mennyis\'egeket is. Ezzel a jel\"ol\'essel az $\eta$
\'es $\eeta$ val\'osz\'{\i}n\H{u}s\'egi v\'al\-to\-z\'ok
k\"olcs\"on\"os inform\'aci\'oja az
$$
I(\eta\wedge\eeta)=\sum_{v_i\in V,\vv_j\in\VV}
r(v_i,\vv_j) \log\( \frac{r(v_i,\vv_j)}{p(v_i)q(\vv_j)}\)
$$
kifejez\'essel egyenl\H{o}.}

\medskip\noindent
{\bf T\'etel a k\"olcs\"on\"os inform\'aci\'o
viselked\'es\'er\H{o}l.} {\it \'Erv\'enyes az
$I(\eta\wedge\eeta)\ge0$ egyen\-l\H{o}t\-len\-s\'eg, \'es
egyenl\H{o}s\'eg akkor \'es csak akkor \'all fenn ebben a
formul\'aban, ha $\eta$ \'es $\eeta$ f\"uggetlenek.}

\medskip\noindent
{\it Bizony\'{\i}t\'as.}\/ Alkalmazzuk az
$r(v_i,\vv_j)=P(\eta=v_i,\eeta=\vv_j)$, \'es
$p(v_i)=\summ_{\vv_j\in\VV} r(v_i,\vv_j)$,
$q(\vv_j)=\summ_{v_i\in V} r(v_i,\vv_j)$ $v_i\in V$, $\vv_j\in\VV$,
jel\"ol\'eseket. Azt kapjuk, felhaszn\'alva a $g(x)=x\log x$
f\"uggv\'eny szigor\'u konvexit\'as\'at, hogy
$$
\align
I(\eta\wedge\eeta)&=\sum_{v_i\in V,\vv_j\in\VV}
r(v_i,\vv_j) \log\( \frac{r(v_i,\vv_j)}{p(v_i)q(\vv_j)}\)
=\sum_{v_i\in V,\vv_j\in\VV} p(v_i)q(\vv_j)
g\(\frac{r(v_i,\vv_j)}{p(v_i)q(\vv_j)}\) \\
&\ge g\(\sum_{v_i\in V,\vv_j\in\VV} r(v_i,\vv_j)\)=g(1)=0,
\endalign
$$
Ebben a sz\'amol\'asban a $g(x)$ f\"uggv\'eny konvexit\'as\'at
alkalmaztuk a $p(v_i)q(\vv_j)$ s\'uly\-f\"ugg\-v\'ennyel. Vegy\"uk
\'eszre, hogy $\summ_{v_i\in V,\vv_j\in\VV}p(v_i)q(\vv_j)=1$, \'es
$p(v_i)q(\vv_j)\ge0$ minden $i$ \'es $j$ indexre.
Tov\'abb\'a felhaszn\'altuk azt is, hogy mivel a $g(x)$, $x\ge0$,
f\"uggv\'eny alulr\'ol korl\'atos, ez\'ert jogunk van a
bizony\'{\i}t\'asban haszn\'alt konvexit\'asi tulajdons\'agot akkor
is haszn\'alni, ha v\'egtelen sok oszt\'opontot tekint\"unk.
Egyenl\H{o}s\'eg a $g(x)$ f\"uggv\'eny szigor\'u konvexit\'asa miatt
csak akkor teljes\"ul, ha
$\frac{r(v_i,\vv_j)}{p(v_i)q(\vv_j)}=\alpha$ egy az $i$ \'es
$j$ indext\H{o}l nem f\"ugg\H{o} $\alpha$ sz\'ammal minden
$i$ \'es $j$ indexre. (Ha $p(v_i)q(\vv_j)=0$, akkor $r(v_i,\vv_j)=0$,
\'es ekkor ezt a t\"ortet tetsz\H{o}leges m\'odon defini\'alhatjuk.)
De mivel
$\summ_{v_i,\vv_j} p(v_i)q(\vv_j)=\summ_{v_i,\vv_j}r(v_i,\vv_j)=1$,
ez csak akkor lehets\'eges, hogy $\alpha=1$, azaz az $\eta$ \'es
$\eeta$ val\'osz\'{\i}n\H{u}s\'agi v\'altoz\'ok f\"uggetlenek.

\medskip\noindent
{\it 1. Megjegyz\'es.}\/ Ha az $\eeta$ val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'o entr\'opi\'aja teljes\'{\i}ti a $H(\tilde\eta)<\infty$
felt\'etelt (vagy $H(\eta)<\infty$), akkor az
$\eta$ \'es $\eeta$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok
k\"olcs\"on\"os inform\'aci\'oja egy\-sze\-r\H{u}b\-ben is
kifejezhet\H{o}, \'es az el\H{o}z\H{o} t\'etel \'all\'{\i}t\'asa
k\"ovetkezik az entr\'opia m\'ar bizony\'{\i}tott
tulajdons\'agaib\'ol is. Ekkor
$$
\align
I(\eta\wedge\eeta)&=\sum_{v_i\in V,\vv_j\in\VV}
r(v_i,\vv_j) \log\(\frac{r(v_i,\vv_j)}{p(v_i)q(\vv_j)}\)\\
&=\sum_{v_i\in V,\vv_j\in\VV}r(v_i,\vv_j)
\log\frac{r(v_i,\vv_j)}{q(\vv_j)}
-\sum_{v_i\in V,\vv_j\in\VV}r(v_i,\vv_j) \log p(v_i) \\
&=H(\eeta)-H(\eeta|\eta),
\endalign
$$
ahonnan $(I\eta\wedge\eeta)=H(\eeta)-H(\eeta|\eta)\ge0$, \'es
egyenl\H{o}s\'eg csak akkor \'all fenn, ha $\eta$ \'es
$\eeta$ f\"uggetlen val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'ok. Ha a $H(\eta)<\infty$ felt\'etel is teljes\"ul,
akkor $I(\eta\wedge\eeta)=H(\eta)+H(\eeta)-H(\eta,\eeta)
=H(\eta)-H(\eta|\eeta)=H(\eeta)-H(\eeta|\eta)$.

\medskip\noindent
{\it 2. Megjegyz\'es.}\/ \'Erdemes felid\'ezni az els\H{o}
fejezetben t\'argyalt eredm\'enyeket \'es t\'argyalni azok
kapcsolat\'at a k\"olcs\"on\"os inform\'aci\'o fogalm\'aval.
El\H{o}sz\"or azt a p\'eld\'at t\'argyaltuk, hogy ha egy
m\'erk\H{o}z\'essorozat $\xi_1,\dots,\xi_n$ eredm\'enyei
egym\'ast\'ol f\"uggetlen \'es egy $\xi$
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi v\'altoz\'oval azonos
eloszl\'as\'u val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok, akkor
k\"or\"ulbel\"ul $2^{nH(\xi)}$ szelv\'enyt kell
kit\"olteni annak \'erdek\'eben, hogy majdnem biztosan legyen
telital\'alatunk. Ha ismerj\"uk egy m\'asik m\'erk\H{o}z\'essorozat
$\eta_1,\dots,\eta_n$ eredm\'enyeit, \'es a
$(\xi_1,\eta_1),\dots,(\xi_n,\eta_n)$ eredm\'enyp\'arok
egym\'ast\'ol f\"uggetlen, \'es egy $(\xi,\eta)$ v\'eletlen
vektorral azonos eloszl\'as\'u val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'ok, akkor az $\eta_1,\dots,\eta_n$ m\'erk\H{o}z\'essorozat
eredm\'enyeinek ismeret\'eben k\"or\"ulbel\"ul $2^{n H(\xi|\eta)}$
szelv\'enyt kell kit\"olten\"unk a majdnem biztos telital\'alat
el\'er\'es\'ehez, teh\'at k\"or\"ulbel\"ul
$2^{-n(H(\xi)-H(\xi|\eta))}=2^{-nI(\xi\wedge\eta)}$-szoros\'at
annak amennyi szelv\'enyt akkor kell kit\"olten\"unk, ha az
$\eta_1,\dots,\eta_n$ m\'erk\H{o}z\'essorozat eredm\'enyeit nem
ismerj\"uk.

Ezt az eredm\'enyt heurisztikusan \'ugy is interpret\'alhatjuk,
hogy az $\eta_j$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o ismerete
$I(\xi\wedge\eta)$-vel cs\"okkenti a $\xi_j$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o megismer\'es\'ehez
sz\"uk\-s\'e\-ges inform\'aci\'ot.
Az $I(\xi\wedge\eta)=H(\xi)-H(\xi|\eta)=H(\eta)-H(\eta|\xi)$
azonoss\'ag azt jelenti, hogy a k\"olcs\"on\"os inform\'aci\'onak
ebben az interpret\'aci\'oj\'aban a $\xi$ \'es $\eta$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok szerepe felcser\'elhet\H{o}.

\medskip
Bevezetem a csatorna kapacit\'as fogalm\'at.

\medskip\noindent
{\bf A csatorna kapacit\'as fogalma.} {\it Legyen adva k\'et
$V=\{v_1,v_2,\dots\}$ \'es $\tilde V=\{\vv_1,\vv_2,\dots\}$
v\'eges vagy megsz\'aml\'alhat\'o halmaz, \'es k\"oz\"ott\"uk
egy $p(\vv_j|v_i)$, $v_i\in V$, $\vv_j\in\VV$,
\'at\-me\-net\-va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gek\-kel
defini\'alt csatorna. A csatorna kapacit\'as\'at a
$$
C=\sup_{\eta,\eeta} I(\eta\wedge\eeta)
$$
k\'eplet adja meg, ahol a szupr\'emumban az \"osszes a csatorna
\'altal \"osszekapcsolt $(\eta,\eeta)$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o p\'art tekintj\"uk.}

\medskip\noindent
{\it Megjegyz\'es.}\/ L\'attuk, hogy egy csatorna kapacit\'asa
mindig nagyobb vagy egyenl\H{o}, mint nulla. S\H{o}t, jellemezni
lehet azt az esetet is, amikor a csatorna kapacit\'as null\'aval
egyenl\H{o}. Ez akkor k\"ovetkezik be, ha b\'armely k\'et a
csatorn\'aval \"osszekapcsolt $\eta$ \'es $\eeta$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o f\"uggetlen. Nem neh\'ez
bel\'atni, hogy ez akkor \'es csak akkor lehets\'eges, ha a
csatorn\'at meghat\'aroz\'o $p(\vv_j|v_i)$
\'atmenetval\'osz\'{\i}n\H{u}s\'egek nem f\"uggnek a $v_i$
bemeneti jel \'ert\'ek\'et\H{o}l. Ez azt jelenti, hogy
b\'armely bemeneti jel lead\'asa eset\'en ugyanolyan
val\'osz\'{\i}n\H{u}s\'eggel kapjuk b\'armely kimeneti jelet.
Ekkor a kimeneti jel ismerete semmilyen inform\'aci\'ot nem
ny\'ujt arr\'ol, hogy milyen bemeneti jelet adtak le.

\medskip\noindent
E fejezet f\H{o} eredm\'enyei arra adnak becsl\'est, hogy, milyen
nagy, azaz h\'any $\lambda$
meg\-k\"u\-l\"on\-b\"oz\-tet\-he\-t\H{o} elemet tartalmaz\'o
halmazt lehet konstru\'alni  egy $n$ hossz\'us\'ag\'u
eml\'ekezet n\'elk\"uli csatorna bemeneti oldal\'an.
A k\"ovetkez\H{o} eredm\'enyeket fogom bel\'atni.

\medskip\noindent
{\bf Csatorna k\'odol\'asi t\'etel.} {\it Legyen adva
adva k\'et $V=\{v_1,v_2,\dots\}$ \'es
$\tilde V=\{\vv_1,\vv_2,\dots\}$ v\'eges vagy megsz\'aml\'alhat\'o
halmaz, \'es k\"oz\"ott\"uk egy $p(\vv_j|v_i)$, $v_i\in V$,
$\vv_j\in\VV$,
\'at\-me\-net\-va\-l\'o\-sz\'{\i\-}n\H{u}\-s\'e\-gek\-kel
defini\'alt $C<\infty$ csatorna kapacit\'as\'u csatorna.
Tekints\"unk egy ezen csatorna \'altal defini\'alt
$n$~hossz\'us\'ag\'u eml\'ekezet n\'elk\"uli csatorn\'at. Minden
$0<\lambda<1$ \'es $\e>0$ sz\'amhoz l\'etezik olyan
$n_0=n_0(\e,\lambda)$ k\"usz\"obindex \'ugy, hogy amennyiben
$n\ge n_0$, akkor l\'etezik $N\ge 2^{(1-\e)Cn}$
$n$ hossz\'us\'ag\'u $(v^{(k)}_{j_1},\dots,v_{j_n}^{(k)})\in V^n$,
$1\le k\le N$, alak\'u $\lambda$ megk\"ul\"onb\"oztethet\H{o}
sorozatot tartalmaz\'o halmaz ennek az $n$ hossz\'us\'ag\'u
eml\'ekezet n\'elk\"uli csatorn\'anak a bemeneti oldal\'an.}

\medskip
A fenti eredm\'eny megford\'{\i}t\'as\'at, azaz egy $\lambda$
megk\"ul\"onb\"oztethet\H{o} halmaz elem\-sz\'a\-m\'a\-ra adott
fels\H{o} becsl\'est  csak v\'eges \'allapotter\H{u}
csatorn\'akra fogom bizony\'{\i}tani. Egy csatorn\'at v\'eges
\'allapotter\H{u}nek nevezek, ha mind a bemeneti jelek $V$ mind
a kimeneti jelek $\VV$ halmaza v\'eges elemsz\'am\'u.

\medskip\noindent
{\bf A csatorna k\'odol\'asi t\'etel megford\'{\i}t\'asa.}
{\it Legyen adva k\'et $V=\{v_1,\dots,v_m\}$ \'es
$\tilde V=\{\vv_1,\dots,\vv_n\}$ v\'eges halmaz, \'es
k\"oz\"ott\"uk egy $p(\vv_j|v_i)$, $v_i\in V$, $\vv_j\in\VV$,
\'at\-me\-net\-va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gek\-kel
defini\'alt v\'eges \'allapotter\H{u} $C<\infty$ csatorna
kapacit\'as\'u csatorna. Tekints\"unk egy ezen csatorna \'altal
defini\'alt $n$~hossz\'us\'ag\'u eml\'ekezet n\'elk\"uli
csatorn\'at. Legyen $A$ a $V^n$ halmaz egy $\lambda$
megk\"ul\"onb\"oztethet\H{o} sorozatokat tartalmaz\'o
 r\'eszhalmaza valamely $0<\lambda<1$ sz\'ammal. Ekkor
l\'etezik olyan $n_0=n_0(\e,\lambda)$ k\"usz\"obindex, hogy
amennyiben $n\ge n_0$, akkor az $A$ halmaz elemsz\'ama kisebb,
mint $2^{(1+\e)Cn}$. S\H{o}t, igaz a k\"ovetkez\H{o}
\'elesebb becsl\'es. Az adott tulajdons\'ag\'u $A$~halmaz
elemsz\'ama kisebb, mint
$\frac2{1-\lambda}2^{Cn+K\sqrt n/\sqrt{1-\lambda}}$ egy
alkalmas, a csatorna tulajdons\'agait\'ol f\"ugg\H{o} $K$
konstanssal.}

\medskip
Miel\H{o}tt r\'at\'ern\'ek a fenti t\'etelek
bizony\'{\i}t\'as\'ara, heurisztikus magyar\'azatot adok arra,
hogy mi\'ert term\'eszetes ilyen eredm\'enyeket v\'arni.

Ha adva van egy csatorn\'at meghat\'aroz\'o $P(\vv_j|v_i)$,
$v_i\in V$, $\vv_j\in \VV$,
\'at\-me\-net\-va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'eg
f\"ugg\-v\'eny, akkor tekints\"unk egy ehhez az
\'atmenetval\'osz\'{\i}n\H{u}s\'eghez adapt\'alt $\mu$
m\'ert\'eket a $V\times\VV$ halmazon, azaz egy olyan $\mu$
val\'osz\'{\i}n\H{u}s\'egi m\'ert\'eket, amelyre egy $\mu$
eloszl\'as\'u $(\eta,\eeta)$ v\'eletlen vektor teljes\'{\i}ti a
$P(\eeta=\vv_j|\eta_i=v_i)=p(\vv_j|v_i)$ azonoss\'agot minden
$v_i\in V$ \'es $\vv_j\i\VV$ pontra. V\'alasszuk ezt a $\mu$
m\'ert\'eket \'ugy, hogy egy $\mu$ eloszl\'as\'u $(\eta,\eeta)$
p\'arra $I(\eta\wedge\eeta)=C$, vagy legal\'abbis
$I(\eta\wedge\eeta)$ nagyon k\"ozel van a $C$ csatorna
kapacit\'ashoz. Te\-kint\-s\"uk a $\mu$ m\'ert\'ek $\mu^n$
$n$-ik hatv\'any\'at a $V^n\times \VV^n$ szorzatt\'eren,
\'es jel\"olje $\nu_1^{n}$ \'es $\nu_2^n$ a $\mu^n$ m\'ert\'ek
vet\"ulet\'et a $V^n$ illetve $\VV^n$ t\'erre. Pr\'ob\'aljunk a
$\lambda$ megk\"ul\"onb\"oztethet\H{o} $v_1\in V^n$,
$v_2\in V_n$,\dots, sorozatokat a $\nu_1^n$ m\'ert\'ek szerint
tipikus sorozatok k\"oz\"ul kiv\'alasztani, \'es v\'alasszuk a
$v_k$ vektornak megfelel\H{o} $B_k$ halmazt \'ugy, mint a
$\mu^n(\cdot|v_k)$ felt\'eteles m\'ert\'ek sze\-rin\-ti tipikus
sorozatok halmaz\'at, illetve ezen halmaz kis
m\'odos\'{\i}t\'as\'at. Ezt a m\'o\-do\-s\'{\i}\-t\'ast a $B_k$
halmazok diszjunkts\'ag\'anak a biztos\'{\i}t\'asa \'erdek\'eben
tessz\"uk. Annak \'erdek\'eben,
hogy megbecs\"ulj\"uk h\'any ilyen $(v_k,B_k)$ p\'art tudunk
v\'alasztani becs\"ulj\"uk meg a $B_k$ halmazok
$\nu_2^n$ m\'ert\'ek\'et. Az els\H{o} fejezet eredm\'enyei
alapj\'an a $B_k$ halmaz k\"or\"ulbel\"ul $2^{nH(\eeta|\eta)}$
sorozatb\'ol \'all, \'es az egyes sorozatok $\nu_2^n$ m\'ert\'eke
k\"or\"ulbel\"ul $2^{-nH(\eta)}$. Ez\'ert
$\nu_2^n(B_k)\sim 2^{nH(\eeta|\eta)-nH(\eta)}
=2^{-nI(\eta\wedge\eeta)}$, \'es k\"or\"ulbel\"ul
$2^{nI(\eta\wedge\eeta)}$ $B_k$ halmaz fedi le a $\VV^n$ teret.
Viszont, ha enn\'el sokkal kevesebb, nevezetesen csak
$2^{n(1-\e)C}\sim 2^{(1-\e)nI(\eta\wedge\eeta)}$ sz\'am\'u
$B_k$ halmazt v\'alasztunk, akkor b\'{\i}zhatunk abban, hogy
ily m\'odon egy a csatorna k\'odol\'asi t\'etelt
teljes\'{\i}t\H{o} rendszert kapunk. A csatorna k\'odol\'asi
t\'etel bizony\'{\i}t\'asa tekinthet\H{o} \'ugy,
mint a fenti heurisztikus okoskod\'as rendbe t\'etele.

Arra, hogy a fenti m\'odon v\'egzett konstrukci\'o \'eles
eredm\'enyt ad csak kev\'esb\'e meggy\H{o}z\H{o} heurisztikus
\'ervet tudok adni. Mindenesetre jegyezz\"uk meg, hogy b\'ar a
$v_k$ sorozatokat \'es a $B_k$ hozz\'atartoz\'o
halmazokat ebben a konstrukci\'oban egy v\'eletlen
szorzatm\'ert\'ek szerint v\'alasztottuk ki, ez a v\'alaszt\'as
kev\'esb\'e speci\'alis, mint ahogy az els\H{o} pillanatban
l\'atszik. A f\"uggetlens\'egb\H{o}l csak azt haszn\'altuk ki,
hogy a $(v_i,\vv_j)$ p\'arok relat\'{\i}v gyakoris\'aga
el\H{o} van \'{\i}rva, \'es a te\-kin\-tett  $\mu$ m\'ert\'ek
megv\'alaszt\'as\'aval ezt a relat\'{\i}v gyakoris\'agot adtuk
meg. Ha  j\'ol \'{\i}rjuk el\H{o} a kiv\'alasztand\'o $v_k$
vektorokban szerepl\H{o} jelek relat\'{\i}v gyakoris\'ag\'at
akkor ezzel a megszor\'{\i}t\'assal nem cs\"okkentett\"uk
l\'enyegesen a keresett $\lambda$ megk\"ul\"onb\"oztethet\H{o}
sorozatokb\'ol \'all\'o $A$ halmaz nagys\'ag\'at. Ez\'ert sz\'ep
esetekben a v\'eletlen v\'alaszt\'as j\'o eredm\'enyt ad.

A csatorna k\'odol\'asi t\'etel bizony\'{\i}t\'asa k\'et lemm\'an
alapszik. Az els\H{o} az eml\'ekezet n\'elk\"uli csatorna
kapacit\'as\'ar\'ol sz\'ol.

\medskip\noindent
{\bf Lemma az eml\'ekezet n\'elk\"uli csatorna kapacit\'as\'ar\'ol.}
{\it Legyen adva adva k\'et $V=\{v_1,v_2,\dots\}$ \'es
$\tilde V=\{\vv_1,\vv_2,\dots\}$ v\'eges vagy megsz\'aml\'alhat\'oan
v\'egtelen sz\'amoss\'ag\'u halmaz, \'es k\"oz\"ott\"uk egy
$p(\vv_j|v_i)$, $v_i\in V$, $\vv_j\in\VV$,
\'atmenetval\'osz\'{\i}n\H{u}s\'egekkel defini\'alt
$C<\infty$ csatorna kapacit\'as\'u csatorna. Adva  k\'et olyan
$\eta$ \'es $\tilde\eta$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o,
amelyek \"ossze vannak kap\-csol\-va ezzel a csatorn\'aval,
tekints\"uk f\"uggetlen, az $(\eta,\eeta)$ p\'arral azonos
eloszl\'as\'u v\'eletlen vektorok egy
$(\eta_1,\eeta_1)$,\dots, $(\eta_n,\eeta_n)$ sorozat\'at, \'es
defini\'aljuk az $\iota_k=\iota_{\eta_k\wedge\eeta_k}$,
$1\le k\le n$, val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'okat a
k\"ovetkez\H{o} k\'eplet seg\'{\i}ts\'eg\'evel:
$\iota_k=\log\frac{p(\vv_j|v_i)}{q(\vv_j)}$, ha $\eta_k=v_i$ \'es
$\eeta_k=\vv_j$, ahol $q(\vv_j)=P(\eeta=\vv_j)$. Minden $\e>0$
sz\'amhoz megadhat\'oak olyan a csatorn\'aval \"osszekapcsolt
$\eta$ \'es $\tilde\eta$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok,
amelyekre $\frac1n\summ_{k=1}^n\iota_k=\frac1n\summ_{k=1}^n
\iota_{\eta_k\wedge\eeta_k}\Rightarrow I(\eta\wedge\eeta)$,
ahol $\Rightarrow$ sztochasztikus konvergenci\'at jel\"ol, \'es
$I(\eta\wedge\eeta)>(1-\e)C$.

Ha feltessz\"uk, hogy a tekintett csatorna olyan, hogy
b\'armely e csatorn\'aval \"ossze\-kap\-csolt $\eta$ \'es $\eeta$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o p\'arra teljes\"ul a
$H(\eeta)<\infty$  rel\'aci\'o is, akkor az is igaz, hogy egy az
e csatorna \'altal defini\'alt $n$~hossz\'us\'ag\'u eml\'ekezet
n\'elk\"uli csatorna csatorna kapacit\'asa $nC$-vel egyenl\H{o}.}

\medskip\noindent
{\it Megjegyz\'es:}\/ Val\'oj\'aban, e lemm\'anak csak az els\H{o},
%A csatorna k\'odol\'asi t\'etel bizony\'{\i}t\'as\'aban
k\"onnyen bizony\'{\i}that\'o r\'esz\'ere lesz sz\"uks\'eg\"unk.
A m\'asodik r\'eszben megfogalmazott eredm\'eny t\'aryal\'as\'anak
ink\'abb elvi okai vannak.
%a csatorna k\'odol\'asi t\'etel bizony\'{\i}t\'as\'aban
%fogjuk haszn\'alni.
Ezen  eredm\'eny szeml\'eletes tartalma az, hogy egy eml\'ekezet
n\'elk\"uli csatorna kapacit\'as\'at, azaz k\'et ezen
csatorn\'aval \"osszekapcsolt val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'o k\"ol\-cs\"o\-n\"os inform\'aci\'oj\'at nem lehet
blokkos\'{\i}t\'assal n\"ovelni. A leg\-jobb, amit tenni tudunk
az, hogy az egyes koordin\'at\'aknak megfelel\H{o} bemeneti \'es
ki\-me\-ne\-ti jeleket egym\'ast\'ol f\"uggetlen\"ul optim\'alisan
v\'alasztjuk. Ez egy\'ebk\'ent azt is jelenti, hogy nem lehet
a k\'odol\'asi t\'etel becsl\'es\'et trivi\'alis
blokkos\'{\i}t\'assal jav\'{\i}tani. A csatorna k\'odol\'asi
t\'etel \'al\-ta\-lunk megfogalmazott \'es k\'es\H{o}bb
bizony\'{\i}tand\'o alakj\'ab\'ol k\"ovetkezik, hogy ez nem
le\-het\-s\'e\-ges v\'eges \'allapotter\H{u} csatorn\'akban.
A fent megfogalmazott lemma eredm\'enye kiz\'arja az ilyen
tipus\'u jav\'{\i}t\'as lehet\H{o}s\'eg\'et \'altal\'anosabb
csatorn\'ak eset\'eben is. A $H(\eeta)<\infty$
felt\'etel  sze\-re\-pel\-te\-t\'e\-s\'e\-nek e lemma
megfogalmaz\'as\'aban  technikai okai vannak. E felt\'etel
teljes\"ul\'ese  vizsg\'alatainkat egyszer\H{u}bb\'e teszi,
mert ekkor  elker\"ul\"unk bizonyos nem fel\-t\'et\-le\-n\"ul
abszolut  konvergens sorok \'atrendez\'es\'evel kapcsolatos
k\'enyelmetlen sz\'amol\'asokat.

\medskip\noindent
{\it Bizony\'{\i}t\'as.}\/ V\'alasszunk olyan a csatorn\'aval
\"osszekapcsolt $\eta$ \'es $\eeta$
val\'osz\'{\i}n\H{u}s\'egi v\'al\-to\-z\'o\-kat amelyekre
$I(\eta\wedge\eeta)\ge (1-\e)C$, ahol $C$ a csatorna
kapacit\'asa. Ekkor
$$ \allowdisplaybreaks
\align
E\iota_k&=\summ_{v_i,\vv_j}
P(\eta=v_i,\eeta=\vv_j)\log\frac{p(\vv_j|v_i)}{q(\vv_j))}
=\summ_{v_i,\vv_j} r(v_i,\vv_j)\log\frac{r(v_i,\vv_j)}
{p(v_i)q(\vv_j)} \\
&=I(\eta\wedge\eeta)\ge (1-\e)C,
\endalign
$$
ahol $r(v_i,\vv_j)=P(\eta=v_i,\eeta=\vv_j)$, $p(v_i)=P(\eta=v_i)$,
\'es $q(\vv_j)=P(\eeta=\vv_j)$. Ez\'ert a nagy sz\'amok
gyenge t\"orv\'enye alapj\'an
$\frac1n\summ_{k=1}^n\iota_k\Rightarrow I(\eta\wedge\eeta)$,
ha $n\to\infty$, \'es $I(\eta\wedge\eeta)\ge (1-\e)C$.

Egy $n$ hossz\'us\'ag\'u eml\'ekezet n\'elk\"uli csatorna
kapacit\'as\'anak a kisz\'amol\'asa \'er\-de\-k\'e\-ben
tekints\"unk k\'et ezen eml\'ekezet n\'elk\"uli csatorna \'altal
\"osszekapcsolt $\eta=(\eta_1,\dots,\eta_n)$ \'es
$\eeta=(\eta_1,\dots,\eeta_n)$ v\'eletlen vektort, \'es
becs\"ulj\"uk meg az $I(\eta\wedge\eeta)$ k\"olcs\"on\"os
inform\'aci\'ot. Ennek \'erdek\'eben el\H{o}sz\"or megmutatom,
hogy $H(\eeta|\eta)=\summ_{k=1}^n H(\eeta_k|\eta_k)$.

Vezess\"uk be a k\"ovetkez\H{o} jel\"ol\'eseket:
$$ \allowdisplaybreaks
\align
p(v_{i_1},\dots,v_{i_n})&=P(\eta_1=v_{i_1},\dots,\eta_n=v_{i_n}),\\
q(\vv_{j_1},\dots,\vv_{j_n})&=
P(\eeta_1=\vv_{j_1},\dots,\eeta_n=\vv_{j_n}),\\
r(v_{i_1},\dots,v_{i_n},\vv_{j_1},\dots,\vv_{j_n})
&=P(\eta_1=v_{i_1},\dots,\eta_n=v_{i_n},
\eeta_1=\vv_{j_1},\dots,\eeta_n=\vv_{j_n}).
\endalign
$$
Ezekkel a jel\"ol\'esekkel
$r(v_{i_1},\dots,v_{i_n},\vv_{j_1},\dots,\vv_{j_n})=
p(v_{i_1},\dots,v_{i_n})\prodd_{k=1}^n p(\vv_{j_k}|v_{i_k})$,
\'es
$$ \allowdisplaybreaks
\align
H(\eeta|\eta)&=\summ_{(v_{i_1},\dots,v_{i_n}),(v_{j_1},\dots,v_{j_n})}
r(v_{i_1},\dots,v_{i_n},\vv_{j_1},\dots,\vv_{j_n})
\log\(\prodd_{k=1}^n p(\vv_{j_k}|v_{i_k}) \)\\
&=\summ_{(v_{i_1},\dots,v_{i_n}),(v_{j_1},\dots,v_{j_n})}
r(v_{i_1},\dots,v_{i_n},\vv_{j_1},\dots,\vv_{j_n})
\(\summ_{k=1}^n\log p(\vv_{j_k}|v_{i_k}) \)\\
&=\summ_{k=1}^n \summ_{(v_{i_1},\dots,v_{i_n}),(v_{j_1},\dots,v_{j_n})}
r(v_{i_1},\dots,v_{i_n},\vv_{j_1},\dots,\vv_{j_n})
\log p(\vv_{j_k}|v_{i_k}).
\endalign
$$
Vezess\"uk be a k\"ovetkez\H{o} mennyis\'egeket is:
$r_k(v_{i_k},\vv_{j_k})=P(\eta_k=v_{i_k},\eeta_k=\vv_{j_k})$,
$1\le k\le n$. Azt \'all\'{\i}tom, hogy ezzel a jel\"ol\'essel
az utols\'o azonoss\'ag jobb oldal\'an l\'ev\H{o} kifejez\'es
bels\H{o} \"osszeg\'et \'{\i}gy \'{\i}rhatjuk fel r\"ogz\'{\i}tett
$k$ indexre.
$$
\align
&\summ_{(v_{i_1},\dots,v_{i_n}),(v_{j_1},\dots,v_{j_n})}
r(v_{i_1},\dots,v_{i_n},\vv_{j_1},\dots,\vv_{j_n})
\log p(\vv_{j_k}|v_{i_k})\\
&\qquad=\sum_{(v_{i_k},\vv_{j_k})} r_k(v_{i_k},v_{j_k})
\log p(\vv_{j_k}|v_{i_k}).
\endalign
$$
Val\'oban, r\"ogz\'{\i}tve a tekintett \"osszegz\'esben a $v_{i_k}$,
\'es $\vv_{j_k}$ argumentumokat, \'es \"osszegezve az \"osszes
t\"obbi argumentum szerint az
$r_k(v_{i_k},v_{j_k})\log p(\vv_{j_k}|v_{i_k})$ kifejez\'est kapjuk,
majd ezekre az argumentumokra is \"osszegezve megkapjuk az el\H{o}bb
fel\'{\i}rt azonoss\'agot. Ezt az azonoss\'agot \"osszegezve a $k$
v\'altoz\'o szerint, \'es felhaszn\'alva az el\H{o}z\H{o}
azonoss\'agot azt kapjuk, hogy
$$
H(\eeta|\eta)=\sum_{k=1}^n
\sum_{(v_{i_k},\vv_{j_k})} r_k(v_{i_k},v_{j_k})
\log p(\vv_{j_k}|v_{i_k})=\sum_{k=1}^n H(\eeta_k|\eta_k),
$$
amint azt \'all\'{\i}tottam.

Vegy\"uk \'eszre, hogy  felt\'eteleink teljes\"ul\'ese eset\'eben
$H(\eeta)\le\summ_{k=1}^n H(\eeta_k)<\infty$, ez\'ert
$I(\eta\wedge\eeta)=H(\eeta)-H(\eeta|\eta)\le
\summ_{k=1}^n(H(\eeta_k)-H(\eeta_k|\eta_k))
=\summ_{k=1}^nI(\eta_k\wedge\eeta_k)$. Tov\'abb\'a, ha az
$\eta=(\eta_1,\dots,\eta_n)$ \'es $\eeta=(\eeta_1,\dots,\eeta_n)$
v\'eletlen vektorok az em\-l\'e\-ke\-zet n\'elk\"uli csatorna
szerinti \"osszekapcsolt val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok,
akkor ezek $(\eta_k,\eeta_k)$, $1\le k\le n$, koordin\'at\'ai
\"osszekapcsolt val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok azon
kiindul\'o csatorna szerint, amelynek a
se\-g\'{\i}t\-s\'e\-g\'e\-vel az em\-l\'e\-ke\-zet n\'elk\"uli
csatorn\'at defini\'altuk. Ez\'ert $I(\eta_k\wedge\eeta_k)\le C$,
\'es a bizony\'{\i}tott egyenl\H{o}tlens\'egb\H{o}l az is
k\"ovetkezik,  hogy $I(\eta\wedge\eeta)\le nC$. Mivel ez
tetsz\H{o}leges az eml\'ekezet n\'elk\"uli csatorna szerint
\"ossze\-kap\-csolt  $\eta$ \'es $\eeta$ v\'eletlen vektorokra
igaz, innen k\"ovetkezik, hogy egy $n$ hossz\'us\'ag\'u eml\'ekezet
n\'elk\"uli csatorna csatorna kapac\'{\i}t\'asa kisebb vagy
egyenl\H{o}, mint~$nC$.

Annak \'erdek\'eben, hogy bel\'assuk, hogy az $n$ hossz\'us\'ag\'u
eml\'ekezet n\'elk\"uli csatorna csatorna kapacit\'asa
val\'oj\'aban egyenl\H{o} az $nC$ mennyis\'eggel tekints\"unk
egym\'ast\'ol f\"ug\-get\-len, \'es az eml\'ekezet n\'elk\"uli
csatorn\'at meghat\'aroz\'o csatorn\'aval \"osszekapcsolt
$(\eta_k,\eeta_k)$, $1\le k\le n$, val\'osz\'{\i}n\H{u}s\'egi
p\'arokat. Ekkor az $\eta=(\eta_1,\dots,\eta_n)$ \'es
$\eeta=(\eeta_1,\dots,\eeta_n)$ v\'eletlen vektorok
\"osszekapcsoltak az eml\'ekezet n\'elk\"uli csatorna \'altal, \'es
$I(\eta\wedge\eeta)=\summ_{k=1}^n I(\eta\wedge_k\eeta_k)$. Mivel
minden $\e>0$ sz\'amra az $(\eta_k,\eeta_k)$ p\'arokat \'ugy is
v\'alaszthatjuk, hogy az $I(\eta_k\wedge\eeta_k)\ge C-\e$
rel\'aci\'o teljes\"ulj\"on, innen k\"ovetkezik, hogy egy
$n$ hossz\'us\'ag\'u eml\'ekezet n\'elk\"uli csatorna csatorna
kapacit\'asa nagyobb vagy egyenl\H{o}, mint $nC$. A lemm\'at
bel\'attuk.

\medskip
A k\"ovetkez\H{o} lemm\'aban olyan als\'o becsl\'est adunk egy
alkalmasan konstru\'alt $\lambda$ megk\"ul\"onb\"oztethet\H{o}
halmaz elemsz\'am\'ar\'ol, amely lehet\H{o}v\'e teszi, hogy az
el\H{o}z\H{o} lemma seg\'{\i}ts\'eg\'evel
bebizony\'{\i}tsuk a csatorna k\'odol\'asi t\'etelt.

\medskip\noindent
{\bf Als\'o becsl\'es alkalmasan konstru\'alt $\lambda$
megk\"ul\"onb\"oztethet\H{o} elemeket tartalmaz\'o halmaz
elemsz\'am\'ar\'ol.} {\it Legyen adva adva k\'et
$V=\{v_1,v_2,\dots\}$ \'es $\tilde V=\{\vv_1,\vv_2,\dots\}$
v\'eges vagy megsz\'aml\'alhat\'o halmaz, \'es k\"oz\"ott\"uk
egy $p(\vv_j|v_i)$, $v_i\in V$, $\vv_j\in\VV$,
\'at\-me\-net\-va\-l\'o\-sz\'{\i\-}n\H{u}\-s\'e\-gek\-kel
defini\'alt csatorna. Legyen $\eta$ \'es $\eeta$ k\'et e
csatorn\'aval \"ossze\-kap\-csolt val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'o, \'es vezess\"uk be a $\iota_{\eta\wedge\eeta}$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ot is a k\"ovetkez\H{o}
k\'ep\-let seg\'{\i}ts\'eg\'evel:
$\iota_{\eta\wedge\eeta}=\log\frac{p(v_i|\vv_j)}{q(\vv_j)}$,
ha $\eta=v_i$, \'es $\eeta=\vv_j$, ahol $q(\vv_j)=P(\eeta=\vv_j)$.
V\'alasszunk k\'et tetsz\H{o}leges $z>0$ \'es $0<\lambda<1$ sz\'amot.
L\'etezik a bemeneti jelek $V$ halmaz\'anak olyan $\lambda$
megk\"ul\"onb\"oztethet\H{o} elemekb\H{o}l \'all\'o r\'eszhalmaza,
amelynek $N$ elem\-sz\'a\-ma teljes\'{\i}ti az
$$
N\ge 2^z(\lambda-P(\iota_{\eta\wedge\eeta}<z))
$$
egyenl\H{o}tlens\'eget.}

\medskip
Miel\H{o}tt le\'{\i}rn\'am a bizony\'{\i}t\'ast, ismertetem
annak f\H{o} gondolat\'at. Egy
$\{v_{i_1},\dots,v_{i_N}\}$ $\lambda$
megk\"ul\"onb\"oztethet\H{o} elemekb\H{o}l \'all\'o halmazt
keres\"unk viszonylag nagy $N$ elemsz\'ammal, valamint a
$v_{i_k}$ pontokhoz olyan diszjunkt $B_{k}$ halmazokat
akarunk t\'ars\'{\i}tani, amelyekre
$\summ_{\vv_j\in B_k}p(\vv_j|v_{i_k})\ge1-\lambda$.
\'Erdemes olyan $B_k$ halmazokat v\'alasztani, amelyekre a
$P(\eeta\in B_k)=\summ_{\vv_j\in B_k}q(\vv_j)$
val\'osz\'{\i}n\H{u}s\'egek kicsik. Mivel
$\summ_{\vv_j\in B_k}p(\vv_j|v_{i_k})\ge1-\lambda$.
(egy heurisztikus okoskod\'asban feltehetj\"uk, hogy az utols\'o
k\'epletben egyenl\H{o}s\'eg van,) ez azt sugallja, hogy olyan
$B_k$ halmazokat \'erdemes defini\'alni, amelyek $\vv_j\in B_k$
elemeire $\frac{q(\vv_j)}{p(\vv_j|v_{i_k})}$ kicsi. Ez\'ert a
$B_k$ halmazt
$B_k=\VV\setminus\{\vv_j\colon\;\frac{p(\vv_j|v_{i_k})}{q(\vv_j)}\le z\}$
alakban keress\"uk, ahol a $z$ sz\'amot a te\-kin\-tett csatorna
tu\-laj\-do\-n\-s\'a\-gai\-t\'ol f\"ugg\H{o}en alkalmasan
v\'alasztjuk meg. \'Ugy akarjuk a $\lambda$
megk\"ul\"onb\"oztethet\H{o} $v_{i_k}\in V$ pontokat v\'alasztani,
hogy a $v_{i_k}$ pont a neki megfelel\H{o} $B_k$ halmazzal
egy\"utt teljes\'{\i}tse a
$\summ_{\vv_j\in B_k}p(\vv_j|v_{i_k})\ge1-\lambda$
egyenl\H{o}tlens\'eget. Val\'oj\'aban kiss\'e m\'ask\'eppen kell
elj\'arni annak \'erdek\'eben, hogy diszjunkt $B_k$ halmazokat
v\'alasszunk. Ha a $v_{i_1}$, \dots, $v_{i_{k-1}}$ pontokat \'es
$B_1,\dots,B_{k-1}$ halmazokat m\'ar kiv\'alasztottuk, akkor
pr\'ob\'alunk olyan $v_{i_k}\in V$ \'es hozz\'atartoz\'o
$B_k=(\VV\setminus \bigcupp_{j=1}^{k-1}B_j)
\setminus\{\vv_j\colon\;\frac{p(\vv_j|v_{i_k})}{q(\vv_j)}\le z\}$
 halmazt tal\'alni, amelyekre
$\summ_{\vv_j\in B_k}p(\vv_j|v_{i_k})\ge1-\lambda$.
Ezt az elj\'ar\'ast addig folytatjuk szukcesszive, am\'{\i}g meg
nem akadunk. A lemma arr\'ol sz\'ol, hogy ilyen m\'odon mekkora
$\lambda$ megk\"ul\"onb\"oztethet\H{o} elemekb\H{o}l \'all\'o
halmazt tudunk konstru\'alni.

\medskip\noindent
{\it A lemma bizony\'{\i}t\'asa.}\/ Defini\'aljuk a
$$
W=\left\{(v_i,\vv_j)\colon\; (v_i,\vv_j)\in V\times\VV,\;
\frac{p(\vv_j|v_i)}{q(\vv_j)}<2^z\right\},
$$
\'es
$$
W^{v_i}=\{\vv_j\colon\;\vv_j\in\VV,\; (v_i,\vv_j)\in W\},
\quad v_i\in V,
$$
halmazokat. Egy olyan $v_{i_1}\in V$ pontot v\'alasztunk, amelyre
$P(\eeta\in \VV\setminus W^{v_{i_1}}|\eta=v_{i_1})\ge 1-\lambda$,
felt\'eve, hogy ilyen pont l\'etezik. Ebben az esetben legyen
$B_1=\VV\setminus W^{v_{i_1}}$.
Ellenkez\H{o} esetben befejezz\"uk a procedur\'at egyetlen pont
kiv\'alaszt\'asa n\'elk\"ul. A
$v_{i_1}\in V$,\dots, $v_{i_{k}}\in V$ pontokat szukcesszive
v\'alasztjuk egym\'as ut\'an, \'es a $v_{i_p}$ ponthoz
t\'ars\'{\i}tott $B_p$ halmazt a
$$
B_1=\VV\setminus V^{v_1},\quad
B_p=\(\bigcapp_{l=1}^{p-1} W^{v_{i_l}}\)\setminus W^{v_{i_p}},
\qquad p=2,3,\dots.
$$
k\'eplettel defini\'aljuk. Ezek a $B_1,B_2,\dots$ halmazok
diszjunktak. Ha a $v_{i_1}\in V$,\dots, $v_{i_{k}}\in V$ pontok
m\'ar ki vannak v\'alasztva, akkor a $k+1$-k l\'ep\'esben olyan
$v_{i_{k+1}}\in V$ pontot keres\"unk, amelyre
$P(\eeta\in\(\bigcapp_{l=1}^kV^{v_{i_l}}\)
\setminus V^{v_{i_{k+1}}}|\eta=v_{i_{k+1}})\ge1-\lambda$, ugyanis ez
jelenti azt, hogy $P(\eeta\in B_{k+1}|\eta=v_{i_{k+1}})\ge1-\lambda$.
Ha ez a felt\'etel teljes\"ul, akkor v\'alasztunk egy k\'{\i}v\'ant
tulajdons\'ag\'u $v_{i_{k+1}}\in V$ pontot, ha nem teljes\"ul, akkor
a $v_{i_p}$ pontok v\'alaszt\'as\'at a $k$-ik l\'ep\'esben
befejezz\"uk. A lemm\'aban szerepl\H{o} $N$ sz\'amot v\'alaszthatjuk
\'ugy, mint a leg\-na\-gyobb olyan $k$ sz\'amot, amelyre v\'alasztottunk
$v_{i_k}$ pontot. Ugyanis az $A=\{v_{i_1},\dots,v_{i_N}\}$
halmaz pontjai a $B_1,\dots,B_N$ halmazokkal egy\"utt $\lambda$
megk\"ul\"onb\"oztethet\H{o} pontok.

Azon $k$ index nagys\'ag\'ara kell teh\'at j\'o als\'o becsl\'est
adni, amelyikre m\'eg tudjuk folytatni az algoritmusunkat, \'es
megfelel\H{o} tulajdons\'ag\'u $v_{i_k}\in V$ pontot tal\'alni.
A $k$-ik l\'ep\'es ut\'an akkor \'es csak akkor tudunk megfelel\H{o}
tulajdons\'ag\'u $v_{i_{k+1}}\in V$ pontot tal\'alni, ha
$\inff_{v_i\in V}P(\eeta\in \VV(k)\cup W^{v_i}|\eta=v_i)\le\lambda$,
ahol $\VV(1)=\VV$, \'es
$\VV(k)=\bigcupp_{l=1}^{k}(\VV\setminus W^{v_{i_l}})$, $k=1,2,\dots$.
Azt, hogy a k\'{\i}v\'ant felt\'etel \'erdekes esetekben teljes\"ul
a k\"ovetkez\H{o} becsl\'esek seg\'{\i}ts\'eg\'evel tudjuk
megmutatni.
$$
\align
&\inff_{v_i\in V}P(\eeta\in \VV(k)\cup W^{v_i}|\eta=v_i)\le
\sum_{v_i\in V}P(\eta=v_i)P(\eeta\in \VV(k)\cup W^{v_i}|\eta=v_i)\\
&\qquad=\sum_{v_i\in V}P(\eta=v_i,\eeta\in \VV(k)\cup W^{v_i})
=P((\eta,\eeta)\in (V\times \VV(k))\cup W)\\
&\qquad\le P(\eeta\in \VV(k))+P((\eta,\eeta)\in W)
\endalign
$$
M\'asr\'eszt
$P((\eta,\eeta)\in W)=P(\iota_{\eta\wedge\eeta}<z)$,
\'es a $\VV(k)$ halmaz definici\'oja alapj\'an
$$ \allowdisplaybreaks
\align
P(\eeta\in\VV(k))&\le\sum_{l=1}^k
P(\eeta\in \VV\setminus W^{v_{i_l}})
=\sum_{l=1}^k\sum_{\vv_j\colon
\frac{p(\vv_j|v_{i_l})}{q(\vv_j)}\ge 2^z} q(\vv_j)\\
&\le\sum_{l=1}^k\sum_{\vv_j\colon
\frac{p(\vv_j|v_{i_l})}{q(\vv_j)}\ge 2^z}
2^{-z}p(\vv_j|v_{i_l})
\le\sum_{l=1}^k\sum_{\vv_j\in \VV}2^{-z}p(\vv_j|v_{i_l})
=\sum_{l=1}^k2^{-z}=k2^{-z}.
\endalign
$$
A fenti becsl\'esekb\H{o}l k\"ovetkezik, hogy
$$
\inff_{v_i\in V}P(\eeta\in \VV(k)\cup W^{v_i}|\eta=v_i)\le
P(\iota_{\eta\wedge\eeta}<z)+k2^{-z},
$$
ez\'ert
$\inff_{v_i\in V}P(\eeta\in \VV(k)\cup W^{v_i}|\eta=v_i)\le\lambda$,
ha $k\le2^z(\lambda-P(\iota_{\eta\wedge\eeta}<z))$.
Ez azt jelenti, hogy a k\'{\i}v\'ant tulajdons\'ag\'u $u_{i_k}\in V$
pontok v\'alaszt\'as\'at tudjuk folytatni a $\bar k=
[2^z(\lambda-P(\iota_{\eta\wedge\eeta}<z))]+1$ \'ert\'ekig,
ahol $[x]$ az $x$ sz\'am eg\'esz r\'esz\'et jel\"oli.
Innen k\"ovetkezik a lemma \'all\'{\i}t\'asa.

\medskip\noindent
{\it A csatorna k\'odol\'asi t\'etel bizony\'{\i}t\'asa.}\/
V\'alasszunk olyan $(\eta',\eeta')$ val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'o p\'art, amelynek tagjai \"ossze vannak kapcsolva az
eml\'ekezet n\'elk\"uli csatorn\'at meg\-ha\-t\'a\-ro\-z\'o
csatorn\'aval, \'es $I(\eta'\wedge\eeta')\ge(1-\frac\e4)C$.
Legyen $(\eta_1,\eeta_1)$, $(\eta_2,\eeta_2)$,\dots,
$(\eta_n,\eeta)$ f\"uggetlen, az $(\eta',\eeta')$ v\'eletlen
vektorral azonos eloszl\'as\'u v\'eletlen vektorok sorozata,
\'es a $\iota_k$ va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi
v\'altoz\'ot defini\'alja a
$\iota_k=\log\frac{p(\vv_j|v_i)}{q(\vv_j)}$, ha $\eta_k=v_i$,
\'es $\eeta_k=\vv_j$ k\'eplet. Vezess\"uk be az
$\eta=(\eta_1,\dots,\eta_n)$ \'es $\eeta=(\eeta_1,\dots,\eeta_n)$
v\'eletlen vektorokat, \'es defini\'aljuk seg\'{\i}ts\'eg\"ukkel a
$\iota_{\eta\wedge\eeta}$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ot
\'ugy, mint az {\it Als\'o ecsl\'es alkalmasan konstru\'alt
$\lambda$ megk\"ul\"onb\"oztethet\H{o} elemeket tartalmaz\'o halmaz
elemsz\'am\'ar\'ol}\/ eredm\'eny megfogalmaz\'as\'aban tett\"uk.
Ekkor $\iota_{\eta\wedge\eeta}=\summ_{k=1}^n\iota_k$, ez\'ert
az eml\'ekezet n\'elk\"uli csatorna kapacit\'as\'ar\'ol
sz\'ol\'o lemma (els\H{o}) eredm\'enye alapj\'an l\'etezik olyan
$n_0$ k\"usz\"obindex, amely\-re igaz, hogy
$P(\iota_{\eta\wedge\eeta}<(1-\frac\e2)Cn)\le \frac\lambda2$,
ha $n\ge n_0$. Ez\'ert alkalmazva az {\it Als\'o becsl\'es
alkalmasan konstru\'alt $\lambda$ megk\"ul\"onb\"oztethet\H{o}
elemeket tartalmaz\'o halmaz elemsz\'am\'ar\'ol} eredm\'eny\'et
$z=(1-\frac\e2)Cn$ v\'alaszt\'assal azt kapjuk, hogy
$N\ge 2^z(\lambda-P(\iota_{\eta\wedge\eeta}<z))\ge
2^{(1-\e/2)Cn}\frac\lambda2\ge 2^{(1-\e)Cn}$, ha
$n\ge n_0(\e,\lambda)$. A t\'etel bizony\'{\i}t\'as\'at
befejezt\"uk.

\medskip
A csatorna k\'odol\'asi t\'etel megford\'{\i}t\'as\'anak a
bizony\'{\i}t\'asa v\'eges \'allapotter\H{u} csa\-tor\-n\'ak\-ra
azon alapul, hogy ebben az esetben a csatorna kapacit\'ast
defini\'al\'o szupr\'emum felv\'etetik, \'es explicit m\'odon
lehet jellemezni azokat a csatorn\'aval \"osszekapcsolt
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi v\'altoz\'o p\'arok
eloszl\'as\'at, amelyek k\"olcs\"on\"os inform\'aci\'oja
egyenl\H{o} a csatorna kapacit\'assal. Az al\'abbi eredm\'enyt
fogom bebizony\'{\i}tani.

\medskip\noindent
{\bf T\'etel v\'eges \'allapotter\H{u} csatorna optim\'alis
bemenet\'enek a jellemz\'es\'er\H{o}l.} {\it Le\-gyen adva k\'et
$V=\{v_1,\dots,v_m\}$ \'es $\tilde V=\{\vv_1,\dots,\vv_n\}$
v\'eges halmaz, \'es k\"oz\"ott\"uk egy
$p(\vv_j|v_i)$, $v_i\in V$, $\vv_j\in\VV$,
\'at\-me\-net\-va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gek\-kel
defini\'alt v\'eges \'allapotter\H{u} $C<\infty$ csatorna
kapacit\'as\'u csatorna. L\'etezik olyan e csatorn\'aval
\"osszekapcsolt $\eta$, $\eeta$
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi v\'altoz\'o p\'ar,
amely\-re $I(\eta\wedge\eeta)=C$. Egy e csatorn\'aval
\"osszekapcsolt $\eta$, $\eeta$
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi v\'altoz\'o p\'arra akkor \'es
csak akkor igaz az $I(\eta\wedge\eeta)=C$ egyenl\H{o}s\'eg, ha a
$p(v_i)=P(\eta=v_i)$, $v_i\in V$, \'es $q(\vv_j)=P(\eeta=\vv_j)$,
$\vv_j\in\VV$,  val\'osz\'{\i}n\H{u}s\'egek teljes\'{\i}tik a
$$
\summ_{\vv_j\in\VV} p(\vv_j|v_i)\log\frac{p(\vv_j|v_i)}{q(\vv_j)}\le C
\quad \text{minden $v_i\in V$ pontban}  \tag3.1
$$
egyenl\H{o}tlens\'egeket, \'es ha $p(v_i)>0$, akkor a $v_i$ pontnak
megfelel\H{o} egyenl\H{o}tlens\'egben egyen\-l\H{o}\-s\'e\-get
is \'{\i}rhatunk.}

\medskip\noindent
{\it Megjegyz\'es.} A (3.1) k\'eplet \'ugy \'ertend\H{o}, hogy
$p(\vv_j|v_i)\log\frac{p(\vv_j|v_i)}{q(\vv_j)}=0$, ha
$p(\vv_j|v_i)=0$. A t\'etel azt is \'all\'{\i}tja, hogy $q(\vv_j)>0$,
ha $p(\vv_j|v_i)>0$ valamilyen $v_i$ bemen\H{o} \'allapotra
(egy az $I(\eta\wedge\eeta)=C$ felt\'etelt teljes\'{\i}t\H{o} a
csatorn\'aval \"osszekapcsolt $\eta,\eeta$ p\'ar \'altal defini\'alt
$q(\vv_j)=P(\eeta=\vv_j)$ val\'osz\'{\i}n\H{u}s\'egre). Igaz a
$$
\summ_{\vv_j\in\VV} p(\vv_j|v_i)\log\frac{p(\vv_j|v_i)}{q(\vv_j)}\ge0
\quad \text{minden $v_i\in V$ pontban}
$$
egyenl\H{o}tlens\'eg is. Ez k\"ovetkezik p\'eld\'aul a
m\'asodik fejezetben bizony\'{\i}tott {\it Egy $I$-di\-ver\-gen\-cia
tipus\'u lemm\'abol} az $a_j=p(\vv_j|v_i)$ \'es
$b_j=q(\vv_j)$ szereposzt\'assal felhaszn\'alva az
$A=\summ_{\vv_j\in\VV}p(\vv_j|v_i)=1$ \'es
$B=\summ_{\vv_j\in \VV}q(\vv_j)=1$ rel\'aci\'okat.

\medskip
A t\'etel bizony\'{\i}t\'asa k\'et f\"uggv\'enyek
konvexit\'as\'aval (vagy konk\'av\'{\i}t\'as\'aval) kapcsolatos
eredm\'enyen alapul. Az els\H{o} lemma arr\'ol sz\'ol, hogy egy
f\"uggv\'eny, amely a k\"olcs\"on\"os inform\'aci\'ot defini\'al\'o
f\"uggv\'eny term\'eszetes kiterjeszt\'es\'enek tekinthet\H{o},
konk\'av.

\medskip\noindent
{\bf Lemma egy f\"uggv\'eny konk\'avit\'as\'ar\'ol.} {\it Legyenek
adva bizonyos $p(i,j)$, $1\le i\le M$, $1\le j\le N$ sz\'amok,
amelyekre $0\le p(i,j)\le 1$ minden $1\le i\le M$ \'es
$1\le j\le N$ indexre, \'es $\summ_{j=1}^N p(i,j)=1$ minden
$1\le i\le M$ indexre. Defini\'aljuk seg\'{\i}ts\'eg\"ukkel az
$$
F(u_1,\dots,u_M)
=\sum_{i=1}^M\sum_{j=1}^N u_i p(i,j)\log\frac{p(i,j)}{y_j},
\quad u_i\ge 0 \text{ minden } 1\le i\le M \text{ indexre}
$$
f\"uggv\'enyt, ahol $y_j=y_j(u_1,\dots,u_M)=\summ_{i=1}^Mp(i,j)u_i$.
Az $F(u_1,\dots,u_M)$ f\"uggv\'eny foly\-to\-nos \'es konk\'av az
$A=\{(u_1,\dots,u_M)\colon\; u_i\ge0, \;1\le i\le M\}$ halmazon.}

\medskip\noindent
{\it Megjegyz\'es.} Az $F$ f\"uggv\'enyt defini\'al\'o \"osszeg
\'ugy \'ertend\H{o}, hogy csak azon $(i,j)$ p\'arokra \"osszegz\"unk,
amelyekre $p(i,j)>0$. Teh\'at az
$u_i p(i,j)\log\frac{p(i,j)}{y_j}=0$ konvenci\'ot fogjuk alkalmazni
a $p(i,j)=0$ esetben akkor is, ha $y_j=0$. Sz\"uks\'eges m\'eg
defini\'alni az $u_i p(i,j)\log\frac{p(i,j)}{y_j}$
kifejez\'est akkor, ha az $u_i=0$, mert ekkor is el\H{o}fordulhat,
hogy $y_j=0$. Ebben az esetben az
$u_i p(i,j)\log\frac{p(i,j)}{y_j}=0$, ha $u_i=0$ konvenci\'ot
fogjuk alkalmazni. A k\"ovetkez\H{o} sz\'amol\'asokban az
egyszer\H{u}bb jel\"ol\'es kedv\'e\'ert a $\log$ term\'eszetes \'es
nem 2 alap\'u logaritmust fog jel\"olni, de ennek nincs nagy
jelent\H{o}s\'ege. A term\'eszetes logaritmusr\'ol a 2 alap\'u
logaritmusra val\'o \'att\'er\'es csak $\log_2 e$-vel val\'o
szorz\'ast jelent.

\medskip\noindent
{\it Bizony\'{\i}t\'as.}\/ Az $F$ f\"uggv\'eny folytonos, ha a
hat\'aron \'ugy defini\'aljuk, ahogy a fenti meg\-jegy\-z\'es\-ben
tett\"uk. Ezen \'all\'{\i}t\'as egyetlen r\'eszletesebb
indokl\'ast ig\'enyl\H{o} r\'esze az, hogy az olyan $(i,j)$
indexp\'arokra, amelyekre $p(i,j)>0$ az
$u_i p(i,j)\log\frac{p(i,j)}{y_j}$ f\"uggv\'eny folytonos az
olyan $u$ pontokban is, amelyek $i$-ik koordin\'at\'aja
$u_i=0$. Azt kell ellen\H{o}rizni, hogy ha $u_i^{(n)}\to0$,
akkor $u_i^{(n)}p(i,j)\log\frac{p(i,j)}{y^{(n)}_j}\to0$. De
ekkor $\frac{p(i,j)}{y_j^{(n)}}\le \frac1{u^{(n)}_i}$, ez\'ert
$u_i^{(n)}p(i,j)\log\frac{p(i,j)}{y^{(n)}_j}
\le u^{(n)}_ip(i,j)\log\frac1{ u^{(n)}_i}\to0$,
\'es ezt kellett bel\'atni. Ha $u_i>0$ akkor az
$u_ip(i,j)\log\frac{p(i,j)}{y_j}$ f\"uggv\'eny folytonoss\'aga
k\"onnyen l\'athat\'o.

Az $F$ f\"uggv\'eny konk\'avit\'as\'anak
bizony\'{\i}t\'as\'ahoz el\'eg megmutatni, hogy a
$\(\frac{\partial^2 F}{\partial u_k\partial u_l}\)$, $1\le k,l\le M$,
m\'atrix negat\'{\i}v szemidefinit minden $(u_1,\dots,u_M)$, $u_i>0$,
$1\le i\le M$ pontban. (Mivel az $F$ f\"uggv\'eny folytonos el\'eg
csak azokat a pontokat tekinteni, amelyek koordin\'at\'ai szigor\'uan
pozit\'{\i}vak.) Sz\'amoljuk ki e m\'atrix elemeit. Fel\'{\i}rhatjuk,
hogy
$$
\frac{\partial F}{\partial u_k}=\sum_{j=1}^Np(k,j)\log p(k,j)
-\summ_{j=1}^N p(k.j)\log y_j
-\summ_{i=1}^M\summ_{j=1}^N u_i p(i,j)\frac{p(k,j)}{y_j}.
$$
Az utols\'o kifejez\'esben szerepl\H{o} kett\H{o}s szumma
val\'oj\'aban konstans. Ugyanis
$$
\summ_{i=1}^M\summ_{j=1}^N u_i p(i,j)\frac{p(k,j)}{y_j}
=\summ_{j=1}^N\frac{p(k,j)}{y_j}\(\summ_{i=1}^M u_i p(i,j)\)
=\summ_{j=1}^N p(k,j)\frac{y_j}{y_j}=1.
$$
Innen
$$
\frac{\partial F}{\partial u_k}
=\summ_{j=1}^Np(k,j)\log\frac{p(k,j)}{y_j}-1
=\summ_{j=1}^N y_j g\(\frac{p(k,j)}{y_j}\)-1,
\tag3.2
$$
(ahol $g(x)=x\log x$), \'es
$$
\frac{\partial^2 F}{\partial u_k\partial u_l}=
-\frac{\partial}{\partial u_l}\(\summ_{j=1}^N p(k,j)\log y_j\)
=-\summ_{j=1}^N\frac{p(k,j)p(l,j)}{y_j}.
$$
(A fenti sz\'amol\'asok jogosak. Az $u_i>0$ minden $1\le i\le N$
felt\'etel biztos\'{\i}tja, hogy $y_j>0$ minden $j$ indexre.
Ez\'ert az $\frac1{y_j}$ alak\'u tagok megjelen\'ese nem
okoz probl\'em\'at a fenti sz\'amol\'asokban.)

Az $F$ f\"uggv\'eny konk\'avit\'as\'anak a bizony\'{\i}t\'as\'ahoz
azt kell bel\'atni,  hogy tetsz\H{o}leges
$((\alpha(1),\dots,\alpha(M))$ vektorra
$$
\summ_{k=1}^M\summ_{l=1}^M
\frac{\partial^2 F}{\partial u_k\partial u_l}\alpha(k)\alpha(l)\le0.
$$
Viszont
$$
\align
&\summ_{k=1}^M\summ_{l=1}^M
\frac{\partial^2 F}{\partial u_k\partial u_l}\alpha(k)\alpha(l)
=-\sum_{k=1}^M\sum_{l=1}^M\summ_{j=1}^N\frac{p(k,j)p(l,j)}{y_j}
\alpha(k)\alpha(l)\\
&\qquad =-\summ_{j=1}^N\frac1{y_j}\sum_{k=1}^M\sum_{l=1}^M
p(k,j)p(l,j)\alpha(k)\alpha(l)
=-\summ_{j=1}^N\frac1{y_j}\(\sum_{k=1}^Mp(k,j)\alpha(k)\)^2\le0.
\endalign
$$

\medskip
Sz\"uks\'eg\"unk lesz m\'eg az el\H{o}z\H{o} lemma egy
kieg\'esz\'{\i}t\'es\'ere is, amelyik a
$\frac{\partial F}{\partial u_k}(u)$ parci\'alis deriv\'alt
viselked\'es\'et olyan $u$ vektorokra is le\'{\i}rja, amelyeknek
van 0 koordin\'at\'aja. Ami\-kor a $k$-ik koordin\'ata szerinti
parci\'alis deriv\'altat tekintj\"uk meg kell k\"ul\"onb\"oztetn\"unk
azt az esetet, amikor az $u$ vektor $u_k$ koordin\'at\'aja
az $u_k>0$ \'es amikor az $u_k=0$ rel\'aci\'ot teljes\'{\i}ti.
Be fogjuk l\'atni, hogy az els\H{o} esetben a parci\'alis deriv\'alt
folytonos, \'es teljes\'{\i}ti a (3.2) formul\'at. A m\'asodik
esetben azt \'all\'{\i}tom, hogy ekkor is l\'etezik (az
egyoldali) parci\'alis deriv\'alt, \'es az egyenl\H{o} a parci\'alis
deriv\'alt ir\'anymenti hat\'ar\'ert\'ek\'evel. Ez az ir\'anymenti
hat\'ar\'er\'ek azonban v\'egtelen is lehet.

Azt, hogy a $\frac{\partial F}{\partial u_k}(u)$ f\"uggv\'enynek
l\'etezik ir\'anymenti hat\'ar\'ert\'eke az $u=(u_1,\dots,u_M)$
pontban azt jelenti, hogy l\'etezik a
$G_k(u)=\limm_{t\to0+}\frac{\partial F}{\partial u_k}(u+t\tilde u)$
esetleg v\'egtelennel egyenl\H{o} hat\'ar\'ert\'ek minden olyan
$\tilde u=(\tilde u_1,\dots,\tilde u_M)$ vektorra, amelynek $k$-ik
koordin\'at\'aja $\tilde u_k=1$, \'es $u+t\tilde u\in A$ el\'eg
kis $t>0$ sz\'amokra. Tov\'abb\'a ez a hat\'ar\'ert\'ek nem f\"ugg
az $\tilde u$ vektor v\'alaszt\'as\'at\'ol. A $\limm_{t\to0+}$
azt jelenti, hogy szigor\'uan pozit\'{\i}v $t>0$ sz\'amokkal
tekintj\"uk ezt a limeszt. Nem neh\'ez l\'atni az $F$
f\"uggv\'eny konk\'avit\'as\'anak felhaszn\'al\'as\'aval, hogy
ha a $G_k(u)$ ir\'anymenti hat\'ar\'ert\'ek l\'etezik egy olyan
$u=(u_1,\dots,u_M)$ pontban, amelyre $u_k=0$, akkor
$G_k(u)=\frac{\partial F}{\partial u_k}(u)$, ahol
$\frac{\partial F}{\partial u_k}(u)$ a megfelel\H{o} f\'eloldali
parci\'alis deriv\'altat jel\"oli.

\medskip\noindent
{\bf Kieg\'esz\'{\i}t\'es az egy f\"uggv\'eny konk\'avit\'as\'ar\'ol
sz\'ol\'o lemm\'ahoz.} {\it A lemm\'aban te\-kin\-tett $F$
f\"uggv\'eny $\frac{\partial F}{\partial u_k}$ parci\'alis
deriv\'altja folytonos f\"uggv\'eny az
$$
A_k=\{(u_1,\dots,u_M)\colon\; u_i\ge0, \text{ minden }
1\le i\le M, \text{ indexre, \'es } u_k>0 \}
$$
halmazon minden $1\le k\le M$ indexre, \'es teljes\'{\i}ti a (3.2)
formul\'at a k\"ovetkez\H{o} ki\-eg\'e\-sz\'{\i}\-t\'es\-sel. Ha
$p(k,j)=0$, akkor $p(k,j)\log \frac{p(k,j)}{y_j}=0$ definici\'o
szerint. Ha $p(k,j)>0$, \'es $u\in A_k$, akkor $y_j>0$.

Ha az $u=(u_1,\dots,u_M)\in A$ pontban $u_k=0$, akkor is l\'etezik a
$\frac{\partial F}{\partial u_k}(u)$ f\"uggv\'eny $G_k(u)$
ir\'anymenti hat\'ar\'ert\'eke az $u$ pontban. Ez az ir\'anymenti
hat\'ar\'ert\'ek akkor \'es csak akkor v\'eges, ha az $y_j=y_j(u)$
sz\'amra $y_j>0$ minden olyan $j$ indexre, amelyre $p(k,j)>0$.}

\medskip\noindent
{\it Bizony\'{\i}t\'as.}\/ Tekints\"unk
egy $u=(u_1,\dots,u_k)\in A_k$ pontot. Mivel $u_k>0$,
$y_j\ge u_kp(k,j)>0$ minden olyan $j$ indexre, amelyre
$p(k,j)>0$. Azt \'all\'{\i}tom, hogy a (3.2) formula minden
$u\in A_k$ pontban \'erv\'enyes, ha azokat a tagokat, amelyekre
$p(k,j)=0$ elhagyjuk az \"osszegez\'esb\H{o}l. Ez esetben csak
olyan $j$ indexeket kell figyelembe venni az \"osszegz\'esben,
amelyekre $\frac1{y_j}<\infty$, ez\'ert a (3.2) formu\'aban
szerepl\H{o} \"osszeg v\'eges. L\'assuk be el\H{o}sz\"or,
hogy a $\frac{\partial F}{\partial u_k}$ kifejez\'esre adott
a (3.2) formu\'at megel\H{o}z\H{o} \"osszef\"ugg\'es
\'erv\'enyes, ha $u\in A_k$.

Ennek igazol\'as\'ahoz el\'eg azt ellen\H{o}rizni, hogy
$$
\frac{\partial}{\partial u_k} u_ip(i,j)\log y_j
=\delta(i,k)p(i,j)\log y_j+u_ip(i,j)\frac{p(k,j)}{y_j},
$$
ahol $\delta(i,k)=0$, ha $i\neq k$,
\'es $\delta(i,k)=1$, ha $i=k$, minden olyan $(i,j)$, p\'arra,
amely\-re $p(i,j)>0$. Ez igaz, ha $u_i>0$, \'es ez\'ert $y_j>0$,
\'es igaz akkor is, ha $u_i=0$, \'es a
$\delta(i,k) p(i,j)\log y_j=0$ valamint a $p(k,j)=0$ esetben a
$\frac{p(k,j)}{y_j}=0$ konvenci\'ot al\-kal\-maz\-zuk. (Ezt a
konvenci\'ot alkalmazzuk akkor is, ha $y_j=0$.) Ekkor az
azonoss\'ag mind a k\'et oldala 0-val  egyenl\H{o}. (Ha $u_i=0$,
akkor $i\neq k$, \'es az azonoss\'ag baloldal\'an szerepl\H{o}
differenci\'aland\'o f\"uggv\'eny a lemma bizony\'{\i}t\'asa
el\H{o}tti megjegyz\'esben megfogalmazott
konvenci\'o szerint azonosan nulla.)

Az az azonoss\'ag, amely seg\'{\i}ts\'eg\'evel a (3.2)
azonoss\'agot ebb\H{o}l a formul\'ab\'ol le\-ve\-zet\-t\"uk
most is alkalmazhat\'o. Teh\'at a (3.2) formula is igaz.
V\'eg\"ul nem neh\'ez l\'atni, hogy a (3.2) k\'eplettel
megadhat\'o $\frac{\partial F}{\partial u_k}(u)$ deriv\'alt
folytonos egy $u\in A_k$ pontban. Azt kell \'eszrevenni,
hogy az $u_k>0$ felt\'etel miatt az $y_j=y_j(u_1,\dots,u_M)$
f\"uggv\'eny folytonos \'es null\'at\'ol szepar\'alt az
$u=(u_1,\dots,u_k)$ pont egy kis k\"ornyezet\'eben minden olyan
$j$ indexre, amelyre $p(k,j)>0$. Ez\'ert a
$g\(\frac{p(k,j)}{y_j}\)$ \'es
$\frac{\partial F}{\partial u_k}$ f\"uggv\'enyek is
folytonosak ebben a pontban.

Ha $u=(u_1,\dots,u_M)\in A$ olyan pont, amelyre $u_k=0$, \'es az
$\tilde u=(\tilde u_1,\dots,\tilde u_M)$ pontra $\tilde u_k=1$,
\'es $u+t\tilde u\in A$ el\'eg kis $t>0$ sz\'amra, akkor
$u+t\tilde u\in A_k$ kis $t>0$ sz\'amokra. Ez\'ert a
$\frac{\partial F}{\partial u_k}(u+t\tilde u)$ kifejez\'esre
\'erv\'enyes a (3.2) formula, \'es az ir\'anymenti deriv\'alt
l\'etez\'es\'ehez azt kell ellen\H{o}rizni, hogy az e formula
jobb  oldal\'an szerepl\H{o} kifejez\'esnek van az $\tilde u$
vektort\'ol f\"uggetlen hat\'ar\'ert\'eke. Ez azonban k\"onnyen
l\'athat\'o felhaszn\'alva, hogy
$\limm_{t\to0}y_j(u+t\tilde u)=y_j(u)$ minden $1\le j\le M$
indexre. Tov\'abb\'a ez a limesz akkor \'es csak akkor v\'egtelen,
ha l\'etezik olyan $j$ index, amelyre $p(k,j))>0$, \'es $y_j=0$.

\medskip
A m\'asik lemma, amely hasznos lesz az
egy v\'eges \'allapotter\H{u} csatorna optim\'alis
bemenet\'enek a jellemz\'es\'eben az \'ugynevezett Kuhn--Tucker
t\'etelnek egy speci\'alis \'es egyszer\H{u}bben bizony\'{\i}that\'o
esete. A Kuhn--Tucker t\'etel a konvex programoz\'as egyik alapvet\H{o}
eredm\'enye. B\'ar a Kuhn--Tucker t\'etel \'altal\'anos alakj\'ara
nem lesz sz\"uks\'ag\"unk, r\"oviden, bizony\'{\i}t\'as n\'elk\"ul
ismertetni fogom ezt az eredm\'enyt is. A bizony\'{\i}t\'as
megtal\'alhat\'o p\'eld\'aul Ji\u{r}\'{\i} Matou\u{s}ek \'es Bernd
G\"artner {\it Understanding and Using Linear Programming}\/
k\"onyv\'eben (Proposition 8.7.2). Bizony\'{\i}tani csak a
k\"ovetkez\H{o} eredm\'enyt fogom.

\medskip\noindent
{\bf A Kuhn--Tucker t\'etel egy speci\'alis esete.} {\it Legyen
adva egy folytonos \'es kon\-k\'av $F(u_1,\dots,u_M)$
f\"ugg\-v\'eny az
$A=\{(u_1,\dots,u_M)\colon\; u_i\ge0,\;1\le i\le M\}$ halmazon,
amelyre a $\frac{\partial F}{\partial u_k}$ parci\'alis
de\-ri\-v\'alt l\'etezik \'es folytonos az
$A_k=\{(u_1,\dots,u_M)\colon\; u_i\ge0,\;1\le i\le M,\text{ \'es }u_k>0\}$
halmazon minden $1\le k\le M$ indexre, tov\'abb\'a l\'etezik a
$\frac{\partial F}{\partial u_k}$ parci\'alis de\-ri\-v\'alt
ir\'anymenti hat\'ar\'ert\'eke azon  $u=(u_1,\dots,u_M)\in A$
pontokban is, amelyekre $u_k=0$. Keress\"uk az $F(u_1,\dots,u_M)$
f\"uggv\'eny maximum\'at a $\summ_{i=1}^Mu_i=1$ felt\'etel
mellett, azaz az $A\cap B$ halmazon, ahol
$B=\{(u_1,\dots,u_M)\colon\;\summ_{i=1}^Mu_i=1\}$. Egy
$\bar u=(\bar u_1,\dots,\bar u_M)$, $\bar u\in A\cap B$,
vektor akkor \'es csak akkor megold\'asa ennek a
sz\'els\H{o}\'ert\'ek feladatnak, ha l\'etezik olyan $D<\infty$
konstans, amelyre $\frac{\partial F}{\partial u_i}(\bar u)\le D$
minden $1\le i\le M$ indexre, \'es ebben a rel\'aci\'oban
egyenl\H{o}s\'eg \'all azon $i$ indexekre, amelyekre $\bar u_i>0$.}

\medskip\noindent
{\it Bizony\'{\i}t\'as.} Legyen $\bar u=(\bar u_1,\dots,\bar u_M)$
a sz\'els\H{o}\'ert\'ek feladat megold\'asa. V\'alasszuk ki e
vektor k\'et $\bar u_i$ \'es $\bar u_j$ koordin\'at\'at \'ugy,
 hogy $\bar u_i>0$. Jel\"olje $u(i,j)$ azt az $M$-dimenzi\'os
vektort, amelynek az $i$-ik koordin\'at\'aja $-1$, a $j$-ik
koordin\'at\'aja 1, \'es az \"osszes t\"obbi koordin\'at\'aja 0.
Ekkor az $\bar u(\vartheta)=\bar u+\vartheta u(i,j)$
vektorra $\bar u(\vartheta)\in A\cap B$, ha a $\vartheta>0$
sz\'am el\'eg kicsi. Innen azt kapjuk, hogy a
$g(\vartheta)=\frac{F(\bar u(\vartheta))-F(\bar u)}{\vartheta}$
f\"uggv\'eny kis $\vartheta>0$ param\'eterrel teljes\'{\i}ti a
$$
0\ge g(\vartheta)=\frac{dF(u(\vartheta))}{d\vartheta}(\vartheta')
=\(-\frac{\partial F}{\partial u_i}+
\frac{\partial F}{\partial u_j}\)(\bar u+\vartheta'\bar u(i,j))
$$
rel\'aci\'ot alkalmas $0<\vartheta'<\vartheta$ sz\'ammal.
A $\vartheta\to0$ hat\'ar\'atmenetet alkalmazva ebben a k\'epletben
azt kapjuk, hogy $\frac{\partial F}{\partial u_j}(\bar u)
\le\frac{\partial F}{\partial u_i}(\bar u)$. Legyen
$D=\frac{\partial F}{\partial u_i}(\bar u)$. Ekkor
$\frac{\partial F}{\partial u_j}(\bar u)\le D$ minden $1\le j\le M$
indexre. De mivel a fenti \'ervel\'esben tetsz\H{o}leges olyan
$i$ indexet v\'alaszthatunk, amelyre $\bar u_i>0$ innen az is
k\"ovetkezik, hogy
$D=\frac{\partial F}{\partial u_i}(\bar u)$ minden olyan $i$ indexre,
amelyre $\bar u_i>0$.

Megford\'{\i}tva, legyen $\bar u=(\bar u_1,\dots,\bar u_M)\in A\cap B$
olyan vektor, amelyikre l\'etezik olyan $D<\infty$ sz\'am, amelyre
$\frac{\partial F}{\partial u_i}(\bar u)\le D$ minden $1\le i\le M$
indexre, \'es ebben a rel\'aci\'oban egyenl\H{o}s\'eg van azon $i$
indexekre, amelyekre $\bar u_i>0$. Ekkor, mivel $F$ konk\'av
f\"uggv\'eny
$$
F(\vartheta u+(1-\vartheta)\bar u)
\ge\vartheta F(u)+(1-\vartheta)F(\bar u),
$$
azaz
$$
\frac{F(\bar u+\vartheta(u-\bar u))-F(\bar u)}\vartheta
\ge F(u)-F(\bar u)
$$
minden $u\in A\cap B$ vektorra \'es $0\le \vartheta\le 1$ sz\'amra.
Innen $\vartheta\to0$ hat\'ar\'atmenettel
$$
\sum_{i=1}^M\frac{\partial F}{\partial u_i}(\bar u)(u_i-\bar u_i)
\ge F(u)-F(\bar u).
$$
Azt \'all\'{\i}tom, hogy
$\summ_{i=1}^M\frac{\partial F}{\partial u_i}(\bar u)(u_i-\bar u_i)\le0$.
Val\'oban, abban a speci\'alis esetben, amikor
$\frac{\partial F}{\partial u_i}(\bar u)= D$ minden $1\le i\le M$
indexre ez a rel\'aci\'o egyenl\H{o}s\'eggel is \'erv\'enyes,
mert $\summ_{i=1}^M\bar u_i=\summ_{i=1}^M u_i=1$ az $u\in B$ \'es
$\bar u\in B$ felt\'etel miatt. A
$\frac{\partial F}{\partial u_i}(\bar u)<D$ szigor\'u
egyenl\H{o}tlens\'eg csak olyan $i$ indexekre \'erv\'enyes, amelyekre
$\bar u_i=0$. Ezenk\'{\i}v\"ul $u_i\ge0$ az $u\in A$ rel\'aci\'o
miatt, ez\'ert ebben az esetben
$\frac{\partial F}{\partial u_i}(\bar u)(u_i-\bar u_i)\le D(u_i-\bar u_i)$.
Innen
$\summ_{i=1}^M\frac{\partial F}{\partial u_i}(\bar u)(u_i-\bar u_i)
\le\summ_{i=1}^M D(u_i-\bar u_i)=0$, amint \'all\'{\i}tottam.
Azt kaptuk, hogy $F(u)-F(\bar u)\le0$ minden $u\in A\cap B$ vektorra,
teh\'at a $\bar u$ pont a vizsg\'alt sz\'els\H{o}\'ert\'ek feladat
megold\'asa. A t\'etelt bel\'attuk.

\medskip
Megfogalmazom a Kuhn--Tucker t\'etel eredeti alakj\'at.

\medskip\noindent
{\bf Kuhn--Tucker t\'etel.} {\it Tekints\"uk a
$$
\gather
\min f(x_1,\dots,x_N)\\
Ax^*=b  \\
x_i\ge0 \text{ minden } 1\le i\le N \text{ indexre}
\endgather
$$
optimaliz\'aci\'os feladatot, ahol $f(x_1,\dots,x_N)$ egy
minden\"utt differenci\'alhat\'o, konvex f\"ugg\-v\'eny,
$b=(b_1,\dots,b_M)\in R^M$, $A$ egy $N\times M$ m\'eret\H{u}
m\'atrix, $x^*$ az $x$ vektor transzpon\'altj\'at jel\"oli,
\'es $x=(x_1,\dots,x_N)$. Egy
$\bar x=(\bar x_1,\dots,\bar x_N)\in R^N$, $x_i\ge0$,
$1\le i\le N$, $A\bar x^*=b$, vektor akkor \'es csak akkor
megold\'asa ennek az optimaliz\'aci\'os feladatnak, ha
l\'etezik olyan $m=(m_1,\dots,m_M)\in R^M$ vektor, amelyre
$$
\frac{\partial f}{\partial x_j}(\bar x_1,\dots,\bar x_N)+ (m, a_j)
\;\;\left\{ \aligned
&=0 \quad \text{ha }\bar x_j>0\\
&\ge0 \quad \text{ha }x_j=0,
\endaligned \right.
$$
ahol $a_j$ az $A$ m\'atix $j$-ik oszlop\'at, \'es $(x,y)$ az
$x$ \'es $y$ vektorok skal\'arszorzat\'at jel\"oli.}

\medskip
Az el\H{o}z\H{o}leg t\'argyalt konk\'av f\"uggv\'eny
maximaliz\'aci\'os probl\'em\'aja \'atfogalmazhat\'o ilyen
konvex optimaliz\'aci\'os probl\'em\'av\'a $-1$-gyel val\'o
szorz\'as seg\'{\i}ts\'eg\'evel. Az optimaliz\'aci\'o ott
kimondott felt\'etele is \'atfogalmazhat\'o az e t\'etelben
kimondott alakra. Ebben az esetben az $1\times N$ m\'eret\H{u}
$A$ m\'atrix szerep\'et a csupa 1 sz\'amot tartalmaz\'o
vektor j\'atssza, \'es az 1 dimenzi\'os $m$ vektor $-D$-vel
egyenl\H{o}, a t\'etelben szerel\H{o} $D$ sz\'ammal. Az e
jegy\-zet\-ben bizony\'{\i}tott t\'etel, --- ha eltekint\"unk
az $F$ f\"uggv\'enyre tett simas\'agi felt\'etelekt\H{o}l --- a
Kuhn--Tucker t\'etel speci\'alis eset\'enek tekinthet\H{o}
ezzel a szereposzt\'assal.

A Kuhn--Tucker t\'etel l\'enyeges \'ujdons\'aga az \'altalunk
t\'argyalt eredm\'enyhez k\'epest az, hogy nem csak egy
line\'aris felt\'etel teljes\"ul\'ese eset\'en jellemzi az
optim\'alis meg\-ol\-d\'a\-so\-kat. Az eredm\'eny ilyen
ir\'any\'u jav\'{\i}t\'as\'at csak l\'enyegesen \'uj gondolatok
felhaszn\'al\'as\'aval le\-he\-tett el\'erni. A t\'etel
igazol\'as\'anak f\H{o} neh\'ezs\'ege a benne szerepl\H{o}
felt\'etel sz\"uk\-s\'e\-ges\-s\'e\-g\'e\-nek, vagyis annak a
t\'enynek a bizony\'{\i}t\'asa, hogy ha egy
$x=(x_1,\dots,x_N)$ vektor megold\'asa a minimum feladatnak
akkor teljes\'{\i}ti a megadott egyenl\H{o}s\'egekb\H{o}l
\'es egyenl\H{o}tlens\'egekb\H{o}l \'all\'o felt\'etelt.
K\"ul\"on\"osen fontos a felt\'etelben szerepl\H{o} $m$
vektor megtal\'al\'asa. Kuhn \'es Tucker ezt a line\'aris
programoz\'as dualit\'as t\'etel\'enek a seg\'{\i}ts\'eg\'evel
tudta megtenni. Az eredeti
optimaliz\'aci\'os feladat megold\'asa teljes\'{\i}t egy
line\'aris optimaliz\'aci\'os feladatot (csak implicit
m\'odon defini\'alt egy\"utthat\'okkal), \'es az $m$ vektor
e line\'aris programoz\'asi feladat du\'alj\'anak a megold\'asa.

Maga a Kuhn--Tucker t\'etel jellege hasonl\'{\i}t a
Lagrange-f\'ele multiplik\'ator m\'od\-szer\-re. A l\'enyeges
k\"ul\"onbs\'eg a k\'et eredm\'eny k\"oz\"ott az, hogy a
Kuhn--Tucker t\'etel az nemcsak sz\"uks\'eges, hanem
el\'egs\'eges felt\'etel\'et is ad arra, hogy egy vektor
az optim\'aliz\'aci\'os feladat megold\'asa legyen, \'es az
optimum keres\'esekor a tartom\'any hat\'arpontjait is
figyelembe veszi. Ennek viszont az az \'ara, hogy csak
viszonylag speci\'alis probl\'em\'akat lehet ezzel a
m\'odszerrel vizsg\'alni. \'Igy p\'eld\'aul a probl\'em\'aban
szerepl\H{o} k\'enyszer felt\'etelek line\'arisak.

\medskip
Az el\H{o}z\H{o}leg igazolt eredm\'enyek seg\'{\i}tenek az
al\'abbi bizony\'{\i}t\'asban.

\medskip\noindent
{\it A v\'eges \'allapotter\H{u} csatorna optim\'alis
bemenet\'enek a jellemz\'es\'er\H{o}l sz\'ol\'o t\'etel
bi\-zo\-ny\'{\i}\-t\'a\-sa.} Ha egy a a csatorn\'aval
\"osszekapcsolt $\eta$, $\eeta$
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi v\'altoz\'o p\'ar
$p(v_i)=P(\eta=v_i)$ val\'osz\'{\i}n\H{u}s\'egeit az
egy f\"uggv\'eny konk\'avit\'as\'ar\'ol sz\'ol\'o lemm\'aban
szerepl\H{o} $u_i$, a csatorna $p(\vv_j|v_i)$
\'atmenetval\'osz\'{\i}n\H{u}s\'egeit az e lemm\'aban
szerepl\H{o} $p(i,j)$ sz\'amokkal azonos\'{\i}tom, akkor
$q(\vv_j)=P(\eeta=\vv_j)=y_j$ a szint\'en e lemm\'aban
szerepl\H{o} $y_j$ sz\'amokkal. Tov\'abb\'a, ha $\eta$ \'es
$\eeta$ k\'et a csatorn\'aval \"osszekapcsolt
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o, \'es $P(\eta=v_i)=u_i$,
$1\le i\le M$, akkor $I(\eta\wedge\eeta)=F(u_1,\dots,u_M)$ a
lemm\'aban defini\'alt $F(\cdot)$ f\"uggv\'ennyel. Ez\'ert
egy olyan $\eta,\eeta$ a csatorn\'aval \"osszekapcsolt
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o p\'ar eloszl\'as\'anak
a jellemz\'ese, amelyre $I(\eta\wedge\eeta)=C$, ahol $C$ a
csatorna kapacit\'asa, ekvivalens azzal a feladattal, hogy
tal\'aljuk meg a lemm\'aban defini\'alt (konk\'av)
$F(u_1,\dots,u_M)$, $u_i\ge0$, $1\le i\le M$, f\"uggv\'eny
maximum\'at a $\summ_{i=1}^Mu_i=1$ k\'enyszerfelt\'etel
mellett. E feladatban egy folytonos f\"uggv\'eny maximum\'at
keress\"uk egy kompakt halmazon, teh\'at ez a maximum l\'etezik.
Ennek megtal\'al\'as\'ahoz
alkalmazhatjuk a {\it A Kuhn--Tucker t\'etel egy speci\'alis
ese\-te}\/ n\'even megfogalmazott \'all\'{\i}t\'ast, mert a
minket \'erdekl\H{o} feladatban e t\'etel felt\'etelei
teljes\"ulnek. Tov\'abb\'a a (3.2) formul\'aban kisz\'amoltuk a
$\frac{\partial F}{\partial u_k}$ parci\'alis deriv\'altakat. E
k\'eplet \'es az el\H{o}bb eml\'{\i}tett t\'etel azt adj\'ak,
hogy egy a csatorn\'aval \"osszekapcsolt $\eta,\eeta$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o p\'arra akkor \'es csak
akkor teljes\"ul az $I(\eta\wedge\eeta)=C$ rel\'aci\'o, ha az
$\eeta$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o
$q(\vv_j)=P(\eta=v_j)$, $1\le j\le N$, eloszl\'asa teljes\'{\i}ti a
$$
\aligned
\summ_{j=1}^N p(\vv_j|v_k)\log\frac{p(\vv_j|v_k)}{q(\vv_j)}&=D,
\quad\text{ha } p(v_k)>0,\\
\summ_{j=1}^N p(\vv_j|v_k)\log\frac{p(\vv_j|v_k)}{q(\vv_j)}&\le D,
\quad\text{ha } p(v_k)=0
\endaligned \tag3.3
$$
rel\'aci\'ot valamilyen $D<\infty$ sz\'ammal minden $1\le k\le M$
indexre. A $k$-ik egyenletet vagy egyenl\H{o}tlens\'eget megszorozva
$p(v_k)$-val egyenl\H{o}s\'eget kapunk minden $k$ indexre. Ezeket
\"osszeadva azt kapjuk, hogy
$$
\summ_{k=1}^M\summ_{j=1}^N r(v_k,\vv_j)
\log\frac{p(\vv_j|v_k)}{q(\vv_j)}=D,
$$
ahol $r(v_k,\vv_j)=P(\eta=v_k,\eeta=\vv_j)$, $1\le k\le M$,
$1\le j\le N$. Ennek az egyenletnek a baloldala egyenl\H{o}
az $I(\eta\wedge\eeta)=C$ sz\'ammal. Teh\'at egy a csatorn\'aval
\"osszekapcsolt $\eta,\eeta$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o
p\'arra akkor \'es csak akkor \'erv\'enyes az $I(\eta\wedge\eeta)=C$
rel\'aci\'o, ha az $\eeta$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o
$q(\vv_j)=P(\eeta=\vv_j)$, $1\le j\le M$, eloszl\'asa teljes\'{\i}ti
a (3.3) rel\'aci\'ot a $D=C$ sz\'ammal. A t\'etelt bel\'attuk.

\medskip
Megfogalmazok egy lemm\'at, amely seg\'{\i}t a csatorna k\'odol\'asi
t\'etel megford\'{\i}t\'as\'anak a bizony\'{\i}t\'as\'aban.

\medskip\noindent
{\bf Fels\H{o} becsl\'es egy $\lambda$ megk\"ul\"onb\"oztethet\H{o}
ele\-me\-ket tartalmaz\'o halmaz elem\-sz\'a\-m\'a\-r\'ol.}
{\it Legyen adva adva k\'et $V=\{v_1,v_2,\dots\}$ \'es
$\tilde V=\{\vv_1,\vv_2,\dots\}$ v\'eges vagy megsz\'aml\'alhat\'o
halmaz, \'es k\"oz\"ott\"uk egy $p(\vv_j|v_i)$, $v_i\in V$,
$\vv_j\in\VV$,
\'at\-me\-net\-va\-l\'o\-sz\'{\i\-}n\H{u}\-s\'e\-gek\-kel
defini\'alt csatorna. Legyen $\eta$ \'es $\eeta$ k\'et e
csatorn\'aval \"osszekapcsolt val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'o. Vezess\"uk be a $q(\vv_j)=P(\eeta=\vv_j)$,
$\vv_j\in\VV$, val\'osz\'{\i}n\H{u}s\'egeket \'es az
$$
A(v_i)=\left\{\vv_j\colon\; \vv_j\in\VV, \;\;
\frac{p(\vv_j|v_i)}{q(\vv_j)}\ge2^{\vartheta}\right\},
\quad v_i\in V
$$
halmazokat egy alkalmasan v\'alasztott $\vartheta$ param\'eterrel.
Tegy\"uk fel, hogy teljes\"ul a
$$
P(\eeta\in A(v_i)|\eta=v_i)
=\sum_{\vv_j\colon\; p(\vv_j|v_i)\ge2^\vartheta q(\vv_j)}p((\vv_j|v_i)
\le\gamma   \tag3.4
$$
egyenl\H{o}tlens\'eg valamely $\gamma<1$ sz\'ammal minden
$v_i\in V$ pontra. Legyen $\gamma+\lambda<1$ valamely
$\lambda>0$ sz\'ammal. Ekkor tetsz\H{o}leges
$A=\{v_{i_1},\dots,v_{i_N}\}\subset V$ $\lambda$
meg\-k\"u\-l\"on\-b\"oz\-tet\-he\-t\H{o} pontokb\'ol \'all\'o
halmaz $N$ elemsz\'am\'ara
$N\le\frac{2^\vartheta}{1-\lambda-\gamma}$.}

\medskip\noindent
{\it Megjegyz\'es.}\/ A (3.4) formul\'aban szerepl\H{o}
felt\'eteles val\'osz\'{\i}n\H{u}s\'eget az ott fel\'{\i}rt
\"osszegk\'ent defini\'aljuk abban az esetben is, ha
$P(\eta=v_i)=0$.

\medskip\noindent
{\it Bizony\'{\i}t\'as.}\/ Adva egy
$A=\{v_{i_1},\dots,v_{i_N}\}\subset V$ $\lambda$
megk\"ul\"onb\"oztethet\H{o} pontokb\'ol \'all\'o halmaz
v\'alasszunk olyan $B_1\in \VV$,\dots, $B_N\in \VV$ diszjunkt
halmazokat, amelyekre
$P(\eeta\in B_k|\eta=v_{i_k})\ge1-\lambda$ minden $1\le k\le N$
indexre. Ekkor
$$
\align
1-\lambda-\gamma&\le
P(\eeta\in B_k\setminus A(v_{i_k})|\eta=v_{i_k})
=\summ_{\vv_j\colon\; \vv_j\in B_k, \, p(\vv_j|v_{i_k})
\le 2^\vartheta q(\vv_j)} p(\vv_j|v_{i_k}) \\
&\le 2^\vartheta\summ_{\vv_j\colon\; \vv_j\in B_k,\, p(\vv_j|v_{i_k})
\le 2^\vartheta q(\vv_j)} q(\vv_j)
=2^\vartheta P(\eeta\in B_k\setminus A(v_{i_k}))
\endalign
$$
minden $1\le k\le N$ indexre. \"Osszegezve ezeket az
egyenl\H{o}tlens\'egeket, \'es felhaszn\'alva azt, hogy a $B_k$
halmazok diszjunktak azt kapjuk, hogy
$$
2^N(1-\lambda-\gamma)\le 2^\vartheta.
$$
A lemm\'at bel\'attuk.

\medskip\noindent
{\it A csatorna k\'odol\'asi t\'etel megford\'{\i}t\'as\'anak a
bizony\'{\i}t\'asa.}\/ Legyen $\eta'$ \'es $\eeta'$ k\'et olyan
az eml\'ekezet n\'elk\"uli csatorna
\'atmenetval\'osz\'{\i}n\H{u}s\'egeit meghat\'aroz\'o
csatorn\'aval \"osszek\"ot\"ott val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'o, amelyekre $I(\eta'\wedge\eeta')=C$, ahol $C$
ennek a csatorn\'anak a csatorna kapacit\'asa. Legyen
$(\eta_1,\eeta_1),\dots,(\eta_n,\eeta_n)$ az $(\eta',\eeta')$
v\'eleten vektorral azonos eloszl\'as\'u, f\"uggetlen v\'eletlen
vektorok sorozata. Vezess\"uk be az
$\eta=(\eta_1,\dots,\eta_n)$ \'es $\eeta=(\eeta_1,\dots,\eeta_n)$
jel\"ol\'est. A csatorna k\'odol\'asi t\'etel
bizony\'{\i}t\'as\'aban a {\it fels\H{o} becsl\'es egy $\lambda$
meg\-k\"u\-l\"on\-b\"oz\-tet\-he\-t\H{o} ele\-me\-ket tartalmaz\'o
halmaz elem\-sz\'a\-m\'a\-r\'ol} eredm\'eny\'et fogom alkalmazni az
$\eta,\eeta$ va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi v\'altoz\'o
p\'arra $\vartheta=Cn+K\frac{\sqrt n}{\sqrt{1-\lambda}}$ param\'eterrel,
ahol $K$ egy a csatorn\'at\'ol f\"ugg\H{o} el\'eg nagy sz\'am. Erre
jogunk van, mert az $\eta$ \'es $\eeta$ val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'ok \"ossze vannak kapcsolva az eml\'ekezet n\'elk\"uli
csatorn\'aval.

Ezen becsl\'es alapj\'an a csatorna k\'odol\'asi t\'etel
megford\'{\i}t\'as\'anak a bizony\'{\i}t\'as\'ahoz el\'eg
megmutatni, hogy
$$
P((\eeta_1,\dots,\eeta_n)\in A((v_{i_1},\dots,v_{i_n}))|
\eta_1=v_{i_1},\dots,\eta_n=v_{i_n})
\le\frac{1-\lambda}2
$$
minden $(v_{i_1},\dots,v_{i_n})\in V^n$ vektorra, ahol
$$
\align
&A((v_{i_1},\dots,v_{i_n})) \\
&=\left\{(\vv_{j_1},\dots,\vv_{j_n})
\colon\; (\vv_{j_1},\dots,\vv_{j_n})\in\VV^n, \;
\frac{\prodd_{k=1}^n p(\vv_{j_k}|v_{i_k})}
{\prodd_{k=1}^n q(\vv_{j_k})}
\ge2^{Cn+K\sqrt n/\sqrt{1-\lambda}}\right\},
\endalign
$$
egy el\'eg nagy $K>0$ konstanssal, mely k\'epletben
$p(\vv_j|v_i)$ jel\"oli az eml\'ekezet n\'elk\"uli
csatorn\'at meghat\'aroz\'o  csatorna
\'at\-me\-net\-va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-ge\-it,
\'es $q(\vv_j)=P(\eeta'=\vv_j)$. Ugyan\-is. ha ez az
egyenl\H{o}tlens\'eg igaz, akkor az el\H{o}bb
eml\'{\i}tett fels\H{o} becsl\'es
$\vartheta=Cn+K\frac{\sqrt n}{\sqrt{1-\lambda}}$ \'es
$\gamma=\frac{1-\lambda}2$ szereposzt\'assal
a t\'etelben megfogalmazott eredm\'enyt szolg\'altatja.

\'At\'{\i}rva az $A((v_{i_1},\dots,v_{i_n}))$ halmaz
definici\'oj\'at \'ugy, hogy a benne szerepl\H{o}
egyen\-l\H{o}t\-len\-s\'eg\-ben a baloldal logaritmusa nagyobb
vagy egyenl\H{o}, mint a jobboldal lo\-ga\-rit\-mu\-sa, \'es
figyelembe v\'eve, hogy a bizony\'{\i}tani k\'{\i}v\'ant
egyenl\H{o}tlens\'egben
tekintett $(\eeta_1,\dots,\eeta_n)$ vektornak mi a
fel\-t\'e\-te\-les el\-osz\-l\'a\-sa az $\eta_1=v_{i_1}$,\dots,
$\eta_n=v_{i_n}$ felt\'etel
mellett a bizony\'{\i}tand\'o \'all\'{\i}t\'asnak megadhatjuk a
k\"ovetkez\H{o} ekvivalens \'atfogalmaz\'as\'at.
R\"ogz\'{\i}ts\"unk valamilyen $v_{i_1}\in V$,\dots, $v_{i_n}\in V$
pontokat, \'es vezess\"uk be a $\zeta_1(v_{i_1})$,\dots,
$\zeta_n(v_{i_n})$ f\"uggetlen val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'okat, \'ugy hogy a $\zeta_k(v_{i_k})$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o eloszl\'as\'at
a $P(\zeta_k(v_{i_k})=\vv_j)=p(\vv_j|v_{i_k})$,
$\vv_j\in\VV$, k\'eplet adja meg minden $1\le k\le n$ indexre.
Ezzel a jel\"ol\'essel a  bizony\'{\i}tani k\'{\i}v\'ant
\'all\'{\i}t\'as eqvivalens a
k\"ovetkez\H{o} egyenl\H{o}tlens\'eggel.
$$
P\(\summ_{i=1}^n \log\frac
{p(\zeta_k(v_{i_k})|v_{i_k})}{q(\zeta_k(v_{i_k}))}
\ge Cn+\frac{K\sqrt n}{\sqrt{1-\lambda}}\)
\le \frac{1-\lambda}2 \tag3.5
$$
minden $(v_{i_1},\dots,v_{i_n})\in V^n$ vektorra.

Vegy\"uk \'eszre, hogy a (3.5) formula szumm\'aj\'aban
szerepl\H{o} tagok v\'arhat\'o \'ert\'eke
$$
E\log\frac {p(\zeta_k(v_{i_k})|v_{i_k})}{q(\zeta_k(v_{i_k}))}=
\sum_{j=1}^n p(\vv_j|v_{i_k})\log \frac{p(\vv_j|v_{i_k})}{q(\vv_j)}
$$
Tov\'abb\'a, mivel $I(\eta'\wedge\eeta')=C$, ahol $C$ az eml\'ekezet
n\'elk\"uli csatorn\'at meghat\'aroz\'o csatorna csatorna
kapacit\'asa, ezt az egyenletet \"osszehasonl\'{\i}tva a
{\it lemma az eml\'ekezet n\'elk\"uli csatorna kapacit\'as\'ar\'ol}
eredm\'eny\'eben szerepl\H{o} (3.1) k\'eplettel azt kapjuk,
hogy a tekintett v\'arhat\'o \'ert\'ek kisebb vagy egyenl\H{o},
mint $C$, \'es a $C$ sz\'ammal egyenl\H{o} azon
$v_{i_k}\in V$ pontokra, amelyekre
$P(\eta'=v_{i_k})>0$. Tov\'abb\'a l\'etezik olyan $D<\infty$
konstans, amelyre
$$
E\(\log\frac {p(\zeta_k(v_{i_k})|v_{i_k})}
{q(\zeta_k(v_{i_k}))}\)^2
=\sum_{j=1}^n p(\vv_j|v_{i_k})\(\log \frac{p(\vv_j|v_{i_k})}{q(\vv_j)}\)^2
\le D \quad \text{minden $v_i\in V$ pontra},
$$
mert ez a kifejez\'esben egy v\'eges \"osszeg szerepel,
amelynek mindegyik tagja v\'eges. (Tud\-juk, hogy ha $p(\vv_j|v_i)>0$,
akkor $q(\vv_j)>0$, \'es csak v\'eges sok k\"ul\"onb\"oz\H{o}
\"osszeget kell tekinten\"unk.)

A most bizony\'{\i}tott \"osszef\"ugg\'esek \'es a Csebisev
egyenl\H{o}tlens\'eg a k\"ovetkez\H{o} becsl\'est adj\'ak
(3.5) k\'epletben szerepl\H{o} f\"uggetlen
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok \"osszeg\'enek az
eloszl\'as\'ara.
$$
\align
&P\(\summ_{i=1}^n \log\frac
{p(\zeta_k(v_{i_k})|v_{i_k})}{q(\zeta_k(v_{i_k}))}
\ge Cn+\frac{K\sqrt n}{\sqrt{1-\lambda}}\) \\
&\qquad \le P\(\summ_{i=1}^n
\(\log\frac {p(\zeta_k(v_{i_k})|v_{i_k})}{q(\zeta_k(v_{i_k}))}
-E\log\frac {p(\zeta_k(v_{i_k})|v_{i_k})}{q(\zeta_k(v_{i_k}))}\)
\ge \frac{K\sqrt n}{\sqrt{1-\lambda}}\) \\
&\qquad\le \frac{Dn(1-\lambda)}{K^2n}
\le \frac{1-\lambda}2,
\endalign
$$
ha a $K$ konstanst el\'eg nagynak ($K^2>2D$) v\'alasztjuk. \'Igy a
(3.5)~formul\'at, \'es ezzel a t\'etelt is bebizony\'{\i}tottuk.

\medskip
\'Erdemes lehet heurisztikus szinten \'attekinteni, hogy milyen
gondolatokra \'ep\"ul a csatorna k\'odol\'asi t\'etelnek illetve e
t\'etel megford\'{\i}t\'as\'anak a bizony\'{\i}t\'asa.

Legyen $(\eta,\eeta)$ olyan a csatorn\'aval \"osszekapcsolt
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o p\'art, amely\-re
$I(\eta\wedge\eeta)=C$, ahol $C$ a csatorna kapacit\'asa,
vagy ha ilyen p\'ar nincs akkor az $I(\eta\wedge\eeta)$ sz\'am
nagyon k\"ozel van ehhez a $C$ \'ert\'ekhez. Annak
bizony\'{\i}t\'asa, hogy alkalmas felt\'etelek mellett mind
a k\'et t\'etel \'erv\'enyes azon \'all\'{\i}t\'as igazol\'as\'an
alapul, hogy egy $n$ hossz\'us\'ag\'u eml\'ekezet n\'elk\"uli
csatorn\'aban az
$$
A(v)=\left\{\vv=(\vv_{j_1},\dots,\vv_{j_n})\in\VV_n\colon\;
\prodd_{k=1}^n\frac{p(\vv_{j_k}|v_{i_k})}{q(\vv_{j_k})}
\sim 2^{Cn}\right\}
$$
halmaz teljes\'{\i}ti a
$P((\eeta_1,\dots,\eeta_n)\in A(v)|(\eta_1,\dots,\eta_n)=v)\sim1$
rel\'aci\'ot tipikus  $v=(v_{i_1},\dots,v_{i_n})\in V^n$ pontokban,
ahol $(\eta_1,\eeta_1)$,\dots, $(\eta_n,\eeta_n)$ az $(\eta,\eeta)$
p\'arral azonos el\-osz\-l\'a\-s\'u, f\"uggetlen v\'eletlen vektorok
sorozata, \'es $q(\vv_j)=P(\eeta=\vv_j)$. Az el\H{o}z\H{o}
mondatban haszn\'alt `tipikus' kifejez\'es els\H{o}
k\"ozel\'{\i}t\'esben azt jelenti, hogy a rel\'aci\'o igaz a
$v=(v_{i_1},\dots,v_{i_n})\in V^n$ vektorok majdnem egy
val\'osz\'{\i}n\H{u}s\'egi halmaz\'ara azon
val\'osz\'{\i}n\H{u}s\'egi m\'ert\'ek szerint, amelyet az
$(\eta_1,\dots,\eta_n)$ vektor eloszl\'asa hat\'aroz meg. A
bizony\'{\i}t\'as r\'eszletesebb vizsg\'alata sor\'an a `tipikus'
sz\'o jelent\'es\'et pontos\'{\i}tani kell. \'Erdemes
meg\-je\-gyez\-ni, hogy az $A(v)$ halmazra fel\'{\i}rt rel\'aci\'o
\'ugy is \'{\i}rhat\'o, hogy
$\summ_{k=1}^n\log \frac{p(\eeta_k|v_{i_k})}{q(\eeta_k)}\sim Cn$
majdnem val\'osz\'{\i}n\H{u}s\'eggel ha $(\eeta_1,\dots,\eeta_n)$
eloszl\'as\'at a
$P(\eeta_1=\vv_{j_1},\dots,\eeta_n=\vv_{j_n})
=\prodd_{k=1}^n p(\vv_{j_k}|v_{i_k})$ k\'eplet adja meg.
Tov\'abb\'a $E\log\frac
{p(\eeta_k|\eta_k)}{q(\eeta_k)}=I(\eta_k\wedge\eeta_k)=C$. Ez\'ert
az el\H{o}bb fel\'{\i}rt rel\'aci\'o olyan t\'enyt fejez ki, hogy
f\"uggetlen val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok \"osszege k\"ozel
van az \"osszeg v\'arhat\'o \'ert\'ek\'ehez.

Az $A(v)$ halmazra megfogalmazott tulajdons\'ag egyik
k\"ovetkezm\'enye az, hogy egy tipikus $v\in V^n$ pontra
$$
\align
P((\eeta_1,\dots,\eeta_n))\in A(v))&=\sum_{\vv\in A(v)} q(\vv)
=\sum_{\vv\in A(v)} q(\vv)\frac{p(\vv|v)}{q(\vv)}
\frac{q(\vv)}{p(\vv|v)}\\
&\sim2^{-Cn}\sum_{\vv\in A(v)} q(\vv)\frac{p(\vv|v)}{q(\vv)}
=2^{-Cn}\sum_{\vv\in A(v)} p(\vv|v)\sim 2^{-Cn},
\endalign
$$
ahol $q(\vv)=\prodd_{k=1}^n q(\vv_{j_k})$, \'es
$p(\vv|v)=\prodd_{k=1}^n\frac{p(\vv_{j_k}|v_{i_k})}{q(\vv_{j_k}}$.
Ha egy olyan $B(v)\subset\VV^n$ halmazt keres\"unk egy $v\in V^n$
ponthoz, amelyre
$P((\eeta_1,\dots,\eeta_n)\in B(v)|(\eta_1,\dots,\eta_n)=v)
\ge1-\lambda$
valamely kis $\lambda>0$ sz\'amra, akkor a $B(v)$ halmaz az
el\H{o}bb defini\'alt $A(v)$ halmaz kis m\'odos\'{\i}t\'asa a
$P(\cdot|(\eta_1,\dots,\eta_n)=v)$ m\'ert\'ek szerint. S\H{o}t,
n\'eh\'any sz\'amunkra nem l\'enyeges felt\'etel teljes\"ul\'ese
eset\'en az is igaz, hogy az $A(v)$ halmazhoz hasonl\'oan a $B(v)$
halmaz  teljes\'{\i}ti a
$P((\eeta_1,\dots,\eeta_n))\in B(v))\sim 2^{-nC}$ rel\'aci\'ot.
Ez\'ert, ha olyan $(v^{(1)},B^{(1)})$,\dots, $(v^{(N)},B^{(N)})$,
$v^{(k)}\in V^n$, $B^{(k)}\subset\VV^n$, minden $1\le k\le N$ indexre,
p\'arokat keres\"unk, amelyekre
$P((\eeta_1,\dots,\eeta_n)\in B^{(k)}|(\eta_1,\dots,\eta_n)=v^{(k)})>
1-\lambda$
minden $k$ indexre, \'es a $B^{(k)}$ halmazok diszjunktak, akkor
legfeljebb $N=2^{Cn(1+o(1)})$ ilyen p\'art v\'alaszthatunk, \'es ezt
mondja ki a csatorna k\'odol\'asi t\'etel megford\'{\i}t\'asa. A
csatorna k\'odol\'asi t\'etel viszont az \'all\'{\i}tja, hogy ennyi
$(v^{(k)},B^{(k)})$ p\'art ki is lehet v\'alasztani.

Term\'eszetesen, az el\H{o}bb v\'azolt gondolatmenetek pontos
kidolgoz\'asa az \'ervel\'es finom\'{\i}t\'as\'at ig\'enyli
t\"obb ponton. Ezek r\'eszleteit azonban itt nem t\'argyalom,
mert a m\'ar le\'{\i}rt bizony\'{\i}t\'as tartalmazza azokat.
Csak egy figyelemre m\'elt\'o r\'eszletet eml\'{\i}tek. A
csatorna k\'odol\'asi t\'etel megford\'{\i}t\'as\'aban az $A(v)$
halmazokra fel\'{\i}rt aszimptotikus rel\'aci\'ot nem elegend\H{o}
csak `tipikus' $v\in V^n$ pontokra bel\'atni, azokat minden
$v\in V^n$ pontra igazolni kell. A bizony\'{\i}t\'as f\H{o}
technikai neh\'ezs\'egei emiatt jelennek meg.

\vfill\eject
%\medskip
\noindent
{\bf 4. Kis hib\'aj\'u \'es viszonylag gyors inform\'aci\'o
tov\'abb\'{\i}t\'as a forr\'as \'es csatorna k\'o\-do\-l\'a\-si
t\'etel se\-g\'{\i}t\-s\'e\-g\'e\-vel.}

\medskip\noindent
A k\"ovetkez\H{o} probl\'em\'aval fogunk foglalkozni. Legyen
adva egy inform\'aci\'o forr\'as, azaz legyen adva egy
\'ert\'ekeit egy v\'eges vagy megsz\'aml\'alhat\'oan
v\'egtelen $X=\{x_1,x_2\dots\}$ hal\-ma\-zon felvev\H{o}
$\xi$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o, \'es legyen
$\xi_1,\xi_2,\dots$ f\"uggetlen, \'es a $\xi$
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi v\'altoz\'oval azonos
eloszl\'as\'u val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok
sorozata, amit inform\'aci\'o forr\'asnak fogunk nevezni.
Legyen ezenk\'{\i}v\"ul adva egy eml\'ekezet n\'elk\"uli
csatorna, amelyet egy olyan
csatorna hat\'aroz meg, amely valamely $V=\{v_1,v_2,\dots]$
bemeneti jelek halmaz\'at \'atviszi kimeneti jelek valamely
$\VV=\{\vv_1,\vv_2,\dots\}$ halmaz\'aba, \'es $p(\vv_j|v_i)$
annak a val\'osz\'{\i}n\H{u}s\'ege, hogy a csatorna
a $v_i$ bemeneti jelet a $\vv_j$ kimeneti jelbe viszi \'at. A
forr\'as jeleit akarjuk k\"oz\"olni a felhaszn\'al\'oval \'ugy,
hogy az (eml\'ekezet n\'elk\"uli) csatorn\'an leadjuk bemeneti
jelek egy sorozat\'at, aminek hat\'as\'ara a felhaszn\'al\'o
kimeneti jelek valamilyen sorozat\'at kapja, \'es ennek
alapj\'an pr\'ob\'alja rekonstru\'alni a forr\'as
$\xi_1,\xi_2,\dots$ \'ert\'ekeit.

Tegy\"uk fel, hogy az inform\'aci\'o forr\'as $\xi_1,\xi_2,\dots$ 
jelei egys\'egnyi sebess\'eggel \'erkeznek, \'es mi is egys\'egnyi
sebess\'eggel tudjuk tov\'abb\'{\i}tani a $v_i$ jeleket a
csatorn\'an kereszt\"ul. Olyan m\'odszert
sze\-ret\-n\'enk kidolgozni, amely lehet\H{o}v\'e teszi, hogy
a felhaszn\'al\'o a forr\'as minden jel\'et $\e$-n\'al kisebb
hib\'aval rekonstru\'alni tudja, ahol $\e>0$ egy el\H{o}re
r\"ogz\'{\i}tett nagyon kicsi sz\'am. Emellett azt szeretn\'enk,
hogy ugyanolyan sebess\'eggel k\"ozvet\'{\i}ts\"uk az
inform\'aci\'ot a csatorn\'an kereszt\"ul, mint ahogyan az
\'erkezik. Teh\'at b\'armilyen nagy $n$ sz\'amra a
felhaszn\'al\'o az $n$-ik id\H{o}pontban ismerje a leadott
$\xi_j$ jeleket minden $1\le j\le n-K$ indexre, ahol $K$ egy
r\"ogz\'{\i}tett, az $n$ id\H{o}pontt\'ol f\"uggetlen sz\'am.

Ismertetek egy term\'eszetes elj\'ar\'ast, amely ezt
lehet\H{o}v\'e teszi akkor, ha a csatorna kapacit\'asa nagyobb,
mint a forr\'as entr\'opi\'aja. De nem teszi lehet\H{o}v\'e akkor,
ha ez a kapacit\'as kisebb, mint a forr\'as entr\'opi\'aja. A
konstrukci\'o, illetve a konstrukci\'o helyess\'eg\'enek
igazol\'asa a forr\'as \'es csatorna k\'odol\'as\'ar\'ol
bizony\'{\i}tott eredm\'enyeken alapul. Azzal az esettel, amikor a
csatorna kapacit\'asa egyenl\H{o} a forr\'as kapacit\'as\'aval nem
foglalkozom, mert ennek a t\'uls\'agosan speci\'alis, \'es ez\'ert
kev\'esb\'e \'erdekes esetnek a t\'argyal\'asa a kor\'abban
bizony\'{\i}tott eredm\'enyek egy \'elesebb v\'altozat\'anak az
igazol\'as\'at ig\'enyeln\'e.

A k\"ovetkez\H{o} elj\'ar\'ast fogjuk alkalmazni. V\'alasztunk
egy alkalmas, el\'eg nagy, de fix $n_0$ sz\'amot, \'es a
$\xi_{ln_0+1},\dots,\xi_{(l+1)n_0}$, $l=0,1,\dots$, blokkokban
megjelen\H{o} sorozatokat fogjuk ismertetni egym\'as ut\'an a
felhaszn\'al\'oval. Megel\'egsz\"unk azzal, hogy nem az \"osszes
blokkot, hanem csak e blokkok egy majdnem 1
val\'osz\'{\i}n\H{u}s\'egi r\'esz\'et fogjuk helyesen ismertetni.
Ennek \'erdek\'eben v\'alasztunk egy alkalmas $N=N(n_0)$
sz\'amot, kiv\'alasztunk a $V^{n_0}$ halmaz, azaz
a $V$ halmaz elemeit tartalmaz\'o $n_0$ hossz\'us\'ag\'u
$(v_{i_1},\dots,v_{i_{n_0}})$ sorozatok ter\'eben egy
megfelel\H{o} $A=A(n_0)=\{v^{(n_0)}(l)
=(v_1(l),\dots,v_{n_0}(l)),\;1\le l\le N(n_0)\}\subset
V^{n_0}$ $N(n_0)$ elem\H{u} halmazt, valamint mindegyik
$v^{(n_0)}(l)\in A(n_0)$ vektorhoz egy $B_l\subset \VV^{n_0}$
halmazt \'ugy, hogy a $B_l$, $1\le l\le N(n_0)$, halmazok a
$\VV^{n_0}$ halmaz egy partici\'oj\'at adj\'ak. Defini\'alunk
egy $f\colon X^{n_0}\to A(n_0)$ f\"uggv\'enyt, amelyet k\'odol\'o,
\'es egy $g\colon A(n_0)\to X^{n_0}$ f\"uggv\'enyt, amelyet
dek\'odol\'o f\"uggv\'enynek fogunk nevezni. Amikor megjelenik
a teljes $\xi_{ln_0+1},\dots,\xi_{(l+1)n_0}$ blokk, akkor
behelyettes\'{\i}tj\"uk azt az $f(\cdot)$ k\'odf\"uggv\'enybe,
azaz tekintj\"uk a (v\'eletlen)
$f(\xi_{ln_0+1},\dots,\xi_{(l+1)n_0})\in A(n_0)$ sorozatot,
\'es ezt elk\"uldj\"uk a felhaszn\'al\'onak a csatorn\'an
kereszt\"ul. \H{O} kap egy (v\'eletlen)
$(\vv_{j_1},\dots,\vv_{j_{n_0}})\in\VV^{n_0}$ sorozatot, \'es
ennek alapj\'an a k\"ovetkez\H{o} m\'odon `dek\'odol', azaz
k\"ovetkeztet az eredeti
$\xi_{ln_0+1},\dots,\xi_{(l+1)n_0}$ blokk \'ert\'ek\'ere.
Kiv\'alasztja azt a $B_l\in\VV^{n_0}$ halmazt, amelyre
$(\vv_{j_1},\dots,\vv_{j_{n_0}})\in B_l$, \'es veszi a neki
megfelel\H{o}
$v^{(n_0)}_l=(v_{i_1}(l),\dots,v_{i_{n_0}}(l))\in A(n_0)$
sorozatot. Erre alkalmazza a $g(\cdot)$ dek\'odol\'o f\"uggv\'enyt,
azaz veszi a $g(v_{i_1}(l),\dots,v_{i_{n_0}}(l))\in X^{n_0}$
sorozatot, \'es ezt v\'alasztja a
$\xi_{ln_0+1},\dots,\xi_{(l+1)n_0}$ sorozatnak. Megmutatom, hogy
ha a csatorna $C$ kapacit\'asa nagyobb, mint a forr\'as
$H(\xi)$ entr\'opi\'aja, akkor az $n_0$
blokkhossz, az $f(\cdot)$ k\'odol\'o \'es $g(\cdot)$ dek\'odol\'o
f\"uggv\'enyek, majd az $A(n_0)$ halmaz $N(n_0)$ elemsz\'am\'anak,
illetve mag\'anak az $A(n_0)$ halmaznak \'es a hozz\'a tartoz\'o
$B_l\subset \VV^{n_0})$, $1\le l\le N(n_0)$, halmazok alkalmas
megv\'alaszt\'as\'aval el\'erhet\H{o}, hogy a felhaszn\'al\'o
ezen elj\'ar\'as seg\'{\i}ts\'eg\'evel legal\'abb $1-\e$
val\'osz\'{\i}n\H{u}s\'eggel a forr\'as \'altal leadott
$\xi_{ln_0+1},\dots,\xi_{(l+1)n_0}$ sorozatot v\'alassza,
b\'armilyen kicsi is legyen az el\H{o}\'{\i}rt $\e>0$ sz\'am.

Ha a csatorna kapacit\'asa nagyobb, mint a forr\'as
entr\'opi\'aja, akkor l\'etezik olyan $\delta>0$ sz\'am, amelyre
$C>H(\xi)+2\delta$. V\'alasszunk egy ilyen $\delta>0$ sz\'amot.
Ekkor a csatorna k\'odol\'asi t\'etel alapj\'an van olyan
$n_0=n_0(\e,\delta)$ k\"usz\"obindex, hogy minden $n\ge n_0$
indexre l\'etezik egy
$2^{(C-\delta)n}\ge N(n)\ge 2^{(H(\xi)+\delta)n}$
elemsz\'am\'u $A(n)\subset V^{n}$ halmaz, valamint a $\VV^{n}$
halmaznak egy olyan $B_1,\dots,B_{N(n)}$ partici\'oja, amely
teljes\'{\i}ti a
$\summ_{\vv^{(n)}\in B_l}p(\vv^{(n)}|(v^{(n)}(l))\ge1-\frac\e2$
egyenl\H{o}tlens\'eget a
$v^{(n)}(l)=(v_{i_1}(l),\dots,v_{i_n}(l))\in A(n)$ vektorra
\'es a neki megfelel\H{o} $B_l\subset \VV^n$ halmazra minden
$1\le l\le N(n_0)$ indexre, ahol
$p(\vv^{(n)}|(v^{(n)}(l))$ az em\'ekezet n\'elk\"uli csatorna
\'atmenetval\'osz\'{\i}n\H{u}s\'ege, azaz
$p(\vv^{(n)}|(v^{(n)}(l))=\prodd_{k=1}^n p(\vv_{j_k}|v_{i_k}(l))$
a $\vv^{(n)}=(\vv_{j_1},\dots,\vv_{j_n})$ \'es
$v^{(n)}(l)=(v_{i_1}(l),\dots,v_{i_n}(l))$ jel\"ol\'essel.
Tov\'abb\'a, mivel $N(n)\ge 2^{(H(\xi)+\delta)n}$,
 a m\'asodik fejezetben bizony\'{\i}tott {\it f\"ug\-get\-len,
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 de\-k\'o\-do\-l\'a\-s\'a\-r\'ol}
sz\'ol\'o t\'etel alapj\'an l\'etezik olyan
$f\colon X^n\to A(n)$, k\'odol\'o \'es
$g\colon A(n)\to X^n$ dek\'odol\'o f\"uggv\'eny, amelyre
$P(g(f(\xi_1,\dots,\xi_n))=(\xi_1,\dots,\xi_n))\ge 1-\frac\e2$,
ha $n\ge n_0(\e,\delta)$ egy eset\-leg nagyobb $n_0$
k\"usz\"obindexszel.

V\'alasszunk egy olyan $n_0$ indexet, amelyre
l\'etezik a k\'{\i}v\'ant tulajdons\'ag\'u $A(n_0)\subset V^{n_0}$
halmaz a $\VV^{n_0}$ halmaz hozz\'atartoz\'o
$B_1,\dots,B_{N(n_0)}$ partici\'oj\'aval egy\"utt, valamint
l\'etezik a  meg\-fe\-le\-l\H{o} tulajdons\'ag\'u $f$ k\'odol\'o
\'es $g$ dek\'odol\'o f\"uggv\'eny is. Ezzel a v\'alaszt\'assal
az el\H{o}bb  ismertetett dek\'odol\'asi elj\'ar\'as hib\'aja
kisebb, mint $\e$. Val\'oban, tekints\"uk az inform\'aci\'o
forr\'as \'altal leadott $\xi_{ln_0+1},\dots,\xi_{(l+1)n_0}$
sorozat $f(\xi_{ln_0+1},\dots,\xi_{(l+1)n_0})=v^{n_0}_l\in A(n_0)$
k\'odj\'at. A felhaszn\'al\'o legal\'abb $1-\frac\e2$
 val\'osz\'{\i}n\H{u}s\'eggel azonos\'{\i}tani fogja ezt a jelet
a csatorn\'an kereszt\"ul kapott jel seg\'{\i}ts\'eg\'evel.
Ezut\'an a $g(\cdot)$ dek\'odol\'o f\"uggv\'eny
seg\'{\i}ts\'eg\'evel v\'egzett dek\'odol\'as is csak $\frac\e2$
val\'osz\'{\i}n\H{u}s\'eggel fogja d\"ont\'ese hib\'aj\'at
n\"ovelni.

\medskip
Az \'all\'{\i}t\'as megford\'{\i}t\'as\'at, azt, hogy ha $C<H(\xi)$
akkor nem lehets\'eges az adott m\'odon kis hib\'aj\'u, gyors
adat\'atvitelt bizos\'{\i}tani csak abban az esetben
bizony\'{\i}tom, ha a tekintett csatorna v\'eges
\'allapotter\H{u}, mert csak ebben az esetben bizony\'{\i}tottam
a csatorna k\'odol\'asi t\'etel megford\'{\i}t\'as\'at, amely fontos
szerepet j\'atszik ezen \'all\'{\i}t\'as igazol\'as\'aban.

Az el\H{o}z\H{o} eredm\'eny megford\'{\i}t\'as\'anak tekinthet\H{o}
\'all\'{\i}t\'as megfogalmaz\'as\'anak \'es bizony\'{\i}t\'as\'anak
\'erdek\'eben le\'{\i}rok egy inform\'aci\'o tov\'abb\'{\i}t\'asi
modellt, \'es megfogalmazok r\'a egy \'all\'{\i}t\'ast. Ez a modell
l\'enyeg\'eben megegyezik az el\H{o}bb t\'argyalt modellel, csak
le\'{\i}r\'as\'aban teszek apr\'o m\'odos\'{\i}t\'ast. A l\'enyeges
k\"ul\"onbs\'eg az, hogy itt nem vezetem be a $g$ dek\'odol\'o
f\"uggv\'enyt, \'es az egyszer\H{u}bb jel\"ol\'es \'erdek\'eben
csak egyetlen blokkot tekintek.

Tekints\"uk az inform\'aci\'o forr\'as \'altal k\"uld\"ott
$n$ hossz\'us\'ag\'u $\xi_1,\dots,\xi_n$ sorozat egy
$f\colon X^n\to V^n$, k\'odf\"uggv\'eny\'et a
$v_i\in V$ csatorna bemeneti jelekb\H{o}l \'all\'o $n$
hossz\'us\'ag\'u sorozatok $V^n$  halmaz\'ara \'es a csatorna 
$\VV$ kimeneti
jeleinek $n$ hossz\'us\'ag\'u sorozataib\'ol \'all\'o $\VV^n$
halmaznak egy $N=N(n)$ elem\H{u} $B_1,\dots,B_N$ partici\'oj\'at.
Ezenk\'{\i}v\"ul rendelj\"uk hozz\'a e partici\'o mindegyik
$B_l$, $1\le l\le N$, elem\'ehez az $X^n$ halmaz valamely
$x^{(n)}(l)=(x_{i_1}(l),\dots,x_{i_n}(l))\in X^n$ elem\'et,
\'ugy hogy $x^{(n)}(l)\neq x^{(n)}(l')$, ha $l\neq l'$.
Al\-kal\-maz\-zuk a k\"ovetkez\H{o} inform\'aci\'o
tov\'abb\'{\i}t\'asi \'es dek\'odol\'asi elj\'ar\'ast. Ha
meg\'erkezik a forr\'asb\'ol a $\xi_1,\dots,\xi_n$ sorozat,
akkor al\-kal\-maz\-zuk r\'a az $f$ k\'odf\"uggv\'enyt. \'Igy
egy $f(\xi_1,\dots,\xi_n)=(v_{i_1},\dots,v_{i_n})\in V^n$
sorozatot kapunk. Ezt \'atengedj\"uk az eml\'ekezet n\'elk\"uli
csatorn\'an \'es kapunk egy $(\vv_{j_1},\dots,\vv_{j_n})\in\VV^n$
sorozatot, amelyet tartalmaz a $B_1,\dots,B_N$ partici\'o egyik
eleme. Ha $(\vv_{j_1},\dots,\vv_{j_n})\in B_l$, $1\le l\le N$,
akkor legyen a dek\'odolt sorozat a $B_l$ halmaznak megfeleltetett
$x^{(n)}=(x_{i_1}(l),\dots,x_{i_n}(l))$ sorozat.

Jel\"olj\"uk az \'{\i}gy kapott `dek\'odol\'o' sorozatot
$(\zeta_1,\dots,\zeta_n)$-nel. Azt \'all\'{\i}tom, hogy ha
$H(\xi)>C$, akkor minden $\e>0$ sz\'amhoz l\'etezik olyan
$n_0=n_0(\e)$ k\"usz\"obindex, hogy ha az el\H{o}bb le\'{\i}rt
elj\'ar\'ast alkalmazzuk $n\ge n_0$ hossz\'us\'ag\'u sorozatokra, 
akkor b\'arhogy is v\'alasztjuk az $f(\cdot)$ k\'odol\'o 
f\"uggv\'enyt, a $\VV^n$ halmaz $B_1,\dots,B_N$ partici\'oj\'at 
\'es b\'arhogy is adjuk meg a $B_l$ halmaz elemeinek a
$B_l\to x^{(n)}(l)=(x_{i_1}(l),\dots,x_{i_n}(l))$ 
hozz\'arendel\'es\'et az $X^n$ halmaz valamely elem\'ehez, a
dek\'odol\'as legfeljebb $\e$ val\'osz\'{\i}n\H{u}s\'eggel ad 
helyes eredm\'enyt, azaz
$P((\xi_1,\dots,\xi_n)=(\zeta_1,\dots,\zeta_n))\le\e$. Ez az
\'all\'{\i}t\'as csak viszonylag nagy $n\ge n_0(\e)$ indexekre
\'erv\'enyes. Ez\'ert a probl\'ema teljes megold\'as\'ahoz j\'o
becsl\'est kell adni a megfelel\H{o} probl\'em\'ara kis $n$
indexek eset\'eben is. De az ut\'obbi feladat megold\'asa a
nagy $n$ indexekre m\'ar bebizony\'{\i}tott eredm\'eny
seg\'{\i}ts\'eg\'evel viszonylag egyszer\H{u}.

A bizony\'{\i}t\'ast indirekt m\'odon v\'egzem el. Felt\'etelezem,
hogy nagy $n$ indexekre is l\'etezik olyan $f(\cdot)$
k\'odf\"uggv\'eny, a $\VV^n$ halmaz olyan $B_1,\dots,B_N$
partici\'oja, illetve e partici\'oknak olyan
$B_l\to x^{(n)}(l)=(x_{i_1}(l),\dots,x_{i_n}(l))$
megfeleltet\'ese, amelyre a fent le\'{\i}rt m\'odon
konstru\'alt $(\zeta_1,\dots,\zeta_n)$ sorozatra
$P((\xi_1,\dots,\xi_n)=(\zeta_1,\dots,\zeta_n))\ge\e$.
Mivel $H(\xi)>C$, v\'alaszthatunk olyan $\delta>0$ sz\'amot,
amelyre $H(\xi)(1-\delta)^4>C$. El\H{o}sz\"or azt mutatom meg,
hogy feltev\'es\"unkb\H{o}l k\"ovetkezik, hogy ha
$n\ge n_0= n_0(\e,\delta)$ valamely $n_0$ k\"usz\"obindexszel
akkor l\'etezik $N_1=N_1(n)\ge 2^{(1-\delta)^2H(\xi)n}$ darab
olyan $x^{(n)}(l)=(x_{i_1}(l),\dots,x_{i_n}(l))\in X^n$
sorozat, amelyekre
$$
P((\xi_1,\dots,\xi_n)=(\zeta_1,\dots,\zeta_n)
|(\xi_1,\dots,\xi_n)=x^{(n)}(l))\ge\frac\e2
\quad \text{minden $1\le l\le N_1$ indexre.}
$$
Ezt megmutand\'o vegy\"uk
\'eszre, hogy ha defini\'aljuk a
$$
\aligned
B=B(n)&=\{(x_{i_1},\dots,x_{i_n})\colon\;
(x_{i_1},\dots,x_{i_n})\in X^n,\\
&\qquad P((\xi_1,\dots,\xi_n)=(\zeta_1,\dots,\zeta_n)
|(\xi_1,\dots,\xi_n)=(x_{i_1},\dots,x_{i_n}))\ge\tfrac\e2\}
\endaligned \tag4.1
$$
halmazt, akkor $P((\xi_1,\dots,\xi_n)\in B)\ge\frac\e2$.
Ugyanis
$$
\e\le P((\xi_1,\dots,\xi_n)=(\zeta_1,\dots,\zeta_n))
\le P((\xi_1,\dots,\xi_n)\in B)+\frac\e2
(1-P((\xi_1,\dots,\xi_n)\in B)),
$$
ahonnan k\"ovetkezik ez az \'all\'{\i}t\'as. Viszont innen az is
k\"ovetkezik, hogy ha $n\ge n_0$ egy el\'eg nagy $n_0$ sz\'ammal,
akkor a $B(n)$ halmaz elemsz\'ama nagyobb, mint
$2^{(1-\delta)^2H(\xi)n}$. Val\'oban, vezess\"uk be a
$$
\align
B_1=B_1(n)&=\{(x_{i_1},\dots,x_{i_n})\colon\;
(x_{i_1},\dots,x_{i_n})\in X^n, \\
&\qquad P((\xi_1,\dots,\xi_n)=(x_{i_1},\dots,x_{i_n}))
<2^{-(1-\delta)H(\xi)n}\}
\endalign
$$
halmazt. L\'attuk kor\'abban, hogy
$P((\xi_1,\dots,\xi_n)\in B_1)\ge 1-\frac\e4$.
Ez\'ert $P(\xi_1,\dots,\xi_n)\in B\cap B_1)\ge\frac\e4$, ahonnan
a $B\cap B_1$, k\"ovetkez\'esk\'eppen a $B=B(n)$ halmaz elemsz\'ama
nagyobb, mint
$\frac\e42^{(1-\delta)H(\xi)n}\ge 2^{(1-\delta)^2H(\xi)n}$,
\'es val\'oj\'aban a $B$ halmaz elemsz\'am\'ara  ilyen als\'o
becsl\'est k\'{\i}v\'antunk adni.

Tekints\"uk a (4.1) formul\'aban defini\'alt $B(n)$ halmazt, \'es
soroljuk fel az elemeit
$B(n)=\{x^{(n)}(l),\;1\le l\le N(n)\}$ 
alakban. L\'attuk, hogy $N(n)\ge 2^{(1-\delta)^2H(\xi)n}$.
Fe\-lel\-tes\-s\"uk meg minden $x^{(n)}(l)\in B(n)$ vektornak a
a $(v^{(n)}(l),B_{u(l)})$ p\'art, ahol 
$v^{(n)}(l)=f(x^{(n)}(l))\in A(n)$ a tekintett modellben 
szerepl\H{o} $f(\cdot)$ k\'odf\"uggv\'ennyel, \'es 
$B_{u(l)}\in\VV^{(n)}$ a $\VV^{(n)}$ halmaz $B_1,\dots,B_N$
partici\'oj\'anak az a $B_{u(l)}$ eleme, amelyre a te\-kin\-tett
modellben a $B_{u(l)}\to x^{(n)}(l)$ megfeleltet\'est defini\'altuk.
(L\'etezik ilyen $B_{u(l)}$ halmaz a
$P((\zeta_1,\dots,\zeta_n)=x^{(n)}(l)
|(\xi_1,\dots,\xi_n)=x^{(n)}(l))\ge\frac\e2$ tulajdons\'ag
miatt.) Vegy\"uk \'eszre, hogy
$$
p(B_{u(l)}|v^{(n)}(l))
=\summ_{\vv^{(n)}\in B_{u(l)}}p(\vv^{(n)}|v^{(n)}(l))\ge\frac\e2,
$$
ahol $p(\vv^{(n)}|v^{(n)}(l))$ az eml\'ekezet n\'elk\"uli csatorna
\'atmenetval\'osz\'{\i}n\H{u}s\'ege, azaz
$$
p(\vv^{(n)}|v^{(n)}(l))=\prodd_{k=1}^n p(\vv_{j_k}|v_{i_k}(l)),
$$
ha $\vv^{(n)}=(\vv_{j_1},\dots,\vv_{j_n})$, \'es
$v^{(n)}(l)=(v_{i_1}(l),\dots,v_{i_n}(l))$. A fel\'{\i}rt
egyenl\H{o}tlens\'eg az\'ert igaz, mert benne annak a
val\'osz\'{\i}n\H{u}s\'eg\'et tekintett\"uk, hogy v\'eve az
$x^{(n)}(l)\in X^n$ sorozatot, \'atengedve azt a csatorn\'an, majd
a kapott jelet az \'altalunk le\'{\i}rt m\'odon dek\'odolva a
$(\zeta_1,\dots,\zeta_n)=x^{(n)}(l)$ sorozatot kapjuk.
Ennek val\'osz\'{\i}n\H{u}s\'ege pedig legal\'abb $\frac\e2$.
Vegy\"uk \'eszre azt is, hogy b\'ar lehets\'eges, hogy
$v^{(n)}(l)=v^{(n)}(l')$ akkor is, ha $l\neq l'$, azaz lehet k\'et
k\"ul\"onb\"oz\H{o} $x^{(n)}(l)\in A(n)$ \'es $x^{(n)}(l')\in A(n)$
vektor, amelyekre $l\neq l'$, \'es $f(x^{(n)}(l))=f(x^{(n)}(l'))$,
viszont b\'armely $v^{(n)}\in V^n$ vektorra az
$f(x^{(n)}(l))=v^{(n)}$ rel\'aci\'o legfeljebb $\frac2\e$
k\"l\"onb\"oz\H{o} $l$ indexre \'allhat fenn. Val\'oban, mivel
$$
\summ_{l\colon f(x^{(n)}(l))=v^{(n)}}p(B_{u(l)}|v^{(n)}(l))=
p\(\left.
\bigcupp_{l\colon f(x^{(n)}(l))=v^{(n)}} B_{u(l)}\right|v^{(n)}\)
\le 1,
$$ 
\'es az \"osszeg mindegyik tagj\'anak az \'ert\'eke
legal\'abb $\frac\e2$, innen k\"ovetkezik az \'all\'{\i}t\'as.

Tekints\"uk a
$C=C(n)=\{v^{(n)}(l)=f(x^{(n)}(l))\colon\; x^{(n)}(l)\in B_n\}$
halmazt, ahol azon  $v^{(n)}(l)$ vektorok k\"oz\"ul, amelyekre
$v^{(n)}(l)=v^{(n)}$ valamely $v^{(n)}\in V^n$ vektorra csak az 
egyik $v^{(n)}(l)$ vektort soroljuk
fel, \'es t\'ars\'{\i}tsuk mindegyik $v^{(n)}(l)\in C$ vektorhoz
a neki megfelel\H{o} $B_{u(l)}$ halmazt a $\VV^n$ halmaz 
$B_1,\dots,B_N$ partici\'oj\'ab\'ol. L\'attuk, hogy
$p(B_{u(l)}|v^{(n)}(l))\ge\frac\e2$, ami azt jelenti, hogy a $C$
halmaz elemei a csatorn\'ara n\'ezve $1-\frac\e2$
megk\"ul\"onb\"oztethet\H{o} elemek. M\'asr\'eszt azt is l\'attuk,
hogy a $C$ halmaz elemsz\'ama na\-gyobb, mint
$\frac\e22^{(1-\delta)^2H(\xi)n}\ge 2^{(1-\delta)^3H(\xi)n}
\ge2^{Cn/(1-\delta)}$, ha $n\ge n_0$. Ez viszont ellentmond a
a csatorna k\'odol\'asi t\'etel megford\'{\i}t\'as\'anak.
Ez\'ert ilyen tulajdons\'ag\'u legal\'abb $\e$ pontoss\'ag\'u
inform\'aci\'o tov\'abb\'{\i}t\'as \'es dek\'odol\'as nem
l\'etezhet, ha $n\ge n_0(\e)$ egy el\'eg nagy $n_0$ sz\'ammal.

Meg kell m\'eg indokolni, hogy r\"ovid blokkok seg\'{\i}ts\'eg\'evel
sem lehet nagyon j\'o inform\'aci\'o tov\'abb\'{\i}t\'ast el\'erni,
ha $H(\xi)>C$. A k\"ovetkez\H{o} \'all\'{\i}t\'ast fogom igazolni.
R\"og\-z\'{\i}t\-s\"unk egy tetsz\H{o}leges $\e>0$ sz\'amot, mondjuk
legyen $\e=\frac12$. Legyen $n_0=n_0(\frac12)$ egy olyan
k\"usz\"obindex, amelyre igaz, hogy minden $n\ge n_0$
hossz\'us\'ag\'u blokkokkal t\"ort\'en\H{o}, az el\H{o}bbiekben
le\'{\i}rt valamilyen $f\colon X^n\to V^n$ k\'odol\'asi
f\"uggv\'eny, a $\VV^n$ halmaz egy $B_1,\dots,B_N$ partici\'oj\'an
\'es egy e partici\'o $B_l$ elemeinek egy $x^{(n)}(l)\in X^n$
elemet megfeleltet\H{o} lek\'epez\'es \'altal meghat\'arozott
inform\'aci\'o tov\'abb\'{\i}t\'as \'es k\'odol\'as 
ered\-m\'e\-nye\-k\'ent b\'armely jelet csak $\frac12$-n\'el 
nagyobb hib\'aval lehet dek\'odolni. Azt \'all\'{\i}tom, hogy ha 
az el\H{o}bb le\'{\i}rt m\'odszert alkalmazzuk olyan $n$ 
hossz\'us\'ag\'u sorozatokra, amelyekre $n<n_0$, azaz 
bevezet\"unk egy $f(\cdot)$ k\'odol\'asi  f\"uggv\'enyt, a 
$\VV^n$ halmaz egy $B_1,\dots,B_N$ partici\'oj\'at, \'es annak 
egy lek\'epez\'es\'et az $X^n$ t\'erre erre az $n<n_0$ indexre, 
\'es ezen objektumok seg\'{\i}ts\'eg\'evel elv\'egezz\"uk a 
fent le\'{\i}rt dek\'odol\'asi elj\'ar\'ast, akkor f\"uggetlen\"ul 
att\'ol, hogy hogyan v\'alasztottuk meg ezeket a mennyis\'egeket, 
mindig olyan elj\'ar\'ast kapunk, amelyben a dek\'odol\'as hib\'aja 
nagyobb, mint $\frac1{2n_0}$.

A bizony\'{\i}t\'as alapgondolata az, hogy ha l\'etezne olyan m\'odszer,
amellyel a dek\'odol\'as hib\'aja kisebb, mint $\frac1{2n_0}$, akkor
ezt alkalmazva $n_0$ egym\'as ut\'ani blokkra olyan dek\'odol\'asi
elj\'ar\'ast kapn\'ank $n_0$-n\'al hosszabb blokkokra, amelyiknek
a hib\'aja kisebb, mint $\frac12$. Vi\-szont tudjuk, hogy ez nem
lehets\'esges.

Val\'oban, adva egy $n<n_0$ sz\'am tekints\"unk valamilyen 
$f\colon X^n\to V^n$ k\'odol\'o f\"ugg\-v\'enyt, a $V^n$ halmaz
egy $B_1,\dots,B_N$ partici\'oj\'at valamint egy $B_l\to x^{(n)}(l)$,
$1\le l\le N$, $x^{(n)}(l)\in V^n$ egy megfeleltet\'es\'et a partici\'o
elemeinek $X^n$-beli pontokkal. Ez defini\'al egy k\'odol\'asi
elj\'ar\'ast az $n$ hossz\'us\'ag\'u sorozatok ter\'en.
Tudjuk defini\'alni a megfelel\H{o} objektumokat az $n_0 n$
hossz\'us\'ag\'u sorozatok ter\'en, \'es az meghat\'aroz egy
dek\'odol\'asi elj\'ar\'ast a $n_0n$ hossz\'us\'ag\'u
sorozatok ter\'en. Nevezetesen, defini\'aljuk az $\bar f$ 
k\'odol\'asi f\"uggv\'enyt a k\"ovetkez\H{o} m\'odon:
$\bar f(x_1,\dots,x_{n_0n})=\prodd_{k=0}^{n_0-1}f(x_{kn+1},\dots,x_{(k+1)n})$.
A $\VV^{n_0n}$ halmaz partici\'oja $N^{n_0}$ elemb\H{o}l \'all,
\'es ezek a $B(l_{i(1)},\dots,l_{i(n_0)})
=B_{l_{i(1)}}\times \cdots\times B_{l_{i(n_0)}}$
halmazok, ahol $1\le i(j)\le N$ minden $1\le j\le n_0$ indexre.
V\'eg\"ul e partici\'o
$B(l_{i(1)},\dots,l_{i(n_0)})$ elem\'enek a
$x^{(n)}(l_{i(1)})\times\cdots\times x^{(n)}(l_{in_0)})\in X^{n_0n}$
vektor felel meg. Nem neh\'ez bel\'atni, hogy ha az eredeti $n_0$
hossz\'us\'ag\'u sorozatok dek\'od\'as\'aban minden egyes $n$
hossz\'usz\'ag\'u sorozat hib\'as dek\'odol\'as\'anak a
val\'osz\'{i}n\H{u}s\'ege 
kisebb, mint $\frac1{2n_0}$, akkor az $n_0n$ hossz\'us\'ag\'u
sorozatok `szorzatter\'eben az \'uj objektumok \'altal meghat\'arozott
dek\'odol\'as hib\'aj\'anak a val\'osz\'{i}n\H{u}s\'ege 
 kisebb, mint $n_0\frac1{2n_0}=\frac12$.
Ugyanis a `szorzatt\'erben az \'uj dek\'odol\'as val\'oj\'aban
\'ugy m\H{u}k\"odik, hogy az egyen $kn_0+1\le n\le (k+1)n$ blokkokat
egym\'ast\'ol f\"uggetlen\"ul az $n$ hossz\'us\'agi blokkokra
\'erv\'enyes szab\'aly szerint blokkoljuk, \'es ha ezen $n_0$
blokk dek\'odol\'asa mindegyik $k$-ra kevesebb, mint $\frac1{2n_0}$
val\'osz\'{i}n\H{u}s\'eggel hib\'asodik meg, akkor igaz az
eml\'{\i}tett becsl\'es. De mivel ilyen hossz\'u
sorozatokkal v\'egzett dek\'odol\'asok hib\'aja nem lehet ilyen
j\'o, innen k\"ovetkezik a r\"ovid sorozatok hib\'aj\'ara
megfogalmazott \'all\'{\i}t\'as. 


\bye


