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

Abstract

A nem polynomial division algorithm in finite field GF(2(m)) based on the lookahead of partial-remainder (LAPR) is proposed. Since our algorithm is based on partial division on group basis and lookahead technique exploiting the linearity in finite field arithmetic, it is possible to completely eliminate polynomial multiplications leading to highly increased throughput per unit time. The inherent regularity and feedforward nature of our algorithm make it possible to be fully pipelined, When pipelined, its throughput is one quotient and one remainder per clock cycle, regardless of the degree of dividend polynomial, which is orders of magnitude faster than the conventional architecture using linear feedback shift register. An area-efficient sequential architecture based on LAPR is also presented. Although the throughput rate of sequential architecture is lower than that of the pipelined one, it is still higher than that of any division architecture ever reported. Those will be shown to be efficient, regular, and easily expandable, and hence, naturally suitable for very large scale integration implementation. In systems requiring modest speed, the high-speed nature of our proposed architecture can be traded for low-power consumption by reducing clock rate. We verified the general validity of the division algorithm based on LAPR bg mathematical manipulation and simulation. The superiority of our proposed architecture compared with other reported ones is demonstrated,vith regard to its throughput, latency delays, and power.