Data Communication (Week 5)

Cheatsheet Content

### Digital to Analog Conversion The process of changing one of the characteristics of an analog signal based on digital data. #### Aspects of Digital-to-Analog Conversion - **Bit rate (N):** Number of bits per second (bps). - **Baud rate (S):** Number of signal elements per second. - In analog transmission, `S ≤ N`. - **Relationship:** $N = S \times r$, where $r$ is the number of data elements carried in one signal element. For binary, $r = 1$. For signals carrying $L$ levels, $r = \log_2 L$. **Example:** An analog signal carries 4 bits per signal element ($r=4$). If 1000 signal elements are sent per second ($S=1000$), the bit rate is $N = 1000 \times 4 = 4000$ bps. ### Amplitude Shift Keying (ASK) - The amplitude of the carrier wave is varied to represent binary 1 or 0. - Frequency and phase remain constant. - Highly susceptible to noise interference. - **Minimum bandwidth (BW):** $(1+d) \times S_{baud}$, where $d$ is the modulation factor. For binary ASK (BASK), usually $d=1$. ### Frequency Shift Keying (FSK) - The frequency of the carrier signal is varied to represent data. - Both peak amplitude and phase remain constant. - For binary FSK (BFSK), two different frequencies represent 0 and 1. ### Phase Shift Keying (PSK) - The phase of the carrier is varied to represent binary 1 or 0. - Peak amplitude and frequency remain constant. - Also known as 2-PSK or Binary PSK (BPSK). - **Minimum bandwidth (BW):** $(1+d) \times S_{baud}$, similar to ASK. ### Constellation Diagram - A diagram that represents the amplitude and phase of a signal element as a point in a two-dimensional space. - Each point corresponds to a unique combination of bits. **Example Constellation Diagrams:** - **ASK (OOK):** Two points on the positive x-axis (e.g., one at 0, one at A). - **BPSK:** Two points on the x-axis, 180 degrees apart (e.g., at A and -A). - **QPSK:** Four points, typically at 45, 135, 225, 315 degrees from the x-axis, all with the same amplitude. ### Quadrature Amplitude Modulation (QAM) - A combination of ASK and PSK. - Varies both amplitude and phase to encode multiple bits per signal element. - Allows for higher data rates. ### Analog to Analog Conversion - The representation of analog information by an analog signal (analog modulation). - Needed when the medium is bandpass or only a bandpass channel is available. #### Types of Analog-to-Analog Conversion - Amplitude Modulation (AM) - Frequency Modulation (FM) - Phase Modulation (PM) ### Amplitude Modulation (AM) - The amplitude of the carrier signal varies with the amplitude of the modulating signal. - Frequency and phase of the carrier remain constant. ### Frequency Modulation (FM) - The frequency of the carrier signal varies with the amplitude of the modulating signal. - Peak amplitude and phase of the carrier remain constant. ### Phase Modulation (PM) - The phase of the carrier signal varies with the amplitude of the modulating signal. - Peak amplitude and frequency of the carrier remain constant. ### Multiplexing - A set of techniques allowing simultaneous transmission of multiple signals across a single data link. - Used when the bandwidth of a medium is greater than the bandwidth needs of individual devices. #### Categories of Multiplexing 1. **Frequency-Division Multiplexing (FDM):** For analog signals. 2. **Wavelength-Division Multiplexing (WDM):** For optical fiber (a type of FDM). 3. **Time-Division Multiplexing (TDM):** For digital signals. ### Frequency Division Multiplexing (FDM) - An analog technique where the link's bandwidth is greater than the combined bandwidths of signals. - Each signal modulates a different carrier frequency. - Modulated signals are combined into a composite signal. - **Guard bands:** Unused bandwidth between channels to prevent overlapping. **Example:** Combining three 4 kHz voice channels into a 12 kHz link (20-32 kHz). - Channel 1: 20-24 kHz - Channel 2: 24-28 kHz - Channel 3: 28-32 kHz **Example:** Five channels, each 100 kHz bandwidth, with 10 kHz guard bands. - Required bandwidth: $5 \times 100 \text{ kHz} + 4 \times 10 \text{ kHz} = 540 \text{ kHz}$. #### Applications of FDM - AM and FM radio broadcasting - Television broadcasting - First Generation Cellular Phone (e.g., AMPS) ### Wavelength Division Multiplexing (WDM) - Designed for high-data-rate fiber-optic cables. - Combines several optical signals (different wavelengths/colors of light) into one fiber. - Prisms are often used for multiplexing and demultiplexing. ### Time Division Multiplexing (TDM) - A digital process where connections share the high bandwidth of a link by sharing time. - Each connection occupies a portion of time in the link. #### Synchronous TDM - Data rate of the link is $n$ times faster than input lines, and unit duration is $n$ times shorter. - If a source has no data, its slot in the output frame is empty, leading to inefficiency. #### Data Rate Management in TDM Strategies for handling unequal input data rates: 1. **Multilevel Multiplexing:** When an input line's data rate is a multiple of others. 2. **Multiple-Slot Allocation:** Allotting more than one slot in a frame to a single input line. 3. **Pulse Stuffing (Bit Padding/Stuffing):** Adding dummy bits to lower-rate input lines to match the highest data rate. ### Error Detection and Correction - Data can become corrupted during transmission due to interference. - Mechanisms are needed to detect and correct errors to ensure data integrity. #### Types of Error - **Single Bit Error:** Only 1 bit is changed from 1 to 0 or 0 to 1. - **Burst Error:** 2 or more bits in the data unit have changed. Burst errors are more common. #### Redundancy - To detect or correct errors, extra bits (redundant bits) are added to the data by the sender. - The receiver uses these bits to check for corruption. #### Detection versus Correction - **Error Detection:** Only determines if an error has occurred (yes/no). Does not locate the error. - **Error Correction:** Requires knowing the exact number of corrupted bits and their locations. More complex than detection. ### Block Coding - Divides messages into blocks of $k$ bits (datawords). - Adds $r$ redundant bits to each block to form an $n$-bit codeword ($n=k+r$). - **Invalid/Illegal codewords:** Codewords that are not used. Their existence allows error detection. - If a received codeword is invalid, an error is detected. If a corrupted codeword happens to be a valid one, the error goes undetected. ### Hamming Distance - The number of differences between corresponding bits of two words of the same size, $d(x, y)$. - If $d(sent, received) \neq 0$, an error has occurred. - Calculated by XORing two words and counting the number of 1s in the result. **Example:** $d(000, 011) = 2$ (0 XOR 0 = 0, 0 XOR 1 = 1, 0 XOR 1 = 1 => two 1s) **Example:** $d(10101, 11110) = 3$ (1 XOR 1 = 0, 0 XOR 1 = 1, 1 XOR 1 = 0, 0 XOR 1 = 1, 1 XOR 0 = 1 => three 1s) #### Minimum Hamming Distance ($d_{min}$) - The smallest Hamming distance between all possible pairs of valid codewords in a coding scheme. - To guarantee detection of up to $s$ errors, $d_{min} = s+1$. - To guarantee correction of up to $t$ errors, $d_{min} = 2t+1$. **Example:** If $d_{min} = 4$: - Error detection capability: $s = d_{min} - 1 = 4 - 1 = 3$ errors. - Error correction capability: $t = (d_{min} - 1)/2 = (4 - 1)/2 = 1.5$. Since errors must be whole numbers, it can correct up to 1 error. ### Simple Parity Check - A parity bit is added to every data unit to make the total number of 1s even (even parity) or odd (odd parity). **Example:** Sending "world" (ASCII). - Original bytes (with even parity bit): - `1110111` (5 ones) -> `11101110` (6 ones, even) - `1101111` (5 ones) -> `11011110` (6 ones, even) - `1110010` (3 ones) -> `11100100` (4 ones, even) - `1101100` (4 ones) -> `11011000` (4 ones, even) - `1100100` (3 ones) -> `11001001` (4 ones, even) **Detection capability:** Can detect any odd number of bit errors. Cannot detect an even number of bit errors. ### Cyclic Redundancy Check (CRC) - Uses binary division (modulo-2 arithmetic). - A sequence of redundant bits (CRC remainder) is appended to the data. - The number of 0s appended is one less than the divisor's length. - The resulting bit sequence must be divisible by the divisor. ### Multiple Access Protocols - Used when multiple nodes or stations share a common link (multipoint or broadcast link). - Coordinates access to the link to prevent collisions and ensure fair access. - Part of the Media Access Control (MAC) sublayer of the data-link layer. #### Taxonomy of Multiple Access Protocols 1. **Random Access:** Stations transmit based on protocol rules; collisions can occur and are resolved. 2. **Controlled Access:** Stations consult each other to determine who has the right to send. 3. **Channelization:** Divides the available bandwidth among different stations. ### Random Access - No station is superior; any station with data can attempt to send. - Collisions are possible and need to be handled. #### ALOHA - Earliest random-access method (University of Hawaii, 1970s). - **Pure ALOHA:** Each station sends a frame whenever it has data. Collisions are detected, and frames are retransmitted after a random backoff time. - **Vulnerable time:** $2 \times T_{fr}$ (twice the frame transmission time). - **Throughput (S):** $G \times e^{-2G}$, where $G$ is the offered load. - **Maximum throughput:** $S_{max} \approx 0.184$ (18.4%) when $G=0.5$. - **Slotted ALOHA:** Time is divided into fixed-size slots ($T_{fr}$). Stations can only send at the beginning of a slot. - Reduces vulnerable time to $T_{fr}$. - **Throughput (S):** $G \times e^{-G}$. - **Maximum throughput:** $S_{max} \approx 0.368$ (36.8%) when $G=1$. #### Carrier Sense Multiple Access (CSMA) - "Sense before transmit" or "listen before talk." - Stations listen to the medium before sending. If busy, they wait. - Reduces collision probability but doesn't eliminate it due to propagation delay. ##### Persistence Methods (What to do if channel is busy/idle?) 1. **1-Persistent:** If idle, send immediately (probability 1). High collision chance. 2. **Nonpersistent:** If idle, send immediately. If busy, wait a random time, then sense again. Reduces efficiency. 3. **p-Persistent:** For slotted channels. If idle, send with probability $p$. With probability $q=1-p$, wait for next slot and recheck. Combines advantages. #### CSMA with Collision Detection (CSMA/CD) - Augments CSMA by detecting collisions during transmission. - If a collision is detected, the station stops transmitting, sends a jam signal, and retransmits after a random backoff. - Efficiency is improved because transmission stops early. #### CSMA with Collision Avoidance (CSMA/CA) - Designed for wireless networks where collision detection is difficult (e.g., hidden terminal problem). - Avoids collisions through: 1. **Interframe Space (IFS):** Waiting periods (DIFS, SIFS) before/between transmissions. 2. **Contention Window:** Random backoff time. 3. **Acknowledgments (ACK):** Receiver sends ACK to confirm successful reception. ##### Frame Exchange (RTS/CTS) - **Request to Send (RTS):** Sender sends RTS after waiting DIFS. Contains duration of required channel time. - **Clear to Send (CTS):** Receiver sends CTS after waiting SIFS. Indicates readiness to receive. - **Data Transmission:** Sender transmits data after waiting SIFS. - **Acknowledgment (ACK):** Receiver sends ACK after waiting SIFS. ##### Network Allocation Vector (NAV) - Other stations, upon hearing an RTS or CTS, set a timer (NAV) for the duration indicated in the control frame. - They defer access until their NAV expires, effectively "reserving" the channel for the current transmission to avoid collisions. ### Controlled Access - Stations consult one another to determine which station has the right to send. - A station cannot send unless authorized. #### Reservation - Time is divided into intervals. - A **reservation frame** precedes data frames. - Each station has a mini-slot in the reservation frame to reserve for data transmission. - Stations that successfully reserve can then send their data. #### Polling - Works with topologies having a **primary station** and **secondary stations**. - Primary controls the link; secondaries follow instructions. - Uses **poll** and **select** functions. - **Select Function:** Primary sends a SELECT frame to a secondary to ask if it's ready to receive data. - **Poll Function:** Primary sends a POLL frame to a secondary to ask if it has data to send. - **Drawback:** System fails if primary station fails. #### Token Passing - Stations are organized in a **logical ring**. - A special packet called a **token** circulates the ring. - Only the station holding the token can transmit data. - When a station finishes transmitting or doesn't have data, it passes the token to its successor. ### Channelization Protocols - Multiple-access methods where the available bandwidth is shared in time, frequency, or through code. #### Frequency Division Multiple Access (FDMA) - Available bandwidth divided into frequency bands. - Each station assigned a band for the entire communication period. - Uses bandpass filters; guard bands prevent interference. - Suitable for stream data. ##### FDMA vs FDM - **FDM:** A physical layer technique that combines multiple signals into a composite signal for transmission over a single link. - **FDMA:** A data link layer technique that assigns a unique frequency band to each user in a shared medium, allowing multiple users to share the channel simultaneously. FDMA uses FDM at the physical layer. #### Time Division Multiple Access (TDMA) - A channel access method for shared medium networks. - Allows several users to share the same frequency by dividing time. - Each station is allocated a time slot during which it can send data. - **Key challenge:** Achieving synchronization between stations due to propagation delays. **Guard times** are inserted to compensate. #### Code-Division Multiple Access (CDMA) - Differs from FDMA (only one channel occupies entire bandwidth) and TDMA (all stations can send simultaneously, no time-sharing). - Based on **Coding Theory:** Each station is assigned a unique code (sequence of numbers called **chips**). - Data is multiplied by the station's code before transmission. - To receive data from a specific sender, the receiver multiplies the composite signal by the sender's code. ##### CDMA Analogy - Multiple conversations in different languages in the same room. Each language acts as a "code." ##### CDMA Properties - If we multiply each code by another, we get 0 (orthogonality). - If we multiply each code by itself, we get the number of stations (e.g., 4 for 4 stations). ##### Data Representation in CDMA - **0 bit:** Encoded as -1. - **1 bit:** Encoded as +1. - **Idle:** 0 (no signal).