Architectures for exponentiation in GF(2m)

Several VLSI architectures for performing exponentiation in GF(2 ^m) are presented. Two approaches to the architecture design are taken. In the first, all intermediate products of the exponentiation are computed in a sequential fashion to minimize the silicon area. In the second approach, all values of raised to the 2^ei power, O⩽i⩽m-1, are precomputed and stored so that the intermediate product terms can be calculated in a parallel fashion. For the two approaches, both synchronous and asynchronous implementations are presented using standard and normal bases. The discussion emphasizes the design and performance tradeoffs incurred in developing such architectures     

Bit-serial Berlekamp-like multipliers for GF(2m)

A bit-serial multiplier for GF(2^m) is presented. This multiplier operates in a similar way to the traditional Berlekamp multiplier and has the same hardware requirements. However the format of the inputs to the proposed multiplier is different, and in some circumstances constant multipliers based on this approach can be clocked faster than those based on the traditional Berlekamp multiplier     

Complexity of the inversion in GF(2m)

The authors propose a method for increasing the speed of element inversion in GF(2^m). Simple modifications are made to the inverter scheme to directly enable the input to represent the element to be inverted     

A Fast VLSI Multiplier for GF(2m)

Multiplication in the finite fieldGF(2^{m}) has particular computational advantages in data encryption systems. This paper presents a new algorithm for performing fast multiplication inGF(2^{m}), which isO(m)in computation time and implementation area. The bit-slice architecture of a serial-in-serial-out modulo multiplier is described and the circuit details given. The design is highly regular, modular, and well-suited for VLSI implementation. The resulting multiplier will have application in algorithms based on arithmetic in large finite fields of characteristic 2, and which require high throughput.     

Improved normal basis inversion in GF(2m)

Recently, Fenn et al. (1996) developed a fast finite field inversion algorithm in GF(2^m) over the normal basis representation which uses about half the time complexity of traditional approaches. Further extensive improvement to this algorithm is presented here     

Novel Radix Finite Field Multiplier for GF(2m)

In this paper, a new High-Radix Finite Field multiplication algorithm for GF(2^m) is proposed for the first time. The proposed multiplication algorithm can operate in a Digit-serial fashion, and hence can give a trade-off between the speed, the area , the input/output pin limitation, and the low power consumption by simply varying the digit size. A detailed example of a new Radix-16 GF(2^m) Digit-Serial multiplication architecture adopting the proposed algorithm illustrates a speed improvement of 75% when compared to conventional Radix-2 bit-serial realization. This is made more significant when it is noted that the speed improvement of 75% was achieved at the expense of only 2.3 times increase in the hardware requirements of the proposed architecture.     

Squaring architecture for GF(2m) and its applications incryptographic systems

A squaring architecture for standard basis field representation is presented. The architecture is based on the observation that a squaring operation in GF(2^m) can be transformed into an addition and a multiplication of two elements of special form, the computational time of which depends on the form of the field polynomial     

A simple decoding of BCH codes over GF(2m)

A simple decoding method for even minimum-distance Bose-Chaudhuri-Hochquenghem (BCH) codes is proposed. In the method the coefficients of an error locator polynomial are given as simple determinants (named Q determinants) composed of syndromes. The error evaluator is realized as a Q determinant divided by an error locator polynomial. The Q determinants can be efficiently obtained with very simple calculations on syndromes enabling the realization of a high-speed decoder of simple configuration. The number of calculations in obtaining the error locator and the error evaluator with the proposed method is smaller than that with the widely used Berlekamp-Massey algorithm when the number of correctable errors of the code is five or less. The proposed method can also be applied to the binary narrow-sense BCH codes of odd minimum distance     

Quantum codes from cyclic codes over GF(4m)

We provide a construction for quantum codes (Hermitian-self-orthogonal codes over GF(4)) starting from cyclic codes over GF(4^m). We also provide examples of these codes some of which meet the known bounds for quantum codes     

Concurrent error detection in array multipliers forGF(2m) fields

Based on Lee-Lu-Lee's array multipliers and the RESO method, a concurrent error detection scheme in array multipliers for GF(2^m ) fields is presented and only one clock cycle is added. The fault tolerant capability in such array multipliers is also included and only two extra clock cycles are required     

SIGMA: a VLSI systolic array implementation of a Galois field GF(2m) based multiplication and division algorithm

Finite or Galois fields are used in numerous applications like error correcting codes, digital signal processing and cryptography. The design of efficient methods for Galois field arithmetic such as multiplication and division is critical for these applications. A new algorithm based on a pattern matching technique for computing multiplication and division in GF(2^m) is presented. An efficient systolic architecture is described for implementing the algorithm which can produce a new result every clock cycle and the multiplication and division operations can be interleaved. The architecture has been implemented using 2-μm CMOS technology. The chip yields a computational rate of 33.3 million multiplications/divisions per second     

Appropriate (CR)m-(RC)n shaping for fastbipolar front-end read-out

The author presents a study of the influence of the order, n and m, of a (CR)^m-(RC)ⁿ shaper on the signal-to-noise, S/N, ratio of a read-out system, subject to input referred f² noise emitted by the bipolar input transistor. As a function of n and m, normalised equivalent noise charges, ENC(n, n), are calculated. Conclusions and some guidelines for filter design are derived from the data obtained     

Fault-Tolerant Bit-Parallel Multiplier for Polynomial Basis of GF(2m)

Novel fault-tolerant architectures for bit-parallel polynomial basis multiplier over GF(2m), which can correct the erroneous outputs using linear code, are presented. A parity prediction circuit based on the code generator polynomial that leads lower space overhead has been designed. For bit-parallel architectures, the space overhead is about 11%. Moreover, there is only marginal time overhead due to incorporation of error-correction capability that amounts to 3.5% in case of the bit-parallel multiplier. Unlike the existing concurrent error correction (CEC) multipliers or triple modular redundancy (TMR) techniques for single error correction, the proposed architectures have multiple error-correcting capabilities.     

FHT algorithm for length N=q.2m

Of late, the discrete Hartley transform (DHT) has become an important real-valued transform. Many fast algorithms for computing the DHT of sequence length N=2^m have been reported. Fast computation of the DHT of length N=q.2^m, where q is an odd integer, is proposed. The key feature of the algorithm is its flexibility in the choice of sequence length N, where N need not necessarily be a power of 2, while giving rise to a substantial reduction in computational complexity when compared to other algorithms     

Every binary (2m-2, 22(m)-2-m, 3) code can belengthened to form a perfect code of length 2m-1

We answer a problem posed by Etzion and Vardy (1998) by showing that a binary code of length N=2(m)-2 with 2(N-m) codewords and minimum distance three can always be lengthened to form a perfect code of length 2(m-1)     

Fast Bit Parallel-Shifted Polynomial Basis Multipliers in GF(2n)

A new nonpipelined bit-parallel-shifted polynomial basis multiplier for GF(2ⁿ) is presented. For some irreducible trinomials, the space complexity of the multiplier matches the best results available in the literature, and its gate delay is equal to T _A+lceillog₂nrceilT_X, where T_A and T_X are the delay of one two-input and and xor gates, respectively. To the best of our knowledge, this is the first time that the gate delay bound T_A+lceillog₂nrceilT_X is reached. For some irreducible pentanomials, its gate delay is equal to T_A +(1+lceillog₂nrceil)T_X. NIST has recommended five binary fields for the elliptic curve digital signature algorithm applications: GF(2¹⁶³), GF(2²³³), GF(2 ²⁸³), GF(2⁴⁰⁹), and GF(2⁵⁷¹), but no irreducible trinomials exist for three degrees, viz., 163, 283 and 571. For the three corresponding binary fields, we show that the gate delay of the proposed multiplier is T_A+(1+lceillog₂nrceil)T_X. This result outperforms the previously known results     

Effective recursive algorithm for computing multiplicative inversesin GF(2m)

Presents an effective recursive algorithm for computing multiplicative inverses in GF(2^m), where m=2^k, employing normal bases. The proposed algorithm requires m-1 cyclic shifts and two multiplications in GF (2^m) and in each subfield of GF(2^m): GF(2^m/2), GF(2^m/4),. . ., GF (2⁸) and GF(2⁴)     

基于滑动窗口技术的有限域GF(2n)乘法算法

在分析现有有限域GF(2n)乘法算法的基础上,将滑动窗口技术应用到有限域GF(2n)的乘法运算中,提出了一个基于滑动窗口技术的有限域GF(2n)乘法算法,分析和仿真结果表明,与被认为目前最快的有限域GF(2n)乘法算法一固定窗口算法相比,该算法有更好的实现效率.     

Synthesis and uniqueness of m-sequences over GF(qn) asn-phase sequences over GF(q)

The construction of m-sequences over GF(qⁿ) from known m-sequences over GF(q) is discussed. An algorithm is given which generates m-sequences over GF(qⁿ) from m-sequences over GF(q), where n phase shifts of known m-sequences over GF(q) are determined by the iterative polynomials. It is shown that n shift distinct m-sequences over GF(qⁿ) generated by the same m-sequences over GF(q) are unique when the elements of GF(qⁿ) are represented by n-tuples of the elements from GF(q)     

A digit-serial multiplier for finite field GF(2/sup m/)

In this paper, an efficient digit-serial systolic array is proposed for multiplication in finite field GF(2/sup m/) using the standard basis representation. From the least significant bit first multiplication algorithm, we obtain a new dependence graph and design an efficient digit-serial systolic multiplier. If input data come in continuously, the proposed array can produce multiplication results at a rate of one every /spl lceil/m/L/spl rceil/ clock cycles, where L is the selected digit size. Analysis shows that the computational delay time of the proposed architecture is significantly less than the previously proposed digit-serial systolic multiplier. Furthermore, since the new architecture has the features of regularity, modularity, and unidirectional data flow, it is well suited to VLSI implementation.