Canal simétrico binario

Un canal simétrico binario (o BSC_p) es un modelo de canal de comunicaciones común utilizado en la teoría de la codificación y la teoría de la información. En este modelo, un transmisor desea enviar un bit (un cero o un uno), y el receptor recibirá un bit. El bit será "volteado" con una "probabilidad de cruce" de p, y por lo demás se recibe correctamente. Este modelo se puede aplicar a diversos canales de comunicación, como líneas telefónicas o almacenamiento en unidades de disco.

El teorema de codificación ruido-canal se aplica a BSC_p, diciendo que la información se puede transmitir a cualquier velocidad hasta la capacidad del canal con error arbitrariomente bajo. La capacidad del canal es ${displaystyle 1-operatorname {H} _{text{b}(p)}$ bits, dónde ${displaystyle operatorname {H} {fnK}}$ es la función binaria entropía. Los códigos incluyendo el código de Forney han sido diseñados para transmitir información de manera eficiente en todo el canal.

Definición

El canal binario simétrico ve cada bit de un mensaje transmitido correctamente con probabilidad 1–p y incorrectamente con probabilidad p, debido al ruido a través del medio de transmisión.

Un canal simétrico binario con probabilidad crossover ${displaystyle p}$, denotado por BSC_p, es un canal con entrada binaria y salida binaria y probabilidad de error ${displaystyle p}$. Eso es, si ${displaystyle X}$ es la variable al azar transmitida ${displaystyle Sí.$ la variable recibida, entonces el canal se caracteriza por las probabilidades condicionales:

${displaystyle {begin{aligned}operatorname {Pr} [Y=0 habitX=0] {Pr} [Y=0 habitX=1] {Pr} [Y=1 habitX=0] {Pr} [Y=1 habitX=1]$

Se supone que ${displaystyle 0leq pleq 1/2}$. Si ${displaystyle p confía1/2}$, entonces el receptor puede cambiar la salida (interpretar 1 cuando ve 0, y viceversa) y obtener un canal equivalente con probabilidad crossover ${displaystyle 1-pleq 1/2}$.

Capacidad

La capacidad del canal simétrico binario, en bits, es:

${displaystyle C_{text{BSC}=1-operatorname {H} _{b}(p)}$

Donde ${displaystyle operatorname {H} _{b}(p)}$ es la función binaria entropía, definida por:

${displaystyle operatorname {H} _{b}(x)=xlog _{2}{2}{x}}+(1-x)log _{2}{frac}{2}{frac} {fn0} {fn0} {1}{1-x}}$

Prueba

La capacidad se define como la máxima información mutua entre entrada y salida para todas las distribuciones posibles de insumos ${displaystyle p_{X}(x)}$: ${displaystyle C=max ¿Por qué?$ La información mutua puede reformularse como ${displaystyle {begin{aligned}I(X;Y) implica=H(Y)-H(Y eternaX)\\cH(Y)-sum _{xin {0,1}{p_{X}(x)H(Y sometidaX=x)}\\cH(Y)-sum _{xin {0,1}{p_{X}(x)}operatorname {H} _{text{b}(p)\\cH(Y)-operatorname {H} _{text{b}(p),end{aligned}}$ donde el primer y segundo paso sigue de la definición de información mutua y entropía condicional respectivamente. La entropía en la salida para un símbolo de entrada dado y fijo (${displaystyle H(Y habitX=x)}$) equivale a la función binaria entropía, que conduce a la tercera línea y esto puede ser más simplificado. En la última línea, sólo el primer término ${displaystyle H(Y)}$ depende de la distribución de entrada ${displaystyle p_{X}(x)}$. La entropía de una variable binaria es a la mayoría de 1 bit, y la igualdad se alcanza si su distribución de probabilidad es uniforme. Por lo tanto, basta con exhibir una distribución de insumos que produce una distribución uniforme de probabilidad para la salida ${displaystyle Sí.$. Para ello, tenga en cuenta que es una propiedad de cualquier canal simétrico binario que una distribución uniforme de probabilidad de los resultados de entrada en una distribución uniforme de probabilidad de la salida. De ahí el valor ${displaystyle H(Y)}$ será 1 cuando elijamos una distribución uniforme para ${displaystyle p_{X}(x)}$. Concluimos que la capacidad de canal para nuestro canal simétrico binario es ${displaystyle C_{text{BSC}=1-operatorname {H} _{text{b}(p)}$.

Teorema de codificación de canales ruidosos

El teorema de codificación ruidoso-canal de Shannon da un resultado sobre la tasa de información que se puede transmitir a través de un canal de comunicación con error arbitrariomente bajo. Estudiamos el caso particular ${displaystyle {text{BSC}_{p}}$.

El ruido ${displaystyle e}$ que caracteriza ${displaystyle {text{BSC}_{p}}$ es una variable aleatoria que consiste en bits aleatorios independientes (n se define a continuación) donde cada bit aleatorio es un ${displaystyle 1}$ con probabilidad ${displaystyle p}$ y a ${displaystyle 0}$ con probabilidad ${displaystyle 1-p}$. Indicamos esto escribiendo "${displaystyle ein {text{BSC}_{p}$".

Lo que este teorema realmente implica es, un mensaje cuando es elegido ${displaystyle {0,1}} {cH00}$, codificado con una función de codificación aleatoria ${displaystyle E}$, y enviado a través de un ruido ${displaystyle {text{BSC}_{p}}$, hay una probabilidad muy alta de recuperar el mensaje original por decodificación, si ${displaystyle k}$ o en efecto la tasa del canal está ligada por la cantidad indicada en el teorema. La probabilidad de decodificación de errores es exponencialmente pequeña.

Prueba

El teorema se puede probar directamente con un método probabilístico. Considerar una función de codificación ${displaystyle E: '{0,1} {k}to {0,1} {n}}$ que se selecciona al azar. Esto significa que para cada mensaje ${displaystyle min {0,1}} {k}}$, el valor ${displaystyle E(m)in {0,1}{n}}$ se selecciona al azar (con iguales probabilidades). Para una función de codificación dada ${displaystyle E}$, la función de decodificación ${displaystyle D:{0,1}n}to {0,1}{k}$ se especifica como sigue: dado cualquier palabra clave recibida ${displaystyle yin {0,1}} {n}}$, encontramos el mensaje ${displaystyle min {0,1}} {k}}$ tal que la distancia Hamming ${displaystyle Delta (y,E(m)}$ es lo más pequeño posible (con lazos rotos arbitrariamente). ()${displaystyle D}$ se llama una función de decodificación de probabilidad máxima.)

La prueba continúa mostrando que al menos una de esas opciones ${displaystyle (E,D)}$ satisface la conclusión del teorema, por integración sobre las probabilidades. Suppose ${displaystyle p}$ y ${displaystyle epsilon }$ están arreglados. Primero mostramos eso, para un fijo ${displaystyle min {0,1}} {k}}$ y ${displaystyle E}$ elegido aleatoriamente, la probabilidad de fracaso ${displaystyle {text{BSC}_{p}}$ el ruido es exponencialmente pequeño n. En este punto, la prueba funciona para un mensaje fijo ${displaystyle m}$. A continuación ampliamos este resultado para trabajar para todos los mensajes ${displaystyle m}$. Lo logramos eliminando la mitad de las palabras clave del código con el argumento de que la prueba de la probabilidad de decodificación de errores sostiene por lo menos la mitad de las palabras clave. Este último método se llama expurgación. Esto da el proceso total el nombre codificación al azar con expurgación.

Continuación de la prueba (sketch)

Corrección ${displaystyle p}$ y ${displaystyle epsilon }$. Dado un mensaje fijo ${displaystyle min {0,1}} {k}}$, necesitamos estimar el valor esperado de la probabilidad de la palabra clave recibida junto con el ruido no devuelve ${displaystyle m}$ en decodificación. Es decir, necesitamos estimar: ${displaystyle mathbb {E} _{E}left[Pr _{ein {text{BSC}_{p}} [D(E(m)+e)neq m]right].}$ Vamos ${displaystyle y}$ sea la palabra clave recibida. Para la palabra clave decodificada ${displaystyle D(y)}$ no ser igual al mensaje ${displaystyle m}$, uno de los siguientes eventos debe ocurrir: ${displaystyle y}$ no miente dentro de la bola de Hamming de radio ${displaystyle (p+epsilon)n}$ centrado en ${displaystyle E(m)}$. Esta afección se utiliza principalmente para facilitar los cálculos. Hay otro mensaje ${displaystyle m'in {0,1} {k}}$ tales que ${displaystyle Delta (y,E(m'))leqslant Delta (y,E(m)}$. En otras palabras, los errores debido al ruido llevan la palabra clave transmitida más cerca de otro mensaje codificado. Podemos aplicar el límite de Chernoff para asegurar la no ocurrencia del primer evento; obtenemos: ${displaystyle Pr_{ein {text{BSC}}_{p}[Delta (y,E(m)] título(p+epsilon)n]leqslant 2^{-{epsilon ^{2}n}$ Esto es exponencialmente pequeño para grande ${displaystyle n}$ (reconozca eso ${displaystyle epsilon }$ se fija). Para el segundo evento, observamos que la probabilidad de que ${displaystyle E(m')in B(y,(p+epsilon)n)}$ es ${displaystyle {text{Vol}(B(y,(p+epsilon)n)/2^{n}$ Donde ${displaystyle B(x,r)}$ es la bola de Hamming de radio ${displaystyle r}$ centrado en vector ${displaystyle x}$ y ${displaystyle {text{Vol}(B(x,r)}$ es su volumen. Usando la aproximación para estimar el número de palabras clave en la bola Hamming, tenemos ${displaystyle {text{Vol}(B(y,(p+epsilon)n)approx 2^{H(p)n}$. Por lo tanto, la probabilidad anterior equivale a ${displaystyle 2^{H(p)n}/2}=2{H(p)n-n}$. Ahora, usando el vínculo sindical, podemos atar la existencia de tal ${displaystyle m'in {0,1} {k}}$ por ${displaystyle leq 2^{k+H(p)n-n}$ que es ${displaystyle 2^{-Omega (n)}$, como desea la elección de ${displaystyle k}$.

Continuación de la prueba (detallada)

Desde el análisis anterior, calculamos la probabilidad del evento de que la palabra clave decodificada más el ruido del canal no es el mismo que el mensaje original enviado. Presentaremos algunos símbolos aquí. Vamos ${displaystyle p(y habitE(m)}$ denota la probabilidad de recibir la palabra clave ${displaystyle y}$ dada la palabra clave ${displaystyle E(m)}$ fue enviado. Vamos ${displaystyle B_{0}$ denota ${displaystyle B(E(m),(p+epsilon)n). }$ ${displaystyle {begin{aligned} Pr _{ein {text{BSC}}_{p}[D(E(m)+e)neq m] implica=sum _{yin {0,1} {n}p(y habitE(m)))cdot 1_{D(y)neq m}\\\leqslant sum _{ynotin] B_{0}p(y sometidaE(m))cdot 1_{D(y)neq m}+sum _{yin ¿Por qué?$ Conseguimos la última desigualdad mediante nuestro análisis usando el Chernoff ligado arriba. Ahora tomando la expectativa de ambos lados tenemos, ${displaystyle {begin{aligned}mathbb {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif}* ^{2}n}+sum _{yin B_{0}mathbb {E} [1_{D(y)neq m}] distantesum _{yin B_{0}p(y pacienciaE(m))leqslant 1\\\leqslant 2^{-{epsilon ¿Qué? {E} [1_{D(y)neq m}]leqslant 2^{k+H(p+epsilon)n-n}{text{ (see above)}\\leqslant 2^{-delta n}end{aligned}}}}}}}$ seleccionando apropiadamente el valor ${displaystyle delta }$. Desde el límite anterior cada uno Mensaje, tenemos ${displaystyle mathbb {fnMicrosoft Sans Serif} [E] _{E}left[Pr _{ein {text{BSC}_{p}left[D(E(m)+e)right]neq mright]right]leqslant 2^{-delta No.$ Ahora podemos cambiar el orden de la suma en la expectativa con respecto al mensaje y la elección de la función de codificación ${displaystyle E}$. Por lo tanto: ${displaystyle mathbb {fnMicrosoft Sans Serif} {E} _{m}left[Pr _{ein {text{BSC}_{p}left[D(E(m)+e)right]neq mright]right]leqslant 2^{-delta No.$ Por lo tanto, en conclusión, por método probabilístico, tenemos alguna función de codificación ${displaystyle E^{*}$ y una función de decodificación correspondiente ${displaystyle D^{*}$ tales que ${displaystyle mathbb {E} {m}left[cH00} Pr _{ein {text{BSC}}_{p}left[D^{*}(E^{*}(m)+e)neq mright]right]leqslant 2^{-delta No.$ En este punto, la prueba funciona para un mensaje fijo ${displaystyle m}$. Pero necesitamos asegurarnos de que el límite anterior se mantenga Todos los mensajes ${displaystyle m}$ simultáneamente. Para eso, vamos a ordenar el ${displaystyle 2^{k}$ mensajes por sus probabilidades de error de decodificación. Ahora al aplicar la desigualdad de Markov, podemos mostrar la probabilidad de decodificación de errores para el primero ${displaystyle 2^{k-1}$ mensajes a la mayoría ${displaystyle 2cdot 2^{-delta No.$. Así, a fin de confirmar que la anterior obligación de mantener cada uno Mensaje ${displaystyle m}$Podríamos recortar el último ${displaystyle 2^{k-1}$ mensajes de la orden orden ordenada. Esto esencialmente nos da otra función de codificación ${displaystyle E'$ con función de decodificación correspondiente ${displaystyle D'$ con una probabilidad de error de decodificación ${displaystyle 2^{-delta No.$ con la misma tarifa. Tomando ${displaystyle delta}$ ser igual a ${displaystyle delta -{tfrac {1}{n}}$ vinculamos la probabilidad de error de decodificación a ${displaystyle 2^{-delta 'n'$. Este proceso de expurgación completa la prueba.

Converso del teorema de capacidad de Shannon

El contrario del teorema de capacidad establece esencialmente que ${displaystyle 1-H(p)}$ es la mejor tarifa que se puede lograr sobre un canal simétrico binario. Formalmente el teorema declara:

La intuición detrás de la prueba es sin embargo mostrar el número de errores para crecer rápidamente a medida que la tasa crece más allá de la capacidad del canal. La idea es que el remitente genera mensajes de dimensión ${displaystyle k}$, mientras el canal ${displaystyle {text{BSC}_{p}}$ introduce errores de transmisión. Cuando la capacidad del canal es ${displaystyle H(p)}$, el número de errores es típicamente ${displaystyle 2^{H(p+epsilon)n}$ para un código de longitud de bloque ${displaystyle n}$. El número máximo de mensajes es ${displaystyle 2^{k}$. La salida del canal por otro lado tiene ${displaystyle 2^{n}$ valores posibles. Si hay alguna confusión entre dos mensajes, es probable que ${displaystyle 2^{k}2^{H(p+epsilon)n}geq 2^{n}$. Por lo tanto, tendríamos ${displaystyle kgeq lceil (1-H(p+epsilon)n)rceil }$, un caso que nos gustaría evitar mantener la probabilidad de decodificación de error exponencialmente pequeña.

Códigos

Muy recientemente, se ha trabajado mucho y también se está haciendo para diseñar códigos de corrección de errores explícitos para lograr las capacidades de varios canales de comunicación estándar. La motivación detrás del diseño de dichos códigos es relacionar la tasa del código con la fracción de errores que puede corregir.

El enfoque detrás del diseño de códigos que satisfacen las capacidades de canal ${displaystyle {text{BSC}}}$ o el canal de borrado binario ${displaystyle {text{BEC}}$ han sido corregir un menor número de errores con una alta probabilidad, y lograr la mayor tasa posible. El teorema de Shannon nos da la mejor tasa que se podría lograr con un ${displaystyle {text{BSC}_{p}}$, pero no nos da una idea de ningún código explícito que logre. De hecho, estos códigos se construyen normalmente para corregir sólo una pequeña fracción de errores con una alta probabilidad, pero lograr una muy buena tasa. El primer código de este tipo se debió a George D. Forney en 1966. El código es un código concatenado concatenando dos tipos diferentes de códigos.

Código de Forney

Forney construyó un código concatenado ${displaystyle C^{*}=C_{out}circ C_{text{in}}$ para lograr la capacidad del teorema de codificación ruidoso-canal ${displaystyle {text{BSC}_{p}}$. En su código,

• El código exterior ${displaystyle C_{text{out}}$ es un código de longitud de bloque ${displaystyle N}$ y tasa ${displaystyle 1-{frac {epsilon } {2}}$ sobre el terreno ${displaystyle F_{2^{k}}$, y ${displaystyle k=O(log N)}$. Además, tenemos un algoritmo de decodificación ${displaystyle D_{text{out}}$ para ${displaystyle C_{text{out}}$ que puede corregir ${displaystyle gamma }$ fracción de los peores errores de caso y se ejecuta en ${displaystyle t_{text{out}(N)}$ tiempo.
• El código interno ${displaystyle C_{text{in}}$ es un código de longitud de bloque ${displaystyle n}$, dimensión ${displaystyle k}$, y una tasa de ${displaystyle 1-H(p)-{frac {epsilon } {2}}$. Además, tenemos un algoritmo de decodificación ${displaystyle D_{text{in}}$ para ${displaystyle C_{text{in}}$ con una probabilidad de error de decodificación ${displaystyle {frac {gamma} } {2}}$ sobre ${displaystyle {text{BSC}_{p}}$ y corre ${displaystyle t_{text{in}(N)}$ tiempo.

Para el código exterior ${displaystyle C_{text{out}}$, un código Reed-Solomon habría sido el primer código en tener en cuenta. Sin embargo, veríamos que la construcción de dicho código no puede hacerse en el tiempo polinomio. Por eso se utiliza un código lineal binario ${displaystyle C_{text{out}}$.

Para el código interno ${displaystyle C_{text{in}}$ encontramos un código lineal buscando exhaustivamente el código lineal de longitud de bloque ${displaystyle n}$ y dimensión ${displaystyle k}$, cuyo índice cumple la capacidad de ${displaystyle {text{BSC}_{p}}$, por el teorema de codificación ruidoso-canal.

La tasa ${displaystyle R(C^{*})=R(C_{text{in})times R(C_{text{out})=(1-{frac {epsilon }{2})(1-H(p)-{epsilon }{2})gq 1-H(p)-epsilon$ que casi conoce ${displaystyle {text{BSC}_{p}}$ capacidad. Observamos además que la codificación y decodificación de ${displaystyle C^{*}$ se puede hacer en el tiempo polinomio con respecto a ${displaystyle N}$. De hecho, la codificación ${displaystyle C^{*}$ toma tiempo ${displaystyle O(N^{2})+O(Nk^{2})=O(N^{2})}$. Además, el algoritmo de decodificación descrito toma tiempo ${displaystyle Nt_{text{in}(k)+t_{text{out}(N)=N^{O(1)}$ mientras ${displaystyle t_{text{out}(N)=N^{O(1)}$; y ${displaystyle t_{text{in}(k)=2^{O(k)}$.

Probabilidad de error de decodificación

Un algoritmo de decodificación natural para ${displaystyle C^{*}$ es:

• Assume ${displaystyle Y... }=D_{text{in}(y_{i}),quad iin (0,N)}$
• Ejecutar ${displaystyle D_{text{out}}$ on ${displaystyle y^{prime }=(y_{1} {prime }ldots y_{N} {prime }}}$

Tenga en cuenta que cada bloque de código para ${displaystyle C_{text{in}}$ se considera un símbolo para ${displaystyle C_{text{out}}$. Ahora desde la probabilidad de error en cualquier índice ${displaystyle i}$ para ${displaystyle D_{text{in}}$ es en la mayoría ${fnMicrosoft {fnMicrosoft {fnMicrosoft {fnMicrosoft {\fnMicrosoft {\\fnMicrosoft {\\fnMicrosoft {fnMicrosoft {fnMicrosoft {\fnMicrosoft {\\fnMicrosoft {\fnMicrosoft {\\fnMicrosoft {\\\\\\\\\\fnMicrosoft {fnMicrosoft\\\\\\\\\\\\\\\\\\\fnMicrosoft\\\\\\\\\\fnMicrosoft\\\\\\\fnMicrosoft\\\\\\\\\\\fnMin } {2}}$ y los errores en ${displaystyle {text{BSC}_{p}}$ son independientes, el número esperado de errores ${displaystyle D_{text{in}}$ es en la mayoría ${fnMicrosoft {fnMicrosoft {fnMicrosoft {fnMicrosoft {\fnMicrosoft {\\fnMicrosoft {\\fnMicrosoft {fnMicrosoft {fnMicrosoft {\fnMicrosoft {\\fnMicrosoft {\fnMicrosoft {\\fnMicrosoft {\\\\\\\\\\fnMicrosoft {fnMicrosoft\\\\\\\\\\\\\\\\\\\fnMicrosoft\\\\\\\\\\fnMicrosoft\\\\\\\fnMicrosoft\\\\\\\\\\\fnMin No.$ por linearidad de expectativa. Ahora la aplicación de Chernoff límite, tenemos la probabilidad de error de más que ${displaystyle gamma N}$ errores que se producen ${displaystyle e^{frac {-gamma No.$. Desde el código exterior ${displaystyle C_{text{out}}$ puede corregir a la mayoría ${displaystyle gamma N}$ errores, esta es la probabilidad de decodificación de errores ${displaystyle C^{*}$. Esto cuando se expresa en términos asintoticos, nos da una probabilidad de error ${displaystyle 2^{-Omega (gamma N)}$. Así, la probabilidad de error de decodificación alcanzada ${displaystyle C^{*}$ es exponencialmente pequeño como el teorema de codificación ruidoso-canal.

Hemos dado una técnica general para construir ${displaystyle C^{*}$. Para descripciones más detalladas en ${displaystyle C_{text{in}}$ y ${displaystyle C_{text{out}}$ Por favor lea las siguientes referencias. Recientemente se han construido algunos otros códigos para lograr las capacidades. Los códigos LDPC han sido considerados con este propósito para su tiempo de decodificación más rápido.

Aplicaciones

El canal simétrico binario puede modelar una unidad de disco utilizada para el almacenamiento de memoria: la entrada del canal representa un bit que se escribe en el disco y la salida corresponde al bit que se lee más tarde. El error puede deberse a que la magnetización cambia, el ruido de fondo o el cabezal de escritura comete un error. Otros objetos que el canal simétrico binario puede modelar incluyen una línea de comunicación telefónica o de radio o una división celular, a partir de la cual las células hijas contienen información de ADN de su célula madre.

Los teóricos suelen utilizar este canal porque es uno de los canales ruidosos más sencillos de analizar. Muchos problemas de la teoría de la comunicación se pueden reducir a un BSC. Por el contrario, ser capaz de transmitir de manera efectiva sobre el BSC puede dar lugar a soluciones para canales más complicados.