Serial protocol delimiting/synchronization techniques

Question

As asynchronous serial communication is widely spread among electronic devices even nowadays, I believe many of us have encountered such a question from time to time. Consider an electronic device D and a computer PC connected with serial line (RS-232 or similar) and required to exchange information continuously. I.e. PC is sending a command frame each X ms, and D is replying with status report/telemetry frame each Y ms (The report can be sent as response to requests or independently - doesn't really matter here). The communication frames can contain any arbitrary binary data. Assuming the communication frames are fixed-length packets.

The problem:

As the protocol is continuous, the receiving side might loose the synchronization or just "join" in the middle of an ongoing sent frame, so it just won't know where the start of frame (SOF) is. A the data has different meaning based on its position relatively to the SOF, the received data will become corrupted, potentially forever.

The required solution

Reliable delimiting/synchronization scheme to detect the SOF with short recovery time (i.e. it shouldn't take more than, say 1 frame to resynchronize).

The existing techniques I am aware (and using some) of:

1) Header / checksum - SOF as predefined byte value. Checksum in the end of frame.

• Pros: Simple.
• Cons: Not reliable. Unknown recovery time.

2) Byte stuffing:

• Pros: Reliable, fast recovery, can be used with any hardware
• Cons: Not that suitable for fixed-size frame-based communication

3) 9th bit marking - prepend each byte with additional bit, while SOF marked with 1 and the data bytes are marked with 0:

• Pros: Reliable, fast recovery
• Cons: Requires hardware support. Not directly supported by most of PC hardware and software.

4) 8th bit marking - kind of emulation of the above, while using the 8th bit instead of 9th, which is leaving only 7bits for each data word.

• Pros: Reliable, fast recovery, can be used with any hardware.
• Cons: Requires an encoding/decoding scheme from/to the conventional 8-bit representation to/from 7-bit representation. Somewhat wasteful.

5) Timeout based - assume the SOF as the first byte coming after some defined idle time.

• Pros: No data overhead, simple.
• Cons: Not that reliable. Won't work well with poor timing systems like, say, Windows PC. Potential throughput overhead.

Question: What are the other possible techniques/solutions exist to address the problem? Can you point to the cons in the above list which can be easily worked around, thus removing them? How do you (or would you) design your systems protocol?

Answer 1

How do you (or would you) design your systems protocol?

In my experience, everyone spends a lot more time debugging communication systems than they ever expected. And so I strongly suggest that whenever you need to make a choice for a communication protocol, you pick whichever option that makes the system easier to debug if at all possible.

I encourage you to play with designing a few custom protocols -- it's fun and very educational. However, I also encourage you to look at the pre-existing protocols. If I needed to communicate data from one place to another, I would try very hard to use some pre-existing protocol that someone else has already spent a lot of time debugging.

Writing your own communication protocol from scratch is highly likely to slam against many of the same common problems that everyone has when they write a new protocol.

There's a dozen embedded system protocols listed at Good RS232-based Protocols for Embedded to Computer Communication -- which one is the closest to your requirements?

Even if some circumstance made it impossible to use any pre-existing protocol exactly, I am more likely to get something working more quickly by starting with some protocol that almost fits the requirements, and then tweaking it.

bad news

As I have said before:

Unfortunately, it is impossible for any communication protocol to have all these nice-to-have features:

• transparency: data communication is transparent and "8 bit clean" -- (a) any possible data file can be transmitted, (b) byte sequences in the file always handled as data, and never mis-interpreted as something else, and (c) the destination receives the entire data file without error, without any additions or deletions.
• simple copy: forming packets is easiest if we simply blindly copy data from the source to the data field of the packet without change.
• unique start: the start-of-packet symbol is easy to recognize, because it is a known constant byte that never occurs anywhere else in the headers, header CRC, data payload, or data CRC.
• 8-bit: only uses 8-bit bytes.

I would be surprised and delighted if there were any way for a communication protocol to have all of these features.

good news

What are the other possible techniques/solutions exist to address the problem?

Often it makes debugging much, much easier if a human at a text terminal can replace any of the communicating devices. This requires the protocol to be designed to be relatively time-independent (doesn't time-out during the relatively long pauses between keystrokes typed by a human). Also, such protocols are limited to the sorts of bytes that are easy for a human to type and then to read on the screen.

Some protocols allow messages to be sent in either "text" or "binary" mode (and require all possible binary messages to have some "equivalent" text message that means the same thing). This can help make debugging much easier.

Some people seem to think that limiting a protocol to only use the printable characters is "wasteful", but the savings in debugging time often makes it worthwhile.

As you already mentioned, if you allow the data field to contain any arbitrary byte, including the start-of-header and end-of-header bytes, when a receiver is first turned on, it is likely that the receiver mis-synchronizes on what looks like a start-of-header (SOH) byte in the data field in the middle of one packet. Usually the receiver will get a mismatched checksum at the end of that pseudo-packet (which is typically halfway through a second real packet). It is very tempting to simply discard the entire pseudo-message (including the first half of that second packet) before looking for the next SOH -- with the consequence the receiver could stay out of sync for many messages.

As alex.forencich pointed out, a much better approach is for the receiver to discard bytes at the beginning of the buffer up to the next SOH. This allows the receiver (after possibly working through several SOH bytes in that data packet) to immediately synchronize on the second packet.

Can you point to the cons in the above list which can be easily worked around, thus removing them?

As Nicholas Clark pointed out, consistent-overhead byte stuffing (COBS) has a fixed overhead that works well with fixed-size frames.

One technique that is often overlooked is a dedicated end-of-frame marker byte. When the receiver turned on in the middle of a transmission, a dedicated end-of-frame marker byte helps the receiver synchronize faster.

When a receiver is turned on in the middle of a packet, and the data field of a packet happens to contain bytes that appear to be a start-of-packet (the beginning of a pseudo-packet), the transmitter can insert a series of end-of-frame marker bytes after that packet so such pseudo-start-of-packet bytes in the data field don't interfere with immediately synchronizing on and correctly decoding the next packet -- even when you are extremely unlucky and the checksum of that pseudo-packet appears correct.

Good luck.

Answer 2

Byte-stuffing schemes have worked great for me over the years. They're nice because they're easy to implement in software or in hardware, you can use a standard USB-to-UART cable to send packets of data, and you're guaranteed to get good-quality framing without having to worry about timeouts, hot-swapping, or anything else like that.

I would advocate for a byte-stuffing method combined with a length byte (packet length modulo 256) and a packet-level CRC, and then use UART with a parity bit. The length byte ensures dropped-byte detection, which works well with the parity bit (because most UARTs will drop any bytes that fail parity). Then the packet-level CRC gives you extra security.

As for the overhead of byte-stuffing, have you looked at the COBS protocol? It's a genius way to do byte-stuffing with a fixed overhead of 1 byte per every 254 transmitted (plus your framing, CRC, LEN, etc).

https://en.wikipedia.org/wiki/Consistent_Overhead_Byte_Stuffing

Answer 3

Your option #1, SOH plus checksum, IS reliable, and it recovers on the next uncorrupted frame.

I'm assuming you either already know the length of a message, or the length is encoded in the byte(s) immediately following SOH. The check byte(s) appear at the end of the message. You also need a receive-side buffer for the data that's at least as long as your longest message.

Every time you see an SOH byte at the head of the buffer, it's potentially the start of a message. You scan through the buffer to compute the check value for that message, and see whether it matches the check bytes in the buffer. If so, you're done; otherwise, you discard data from the buffer until you get to the next SOH byte.

Note that if a message actually HAS data errors, this algorithm will discard it — but you were probably going to do that anyway. If your check algorithm includes forward error correction, you can check each potential message alignment for correctable errors.

If the messages are fixed length, you can dispense with the SOH byte altogether — just test EVERY possible start position for a valid check value.

You can also dispense with the check algorithm and keep the SOH byte only, but this makes the algorithm less deterministic. The idea is that for valid message alignments, the SOH will always appear at the start of a message. If you have an incorrect alignment, the next byte in the data stream is unlikely to be another SOH (depends on how often SOH appears in the message data). You can pick out the valid SOH bytes on this basis alone. (This is basically how the framing on synchronous telecom services like T1 and E1 works.)

Answer 4

One option not mentioned but is widely used (especially on the internet) is ASCII/text encoding (actually, most modern implementations assume UTF-8). In my experience, hardware guys hate to do this but software people tend to prefer this over almost anything else (it mostly comes for the Unix tradition of making all things text based).

The advantage of text encoding is that you can use non-printable characters for framing. For example, the simplest would be to use something like 0x00 to indicate start of frame and 0xff for end of frame.

I've seen two main ways data are encoded as text:

1. When a hardware/assembly guy is asked to do this then it will most probably be implemented as hex encoding. This is simply converting the bytes to their hex values in ASCII. The overhead is large. Basically you'll transmit two bytes for every actual data byte.

2. When a software guy is asked to do this then it will probably be implemented as base64 encoding. This is the de-facto encoding of the internet. Used for everything from email MIME attachments to URL data encoding. The overhead is exactly 33%. Much better than simple hex encoding.

Alternatively, you can completely abandon binary data and transmit text. In this case the most common technique is to delimit data with newline (either just "\n" or "\r\n"). NMEA (GPS), Modem AT commands and Adventech ADAM sensors are some of the most common examples of this.

All these text-based protocols/framing have the following pros and cons:

Pro:

• Easy to debug
• Easy to implement in a scripting language
• Hardware can simply be tested using Hyperterminal/minicom
• Easy to implement on the hardware (unless it's a really small micro like a PIC)
• Can be either fixed size frame or varying size.
• Predictable framing and fast sync recovery time (recovers at end of current frame)

Con:

• Very large overhead compared to pure binary transmission (then again, text I/O can also "compress" numbers like sending one byte "0" (0x30) instead of four bytes 0x00000000)
• Not so clean to implement on very small micros like the PIC (unless your library includes an sprintf() function)

Personally to me the pros heavily outweigh the cons. The ease of debugging alone counts as 5 points (so that single point alone already outweighs both cons).

---

Then there are not-so-carefully-thought-out solutions often coming from software guys: send encoded data without thinking about framing.

I've had to interface with hardware that sent raw XML in the past. The XML was all the framing there was. Fortunately, it's fairly easy to figure out frame boundaries by the <xml></xml> tags. The big con for me is that it uses more than one byte for framing. Also, the framing itself may not be fixed since the tag may contain attributes: <tag foo="bar"></tag> so you'd have to buffer for the worst case to find the start of frame.

Recently I've seen people start sending JSON out of serial ports. With JSON framing is at best a guess. You only have the "{" (or "[") character to detect frame but they're also contained in the data. So you end up needing a recursive descent parser (or at least a brace counter) to figure out the frame. At least it's trivial to know if the current frame ends prematurely: "}{" or "][" are illegal in JSON and thus indicate that the old frame has ended and a new frame has started.

Answer 5

What you describe as "Xth bit marking" can be generalized into other codes that have the property of expanding the data by a constant fraction, leaving some codewords free to be used as delimiters. Often these codes provide other benefits too; CDs use eight to fourteen modulation, which guarantees a maximum run length of 0 bits between each 1. Other examples include Forward Error Correction block codes, which use additional bits to encode error detection and correction information, too.

Another system you haven't mentioned is to use out of band information, such as a chip select line, to delimit transactions or packets.

Answer 6

Another option is what is known as line coding. Line coding gives the signal certain electrical characteristics that make it easier to transmit (DC balanced and maximum run length guarantees) and they support control characters for framing and clock synchronization. Line codes are used in all modern high speed serial protocols - 10M, 100M, 1G, and 10G Ethernet, serial ATA, FireWire, USB 3, PCIe, etc. Common line codes are 8b/10b, 64b/66b and 128b/130b. There are also simpler line codes that do not provide framing information, only DC balance and clock sync. Examples of these are Machester and NRZ. You probably want to use 8b/10b if you want to sync quickly; the other line codes are not designed to sync in a hurry. Using a line code like one offering the above will require use of custom hardware to transmit and receive.

As for your option 5, standard RS232 serial is supposed to support sending and receiving breaks where the line is idle for a couple of byte times. However, this may not be supported on all systems.

Generally the simplest and most reliable framing method is your option 1, in combination with a length field and simple CRC or checksum routine. The decoding routine is simple: discard bytes until you get a start byte, read the length field, wait for the whole frame, check the checksum, keep if good. If the checksum is bad, start discarding bytes from the buffer until you get a start byte and repeat. The main issue with this technique is finding a start of frame byte that actually isn't a start of frame byte. To alleviate this issue, one technique is to escape bytes with the same value as the start of frame byte with another control character, and then changing the escaped byte so it has a different value. In this case, you will also have to do the same thing with the new control byte. The downside of this method is that your packet length can now vary based on the content, but the start of frame byte should now be completely unambiguous.