Cyclic redundancy check
lastmod 2018-12-26created 2018-12-261 edits
A cyclic redundancy check (CRC) is a method of determining a check value used to verify whether transmitted data contains errors when data is sent over a network or similar channel.
Before the data is sent, a CRC value is computed from the given data and appended to it for transmission; after the transmission finishes, the CRC value is computed again from the received data. The two values are then compared, and if they differ, it can be concluded that errors were introduced during transmission, for example by noise.
CRC is easy to implement in binary hardware and excels at detecting common errors that occur during data transmission. However, because of the structure of CRC, it is easy to deliberately construct other data with a given CRC value, so it cannot be used to verify data integrity. Functions such as MD5 are used for that purpose.
Computing a cyclic redundancy check can be approached in hardware or in software. In hardware, computing over serial data is simple. In communication systems, the closer a protocol layer is to the physical layer, the more a hardware approach is used, and the closer it is to the upper layers, the more a software approach is applied.
In communication systems, layers closer to the physical layer tend to use serial data, so a hardware computation method is used, since transmission lines carry almost entirely serial data. In this case the cyclic redundancy check produces output for bit-by-bit input, which is simple to build as a logic circuit. Higher layers, however, use parallel data (in octets, 8 bits). In these cases a software approach is used, mostly computing byte by byte. Since a cyclic redundancy check ultimately comes down to per-bit XOR operations on bit-level input, even computing a single byte has limits for fast software computation. In such cases, precomputed tables are commonly used.