Low-complexity bit-parallel systolic multipliers over GF(2)

This paper presents new time-dependent and time-independent multiplication algorithms over finite fields GF(2^m) by employing an interleaved conventional multiplication and a folded technique. The proposed algorithm allows efficient realization of the bit-parallel systolic multipliers. The results show that the proposed time-independent multiplier saves about 54% space complexity as compared to other related multipliers for polynomial and dual bases of GF(2^m). The proposed architectures include the features of regularity, modularity and local interconnection. Accordingly, it is well suited for VLSI implementation.     

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)     

Exploit Network Coding Over GF(2 q ) for Multi-user Cooperative Wireless Networks

In this paper, we present a decode-and-forward network coded (DFNC) scheme over GF(2 ^q ) for the multi-user cooperative communication systems. In particular, we consider a cooperative network with m users transmitting independent packets to the same destination. These users form a cooperation set to help each other by using linear network coding. We propose a coding coefficients construction method which can efficiently reduce the transmission overhead from m(q + log₂ m) to m bits compared with conventional random network coding. Furthermore, we propose a novel decoding algorithm—credit-based updating algorithm in order to improve the solvability of decoding set of equations at the destination. The proposed decoding algorithm is combined with channel decoding and is applied on symbol-level. It can fully make use of the error recovery property of network coding while conventional decoding algorithms (e.g., Gaussian elimination) overlook it. We theoretically analyze the diversity performance in terms of information outage probability, and the results show that diversity order of m + 1 can be achieved for a m-user cooperation system. Moreover, we conduct extensive simulations to show that DFNC outperforms other transmission schemes in terms of symbol error rate and achieves higher diversity order. We also demonstrate that the proposed decoding algorithm provides significant performance gain over conventional decoding algorithm.     

On the dimension and minimum distance of BCH codes over GF(q)

In this paper, only narrow-sense primitive BCH codes over GF(q) are considered. A formula, that can be used in many cases, is first presented for computing the dimension of BCH codes. It improves the result given by MacWilliams and Sloane in 1977. A new method for finding the dimension of all types of BCH codes is proposed. In second part, it is proved that the BCH bound is the leader of some cyclotomic coset, and we guess that the minimum distance for any BCH code is also the leader of some cyclotomic coset. Supported by the National Natural Science Foundation of China     

Fountain Codes Over GF(q)

Binary fountain codes such as Luby transform codes are a class of erasure codes which have demonstrated an asymptotic performance close to the Shannon limit when decoded with the belief propagation algorithm. When these codes are generalized to GF(q) for q > 2, their performance approaches the Shannon limit much faster than the usual binary fountain codes. In this paper, we extend binary fountain codes to GF(q). In particular, we generalize binary Luby transform codes to GF(q) to develop a low complexity maximum likelihood decoder. The proposed codes have numerous advantages, including low coding overhead, low encoding and decoding complexity, and good performance over various message block lengths, making them practical for real‐time applications. Copyright © 2011 John Wiley & Sons, Ltd.     

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.     

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.     

GF(q)‐based precoding: information theoretical analysis and performance evaluation

In this paper, a new precoding scheme that is based on the operations in Galois field of size q = 2^m(GF(q)) is proposed. Generally, precoding is a processing technique at transmitters to match the input signal to the channel in order to achieve optimal channel capacity through fully utilizing space, time, and frequency diversity. Precoding schemes can be divided into two main categories: linear precoding and nonlinear precoding. It has been shown from an information theoretical aspect that both the linear and nonlinear precoding schemes can achieve the optimal channel capacity. Our proposed GF(q)‐based precoding scheme is a nonlinear precoding technique, and the idea originates from finite inputs of the modulated symbols. When representing the modulated symbols and the elements in precoding matrix with the finite elements in Galois field of size q, and applying the operations defined in GF(q), we can obtain the precoded symbols that contains information of the original symbols. Starting from binary symmetry channel to additive Gaussian white noise channels, we have demonstrated that the proposed GF(q)‐based precoding schemes can enhance the system mutual information when the original finite inputs are not uniformly distributed. In addition, inspired by the mutual information analysis in binary symmetry channel, we investigated the selection of the precoding matrix in GF(q)‐based precoding schemes. As mutual information indicates the information about the source carried by the symbols of the channel output, greater mutual information enables the receivers to recover more information about the original source. To further utilize the greater mutual information brought by the proposed GF(q)‐based precoding schemes, we proposed a novel‐receiving structure by exchanging soft information between the GF(q) decoding block and channel decoding block. Simulation results show that the proposed iterative receiver improves the system bit error rate performance by 1 and 2 dB at the bit error rate level of 10 ^− 6 with binary phase shift keying and quadrature phase shift keying modulations, respectively. Inspired by the encouraging results of greater mutual information and better bit error rate performance, we are convinced that the proposed GF(q)‐based precoding schemes can be extended to fading channels and multiple input–multiple output systems to further approach channel capacity. Copyright © 2016 John Wiley & Sons, Ltd.     

New Bit-Parallel Systolic Architectures for Computing Multiplication,Multiplicative Inversion and Division in GF(2<Superscript>m</Superscript>) Under Polynomial Basis and Normal Basis Representations

A new bit-parallel systolic multiplier over GF(2^m) under the polynomial basis and normal basis is proposed. This new circuit is constructed by m ² identical cells, each of which consists of one two-input AND gate, one three-input XOR gate and five 1-bit latches. Especially, the proposed architecture is without the basis conversion as compared to the well-known multipliers with the redundant representation. With this proposed multiplier, a parallel-in parallel-out systolic array has also been developed for computing inversion and division over GF(2^m). The proposed architectures are well suited to VLSI systems due to their regular interconnection pattern and modular structure.

GF(2n)域上的一种Ⅱ型优化正规基乘法器及其FPGA实现

有限域GF(2ⁿ)上的椭圆曲线密码体制以其密钥短,安全强度高的优点正在获得广泛的重视和应用.该密码体制最主要的运算是有限域上的乘法运算.本文提出了一种基于Ⅱ型优化正规基的乘法器,该乘法器具有Massey-Omura乘法器的优点,又避免了其不足,易于编程,适合FPGA实现.实验表明,该算法简单,快速.     

有限域GF (2m)上的一个新的求逆算法

根据有限域GF(2^m)上的正规基表示和Massey-Omura乘法器,本文提出了一个复杂性为O(logm)的求逆算法。新算法完成一次求逆运算只需要[log₂(m-1)]+w(m-1)-1次乘法和m-1次循环移位,这里[x]表示小于等于x的最大整数,w(m-1)表示m-1的二进制表示中“1”的个数。     

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.     

Design and Implementation of a Polynomial Basis Multiplier Architecture Over GF(2m)

In this paper, the design and circuit implementation of a polynomial basis multiplier architecture over Galois Fields GF(2^m) is presented. The proposed architecture supports field multiplication of two m-term polynomials where m is a positive integer. Circuit implementations based on this parameterized architecture where m is configurable is suitable for applications in error control coding and cryptography. The proposed architecture offers low latency, polynomial basis multiplication where the irreducible polynomial P(x)?=?x ^m ?+?p _kt .?x ^kt ?+?…?+?p ₁.?x?+?1 with m ≥ kt + 4 is dynamically reconfigurable. Results of the complexity analysis show that the proposed architecture requires less logic resources compared to existing sequential polynomial basis multipliers. In terms of timing performance, the proposed architecture has a latency of m/4, which is the lowest among the multipliers found in literature for GF(2^m).     

On the mean value and variance of distance distribution of non-linear codes in GF(q)

This paper presents the lower bounds and upper bounds for the mean value and variance of distance distribution of non-linear codes in GF(q). By presenting several examples, it is shown that these bounds could be achieved.     

Low-density parity check codes over GF(q)

Gallager's (1962) low-density binary parity check codes have been shown to have near-Shannon limit performance when decoded using a probabilistic decoding algorithm. We report the empirical results of error-correction using the analogous codes over GF(q) for q>2, with binary symmetric channels and binary Gaussian channels. We find a significant improvement over the performance of the binary codes, including a rate 1/4 code with bit error probability <10^-5 at E_b/N₀=0.2 dB     

An Efficient Look-up Table-based Approach for Multiplication over GF(2 m ) Generated by Trinomials

In this paper, we present an efficient look-up table (LUT)-based approach to design multipliers for GF(2 ^m ) generated by irreducible trinomials. A straightforward LUT-based multiplication requires a table of size (m×2 ^m ) bits for the Galois field of degree m. The LUT size, therefore, becomes quite large for the fields of large degrees recommended by the National Institute of Standards and Technology (NIST). Keeping that in view, we have proposed a digit-serial LUT-based design, where operand bits are grouped into digits of fixed width, and multiplication is performed in serial/parallel manner. We restrict the digit size to 4 to store only 16 words in the LUT to have lower area-delay complexity. We have also proposed a digit-parallel LUT-based design for high-speed applications, using the same LUT as the digit-serial design, at the cost of some additional multiplexors and combinational logic for parallel modular reductions and additions. We have presented a simple circuit for the initialization of LUT content, which can be used to update the LUT in three cycles whenever required. The proposed digit-serial design involves less area-complexity and less time-complexity than those of the existing LUT-based designs. The proposed digit-parallel design offers nearly 28 % improvement in area-delay product over the best of the existing LUT-based designs. NIST has recommended five binary finite fields for elliptic curve cryptography, out of which two are generated by the trinomials Q(x)=x ²³³+x ⁷⁴+1 and Q(x)=x ⁴⁰⁹+x ⁸⁷+1. In this paper, we have designed a reconfigurable multiplier that can be used for both these fields. The proposed reconfigurable multiplier is shown to have a negligible reconfiguration overhead and would be useful for cryptographic applications.     

Low Power Semi-systolic Architectures for Polynomial-Basis Multiplication over GF(2m) Using Progressive Multiplier Reduction

We present low area and low power semi-systolic array architectures for polynomial basis multiplication over GF(2^m) using Progressive Multiplier Reduction Technique (PMR). These architectures are explored using linear and nonlinear techniques applied to the polynomial multiplication algorithm. The nonlinear techniques allow the designer, to control the processor workload and reduce the inter-processor communications. The semi-systolic architectures obtained have simple structure with local communication. ASIC implementations of our designs and comparable published designs show that the proposed scalable semi-systolic structures have less area complexity (56.8–94.6 %) and power consumption (55.2–84.2 %) except for a scalable design published by the same authors. However, one of the proposed scalable designs outperforms this design in terms of throughput by 73.8 %. This makes the proposed designs suited to embedded applications that require low power consumption and moderate speed.     

Improved Scalar Multiplication on Elliptic Curves Defined over F2mn

We propose two improved scalar multiplication methods on elliptic curves over F_qn where q = 2^m using Frobenius expansion. The scalar multiplication of elliptic curves defined over subfield F_q can be sped up by Frobenius expansion. Previous methods are restricted to the case of a small m. However, when m is small, it is hard to find curves having good cryptographic properties. Our methods are suitable for curves defined over medium‐sized fields, that is, 10 ≤ m ≤ 20. These methods are variants of the conventional multiple‐base binary (MBB) method combined with the window method. One of our methods is for a polynomial basis representation with software implementation, and the other is for a normal basis representation with hardware implementation. Our software experiment shows that it is about 10% faster than the MBB method, which also uses Frobenius expansion, and about 20% faster than the Montgomery method, which is the fastest general method in polynomial basis implementation.     

An efficient and high-speed VLSI implementation of optimal normal basis multiplication over GF(2m)

Finite field multiplication is one of the most important operations in the finite field arithmetic and the main and determining building block in terms of overall speed and area in public key cryptosystems. In this work, an efficient and high-speed VLSI implementation of the bit-serial, digit-serial and bit-parallel optimal normal basis multipliers with parallel-input serial-output (PISO) and parallel-input parallel-output (PIPO) structures are presented. Two general multipliers, namely, Massey–Omura (MO) and Reyhani Masoleh–Hassan (RMH) are considered as case study for implementation. These multipliers are constructed by using AND, XOR–AND and XOR tree components. In the MO multiplier, to have strong input signals and have a better implementation, the row of AND gates are implemented by using inverter and NOR components. Also the XOR–AND component in the RMH structure is implemented using a new low-cost structure. The XOR tree in both multipliers consists of a high number of logic stages and many inputs; therefore, to optimally decrease the delay and increase the drive ability of the circuit for different loads, the logical effort method is employed as an efficient method for sizing the transistors. The multipliers are first designed for different load capacitances using different structures and different number of stages. Then using the logical effort method and a new proposed 4-input XOR gate structure, the circuits are modified for acquiring minimum delay. Using 0.18 μm CMOS technology, the bit-serial, digit-serial and bit-parallel structures with type-1 and type-2 optimal normal basis are implemented over the finite fields GF(2²²⁶) and GF(2²³³) respectively. The results show that the proposed structures have better delay and area characteristics compared to previous designs.     

Fast algorithm for finding primitive polynomials over GF(q)

An efficient algorithm for the construction of primitive polynomials of degree m over GF(q) is proposed. The algorithm runs in time O(km/sup 2/), where k is an integer such that gcd (k,q/sup m-1/)=1.<>