EE 122: Encoding And FramingOverviewEncodingAssumptionsNon-Return to Zero (NRZ)Non-Return to Zero Inverted (NRZI)Manchester4-bit/5-bitSlide 9FramingByte-Oriented Protocols: Sentinel ApproachByte-Oriented Protocols: Byte Counting ApproachBit-Oriented ProtocolsClock-Based Framing (SONET)Slide 15Slide 16SummaryEE 122: Encoding And FramingIon StoicaSeptember 9, [email protected] 2OverviewEncoding[email protected] 3EncodingGoal: send bits from one node to another node on the same physical media-This service is provided by the physical layerProblem: specify a robust and efficient encoding scheme to achieve this goalAdaptorAdaptorAdaptorAdaptorSignalAdaptor: convert bits into physical signal and physical signal back into [email protected] 4AssumptionsWe use two discrete signals, high and low, to encode 0 and 1The transmission is synchronous, i.e., there is a clock used to sample the signal-In general, the duration of one bit is equal to one or two clock [email protected] 5Non-Return to Zero (NRZ)1 high signal; 0 low signal00 1 0 1 0 1 1 0NRZ(non-return to zero)ClockDisadvantages: when there is a long sequence of 1’s or 0’s-Sensitive to clock skew, i.e., difficult to do clock recovery -Difficult to interpret 0’s and 1’s (baseline wander)[email protected] 6Non-Return to Zero Inverted (NRZI)1 make transition; 0 stay at the same levelSolve previous problems for long sequences of 1’s, but not for 0’s00 1 0 1 0 1 1 0ClockNRZI(non-return to zero intverted)[email protected] 7Manchester1 high-to-low transition; 0 low-to-high transitionAddresses clock recovery and baseline wander problemsDisadvantage: needs a clock that is twice as fast as the transmission rate00 1 0 1 0 1 1 [email protected] 84-bit/5-bitGoal: address inefficiency of Manchester encoding, while avoiding long periods of low or high signalsSolution:-Use 5 bits to encode every sequence of four bits such that no 5 bit code has more than one leading 0 and two trailing 0’s-Use NRZI to encode the 5 bit codes 0000 111100001 010010010 101000011 101010100 010100101 010110110 011101111 011111000 100101001 100111010 101101011 101111100 110101101 110111110 111001111 111014-bit 5-bit 4-bit [email protected] 9OverviewEncoding[email protected] 10FramingGoal: send a block of bits (frames) between nodes connected on the same physical media-This service is provided by the data link layerUse a special byte (bit sequence) to mark the beginning (and the end) of the frame Problem: what happens if this sequence appears in the data [email protected] 11Byte-Oriented Protocols: Sentinel ApproachSTX – start of textETX – end of text Problem: what if ETX appears in the data portion of the frame?Solution-If ETX appears in the data, introduce a special character DLE (Data Link Escape) before it-If DLE appears in the text, introduce another DLE character before itProtocol examples-BISYNC, PPP, DDCMPText (Data)STX [email protected] 12Byte-Oriented Protocols: Byte Counting ApproachSender: insert the length of the data (in bytes) at the beginning of the frame, i.e., in the frame headerReceiver: extract this length and decrement it every time a byte is read. When this counter becomes zero, we are [email protected] 13Bit-Oriented ProtocolsBoth start and end sequence can be the same-E.g., 01111110 in HDLC (High-level Data Link Protocol)Sender: inserts a 0 after five consecutive 1sReceiver: when it sees five 1s makes decision on the next two bits-if next bit 0 (this is a stuffed bit), remove it-if next bit 1, look at the next bit•If 0 this is end-of-frame (receiver has seen 01111110) •If 1 this is an error, discard the frame (receiver has seen 01111111)Text (Data)[email protected] 14Clock-Based Framing (SONET)SONET (Synchronous Optical NETwork)Example: SONET ST-1: 51.84 [email protected] 15Clock-Based Framing (SONET)First two bytes of each frame contain a special bit pattern that allows to determine where the frame startsNo bit-stuffing is usedReceiver looks for the special bit pattern every 810 bytes-Size of frame = 9x90 = 810 bytes90 columns9 rowsData (payload)overheadSONET STS-1 [email protected] 16Clock-Based Framing (SONET)Details:-Overhead bytes are encoded using NRZ-To avoid long sequences of 0’s or 1’s the payload is XOR-ed with a special 127-bit patter with many transitions from 1 to [email protected] 17SummaryEncoding – specify how bits are transmitted on the physical mediaChallenge – achieve: -Efficiency – ideally, bit rate = clock rate-Robust – avoid de-synchronization between sender and receiver when there is a large sequence of 1’s or 0’s Framing – specify how blocks of data are transmittedChallenge-Decide when a frame starts/ends-Differentiate between the true frame delimiters and delimiters appearing in the payload
View Full Document