This is a continuation of my last three blog posts.
Maxim has application note 27, "Understanding and Using Cyclic Redundancy Checks with Maxim 1-Wire and iButton Products", that I will refer to here. You can see this here.
If you transmit data from one place to another you want to know that the data arrived unchanged. The cyclic redundancy check is the best way to tell you if the transmission was successful.
We transmit serial data from two sources within the DS18B20: from its Read Only Memory which has the ROM code stored, and from the scratchpad memory. Basically, while transferring data to us, the user, the DS18B20 looks at the data it is sending, one bit at a time, and makes a calculation. The result of that calculation is an additional byte that is tacked on to the data stream. The value of this byte depends solely on the bits that have preceded it in the transmission. This additional byte is the CRC byte. The ROM code is actually 7 bytes long but the CRC byte makes it 8 bytes long. The scratchpad data is 8 bytes long and its CRS makes it 9 bytes long.
My code calculates the CRC as each bit of each byte is received. One of the nice things about CRC, and, this should be kept in mind, is if the transmission was successfully received, my calculation of the CRC will be 0. It's very easy to check for 0 in code. Any result besides 0 means the transmission failed.
How do you calculate CRC? It's hard to put that into words. The mechanism for calculating CRC is generally expressed as an electronic circuit. You can actually build this circuit and calculate the CRC, or you can emulate this circuit in software. I have done the latter in my One_wire_DS18B20 library file. I was surprised how few lines of code it took to write the CRC function. More on this later.
Getting Into Electronic Hardware
Here we go diving into interesting waters. But, I don't know how to otherwise discuss how this all works. So here we go. Maxim gives a representation of the electronic circuit in it's figure 2 of the application note. Here it is:
I have my own version of that figure that shows more detail, especially what is in those boxes called stages:
There are two different kinds of parts here, the boxes are called flip-flops (No connection to the ones you wear to the beach). Let's look at a flip-flop a little more closely:
Why the funny name, flip-flop? The name describes the functionality, perfectly. The output from the part can be made to flip from one state to another. That is, from a high voltage to a low voltage; or, stated another way, from a logic HIGH state to a logic LOW state; or, stated yet another way, from a "1" to a "0". Of course going back in the other direction is just as easy. Flip-flops make up a large part of the circuitry in your computer microprocessor. There are thousands of them. The simplest can be constructed with just two transistors. The flip-flip we are showing here is a bit more complex and is called a D flip-flop. Below the flip-flop, is a timing diagram that plots voltage (vertical) against time (horizontal). When the voltage is at it's high state we call this a logic "1". When the voltage is near 0 volts, we call this a "0". (That is arbitrary, we could call a high voltage a "0" and a low voltage a "1").
We see three signals, or waveforms: "Data", "Clock", and "Output" (we are going to ignore reset). "Data" is the information that is being transmitted serially, one bit at a time. "Clock" is another signal, and when it makes a transition from a "0" to a "1", the logic level the device sees on its "D" pin, will appear at its "Q" pin. We show that the data on the "D" pin is "latched" on the rising edge of "Clock" by those upward arrows on the "Clock" waveform. The first time we see "Clock" going from a low to a high, the "Data" happens to be high (or a "1"). After a really short delay, that "1" appears at the output of the flip-flop. That little delay is important. It is not obvious why here, but will be when we consider more than one flip-flop. If you look at each rising transition you will see the output will mirror what is at the "D" pin. So far, not so interesting. But. wait, let's connect a second flip-flop to the first one.
We connect a second D flip-flop so that its "D" ("D" for data, by the way) pin connects to "Q" of the first one. "Clock" connects to both flip-flops. Now we can see why that little delay is important. When we look at the second time the "Clock" goes from low to high, we see that the "D" pin of the first flip-flop is low, so the output of the first flip-flop wants to go low to follow the input. However, there is a slight delay so it stays high for a little while longer. If that delay was not there, the output of the first flip-flop would be changing at the exact time that "Clock" is latching the data at the input of the second flip-flop. What would the output of the second flip-flop be? A "1" or a "0"? Who knows! That little set-up delay assures that the input of the second flip-flop is a "1" long enough so the "Clock" latches a "1" at the output of the second flip-flop.
Is this circuit any more useful than the first? The usefulness of the circuit will be evident if we add more flip-flops. Let's have a total of 8:
Remember, "Data" is the information coming into the circuit one bit at a time. "Clock" captures that information in the first flit-flop. As new bits arrive, they cascade to the other flip-flops from left to right. Each rising edge of "Clock" shifts the information on "Data" from flip-flop to flip-flop. Thus, this circuit is called a shift register. The flip-flop outputs are labeled "Q7" - "Q0".
The circuit is also called a serial to parallel converter. After shifting in the serial data enough times to get the first bit cascaded down to the last flip-flop, the original eight bit data word is available on "Q7" - "Q0" in parallel format. We could connect "Q7" - "Q0" to other circuitry if we wished.
Why the grayed out areas? We don't have enough information to know if the logic levels in these areas are a "1" or a "0".
My project emulates the shift register in software. Every time we ask for data from the DS18B20, we call on a couple of functions in my 1_Wire library. We emulate "clock" with a "for" loop to shift in each bit of each byte. The "Q7" - "Q0" outputs are represented by an eight bit variable. We call that loop enough times to capture each byte in the message from the DS18B20.
As we shift in each bit, we do a calculation to determine the CRC value. We continue that calculation until the last bit of the last byte of the message has been shifted in from the DS18B20. For example, if we were capturing ROM code, we would capture eight bytes. The last byte of the ROM code is the CRC value (calculated by Maxim). After shifting in all 64 bits, the result of our calculation should be "00000000" (Recall my forth paragraph above).
Enough Background - Getting To The Cyclic Redundancy Check
Let's repeat that figure at the top of this post:
Notice that this is similar to the shift register above. We have added three parts called exclusive OR gates. They each have two inputs on the left and one output on the right. The exclusive OR is one of a series of logic circuits. Some of the others are inverters (also called NOT gates), AND gates, and OR gates. These devices look at the logic levels at their inputs ("1" or "0") and decide what the logic level of their output will be. The output of the inverter is opposite of the input. The output of the AND gate is "0" unless all the inputs are "1". The output of the OR gate is a "1" if any of it's inputs are "1". The output of the exclusive OR gate will be "0" if the logic level of the inputs are the same (both "0" or both "1"). If the inputs are different ("0", "1" or "1", "0") the output will be a "1".
That CRC circuit seems to be a bastardized version of the shift register. The output from the last stage is fed back into the circuit. This circuit is specific to the way Maxim handles the CRC for devices that transfer data in eight bit bytes. They have a different circuit for devices that transfer 16 bit bytes. That circuit has 16 "stages"
The type of CRC circuit is also know by its polynomial, a mathematical expression representing the number of stages, and where, and, how many exclusive ORs are in the circuit. The polynomial for our circuit is shown on the figure above from Maxim's application. It is X8 + X5 + X4 + 1. This means we take the output of the forth, fifth, and eighth stage as inputs to our exclusive OR gates. There are other schemes with different number of exclusive OR gates that feedback to different stages. These have different polynomials.
The mathematics of the cycle redundancy check is quite involved and I won't begin to discuss it here. There is plenty of in-depth information on the web. Let's move on to the final discussion of implementing the CRC in software.
Calculating the CRC in Software and in Our Equivalent Circuit
The following code is taken from my calculateCRC_byte function found in my One-Wire_DS18B20 library.
The Equivalent CRC Circuit diagram contains the value of the CRC in the eight bits of "Q7" - "Q0". Note, however, the sketch variable "CRC" is an int, not a byte, making it 16 bits long. The reason "CRC" is 16 bits long is due to lines 11 and 14 of the sketch. On those lines, "CRC" is operated upon by a value that is nine bits long. Hence, "CRC" must be longer than 8 bits. When we reach the bottom of the function, the top eight bits of "CRC" will always be "00000000". The lower eight bits will be equivalent to "Q7" - "Q0" in the circuit. The top eight bits will also be "00000000" when we arrive at the "IF" statement in line 10.
The sketch has two loops, an outer loop for the number of bytes we send to the function, and an inner loop that runs eight times, once for each bit of the incoming byte, "inByte[i]".
Lines 9 Through 15 of the Code
Comparing the equivalent circuit to the sketch, the "IF" statement in line 10 implements, exactly, the exclusive OR gate on the left of the equivalent circuit. Let's look at that statement closely:
The "%" operator is called a modulo. The result of the modulo operation is the remainder after dividing whatever is to the left of the operator by whatever is to the right of the operator. In this case, we divide the current value of the variable "CRC" by 2. If the value of the variable "CRC" is even, the modulo will be "0". If odd, the module will be "1". Whether or not "CRC" is even or odd depends solely upon the value of its least significant bit (last bit on the right). Therefore, the value of "CRC % 2" is the value of the least significant bit of "CRC".
The CRC Equivalent Circuit holds the value of the CRC on its outputs "Q7" - "Q0". Applying the same argument as in the last paragraph, "CRC % 2" is the value of "Q0", the least significant bit of the CRC stored in the flip-flops.
Using what we learned above, "inByte[i] % 2", will give us the value of the least significant bit of the data byte, "inByte[i]". This is exactly the same as the current value of "Data" in the CRC Equivalent Circuit.
The symbol "^", in the "IF" statement, sitting between the two modulo expressions, is the bitwise exclusive OR operator. Because, "Q0" and "Data" connect to the exclusive OR at the left of the equivalent circuit, the entire "IF" statement is equivalent to that same exclusive OR gate. The result of the "IF" statement is precisely the same as the output of the left-hand exclusive OR gate. From our discussion of how the exclusive OR works, if the value of the least significant bit of the variable "CRC" and the value of the least significant bit of the array "inByte[i]" are the same (both "0" or both "1"), the result of the "IF" statement will be "0", otherwise (one is a "0" and the other a "1") the result will be a "1". In the same manner, if the value of "Q0" and the value of "Data" are the same, the output of the exclusive OR gate in the equivalent circuit will be "0". If different, the value will be "1". This output is the input to the first flip-flop at the left of the circuit, and one of the inputs of the other two exclusive OR gates in the equivalent circuit.
We described of the exclusive OR gate as being a "0" if its inputs were the same and a "1" if they were different. We used that description to evaluate the "IF" statement and the output of the exclusive OR at the left of the equivalent circuit. There is another useful way to look at an exclusive OR gate, and we will use that way in the following discussion. We can look at one input of an exclusive OR as a control input that controls the relationship between the second input and the output of the gate. If this control input is a "0", the output of the exclusive OR will follow the other input. If the control is a "1", the output will be opposite of the input (A "0" becomes a "1" and a "1" becomes a "0").
The result of the "IF" statement controls which of the two operations we apply to the value of "CRC" (either line 11 or line 14). We either exclusive OR "CRC" with "100011000" or "000000000". In our new way to look at the exclusive OR gate, those two series of nine bits are the control inputs to nine exclusive OR gates. They control what happens to value of the variable "CRC" at that point in the sketch. We can call them a control word.
Let's operate on a sample byte to see what those control bits do:
| 011010101 | Sample | 011010101 | 000000000 | Control Word | 100011000 | 011010101 | Result | 111001101 |
Note that when the control word is "000000000", there is no change to the sample, the result is the same as the sample.
I said the nine bit control word was like having nine exclusive ORs. But, six of those bits are always "0", both in line 11 and line 14. Consequently, we can replace those six exclusive ORs with direct connections, meaning there are only three exclusive ORs. This happens to be the same number of exclusive OR gates in our equivalent circuit. In fact, they are in the same relative positions. The most significant bit of our control word corresponds to the left-hand exclusive OR gate. The two bits of the control word that can change, are in exactly the same place as the other two exclusive OR gates in the circuit.
The purpose of the exclusive ORs are to modify the value of CRC existing at "Q7" - "Q0", or the value of the variable "CRC", before there is further processing. If the control word is "000000000", there will be no change in the value of "CRC". Since, the effect of exclusive ORing "CRC" with "000000000" is no effect at all, lines 13 - 15 of the sketch are superfluous. They do not appear in my actual code. I only added them here because it made explanations easier.
Let's look at the output of our exclusive ORs, be they in the sketch or the equivalent circuit. Exclusive ORing with "000000000" was the result of the output of the "IF" statement being "0". Let's see what happens to the equivalent circuit when the output of the left-hand exclusive OR is "0". First, the input to the left-hand flip-flop will be "0". The output of the left-hand exclusive OR also connects to an input of the other two exclusive ORs. Let's consider the output of the left-hand exclusive OR to be the control input to the other two flip-flops. If this control input is "0", the output of the two flip-flops ("Q4" and "Q3") will be the same as their other inputs, meaning there will be no change to the CRC.
When the output of the "IF" statement is "1" we will modify the value of the variable "CRC" with "100011000". At the equivalent circuit, the output of the left-hand exclusive OR will be a "1". The effect will be that the input of the left-hand flip-flop will be "1" and the control input to the other two exclusive ORs will be a "1". This will cause the "X4" to be of the opposite logic level of "Q4" and "X3" to be of the opposite logic level of "Q3". In other words, we have flipped those two bits.
Lines 16 and 17 of the Code
"Whew", we now have the variable "CRC", and the inputs of those flip-flops, set up for the next operation.
In the equivalent circuit, the signal labeled "Clock", which has been at "0" will briefly go to a "1" and back to "0". As in our discussion of the shift register, the logic level at the inputs of those flip-flops will now appear at the outputs of the flip-flops. This has the effect of shifting the current value of CRC down one position. Sometime after that, the value of "Data" will have the next bit of the serial data coming into the circuit.
Our sketch has an exact equivalent to the "clock" signal. That equivalent is line 16: "CRC >>= 1;". This operation will take the value of "CRC" and shift all 16 bits down one bit position to the right. A "0" will be shifted into the most significant bit of "CRC".
The next line, line 17, shifts the eight bits of "inByte[i]"down one bit to the right. A "0" will be shifted into the most significant bit. The operations of lines 16 and 17, are directly comparable to applying the clock to the flip-flops, and introducing the next data bit, in the equivalent circuit.
An Example
Let's take an example of two bytes and walk them through the sketch. Let's assume the two bytes are "10110100" and "01010011". If I run "10110100" through the sketch, by itself, the resulting CRC will be "0000000001010011". If we ignore the top 8 bits, the CRC is the same as the second byte we will pass to the sketch. Since the second byte is the same as the CRC of the first byte, the final CRC should be "0000000000000000", after processing both bytes.
First Byte 1:
| i | j | inByte[i] | CRC | CRC Before Right Shift |
| 0 | 0 | 10110100 | 0000000000000000 | 0000000000000000 |
| 0 | 1 | 01011010 | 0000000000000000 | 0000000000000000 |
| 0 | 2 | 00101101 | 0000000000000000 | 0000000100011000 |
| 0 | 3 | 00010110 | 0000000010001100 | 0000000010001100 |
| 0 | 4 | 00001011 | 0000000001000110 | 0000000101011110 |
| 0 | 5 | 00000101 | 0000000010101111 | 0000000010101111 |
| 0 | 6 | 00000010 | 0000000001010111 | 0000000101001111 |
| 0 | 7 | 00000001 | 0000000010100111 | 0000000010100111 |
| 0 | 7 | 00000000 | 0000000001010011 | <-After the Final Shift |
Now Byte 2:
| i | j | inByte[i] | CRC | CRC Before Right Shift |
| 1 | 0 | 01010011 | 0000000001010011 | 0000000001010011 |
| 1 | 1 | 00101001 | 0000000000101001 | 0000000000101001 |
| 1 | 2 | 00010100 | 0000000000010100 | 0000000000010100 |
| 1 | 3 | 00001010 | 0000000000001010 | 0000000000001010 |
| 1 | 4 | 00000101 | 0000000000000101 | 0000000000000101 |
| 1 | 5 | 00000010 | 0000000000000010 | 0000000000000010 |
| 1 | 6 | 00000001 | 0000000000000001 | 0000000000000001 |
| 1 | 7 | 00000000 | 0000000000000000 | 0000000000000000 |
| 1 | 7 | 00000000 | 0000000000000000 | <-After the Final Shift |
The DS18B20 transmits data least significant bit first. If you had an application that transmits most bit significant first you would have to modify the "IF" statement. Assuming the data coming in is 8 bits in length, you could replace "inByte[i] % 2", with "inByte[i] > 127". Also, "inByte[i] >>= 1" would be replaced with "inByte[i] <<= 1". If the CRC is calculated using a different polynomial, you would have to modify line 11 accordingly.
Feel free to download and experiment with this sketch. You can enter as many bytes as you wish. Just add some print statements and setup() and loop() to feed the function.
