|
For a linear feedback shift register (LFSR) of length L,
initial state s0, ..., sL - 1 ∈GF(q),
and connection polynomial
C(D) = 1 + c1 D + c2 D2 + ... + cL DL (also over GF(q)),
the j'th element of the sequence is computed as
sj = - ∑i=1L ci sj - i for j ≥L.
Computes the first t sequence elements of the LFSR with connection
polynomial C and initial state the sequence S (thus, the length of the LFSR
is assumed to be the length of S).
C must be at least degree 1, its coefficients
must come from the same finite field as the universe of S,
and its constant coefficient must be 1.
Also, the sequence S must have at
least as many terms as the degree of C.
Computes the next state of the LFSR having
connection polynomial C and current state the sequence S (thus, the length of
the LFSR is assumed to be the length of S).
C must be at least degree 1, its coefficients
must come from the same finite field as the universe of S,
and its constant coefficient must be 1.
Also, the sequence S must have at
least as many terms as the degree of C.
ConnectionPolynomial(S) : SeqEnum -> RngUPolElt, RngIntElt
CharacteristicPolynomial(S) : SeqEnum -> RngUPolElt, RngIntElt
Given a sequence S of elements from GF(q), return the connection
polynomial C(D) and the length L of a LFSR that generates
the sequence S.
Note that it is possible that the BerlekampMassey will
return a singular LFSR (i.e. the degree of C(D) is less than L),
and therefore one must be sure to use the first L elements of S to
regenerate the sequence.
We first create a sequence and then use BerlekampMassey to get the
connection polynomial and its length:
> S:= [GF(2)| 1,1,0,1,0,1,1,1,0,0,1,0];
> C<D>, L := BerlekampMassey(S);
> C;
D^3 + D^2 + 1
> L;
5
Now create a new sequence T containing the first L elements of S,
and reconstruct the sequence from C(D) and T.
> T := S[1..L];
> LFSRSequence(C, T, #S);
[ 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0 ]
Outputs a sequence of t bits from the shrinking generator having
connection polynomials C1 and C2 and initial states sequences
S1 and S2
(thus, the lengths of the LFSRs are assumed to be the lengths of S1
and S2).
Bits are represented as elements from GF(2).
Polynomial coefficients and sequence elements must be from GF(2).
The degrees of the connection polynomials must be at least 1 and
their trailing coefficients must be 1.
The number of elements in the initial states must be at least
as large as the degrees of the corresponding connection polynomials.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|