Get Adobe Flash player
FacebookTwitterGoogle+
English Arabic French German Italian Portuguese Russian Spanish

Did you know?

The word engineering is derived from the Latin word ingeniere which means ingenious.
 

Help us stay online:

small donate

crcAll 1-Wire® devices, including iButton® devices, contain an 8-byte unique registration number in read-only memory (ROM). This registration number is used as a unique network address on a 1-Wire bus. To ensure data communication integrity, one byte of each registration number is a DOW CRC byte. This article explains how to calculate this 8-bit DOW CRC and gives example code that is used in iButton AVR readout example project used with DS1990R-F5.

 In the first part of this article we will give detailed explanation of CRC calculation. There are several ways to calculate and all will be mentioned. After that overview, example of C code I used will be provided.

The Maxim iButton products are a family of devices that all communicate over a single wire following a specific command sequence referred to as the 1-Wire Protocol. A key feature of each device is a unique 8-byte ROM code written into each part at the time of manufacture. The components of this 8-byte code can be seen in Figure 1. The least significant byte contains a family code that identifies the type of iButton product. For example, the DS1990A has a family code of 01 Hex and the DS1991 has a family code of 02 Hex. Since multiple devices of the same or different family types can reside on the same 1-Wire bus simultaneously, it is important for the host to be able to determine how to properly access each of the devices that it locates on the 1-Wire bus. The family code provides this information. The next 6 bytes contain a unique serial number that allows multiple devices within the same family code to be distinguished from each other. This unique serial number can be thought of as an "address" for each device on the 1-Wire bus. The entire collection of devices plus the host form a type of miniature local area network, or MicroLAN; they all communicate over the single common wire. The most significant byte in the ROM code of each device contains a Cyclic Redundancy Check (CRC) value based on the previous 7 bytes of data for that part. When the host system begins communication with a device, the 8-byte ROM is read, LSB first. If the CRC that is calculated by the host agrees with the CRC contained in byte 7 of ROM data, the communication can be considered valid. If this is not the case, an error has occurred and the ROM code should be read again.

 1 CRC

Figure 1. iButton system configuration using DOW CRC.

Some of the iButton products have up to 8kB of RAM in addition to the 8 bytes of ROM that can be accessed by the host system with appropriate commands. Even if iButtons do not have CRC hardware onboard, if the host has the capability to calculate a CRC value for the ROM codes, then a procedure to store and retrieve data in the RAM portion of the devices using CRCs can also be developed. Data can be written to the device in the normal manner; then a CRC value that has been calculated by the host is appended and stored with the data. When this data is retrieved from the iButton, the process is reversed. The host compares the CRC value that was computed for the data bytes to the value stored in memory as the CRC for that data. If the values are equal, the data read from the iButton can be considered valid. In order to take advantage of the power of CRCs to validate the serial communication on the 1-Wire bus, an understanding of what a CRC is and how they work is necessary. In addition, a practical method for calculation of the CRC values by the host will be required for either a hardware or software implementation.

Background

Serial data can be checked for errors in a variety of ways. One common way is to include an additional bit in each packet being checked that will indicate if an error has occurred. For packets of 8-bit ASCII characters, for example, an extra bit is appended to each ASCII character that indicates if the character contains errors. Suppose the data consisted of a bit string of 11010001. A 9th bit would be appended so that the total number of bits that are 1s is always an odd number. Thus, a 1 would be appended and the data packet would become 111010001. The underlined character indicates the parity bit value required to make the complete 9-bit packet have an odd number of bits. If the received data was 111010001, then it would be assumed that the information was correct. If, however, the data received was 111010101, where the 7th bit from the left has been incorrectly received, the total number of 1s is no longer odd and an error condition has been detected and appropriate action would be taken. This type of scheme is called odd parity. Similarly, the total number of 1s could also be chosen to always be equal to an even number, thus the term even parity. This scheme is limited to detecting an odd number of bit errors, however. In the example above, if the data were corrupted and became 111011101, where both the 6th and 7th bits from the left were wrong, the parity check appears correct; yet the error would go undetected whether even or odd parity was used.

Maxim 1-Wire CRC

The error detection scheme most effective at locating errors in a serial data stream with a minimal amount of hardware is the Cyclic Redundancy Check (CRC). The operation and properties of the CRC function used in Maxim products will be presented without going into the mathematical details of proving the statements and descriptions. The mathematical concepts behind the properties of the CRC are described in detail in the references. The CRC can be most easily understood by considering the function as it would actually be built in hardware, usually represented as a shift register arrangement with feedback as shown in Figure 2. Alternatively, the CRC is sometimes referred to as a polynomial expression in a dummy variable X, with binary coefficients for each of the terms. The coefficients correspond directly to the feedback paths shown in the shift register implementation. The number of stages in the shift register for the hardware description, or the highest order coefficient present in the polynomial expression, indicate the magnitude of the CRC value that will be computed. CRC codes that are commonly used in digital data communications include the CRC-16 and the CRC-CCITT, each of which computes a 16-bit CRC value. The Maxim 1-Wire CRC (DOW CRC) magnitude is 8 bits, which is used for checking the 64-bit ROM code written into each 1-Wire product. This ROM code consists of an 8-bit family code written into the least significant byte, a unique 48-bit serial number written into the next 6 bytes, and a CRC value that is computed based on the preceding 56 bits of ROM and then written into the most significant byte. The location of the feedback paths represented by the exclusive-or gates in Figure 2, or the presence of coefficients in the polynomial expression, determine the properties of the CRC and the ability of the algorithm to locate certain types of errors in the data. For the DOW CRC, the types of errors that are detectable are:

1. Any odd number of errors anywhere within the 64-bit number.

2. All double-bit errors anywhere within the 64-bit number.

3. Any cluster of errors that can be contained within an 8-bit "window" (1-8 bits incorrect).

4. Most larger clusters of errors.

The input data is exclusive-or'd with the output of the eighth stage of the shift register in Figure 2. The shift register may be considered mathematically as a dividing circuit. The input data is the dividend, and the shift register with feedback acts as a divisor. The resulting quotient is discarded, and the remainder is the CRC value for that particular stream of input data, which resides in the shift register after the last data bit has been shifted in. From the shift register implementation it is obvious that the final result (CRC value) is dependent, in a very complex way, on the past history of the bits presented. Therefore, it would take an extremely rare combination of errors to escape detection by this method.

  3 CRC polynom

Figure 2. Maxim 1-Wire 8-bit CRC.

Methods of CRC calculation

To calculate CRC basically you have two ways:

- First is to make mathematical calculation that demands more processor time and is more complicated to understand but requires little flash memory and some RAM memory.

- Second is to make array of precalculated CRC results. This way calculation is much faster and requires maybe even little bit less RAM, but will eat up 256 bytes of flash code memory space.

Usually when we make program RAM memory is more critical while flash memory is big enough. This made me choose second approach. This and fact that after reading application note on maxim dallas site, I was even more confused than before reading it. See for yourself explanation on this link.

To calculate CRC as previously said we store array of CRC values. Code that is fully tested is given below with comments explaining its functionality. This code is fully tested in project iButton AVR readout example project used with DS1990R-F5 and is working perfectly.

unsigned char iButtonData[8] = { 0x00, 0x0, 0x00, 0x00, 0x00, 0x00, 0x00 , 0x00};
const unsigned char crcTable[] = {
0, 94, 188, 226, 97, 63, 221, 131, 194, 156, 126, 32, 163, 253, 31, 65,
157, 195, 33, 127, 252, 162, 64, 30, 95, 1, 227, 189, 62, 96, 130, 220,
35, 125, 159, 193, 66, 28, 254, 160, 225, 191, 93, 3, 128, 222, 60, 98,
190, 224, 2, 92, 223, 129, 99, 61, 124, 34, 192, 158, 29, 67, 161, 255,
70, 24, 250, 164, 39, 121, 155, 197, 132, 218, 56, 102, 229, 187, 89, 7,
219, 133, 103, 57, 186, 228, 6, 88, 25, 71, 165, 251, 120, 38, 196, 154,
101, 59, 217, 135, 4, 90, 184, 230, 167, 249, 27, 69, 198, 152, 122, 36,
248, 166, 68, 26, 153, 199, 37, 123, 58, 100, 134, 216, 91, 5, 231, 185,
140, 210, 48, 110, 237, 179, 81, 15, 78, 16, 242, 172, 47, 113, 147, 205,
17, 79, 173, 243, 112, 46, 204, 146, 211, 141, 111, 49, 178, 236, 14, 80,
175, 241, 19, 77, 206, 144, 114, 44, 109, 51, 209, 143, 12, 82, 176, 238,
50, 108, 142, 208, 83, 13, 239, 177, 240, 174, 76, 18, 145, 207, 45, 115,
202, 148, 118, 40, 171, 245, 23, 73, 8, 86, 180, 234, 105, 55, 213, 139,
87, 9, 235, 181, 54, 104, 138, 212, 149, 203, 41, 119, 244, 170, 72, 22,
233, 183, 85, 11, 136, 214, 52, 106, 43, 117, 151, 201, 74, 20, 246, 168,
116, 42, 200, 150, 21, 75, 169, 247, 182, 232, 10, 84, 215, 137, 107, 53
};
int iButtonCRC()
{
unsigned char i,crc,tmp;
for(i=0,crc=0;i<7;i++)
{
tmp = crc ^ iButtonData[i];
crc = crcTable[tmp];
}
/*if(crc==iButtonData[7])
return(1);
return(0); */ //this can be used to accept only valid codes read since
// iButtonData[7] is actually CRC data read from iButton that should be the
//same number as calculated CRC using provided function
return(crc);
}

It is simple code that works very fast and is easy to understand. I hope this helped you. Feel free to comment and see the rest on the site for more quality information from field of electronics.

 

Special thanks to Zoran Radmilovic for CRC calculation contribution.

Partial source: http://www.maxim-ic.com