Binary symmetric channel
A binary symmetric channel (or BSC p ) is a common communications channel model used in coding theory and information theory.
≈ 6 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
A binary symmetric channel (or BSC p ) is a common communications channel model used in coding theory and information theory. In this model, a transmitter wishes to send a bit (a zero or a one), and the receiver will receive a bit. The bit will be "flipped" with a "crossover probability" of p, and otherwise is received correctly.
This model can be applied to varied communication channels such as telephone lines or disk drive storage. The noisy-channel coding theorem applies to BSC p , saying that information can be transmitted at any rate up to the channel capacity with arbitrarily low error.
The channel capacity is 1 - \operatorname H_\text{b}(p) bits, where \operatorname H_\text{b} is the binary entropy function. Codes including Forney's code have been designed to transmit information efficiently across the channel. \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{align} It is assumed that 0 \le p \le 1/2 .
If p > 1/2 , then the receiver can swap the output (interpret 1 when it sees 0, and vice versa) and obtain an equivalent channel with crossover probability 1 - p \le 1/2 . \ C_{\text{BSC}} = 1 - \operatorname H_\text{b}(p), where \operatorname H_\text{b}(p) is the binary entropy function, defined by: \operatorname H_\text{b}(x)=x\log_2\frac{1}{x}+(1-x)\log_2\frac{1}{1-x}
Proof
The theorem can be proved directly with a probabilistic method. Consider an encoding function E: \{0,1\}^k \to \{0,1\}^n that is selected at random. This means that for each message m \in \{0,1\}^k , the value E(m) \in \{0,1\}^n is selected at random (with equal probabilities).
For a given encoding function E , the decoding function D:\{0,1\}^n \to \{0,1\}^k is specified as follows: given any received codeword y \in \{0,1\}^n , we find the message m\in\{0,1\}^{k} such that the Hamming distance \Delta(y, E(m)) is as small as possible (with ties broken arbitrarily). ( D is called a maximum likelihood decoding function.)
The proof continues by showing that at least one such choice (E,D) satisfies the conclusion of theorem, by integration over the probabilities. Suppose p and \epsilon are fixed.
First we show that, for a fixed m \in \{0,1\}^{k} and E chosen randomly, the probability of failure over \text{BSC}_p noise is exponentially small in n. At this point, the proof works for a fixed message m . Next we extend this result to work for all messages m . We achieve this by eliminating half of the codewords from the code with the argument that the proof for the decoding error probability holds for at least half of the codewords. The latter method is called expurgation.
This gives the total process the name random coding with expurgation. Forney constructed a concatenated code C^{*} = C_\text{out} \circ C_\text{in} to achieve the capacity of the noisy-channel coding theorem for \text{BSC}_p . In his code, The outer code C_\text{out} is a code of block length N and rate 1-\frac{\epsilon}{2} over the field F_{2^k} , and k = O(\log N) . Additionally, we have a decoding algorithm D_\text{out} for C_\text{out} which can correct up to \gamma fraction of worst case errors and runs in t_\text{out}(N) time.
The inner code C_\text{in} is a code of block length n , dimension k , and a rate of 1 - H(p) - \frac{\epsilon}{2} . Additionally, we have a decoding algorithm D_\text{in} for C_\text{in} with a decoding error probability of at most \frac{\gamma}{2} over \text{BSC}_p and runs in t_\text{in}(N) time.
For the outer code 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 C_\text{out} .
For the inner code C_\text{in} we find a linear code by exhaustively searching from the linear code of block length n and dimension k , whose rate meets the capacity of \text{BSC}_p , by the noisy-channel coding theorem. The rate 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 \text{BSC}_p capacity.
We further note that the encoding and decoding of C^{*} can be done in polynomial time with respect to N . As a matter of fact, encoding C^{*} takes time O(N^{2})+O(Nk^{2}) = O(N^{2}) . Further, the decoding algorithm described takes time Nt_\text{in}(k) + t_\text{out}(N) = N^{O(1)} as long as t_\text{out}(N) = N^{O(1)} ; and t_\text{in}(k) = 2^{O(k)} .
Assume y_{i}^{\prime} = D_\text{in}(y_i), \quad i \in (0, N) Execute D_\text{out} on y^{\prime} = (y_1^{\prime} \ldots y_N^{\prime}) Note that each block of code for C_\text{in} is considered a symbol for C_\text{out} . Now since the probability of error at any index i for D_\text{in} is at most \tfrac{\gamma}{2} and the errors in \text{BSC}_p are independent, the expected number of errors for D_\text{in} is at most \tfrac{\gamma N}{2} by linearity of expectation.
Now applying Chernoff bound, we have bound error probability of more than \gamma N errors occurring to be e^\frac{-\gamma N}{6} . Since the outer code C_\text{out} can correct at most \gamma N errors, this is the decoding error probability of C^{*} . This when expressed in asymptotic terms, gives us an error probability of 2^{-\Omega(\gamma N)} .
Thus the achieved decoding error probability of C^{*} is exponentially small as the noisy-channel coding theorem. We have given a general technique to construct C^{*} . For more detailed descriptions on C_\text{in} and 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.
Notes
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
Text derived from https://en.wikipedia.org/w/index.php?oldid=1365609566 under CC BY-SA 4.0; modifications have been made.