Networking Encoding and Framing Notes

Shannon's Theorem

• Example with a voice-grade phone line:
  • Bandwidth $B = 3300 - 300 \text{ Hz} = 3 \text{ KHz}$
  • Typical Signal-to-Noise Ratio (SNR) = 30 dB, where $dB = 10 \times \log_{10}(S/N)$
  • For 30 dB, $S/N = 1000$
  • Capacity $C = 3000 \times \log_2(1 + 1000) \approx 30 \text{ Kbps}$
  • Higher bandwidth $B$ (in Hz) results in higher capacity.
  • Is it possible to achieve infinite capacity by infinitely increasing $B$? The limit is $S/(n<em>0 \ln 2) = 1.44 S/n</em>0$
  • Higher $S/N$ also yields higher capacity.

Shannon's Theorem: Example 2

• Can the signal be weaker than noise?
  • Assume a capacity of 50 Kbps over a 1 MHz bandwidth.
  • The required SNR is then:
    • $C = B \log_2(1 + S/N)$
    • $S/N = 2^{C/B} - 1 = 0.035$, or -14.5 dB
• Spread Spectrum Communications (e.g., CDMA):
  • Transmit a weak signal over a large bandwidth.
  • Advantages: low-power communication, secure/stealthy communication, anti-jamming, etc.

Relating Nyquist and Shannon

• Assume $B = 1 \text{ MHz}$ and SNR = 24 dB.
• How many signal levels (or different symbols) are required to achieve the max rate?
  • $24 \text{ dB} = 10 \log_{10}(S/N) \rightarrow S/N = 10^{2.4} = 251$
• Using Shannon's formula:
  • $C = 10^6 \times \log_2(1 + 251) = 10^6 \times 8 = 8 \text{ Mbps}$
• Theoretical limit.
• Using Nyquist's theorem:
  • max symbol rate $= 2B = 2 \text{ Msymbol/s}$
  • Each symbol should carry $8/2 = 4$ bits.
  • To enable that, $M = 16$ different symbols should be used because the # of bits carried by a symbol is $\log_2 M = 4 \rightarrow M = 16$.

Encoding

• Signals travel between signaling components; bits flow between adaptors.
• NRZ (Non-return-to-zero) encoding of a bit stream.

Encoding: Problems with NRZ

• Baseline Wander:
  • The receiver keeps an average of the signals it has seen so far.
  • Uses the average to distinguish between low and high signal.
  • When a signal is significantly lower than the average, it is 0, else it is 1.
  • Too many consecutive 0's and 1's cause this average to change, making it difficult to detect.
• Clock Recovery:
  • Frequent transitions from high to low or vice versa are necessary to enable clock recovery.
  • Both the sending and decoding process is driven by a clock.
  • Every clock cycle, the sender transmits a bit and the receiver recovers a bit.
  • The sender and receiver have to be precisely synchronized.

Encoding: NRZI

• NRZI (level change to represent 1) – Non Return to Zero Inverted
  • Sender makes a transition from the current signal to encode 1 and stays at the current signal to encode 0.
  • Solves for consecutive 1’s.

Encoding: Manchester Encoding

• Manchester encoding (using flip for 0 and 1):
  • Merging the clock with signal by transmitting Ex-OR of the NRZ encoded data and the clock.
  • Clock is an internal signal that alternates from low to high; a low/high pair is considered as one clock cycle.
  • In Manchester encoding:
    • 0: low → high transition
    • 1: high → low transition

Encoding: Example

• Different encoding strategies are visualized (NRZ, Clock, Manchester, NRZI) for the bit sequence 0010111101000010.

Encoding: Problems with Manchester

• Doubles the rate at which the signal transitions are made on the link.
  • The receiver has half of the time to detect each pulse of the signal.
  • The rate at which the signal changes is called the link’s baud rate.
  • In Manchester, the bit rate is half the baud rate.

4b/5b Encoding Scheme

• To solve low coding efficiency of the Manchester encoding (50%).
• Encode 4-bit symbols into 5-bit codes (insert extra bits to break the sequence of long “0”s).
  • A 4-bit original is mapped into a 5-bit codeword.
  • Each codeword has no more than one starting zero, and no more than two trailing zeros.
  • No more than 3 consecutive zeros.
  • Then use NRZI to solve the consecutive 1s problem.
  • 80% efficiency (1 bit is overhead).

Example of 4b/5b Encoding

• A table illustrates the mapping between 4-bit data symbols and their corresponding 5-bit codes.

Framing

• The process of grouping bits into frames (messages or packets).
• Typically implemented by the network adaptor.
• Why frames? Easy to process because you get boundaries and structures!

Byte-Oriented Framing

• BISYNC: Binary synchronous communication.
  • Frame is a collection of bytes.
  • Need to indicate the beginning and end of a frame.
  • Sentinel characters are used:
    • SYN: Synchronization character.
    • SOH: Start of header.
    • STX, ETX: Start of text, End of text.
    • CRC: Cyclic redundancy check.

Engineering Problems in Framing

1. How do you identify the beginning and ending of a frame?
   • Answer: use “flags” (pre-defined bit/byte sequence).
2. How do you differentiate these flags from the same sequence in the payload?
   • Answer 1: Precede it with a DLE (data-link-escape) character.

Byte-counting Framing

• Answer 2: Include the # of bytes in the frame as a field in the header (PPP).
• Digital Data Communications Protocol (DDCMP).
  • Count: Specifies # of bytes in the body.
  • CRC ensures that count field is not corrupted.

Bit-oriented Framing

• Answer 3: bit stuffing.
• High-Level Data Link Control (HDLC).
  • Beginning/end of frame, flag: 01111110.
  • In the body, instead of inserting bytes do bit stuffing.
  • Sender adds a 0 after five consecutive 1s.
  • Receiver removes zero after five 1s, so there won’t be more than 5 consecutive “1”s in the body of the frame.

Example of Bit-stuffing

• Illustrates bit stuffing process at the sender and removal at the receiver.
• Length of frame: Variable, depends on the data.