Eugene Chien Ko

US Patent:

59056649, May 18, 1999

Filed:

Apr 4, 1997

Appl. No.:

8/832986

Inventors:

Eugene Ko - Milpitas CA
Juin-Yeu Joseph Lu - Santa Clara CA

Assignee:

National Semiconductor Corp. - Santa Clara CA

International Classification:

G06F7/38;7/00

US Classification:

364746

Abstract:

A circuit that determines the remainder of a modulo 2 polynomial division in just one clock cycle. Specifically, each term of the remainder is determined in parallel with each other term of the remainder. The circuit includes a network of XOR devices to determine H(X)=P(X) mod G(X), where P(X) is a first binary polynomial, of a form: a. sub. m X. sup. m +a. sub. m-1 X. sup. m-1 30. . . +a. sub. 0, where a={0,1} and X={0,1}; G(X) is a second binary polynomial, of a form: a. sub. n X. sup. n +a. sub. n-1 X. sup. n-1 +. . . +a. sub. 0, where a={0,1} and X={0,1}, and m>n; and H(X) is a third binary polynomial, of a form: b. sub. p X. sup. p +b. sub. p-1 X. sup. p-1 +. . . +. sub. The configuration of the network of XOR devices is determined by reducing terms of the first binary polynomial to have only terms having less than the degree of the second binary polynomial. Then, for each term of the third binary polynomial (i. e. , the remainder), it is determined which reduced terms of the first binary polynomial affect it.