Decimation#
- Decimation(S, f, d): SeqEnum, RngIntElt, RngIntElt -> SeqEnum#
Given a binary sequence \(S\), and integers \(f\) and \(d\), return the decimation of \(S\). This is the sequence containing elements \(S[f]\), \(S[f+d]\), \(S[f+2d]\), … where the indices in \(S\) are interpreted with wrap-around as integers between \(1\) and \(\#S\).
- Decimation(S, f, d, t): SeqEnum, RngIntElt, RngIntElt, RngIntElt -> SeqEnum#
Decimation of the sequence \(S\). Returns a new sequence containing the first \(t\) elements of \(S[f]\), \(S[f+d]\), \(S[f+2d]\), … where the indices in \(S\) are interpreted with wrap-around as integers between \(1\) and #\(S\).
- Example: decimate (ex-29a760)#
Given a primitive polynomial over \({\bf F}_{q}\), one can obtain another primitive polynomial by decimating an LFSR sequence obtained from the initial polynomial. This is demonstrated in the code below.
> K := GF(7); > C<D> := PrimitivePolynomial(K, 2); > C; D^2 + 6*D + 3
In order to generate an LFSR sequence, we must first multiply this polynomial by a suitable constant so that the trailing coefficient becomes \(1\).
> C := C * Coefficient(C,0)^-1; > C; 5*D^2 + 2*D + 1
We are now able to generate an LFSR sequence of length \(7^2 - 1\). The initial state can be anything other than \([0, 0]\).
> t := LFSRSequence (C, [K| 1,1], 48); > t; [ 1, 1, 0, 2, 3, 5, 3, 4, 5, 5, 0, 3, 1, 4, 1, 6, 4, 4, 0, 1, 5, 6, 5, 2, 6, 6, 0, 5, 4, 2, 4, 3, 2, 2, 0, 4, 6, 3, 6, 1, 3, 3, 0, 6, 2, 1, 2, 5 ]
We decimate the sequence by a value \(d\) having the property \(\gcd(d,48)=1\).
> t := Decimation(t, 1, 5); > t; [ 1, 5, 0, 6, 5, 6, 4, 4, 3, 1, 0, 4, 1, 4, 5, 5, 2, 3, 0, 5, 3, 5, 1, 1, 6, 2, 0, 1, 2, 1, 3, 3, 4, 6, 0, 3, 6, 3, 2, 2, 5, 4, 0, 2, 4, 2, 6, 6 ] > B := BerlekampMassey(t); > B; 3*D^2 + 5*D + 1
To get the corresponding primitive polynomial, we multiply by a constant to make it monic.
> B := B * Coefficient(B, 2)^-1; > B; D^2 + 4*D + 5 > IsPrimitive(B); true