Dr. Mark Humphrys

School of Computing. Dublin City University.

Home      Blog      Teaching      Research      Contact

My big idea: Ancient Brain


CA114      CA170

CA668      CA669      Projects

3.1.2 Framing

How does receiver detect start and end of a frame?
Listening on a wire, nothing may be sent for long periods. How do we avoid "reading" the thermal noise as data?

Time gaps between frames

Like spaces between words. Won't work. Transmission delays may remove some gaps and introduce new ones.

Character count

Field in header gives no. of chars in frame.
Shown in (a) below. Char count includes the counting character itself:


Problem shown in (b). Transmission error changed 5 to 7. All frames now out of synch.
Even if we detect error, we have no way of recovering - of finding where next frame starts.


Note on detecting error:
There will be an overall check of the frame when it gets through (see "checksum" methods later), so normally we do know that the frame was bad. We do not accept any random stream of bits. The issue is can we find the next frame.

Start and end bytes (with byte stuffing)

Each frame starts with special start and end bytes (flag bytes). Here will imagine it as same byte, FLAG.
After error, can always find start of next frame.
See (a) below:

Q. What if flag byte itself is in the data?
Probably won't happen for text data, but could easily happen with binary data.
A. Insert special escape byte (ESC) before each FLAG in data. Removed at far end. This is called byte stuffing or character stuffing.

Q. What if ESC itself is in data?
A. Insert another ESC before it.
See (b) above.

De-stuffing recovers original chars.

What if control bytes themselves get corrupted?

Q. Say ESC byte gets corrupted by noise. Detect pre-mature end-of-frame.
Or FLAG byte gets corrupted and frame runs on too long.

A. Frame checksum figures this is bad frame.
Can still find next frame by looking for next FLAG. At most lose 1 or 2 frames.

Error-detection in general

Q. What if all ESC and FLAG bytes get corrupted?

A. All error-detection and correction methods only work below a certain error rate

Start and end flags (with bit stuffing)

Byte stuffing specifies char format (e.g. 8 bits per char).
To allow arbitrary no. of bits per char, use stuffing at bit-level rather than at byte-level.

Each frame begins and ends with bit pattern 01111110 (6 1's)
If 5 1's in a row in data, stuff a 0 in so will never be 6 in a row.
Stuff it in always - whether the next char was going to be a 1 or not.
De-stuffer removes the 0's after any 5 1's.

(a) Original data.
(b) Stuffed data transmitted.
(c) De-stuffed data received.

Might use all these methods:
Character count, start and end flags, and checksum.

ancientbrain.com      w2mind.org      humphrysfamilytree.com

On the Internet since 1987.

Wikipedia: Sometimes I link to Wikipedia. I have written something In defence of Wikipedia. It is often a useful starting point but you cannot trust it. Linking to it is like linking to a Google search. A starting point, not a destination. I automatically highlight in red all links to Wikipedia and Google search and other possibly-unreliable user-generated content.