Browse Prior Art Database

Programmed Cyclic Redundancy Checking

IP.com Disclosure Number: IPCOM000087264D
Original Publication Date: 1977-Jan-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 2 page(s) / 31K

Publishing Venue

IBM

Related People

Hanover, HC: AUTHOR [+2]

Abstract

Cyclic redundancy checking (CRC) is a relatively old technique of error detection in the transmission of data. Boudreau and Steen developed an equation relating the CRC after J+l characters to the CRC after J characters [*]. For four-bit characters and a 16-bit CRC, Aj+1 = [Aj + Cj+1]G/4/, where Aj = a/j/(o), a/j/(1), ---- , a/j/(15)= j/th/ CRC remainder Cj+l = (0,0,...,C/j+1/(o), C/j+1/(o), C/j+1/(1), C/j+1/(2), C/j+1/(3).

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 93% of the total text.

Page 1 of 2

Programmed Cyclic Redundancy Checking

Cyclic redundancy checking (CRC) is a relatively old technique of error detection in the transmission of data. Boudreau and Steen developed an equation relating the CRC after J+l characters to the CRC after J characters [*]. For four-bit characters and a 16-bit CRC, Aj+1 = [Aj + Cj+1]G/4/, where

Aj = a/j/(o), a/j/(1), ---- , a/j/(15)= j/th/ CRC remainder

Cj+l = (0,0,...,C/j+1/(o), C/j+1/(o), C/j+1/(1),

C/j+1/(2), C/j+1/(3).

In the above-identified article, the message polynomial is handled low-order bits first.

In situations where the message polynomial is received high-order bits first, there are two alternatives. The first is to simply receive the entire message, reverse the bits and treat them in accordance with the above equations. There are occasions when there is not sufficient time to make such a bit reversal. In this situation, one can make a matrix transformation such that a new generator matrix H/4/ is produced, viz., H/4/ = Transform (G/4/) and the following equations apply:. Bj+l - (Bj + Dj+l)H/4/, when

Bj = a/j/(15), a/j/(14), ---- , a/j/(o)= bit reversed CRC

remainder Dj+l = (C/j+1/(3), C/j+1/(2), C/j+1/(1),

C/j+1/(0) 0, --- 0) = bit reversed character.

Using the above equations for bit rcversed message polynomials and the principles set forth in the above-identified article, one can readily implement a system to generate a CRC.
[*] Boudreau and Steen, "Cyclic Redundancy Checking by Program",

Proceedings of the...