From 0d6ce142ff2b53d6fa3dfd7b06cbff499faa53b1 Mon Sep 17 00:00:00 2001 From: mo khan Date: Mon, 8 Sep 2025 20:12:14 -0600 Subject: feat: complete 2.x --- comp347/assignment3/assignment3.md | 532 ++++++++++++++++++++++++++++++++++++- 1 file changed, 524 insertions(+), 8 deletions(-) (limited to 'comp347/assignment3') diff --git a/comp347/assignment3/assignment3.md b/comp347/assignment3/assignment3.md index 7c9b874..6a8c850 100644 --- a/comp347/assignment3/assignment3.md +++ b/comp347/assignment3/assignment3.md @@ -504,13 +504,323 @@ Modern Wi-Fi technology encompasses several IEEE 802.11 standards that have evol ### 2.1 Code Division Multiple Access (CDMA) (15%) -[To be completed] +Code Division Multiple Access (CDMA) is a sophisticated channel access method that enables multiple users to share the same frequency spectrum simultaneously by assigning unique codes to each user. This research examines CDMA technology, focusing on Wideband CDMA (W-CDMA) used in 3G UMTS networks. + +## CDMA Technology Overview + +CDMA differs fundamentally from Time Division Multiple Access (TDMA) and Frequency Division Multiple Access (FDMA) by using mathematical coding techniques rather than time slots or frequency separation to distinguish between users. All users transmit simultaneously on the same frequency band, with separation achieved through orthogonal or quasi-orthogonal spreading codes. + +## Selected CDMA Scheme: Wideband CDMA (W-CDMA) + +**W-CDMA** is the air interface standard used in 3G UMTS (Universal Mobile Telecommunications System) networks, standardized by 3GPP (3rd Generation Partnership Project). This scheme represents an evolution from earlier CDMA implementations like IS-95. + +### How W-CDMA Works: + +#### 1. Spreading Process +**Direct Sequence Spread Spectrum:** +- Each user's data stream is multiplied by a unique spreading code (channelization code) +- The spreading code has a much higher bit rate (chip rate) than the original data +- W-CDMA uses a chip rate of 3.84 Mcps (Mega-chips per second) +- This spreads the signal across a 5 MHz bandwidth + +**Mathematical Representation:** +``` +Transmitted Signal = Data Stream × Spreading Code × Scrambling Code +``` + +#### 2. Channelization Codes +**Orthogonal Variable Spreading Factor (OVSF) Codes:** +- Uses Walsh-Hadamard codes that are perfectly orthogonal +- Variable length codes support different data rates +- Spreading factors range from 4 to 512 +- Higher spreading factors = lower data rates but better interference resistance + +**Code Tree Structure:** +- Codes organized in a binary tree structure +- Parent-child codes are orthogonal to each other +- Enables flexible bandwidth allocation + +#### 3. Scrambling Codes +**Gold Codes:** +- Long pseudo-random sequences (2^18 - 1 = 262,143 chips) +- Used to separate different cells and users +- Provide quasi-orthogonal separation +- Enable soft handoff between cells + +#### 4. Power Control +**Fast Power Control:** +- Adjusts transmission power 1500 times per second +- Compensates for near-far effect and fading +- Critical for maintaining signal quality and minimizing interference +- Uses feedback from receiver to base station + +### Detailed Operation: + +#### Uplink (Mobile to Base Station): +1. **Voice/Data Encoding:** User data is channel coded and interleaved +2. **Spreading:** Data multiplied by user-specific OVSF channelization code +3. **Scrambling:** Result multiplied by mobile-specific scrambling code +4. **Power Control:** Transmission power adjusted based on base station commands +5. **Transmission:** Signal transmitted across 5 MHz bandwidth + +#### Downlink (Base Station to Mobile): +1. **Code Allocation:** Base station assigns OVSF codes to different users +2. **Spreading:** Each user's data spread with their assigned code +3. **Scrambling:** All users' signals scrambled with cell-specific code +4. **Combining:** All spread signals combined and transmitted simultaneously +5. **Reception:** Mobile uses correlation with its assigned codes to extract data + +### Advanced W-CDMA Features: + +#### 1. Rake Receiver +- **Multipath Combining:** Combines multiple delayed copies of the same signal +- **Finger Assignment:** Each "finger" processes a different multipath component +- **Diversity Gain:** Improves signal quality by combining multipath signals +- **Adaptive:** Automatically tracks and combines strongest multipath components + +#### 2. Soft Handoff +- **Multiple Base Stations:** Mobile simultaneously connected to multiple cells +- **Seamless Transition:** No break in communication during handoff +- **Macro Diversity:** Combines signals from multiple base stations +- **Quality Improvement:** Better coverage at cell boundaries + +#### 3. Variable Data Rates +- **Multi-Rate Services:** Supports different data rates simultaneously +- **Code Rate Adaptation:** Changes spreading factor based on required data rate +- **Dynamic Allocation:** Real-time adjustment of resources based on demand + +## Advantages of CDMA over TDM and FDM: + +### 1. Capacity Benefits +**Statistical Multiplexing:** +- Multiple users share the same spectrum simultaneously +- Capacity limited by interference rather than fixed time slots or frequencies +- Better utilization of available spectrum +- Graceful degradation as load increases + +**Voice Activity Factor:** +- Takes advantage of natural pauses in speech +- Users only interfere when actually transmitting +- Effective capacity gain of 2-3x over continuous transmission systems + +### 2. Security and Privacy +**Spread Spectrum Security:** +- Difficult to intercept or jam due to spreading +- Signals appear as noise to unauthorized receivers +- Each user has unique code sequence +- Inherent encryption through spreading process + +### 3. Quality Benefits +**Interference Averaging:** +- Each user sees interference from all other users as white noise +- Better error performance compared to single-user interference +- Soft capacity limit rather than hard blocking + +**Multipath Resistance:** +- Rake receivers exploit multipath propagation +- Converts multipath fading into diversity gain +- Better performance in urban environments + +### 4. Flexibility +**Dynamic Resource Allocation:** +- No fixed time slots or frequency assignments +- Adaptive data rates based on channel conditions and requirements +- Seamless integration of voice and data services +- Support for multimedia applications + +## Comparison with TDM and FDM: + +| Aspect | CDMA | TDM | FDM | +|--------|------|-----|-----| +| **Separation Method** | Unique codes | Time slots | Frequency bands | +| **Spectrum Efficiency** | High (statistical multiplexing) | Medium (fixed slots) | Low (guard bands) | +| **Capacity** | Soft limit, interference-limited | Hard limit, slot-limited | Hard limit, bandwidth-limited | +| **Near-Far Effect** | Critical issue, needs power control | Minimal impact | Minimal impact | +| **Multipath Handling** | Beneficial (Rake receiver) | Requires equalization | Requires equalization | +| **Security** | High (spreading codes) | Low (time-based) | Low (frequency-based) | +| **Implementation** | Complex (correlation, power control) | Medium (synchronization) | Simple (filtering) | + +## Sources and References: + +1. **3GPP Technical Specifications:** TS 25.213 (Spreading and modulation), TS 25.214 (Physical layer procedures) +2. **Viterbi, A.J.** "CDMA: Principles of Spread Spectrum Communication" - Addison-Wesley, 1995 +3. **Holma, H. and Toskala, A.** "WCDMA for UMTS: Radio Access for Third Generation Mobile Communications" - Wiley, 2004 +4. **IEEE Communications Magazine:** Various articles on CDMA evolution and implementation (1995-2005) +5. **ITU-R Recommendation M.1457:** "Detailed specifications of the radio interfaces of International Mobile Telecommunications-2000" + +**Key Insight:** W-CDMA represents a sophisticated evolution of CDMA technology that achieves superior spectrum efficiency and service flexibility compared to traditional TDM/FDM approaches by leveraging advanced signal processing, power control, and code design techniques, though at the cost of increased implementation complexity and the critical need for precise power management. ### 2.2 Two-Dimensional Checksum (15%) **Given payload:** 1011 0110 1010 1011 -[To be completed] +**Objective:** Design a minimal-length two-dimensional checksum using even parity that can detect and correct any single-bit error. + +## Step 1: Determine Optimal Data Arrangement + +**Given data:** 16 bits total +**Arrangement:** For optimal checksum length, arrange in a rectangular matrix + +**Testing arrangements for minimal checksum overhead:** + +### Option 1: 4×4 arrangement +``` +1 0 1 1 | Row parity +0 1 1 0 | +1 0 1 0 | +1 0 1 1 | +───────── +Col parity +``` +- Row parity bits: 4 bits +- Column parity bits: 4 bits +- Total checksum: 8 bits (50% overhead) + +### Option 2: 2×8 arrangement +``` +1 0 1 1 0 1 1 0 | Row parity +1 0 1 0 1 0 1 1 | +───────────────── +Col parity (8 bits) +``` +- Row parity bits: 2 bits +- Column parity bits: 8 bits +- Total checksum: 10 bits (62.5% overhead) + +### Option 3: 8×2 arrangement +``` +1 0 | Row parity +1 1 | +0 1 | +1 0 | +1 0 | +1 0 | +1 0 | +1 1 | +────── +Col parity +``` +- Row parity bits: 8 bits +- Column parity bits: 2 bits +- Total checksum: 10 bits (62.5% overhead) + +**Optimal Choice:** 4×4 arrangement provides minimum checksum length (8 bits) + +## Step 2: Calculate Checksum Values + +### Data Matrix Arrangement: +``` +Position: (row, col) +1 0 1 1 (positions: 1,1 1,2 1,3 1,4) +0 1 1 0 (positions: 2,1 2,2 2,3 2,4) +1 0 1 0 (positions: 3,1 3,2 3,3 3,4) +1 0 1 1 (positions: 4,1 4,2 4,3 4,4) +``` + +### Row Parity Calculation (Even Parity): +- **Row 1:** 1⊕0⊕1⊕1 = 1 → **Row parity R₁ = 1** +- **Row 2:** 0⊕1⊕1⊕0 = 0 → **Row parity R₂ = 0** +- **Row 3:** 1⊕0⊕1⊕0 = 0 → **Row parity R₃ = 0** +- **Row 4:** 1⊕0⊕1⊕1 = 1 → **Row parity R₄ = 1** + +### Column Parity Calculation (Even Parity): +- **Col 1:** 1⊕0⊕1⊕1 = 1 → **Column parity C₁ = 1** +- **Col 2:** 0⊕1⊕0⊕0 = 1 → **Column parity C₂ = 1** +- **Col 3:** 1⊕1⊕1⊕1 = 0 → **Column parity C₃ = 0** +- **Col 4:** 1⊕0⊕0⊕1 = 0 → **Column parity C₄ = 0** + +### Complete Transmission Block: +``` +Data Matrix: Parity +1 0 1 1 R₁ = 1 +0 1 1 0 R₂ = 0 +1 0 1 0 R₃ = 0 +1 0 1 1 R₄ = 1 +───────── ───── +C₁C₂C₃C₄ P +1 1 0 0 +``` + +### Overall Parity Calculation: +**P = R₁⊕R₂⊕R₃⊕R₄ = 1⊕0⊕0⊕1 = 0** + +**Final Checksum Field:** **1100 1010 0** +- Row parities: 1010 +- Column parities: 1100 +- Overall parity: 0 +- **Total checksum length: 9 bits** + +## Step 3: Prove Minimality + +### Theoretical Lower Bound: +For single error correction capability with n data bits: +- **Hamming bound:** 2^k ≥ n + k + 1 (where k = parity bits) +- For n = 16: 2^k ≥ 16 + k + 1 = 17 + k +- Minimum k = 5 bits (since 2^5 = 32 ≥ 21) + +### Two-Dimensional Parity Analysis: +**Our scheme uses 9 bits vs theoretical minimum of 5 bits** + +**Justification for additional overhead:** +1. **Error Localization:** Two-dimensional parity provides exact error position +2. **Correction Capability:** Automatic correction without retransmission +3. **Implementation Simplicity:** Simple XOR operations vs complex syndrome decoding +4. **Practical Minimum:** For rectangular arrangement with integer dimensions + +### Alternative Arrangements Comparison: +- 1×16: Requires 1 + 16 + 1 = 18 parity bits +- 2×8: Requires 2 + 8 + 1 = 11 parity bits +- 4×4: Requires 4 + 4 + 1 = 9 parity bits ← **MINIMAL** +- 8×2: Requires 8 + 2 + 1 = 11 parity bits +- 16×1: Requires 16 + 1 + 1 = 18 parity bits + +**Proof of minimality:** 4×4 arrangement provides the shortest checksum length among all possible rectangular matrix arrangements. + +## Step 4: Prove Single-Bit Error Detection and Correction + +### Error Detection Mechanism: +1. **Row parity mismatch** indicates error in that row +2. **Column parity mismatch** indicates error in that column +3. **Intersection** of failing row and column identifies exact error position +4. **Overall parity** distinguishes between single-bit and parity-bit errors + +### Error Correction Examples: + +#### Example 1: Data bit error at position (2,3) +**Received data with error:** +``` +1 0 1 1 R₁ = 1 ✓ +0 1 0 0 R₂ = 1 ✗ (should be 0) +1 0 1 0 R₃ = 0 ✓ +1 0 1 1 R₄ = 1 ✓ +───────── +1 0 0 0 C₃ = 1 ✗ (should be 0) +``` + +**Error localization:** Row 2 fails, Column 3 fails → Error at (2,3) +**Correction:** Flip bit at position (2,3): 0 → 1 + +#### Example 2: Parity bit error (R₂ error) +**Received data with parity error:** +``` +1 0 1 1 R₁ = 1 ✓ +0 1 1 0 R₂ = 1 ✗ (should be 0) +1 0 1 0 R₃ = 0 ✓ +1 0 1 1 R₄ = 1 ✓ +───────── +1 1 0 0 All column parities ✓ +``` + +**Error detection:** Only row parity fails, columns are correct → Parity bit error +**Correction:** Correct R₂ parity bit + +### Comprehensive Error Coverage: +- **Data bit errors:** Detected by row AND column parity failures +- **Row parity errors:** Detected by row failure, columns correct +- **Column parity errors:** Detected by column failure, rows correct +- **Overall parity errors:** Detected by overall parity mismatch + +**Conclusion:** The two-dimensional checksum with 9-bit overhead (4×4 arrangement) provides minimal-length error detection and correction for the given 16-bit payload, with 100% single-bit error detection and correction capability. ### 2.3 CSMA/CD Ethernet Analysis (20%) @@ -520,19 +830,225 @@ Modern Wi-Fi technology encompasses several IEEE 802.11 standards that have evol - Propagation speed: 2×10^8 m/sec - Frame size: 1,024 bits - Backoff intervals: multiples of 512 bits -- Repeater delay: 20-bit transmission time +- Repeater delay: 20-bit transmission time each - Post-collision: A draws K=0, B draws K=1 +- Jam signal: 48 bits -[To be completed] +## Part (a): One-way propagation delay and delivery time + +### Step 1: Calculate one-way propagation delay + +**Physical propagation time:** +- Cable length: 180 m +- Propagation speed: 2×10^8 m/sec +- Physical delay = 180 m ÷ (2×10^8 m/sec) = 0.9 μs + +**Repeater delays:** +- 3 repeaters × 20-bit transmission time each +- At 1 Gbps: 1 bit time = 1 ns +- Total repeater delay = 3 × 20 bits × 1 ns/bit = 60 ns = 0.06 μs + +**Total one-way propagation delay:** +Total delay = Physical delay + Repeater delays +Total delay = 0.9 μs + 0.06 μs = **0.96 μs** + +### Step 2: Timeline analysis for collision scenario + +**t = 0**: Both A and B start transmitting simultaneously + +**Collision detection and jam signal:** +- Collision occurs immediately since both start at t=0 +- Jam signal duration: 48 bits = 48 ns +- Jam signal completes at t = 48 ns + +**Exponential backoff:** +- A draws K=0 → Backoff time = 0 × 512 bits = 0 bits = 0 ns +- B draws K=1 → Backoff time = 1 × 512 bits = 512 bits = 512 ns + +### Step 3: Calculate A's complete packet delivery time + +**Timeline for A's successful transmission:** +- t = 0: Initial collision occurs +- t = 48 ns: Jam signal ends +- t = 48 ns: A waits 0 ns (K=0), B waits 512 ns +- t = 48 ns: A starts retransmission (B still in backoff) +- t = 48 ns + 1,024 ns: A finishes transmission = 1,072 ns +- t = 1,072 ns + 960 ns: Signal propagates to B = 2,032 ns + +**A's packet is completely delivered at B at t = 2,032 ns = 2.032 μs** + +## Part (b): Switches instead of repeaters with 8-bit processing delay + +### Modified scenario: +- Only A has packet to send +- 3 switches replace repeaters +- Each switch: 8-bit processing delay + store-and-forward delay +- Store-and-forward delay = 1,024 bits (full packet) + +### Switch delay calculation: +**Per switch delay:** +- Processing delay: 8 bits = 8 ns +- Store-and-forward delay: 1,024 bits = 1,024 ns +- Total per switch: 8 + 1,024 = 1,032 ns + +**Total switch delays:** +- 3 switches × 1,032 ns = 3,096 ns = 3.096 μs + +**Physical propagation delay:** +- Same as before: 0.9 μs + +### Timeline for switch-based transmission: +- t = 0: A starts transmission +- t = 1,024 ns: A completes transmission to first switch +- t = 1,024 + 1,032 = 2,056 ns: First switch forwards +- t = 2,056 + 1,032 = 3,088 ns: Second switch forwards +- t = 3,088 + 1,032 = 4,120 ns: Third switch forwards +- t = 4,120 + 900 = 5,020 ns: Signal reaches B + +**A's packet is delivered at B at t = 5.020 μs** + +## Detailed CSMA/CD Analysis + +### Collision Detection Process: +1. **Initial Transmission**: Both nodes detect carrier as free and begin transmission +2. **Collision Occurrence**: Signals interfere when they meet on the medium +3. **Collision Detection**: Each node detects voltage levels exceeding normal thresholds +4. **Jam Signal**: Both nodes transmit 48-bit jam signal to ensure all nodes detect collision +5. **Backoff Algorithm**: Exponential backoff with binary exponential backoff (BEB) + +### Why RTT is Critical for CSMA/CD: +- **Collision Detection Window**: Must detect collision within one round-trip time +- **Minimum Frame Size**: Frame transmission time must exceed RTT to ensure collision detection +- **Network Diameter Limit**: RTT constrains maximum network size +- **Slot Time**: Backoff intervals based on worst-case RTT scenarios + +### Performance Considerations: +- **Efficiency**: η = 1/(1 + 6.44 × a) where a = RTT×bandwidth/frame_size +- **Throughput Degradation**: Higher collision rates reduce effective throughput +- **Network Utilization**: Optimal performance requires balanced frame size vs. propagation delay + +**Key Insight**: CSMA/CD performance is fundamentally limited by propagation delay, which determines collision detection capabilities and minimum frame sizes. The replacement of repeaters with switches eliminates collision domains but introduces store-and-forward delays that can significantly impact end-to-end latency for larger networks. ### 2.4 802.11 RTS/CTS Transmission (10%) **Given:** -- 802.11 station with RTS/CTS -- 1024 bytes of data -- All other stations idle +- 802.11 station configured to always use RTS/CTS +- 1024 bytes of data to transmit +- All other stations idle at t = 0 +- Station wants to transmit at t = 0 + +## 802.11 Frame Specifications + +**Standard 802.11 frame sizes and timing parameters:** +- **RTS frame:** 20 bytes (160 bits) +- **CTS frame:** 14 bytes (112 bits) +- **ACK frame:** 14 bytes (112 bits) +- **Data frame:** 1024 bytes payload + 28 bytes header = 1052 bytes (8416 bits) +- **SIFS (Short Interframe Space):** 10 μs +- **DIFS (Distributed Interframe Space):** 50 μs +- **Slot time:** 20 μs +- **Data rate:** 11 Mbps (802.11b standard assumption) + +## RTS/CTS Protocol Sequence + +### Step 1: Channel Access and RTS Transmission + +**t = 0:** Station wants to transmit +- **DIFS wait:** Station must wait DIFS before accessing idle channel +- **t = 0 to 50 μs:** Station waits DIFS period +- **t = 50 μs:** Station begins RTS transmission + +**RTS transmission time:** +- RTS frame size: 160 bits +- Transmission time = 160 bits ÷ 11 Mbps = 14.55 μs +- **t = 50 μs to 64.55 μs:** RTS transmission + +### Step 2: CTS Response + +**SIFS wait after RTS:** +- **t = 64.55 μs to 74.55 μs:** SIFS period (10 μs) +- **t = 74.55 μs:** Access Point begins CTS transmission + +**CTS transmission time:** +- CTS frame size: 112 bits +- Transmission time = 112 bits ÷ 11 Mbps = 10.18 μs +- **t = 74.55 μs to 84.73 μs:** CTS transmission + +### Step 3: Data Transmission + +**SIFS wait after CTS:** +- **t = 84.73 μs to 94.73 μs:** SIFS period (10 μs) +- **t = 94.73 μs:** Station begins data transmission + +**Data frame transmission time:** +- Data frame size: 8416 bits (1024 bytes payload + 28 bytes header) +- Transmission time = 8416 bits ÷ 11 Mbps = 765.09 μs +- **t = 94.73 μs to 859.82 μs:** Data transmission + +**Station completes transmission at t = 859.82 μs** + +### Step 4: ACK Reception + +**SIFS wait after data:** +- **t = 859.82 μs to 869.82 μs:** SIFS period (10 μs) +- **t = 869.82 μs:** Access Point begins ACK transmission + +**ACK transmission time:** +- ACK frame size: 112 bits +- Transmission time = 112 bits ÷ 11 Mbps = 10.18 μs +- **t = 869.82 μs to 880 μs:** ACK transmission + +**Station receives acknowledgment at t = 880 μs** + +## Complete Timeline Summary + +| Time (μs) | Event | Duration (μs) | +|-----------|-------|---------------| +| 0 - 50 | DIFS wait | 50.00 | +| 50 - 64.55 | RTS transmission | 14.55 | +| 64.55 - 74.55 | SIFS wait | 10.00 | +| 74.55 - 84.73 | CTS transmission | 10.18 | +| 84.73 - 94.73 | SIFS wait | 10.00 | +| 94.73 - 859.82 | Data transmission | 765.09 | +| 859.82 - 869.82 | SIFS wait | 10.00 | +| 869.82 - 880.00 | ACK transmission | 10.18 | + +## Answers to Questions + +### When does the station complete transmission? +**The station completes transmission at t = 859.82 μs** + +This represents the end of the data frame transmission. The actual data payload has been fully transmitted to the access point. + +### When can the station receive the acknowledgment? +**The station receives the acknowledgment at t = 880.00 μs** + +This marks the successful completion of the entire RTS/CTS/Data/ACK sequence. + +## Protocol Analysis + +### RTS/CTS Benefits Demonstrated: +1. **Hidden Node Protection:** RTS/CTS sequence reserves the channel for the entire data transmission +2. **Collision Avoidance:** Other stations hear either RTS or CTS and defer transmission +3. **Channel Reservation:** Duration field in RTS/CTS frames reserves channel for complete sequence +4. **Efficiency for Large Frames:** Overhead is justified for larger data frames like the 1024-byte payload + +### Timing Overhead Analysis: +- **Total sequence time:** 880 μs +- **Actual data transmission time:** 765.09 μs +- **Protocol overhead time:** 114.91 μs (13.1% overhead) +- **Overhead breakdown:** + - DIFS: 50 μs (5.7%) + - RTS/CTS frames: 24.73 μs (2.8%) + - SIFS periods: 30 μs (3.4%) + - ACK frame: 10.18 μs (1.2%) + +### Performance Considerations: +- **Efficiency:** 86.9% channel utilization for data transmission +- **Latency:** 880 μs total time for 1024-byte frame transmission +- **Throughput:** Effective data rate ≈ 9.3 Mbps (considering protocol overhead) -[To be completed] +**Key Insight:** The RTS/CTS mechanism trades modest protocol overhead (13.1%) for robust collision avoidance and hidden node protection, making it particularly valuable in wireless environments with potential hidden nodes or high collision probability. ### 2.5 Bluetooth Frame Format Analysis (10%) -- cgit v1.2.3