Canal simétrico binario

Este artículo incluye una lista de referencias generales , pero permanece en gran parte sin verificar porque carece de suficientes citas en línea correspondientes . Ayude a mejorar este artículo introduciendo citas más precisas. ( Marzo de 2013 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla )

Un canal binario simétrico (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 uno) y el receptor recibirá un bit. El bit se "invertirá" con una " probabilidad de cruce " de p , y de lo contrario se recibirá correctamente. Este modelo se puede aplicar a diversos canales de comunicación, como líneas telefónicas o almacenamiento en unidad de disco .

El teorema de codificación de canal ruidoso se aplica al BSC _p , diciendo que la información se puede transmitir a cualquier velocidad hasta la capacidad del canal con un error arbitrariamente bajo. La capacidad del canal es bits, donde es la función de entropía binaria . Los códigos, incluido el código de Forney, se han diseñado para transmitir información de manera eficiente a través del canal.${\displaystyle 1-\operatorname {H} _{\text{b}}(p)}$${\displaystyle \operatorname {H} _{\text{b}}}$

Definición

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

Un canal simétrico binario con probabilidad de cruce , denotado por BSC _p , es un canal con entrada binaria y salida binaria y probabilidad de error . Es decir, si es la variable aleatoria transmitida y la variable recibida, entonces el canal se caracteriza por las probabilidades condicionales : ^[1]${\displaystyle p}$${\displaystyle p}$${\displaystyle X}$${\displaystyle Y}$

${\displaystyle {\begin{aligned}\operatorname {Pr} [Y=0|X=0]&=1-p\\\operatorname {Pr} [Y=0|X=1]&=p\\\operatorname {Pr} [Y=1|X=0]&=p\\\operatorname {Pr} [Y=1|X=1]&=1-p\end{aligned}}}$

Se asume eso . Si , entonces el receptor puede intercambiar la salida (interpretar 1 cuando ve 0, y viceversa) y obtener un canal equivalente con probabilidad de cruce .${\displaystyle 0\leq p\leq 1/2}$${\displaystyle p>1/2}$${\displaystyle 1-p\leq 1/2}$

Capacidad

La capacidad de canal del canal simétrico binario, en bits , es: ^[2]

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

donde es la función de entropía binaria , definida por: ^[2]${\displaystyle \operatorname {H} _{\text{b}}(p)}$

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

Prueba [3]

La capacidad se define como la máxima información mutua entre la entrada y la salida para todas las posibles distribuciones de entrada :${\displaystyle p_{X}(x)}$ ${\displaystyle C=\max _{p_{X}(x)}\left\{\,I(X;Y)\,\right\}}$ La información mutua se puede reformular como ${\displaystyle {\begin{aligned}I(X;Y)&=H(Y)-H(Y|X)\\&=H(Y)-\sum _{x\in \{0,1\}}{p_{X}(x)H(Y|X=x)}\\&=H(Y)-\sum _{x\in \{0,1\}}{p_{X}(x)}\operatorname {H} _{\text{b}}(p)\\&=H(Y)-\operatorname {H} _{\text{b}}(p),\end{aligned}}}$ donde el primer y segundo paso se 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 determinado y fijo ( ) es igual a la función de entropía binaria, que conduce a la tercera línea y esto se puede simplificar aún más.${\displaystyle H(Y|X=x)}$ En la última línea, solo el primer término depende de la distribución de entrada . La entropía de una variable binaria es como máximo de 1 bit y se logra la igualdad si su distribución de probabilidad es uniforme. Por lo tanto, es suficiente exhibir una distribución de entrada que produzca una distribución de probabilidad uniforme para la salida . Para esto, tenga en cuenta que es una propiedad de cualquier canal simétrico binario que una distribución de probabilidad uniforme de la entrada da como resultado una distribución de probabilidad uniforme de la salida. Por tanto, el valor será 1 cuando elijamos una distribución uniforme para . Concluimos que la capacidad del canal para nuestro canal simétrico binario es .${\displaystyle H(Y)}$${\displaystyle p_{X}(x)}$${\displaystyle Y}$${\displaystyle H(Y)}$${\displaystyle p_{X}(x)}$${\displaystyle C_{\text{BSC}}=1-\operatorname {H} _{\text{b}}(p)}$

Teorema de codificación de canal ruidoso

El teorema de codificación de canal ruidoso 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 un error arbitrariamente bajo. Estudiamos el caso particular de .${\displaystyle {\text{BSC}}_{p}}$

El ruido que caracteriza es una variable aleatoria que consta de n bits aleatorios independientes (n se define a continuación) donde cada bit aleatorio es a con probabilidad y a con probabilidad . Lo indicamos escribiendo " ".${\displaystyle e}$${\displaystyle {\text{BSC}}_{p}}$${\displaystyle 1}$${\displaystyle p}$${\displaystyle 0}$${\displaystyle 1-p}$${\displaystyle e\in {\text{BSC}}_{p}}$

Teorema  :  para todos todos , todos lo suficientemente grandes (dependiendo de y ), y todos , existe un par de funciones de codificación y decodificación y respectivamente, de modo que cada mensaje tiene la siguiente propiedad: ${\displaystyle p<{\tfrac {1}{2}},}$${\displaystyle 0<\epsilon <{\tfrac {1}{2}}-p}$${\displaystyle n}$${\displaystyle p}$${\displaystyle \epsilon }$${\displaystyle k\leq \lfloor (1-H(p+\epsilon ))n\rfloor }$${\displaystyle E:\{0,1\}^{k}\to \{0,1\}^{n}}$${\displaystyle D:\{0,1\}^{n}\to \{0,1\}^{k}}$${\displaystyle m\in \{0,1\}^{k}}$

${\displaystyle \Pr _{e\in {\text{BSC}}_{p}}[D(E(m)+e)\neq m]\leq 2^{-{\delta }n}}$.

Lo que este teorema implica en realidad es que, cuando se selecciona un mensaje , se codifica con una función de codificación aleatoria y se envía a través de un ruido , existe una probabilidad muy alta de recuperar el mensaje original mediante la decodificación, si o en efecto la velocidad del canal es limitada por la cantidad indicada en el teorema. La probabilidad de error de decodificación es exponencialmente pequeña.${\displaystyle \{0,1\}^{k}}$${\displaystyle E}$${\displaystyle {\text{BSC}}_{p}}$${\displaystyle k}$

Prueba

El teorema se puede demostrar directamente con un método probabilístico . Considere una función de codificación que se selecciona al azar. Esto significa que para cada mensaje , el valor se selecciona al azar (con iguales probabilidades). Para una función de codificación dada , la función de decodificación se especifica de la siguiente manera: dada cualquier palabra de código recibida , encontramos el mensaje tal que la distancia de Hamming es lo más pequeña posible (con lazos rotos arbitrariamente). ( se denomina función de decodificación de máxima verosimilitud ).${\displaystyle E:\{0,1\}^{k}\to \{0,1\}^{n}}$${\displaystyle m\in \{0,1\}^{k}}$${\displaystyle E(m)\in \{0,1\}^{n}}$${\displaystyle E}$${\displaystyle D:\{0,1\}^{n}\to \{0,1\}^{k}}$${\displaystyle y\in \{0,1\}^{n}}$${\displaystyle m\in \{0,1\}^{k}}$ ${\displaystyle \Delta (y,E(m))}$${\displaystyle D}$

La demostración continúa mostrando que al menos una de esas opciones satisface la conclusión del teorema, por integración sobre las probabilidades. Supongamos que y son fijos. Primero mostramos que, para un fijo y elegido al azar, la probabilidad de falla por ruido es exponencialmente pequeña en n . En este punto, la prueba funciona para un mensaje fijo . A continuación, ampliamos este resultado para que funcione con todos los mensajes . Logramos esto eliminando la mitad de las palabras de código del código con el argumento de que la prueba de la probabilidad de error de decodificación es válida para al menos la mitad de las palabras de código. El último método se llama expurgación. Esto le da al proceso total el nombre de codificación aleatoria con expurgación .${\displaystyle (E,D)}$${\displaystyle p}$${\displaystyle \epsilon }$${\displaystyle m\in \{0,1\}^{k}}$${\displaystyle E}$${\displaystyle {\text{BSC}}_{p}}$${\displaystyle m}$${\displaystyle m}$

Continuación de la prueba (croquis)

Arreglar y . Dado un mensaje fijo , necesitamos estimar el valor esperado de la probabilidad de que la palabra de código recibida junto con el ruido no se devuelva en la decodificación. Es decir, necesitamos estimar:${\displaystyle p}$${\displaystyle \epsilon }$${\displaystyle m\in \{0,1\}^{k}}$${\displaystyle m}$ ${\displaystyle \mathbb {E} _{E}\left[\Pr _{e\in {\text{BSC}}_{p}}[D(E(m)+e)\neq m]\right].}$ Sea la palabra en clave recibida. Para que la palabra de código decodificada no sea igual al mensaje , debe ocurrir uno de los siguientes eventos:${\displaystyle y}$${\displaystyle D(y)}$${\displaystyle m}$ ${\displaystyle y}$no se encuentra dentro de la bola de Hamming de radio centrada en . Esta condición se utiliza principalmente para facilitar los cálculos.${\displaystyle (p+\epsilon )n}$${\displaystyle E(m)}$ Hay otro mensaje como ese . En otras palabras, los errores debidos al ruido acercan la palabra de código transmitida a otro mensaje codificado.${\displaystyle m'\in \{0,1\}^{k}}$${\displaystyle \Delta (y,E(m'))\leqslant \Delta (y,E(m))}$ Podemos aplicar el límite de Chernoff para asegurar la no ocurrencia del primer evento; obtenemos: ${\displaystyle Pr_{e\in {\text{BSC}}_{p}}[\Delta (y,E(m))>(p+\epsilon )n]\leqslant 2^{-{\epsilon ^{2}}n}.}$ Esto es exponencialmente pequeño para grande (recuerde que es fijo).${\displaystyle n}$${\displaystyle \epsilon }$ Para el segundo evento, observamos que la probabilidad de que es dónde está la bola de Hamming de radio centrada en el vector y es su volumen. Usando la aproximación para estimar el número de palabras de código en la bola de Hamming, tenemos . Por tanto, la probabilidad anterior asciende a . Ahora, usando el límite de unión , podemos establecer el límite superior de la existencia de tal por el cual es , según lo deseado por la elección de .${\displaystyle E(m')\in B(y,(p+\epsilon )n)}$${\displaystyle {\text{Vol}}(B(y,(p+\epsilon )n)/2^{n}}$${\displaystyle B(x,r)}$${\displaystyle r}$${\displaystyle x}$${\displaystyle {\text{Vol}}(B(x,r))}$${\displaystyle {\text{Vol}}(B(y,(p+\epsilon )n))\approx 2^{H(p)n}}$${\displaystyle 2^{H(p)n}/2^{n}=2^{H(p)n-n}}$${\displaystyle m'\in \{0,1\}^{k}}$${\displaystyle \leq 2^{k+H(p)n-n}}$${\displaystyle 2^{-\Omega (n)}}$${\displaystyle k}$

Continuación de la prueba (detallada)

A partir del análisis anterior, calculamos la probabilidad del evento de que la palabra de código decodificada más el ruido del canal no sea lo mismo que el mensaje original enviado. Introduciremos aquí algunos símbolos. Dejado denotar la probabilidad de recibir la palabra de código , dado que la palabra de código se envió. Vamos a denotar${\displaystyle p(y|E(m))}$${\displaystyle y}$${\displaystyle E(m)}$${\displaystyle B_{0}}$${\displaystyle B(E(m),(p+\epsilon )n).}$ ${\displaystyle {\begin{aligned}\Pr _{e\in {\text{BSC}}_{p}}[D(E(m)+e)\neq m]&=\sum _{y\in \{0,1\}^{n}}p(y|E(m))\cdot 1_{D(y)\neq m}\\&\leqslant \sum _{y\notin B_{0}}p(y|E(m))\cdot 1_{D(y)\neq m}+\sum _{y\in B_{0}}p(y|E(m))\cdot 1_{D(y)\neq m}\\&\leqslant 2^{-{\epsilon ^{2}}n}+\sum _{y\in B_{0}}p(y|E(m))\cdot 1_{D(y)\neq m}\end{aligned}}}$ Obtenemos la última desigualdad mediante nuestro análisis utilizando el límite de Chernoff anterior. Ahora, teniendo en cuenta la expectativa de ambos lados, tenemos, ${\displaystyle {\begin{aligned}\mathbb {E} _{E}\left[\Pr _{e\in {\text{BSC}}_{p}}[D(E(m)+e)\neq m]\right]&\leqslant 2^{-{\epsilon ^{2}}n}+\sum _{y\in B_{0}}p(y|E(m))\mathbb {E} [1_{D(y)\neq m}]\\&\leqslant 2^{-{\epsilon ^{2}}n}+\sum _{y\in B_{0}}\mathbb {E} [1_{D(y)\neq m}]&&\sum _{y\in B_{0}}p(y|E(m))\leqslant 1\\&\leqslant 2^{-{\epsilon ^{2}}n}+2^{k+H(p+\epsilon )n-n}&&\mathbb {E} [1_{D(y)\neq m}]\leqslant 2^{k+H(p+\epsilon )n-n}{\text{ (see above)}}\\&\leqslant 2^{-\delta n}\end{aligned}}}$ eligiendo adecuadamente el valor de . Dado que el límite anterior es válido para cada mensaje, tenemos${\displaystyle \delta }$ ${\displaystyle \mathbb {E} _{m}\left[\mathbb {E} _{E}\left[\Pr _{e\in {\text{BSC}}_{p}}\left[D(E(m)+e)\right]\neq m\right]\right]\leqslant 2^{-\delta n}.}$ 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 . Por eso:${\displaystyle E}$ ${\displaystyle \mathbb {E} _{E}\left[\mathbb {E} _{m}\left[\Pr _{e\in {\text{BSC}}_{p}}\left[D(E(m)+e)\right]\neq m\right]\right]\leqslant 2^{-\delta n}.}$ Por lo tanto, en conclusión, por método probabilístico, tenemos alguna función de codificación y una función de decodificación correspondiente tal que${\displaystyle E^{*}}$${\displaystyle D^{*}}$ ${\displaystyle \mathbb {E} _{m}\left[\Pr _{e\in {\text{BSC}}_{p}}\left[D^{*}(E^{*}(m)+e)\neq m\right]\right]\leqslant 2^{-\delta n}.}$ En este punto, la prueba funciona para un mensaje fijo . Pero debemos asegurarnos de que el límite anterior se aplique a todos los mensajes simultáneamente . Para eso, clasifiquemos los mensajes por sus probabilidades de error de decodificación. Ahora, aplicando la desigualdad de Markov , podemos mostrar la probabilidad de error de decodificación para que los primeros mensajes sean como máximo . Por lo tanto, para confirmar que lo anterior es válido para cada mensaje , podríamos simplemente recortar los últimos mensajes del orden ordenado. Esto esencialmente nos da otra función de codificación con una función de decodificación correspondiente con una probabilidad de error de decodificación de como máximo${\displaystyle m}$${\displaystyle m}$ ${\displaystyle 2^{k}}$${\displaystyle 2^{k-1}}$${\displaystyle 2\cdot 2^{-\delta n}}$${\displaystyle m}$${\displaystyle 2^{k-1}}$${\displaystyle E'}$${\displaystyle D'}$${\displaystyle 2^{-\delta n+1}}$con la misma tarifa. Tomando como igual a , ceñimos la probabilidad de error de decodificación a . Este proceso de expurgación completa la prueba.${\displaystyle \delta '}$${\displaystyle \delta -{\tfrac {1}{n}}}$${\displaystyle 2^{-\delta 'n}}$

Inverso del teorema de la capacidad de Shannon

El inverso del teorema de la capacidad establece esencialmente que es la mejor tasa que se puede lograr en un canal simétrico binario. Formalmente, el teorema establece:${\displaystyle 1-H(p)}$

Teorema  -  Si a continuación, la siguiente es cierto para cada codificación y decodificación de función : y : respectivamente: [ .${\displaystyle k}$ ${\displaystyle \geq }$ ${\displaystyle \lceil }$ ${\displaystyle (1-H(p+\epsilon )n)}$ ${\displaystyle \rceil }$${\displaystyle E}$${\displaystyle \{0,1\}^{k}}$ ${\displaystyle \rightarrow }$ ${\displaystyle \{0,1\}^{n}}$${\displaystyle D}$${\displaystyle \{0,1\}^{n}}$ ${\displaystyle \rightarrow }$ ${\displaystyle \{0,1\}^{k}}$${\displaystyle \Pr _{e\in {\text{BSC}}_{p}}}$${\displaystyle D(E(m)+e)}$ ${\displaystyle \neq }$ ${\displaystyle m]}$ ${\displaystyle \geq }$ ${\displaystyle {\frac {1}{2}}}$

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

Códigos

Very recently, a lot of work has been done and is also being done to design explicit error-correcting codes to achieve the capacities of several standard communication channels. The motivation behind designing such codes is to relate the rate of the code with the fraction of errors which it can correct.

The approach behind the design of codes which meet the channel capacities of ${\displaystyle {\text{BSC}}}$ or the binary erasure channel ${\displaystyle {\text{BEC}}}$ have been to correct a lesser number of errors with a high probability, and to achieve the highest possible rate. Shannon's theorem gives us the best rate which could be achieved over a ${\displaystyle {\text{BSC}}_{p}}$, but it does not give us an idea of any explicit codes which achieve that rate. In fact such codes are typically constructed to correct only a small fraction of errors with a high probability, but achieve a very good rate. The first such code was due to George D. Forney in 1966. The code is a concatenated code by concatenating two different kinds of codes.

Forney's code

Forney constructed a concatenated code ${\displaystyle C^{*}=C_{\text{out}}\circ C_{\text{in}}}$ to achieve the capacity of the noisy-channel coding theorem for ${\displaystyle {\text{BSC}}_{p}}$. In his code,

• The outer code ${\displaystyle C_{\text{out}}}$ is a code of block length ${\displaystyle N}$ and rate ${\displaystyle 1-{\frac {\epsilon }{2}}}$ over the field ${\displaystyle F_{2^{k}}}$, and ${\displaystyle k=O(\log N)}$. Additionally, we have a decoding algorithm ${\displaystyle D_{\text{out}}}$ for ${\displaystyle C_{\text{out}}}$ which can correct up to ${\displaystyle \gamma }$ fraction of worst case errors and runs in ${\displaystyle t_{\text{out}}(N)}$ time.
• The inner code ${\displaystyle C_{\text{in}}}$ is a code of block length ${\displaystyle n}$, dimension ${\displaystyle k}$, and a rate of ${\displaystyle 1-H(p)-{\frac {\epsilon }{2}}}$. Additionally, we have a decoding algorithm ${\displaystyle D_{\text{in}}}$ for ${\displaystyle C_{\text{in}}}$ with a decoding error probability of at most ${\displaystyle {\frac {\gamma }{2}}}$ over ${\displaystyle {\text{BSC}}_{p}}$ and runs in ${\displaystyle t_{\text{in}}(N)}$ time.

For the outer code ${\displaystyle C_{\text{out}}}$, a Reed-Solomon code would have been the first code to have come in mind. However, we would see that the construction of such a code cannot be done in polynomial time. This is why a binary linear code is used for ${\displaystyle C_{\text{out}}}$.

For the inner code ${\displaystyle C_{\text{in}}}$ we find a linear code by exhaustively searching from the linear code of block length ${\displaystyle n}$ and dimension ${\displaystyle k}$, whose rate meets the capacity of ${\displaystyle {\text{BSC}}_{p}}$, by the noisy-channel coding theorem.

The rate ${\displaystyle R(C^{*})=R(C_{\text{in}})\times R(C_{\text{out}})=(1-{\frac {\epsilon }{2}})(1-H(p)-{\frac {\epsilon }{2}})\geq 1-H(p)-\epsilon }$ which almost meets the ${\displaystyle {\text{BSC}}_{p}}$ capacity. We further note that the encoding and decoding of ${\displaystyle C^{*}}$ can be done in polynomial time with respect to ${\displaystyle N}$. As a matter of fact, encoding ${\displaystyle C^{*}}$ takes time ${\displaystyle O(N^{2})+O(Nk^{2})=O(N^{2})}$. Further, the decoding algorithm described takes time ${\displaystyle Nt_{\text{in}}(k)+t_{\text{out}}(N)=N^{O(1)}}$ as long as ${\displaystyle t_{\text{out}}(N)=N^{O(1)}}$; and ${\displaystyle t_{\text{in}}(k)=2^{O(k)}}$.

Decoding error probability

A natural decoding algorithm for ${\displaystyle C^{*}}$ is to:

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

Note that each block of code for ${\displaystyle C_{\text{in}}}$ is considered a symbol for ${\displaystyle C_{\text{out}}}$. Now since the probability of error at any index ${\displaystyle i}$ for ${\displaystyle D_{\text{in}}}$ is at most ${\displaystyle {\tfrac {\gamma }{2}}}$ and the errors in ${\displaystyle {\text{BSC}}_{p}}$ are independent, the expected number of errors for ${\displaystyle D_{\text{in}}}$ is at most ${\displaystyle {\tfrac {\gamma N}{2}}}$ by linearity of expectation. Now applying Chernoff bound, we have bound error probability of more than ${\displaystyle \gamma N}$ errors occurring to be ${\displaystyle e^{\frac {-\gamma N}{6}}}$. Since the outer code ${\displaystyle C_{\text{out}}}$ can correct at most ${\displaystyle \gamma N}$ errors, this is the decoding error probability of ${\displaystyle C^{*}}$. This when expressed in asymptotic terms, gives us an error probability of ${\displaystyle 2^{-\Omega (\gamma N)}}$. Thus the achieved decoding error probability of ${\displaystyle C^{*}}$ is exponentially small as the noisy-channel coding theorem.

We have given a general technique to construct ${\displaystyle C^{*}}$. For more detailed descriptions on ${\displaystyle C_{\text{in}}}$ and ${\displaystyle C_{\text{out}}}$ please read the following references. Recently a few other codes have also been constructed for achieving the capacities. LDPC codes have been considered for this purpose for their faster decoding time.^[4]

Applications

The binary symmetric channel can model a disk drive used for memory storage: the channel input represents a bit being written to the disk and the output corresponds to the bit later being read. Error could arise from the magnetization flipping, background noise or the writing head making an error. Other objects which the binary symmetric channel can model include a telephone or radio communication line or cell division, from which the daughter cells contain DNA information from their parent cell.^[5]

This channel is often used by theorists because it is one of the simplest noisy channels to analyze. Many problems in communication theory can be reduced to a BSC. Conversely, being able to transmit effectively over the BSC can give rise to solutions for more complicated channels.

See also

• Z channel

Notes

1. MacKay (2003), p. 4.
2. MacKay (2003), p. 15.
3. Cover & Thomas (1991), p. 187. sfnp error: no target: CITEREFCoverThomas1991 (help)
4. Richardson and Urbanke
5. MacKay (2003), p. 3–4.

References

• Thomas M. Cover; Joy A. Thomas (1991). Elements of Information Theory. Hoboken, New Jersey: Wiley. ISBN 978-0-471-24195-9.
• G. David Forney. Concatenated Codes. MIT Press, Cambridge, MA, 1966.
• Venkat Guruswamy's course on Error-Correcting Codes: Constructions and Algorithms, Autumn 2006.
• MacKay, David J.C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press. ISBN 0-521-64298-1.
• Atri Rudra's course on Error Correcting Codes: Combinatorics, Algorithms, and Applications (Fall 2007), Lectures 9, 10, 29, and 30.
• Madhu Sudan's course on Algorithmic Introduction to Coding Theory (Fall 2001), Lecture 1 and 2.
• A mathematical theory of communication C. E Shannon, ACM SIGMOBILE Mobile Computing and Communications Review.
• Modern Coding Theory by Tom Richardson and Rudiger Urbanke., Cambridge University Press