Useful, efficient software matches the user's needs, knowledge and skill. Don't buy a swiss army knife when you need a wrench...

About Us

A young company still hungry for challenges, with 30+ years of experience with software development from small embedded systems to distributed real time PC networks and SQL databases. A reasonable design effort to deliver high-quality software e.g. for medical devices on schedule.

External Links

Customers

LabWare

Other sites

Arbitration
Often there is more than one sender over the channel. Arbitration is some means to avoid (or at least detect when) two nodes send simultaneously clobbering the message.
In general ensuring one sender has to be resolved in hardware, e.g. by the communication topology.
If media has one sending channel per master and slaves just respond to master requests there will be no collission. Simplest example is the RS232C protocol which is point to point and separate sending channels for endpoints. LIN bus is a single master bus and thus avoids arbitration. Modern Ethernet over Twisted pair networks also works where each node is connected point-to-point with a switch also this way though earlier Ethernet coaxial cable networks shared a common media.
Ring-formed networks where each node receives on one channel from previous node and sends on another channel to the next node can also avoid collissions provided there are adequate buffers for incoming messages during transmit of own messages.
With a shared media collissions can be avoided using a token allowing each node in a round-robin fashion to be the sender. This is but the only way software can implement arbitration.
Some networks implement a dominant level ensuring the node with the most "dominant" address win the arbitration. Typical examples are CAN and I2C buses. This works only for relatively slow networks and short distances since a bit time (at least during arbitration) must be long enough for all nodes on the network to detect the dominant state and recessive nodes to stop transmitting.
Faster networks may settle with collission detection, e.g. CSMA/CD used with coaxial cable Ethernet, where nodes send until they determine a transmission error has occurred, accept the message as clobbered and tries again later.
Error detection
Assuming we have transmission errors (and of course that we are interested in detecting or even correcting the errors). In general Cyclic Redundancy Check (CRC) codes are far superior to simple checksums like summing bytes modulo 2 or similar.
A good error detection code will reduce the risk of an undetected error by a factor equivalent to the number of different codes possible. Thus a 1 byte code will optimally detect 255 errors out of 256. Thus if we estimate an error will occur once every year on average chances are good the system will transmit an erroneous message once every 100 years or so. If an error is estimated every day we should probably use a 16-bit CRC and if it occurs every second a 32 bit CRC is probably the way to go. If you want to transfer a 2 TB hard disk (2^41 bits) with a risk about one in a million (approx 2^20) of an undetected error, a 64-bit CRC would be adequate. Assuming a good CRC algorithm is used of course.
In general CRC should be computed over the variable bytes only thus not including framing. And for escaped byte codes the CRC should be calculated for the resulting byte, not the transmitted symbols. CRC value may itself need to be escaped.
Here is a good article on CRCs for embedded netorks.
CRCs can be calculated efficiently using a table. Normally a 256-entry table is used to process a byte at a time, but to save code memory a 15-entry table can be used processing a nibble (4 bits) at a time.
Our block with crc now looks like this:

data

crc

framing

Possibly with a START before data.
A pretty good place to look for crc algorithms is pycrc. It is script that generates code for many crc variants.

< Previous

Error correction
The most common way to deal with transmission errors is that the receiver asks the sender to re-send the message. Under normal circumstances error rate i slow and the message will be correctly received on the second attempt. In any case there will be some limit on the number of retries (and timeout waiting for a message re-send).

For the sender to know when the message is received and thus no re-send will be necessary the receiver needs to acknowledge the message so the sender can let go of the message and proceed to the next message. Basically there are two outcomes - ACK meaning i twent OK and receiver is ready for next message, or NAK meaning something went wrong. In the event of a NAK the sender needs handle the situation either by re-sending the message or to just report the incident.

To structure the protocol stack we should take care of error correction in a dedicated layer, thus we must be able to distinguish data packets from ACK/NAK packets, e.g. like this:

Sent:

TYPE_DATA

data

crc

framing

Receved:

TYPE_ACK

ack data

crc

framing

One obvious way is to use the START as start of a data package and another dedicated code for ACK packages.

An extension is to have a third type of packet that does not use error correction (no ACK is expected in return). Maybe even a type of package that doesn't transmit crc, e.g. if receiver can still use the message despite errors, like an audio channel.

All this costs some codes though increasing the number of codes that can not be transmitted in its raw form.

The crc could as well be transmitted at start of message. It is natural to have it in the end since this is where we compare computed crc with sender's supplied crc.

If we only have a unidirectional channel the receiver must be able to correct errors in the message without being able to ask for re-send. This can also be the case if turn-around time is unacceptably long, e.g. when streaming real time data like audio or video. An extreme is sending a command to a Mars vehicle - with two hours transmit speed in each direction you wouldn't want a resend request 4 hours later but rather send every command 10 times or so to be reasonably confident at least one of them got through.

Error correcting codes are complex but pretty standard, implemented on every hard disk to reduce irreparable surface errors. But usually in an embedded system it is cheaper to manage with resend requests.

An easy (though not optimal) forward error correcting scheme is to send an (up to) 8 byte block, then two more bytes with horizontal and vertical parity bits.

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

Grey digits are (even) parity. If the parity is wrong in one row and one column we can pinpoint which bit is in error. If only one bit is wrong we assume it is the parity bit, but it could of course be a multi-bit error. With 9 bit transfers this scheme is trivial and you get an extra bit (unfilled corner above) indicating error in parity.

Next >

E-mail: info@usefulsoftware.se, Phone: +46 708 727662

Useful Software Sweden AB