Concepts and Experiments for Optimizing Wide-Input Streaming CRC Circuits

Inhalt:
Cyclic Redundancy Check (CRC) is one of the most common checksum methods for data storage and communication. As the progress of silicon technology provides density but hardly any speed gains anymore, increases in data communication bandwidth can only be achieved with higher parallelism. Traditional methods for CRC calculation either result in high circuit cost or limit clock speed when the width of the input data increases. The basic idea presented in this paper is to use an arbitrary generator system for the representation of the partial checksum. This opens a wide design space and introduces redundancy. Two methods are presented that can be combined. The first method results in an optimal step matrix for maximal speed. For the wide input matrix, a large space is searched for a good solution. The second method focuses on the input matrix and uses clustering to select a generator system that reduces the density and logic depth for the input matrix. As an implementation would make use of common subexpression elimination (CSE), a simple yet effective CSE algorithm is presented, which is integrated into the two optimization methods for proper cost evaluation. First results for Ethernet and SCTP checksums are given.