Almost every form of digital information exchange can introduce communication errors. Sometimes, these errors can be ignored (for example, an erroneous pixel in a high-resolution video is merely unnoticeable). However, most of the time, they cannot be ignored, and we want to ensure that the receiver gets an absolutely correct stream of information.In order to overcome the inherent inaccuracy of information transmission, a few methods for error detection and correction have been developed. Generally speaking, these methods introduce some redundancy to the actual message, which in turn can be used to detect errors and in some cases to recover the original data.
One of the most common methods is the use of the CRC (cyclic redundancy check) function, a family of codes commonly used to ensure data integrity in digital data streams by detecting errors due to noise or dropouts of bits in the message stream. The CRC calculates a series of bits (also commonly referred to as a CRC) that is appended to the data stream and transmitted along with the message. The receiver performs a CRC function on the message and compares the result with the received CRC code to verify the integrity of the message. CRC is commonly used in a number of applications such as digital communications and computer data storage systems.
The CRC is performed through binary polynomial division between the transmitted message and a polynomial divisor and is usually implemented using a linear feedback shift register (LFSR). An LFSR is a shift register where its next state is a linear combination of its previous state and input bits. In our context, the linear operators are Logical XOR and Logical AND. Since the operation of an LFSR circuit is deterministic, and the CRC is shorter than the message, typically few messages are mapped to each CRC value. A well-chosen polynomial ensures an evenly distributed mapping of messages to CRC values (for example, if all messages were mapped to the same CRC, detection of an error in a message bit would be impossible).
The trick in an embedded systems design is to implement this technique in the most efficient way possible and in the smallest possible footprint. In this article, we discuss aspects of the theory and implementation of LFSRs and CRCs, illustrated using a family of instructions on Analog Devices’ Blackfin processor specifically defined for addressing the task of efficient LFSR implementation. We also provide a method for converting an implementation from an Internal LFSR form to an External LFSR form.
