Shannonin toinen lause
In informaatioteoriaan , toinen lause Shannon koodauksen mainitun kanavan osoittaa, että on mahdollista siirtää digitaalista dataa on kanava jopa meluisassa lähes virheettömästi enintään laskettua. Tämä Claude Shannonin vuonna 1948 julkaisema tulos perustuu Harry Nyquistin ja Ralph Hartleyn aikaisempaan teokseen . Ensimmäisen tiukan todistuksen vahvisti Amiel Feinstein vuonna 1954. Se on perustavanlaatuinen tietoteoriassa, ja sillä on laaja käyttö televiestinnän ja tietojen varastoinnin aloilla .
Kanavan Shannon-raja tai kapasiteetti on suurin teoreettinen tiedonsiirtonopeus kyseisellä kanavalla tietylle melutasolle .
Johdanto
Yksi niin sanotun digitaalisen tekniikan tärkeimmistä eduista on, että se mahdollistaa tietojen vaihdon menettämättä tietoja. Kuitenkin nämä tiedot kulkevat enimmäkseen kanavilla, jotka eivät ole luotettavia, koska ne ovat altistuneet erilaisille häiriöille ja melulle . Kuinka voimme sitten poistaa lähetysvirheet? Ratkaisu on redundanssin lisääminen lähteen lähettämään viestiin virheiden korjaamiseksi. Puhumme kanavan koodauksesta korjauskoodilla .
Lause osoittaa, että lähteille, joiden bittinopeus on pienempi kuin tietty siirtokanavaan liitetty kapasiteetti, on koodeja, jotka dekoodauksen yhteydessä virhesuhde on niin pieni kuin halutaan.
Usein kiinteän keston ajan lähetettävät symbolit korvaavat lähteen entropian nopeudella bitteinä / s. Sama koskee kanavan kapasiteettia, joka voi olla virtaus tai keskinäinen tieto (josta tietty sekaannus). Jälkimmäinen määräytyy kanavan fyysisten ominaisuuksien perusteella. Shannon-Hartley-lause antaa esimerkiksi rajoitetun kaistanleveyden kanavan kapasiteetin, joka käy läpi Gaussin melua (katso signaali kohinaan ).
On huomattava, että virhesuhteen poistamiseksi erilaiset todisteet pyrkivät koodisanojen pituuteen kohti ääretöntä. Joten jos lause mahdollistaa tällaisten koodien löytämisen, se ei tarjoa tyydyttävän algoritmisen monimutkaisuuden dekoodausalgoritmeja . Nykyään konvoluutioiset turbokoodit tai LDPC ( Low-density parity-check ) -koodit mahdollistavat sellaisten signaalien lähettämisen, joiden entropia lähestyy kanavan kapasiteettia samalla kun ne pysyvät dekoodattavissa reaaliajassa.
Yksityiskohdat
Erillinen lähde lähettää jokaisen ennalta määritetyn aakkosen symbolin tietyllä taajuudella. Muodollisesti se mallinnetaan kategorisella satunnaismuuttujalla . Kutsumme lähteen koodausta mistä tahansa satunnaismuuttujasta siten, että ehdollinen entropia on nolla (ei tiedon menetystä tai vahvistusta).
ATs{\ displaystyle {\ mathcal {A}} _ {s}}
S{\ displaystyle S}
S{\ displaystyle S}
E{\ displaystyle E}
H(S|E){\ displaystyle H (S | E)}![H (S | E)](https://wikimedia.org/api/rest_v1/media/math/render/svg/00d2a9e198661a5af349dc35bb33d785759a4e7c)
Lähteen ja aakkosen perusteella kutsumme lähetyskanavaksi mitä tahansa toimintoa koodausten joukossa ja arvot kategoristen satunnaismuuttujien joukossa .
S{\ displaystyle S}
ATd{\ displaystyle {\ mathcal {A}} _ {d}}
f{\ displaystyle f}
E(S){\ displaystyle {\ mathcal {E}} (S)}
ATd{\ displaystyle {\ mathcal {A}} _ {d}}![{\ displaystyle {\ mathcal {A}} _ {d}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/13061e60168b62e45653075b69153c444d4e6e38)
Kanavan kapasiteetti saadaan:
f{\ displaystyle f}![f](https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61)
VS(f)=supE∈E(S)Minä(E,f(E)){\ displaystyle C (f) = \ sup _ {E \ muodossa {\ mathcal {E}} (S)} I (E, f (E))}
missä tarkoittaa keskinäistä tietoa .
Minä{\ displaystyle I}![Minä](https://wikimedia.org/api/rest_v1/media/math/render/svg/535ea7fc4134a31cbe2251d9d3511374bc41be9f)
Lause
Alustavat huomautukset
Huomaa:
-
R{\ displaystyle R}
lähdekoodauksen entropia .
-
X{\ displaystyle X}
kaikki sallitut kanavatulot.x{\ displaystyle {\ textbf {x}}}![\ textbf {x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/85631435f001c884eca834164392982c621f40e2)
-
Y{\ displaystyle Y}
kaikki kanavan sallitut lähdöt .y{\ displaystyle {\ textbf {y}}}![\ textbf {y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9217602eb948f6bfca224665a8b6aac54e15725b)
-
VS{\ displaystyle C}
kanavan kapasiteetti ilman muistia.
-
s(y|x){\ displaystyle p ({\ textbf {y}} | {\ textbf {x}})}
erillisen kanavan siirtymätodennäköisyydet ilman muistia (havaitsemisen todennäköisyys sisääntulon jälkeen ).y{\ displaystyle {\ textbf {y}}}
x{\ displaystyle {\ textbf {x}}}![\ textbf {x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/85631435f001c884eca834164392982c621f40e2)
Dekoodaus suoritetaan suurimman todennäköisyyden merkityksessä, eli sanasta päätetään, jos:
x{\ displaystyle {\ textbf {x}}}![\ textbf {x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/85631435f001c884eca834164392982c621f40e2)
∀x′≠x,s(y|x)>s(y|x′){\ displaystyle \ forall {\ textbf {x}} '\ neq {\ textbf {x}}, p ({\ textbf {y}} | {\ textbf {x}})> p ({\ textbf {y} } | {\ textbf {x}} ')}
Osavaltiot
Vakionopeudelle on koodisarja, joka poistaa virheen todennäköisyyden.
R<VS{\ displaystyle R <C}![R <C](https://wikimedia.org/api/rest_v1/media/math/render/svg/fffc6476f6ba31efec56b837c6fa92d39d097495)
Todiste lohkokoodista
Sanan virhetodennäköisyyden kasvu
Pankaamme merkille .
Φx(y)={1,jos on x′ kuten s(y|x)>s(y|x′)0,jos ei{\ displaystyle \ Phi _ {\ textbf {x}} ({\ textbf {y}}) = {\ begin {cases} 1, ja {\ text {jos sellaisia on}} {\ textbf {x}} ' {\ text {kuten}} p ({\ textbf {y}} | {\ textbf {x}})> p ({\ textbf {y}} | {\ textbf {x}} ') \\ 0, & {\ text {muuten}} \ end {cases}}}![\ Phi _ {\ textbf {x}} (\ textbf {y}) = \ begin {cases} 1, & \ text {jos on}} textbf {x} '\ text {sellainen}} p (\ textbf {y} | \ textbf {x})> p (\ textbf {y} | \ textbf {x} ') \\ 0, & \ text {muuten} \ loppu {tapaukset}](https://wikimedia.org/api/rest_v1/media/math/render/svg/078860e7e8218f25a0cf28f6b1d2b80f94c45fb0)
Virheen todennäköisyys sanaa kirjoitettaessa on:
x{\ displaystyle {\ textbf {x}}}![\ textbf {x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/85631435f001c884eca834164392982c621f40e2)
E(x)=∑y∈Ys(y|x)Φx(y){\ displaystyle {\ mathcal {E}} ({\ textbf {x}}) = \ summa _ {{\ textbf {y}} \ Y} p ({\ textbf {y}} | {\ textbf {x }}) \ Phi _ {\ textbf {x}} ({\ textbf {y}})}
Mutta meillä on lisäys:
s>0{\ displaystyle s> 0}![s> 0](https://wikimedia.org/api/rest_v1/media/math/render/svg/76beea94b6662bd490c61c0628dddd8a8cd35538)
Φx(y)≤(∑x′≠xs(y|x′)11+ss(y|x)11+s)s{\ displaystyle \ Phi _ {\ textbf {x}} ({\ textbf {y}}) \ leq \ left ({\ frac {\ sum _ {{\ textbf {x}} '\ neq {\ textbf {x }}} p ({\ textbf {y}} | {\ textbf {x}} ') ^ {\ frac {1} {1 + s}}} {p ({\ textbf {y}} | {\ textbf {x}}) ^ {\ frac {1} {1 + s}}}} \ oikea) ^ {s}}
Mistä :
E(x)≤∑y∈Ys(y|x)11+s(∑x′≠xs(y|x′)11+s)s{\ displaystyle {\ mathcal {E}} ({\ textbf {x}}) \ leq \ sum _ {{\ textbf {y}} \ in Y} p ({\ textbf {y}} | {\ textbf { x}}) ^ {\ frac {1} {1 + s}} \ left (\ summa _ {{\ textbf {x}} '\ neq {\ textbf {x}}} p ({\ textbf {y} } | {\ textbf {x}} ') ^ {\ frac {1} {1 + s}} \ oikea) ^ {s}}
Todennäköinen koodisarja
Oletetaan, että koodisanat ovat peräisin lain mukaisista riippumattomista arvonnoista , sitten:
L{\ displaystyle {\ mathcal {L}}}![\ mathcal {L}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9027196ecb178d598958555ea01c43157d83597c)
E¯(x)=E[E(x)]≤E[∑y∈Ys(y|x)11+s(∑x′≠xs(y|x′)11+s)s]{\ displaystyle {\ bar {\ mathcal {E}}} ({\ textbf {x}}) = \ mathbb {E} [{\ mathcal {E}} ({\ textbf {x}})] \ leq \ mathbb {E} \ left [\ sum _ {{\ textbf {y}} \ in Y} p ({\ textbf {y}} | {\ textbf {x}}) ^ {\ frac {1} {1+ s}} \ vasen (\ summa _ {{\ textbf {x}} '\ neq {\ textbf {x}}} p ({\ textbf {y}} | {\ textbf {x}}') ^ {\ frac {1} {1 + s}} \ oikea) ^ {s} \ oikea]}
Lineaarisuuden mukaan :
E{\ displaystyle \ mathbb {E}}![\ mathbb {E}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ad9faf1fd4a61d36d7f8a2f3204f3805a43c0d4a)
E¯(x)≤∑y∈YE[s(y|x)11+s(∑x′≠xs(y|x′)11+s)s]{\ displaystyle {\ bar {\ mathcal {E}}} ({\ textbf {x}}) \ leq \ sum _ {{\ textbf {y}} \ muodossa Y} \ mathbb {E} \ vasen [p ( {\ textbf {y}} | {\ textbf {x}}) ^ {\ frac {1} {1 + s}} \ vasen (\ summa _ {{\ textbf {x}} '\ neq {\ textbf { x}}} p ({\ textbf {y}} | {\ textbf {x}} ') ^ {\ frac {1} {1 + s}} \ oikea) ^ {s} \ oikea]}
Koodisanat piirretään kuitenkin itsenäisesti, joten:
E¯(x)≤∑y∈YE[s(y|x)11+s]E[(∑x′≠xs(y|x′)11+s)s]{\ displaystyle {\ bar {\ mathcal {E}}} ({\ textbf {x}}) \ leq \ sum _ {{\ textbf {y}} \ muodossa Y} \ mathbb {E} \ vasen [p ( {\ textbf {y}} | {\ textbf {x}}) ^ {\ frac {1} {1 + s}} \ oikea] \ mathbb {E} \ vasen [\ vasen (\ summa _ {{\ textbf {x}} '\ neq {\ textbf {x}}} p ({\ textbf {y}} | {\ textbf {x}}') ^ {\ frac {1} {1 + s}} \ oikea) ^ {s} \ oikea]}
Lisäksi, jos , on kovera ja Jensenin eriarvoisuus antaa:
s<1{\ displaystyle s <1}
x↦xs{\ displaystyle x \ mapsto x ^ {s}}![x \ mapsto x ^ s](https://wikimedia.org/api/rest_v1/media/math/render/svg/d661988fbe98a94ff00da7d7e2bede57f6dcb610)
E¯(x)≤∑y∈YE[s(y|x)11+s](E[∑x′≠xs(y|x′)11+s])s{\ displaystyle {\ bar {\ mathcal {E}}} ({\ textbf {x}}) \ leq \ sum _ {{\ textbf {y}} \ muodossa Y} \ mathbb {E} \ vasen [p ( {\ textbf {y}} | {\ textbf {x}}) ^ {\ frac {1} {1 + s}} \ oikea] \ vasen (\ mathbb {E} \ vasen [\ summa _ {{\ textbf {x}} '\ neq {\ textbf {x}}} p ({\ textbf {y}} | {\ textbf {x}}') ^ {\ frac {1} {1 + s}} \ oikea] \ oikea) ^ {s}}
Ja lineaarisuuden mukaan:
E¯(x)≤∑y∈YE[s(y|x)11+s](∑x≠x′E[s(y|x′)11+s])s{\ displaystyle {\ bar {\ mathcal {E}}} ({\ textbf {x}}) \ leq \ sum _ {{\ textbf {y}} \ muodossa Y} \ mathbb {E} \ vasen [p ( {\ textbf {y}} | {\ textbf {x}}) ^ {\ frac {1} {1 + s}} \ oikea] \ vasen (\ summa _ {{\ textbf {x}} \ neq {\ textbf {x}} '} \ mathbb {E} \ left [p ({\ textbf {y}} | {\ textbf {x}}') ^ {\ frac {1} {1 + s}} \ oikea] \ oikea) ^ {s}}
Kulta:
∀x′∈X,E[s(y|x′)11+s]=∑x∈XL(x)s(y|x)11+s{\ displaystyle \ forall {\ textbf {x}} '\ X: ssä, \ mathbb {E} \ vasen [p ({\ textbf {y}} | {\ textbf {x}}') ^ {\ frac {1 } {1 + s}} \ oikea] = \ summa _ {{\ textbf {x}} \ X} {\ mathcal {L}} ({\ textbf {x}}) p ({\ textbf {y} } | {\ textbf {x}}) ^ {\ frac {1} {1 + s}}}
Siksi :
E¯(x)≤(|X|-1)s∑y∈Y[∑x∈XL(x)s(y|x)11+s]1+s{\ displaystyle {\ bar {\ mathcal {E}}} ({\ textbf {x}}) \ leq \ left (| X | -1 \ right) ^ {s} \ summa _ {{\ textbf {y} } \ sisään Y} \ vasen [\ sum _ {{\ textbf {x}} \ X: ssä} {\ mathcal {L}} ({\ textbf {x}}) p ({\ textbf {y}} | { \ textbf {x}}) ^ {\ frac {1} {1 + s}} \ oikea] ^ {1 + s}}
Tämä kasvu ei riipu , on olemassa koodi, jonka virhetodennäköisyyttä kasvatetaan tällä samalla määrällä.
x{\ displaystyle {\ textbf {x}}}![\ textbf {x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/85631435f001c884eca834164392982c621f40e2)
Aiheeseen liittyvät artikkelit
Huomautuksia ja viitteitä
-
(vuonna) Sae-Young Chung , G. David Forney, nuorempi (vuonna) , Thomas J. Richardson ja Rüdiger Urbanke , " Alhaisen tiheyden pariteettitarkistuskoodien suunnittelusta 0,0045 dB: n sisällä Shannon-rajasta " , IEEE Communication Letters , voi. 5,Helmikuu 2001, s. 58-60 ( ISSN 1089-7798 , lue verkossa )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">