Information Theory Lecture Notes

Introduction

• Aim: Make the topic accessible to both newcomers and experts in information theory.
• Focus: Not just solutions but also the intriguing questions posed by the field.
• Topic: Celebrating Claude Shannon's contributions to the field.

Background on Claude Shannon

• Born in 1916 in Gaylord, Michigan.
• His work coincided with the rise of telephony; communication was becoming more important.
• Contextual photos:
  • 1892: Alexander Graham Bell makes the first phone call from NYC to Chicago.
  • 1911: Overhead telephone wires causing issues in Pratt, Kansas.

The Nature of Communication

• Early communication was noisy and unreliable.
• Shannon's primary question: Can we communicate reliably in a noisy world?
• Simple model:
  • Sending bits (0s and 1s) through a channel.
  • Received bits may be corrupted due to noise.
  • Reliability question: Can we communicate with a certain error rate?

Redundancy in Communication

• Increasing reliability through redundancy (sending extra bits).
• Example:
  • Transmitting '0' as '000' and '1' as '111' to improve the chances of correct reception.
• Trade-off:
  • More redundancy = higher reliability, but lower transmission rate.
• Shannon's fundamental question:
  • Can we increase reliability without decreasing the information rate?

Shannon's Capacity Theorem

• Each communication channel has a maximum rate (capacity) that can be achieved reliably.
• Capacity: The highest rate at which information can be transmitted with an arbitrarily low probability of error.
• Characterization of capacity: Defined as a function of the relationship between input and output of the channel.

Applying Shannon's Work to Networks

• Transition from point-to-point communication to network communication.
• Networks consist of multiple transmitters and receivers.
• Capacity region: Collection of achievable rates in a network.
• Question: Is the capacity of individual channels sufficient to determine the capacity of the entire network?

Critical Insights on Network Capacity

• Understanding network capacity involves considering how edges (channels) interact.
• Removing a noisy channel may not always result in predictable changes to the capacity.
• Case study: Removing a wire and its impact on network capacity.
• Hypothesis: If a rate is achievable in a network with an edge of capacity Δ, will it still be achievable when that edge is removed?

Open Questions in Information Theory

• Current understanding does not fully solve the posed questions.
• Some examples support the hypothesis, but many cases remain unsolved.
• Discussions of existing bounds and their implications.

Cooperation and Communication

• Cooperation among nodes can significantly impact network capacity.
• The impact of removing an edge can grow much larger than its nominal capacity.
• Examples show that communication can still enhance capacity even at rates approaching zero.

Conclusion

• Shannon's work laid the foundation for understanding communication in isolation but much remains to be explored in network contexts.
• Important ongoing questions include:
  • The behavior of individual channels in larger networks.
  • The disparity between individual edge capacity and overall network capacity.
• Future work in this area has the potential to solve multiple open questions in information theory.