Page 235 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Polynomial Bases 215

has 1s in the t + 1 columns 0, k , k , . . . , k . The consecutive rows of P
1 2 t
can be obtained by using a linear feedback shift register and thus the
number of 1s in rows from 0 to m – k – 1 is equal to t + 1, corresponding
t
to the t + 1 segmented lines. This fact can be observed, for example,
in the matrices P given in Figs. 7.11 and 7.12 for trinomials. The last
column of P contains 1 in rows i = m – k – 1, with j = t, . . . , 2, 1. When
j
a row ends with a 1, the following row originates new lines in
columns 0, k , k , . . . , k , if there are no previous lines that pass these
1 2 t
columns [RH04]. If there exists a previous line that passes the column
of k , 1 ≤ j ≤ t, then the previous line terminates in the column k − 1
j j
and no new line originates from column k due to the XOR of two
j
lines. This fact can be observed in row s and columns s, . . . , m – s in
Fig. 7.9 for an s-ESP.
If the lines of matrix P are divided into t + 1 sets, then P can be
decomposed in a sum of matrices P = P + P + . . . + P where the
0 1 t
entries are different from 0 of P , 0 ≤ i ≤ t start from column k , assum-
i i
ing that k = 0 [RH04]. The graphical representations of the matrices
0
P , P , P , and P for pentanomials fx () = x + x + x + x + 1 , 1 ≤
m
k
k
k
2
1
3
0 1 2 3
k < k < k ≤ m/2 are shown in Fig. 7.10.
1 2 3

(a) (b)

(c) (d)
FIGURE 7.10 Submatrices of P = P + P + P + P for pentanomials f(x) = x m
0 1 2 3
k
k
k
+ x 3 + x 2 + x 1 +1, for 1 ≤ k < k < k ≤ m/2. (a) P , (b) P , (c) P , (d) P .
1 2 3 0 1 2 3