Haixia Wu， Yilong Bai， Tian Wang， Xiaoran Li and Long He

（School of Information and Electronics, Beijing Institute of Technology, Beijing 100081, China）

Abstract: In order to improve the circuit complexity and reduce the long latency of B –1 operations,a novel B –1 operation in Galois Field GF(24) is presented and the corresponding systolic realization based on multiple-valued logic (MVL) is proposed. The systolic structure employs multiplevalued current mode (MVCM) by using dynamic source-coupled logic (SCL) to reduce the initial delay and the transistor and wire counts. The performance is evaluated by HSPICE simulation in 0.18 μm CMOS technology and a comparison is conducted between our proposed implementation and those reported in the literature. The initial delay and the sum of transistors and wires in our MVL design are about 43% and 13% lower, respectively, in comparison with other corresponding binary CMOS implementations. The systolic architecture proposed is simple, regular, and modular,well suited for very large scale integration (VLSI) implementations. The combination of MVCM circuits and relevant algorithms based on MVL seems to be a potential solution for high performance arithmetic operations in GF(2k).

Key words: multiple-valued logic (MVL)；systolic B –1 circuit；Galois Fields

Finite field arithmetic plays an important role in fields such as cryptography, error correction coding, and digital signal processing. For most applications, very large scale integration(VLSI) implementation is necessary in order to meet the requirements of area, speed and safety.To a great extent, the efficiency of these applications depends on the efficiency of arithmetic in a finite field. Therefore, it is crucial to develop effective algorithms in finite fields and to effective VLSI implementations. Effective algorithms and efficient hardware structures for such operations are desirable[1?8]. Compared with binary logic,multiple-valued logic (MVL) has more than two logic states, so MVL integrated circuits can be expected to reduce the number of wires and the number of devices in arithmetic and logic systems[9?11]. This article mainly discusses how to operateB?1using MVL, and how to improve the performance of the arithmetic unit in Galois Fields. The quaternary algorithm ofB?1, its systolic quaternary circuits with dynamic current-mode multiple-valued circuitry, and the final performance are presented in this manuscript.

1 Relationship Between the Quaternary and Galois Fields

Field elements for a certainkin GF(2k) are distinct for a certain irreducible polynomial. Let GF(2k) denote the binary extension field defined over the prime field GF(2). In order to construct GF(2k) and to represent its elements, a primitive elementaand an irreducible polynomial of degreekwhose coefficients are in GF(2k)are needed. It is possible to derive different representations by defining GF(2k) over the field

2 Quaternary Multiplier and Adder in GF(4)

MVL circuits can be roughly classified into two categories: current-mode and voltage-mode.The multiple-valued current-mode (MVCM) circuits based on dynamic source-coupled logic(SCL) are applied for the proposed design. A MVCM circuit consists of three basic components: a comparator, an output generator, and a linear summation circuit. In the comparator, the input quaternary signalA0is compared with a threshold value, and a binary differential output(a0a0') will be generated. Then, the binary differential signals will be transmitted as the input signals of the output generator to control the generation of the output signals. Without any active devices, the linear summation can be performed simply by wiring the two branches. In this way,the final output is quaternary current signals[9?11].So the design of the output generator is the key part for a MVCM circuit based on SCL. The circuit diagrams of the output generator of the proposed quaternary multiplier in GF(4) and the quaternary adder are shown in Fig.1 and Fig.2,respectively. Further details can be found in Ref.[9]. The two modules can be represented as the two symbols shown in Fig. 3, respectively.

Fig. 1 Output generator circuit diagram of the quaternary multiplier

Fig. 2 Output generator circuit diagram of the quaternary adder

Fig. 3 Multiplier and adder symbols

3 Algorithm of B –1 in Galois Fields

4 Quaternary B –1 Operations in Galois Fields

5 Evaluations

The design is evaluated with 0.18 μm CMOS technology with 1.8 V supply voltage. Fig.5 shows the input and the output waveforms of the simulation with the period of the clock being 10 ns.Tab.4 shows the sequence analysis of the output under such a set of the input, thenth output is obtained after (n+13) clock periods, and these outputs are correct according to the operation rules. Tab.5 shows the voltage swing corresponding to multiple logic value in proposed implementation. Tab.6 shows the performance comparison with other corresponding CMOS implementations.

Fig. 4 Quaternary B–1 systolic circuit in GF((22)2)

Fig. 5 Waveforms of the input and output for B –1

Tab. 4 Sequence analysis of the simulation data for B –1

Tab. 5 Voltage swing corresponding to quaternary logic and binary logic

6 Conclusion

In this paper, a quaternaryB–1operation in GF(24) is presented, and its systolic realization is based on MVCM are proposed. The design of the systolic circuit employs dynamic source-coupled logic (SCL) to reduce the device and interconnection counts, and to improve the speed. The performance is evaluated by an HSPICE simulation with 0.18 μm CMOS technology, and a comparison is conducted between our proposed implementation and those reported in the literature.The simulation shows that the initial delay and the sum of the transistors and wires in our MVL design are 13 clocks and 20 722, about 43% and 13% lower, respectively, in comparison with the corresponding binary CMOS implementation, although there is not an obvious improvement compared to the design based on multiple valued voltage mode (MVVM) by using the neuron MOSFET proposed in Ref.[12]. The systolic architecture in our design is simple, regular, and modular, suitable for VLSI implementation, and

can be easily applied as a basic unit in arithmetic-processor chip design for cryptography, error correction coding, switching-theory, digital signal processing, and more. The combination of MVCM circuits and relevant algorithms based on MVL seems to be a potential solution for high performance arithmetic operations in GF(2k).Noise has always been a concern of multi-valued logic. As a future research work, it is crucial to eliminate noise or optimize noise margin and to reduce static power dissipation while maintaining high speed operation. If these problems are successfully solved, multiple-valued logic will become a reality approach for high performance arithmetic VLSI systems.

Tab. 6 Comparison of B?1 in GF(24)