Question

Consider a framing strategy in which you receive an infinite sequence of bytes 
(a byte-oriented scheme), and you begin each message with a special byte, SOF 
(start of frame), and end the message with a EOF (end of frame). Assume that the 
user very frequently in its data includes bytes whose values are equal to the SOF 
or EOF byte (possibly many in each message).
Design a byte-oriented protocol(give me some pseudocode or a good english description, you don't have to use my 
notation) such that it creates the smallest amount of overhead possible.

This is all information i have.

Answer 1

To exactly decode the encoded frame, we need to ensure that there's no ambiguity (in terms of characters like SOF and EOF).

Problems in framing:

1. Detecting the start of frame

2. Detecting the end of frame

Both of these problems can be solved with the help of bit stuffing. The framing algorithm inserts a bit if at any point SOF/EOF appears anywhere in the data.

For every byte, check if you've already encountered SOF. In that case, the SOF is in the data and you need to break it using bit stuffing.

Similarly, for EOF - check if the previous delimiter you encountered was a EOF. If yes, then the previous delimiter was data instead of EOF because the current EOF is the actual EOF. In that case, the previous EOF needs to be broken.

How to break an EOF/SOF :-

Say that the bit representation of EOF is 01111 and the data to be broken is also 01111. Just prepend a 0 to the last 1 you encountered, converting it to 011101. So, while decoding the frame, you would know that if you just encountered  011101, its EOF that is actually a part of data. Hence, you just decode it to 01111 and you're done.

Space cost :- No. of times SOF/EOF appears as data * 1 bit.

Time cost:- Every time you need to match characters to check if they're SOF/EOF. So, it's O(n) for string matching in the worst case where n is the total no. of bits transmitted.