Communication over a Noisy Channel

What this lecture covers

This is a recitation-style problem that models a binary communication channel where each bit sent (0 or 1) can be flipped by noise. It builds on the multiplication rule, the law of total probability, independence, and Bayes' rule, applying them together to a single running example rather than introducing new theory.

After watching, you should be able to compute the probability that a single bit or a sequence of bits is transmitted correctly, evaluate a redundancy scheme that repeats each bit three times with majority-vote decoding, and use Bayes' rule to infer which bit was likely sent given a corrupted received sequence.

Key ideas

• Binary noisy channel: a sent bit (0 or 1) can be received correctly or flipped, with error probabilities epsilon_0 (for a sent 0) and epsilon_1 (for a sent 1).
• Law of total probability: the overall success probability is found by partitioning on whether a 0 or a 1 was sent, weighted by p and 1-p.
• Independence across bits: each bit in a sequence is transmitted through the channel independently, so the probability of a whole sequence succeeding is a product of per-bit probabilities.
• Redundancy with majority rule: sending each bit three times and decoding by majority vote can improve reliability, at the cost of tripling the number of bits sent.
• Bayes' rule for inference: given a received sequence, you can compute the probability that a particular bit was originally sent by combining the prior p with the channel's conditional probabilities.

Walkthrough

Setting up the channel model (0:00)

The instructor introduces the idea of a noisy communication channel using everyday examples like the internet or a phone call, then narrows to a binary channel that sends a single bit at a time. A sent 0 is received as 0 with probability 1 - epsilon_0 and flipped to 1 otherwise; a sent 1 is received as 1 with probability 1 - epsilon_1 and flipped to 0 otherwise. A random bit is 0 with probability p and 1 with probability 1-p.

Part a: probability of a single successful transmission (3:03)

Using a probability tree, the lecture identifies the two ways a transmission succeeds (0 to 0, or 1 to 1) and combines them with the law of total probability, giving p(1-epsilon_0) + (1-p)(1-epsilon_1).

Part b: a sequence of four bits (5:06)

For the sequence 1,0,1,1, the lecture argues that each bit transmits independently with the same error structure, so the probability of the whole sequence succeeding is the product of the four individual success probabilities, simplifying to (1-epsilon_0)(1-epsilon_1)^3.

Part c: redundancy and majority-rule decoding (9:16)

To improve reliability, each bit is sent three times, and the receiver decodes by majority vote among the three received bits. The lecture enumerates the four three-bit outcomes that decode to 0, then computes the probability that a sent 000 is correctly decoded by summing the probabilities of those four outcomes.

Part d: inferring the sent bit with Bayes' rule (13:24)

Given a received sequence of 1,0,1, the lecture computes the probability that 0 was actually sent, applying Bayes' rule with the law of total probability in the denominator, and working out each conditional probability from the channel model.

Before you watch

• Be comfortable with the multiplication rule, the law of total probability, and Bayes' rule from earlier lectures in this course.
• Know what independence between events means, since the sequence calculations depend on it.

Check your understanding

1. Why does the probability of a sequence of bits transmitting correctly factor into a product of individual bit probabilities?
2. How does the majority-rule decoding scheme use redundancy to potentially reduce the effective error rate?
3. In part d, why does the same term that appears in the numerator of Bayes' rule also appear in the denominator?
4. What trade-off does the lecture mention between adding redundancy and the channel's throughput?