Mukaan Shannonin lause

Informaatioteoriassa, Shannonin lause tai toisen kanavakoodaus lause todetaan, että viestintäkanavana vaikuttaa melu, on mahdollista lähettää tietoja virhetodennäköisyydellä Pe niin pieni kuin halutaan enintään taajuus kanavan läpi sama. Tämä yllättävä tulos, joka tunnetaan myös nimellä keskeinen lause tietojen teoria, esiteltiin ensimmäistä kertaa Claude Shannonin vuonna 1948.

Shannon kapasiteettia, joka tunnetaan myös nimellä Shannon raja, viestintäkanava on suurin siirtonopeus tietoja, jotka voivat tarjota kanavan tietyn tason signaali / kohina-suhde, jossa virhetaso mielivaltaisesti pieni.

Näkymä

Lause, muotoiltu 1948 Claude Shannon, kuvailee mahdollisimman tehokkuutta menetelmän korjata mahdolliset virheet funktiona melutaso. Teoria ei selitä miten rakentaa hyvää koodia, vaan ainoastaan ​​vahvistetaan, mitä koodi suorituskyky erinomainen. Toinen Shannon lause on lukuisia sovelluksia, sekä televiestinnän alalla ja tietojen arkistointi. Tämä lause on perusta modernin tieto- teorian. Shannon antoi vain jälkeäkään todisteita. Ensimmäinen tiukka todiste johtuu Amiel Feinstein vuonna 1954.

Lause todetaan, että koska kanavan kapasiteetti C, johon tiedot lähetetään nopeudella R, sitten jos

on koodi, jonka avulla voit tehdä virheen todennäköisyyttä vastaanottimeen mielivaltaisesti pieni. Tämä tarkoittaa sitä, että, teoriassa, on mahdollista lähettää tietoja ilman virhettä tapauksessa vähemmän kuin C.

Käänteinen on myös tärkeää. Jos

et tavoita todennäköisyys virheen niin pieni kuin halutaan. Kaikki koodi olisi todennäköisyys virhe on suurempi kuin tietty arvo on suurempi kuin nolla, ja tämä arvo kasvaa korko. Sen vuoksi ei ole mahdollista taata, että tiedot lähetetään luotettavasti kanavalla suurempi kuin kapasiteetti. Lause ei pidä tapausta, jossa R ja C ovat yhtä.

Yksinkertaisia ​​malleja, kuten koodit toistoa menetelmiä virheenkorjausta tehottomia ja eivät pysty lähestymään Shannon raja. Käänteisesti kehittyneitä tekniikoita kuten Reed-Solomon koodeista tai Turbo koodeja, on paljon lähempänä Shannon raja, kustannuksella korkea laskennallinen vaativuus. Käyttämällä uusinta Turbo tunnuksia ja laskentateho saatavilla tänään DSP, se on nyt mahdollista päästä lähemmäksi kuin 10,1 desibeliä verrattuna Shannon raja

Lausunto

Lause:

Seuraa demo

Kuten monet muut keskeisistä tuloksista informaatioteorian, todiste toisen lauseen Shannon sisältyy osoitus saavutettavuutta ja testi käänteinen. Nämä kaksi komponenttia käytetään rajoittamaan, tässä tapauksessa joukko ääressä lähellä, jotka voivat kommunikoida meluisassa kanava ja todistaa, että nämä rajat ovat rajoja tiukasti.

Seuraavat kappaleet ovat vain kokoelma lukuisia menetelmiä ehdotti informaatioteorian.

Tavoitettavuus varten erillistä kanavaa ilman muistia

Tämä erityisesti tavoitettavuus on samanlainen kuin se, jota käytetään osoittamaan ominaisuuksia asymptoottinen equipartition.

Tämä tekniikka käyttää väite, joka perustuu valintaan satunnainen koodi, jonka joukko koodisanoja on rakennettu sattumanvaraisesti; näin voidaan vähentää laskennallista monimutkaisuutta, kuitenkin, yrittäen olemassaolo koodin, joka vastaa haluttavan virhetodennäköisyyden kunkin hitaammin kuin kanavan kapasiteetti.

Käyttämällä argumentti liittyy AEP, päivämäärät jouset symbolien kauan se lähteitä pitkiä merkkijonoja n lähtöjen kanava, voimme määritellä joukko yhdessä tyypillinen seuraavalla tavalla:

Sanomme, että kahden sekvenssin ja ovat yhdessä tyypillisiä jos ne jäävät kokonaisuudessaan yhdessä tyypillinen hiljattain määritelty.


Portaat

  • Tyyliin argumentti satunnainen koodaus, luomme satunnaisia ​​koodisanoja pituudeltaan n päässä todennäköisyystiheys Q.
  • Tämä koodi tunnetaan sekä lähetin ja vastaanotin; Lisäksi se edellyttää, että molemmat tietävät siirtyminen matriisin kanavan käytössä.
  • Viesti W valitaan mukaan tasaisuus on joukko mahdollisia koodisanoja. Eli.
  • Viesti lähetetään kanavan.
  • Vastaanotin vastaanottaa viestin mukaisesti jakelun
  • Lähettämällä koodisanojen kanavalla, vastaanottaa ja purkaa joissakin lähde symboli, jos on vain koodisana joka on yhdessä tyypillinen kanssa Y. Jos on koodisanoja yhdessä tyypillinen, tai jos on useampi kuin yksi, sitten teet virheen. Virhe tapahtuu myös, kun koodisana dekoodataan ei vastaa koodisana lähetetään. Tämä tekniikka on tarkoitettu koodaus tyypillinen asetettu.

Virheen todennäköisyys on jaettu kahteen osaan:

  • Ensinnäkin voi olla virhe, jos ei ole yhtäjaksoista X yhdessä tyypillinen sekvenssin Y saanut.
  • Toiseksi voi olla virhe, jos väärässä järjestyksessä X on yhdessä tyypillinen kanssa sekvenssin Y sai.
  • Perustuu oletukseen satunnaisuuden koodi, voimme vaatia, että keskimääräinen todennäköisyys virheen keskiarvoina kaikki koodit, ei riipu lähetetty. Voimme siis, yleispätevyyttä menettämättä, oletetaan W = 1.
  • Liitoksesta AEP, me tiedämme, että todennäköisyys, että ei ole olemassa yhdessä tyypillisiä sekvenssit X, yleensä 0, kun crescer n. Voimme rajoittaa ylhäältä tämä todennäköisyys.
  • Myös liitoksesta AEP, tiedämme, että todennäköisyys, että tietty, ja tuloksena W = 1 yhdessä on tyypillinen.

Määritellään:

Jos viesti on yhdessä tyypillinen kanssa vastaanotetun sekvenssin lähetetään, kun viesti ensin.

Voimme havaita, että yleensä äärettömään n, jos kanava, todennäköisyys virheen yleensä nolla.

Lopuksi, se on on osoittanut, että koko keskimäärin koodisanojen on "hyvä", on varmasti joukko koodisanoja, joiden esitykset on parempi kuin keskimäärin, ja tämä täyttää meidän tarvitse olla todennäköisyys virheen niin pieni kuin halutaan tiedonanto meluisa kanavalla.

Demo kääntää heikko erilliskanavaa ilman muistia

Oletetaan, että meillä koodi koostuu. Olkoon W uuttaa tasaisesti tällä laitteella kuin indeksi. Ja ovat koodisanoja ja sai vastaavasti

  •  käyttämällä yhtälöt liittyvät entropia ja vastavuoroista tiedottamista.
  •  koska X on funktio W:
  •  käyttäen eriarvoisuus Fano
  •  siitä, että kapasiteetti on suurin keskinäinen tiedot.

Näiden vaiheiden on että. Klo yleensä pituudeltaan n äärettömään, saamme joka rajoittuu yläreunasta 0, kun R on suurempi kuin C; vaan saamme alhainen virhemääriä mieleisekseen jos R on pienempi kuin C.

Mielenosoitus vahva käänteinen diskreetti kanavia ilman muistia

Vahva käänteinen lause, osoittaa Wolfowitz vuonna 1957, todetaan, että

joillekin positiivinen vakio. Vaikka käänteinen heikoissa valtioissa että todennäköisyys virhe on ehdottomasti suurempi kuin 0 taipumus äärettömään, voimakas lause todetaan, että virhe on taipumus eksponentiaalisesti 1. Joten, on kynnys, joka jakaa välillä viestintä täydellisesti luotettava ja täysin epäluotettava.

Lause Kanavakoodauksen kanavien ilman muistia epävakaa

Oletamme, että kanava on vapaa muistista, vaan että sen siirtyminen todennäköisyydet vaihdella ajan funktiona, tunnetulla tavalla sekä lähettimestä vastaanottimeen.

Kanavan kapasiteetti saadaan

Maksimi saadaan jakaumat, jotka saavuttavat kapasiteetin kunkin kanavan eli

jossa on kapasiteetti i: nnen kanavan.

Seuraa demo

Mielenosoitus noudattaa pääosin samat vaiheet ensimmäisen Shannonin lause. Tavoitettavuutta on peräisin satunnainen koodaus, jossa kukin symboli valittu sattumanvaraisesti jakelu, joka saavuttaa kapasiteetin tietylle kanavalle. Perustuvat väitteet tyypillisyyden käyttää määritelmää tyypillinen asetettu suoran kiinteissä lähteissä määritelty AEP.

Alaraja tulee pelata, kun se konvergoi.

  0   0
Edellinen artikkeli David Kross
Seuraava artikkeli Gyps rueppelli

Kommentit - 0

Ei kommentteja

Lisääkommentti

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Merkkiä jäljellä: 3000
captcha