Circuit for determining, in parallel, the terms of a remainder that results from dividing two binary polynomials

摘要

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.0. 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. From this determination, the configuration of sub-networks of XOR devices is determined.