Algorithms – Is There a Specific Algorithm to Decode Protocols?

algorithmsprotocol

I am designing a simple logic analyzer, I know that the best way to decode a protocol like I2C, SPI, UART is whit something like an FPGA but I want to do it by software by now 🙂 I am running on an OMAP4460 ARM proccesor.

I would like to know if there is an special way of decoding protocols like I2C, SPI, UART or it is simply if() and flags as the normal way.

Best Answer

A lot of people are doing what you are doing and making their own logic analyzer. Some logic analyzers and scopes are able to do the decoding you are describing, including some that have open source software and hardware.

My suggestion is that you join with others to do some or most of what you are trying to do, or that you scope your effort as narrowly as possible to get something simple running, then build it up from there.

Reusing / Collaborating on existing projects:

If you are using Arduino, you can buy hardware for it and download software including the I2C, SPI, and UART support very reasonably.

http://www.arduinolab.us/

Another similar project is described here:

http://www.seeedstudio.com/depot/open-workbench-logic-sniffer-p-612.html?cPath=61_68

Other people are working on this kind of stuff at sump.org. Sump seems to provide a hardware and two part software solution - one part on a PC used to display, the other on a target to capture. The RS232 protocol between seems to be used by others, so potentially if you like what they did, you can skip the PC side and just implement the target side protocols.

Going it Alone, Starting Simple

I suggest that to make your implementation as easy as possible, you have the user configure as many options as possible instead of trying to figure them out. Depending on protocol, some items the user might select include:

  • Interface speed (baud rate or expected clock rate).
  • Parity (none, mark, space, odd, even).
  • Master/slave address(es).
  • What input does what function (UART: RX, TX, maybe DSR, DTR, CTS, I2C: CLK, DATA, SPI: MISo, MOSI, CLK, SPID/SSEL0..N.
  • Polarity if inputs for any of the pins might be inverted from normal.
  • Address size.

Use the links from the earlier section, to see what Arduino and Sump guys are doing to get some ideas by looking at their sample code and documentation.

I suspect the UART will be the simplest to implement. Both transmit and receive have identical structure, so you can make one state machine that implements both, and takes the an analyzer channel as its parameter. You will need to sample this no less than twice the baud rate (8x or 16x might be better). Typically, when idle, the line will be pulled up by a resistor, then the beginning of a byte (8 bits) will be signaled by a start bit (logic 0), followed by eight data bits, followed by an optional parity bit, and a mandatory stop bit (logic 1). Timing diagrams for this bit pattern, with parity and without parity respectively, can be found at the following links:

http://www.romux.com/tutorials/embedded-system/peripherals

http://www.commfront.com/RS232_Protocol_Analyzer_Monitor/RS232_Analyzer_Monitor_Tester_TUTORIAL.HTM

The first reference also discusses DTC and DCE conventions and some other things you may want to monitor for UART serial if you wire it up beyond TX, RX, and GND.

You can use a timer to poll the input levels, and a state machine with states like UART_IDLE, UART_START_DETECTED, UART_D0, ..., UART_D7, UART_PARITY, UART_STOP, and UART_RECOVER could be used. UART_RECOVER might be a state that follows the detection of an exception where parity is not what it should be based on calculated parity, an expected stop bit that shows logic 0, or a start bit (or other bit) that changes within your over sampling, perhaps because of noise that is logic low like a start bit, but lasts much less than a bit time. It may be beneficial to use more than one recovery state to count out a certain amount of time, or look for a stop/idle/start sequence.

I2C and SPI are synchronous serial protocols, so if you indicate which input is clock, you can sample or if desired over sample to determine whether data bits are zero or one when the clock transitions. You will potentially be able to show addresses, data words, and either direction (I2C master or slave, read or write) or selected device (SPI).

Github and other open source repositories may have a lot of the code you need already written, and the wikipedia references include some bit-banging code that could be adapted (or at least studied) with high benefit.

http://en.wikipedia.org/wiki/I%C2%B2C

http://en.wikipedia.org/wiki/Serial_Peripheral_Interface_Bus

If you write these from scratch, start with a bunch of test cases for things like master read, master write, slave read, slave write, ideally taken from the spec or a known good implementation. Being able to loop back your hardware or even to unit test your state machine with simulated inputs from a table, will accelerate your debug and let you retest quickly as you revise the code.

You will need more state machines. I2C and SPI will be separate of course. You may have nested state machines because there is a bit oriented recognition and a frame oriented recognition. You may chose to divide things up so major use cases get their own decode functions in the code.

I2C and SPI may need to be more flexible about timing. They will step through some state transitions based on changes on the clock and others based on changes in the data, but you will probably still use a timer to drive your sampling and your state machines. Exception handling will be more complex, and use of nested state machines can help. Grady Booch (et al) have great examples of state machines and nested state machines in section 5.11 of his book "Object Oriented Design and Analysis with Applications", 3rd Edition (c) 2007.

Related Topic