Improved algorithm for division over GF(2/sup m/)

An improved algorithm for division over GF(2/sup m/) is proposed. It is based on a look-ahead procedure that allows division over GF(2/sup m/) to be performed in any number of clock cycles up to 2/sup m/-1. The hardware complexity of the divider depends on the level of look-ahead chosen and hence the speed of operation required. An example using this divider in solving the key equation for single-error correcting Reed-Solomon codes is also considered.<>     

Lehmer-based algorithm for computing inverses in Galois fields GF(2/sup m/)

An algorithm for computing multiplicative inverses in Galois fields GF(2/sup m/) is presented. It is based on Lehmer's algorithm for computing the greatest common divisor of two integers. The algorithm is designed to be advantageous for Galois fields of large size.     

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.     

Fast algorithms for determining the linear complexity of sequences over GF(p/sup m/) with period 2/sup t/n

We prove a result which reduces the computation of the linear complexity of a sequence over GF(p^m) (p is an odd prime) with period 2n (n is a positive integer such that there exists an element bisinGF(p^m), bⁿ=-1) to the computation of the linear complexities of two sequences with period n. By combining with some known algorithms such as the Berlekamp-Massey algorithm and the Games-Chan algorithm we can determine the linear complexity of any sequence over GF(p^m) with period 2^tn (such that 2 ^t|p^m-1 and gcd(n,p^m-1)=1) more efficiently     

Hybrid multiplier for GF(2/sup m/) defined by some irreducible trinomials

A trade-off between performance and area is important to design an efficient hardware structure for arithmetic operations in GF(2/sup m/). Proposed is a hybrid multiplier for GF(2/sup m/) with an irreducible trinomial, which can be constructed in variable structures depending on such a performance area trade-off.     

Design of flexible GF(2/sup m/) elliptic curve cryptography processors

The design of flexible elliptic curve cryptography processors (ECP) is considered in this paper. Novel word-level algorithms and implementations for the underlying GF(2/sup m/) multiplication and squaring arithmetic which enable improved flexibility versus performance tradeoffs, are presented and employed in the design of an efficient flexible ECP architecture; corresponding field-programmable gate-array (FPGA) prototyping results for two different processor word lengths are also included for evaluation.     

Normal basis multiplication algorithm for GF(2/sup n/)

A normal basis multiplication algorithm is presented. Its complexity depends on the multiplicative order of the normal element.     

Class of shortened cyclic codes over GF(2/sup 8/) for byte-oriented systems

The author proposes shortened cyclic codes over GF(2/sup 8/), designed to provide additional error protection from both random as well as burst errors, for data consisting of 8-bit bytes, all having even (or odd) parity (e.g. ASCII characters). A specific code of length 29 bytes is described in detail.<>     

Algorithm for unified modular division in GF(p) and GF(2/sup n/) suitable for cryptographic hardware

A unified algorithm to compute modular division in both GF(p) and GF(2/sup n/) fields is presented. It uses a counter variable to keep track of the difference between two field elements, and in this way eliminates the need for comparisons which are usually expensive and time-consuming. The computations in both fields are performed using additions/subtractions and bit shifts, besides using a simple control flow, which makes it suitable for hardware implementation.     

Linear time encoding of cycle GF(2/sup p/) codes through graph analysis

In this letter, we present a linear-complexity encoding algorithm for any cycle GF(2/sup P/) code C/sub E/(G,H). We just need to investigate the case where G is a nontrivial connected graph. If G is a tree, the only codeword is the all-zero word. If G is not a tree, first, we show that through graph analysis H can be transformed into an equivalent block-diagonal upper-triangular form simply by permuting the rows and columns of H; then, we show that whether H is full row-rank or not, the code can be encoded in linear time.     

Low complexity bit-parallel normal bases multipliers for GF(2/sup n/)

Based on the divide-and-conquer technique, three bit-parallel normal bases multipliers are presented for GF(2/sup n/). The space complexity of one multiplier is about 3/4 of the smallest known normal bases multiplier, although it needs at most one more XOR gate delay.     

Fast transform for decoding both errors and erasures of Reed-Solomon codes over GF(2/sup m/) for 8/spl les/m/spl les/10

In this letter, it is shown that a fast, prime-factor discrete Fourier transform (DFT) algorithm can be modified to compute Fourier-like transforms of long sequences of 2/sup m/-1 points over GF(2/sup m/), where 8/spl les/m/spl les/10. Using these transforms, together with the Berlekamp-Massey algorithm, the complexity of the transform-domain decoder for correcting both errors and erasures of the Reed-Solomon codes of block length 2/sup m/-1 over GF(2/sup m/) for 8/spl les/m/spl les/10 is reduced substantially from the previous time-domain decoder. A computer simulation verifies these new results.     

Compression mappings on primitive sequences over Z/(p/sup e/)

Let Z/(p/sup e/) be the integer residue ring with odd prime p/spl ges/5 and integer e/spl ges/2. For a sequence a_ over Z/(p/sup e/), there is a unique p-adic expansion a_=a_/sub 0/+a_/spl middot/p+...+a_/sub e-1//spl middot/p/sup e-1/, where each a_/sub i/ is a sequence over {0,1,...,p-1}, and can be regarded as a sequence over the finite field GF(p) naturally. Let f(x) be a primitive polynomial over Z/(p/sup e/), and G'(f(x),p/sup e/) the set of all primitive sequences generated by f(x) over Z/(p/sup e/). Set /spl phi//sub e-1/ (x/sub 0/,...,x/sub e-1/) = x/sub e-1//sup k/ + /spl eta//sub e-2,1/(x/sub 0/, x/sub 1/,...,x/sub e-2/) /spl psi//sub e-1/(x/sub 0/,...,x/sub e-1/) = x/sub e-1//sup k/ + /spl eta//sub e-2,2/(x/sub 0/,x/sub 1/,...,x/sub e-2/) where /spl eta//sub e-2,1/ and /spl eta//sub e-2,2/ are arbitrary functions of e-1 variables over GF(p) and 2/spl les/k/spl les/p-1. Then the compression mapping /spl phi//sub e-1/:{G'(f(x),p/sup e/) /spl rarr/ GF(p)/sup /spl infin// a_ /spl rarr/ /spl phi//sub e-1/(a_/sub 0/,...,a_/sub e-1/) is injective, that is, a_ = b_ if and only if /spl phi//sub e-1/(a_/sub 0/,...,a_/sub e-1/) = /spl phi//sub e-1/(b_/sub 0/,...,b_/sub e-1/) for a_,b_ /spl isin/ G'(f(x),p/sup e/). Furthermore, if f(x) is a strongly primitive polynomial over Z/(p/sup e/), then /spl phi//sub e-1/(a_/sub 0/,...,a_/sub e-1/) = /spl psi//sub e-1/(b_/sub 0/,...,b_/sub e-1/) if and only if a_ = b_ and /spl phi//sub e-1/(x/sub 0/,...,x/sub e-1/) = /spl psi//sub e-1/(x/sub 0/,...,x/sub e-1/) for a_,b_ /spl isin/ G'(f(x),p/sup e/).     

On binary images of shortened cyclic (8, 5) codes over GF(2/sup 8/)

We have generated binary images of a large number of shortened cyclic (8, 5) codes over GF(2/sup 8/) and have computed weight distributions of the binary images of the codes. Based on the weight distributions, we have chosen four codes with the largest minimum weight 8 and the second largest minimum weight 7 among the generated codes. Over an additive white Gaussian noise channel with binary phase-shift keying modulation, simulation results have shown that block error rates of the chosen codes by a soft-decision decoding based on order-2 reprocessing are smaller than those of (64, 40) subcodes of Reed-Muller (64, 42) code by maximum likelihood decoding.     

Cyclic codes over GR(4/sup m/) which are also cyclic over /spl Zopf//sub 4/

Let GR(4/sup m/) be the Galois ring of characteristic 4 and cardinality 4/sup m/, and /spl alpha/_={/spl alpha//sub 0/,/spl alpha//sub 1/,...,/spl alpha//sub m-1/} be a basis of GR(4/sup m/) over /spl Zopf//sub 4/ when we regard GR(4/sup m/) as a free /spl Zopf//sub 4/-module of rank m. Define the map d/sub /spl alpha/_/ from GR(4/sup m/)[z]/(z/sup n/-1) into /spl Zopf//sub 4/[z]/(z/sup mn/-1) by d/spl alpha/_(a(z))=/spl Sigma//sub i=0//sup m-1//spl Sigma//sub j=0//sup n-1/a/sub ij/z/sup mj+i/ where a(z)=/spl Sigma//sub j=0//sup n-1/a/sub j/z/sup j/ and a/sub j/=/spl Sigma//sub i=0//sup m-1/a/sub ij//spl alpha//sub i/, a/sub ij//spl isin//spl Zopf//sub 4/. Then, for any linear code C of length n over GR(4/sup m/), its image d/sub /spl alpha/_/(C) is a /spl Zopf//sub 4/-linear code of length mn. In this article, for n and m being odd integers, it is determined all pairs (/spl alpha/_,C) such that d/sub /spl alpha/_/(C) is /spl Zopf//sub 4/-cyclic, where /spl alpha/_ is a basis of GR(4/sup m/) over /spl Zopf//sub 4/, and C is a cyclic code of length n over GR(4/sup m/).     

BiCMOS nonthreshold logic for high-speed low-power applications

New high-speed low-power BiCMOS nonthreshold logic (BNTL) circuits are presented. These circuits offers a built-in CMOS and bipolar level conversion and are suitable for reduced power supply voltage. A 4-b carry lookahead generator (CLG) circuit is designed in BNTL, ECL, and CMOS using 0.8-μm BiCMOS technology. Circuit simulations show that this new logic provides speed comparable to or better than that provided by emitter-coupled logic (ECL) for lower power dissipation     

An efficient reconfigurable multiplier architecture for Galois field GF(2)

This paper describes an efficient architecture of a reconfigurable bit-serial polynomial basis multiplier for Galois field GF(2^m), where 1<m≤M. The value m, of the irreducible polynomial degree, can be changed and so, can be configured and programmed. The value of M determines the maximum size that the multiplier can support. The advantages of the proposed architecture are (i) the high order of flexibility, which allows an easy configuration for different field sizes, and (ii) the low hardware complexity, which results in small area. By using the gated clock technique, significant reduction of the total multiplier power consumption is achieved.     

A fast algorithm for determining the minimal polynomial where of a sequence with period 2p/sup n/ over GF (q)

A fast algorithm is presented for determining the linear complexity and the minimal polynomial of a sequence with period 2p/sup n/ over GF (q), where p and q are odd prime, and q is a primitive root (mod p/sup 2/). The algorithm uses the fact that in this case the factorization of x/sup 2p(n)/-1 is especially simple.     

Algorithm and architecture for a Galois field multiplicative arithmetic processor

We present a new algorithm for generic multiplicative computations of the form ab/c in GF(p/sup m/), including multiplication, inversion, squaring, and division. The algorithm is based on solving a sequence of congruences that are derived from the theory of Grobner bases in modules over the polynomial ring GF(p)[x]. Its corresponding hardware and software architectures can be successfully used in applications such as error control coding and cryptography. We describe a versatile circuit associated with the algorithm for the most important case p=2. The same hardware can be used for a range of field sizes thus permitting applications in which different levels of error control or of security are required by different classes of user. The operations listed are all performed by the hardware in the same number of clock cycles, which prevents certain side-channel attacks. The loss in performance by having 2m iterations for multiplication is compensated by the full parameterization of the Galois field and the ability to perform division and multiplication in parallel.