Information Theory System and Coding

1

Information theory was founded by Claude Shannon (1948) in his landmark paper 'A Mathematical Theory of Communication'. It quantifies information, defines channel capacity, and establishes the fundamental limits of communication systems.

2

Information content of an event with probability p is I = log₂(1/p) bits. Rarer events (smaller p) carry more information — a certain event (p=1) has 0 bits of information; a very unlikely event has high information content.

3

Entropy (H) = average information per symbol = H = Σ p · log₂(1/p) bits/symbol. Entropy measures the average uncertainty or randomness of a source. It is MAXIMUM when all symbols are equally likely (uniform distribution) and minimum (zero) when one symbol is certain.

4

Information rate R = entropy × symbol rate (bits per second). This represents the average information output of a source per second.

5

Channel capacity = the maximum rate at which information can be reliably transmitted over a channel. Shannon-Hartley theorem: C = B · log₂(1 + S/N), where B = bandwidth (Hz), S/N = signal-to-noise ratio. Higher bandwidth or higher SNR → higher capacity.

6

Analog signal = continuous in both time and amplitude. Digital signal = discrete in both time and amplitude (quantized). Analog-to-digital conversion (ADC) converts analog signals for digital processing.

7

Fourier series/transform decomposes a signal into its constituent frequency components — time domain ↔ frequency domain. The Fourier transform reveals what frequencies are present in a signal. Essential for signal analysis, filtering, and modulation.

8

Power Spectral Density (PSD) describes how a signal's power is distributed over frequency. Its inverse Fourier transform is the autocorrelation function (Wiener–Khinchin theorem). PSD is used to analyze noise and signal characteristics.

9

Bandwidth = the range of frequencies contained in a signal (frequency domain) or the capacity of a channel. Wider bandwidth → more information can be transmitted per second.

1

Analog-to-Digital Conversion (ADC) involves three steps: Sampling (take snapshots of the analog signal at regular intervals) → Quantization (round each sample to the nearest discrete level) → Encoding (represent each quantized value as a binary number).

2

Nyquist Sampling Theorem: to perfectly reconstruct an analog signal, the sampling rate must be fs ≥ 2 × fmax (at least twice the highest frequency component). Sampling below the Nyquist rate causes aliasing — the reconstructed signal contains false frequencies.

3

PAM (Pulse Amplitude Modulation) — the amplitude of each pulse varies proportionally with the instantaneous sample value of the analog signal. PAM is the first stage of PCM.

4

PCM (Pulse Code Modulation) — sample the analog signal, quantize each sample, then encode into binary. PCM is the basis of digital audio (CDs), telephony (PSTN G.711), and digital storage. Each sample is represented by n bits, giving 2ⁿ quantization levels.

5

Quantization noise/error — the error introduced by rounding sampled values to the nearest discrete level. The finer the quantization (more bits), the smaller the quantization noise and the higher the signal quality.

6

DPCM (Differential PCM) — instead of encoding each full sample value, DPCM encodes the difference between successive samples. Since consecutive samples are often similar, differences are smaller and fewer bits are needed, reducing bit rate compared to PCM.

7

Delta Modulation (DM) — simplest form of differential coding; uses just 1 bit per sample to indicate whether the signal went up (+) or down (−). Very low bit rate but suffers from: Slope overload (signal changes too fast for the step size) and Granular noise (signal is flat but the quantizer keeps jumping up/down).

8

TDM (Time-Division Multiplexing) — multiple signals share a single channel by taking turns in assigned time slots. Used extensively in telephony (T1/E1 carriers). FDM (Frequency-Division Multiplexing) — signals share a channel at different frequencies simultaneously.

9

Pulse Time Modulation: PWM (Pulse Width Modulation) — width of pulse varies with signal. PPM (Pulse Position Modulation) — position of pulse varies with signal. Both encode information in the timing of pulses.

10

ISI (Inter-Symbol Interference) — occurs when pulses from adjacent time slots spread and overlap, causing detection errors. Caused by bandwidth-limited channels. Reduced by proper filtering (e.g., raised-cosine filter) and channel equalization. PLL (Phase-Locked Loop) — a feedback circuit that synchronises its output phase and frequency to an input reference; used in clock recovery, frequency synthesis, and demodulation.

1

Source coding reduces redundancy in the source data to enable efficient storage and transmission. The goal is to represent the source output using as few bits as possible while maintaining the ability to reconstruct it.

2

Shannon's Source Coding Theorem (noiseless coding theorem): the average code length L̄ must satisfy L̄ ≥ H (average code length cannot be less than entropy). Efficiency = H / L̄ (ranges 0 to 1).

3

Shannon-Fano Coding — a top-down algorithm: sort symbols by probability (descending), then repeatedly split the list into two groups of nearly equal probability, assigning 0/1 to each half. Builds the code tree from the root downward. Simple but not always optimal.

4

Huffman Coding — a bottom-up algorithm: repeatedly merge the two symbols (or groups) with the lowest probability, building a binary tree from the leaves upward. The resulting prefix code is optimal — it achieves the minimum average code length among all prefix-free codes. Assigns shorter codes to more frequent symbols.

5

Prefix code (prefix-free code) — no codeword is a prefix of another. This property allows unambiguous decoding without needing separators between codewords. Both Huffman and Shannon-Fano codes are prefix codes.

6

Shannon's Channel Capacity Theorem: reliable transmission is possible if and only if the data rate R < channel capacity C. If R > C, reliable transmission is theoretically impossible regardless of coding used.

7

Signal Classification by Periodicity: Periodic signal — repeats exactly after a period T. Aperiodic (non-periodic) — does not repeat. By Predictability: Deterministic — completely predictable from a mathematical formula. Random (stochastic) — described statistically; cannot be exactly predicted.

8

Energy Signal — has finite total energy (E < ∞) and zero average power. Usually non-periodic (transient). Example: a single pulse. Power Signal — has finite average power and infinite total energy. Usually periodic (sustained). Example: a sinusoid. A signal is one or the other (or neither), not both.

1

Transmission Impairments degrade signal quality over a communication channel. Four main types: Attenuation (loss of signal strength/power over distance — cables, connectors), Distortion (signal shape changes — e.g., delay distortion where different frequency components travel at different speeds), Noise (unwanted signals added to the channel — thermal, impulse, crosstalk, intermodulation), Crosstalk (signal from one channel induces interference on an adjacent channel).

2

Error Detection adds redundant bits to detect whether errors occurred during transmission. Parity bit — adds 1 bit; detects single-bit errors only (even or odd parity). Checksum — sum-based; used in TCP/IP headers, simple but less robust. CRC (Cyclic Redundancy Check) — uses polynomial division by a generator polynomial; provides strong burst-error detection; used in Ethernet, HDLC, ZIP files.

3

Hamming Code — designed by Richard Hamming. Adds redundant parity bits at specific positions (powers of 2). Can detect up to 2-bit errors and correct single-bit errors. Extended Hamming codes provide double-error detection.

4

Hamming Distance between two codewords = number of bit positions where they differ. The minimum Hamming distance of a code determines its error capability: to detect d errors: min distance ≥ d+1; to correct d errors: min distance ≥ 2d+1.

5

FEC (Forward Error Correction) — the receiver corrects errors itself using redundant bits without requesting retransmission. Used where retransmission is not practical (satellite, broadcast, deep space). Examples: Hamming, Convolutional codes, Turbo codes, LDPC codes.

6

ARQ (Automatic Repeat reQuest) — error control by retransmission. Receiver requests retransmission when errors are detected (NAK) or when a timeout expires. Requires a return channel.

7

Lossless Compression — data is compressed and can be perfectly reconstructed. No information is lost. Used for text, executables, archives. Examples: Huffman coding, RLE (Run-Length Encoding), LZW (Lempel-Ziv-Welch — used in GIF, ZIP).

8

Lossy Compression — some data is discarded; original cannot be perfectly reconstructed. Acceptable for perceptual media where small losses are not noticed. Examples: JPEG (images), MP3/AAC (audio), MPEG/H.264 (video). Achieves much higher compression ratios than lossless.

1

Data Link Control (DLC) manages the reliable transfer of data frames between two directly connected nodes. Responsibilities include: framing, error detection/correction, flow control, and link management.

2

Flow Control prevents a fast sender from overwhelming a slow receiver. Stop-and-Wait — sender sends one frame, waits for an ACK before sending the next. Simple but inefficient (low channel utilization; channel sits idle while waiting). Sliding Window — sender can have multiple unacknowledged frames in flight (a 'window' of frames). Higher throughput by keeping the channel busy. Window size determines how many frames can be outstanding.

3

ARQ (Automatic Repeat reQuest) — error control strategy using acknowledgements (ACK = success, NAK = error) and timeouts. Three ARQ protocols: Stop-and-Wait ARQ (retransmit the single unacknowledged frame), Go-Back-N ARQ (retransmit the erroneous frame AND ALL subsequent frames), Selective Repeat ARQ (retransmit ONLY the specific erroneous frame).

4

Go-Back-N ARQ — simpler buffer requirement at receiver (accepts frames in order only). When an error is detected, the sender goes back N frames and retransmits from the error point. More retransmissions but simpler receiver.

5

Selective Repeat ARQ — most efficient (minimum retransmissions), but requires the receiver to buffer out-of-order frames and the sender to track which frames were NAKed. Most complex but minimizes unnecessary retransmissions.

6

Asynchronous Transmission — transmits one character at a time, each framed with a start bit and one or more stop bits. No shared clock between sender and receiver. Simple, low overhead per connection, but higher per-character overhead (typically 10 bits for 8 data bits). Example: traditional RS-232 serial ports, early modems.

7

Synchronous Transmission — transmits blocks of characters using a shared clock signal for synchronization. No start/stop bits per character. Much more efficient for large volumes of data with lower per-bit overhead. Examples: HDLC, Ethernet, T1/E1 lines.

8

Framing — the process of packaging bits into recognizable units (frames) with headers, data, and trailers. Enables the receiver to determine where frames start and end. Methods: character count, byte stuffing (character stuffing), bit stuffing (flag bytes).

1

Encoding converts digital data into a digital signal format for transmission over a digital channel (baseband transmission). Modulation varies one or more properties of a high-frequency carrier signal with the data, enabling transmission over an analog channel or radio channel (bandpass transmission).

2

Line Coding — encoding schemes for digital-to-digital transmission. NRZ-L (Non-Return to Zero Level) — signal level directly represents bit value. NRZ-I (Inverted) — transition at start of 1 bit. Manchester encoding — mid-bit transition for every bit: low-to-high = 0, high-to-low = 1 (or vice versa). Manchester is self-clocking — the receiver can extract the clock from the data transitions. Used in Ethernet (10BASE-T).

3

Digital Modulation (Shift Keying): ASK (Amplitude Shift Keying) — carrier amplitude changes to represent 0/1 (e.g., On-Off Keying). FSK (Frequency Shift Keying) — carrier frequency changes (e.g., one frequency for 0, another for 1). PSK (Phase Shift Keying) — carrier phase changes (e.g., 0° for 0, 180° for 1 in BPSK). PSK is more noise-resistant than ASK.

4

QPSK (Quadrature Phase Shift Keying) — uses 4 phase values (0°, 90°, 180°, 270°), encoding 2 bits per symbol. More spectrally efficient than BPSK. QAM (Quadrature Amplitude Modulation) — varies both amplitude AND phase, carrying multiple bits per symbol. 16-QAM = 4 bits/symbol, 64-QAM = 6 bits/symbol. Used in cable TV, DSL, Wi-Fi (802.11).

5

Analog Modulation: AM (Amplitude Modulation) — carrier amplitude varies with the message signal. FM (Frequency Modulation) — carrier frequency varies with the message. PM (Phase Modulation) — carrier phase varies with the message. FM is more noise-resistant than AM.

6

Modem (Modulator-Demodulator) — converts digital data to analog signals (modulation) for transmission over analog telephone lines, and converts analog signals back to digital at the receiver (demodulation). Essential for connecting digital devices to analog networks.

7

DPSK (Differential PSK) — encodes data as phase changes (transitions) between symbols rather than absolute phase. Easier to demodulate since it doesn't require a reference phase. A transition = 1, no transition = 0 (or vice versa).

8

Bandwidth efficiency — measured in bits/s/Hz; higher-order modulation schemes (QAM) carry more bits per Hz of bandwidth but require a better signal-to-noise ratio. There is a trade-off between spectral efficiency and noise tolerance.