A new division algorithm based on lookahead of partial-remainder(LAPR) for high-speed/low-power coding applications

摘要

A new polynomial division algorithm in finite field GF(2mn) based on the lookahead of partial-remainder (LAPR) is proposed.nSince our algorithm is based on partial division on group basis andnlookahead technique exploiting the linearity in finite field arithmetic,nit is possible to completely eliminate polynomial multiplicationsnleading to highly increased throughput per unit time. The inherentnregularity and feedforward nature of our algorithm make it possible tonbe fully pipelined. When pipelined, its throughput is one quotient andnone remainder per clock cycle, regardless of the degree of dividendnpolynomial, which is orders of magnitude faster than the conventionalnarchitecture using linear feedback shift register. An area-efficientnsequential architecture based on LAPR is also presented, Although thenthroughput rate of sequential architecture is lower than that of thenpipelined one, it is still higher than that of any division architecturenever reported. They are shown to be efficient, regular, and easilynexpandable, and hence, naturally suitable for very large scalenintegration implementation. In systems requiring modest speed, thenhigh-speed nature of our proposed architecture can be traded for lownpower consumption by reducing clock rate. We verified the generalnvalidity of the division algorithm based on LAPR by mathematicalnmanipulation and simulation. The superiority of our proposednarchitecture compared with other reported ones is demonstrated withnregard to its throughput, latency delays, and power