Introduction to EECS II: Digital Communication Systems

COURSE DESCRIPTION

An introduction to several fundamental ideas in electrical engineering and computer science, using digital communication systems as the vehicle. The three parts of the course—bits, signals, and packets—cover three corresponding layers of abstraction that form the basis of communication systems like the Internet.

The course teaches ideas that are useful in other parts of EECS: abstraction, probabilistic analysis, superposition, time and frequency-domain representations, system design principles and trade-offs, and centralized and distributed algorithms. The course emphasizes connections between theoretical concepts and practice using programming tasks and some experiments with real-world communication channels.

Syllabus

Course Meeting Times

Lectures: 2 sessions / week, 1 hour / session

Recitations: 2 sessions / week, 1 hour / session

Course Objectives

An introduction to several fundamental ideas in electrical engineering and computer science, using digital communication systems as the vehicle. The three parts of the course—bits, signals, and packets—cover three corresponding layers of abstraction relevant to the system:

• binary representation, compression (source coding), and error correction (channel coding) for messages transmitted across a noisy link;
• signal representation of binary messages for transmission across a shared physical channel subject to distortion and noise;
• efficient, reliable communication across networks made up of multiple links.

Topics investigated in depth include:

• Bits: Information and entropy, Huffman coding and LZW compression, error correction with linear block codes and convolutional codes (Viterbi decoding).
• Signals: Additive Gaussian noise and the relationship between noise variance and bit errors, linear-time invariant channel models, frequency-domain (Fourier) analysis, spectral content of signals and filtering, modulation and demodulation.
• Packets: Media access protocols (TDMA, Aloha, and carrier sense), packet-switched networks, queues, and Little’s law, network routing (distance/path vector & link-state protocols), and reliable data transport (adaptive timers, stop-and-wait, sliding windows, round-trip time and bandwidth-delay product concepts).

These topics form the basis of communication systems like the Internet.

The course teaches ideas that are useful in other parts of EECS: abstraction, probabilistic analysis, superposition, time- and frequency-domain representations, system design principles and trade-offs, and centralized and distributed algorithms. The course emphasizes connections between theoretical concepts and practice using programming tasks and some experiments with real-world communication channels.

At the end of the course, a successful student will understand these topics and be able to apply them to the design and analysis of communication systems and networks. In particular, they will appreciate how to build reliable and efficient communication systems: cleverly applying redundancy for reliability and sharing via multiplexing channels, links, and paths for efficiency.

Lecture 1: Overview: Information and Entropy

Description: This lecture covers some history of digital communication, with a focus on Samuel Morse and Claude Shannon, measuring information and defining information, the significance of entropy on encodings, and Huffman’s coding algorithm.

Instructor: George Verghese

Lecture 2: Compression: Huffman and LZW

Description: This lecture covers examples of Huffman coding and limitations of coding. Lempel-Ziv-Welch is introduced as an adaptive variable-length code, and an example is done in lecture.

Instructor: George Verghese

Lecture 3: Errors, Channel Codes

Description: This lecture places in context the abstraction layers in the network communication model and covers digital signaling. Metrics such as channel capacity and Hamming distance are introduced.

Instructor: George Verghese

Lecture 4: Linear Block Codes, Parity Relations

Description: This lecture continues to cover linear block codes. The generator matrix and matrix notation are introduced, along with examples of error correction through rectangular code and Hamming code.

Instructor: George Verghese

Lecture 5: Error Correction, Syndrome Decoding

Description: This lecture continues to explore error correction through a closer look at the generator matrix and the parity check matrix. Syndrome decoding is presented in its matrix form by example, and better error protection is discussed afterward.

Instructor: George Verghese

Lecture 6: Convolutional Codes

Description: This lecture starts with historical applications of error control and convolutional codes in space programs. Convolutional codes are introduced along with examples and transformations in shift-register, state-machine, and trellis view.

Instructor: George Verghese

Lecture 7: Viterbi Decoding

Description: This lecture starts with a review of encoding and decoding. The Viterbi algorithm, which includes a branch metric and a path metric, is introduced as a way to find the maximum-likelihood path during decoding.

Instructor: George Verghese

Lecture 8: Noise

Description: This lecture introduces a noise model based on a Gaussian random variable. Background on calculating mean and variance of probability density function is given alongside steps to estimate noise parameters and calculate bit energy.

Instructor: George Verghese

Lecture 9: Transmitting on a Physical Channel

Description: This lecture begins with background on probability for working with random variables. Conversion, and signal modulation and demodulation are explained. The unit step and sample are introduced alongside time invariant and linear systems.

Instructor: George Verghese

Lecture 10: Linear Time-Invariant (LTI) Systems

Description: This lecture covers modeling channel behavior, relating the unit sample and step responses, decomposing a signal into unit samples, modeling LTI systems, and properties of convolutions.

Instructor: George Verghese

Lecture 11: LTI Channel and Intersymbol Interference

Description: This lecture provides an introduction to Audiocom, which is used for the unit’s assignments. The demonstration addresses troubleshooting and reading the output, and places it in context with course content discussed so far.

Instructors: Hari Balakrishnan and George Verghese

Lecture 12: Filters and Composition

Description: This lecture covers the limitation of time-domain and convolutions, and introduces frequency-domain and sinusoidal inputs to LTI systems. Application of complex exponentials to representing sinusoids is shown.

Instructor: George Verghese

Lecture 13: Frequency Response of LTI Systems

Description: This lecture continues the discussion of properties of the frequency response and the shift from time to frequency domain. Examples of deconvolution in frequency-domain view, designing an ideal low-pass filter, and spectral decomposition are provided.

Instructor: George Verghese

Lecture 14: Spectral Representation of Signals

Description: This lecture starts with a demonstration of echo cancelation using deconvolution, and then continues to cover the spectral content of signals. Fast Fourier transform, and the effect of a low-pass channel are also discussed.

Instructor: George Verghese

Lecture 15: Modulation/Demodulation

Description: This lecture introduces phase characteristic in the frequency response, and the derivation of DTFT for a rectangular pulse. An example of how to send a pulse over a low-pass and a bandpass channel opens discussion about modulation and demodulation.

Instructor: George Verghese

Lecture 16: More on Modulation/Demodulation

Description: This lecture starts with applying FFT for a finite duration and the difference between DTFT and DTFS. The remainder of the lecture covers the demodulation frequency diagram, correcting error in demodulation and phase ambiguity, and multiple trasnmitters.

Instructor: George Verghese

Lecture 17: Packet Switching

Description: This lecture introduces communication networks, with MIT’s network serving as an example. Packet-switched networks are discussed with examples of packet headers, traffic, and the sources of delay.

Instructor: Hari Balakrishnan

Lecture 18: MAC Protocols

Description: This lecture focuses on shared media networks and shared communications channels. Measures for optimization such as utilization, fairness, and bounded delay are introduced, along with an example model using slotted and stabilized Aloha.

Instructor: Hari Balakrishnan

Lecture 19: Network Routing (without failures)

Description: This lecture covers networking routing in multi-hop networks. After an interactive simulation game, distributed routing, distance-vector routing, and link-state routing are discussed with minimum cost path in mind.

Instructor: Hari Balakrishnan

Lecture 20: Network Routing (with failures)

Description: This lecture continues to cover routing protocols within the context of failure. Failure resilience for the different protocols is discussed along with the solution of periodic communication for eventual convergence.

Instructor: Hari Balakrishnan

Lecture 21: Reliable Transport

Description: This lecture covers implementation of TCP and providing reliable data transfer. The stop-and-wait and sliding window protocols are discussed with their benefits and disadvantages in preventing lost or duplicate packets.

Instructor: Hari Balakrishnan

Lecture 22: Sliding Window Analysis, Little's Law

Description: This lecture continues with an analysis of sliding window protocol and how it handles packet loss. Little’s Law is introduced to relate the average number of packets to the average service rate and average delay of a stable system.

Instructor: Hari Balakrishnan

Lecture 23: A Brief History of the Internet

Description: This lecture offers a historical account of the development of the Internet and Internet Protocol (IP). The ideal case for area networking is presented, followed by the creation of the domain name system (DNS).

Instructor: Hari Balakrishnan

Lecture 24: History of the Internet cont'd, Course Summary

Description: This lecture continues the history of the Internet through the recent decades and addresses problems such as rapid growth, congestion, service attacks, and security threats. A summary of the course content is then presented at the end.

Instructor: Hari Balakrishnan