Browse Prior Art Database

Method for CRC generation using remainder slicing and parallel table lookups

IP.com Disclosure Number: IPCOM000109304D
Publication Date: 2005-Mar-23
Document File: 3 page(s) / 88K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for cyclic redundancy code (CRC) generation using remainder slicing and parallel table lookups. Benefits include improved functionality and improved performance.

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

Method for CRC generation using remainder slicing and parallel table lookups

Disclosed is a method for cyclic redundancy code (CRC) generation using remainder slicing and parallel table lookups. Benefits include improved functionality and improved performance.

Background

              Conventionally, Internet and data center applications require reliable and secure transactions at gigabit per second rates. To detect changes of content in transit, a number of server protocols support sophisticated data integrity checks. Software based CRC generation algorithms are computation intensive and fail to meet the requirement of high-speed packet processing at Internet servers.

              CRC algorithms perform long division using module-2 arithmetic. Table driven CRC algorithms are based on the precomputation of all possible remainders and use a look-up table to replace multiple long division steps. The disadvantage of table driven CRC algorithms is their memory requirement due to reading a large number of bits at a time. For example, to achieve acceleration by reading 32 bits at a time, table driven algorithms require a table of 232 entries and 16 GB of memory.

              The table driven 32-bit CRC single table algorithms result in a 7 clock cycles per byte execution cost. A 4096-byte data block requires more than 28,000 CPU clocks.

General description

              The disclosed method includes accelerated table-driven CRC algorithms. The method slices each data chunk (such as 32 bits) into multiple-bit groups and performs lookups into multiple small tables. The method enables reasonable cache footprints while at least doubling the conventional performance of table-driven algorithms. 

Advantages

              The disclosed method provides advantages, including:

·         Improved functionality due to providing a CRC algorithm without requiring specialized instruction sets

·         Improved performance due to improved execution time by using accelerated algorithms

Detailed description

First Step

Let P be the initial p most significant (i.e., initially transmitted) bits of an input bit stream B. Let l > p be the length of B in bits. Let also gg < l be the length of the generator polynomial G(x) used in the generation of the CRC value. We consider that the l-g+1 most significant bits of the input stream B are the information bits which are being encoded, whereas the  g-1 least significant bits of B are equal to zero as required by typical CRC generation algorithms. For the binary numbers P and B we write:

 

(1)

where b1 is the most significant bit of P and B.

The binary number P is sliced into m slices, which we symbolize as P1, P2, ..., Pm, of lengths  p1, p2, ..., pm such that P = [P1:P2: ...:Pm] and  p = ∑i pi for every i ∊[1, m]. As mentioned before, the binary number P is sliced in order for our algorithms to be able to read potentially large amount of data without having to access a lookup table of 2p entries.

For each of the slices, a table lookup is perf...