Framing - Bit Stuffing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Bit Stuffing Distinction Levels:
 
┌─────────────────────────────────────────────────────────────────┐
│                    Consecutive 1s Interpretation                │
├─────────────────────────────────────────────────────────────────┤
│  0 to 5 consecutive 1s:  NORMAL DATA                            │
│                          → Pass through to upper layer          │
│                                                                 │
│  5 consecutive 1s + 0:   STUFFED BIT DETECTED                   │
│                          → Discard the 0, keep the five 1s      │
│                                                                 │
│  6 consecutive 1s + 0:   FLAG PATTERN (01111110)                │
│                          → Frame boundary detected              │
│                                                                 │
│  7+ consecutive 1s:      ABORT SEQUENCE                         │
│                          → Discard current frame, reset         │
└─────────────────────────────────────────────────────────────────┘
 
The "one extra 1" between each level creates:
• 1-bit margin between data and flags
• 1-bit margin between flags and aborts
• Clear separation for reliable detection

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

def bit_stuff(data_bits: list[int]) -> list[int]:
    """
    Perform bit stuffing on input data.
    
    After every 5 consecutive 1s, inserts a 0 bit.
    This ensures the flag pattern (01111110) cannot appear in data.
    
    Args:
        data_bits: List of input data bits (0 or 1)
        
    Returns:
        List of stuffed bits (always longer than or equal to input)
    """
    stuffed_output = []
    consecutive_ones = 0
    
    for bit in data_bits:
        # Always output the current data bit
        stuffed_output.append(bit)
        
        if bit == 1:
            consecutive_ones += 1
            
            # After 5 consecutive 1s, stuff a 0
            if consecutive_ones == 5:
                stuffed_output.append(0)  # Insert stuffed bit
                consecutive_ones = 0       # Reset counter
                # Note: counter resets because we just output a 0
        else:
            consecutive_ones = 0  # Reset on any 0
    
    return stuffed_output
 
 
def demonstrate_stuffing():
    """Demonstrate bit stuffing with various input patterns."""
    
    test_cases = [
        # Case 1: Normal data (no stuffing needed)
        [1, 0, 1, 0, 1, 0, 1, 0],
        
        # Case 2: Exactly 5 ones (triggers stuffing)
        [1, 1, 1, 1, 1, 0, 0, 0],
        
        # Case 3: 6 consecutive ones (would be flag without stuffing)
        [1, 1, 1, 1, 1, 1, 0, 0],
        
        # Case 4: 8 consecutive ones (multiple stuffs needed)
        [1, 1, 1, 1, 1, 1, 1, 1],
        
        # Case 5: Worst case - all ones
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        
        # Case 6: Contains exact flag pattern in data
        [0, 1, 1, 1, 1, 1, 1, 0],  # 01111110 = flag!
    ]
    
    print("Bit Stuffing Demonstration")
    print("=" * 60)
    
    for i, data in enumerate(test_cases, 1):
        stuffed = bit_stuff(data)
        overhead = len(stuffed) - len(data)
        
        print(f"\nCase {i}:")
        print(f"  Input:   {''.join(map(str, data))} ({len(data)} bits)")
        print(f"  Stuffed: {''.join(map(str, stuffed))} ({len(stuffed)} bits)")
        print(f"  Overhead: {overhead} bit(s) ({100*overhead/len(data):.1f}%)")
 
 
if __name__ == "__main__":
    demonstrate_stuffing()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

Input Data: 1 1 1 1 1 1 1 0
            ^------------------- Process bit by bit
 
Step 1: Read bit 1
        Output: 1
        Consecutive 1s: 1
 
Step 2: Read bit 1
        Output: 1
        Consecutive 1s: 2
 
Step 3: Read bit 1
        Output: 1
        Consecutive 1s: 3
 
Step 4: Read bit 1
        Output: 1
        Consecutive 1s: 4
 
Step 5: Read bit 1
        Output: 1
        Consecutive 1s: 5
        → STUFF A ZERO!
        Output: 0 (stuffed)
        Consecutive 1s: 0 (reset)
 
Step 6: Read bit 1
        Output: 1
        Consecutive 1s: 1
 
Step 7: Read bit 1
        Output: 1
        Consecutive 1s: 2
 
Step 8: Read bit 0
        Output: 0
        Consecutive 1s: 0 (reset)
 
RESULT:
  Input:  1 1 1 1 1 1 1 0     (8 bits)
  Output: 1 1 1 1 1 0 1 1 0   (9 bits)
                  ^
                  Stuffed bit prevents 01111110 formation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

def bit_destuff(stuffed_bits: list[int]) -> dict:
    """
    Remove stuffed bits from input stream.
    
    After every 5 consecutive 1s, the next bit (which must be 0)
    is discarded as it was a stuffed bit.
    
    Args:
        stuffed_bits: List of stuffed bits received
        
    Returns:
        Dictionary with:
        - 'data': Recovered original data bits
        - 'stuffed_count': Number of stuffed bits removed
        - 'error': Error message if invalid sequence detected
    """
    original_data = []
    consecutive_ones = 0
    stuffed_count = 0
    skip_next = False
    
    for i, bit in enumerate(stuffed_bits):
        # If we're skipping (expecting stuffed 0 after 5 ones)
        if skip_next:
            if bit == 0:
                stuffed_count += 1  # Count the removed stuffed bit
            else:
                # Error: Expected stuffed 0 but got 1
                return {
                    'data': original_data,
                    'stuffed_count': stuffed_count,
                    'error': f'Expected stuffed 0 at position {i}, got 1'
                }
            skip_next = False
            consecutive_ones = 0  # Reset after handling stuffed bit
            continue
        
        # Normal bit processing
        original_data.append(bit)
        
        if bit == 1:
            consecutive_ones += 1
            if consecutive_ones == 5:
                # Next bit should be stuffed 0
                skip_next = True
        else:
            consecutive_ones = 0
    
    return {
        'data': original_data,
        'stuffed_count': stuffed_count,
        'error': None
    }
 
 
def demonstrate_destuffing():
    """Demonstrate bit destuffing with step-by-step output."""
    
    test_cases = [
        # Example 1: Single stuffed bit
        [1, 1, 1, 1, 1, 0, 1, 1, 0],
        
        # Example 2: Multiple stuffed bits
        [1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0],
        
        # Example 3: No stuffing needed (random data)
        [1, 0, 1, 1, 0, 1, 0, 0],
    ]
    
    print("Bit Destuffing Demonstration")
    print("=" * 60)
    
    for i, stuffed in enumerate(test_cases, 1):
        result = bit_destuff(stuffed)
        
        print(f"\nCase {i}:")
        print(f"  Stuffed input: {''.join(map(str, stuffed))}")
        print(f"  Recovered:     {''.join(map(str, result['data']))}")
        print(f"  Stuffed bits removed: {result['stuffed_count']}")
        if result['error']:
            print(f"  Error: {result['error']}")
 
 
def verify_roundtrip():
    """Verify that stuffing followed by destuffing recovers original data."""
    
    # Test with various challenging patterns
    test_data = [
        [1, 1, 1, 1, 1, 1, 1, 1],  # Long run of ones
        [0, 1, 1, 1, 1, 1, 1, 0],  # Would-be flag pattern
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],  # 15 ones
        [1, 0] * 50,               # Alternating pattern
    ]
    
    print("\n\nRound-Trip Verification")
    print("=" * 60)
    
    for original in test_data:
        # Stuff the data
        stuffed = bit_stuff(original)
        # Destuff the result
        result = bit_destuff(stuffed)
        recovered = result['data']
        
        # Verify equality
        match = original == recovered
        
        print(f"\nOriginal ({len(original)} bits): {''.join(map(str, original[:20])}{'...' if len(original) > 20 else ''}")
        print(f"Stuffed  ({len(stuffed)} bits):  {''.join(map(str, stuffed[:25])}{'...' if len(stuffed) > 25 else ''}")
        print(f"Recovered: {'✓ MATCH' if match else '✗ MISMATCH'}")
 
 
if __name__ == "__main__":
    demonstrate_destuffing()
    verify_roundtrip()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

Input (Stuffed): 1 1 1 1 1 0 1 1 0
                           ^----- This is the stuffed bit
 
Step 1: Read bit 1
        Output to data: 1
        Consecutive 1s: 1
        
Step 2: Read bit 1
        Output to data: 1
        Consecutive 1s: 2
 
Step 3: Read bit 1
        Output to data: 1
        Consecutive 1s: 3
 
Step 4: Read bit 1
        Output to data: 1
        Consecutive 1s: 4
 
Step 5: Read bit 1
        Output to data: 1
        Consecutive 1s: 5
        → Next bit is stuffed, prepare to skip
 
Step 6: Read bit 0
        SKIP THIS BIT (stuffed)
        No output to data
        Consecutive 1s: 0 (reset)
 
Step 7: Read bit 1
        Output to data: 1
        Consecutive 1s: 1
 
Step 8: Read bit 1
        Output to data: 1
        Consecutive 1s: 2
 
Step 9: Read bit 0
        Output to data: 0
        Consecutive 1s: 0 (reset)
 
RESULT:
  Stuffed input: 1 1 1 1 1 0 1 1 0  (9 bits)
  Original data: 1 1 1 1 1 1 1 0    (8 bits)
  
PERFECT RECOVERY: Original data is restored exactly!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

Complete Bit-Stuffing Frame Transmission Pipeline:
 
SENDER SIDE:
============
 
1. Application Data (Network Layer)
   ┌───────────────────────────────────────────┐
   │  Original frame contents (any bit pattern) │
   │  Example: 01111110 11111111 00000000       │
   └───────────────────────────────────────────┘
                      ↓
                      
2. Bit Stuffing (Data Link Layer)
   ┌───────────────────────────────────────────┐
   │  Insert 0 after every 5 consecutive 1s    │
   │  01111(0)110 11111(0)11(0)1 00000000      │
   └───────────────────────────────────────────┘
                      ↓
                      
3. Add Flags (Data Link Layer)
   ┌───────────────────────────────────────────┐
   │  Prepend and append 01111110 flag         │
   │  01111110 [stuffed data] 01111110         │
   └───────────────────────────────────────────┘
                      ↓
                      
4. Physical Transmission
   ┌───────────────────────────────────────────┐
   │  Convert to voltage/light/RF signals      │
   │  ~~~~~~↗↘~~~~↗↘↗~~~~↗↘~~~~               │
   └───────────────────────────────────────────┘
 
 
RECEIVER SIDE:
==============
 
5. Physical Reception
   ┌───────────────────────────────────────────┐
   │  Sample and recover bit stream            │
   │  01111110 [stuffed data] 01111110         │
   └───────────────────────────────────────────┘
                      ↓
                      
6. Flag Detection (Data Link Layer)
   ┌───────────────────────────────────────────┐
   │  Identify frame boundaries                │
   │  Extract: [stuffed data]                  │
   └───────────────────────────────────────────┘
                      ↓
                      
7. Bit Destuffing (Data Link Layer)
   ┌───────────────────────────────────────────┐
   │  Remove 0 after every 5 consecutive 1s   │
   │  Recover: 01111110 11111111 00000000      │
   └───────────────────────────────────────────┘
                      ↓
                      
8. Deliver to Network Layer
   ┌───────────────────────────────────────────┐
   │  Original frame contents restored exactly │
   └───────────────────────────────────────────┘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

PROOF: Flag Pattern Cannot Appear in Stuffed Data
==================================================
 
Lemma: Bit stuffing inserts a 0 after every 5 consecutive 1s.
 
Assume (for contradiction) that 01111110 appears in stuffed output.
 
Case 1: All six 1s came from original data (no stuffed bit among them)
        
        If data contained 111111 (six consecutive 1s):
        - After 5th one, algorithm inserts 0
        - Output becomes: 11111(0)1...
        - Maximum consecutive 1s is 5, not 6
        - Contradiction: Six consecutive 1s cannot form
        
Case 2: Some of the six 1s are stuffed bits
        
        Stuffed bits are always 0, never 1.
        Therefore stuffed bits cannot be among the six 1s.
        - Contradiction: No stuffed 1 bits exist
        
Case 3: The six 1s span across a stuffed 0
        
        To get: 011111 [stuffed 0] 10
        The stuffed 0 breaks the sequence.
        Cannot have 6 consecutive 1s spanning a 0.
        - Contradiction: Sequence is broken
 
Conclusion: In all cases, contradiction is reached.
            Therefore 01111110 CANNOT appear in stuffed data.  ∎

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

PROOF: Perfect Data Recovery
=============================
 
Key Insight: Stuffed bits are uniquely identifiable.
 
For any bit in the stuffed output, exactly one of these is true:
1. It's a data bit that followed <5 consecutive 1s
2. It's a data bit that is the 5th consecutive 1
3. It's a stuffed 0 inserted after 5 consecutive 1s
 
The receiver can distinguish these cases because:
- It counts consecutive 1s
- A 0 following exactly 5 ones is ALWAYS stuffed
- All other 0s are data bits
- All 1s are data bits
 
Proof by induction on data length:
 
Base case: data = [] (empty)
    stuff([]) = []
    destuff([]) = []  ✓
 
Inductive step: Assume property holds for data of length n.
                Prove for data of length n+1.
 
Let data' = data + [bit] where bit ∈ {0, 1}
 
Case A: bit = 0
    No stuffing triggered. Stuffed output has one more 0.
    Destuffer sees 0 (not after 5 ones), keeps it.
    Recovery: correct  ✓
 
Case B: bit = 1, not the 5th consecutive
    No stuffing triggered. Stuffed output has one more 1.
    Destuffer sees 1, increments counter, keeps it.
    Recovery: correct  ✓
 
Case C: bit = 1, the 5th consecutive
    Stuffing triggered. Output has: ...1 (data) 0 (stuffed)
    Destuffer sees 5th one, keeps it, then skips next 0.
    Recovery: correct  ✓
 
By induction, property holds for all data lengths.  ∎

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

class ByteAlignedBitStuffer:
    """
    Bit stuffer that works with byte-aligned input/output.
    
    Handles the complexity of bit-level operations on byte streams.
    """
    
    def __init__(self):
        self.pending_bits = []  # Bits awaiting byte completion
        
    def stuff_bytes(self, data_bytes: bytes) -> tuple[bytes, int]:
        """
        Stuff bytes of data, return stuffed bytes and bit count.
        
        Returns:
            (stuffed_bytes, total_bit_count)
            The last byte may be partially filled.
        """
        # Convert bytes to bits
        data_bits = []
        for byte in data_bytes:
            for i in range(7, -1, -1):
                data_bits.append((byte >> i) & 1)
        
        # Apply bit stuffing
        stuffed_bits = []
        consecutive_ones = 0
        
        for bit in data_bits:
            stuffed_bits.append(bit)
            if bit == 1:
                consecutive_ones += 1
                if consecutive_ones == 5:
                    stuffed_bits.append(0)  # Stuff a zero
                    consecutive_ones = 0
            else:
                consecutive_ones = 0
        
        # Convert bits back to bytes (padding if necessary)
        stuffed_bytes = []
        bit_count = len(stuffed_bits)
        
        # Pad to byte boundary
        while len(stuffed_bits) % 8 != 0:
            stuffed_bits.append(0)  # Padding (tracked separately)
        
        for i in range(0, len(stuffed_bits), 8):
            byte_val = 0
            for j in range(8):
                byte_val = (byte_val << 1) | stuffed_bits[i + j]
            stuffed_bytes.append(byte_val)
        
        return bytes(stuffed_bytes), bit_count
 
 
# Demonstration
stuffer = ByteAlignedBitStuffer()
test_data = bytes([0xFF, 0xFF])  # All ones - maximum stuffing
stuffed, bit_count = stuffer.stuff_bytes(test_data)
 
print(f"Input: {test_data.hex()} ({len(test_data)*8} bits)")
print(f"Stuffed: {stuffed.hex()} ({bit_count} actual bits)")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

Synchronization Recovery Procedure:
 
State: Receiver is synchronized but errors occur
 
1. Flag Detection Fails:
   [Normal Frame] [Corrupted Flag] [Next Frame]
                  ^^^^^^^^^^^^
                  Receiver doesn't see end of first frame
   
   → CRC check on (combined content) will fail
   → Receiver discards and waits for next valid flag
   
2. False Flag Detection:
   [Frame Start] [Data with error creating 01111110] [Real End]
                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                 Corrupted data looks like flag
   
   → Frame appears shorter than expected
   → CRC check fails (wrong data in calculation)
   → Receiver discards and resynchronizes
   
3. Recovery Strategy:
   After any CRC failure:
   - Discard current buffer
   - Enter "hunt mode" - scan for valid flag
   - Wait for 01111110 pattern
   - Resume normal reception after flag
   
4. Idle Fill During Recovery:
   Sender can transmit: 01111110 01111110 01111110...
   These continuous flags help receiver regain sync