Residue Generation by Carry Save Addition
Original Publication Date: 1985-Nov-01
Included in the Prior Art Database: 2005-Feb-19
The invention is a method that provides a fast, inexpensive method for generating residue codes for large binary numbers or data sets. Residue codes are well known, as are their error-checking properties. However, the expense, in terms of circuits and performance, of using residue codes for error checking has limited their use for this purpose. The invention provides a method of generating a class of residue codes rapidly and inexpensively via simple addition. The invention is based on the following observation. A property of discrete numbering systems is that the remainder or residue of a number divided by (B-1), where B is the base of the numbering system, can be found by adding the digits for the number modulo (B-1). For example, the residue modulo 9 of 125 (base 10) can be found by adding 1 + 2 + 5 = 8, or 9 125 = 8.