5
\$\begingroup\$

It seems to happen fairly often that I'm working on a system that incorporates a serial (SPI or async) command set.

As such, I generally have to put together a set of arbitrary command byte values that represent possible commands.

As such, I seem to find myself trying to maximize the distinction between possible commands. For example, If I have a grand total of 4 commands, I would choose something like:

 0x81, 0b10000001
 0x42, 0b01000010
 0x24, 0b00100100
 0X18, 0b00011000

or better yet (as it allows further expansion)

0xA5, 0b10100101
0x5A, 0b01011010
0X99, 0b10011001
0x66, 0b01100110
0x96, 0b10010110
0x69, 0b01101001

Both have the advantage of being both very distinct, so noise has little chance of corrupting one to look like another, and also being possible to (manually) determine the command using only a single logic-analyser or oscilloscope channel.

So, given the assumption that you are designing an arbitrary protocol, and the assumption that noise isn't a significant consideration, What is good advice and/or comments about the best way to choose binary constants for the command definition of a serial interface?

Actually, this seems pretty broadly applicable to any situation where you are using binary commands between two (or more!) systems.

\$\endgroup\$
  • 1
    \$\begingroup\$ It really isn't clear what your goal is here. Are you really expecting a high bit error rate on your communications link, or just the occasional glitch? Is it really only the command byte that needs to be protected, or the entire packet/message? Normally, it's the latter answer for both, and a checksum/retry mechanism is the usual approach. \$\endgroup\$ – Dave Tweed Oct 7 '12 at 10:48
  • 1
    \$\begingroup\$ @DaveTweed - I wouldn't disagree that it's kind of a vague question, I'm kind of vague on what I should consider when choosing command words. I think it's pretty safe to assume a low error rate. The question is really: Assuming a sufficient checksum system to catch any bit-error, what other considerations are useful when picking values for a protocol? \$\endgroup\$ – Connor Wolf Oct 7 '12 at 12:51
  • \$\begingroup\$ Basically, I have a system where I have some on-board serial comms. It's all pretty well packaged, and noise isn't a big consideration. As such, I am in the position of needing to put together a very minimal protocol, and am wondering what other people take into consideration in a similar situation, and/or if just choosing constants off the top of my head is a really bad idea for some reason I am missing at the moment. \$\endgroup\$ – Connor Wolf Oct 7 '12 at 13:12
  • \$\begingroup\$ @FakeName, by editting in a new assumption "that noise isn't a significant consideration", you've made three answers, that were very good answers to the original question, irrelevant. Maybe it would be a better to keep this question as it was, and open a new question with the new assumptions? \$\endgroup\$ – The Photon Oct 7 '12 at 16:43
  • \$\begingroup\$ @ThePhoton - Well, two of the answers were written after the edit, so I'm not so sure. \$\endgroup\$ – Connor Wolf Oct 7 '12 at 23:11
5
\$\begingroup\$

The word is Hamming Distance, which is the number of symbols different between any two codes. If you would use any possible combination of an 8-bit code your Hamming Distance is 1: a change of just 1 bit will give you new valid code. That means that even 1-bit errors can't be detected, less corrected.

Now take the Hamming cube:

enter image description here

Here there are only 2 valid 3-bit codes: 000 and 111. The Hamming Distance is 3, which means that less than 3 bit-errors can be detected. Single-bit errors can even be corrected: if the code should be 000 and you have 001, that's a single bit. If you measure the distance in the cube to the two valid codes you'll have to follow 2 edges to arrive at 111, but only 1 edge for 000. So it's either a single-bit error, and then you can correct it, or a multiple-bit error, like, which you can detect (because it's not a valid code) but not correct (you don't know if it should be 000 or 111).

A long time ago a watched a BBC Open University program on coding where they explained how a Hadamard Matrix provides a list of codes with a Hamming Distance of n for a 2\$^n\$ \$\times \$ 2\$^n\$ matrix. The construction of a Hadamard matrix is interesting in itself, and a nice programming exercise. Start with a single bit:

1

now you make a matrix of 2 by 2 bit, following this rule: copy the 1 in all quadrants, except bottom right, where you place the inverse:

1 1
1 0

Next level (this is a recursive algorithm) you apply the same rule to the 2 by 2 matrix, so that you get a 4 by 4 matrix. In each quadrant you copy the previous matrix, except the bottom right where you invert it:

1 1   1 1
1 0   1 0

1 1   0 0
1 0   0 1 

And so on. At the next level we'll have 8 codes (lines) with a Hamming Distance of 3:

1 1 1 1   1 1 1 1
1 0 1 0   1 0 1 0
1 1 0 0   1 1 0 0
1 0 0 1   1 0 0 1

1 1 1 1   0 0 0 0
1 0 1 0   0 1 0 1
1 1 0 0   0 0 1 1
1 0 0 1   0 1 1 0

You can extend the Hadamard Matrix as far as you want. If you want to detect up to 6 bit errors you'll have a 64 by 64 matrix. This kind of forward error coding is used for instance in space communication, where the distance of the spacecraft may be so large that the signal becomes extremely noisy. The fact that there is only a limited number of valid codes, despite a long code length, allows detection of a signal below the noise floor.

|improve this answer|||||
\$\endgroup\$
4
\$\begingroup\$

You first have to decide what you are trying to protect against, and what you want the system to do in case of transmission error. You also need to consider the chance of data corruption, and what the costs are if bad data is interpreted as valid data.

For on-board communication, you generally ignore the whole issue. You are already likely making lots of assumptions that the output of one digital chip will correctly appear at the input of others on the same board. Serial communication between two devices on the same board is no different. The type of disturbance that would cause a error in on-board direct wired signalling would likely cause other problems too or would be so way out of spec that it is unreasonable to protect against. For example, someone shuffling accross a carpet and then zapping any exposed conductor on the open board with 10 kV of static electricity will cause all kinds of failure, but that is also a abuse that is way out of spec.

If you think the serial communication will have some small but significant enough bit error rate that you can't just ignore it, then the usual scheme is to send data in packets with checksums. The receiver ignores any packet with invalid checksum. A properly designed checksum will use less bits and therefore be less overhead than a clumsy approach like limiting the opcode space so that no two opcodes are 1 bit apart from each other. Think about it, and you will see that is basically sending a smaller opcode with the extra bits being a low performing checksum. It can only detect single bit errors in the opcode, can't correct it, and doesn't help the rest of the message. If the bit error rate is low, the chance of a single bit error in a whole packet is low, so covering the whole packet with a checksum uses less bits per checked data bit and covers all bits sent.

If it is good enough to simply discard bad commands, then you can stop there. If you need to know that a command was correctly received, then you have to to use some kind of two way communication scheme. The simplest form is the receiver sends a ACK (properly wrapped in a checksummed packet of course), and the transmitter doesn't send anything new until the ACK is received. If the ACK is not received after a timeout, then the transmitter sends the last packet again. More complicated protocols allow the transmitter to get ahead of the receiver, so there is usually a sequence number or the like encoded in each packet. There are lots of ways, and some of them get pretty fancy. TCP, for example, does this with a arbitrary byte stream. There are no packet boundaries since it is assumed network packets can be broken up or combined between the transmitter and receiver.

 

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

I would try some form of forward error correction on each command. If we know how many distinct commands we need, then we can pick an existing code (Hamming, Reed-Solomon, etc.) and use the most redundant form that still fits in one byte. An advantage is that there are established algorithms to help you decode corrupted bytes.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I tend to go with LRCs, since they're stupidly easy to implement. This isn't a lot of data (maybe 5-10 bytes), and resending the packet isn't too big a deal. FEC is way, way overkill in this application. \$\endgroup\$ – Connor Wolf Oct 7 '12 at 6:49
  • \$\begingroup\$ Sure it's overkill, but FEC is still a convenient way to generate maximally-different codewords, since that's pretty much the whole idea behind FEC. \$\endgroup\$ – Theran Oct 7 '12 at 7:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.