We are running a survey to help us improve the experience for all of our members. If you see the survey appear, please take the time to tell us about your experience if you can.
(Sorry for my limited English ability and limited technical ability.)
I have been requested to design an I/O-Control (Communication) Protocol. This simple protocol is designed for a LPC23xx based USBCDC, the USBCDC software solution is based on the open source project LPCUSB. The USB Host side is a Linux X86 platform. So that, the Linux X86 platform can control the I/O Port of my LPC23xx board via USBCDC connection.
Due to my limited technical ability, I am afraid that, I may make some obvious mistakes, or be unable to consider some complicated scenarios. So, please kindly give me some advices.
This simple protocol:
======================== 0xDEF0 -> 2Bytes (Head, 0xDE first) >=======Content=======< Length -> 2Bytes (Little-Endian) C-Type -> 3Bytes C-Data -> 13Bytes (Variable Length) CRC-32 -> 4Bytes (Little-Endian) >=======Content=======< 0xDE0F -> 2Bytes (Tail, 0xDE first) ======================== Length = C-Type size + C-Data size CRC-32 is for { Length, C-Type, C-Data } Stuffing Rule -> Tx-Side replaces all 0xDE of the Content with 0xDEAA Rx-Side replaces all 0xDEAA of the Content with 0xDE So that, the Length and CRC32 fields are also stuffed.
This is my first time doing the Bit Stuffing, are there any obvious defects or potential problems on my design?
And, if my design is acceptable, then I have a question, will the Stuffing break the CRC32 Error Detection? Because, the transmitted data is stuffed, not the same as the original one.
Hi Per,
Many Thanks.
Due to my limited ability, I didn't read those two articles talking about the Stuffing affects CRC Error Detection. I just searched/found the sentences, which I think I need. Now, with your comments, I have more confidence with my original guess, at least, I know my original guess is reasonable.
jcho.de/.../cia-94.pdf 3.4 Error Transformation "Due to the bit stuffing effects, the error detection capabilities of the CRC are reduced from safely detecting h - 1 = 5 bit errors to 2 errors."
This conclusion is typical lie using figures, which cannot be compared with each other.
"h - 1 = 5 bit errors" derives from hamming distance of CRC. As the background, random error is supposed.
On the other hand, "2 errors" stands for ONE stuff bit deleting error AND ONE stuff bit creating error. These deleting/creating errors should be in a pair, because CAN (and USB also) checks byte boundary. The probability of these deleting/creating error bits aren't random one.
As the background probability structure is different, these two figures can't be compared directly.
Tsuneo
hamming distance of CRC. As the background, random error is supposed.
No. Background has nothing to do with it. Hamming distance is about any kind of error, regardless of whether it's random or not. A CRC16 guarantees that you have to flip at least 5 bits before you can get a false-positive check result.
The effect of bit stuffing reduces this to two. I.e. you can now get a false-positive check by flipping only 2 bits.
"The effect of bit stuffing reduces this to two. I.e. you can now get a false-positive check by flipping only 2 bits."
That still greatly depends on if you compute crc on the stuffed or unstuffed data.
And the next thing is that different CRC polynomials have different behaviour. On one hand, they can handle a limited number of random bit errors. But you can get a different performance for a burst error compared to randomly spaced bit errors.
And having an inner CRC (message data) and an outer CRC (carrier protocol) does greatly affect the probability of an error not being detected. Multiple detection methods quickly increases the probability of detecting an error - you don't have just a crc16 anymore.
Thanks to all.
I am trying to understand all these comments with my very limited ability. I write down my understanding here so that, it can be verified by Experts.
I think/guess:
Tsuneo is talking about the probability distribution, one is random bit errors, another is a paired bit error. This talking is mainly for Figures Comparing.
Hans-Bernhard is talking about CRC Error Detection. This talking is mainly for how Stuffing affects Error Detection.
And Per is talking about different CRC polynomials have different behaviors.
Tsuneo is talking about the probability distribution, one is random bit errors, another is a paired bit error.
Actually he's trying to argue against the results of that paper at jcho.de, which concern how bit stuffing reduces error-checking capability of a CRC. And his argument is, IMHO, wrong.
OTOH, what you're doing there is not actually bit stuffing. It's a plain old escape character mechanism. Bit stuffing happens on the layer where individual bits actually get sent over the data line of a (synchronous) serial protocol. It's used to avoid extended periods without any signal changes on the line.
The use of escape sequences in data messages is normally called _byte_ stuffing as compared to the _bit stuffing in RLL-encoded data where the data may only have a limited number of 1 or 0 in a sequence to maintain self-clocking and where messages normally starts with magic bit patterns (such as a long sequence of ones) that may not happen within the data.
One thing with RLL data is that if you have a scheme where you may not have more than 5 consecutive zeroes or ones, a single bit toggle may extend one such sequence - possibly even merging two sequences making 5+1+5 into 11 consecutive bits. You normally avoids code sequences where a single bit error can result so grave errors by defining patterns with a specific "resilience" by making sure that there is a suitable hamming distance between the allowed patterns.
But it doesn't matter how good CRC is to detect an error in a message, if you get more bit errors in such a pattern than it can support. On one hand, one pattern may suddenly look like a different pattern. This can be detected by CRC. But the bit errors can break the self-clocking properties of the data stream in which case you will have to wait for the next block start. Without synchronization, you may not even be able to locate the bits that after unstuffing should form the CRC.
So you may have a data encoding scheme where the CRC can detect 5 bit errors but it can be enough with 2 bit errors to lose the synchronization. The damaged data is no longer self-clocking.
where the CRC can detect 5 bit errors but it can be enough with 2 bit errors to lose the synchronization.
It's a little worse than that. A full-on violation of the bit-stuffing rules would be detectable by the receiver, at which point it knows that the data are compromised without even looking at the CRC.
The real problem is that you can have pairs of bit-flips that transfrom one correctly bit-stuffed frame into another correctly bit-stuffed frame. Basically, in a 4->5 bit stuffing scheme:
000010101010101110001 -unstuff-> 0000.0101.0101.0111.0001 2 bits flipped: 010010101010101111001 -unstuff-> 0100.1010.1010.1011.1101
So two flipped bits in the stuffed stream can turn into a basically unlimited number of flipped bits in the un-stuffed stream. And that breaks CRC's Hamming distance property, because the un-stuffed stream now has not 2, but about 10 flipped bits.
Yes, of course.
Having RLL-encoded data you are only safe when your bit errors are covered by the hamming distance of the patterns used in the stuffing. As soon as a pattern gets more damaged, you lose synchronization. Which may either result in incorrect decoding of following patterns or in the receiver seeing an invalid pattern forcing it to break reception until it sees a synchronization.
But you normally avoids stuffing schemes where you after four-in-a-row force an extra reversed bit. It is way too fragile even if it is compact, since there is no hamming distance. And it can be problematic with encodings where fixed-length data can encode into random-length output.
You normally compute a full set of output patterns with best possible hamming distance. You may for example split the input data into 5-bit blocks and replace with 8-bit blocks. Depending on the size of the input and output code blocks, you can have output code blocks with different hamming distance, allowing one or more bits in each block be inverted while still being able to correctly decode the data. And if a scheme with fixed size of input and output blocks is used, bit errors may not change the length of the stream. This also allows two-dimensional parity information to be used to greatly improve the error-correcting abilities.
But at the very minimum, somethink like the 4B/5B encoding should be used, where each 4-bit group is converted to a 5-bit group with good self-clocking properties and making sure you have a fixed length making sure that bit errors will not produce a a random sequence of decoded bit errors. And the 4B/5B encoding have patterns available for inlining commands in the data stream.
You normally compute a full set of output patterns with best possible hamming distance.
Good plan, but slightly besides the point, since that's no longer bit stuffing. That's a different technique which has variuos different names: Hamming Code or Group Code Recording, among others.