Methods and apparatus for error checking code decomposition
AssigneeAltera Corporation
InventorsGregg William Baeckler, Babette Van Antwerpen
Life of this patent
Estimating the term…
Abstract
Methods and apparatus are provided for more efficiently implementing error checking code circuitry on a programmable chip. In one example, Cyclic Redundancy Check (CRC) exclusive OR (XOR) circuitry is decomposed to allow efficient implementation on lookup tables (LUTs) of various sizes on a device. XOR cancellation factoring is used to break up wide CRC XORs into blocks that fit in various LUTs while maintaining focus on minimizing logic depth and logic area. Simulated annealing is used to further reduce logic area cost.
Claims20
A method for decomposition of a circuit for implementation on a programmable chip, the method comprising:
- identifying a supported programmable chip lookup table (LUT) size, a cyclic redundancy check (CRC) width, and a polynomial associated with the CRC width;
- determining a plurality of wide Exclusive OR (XOR) operations corresponding to a plurality of CRC output bits for a system, wherein the wide XOR operations include a plurality of XOR inputs;
- and
- factoring the wide XOR operations with cancellation using a processor to break the wide XOR operations into XOR operations no wider than the supported LUT size.
A system, comprising:
- an interface operable to receive a supported programmable chip lookup table (LUT) size, a cyclic redundancy check (CRC) width, and a polynomial associated with the CRC width;
- and
- a processor configured to determine a plurality of wide Exclusive OR (XOR) operations corresponding to a plurality of CRC output bits for a system, wherein the wide XOR operations include a plurality of XOR inputs, the processor further configured to factor the wide XOR operations with cancellation to break the wide XOR operations into XOR operations no wider than the supported LUT size.
A computer readable storage medium having computer code embodied therein, the computer readable medium comprising:
- computer code for identifying a supported programmable chip lookup table (LUT) size, a cyclic redundancy check (CRC) width, and a polynomial associated with the CRC width;
- computer code for determining a plurality of wide Exclusive OR (XOR) operations corresponding to a plurality of CRC output bits for a system, wherein the wide XOR operations include a plurality of XOR inputs;
- and
- computer code for factoring the wide XOR operations with cancellation using a processor to break the wide XOR operations into XOR operations no wider than the supported LUT size.
Dependencies are inferred from the claim text.