Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Binary symmetric channel
Summary
A binary symmetric channel (or BSCp) 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 BSCp, saying that information can be transmitted at any rate up to the channel capacity with arbitrarily low error. The channel capacity is bits, where is the binary entropy function. Codes including Forney's code have been designed to transmit information efficiently across the channel.
A binary symmetric channel with crossover probability , denoted by BSCp, is a channel with binary input and binary output and probability of error . That is, if is the transmitted random variable and the received variable, then the channel is characterized by the conditional probabilities:
It is assumed that . If , then the receiver can swap the output (interpret 1 when it sees 0, and vice versa) and obtain an equivalent channel with crossover probability .
The channel capacity of the binary symmetric channel, in bits, is:
where is the binary entropy function, defined by:
{| class="toccolours collapsible collapsed" width="80%" style="text-align:left"
!Proof
|-
|The capacity is defined as the maximum mutual information between input and output for all possible input distributions :
The mutual information can be reformulated as
where the first and second step follows from the definition of mutual information and conditional entropy respectively. The entropy at the output for a given and fixed input symbol () equals the binary entropy function, which leads to the third line and this can be further simplified.
In the last line, only the first term depends on the input distribution . The entropy of a binary variable is at most 1 bit, and equality is attained if its probability distribution is uniform.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related courses (4)
COM-404: Information theory and coding
The mathematical principles of communication that govern the compression and transmission of data and the design of efficient methods of doing so.
CS-308: Introduction to quantum computation
The course introduces the paradigm of quantum computation in an axiomatic way. We introduce the notion of quantum bit, gates, circuits and we treat the most important quantum algorithms. We also touch
COM-102: Advanced information, computation, communication II
Text, sound, and images are examples of information sources stored in our computers and/or communicated over the Internet. How do we measure, compress, and protect the informatin they contain?