Residue calculation circuit

A residue calculation circuit for calculating a residue for input residue data, comprising:

• first through nth delay means connected in cascade for delaying input residue data supplied to said first delay means, each of said first through nth delay means delaying data supplied thereto and outputting respective delayed data;
• means for multiplying said input residue data by a first coefficient to obtain a first product, for obtaining a residue of said first product with regard to a predetermined residue number and for supplying said residue of said first product as an output;
• first through nth multiplication means for multiplying said delayed data of said first through nth delay means, respectively, by n respective coefficients to obtain n respective products, for obtaining a respective residue of each of said n respective products with regard to said predetermined residue number, and for adding a predetermined correction value to each of said respective residues to obtain n respective correction data;
• first stage addition means for performing binary non-residue addition of said residue from said means for multiplying and said correction data from said first multiplication means to obtain first stage sum data, and for supplying as an output said first stage sum data and a first stage carry signal representing a presence or absence of a carry of said first stage addition means;
• further addition means including second through nth stage addition means for respectively performing binary non-residue addition of said sum data output from a previous stage addition means and said respective correction data output from the second through nth of said multiplication means to obtain respective second through nth stage sum data, and for respectively supplying as an output said second through nth stage sum data and a second through nth stage carry signal representing a presence or absence of a carry of said respective second through nth stage addition means;
• means for accumulating inverse values of said first through nth stage carry signals to obtain a cumulative carry value;
• carry multiplying means for multiplying said cumulative carry value by said predetermined correction value to obtain a cumulative correction value;
• and
• means for subtracting said cumulative correction value from said nth stage sum data supplied from said nth stage addition means to obtain corrected data and supplying said corrected data as an output.