Algorithms of accelerated division on modulo 2
Andrey N. Malchukov, Alexander Osokin, Y.B. Bourkatovskaya · Korea-Russia International Symposium on Science and Technology · 2003
Two algorithms of accelerated division on modulo 2 are proposed. Let us consider polynomials: A(x)=/spl Sigma//sub i=0//sup n/a/sub n-i/x/sup n-i/, B(x)=/spl Sigma//sub i=0//sup m/a/sub m-i/x/sup m-i/, where a/sub i/, b/sub j/ ? {0,1}; n ? m. Generally only one bit of quotient is computed in one step. The first algorithm is based on based on simultaneous computation of high- and low-order bits of the quotient. Theorem 1. Consider polynomials A(x) and B(x) specified by the above equation. If s is the number of the high-order insignificant zeros of B(x) and /spl exist/j:0/spl les/j<s, a/sub j/=1, then A(x) is not divided exactly into B(x). A polynomial A'(x) is constructed from the polynomial A(x) by writing the coefficients of A(x) in the reverse order, that is, A'(x)=x/sup n/A(x/sup -1/)=/spl Sigma//sub i=0//sup n/a/sub n-i/x/sup n-i/. Theorem 2. Consider polynomials A(x), B(x) and polynomials A'(x), B'(x). If A(x) is divided exactly into B(x), then A'(x) is divided exactly into B'(x), and the corresponding quotients C(x) and C'(x) will have the reverse order of the coefficients. Using these results we can to determine that A(x) is not divided exactly into B(x) without ending division. It allows us to reduce the division time. The second algorithm is based on properties of cyclic codes and a generating matrix in its systematic form. It allows us to compute a remainder from division of the dividend by the generating polynomial in one step. The dividend is represented in a parallel code.