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     

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     

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     

Massey-Omura type adder for elements of finite fields GF(2m) in logarithmic representation

The multiplication, inversion, division and exponentiation of elements of GF(2^m) are easily implemented with conventional arithmetic and logical units when the elements are in the logarithmic representation. An electronic architecture for the addition of two elements in the logarithmic representation is presented. The architecture of the adder is similar to that of the Massey-Omura multiplier for the normal basis representation. In particular, the same combinatorial circuit is used to successively compute every bit of the sum     

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     

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.     

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.     

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     

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     

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     

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     

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)     

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     

Concurrent error detection architectures for Gaussian normal basis multiplication over GF(2)

This paper presents a method of using a parity prediction scheme for detecting erroneous outputs in bit-parallel, sequential, and digit-serial Gaussian normal basis (GNB) multipliers over GF(2^m). Although all-type NB multipliers have different time and space complexities, our analytical results indicate that all-type GNB multipliers have the same structure if they use parity prediction function. For example, in the field GF(2²³³), we have estimated that the error detection rate for a sequential multiplier is nearly 100% if a comparison is made as per clock cycle. Our analytical results also show that the area overhead of the proposed digit-serial multiplier with concurrent error detection does not exceed 5%. Several efficient parity prediction techniques will be shown in this work to provide a low overhead solution to concurrent error detection particularly when the cryptography implementations using GF(2^m) multiplier require higher reliability and the protection against adversarial attacks.     

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     

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⁴)     

Concurrent error detection in highly structured logic arrays

Two strategies for encoding the inputs and outputs of highly structured logic arrays (HSLAs) are introduced. The two schemes are particularly relevant for concurrent error detection of both permanent and nonpermanent errors in programmable logic arrays (PLAs) and read-only memories (ROMs). The first method of concurrent error detection (CED) is based on a comprehensive fault model and relies on detection of unidirection errors. The second approach relies on a detailed examined of decoder layouts resulting in fault avoidance through layout rules, which avoid failures causing unidirectional errors. Efficient parity techniques are shown to provide a low-overhead solution to concurrent error detection when coupled with appropriate fault-avoidance techniques.     

Concurrent error detection and fault location in an FFTarchitecture

A new approach for concurrent error detection in a homogeneous architecture for the computation of the complex N-point fast Fourier transform (FFT) in radix-2 is presented. The proposed approach is based on the relationship between cell computations. It is proved that 100% probability of detection is possible. Overhead issues for hardware and timing are addressed. It is proved that hardware overhead for concurrent error detection is 50% compared to a fault-intolerant complex two-point implementation. A modest time overhead is encountered for error detection and fault location. Error detection can be accommodated online and on a component basis (multiplier or adder/subtractor): full fault location is accomplished by a roving technique. The proposed technique can be efficiently accommodated in a homogeneous layout. A two-phase reconfiguration policy for the proposed architecture is presented. It is proved that switching and routing overhead is modest, while reliability is significantly improved over previous approaches     

VLSI-based array dividers with concurrent error detection

An alternative design of VLSI-based array dividers with concurrent error detection by recomputing using partitioned architecture (REPA) is proposed. The basic concept is that the divider array can be divided into two identical parts and its operation can be completed by using one part through two iterative calculations. With two such parts, a concurrent error detection scheme can be designed by using a space redundancy approach, and the detecting action is achieved at each iteration. The design is better than previous designs, such as RESO and AL, in terms of area requirement, time penalty, fault model and error latency. Advanced analysis of m partitions is also included. The experimental results are attractive, especially for designs with application-specified trade-offs between speed performance and area cost.     

Public-key cryptosystem over ring Z[√-3]/(2m)

The author improves the public-key cryptosystem presented recently (see IEE Proc. E, vol.134, no.5, p.254-6, 1987) and designs a new method of compressing the data expansion