Simple checksum calculation

When data is transmitted over communication lines, a checksum is used , calculated according to some algorithm. The algorithm is often complex, of course, it is mathematically justified, but it is very inconvenient when there is a shortage of resources, for example, when programming microcontrollers.



To simplify the algorithm, without losing quality, you need a bit of “bit magic,” which is an interesting topic in itself.

Without a checksum, it is dangerous to transmit data, since interference is present everywhere and always, the whole question is only in their probability of occurrence and the side effects caused by them. Depending on the conditions, the algorithm of error detection and the amount of data in the checksum are chosen. The algorithm is more complicated, and the checksum is larger, less errors are not recognized.
')


The cause of interference at the physical level, during data transmission.



Here is an example of the most typical algorithm for a microcontroller, which has actually become an industry standard since 1979.


Such code is not weak, there is an option without a table , but slower (bit-by-bit data processing is necessary), in any case able to take out the brain to both the programmer and the microcontroller. Not in any microcontroller the algorithm with the table will get at all.

Let's analyze the algorithms that generally can confirm the integrity of the data with a low price.

Parity bit (1-bit checksum)

In the first place is a simple parity bit. If necessary, the hardware is formed, the principle is the simplest, and is described in detail in Wikipedia . There is only one drawback, it skips double errors (and even an even number of errors), when the parity of all bits does not change. It can be used to collect statistics on the presence of errors in the stream of transmitted data, but data integrity does not guarantee, although it reduces the likelihood of a missed error by 50% (depends, of course, on the type of interference on the line, in this case it is assumed that the number of even and odd failures is equal to ).
To enable the parity bit, often no code is needed, just indicate that the UART should use the parity bit. Typically, simply specify:


Often, developers even forget that the UART has the ability to check bit parity on board. In addition to the integrity of the transmitted data, this allows you to avoid a steady breakdown of synchronization (for example, when transmitting data over the air), when the payload can randomly simulate start and stop bits, and instead of data at the output of the buffer, start and stop bits in random order.

8-bit checksum

If the parity is small (and this is usually small), an additional checksum is added. Calculate the checksum, you can as the amount of previously transferred bytes, simply and logically



Naturally, the overflow bits are not taken into account, the result is placed in the 8 bits allocated for the checksum. You can skip the error if, in the event of an accidental failure, one byte is increased by some value, and the other byte is reduced by the same value. Checksum does not change. Let's conduct an experiment on data transfer. Baseline data are as follows:

1. The data block is 8 bytes.
2. Random ($ FF + 1) pseudo-random data population
3. Randomly change 1 bit in a data block with an XOR operation with a specially prepared byte, which has one single bit at a random position.
4. We repeat the previous paragraph 10 times, this can result in 0 to 10 bad bits (2 errors can be superimposed on each other when restoring data), we ignore the option with 0 bad bits in the future as useless for us.

We transmit a virtual telegram N times. The ideal checksum will reveal an error in the amount of information available to it about the message, more information, a higher probability of detecting a faulty telegram. Probability of missing an error for 1 bit of checksum:

.

For 8 bits:

,

for 256 sent telegrams with an error, one will pass the checksum check. We look at the statistics from virtual data transfer using a simple test program:



Or conditional efficiency = 55% of the capabilities of the “ideal” checksum. Such is the fee for the simplicity of the algorithm and the speed of data processing. In general, for many applications, the algorithm is operational. One addition operation and one 8-bit variable are used. There is no possibility of incorrect implementation. Therefore, the algorithm is used in the ADAMS, ICP controllers as part of the DCON protocol (the parity bit can be included there, the ASCI characters only, which also contributes to improving the reliability of data transmission and the resulting reliability is somewhat higher, as part of the errors are detected by other, additional features not related to checksum).

Despite the probability of passing an error of 1: 143, the probability of finding an error better than 1: 256 is impossible theoretically. There are losses in the quality of work, but this is not always significant. If you need higher reliability, you need to use a checksum with a large number of bits. Or, in other words, a simple checksum does not efficiently use about 0.75 bits out of 8 available bits of information in the checksum.

For comparison, instead of the sum, bitwise XOR is added. It became significantly worse, the probability of detecting an error was 1:67 or 26% of the theoretical limit. Simplified, this can be explained by the fact that XOR changes even fewer bits in the checksum when an error occurs, lower the response to a single bit failure, and a repeated error is more likely to return the checksum to its original state.

It can also be argued that the checksum for XOR is 8 independent checksums of 1 bit. The probability that an error will occur in one of 8 bits is 1: 8, the probability of double failure 1:64, which we observe, the theoretical value coincided with experimental data.

We need such an algorithm to replace with the single error the maximum number of bits in the checksum. But we are, in total, limited by the complexity of the algorithm, and the resources at our disposal. Not all microcontrollers have a hardware CRC calculation unit. But, almost everywhere, there is a multiplication unit. Calculate the checksum as the product of a sequence of bytes, on some "magic" constant:

 CRC=CRC + byte*211 

The constant should be simple, and be large enough to change a larger number of bits after each operation, 211 is quite suitable, we check:


Only 72% of the theoretical limit, a slight improvement over the simple amount. The algorithm in this form does not make sense. In this case, important information from the discarded high bits of 8..16 is lost, and they must be taken into account. The easiest way is to mix the XOR function with the lower bits 1..8. We come to an even more intensive modification of the checksum, preferably with minimal resources. Add focus from cryptographic algorithms

 CRC=CRC + byte*211 CRC= CRC XOR (CRC SHR 8); // "" ,     CRC=CRC AND $FF; //     8,   16  

• The intermediate CRC for the first action is 16-bit (after calculations it is cut to 8 bits) and in the future we work as with 8-bit, if we have an 8-bit microcontroller, this will speed up data processing.
• We return the high bits and mix with the low bits.

Checking:


The result is 91% of the theoretical limit. It is quite suitable for use.

If there is no multiplication unit in the microcontroller, you can simulate the multiplication of the operations of addition, offset and XOR. The essence of the process is the same, modified by an error bit, evenly “distributed” over the remaining bits of the checksum.

 CRC := (CRC shl 3) + byte; CRC := (CRC shl 3) + byte; CRC:=(CRC XOR (CRC SHR 8)) ; //      

Result:


Surprisingly good result. The average value is 254.5 or 99% of the theoretical limit, operations are slightly more, but they are all simple and no multiplication is used.

If for internal storage of intermediate checksum values ​​we give 16 bits to the variable (but only the lower 8 bits are transmitted via the communication line), which is not a problem even for the weakest microcontroller, we will get some improvement in the operation of the algorithm. In general, saving 8 bits does not make much sense, and the 8-bit intermediate variable was previously used simply to simplify the understanding of the algorithm.


That corresponds to 100.6% of the theoretical limit, quite a good result for such a simple one-line algorithm:

 CRC:=CRC + byte*44111; //   16- 

Full 16-bit multiplication is used. Again, it was not without the magic number 44111 (selected from general considerations without going through the entire subset of numbers). More precisely, it makes sense to select a constant only after having decided on the expected type of errors in the data transmission line.

Such a high result is explained by the fact that 2 cycles of multiplication in a row completely mix the bits, which is what we needed. The exception, it seems, is the last byte of the telegram, especially its high bits, they are not fully mixed in the checksum, but the probability that an error will occur in them is small, approximately 4%. This feature practically does not manifest itself statistically, at least on my set of test data and an error limited to 10 failed bits. To exclude this feature, you can do N + 1 iterations by adding a virtual byte in addition to the ones in the test data block (but this is a complication of the algorithm).

Option without multiplication with the same result. The CRC variable is 16-bit, 8-bit data, the result of the algorithm is the lower 8 bits of the checksum found:

 CRC := (CRC shl 2) + CRC + byte; CRC := (CRC shl 2) + CRC + byte; CRC:=(CRC XOR (CRC SHR 8)); 

The result is 100.6% of the theoretical limit.

The non-multiplication option is simpler, leaving the bare minimum of functions, only 3 mathematical operations:

 CRC:=byte + CRC; CRC:=CRC xor (CRC shr 2); 

The result is 86% of the theoretical limit.

In this case, the loss of the most significant bits is not; they are returned to the lower part of the variable through the XOR function (bit mixer).

A slight improvement in some cases gives the same:

• Double pass on processed data. But at the cost of complicating the algorithm (the outer loop must be specified), at the cost of doubling the processing time.
• The processing of an additional, virtual byte at the end of the processed data, the complexity of the algorithm and the time of the algorithm is almost nonexistent.
• Using a variable to store a checksum greater in bit depth than the final checksum and mixing the lower bits with the high bits.

The result of the work of the considered algorithms, from simple and weak, to complex and qualitative:

16-bit checksum

Further, suppose that 8 bits are not enough for us to form a checksum.



The next option is 16 bits, and the theoretical error probability of the transmitted data is 1: 65536, which is much better. Reliability grows exponentially. But, as a side effect, the amount of auxiliary data is growing, by the example of our telegram, 2 bytes of checksum are added to 8 bytes of useful information.

Simple sum and XOR algorithms, as applied to the 16-bit and subsequent CRCs, are not considered at all, they practically do not improve the quality of work, compared to the 8-bit variants.

We modify the algorithm for processing a checksum of 16 bits, it should be noted that there is also a magic number 8 and 44111, a significant and unreasonable change worsens the work of the algorithm several times.

 CRC:=CRC + byte16*44111; //  16- CRC:=CRC XOR (CRC SHR 8); 

Result:


That corresponds to 109% of the theoretical limit. There is a measurement error, but it is excusable for 10 million iterations. It also affects the creation algorithm, and in general the type of errors. For a more accurate analysis, in any case, you need to adjust the conditions for errors in a particular data line.

Additionally, I note that you can use 32-bit intermediate variables to accumulate the result, and use the final checksum as the lower 16 bits. In many cases, for any digit of the checksum, the quality of the algorithm improves somewhat.

32-bit checksum

Let's move on to the 32-bit checksum option. There is a problem with the time devoted to the analysis of statistical data, since the number of transmitted telegrams is already comparable to 2 ^ 32. The algorithm is the same; magic numbers change upwards

 CRC:=CRC+byte32*$990C9AB5; CRC:=CRC XOR (CRC SHR 16); 

Over 10 million iterations, no error was detected. To speed up the collection of statistics cut the CRC to 24 bits:

 CRC = CRC AND $FFFFFF; 

The result, out of 10 million iterations, the error was detected 3 times


Quite a good result and generally close to the theoretical limit for 24-bit checksum (1: 16777216). Here it should be noted that the data integrity control function is evenly distributed across all CRC bits, and it is quite possible to discard them from any side if there is a limit on the size of the transmitted CRC.

For full-fledged 32 bits, it’s enough to wait long for the result, there are simply no errors, for an acceptable waiting time.

Option without multiplication:

 CRC := (CRC shl 5) + CRC + byte; CRC := (CRC shl 5) + CRC; CRC:=CRC xor (CRC shr 16); 

There was no failure for a full-fledged checksum. The checksum trimmed to 24 bits shows approximately the same results, 8 errors per 100 million iterations. Intermediate variable CRC 64-bit.

64-bit checksum

And finally, 64-bit checksum, the maximum checksum, which makes sense when transferring data at the lower level:

 CRC:=CRC+byte64*$5FB7D03C81AE5243; CRC:=CRC XOR (CRC SHR 8); //   1..20 

Wait for the data transmission error, until the end of the universe, probably will not work :)



A method similar to that used for the CRC32 showed similar results. More bits are left, higher reliability is in full compliance with the theoretical limit. Checked on the lower 20 and 24 bits, this seems to be quite sufficient to assess the quality of the algorithm.

You can also apply for 128-bit numbers (and even larger ones), the main thing is to choose correctly 128-bit magic constants. But this is clearly not for microcontrollers, such numbers are not supported by the compiler.

Comments

In general, the multiplication method is similar to the generation of a pseudo-random sequence, only taking into account the useful data involved in the process.

I recommend to use in microcontrollers, or to check the integrity of any transmitted data. It is a working method, already as it is, despite the simplicity of the algorithm.

My CRC research project on githab .

Further, it would be interesting to optimize the algorithm for more real data (not pseudo-random numbers by the standard algorithm), to select more suitable magic numbers for a number of tasks and initial conditions, I think you can still win fractions of a percent in the quality of the algorithm. Optimize the algorithm for speed, readability of the code (the simplicity of the algorithm), quality of work. Ideally, get and test code samples for all types of microcontrollers, for this you need examples using the multiplication of 8, 16, 32 bit data, and no multiplication at all.