Un canal simètric binari (o BSCp) és un model de canal de comunicacions comú utilitzat en teoria de codificació i teoria de la informació. En aquest model, un transmissor vol enviar un bit (un zero o un u) i el receptor rebrà un bit. El bit es "invertirà" amb una "probabilitat de creuament" de p, i altrament es rebrà correctament. Aquest model es pot aplicar a diversos canals de comunicació com ara línies telefòniques o emmagatzematge en unitats de disc.

El teorema de codificació de canal sorollós s'aplica al BSC p, dient que la informació es pot transmetre a qualsevol velocitat fins a la capacitat del canal amb un error arbitràriament baix. La capacitat del canal és bits, on és la funció d'entropia binària. Els codis que inclouen el codi de Forney han estat dissenyats per transmetre informació de manera eficient a través del canal.

Definició alt=Binary symmetric channel|miniatura|El canal simètric binari veu cada bit d'un missatge transmès correctament amb probabilitat 1– p i incorrectament amb probabilitat p, a causa del soroll a través del medi de transmissió. Un canal simètric binari amb probabilitat de creuament , denotada per BSC p, és un canal amb entrada binària i sortida binària i probabilitat d'error És a dir, si és la variable aleatòria transmesa i la variable rebuda, aleshores el canal es caracteritza per les probabilitats condicionals:

Se suposa que Si , aleshores el receptor pot intercanviar la sortida (interpretar 1 quan veu 0 i viceversa) i obtenir un canal equivalent amb probabilitat de creuament .

Capacitat miniatura|300x300px|Gràfic que mostra la proporció de la capacitat d'un canal (eix y) que es pot utilitzar per a la càrrega útil en funció del soroll del canal (probabilitat de canvis de bits; eix x ). La capacitat del canal simètric binari, en bits, és:

on és la funció d'entropia binària, definida per:

Teorema de codificació de canals sorollosos El teorema de codificació de canals sorollosos de Shannon dóna un resultat sobre la velocitat d'informació que es pot transmetre a través d'un canal de comunicació amb un error arbitràriament baix. Estudiem el cas particular de .

El soroll que caracteritza és una variable aleatòria que consisteix en n bits aleatoris independents (n es defineix a continuació) on cada bit aleatori és un amb probabilitat i un amb probabilitat . Ho indiquem escrivint " ".

El que realment implica aquest teorema és un missatge quan es pren de , codificat amb una funció de codificació aleatòria , i enviat a través d'un sorollós , hi ha una probabilitat molt alta de recuperar el missatge original descodificant-lo, si o, de fet, la velocitat del canal està limitada per la quantitat indicada al teorema. La probabilitat d'error de descodificació és exponencialment petita.El que realment implica aquest teorema és un missatge quan es pren de , codificat amb una funció de codificació aleatòria , i enviat a través d'un sorollós , hi ha una probabilitat molt alta de recuperar el missatge original descodificant-lo, si o, de fet, la velocitat del canal està limitada per la quantitat indicada al teorema. La probabilitat d'error de descodificació és exponencialment petita.

Prova El teorema es pot demostrar directament amb un mètode probabilístic. Considereu una funció de codificació que es selecciona a l'atzar. Això significa que per a cada missatge , el valor es selecciona a l'atzar (amb probabilitats iguals). Per a una funció de codificació determinada , la funció de descodificació s'especifica de la següent manera: donada qualsevol paraula de codi rebuda , trobem el missatge de manera que la distància de Hamming és tan petit com sigui possible (amb els empats trencats arbitràriament). s'anomena funció de descodificació de màxima versemblança.)

La demostració continua mostrant que almenys una d'aquestes opcions satisfà la conclusió del teorema, per integració sobre les probabilitats. Suposem i són fixos. Primer mostrem que, per a un fix i escollit a l'atzar, la probabilitat de fallada respecte a el soroll és exponencialment petit en n. En aquest punt, la demostració funciona per a un missatge fix A continuació, estenem aquest resultat perquè funcioni per a tots els missatges. Ho aconseguim eliminant la meitat de les paraules de codi del codi amb l'argument que la demostració de la probabilitat d'error de descodificació es compleix per a almenys la meitat de les paraules de codi. Aquest darrer mètode s'anomena expurgació. Això dóna al procés total el nom de codificació aleatòria amb expurgació.

El contrari del teorema de la capacitat de Shannon El contrari del teorema de la capacitat estableix essencialment que és la millor velocitat que es pot aconseguir sobre un canal simètric binari. Formalment, el teorema estableix:La intuïció darrere de la demostració, però, mostra que el nombre d'errors creix ràpidament a mesura que la taxa supera la capacitat del canal. La idea és que l'emissor genera missatges de dimensió , mentre que el canal introdueix errors de transmissió. Quan la capacitat del canal és , el nombre d'errors sol ser per a un codi de longitud de bloc El nombre màxim de missatges és . La sortida del canal, en canvi, té valors possibles. Si hi ha alguna confusió entre dos missatges, és probable que Per tant, tindríem , un cas que voldríem evitar per mantenir la probabilitat d'error de descodificació exponencialment petita.

Codis Molt recentment, s'ha fet i s'està fent molta feina per dissenyar codis explícits de correcció d'errors per aconseguir les capacitats de diversos canals de comunicació estàndard. La motivació darrere del disseny d'aquests codis és relacionar la velocitat del codi amb la fracció d'errors que pot corregir.

L'enfocament darrere del disseny de codis que s'adapten a les capacitats del canal de o el canal d'esborrat binari han estat corregir un nombre menor d'errors amb una alta probabilitat i aconseguir la taxa més alta possible. El teorema de Shannon ens dóna la millor taxa que es pot aconseguir durant un , però no ens dóna una idea de cap codi explícit que aconsegueixi aquesta taxa. De fet, aquests codis es construeixen normalment per corregir només una petita fracció d'errors amb una alta probabilitat, però aconsegueixen una taxa molt bona. El primer codi d'aquest tipus va ser degut a George D. Forney el 1966. El codi és un codi concatenat concatenant dos tipus diferents de codis.

Aplicacions El canal simètric binari pot modelar una unitat de disc utilitzada per a l'emmagatzematge de memòria: l'entrada del canal representa un bit que s'escriu al disc i la sortida correspon al bit que es llegeix posteriorment. Podrien sorgir errors a causa de la inversió de la magnetització, el soroll de fons o un error del capçal d'escriptura. Altres objectes que el canal simètric binari pot modelar inclouen una línia de comunicació telefònica o per ràdio o una divisió cel·lular, de la qual les cèl·lules filles contenen informació d'ADN de la seva cèl·lula mare.

Els teòrics sovint utilitzen aquest canal perquè és un dels canals sorollosos més senzills d'analitzar. Molts problemes en la teoria de la comunicació es poden reduir a un BSC. Per contra, poder transmetre eficaçment a través del BSC pot donar lloc a solucions per a canals més complicats.

Referències

Categoria:Teoria de la informació