DESIGN OF WORD LEVEL MULTIPLICATION ALGORITHM ON REORDERED NORMAL BASIS
G. Yuvaraj · 2012
Normal basis is widely used for representation of binary field elements Much attention has been paid to trade off between time and number of gates, but until little attention has been paid to the problem of connecting the gates in economical and regular way to minimize chip and chip area and design costs. Two new level high speed architectures, reordered normal basis type-I and reordered normal basis type-II for binary field multiplication are proposed. It allows the designer to trade off between area and speed. Optimal normal basis type-II is a special class of exhibiting very low multiplication complexity. Reordered normal basis is referred to as a certain permutation of optimal normal basis. One unique feature of the proposed architectures is that the critical path delay is independent of the number of words or the field size. This enables the proposed multipliers to operate at very high clock rates regardless of the number of words or the field size. Arithmetic operations in the Galois field GF(2 m ) have several applications in coding theory, computer algebra and cryptography. Several algorithms for basic arithmetic operations in finite fields are suitable for both hardware and software implementations have been recently developed. The applications of these algorithms are found in error-correcting codes and public key cryptography. The proposed algorithms are suitable for obtaining high speed implementations of the field operations on signal processors and microprocessors. The efficient implementation of multipliers plays a major rule in system performance. Two bases are commonly used in practice they are polynomial basis and normal basis. Optimal normal basis (ONB) type-I and type-II are two special classes of normal basis for which the complexity of multiplication is minimized. ONB type-II has been recommended and widely used for the design of arithmetic with cryptographic applications. Reordered normal basis is a reordered version of an ONB type-II and was initially proposed in the 1994. Later, this basis was used to create efficient ONB type-II multipliers in the 2001. One advantage of the normal basis is that the squaring of an element is computed by a cyclic shift of the binary representation. For binary field multiplication three types of architectures are present: bit level, fully parallel, and word level. The bit level and fully parallel architectures represent extreme design styles while word level architectures fill the gap between the two extremes and allow the designer to set the trade-off between the area and speed. Bit serial multiplier needs m number of more flip-flops than the word level multipliers as the serial output needs to be stored because of word level multipliers does not independent of the number of words.