We define an object FSR (Feedback Shift Register), which can come in two flavours: with linear feedback LFSR (2.2-1) and external feedback NLFSR (2.3-1). The third FSR object is called FILFUN (2.3-2), i.e. ``filtering function''. A filtering function is simply a multivariate function, and because of the similarities between filtering functions and NLFSR feedbacks, the FILFUN is created as an FSR object, which allows the reuse of most NLFSR methods. Because of many similarities between the three, the basic common functionality can be found here, while specialized functions (such as LFSR, NLFSR and FILFUN object creation) can be found in the corresponding sections. Three basic functionalities are defined for FSR objects of both types:
LoadFSR - load the initial state.
StepFSR - perform one step
RunFSR - perform a sequence of steps.
Defining the FILFUN as an FSR calls for a fourth method:
LoadStepFSR - load the initial state and perform one step.
LoadStepFSR is implemented as LoadFSR, followed by StepFSR.
‣ IsFSR | ( filter ) |
This is the category of FSR objects. Objects in this category are created using functions LFSR (2.2-1), NLFSR (2.3-1) and FILFUN (2.3-2).
‣ FieldPoly( fsr ) | ( attribute ) |
‣ UnderlyingField( fsr ) | ( attribute ) |
‣ FeedbackVec( fsr ) | ( attribute ) |
‣ OutputTap( fsr ) | ( attribute ) |
FieldPoly of the fsr stores the irreducible polynomial used to construct the extension field or 1 in case of a prime field.
UnderlyingField of the fsr is the finite field over which the fsr is defined (all indeterminates and constants are from this field).
NOTE: it may seem redundant to store both FieldPoly and UnderlyingField, especially since they can also be accessed from the basis component of the fsr, however, they are used by other functions in the package.
FeedbackVec of the fsr stores the coefficients of the FeedbackPoly without its leading term in case of LFSR, and coefficients of the nonzero monomials present in the multivariate function defining the feedback in case of NLFSR and FILFUN.
OutputTap holds the output tap position(s): the sequence elements are taken from the stage(s) listed in OutputTap. In case of FILFUL, this attribute is set to stage \(S_0\) and is never used.
‣ ConstTermOfFSR( fsr ) | ( method ) |
Returns the constant term of the polynomial defining the feedback function for (N)LFSR or the filtering function for FILFUN. Example below shows the constant term for a simple FILFUN and an LFSR.
gap> test := FILFUN(GF(2), x_1^5+x_0*x_1+Z(2)^0); < FILFUN of length 2 over GF(2), with the MultivarPoly = x_0*x_1+x_1+Z(2)^0> gap> ConstTermOfFSR(test); Z(2)^0 gap> test := LFSR(GF(2), x_1^5+x_1^3+x_1); < empty LFSR over GF(2) given by FeedbackPoly = x_1^5+x_1^3+x_1 > gap> ConstTermOfFSR(test); 0*Z(2)
‣ Length( fsr ) | ( attribute ) |
‣ InternalStateSize( fsr ) | ( attribute ) |
‣ Threshold( fsr ) | ( attribute ) |
Length of the fsr is the number of its stages.
InternalStateSize of the fsr is size in bits needed to store the state computed as \(length \cdot width\), where \( width = DegreeOverPrimeField(UnderlyingField(\textit{fsr}))\).
Threshold of the fsr is currently set to \(Characteristic(\textit{fsr})^t+\ell\), where \(t=InternalStateSize(\textit{fsr})\) and \(\ell=Length(\textit{fsr})\). Threshold is not related to the fsr itself, but to the number of times the fsr can be clocked, that is it serves as the upper threshold to the length of the sequence produced.
‣ ChangeBasis( fsr, B ) | ( method ) |
‣ WhichBasis( fsr ) | ( method ) |
ChangeBasis allows changing the basis of the fsr to basis B. The argument B must be given for the UnderlyingField(fsr) over its prime subfield.
WhichBasis returns the basis currently set for the fsr. Elements in the fsr state are still represented in GAP native representation, but the functions with basis switch turned on will print the elements w.r.t. to currently set basis.
‣ SymbolicFSR( fsr ) | ( method ) |
SymbolicFSR returns the value of component sym currently set for the fsr. Component sym is updated during the loading with LoadFSR (2.1-7) or during StepFSR (2.1-9), when a symbol is used for the external step. SymbolicFSR is shown in the example for LoadFSR (2.1-7).
‣ LoadFSR( fsr, ist ) | ( method ) |
Loading the fsr with the initial state ist, which is a vector of same length as fsr. The vector elements must be either FFEs from the underlying finite field of the fsr or symbols. If either of these requirements is violated, loading fails and error message appears. At the time of loading the initial sequence element(s) (i.e., zeroth element(s)) are obtained and numsteps is set to 0.
Symbols \(s_0, \dots, s_{199}\) are prepared as global variables at the time the package is loaded. Below is an example of loading an LFSR with finite field elements and with symbols.
gap> K := GF(2);; y := X(K, "y");; l := y^3 + y + 1;; gap> test := LFSR(K, l); < empty LFSR over GF(2) given by FeedbackPoly = y^3+y+Z(2)^0 > gap> ist := [One(K), One(K), One(K)];; LoadFSR(test,ist);; gap> SymbolicFSR(test); false gap> ist := [s_2, s_1, s_0];; LoadFSR(test,ist);; gap> SymbolicFSR(test); true
‣ FeedbackFSR( fsr ) | ( method ) |
Returns: The new element computed by evaluating the feedback function using the current values from the state component of the fsr or returns an error if the fsr is not loaded.
In case of symbolic FSR, the resulting feedback is reduced w.r.t. UnderlyingField \(\mathbb{F}_q\) using the relationship \(s_i^q=s_i\).
‣ StepFSR( fsr[, elm] ) | ( method ) |
Returns: The next sequence element(s) generated by fsr in case of (N)LFSR and the new value in case of FILFUN. An error if the fsr is not loaded.
StepFSR performs one step the fsr, i.e., call FeedbackFSR (2.1-8) to compute the feedback value \(fb = \) FeedbackFSR(\(fsr\)) and then obtain the new element using one of two options:
regular step - the new state depends only of the feedback and the current state (call StepFSR(fsr)): \(new = fb \)
external step - the optional parameter elm is used and then the new element is computed as a sum of the computed feedback \(fb\) and elm, i.e., new state depends on the feedback, the current state and the input elm (call StepFSR(fsr, elm)): \(new = fb + elm\). The element elm must be an element of the underlying finite field or a symbol \(s_0, \dots, s_{199}\).
In case of the two true feedback shift registers LFSR and NLFSR, the state and numsteps are updated, then the sequence element(s) denoted by OutputTap are returned. The state is updated by shifting the current state and updating the vacant stage with \(new\) computed either as regular or external step. In case of the FILFUN, there is no notion of shifting or registers; the state and numspets are not updated, and the value \(new\) is returned by the StepFSR.
‣ LoadStepFSR( fsr[, elm, pr] ) | ( method ) |
Returns: The next sequence element(s) generated by fsr in case of (N)LFSR and the new value in case of FILFUN.
LoadStepFSR calls LoadFSR (2.1-7), followed by a regulat or an external StepFSR (2.1-9). A printswitch pr can also be used. This method is implememented maianly for the FILFUNs, but also works for (N)LFSRs. For the (N)LFSRs, LoadStepFSR will return two sequence elements, \(seq_0, seq_1\), where \(seq_0\) is the output from the OutputTap stages after loading, and \(seq_1\) the output after the first step. For the FILFUNs, LoadStepFSR returns only the element \(new = fb \) or \(new = fb + elm\), as explained in StepFSR (2.1-9).
Example of LoadStepFSR below is called for FILFUN filfun over \(\mathbb{F}_{2^4}\), first showing a regular and then the external LoadStepFSR. Then, the regular LoadStepFSR is shown for an NLFSR with the same multivariate polynomial.
gap> F := GF(2^4);; f := x_0*x_1+x_2;; filfun := FILFUN(F, f);; gap> LoadStepFSR(filfun, [Z(2)^0, Z(2)^0,Z(2)^0]); 0*Z(2) gap> LoadStepFSR(filfun, [Z(2)^0, Z(2)^0,Z(2)^0], Z(2^4)); Z(2^4) gap> nlfsr := NLFSR(F, f,3);; gap> LoadStepFSR(nlfsr, [Z(2)^0, Z(2)^0,Z(2)^0]); [ Z(2)^0, Z(2)^0 ]
‣ RunFSR( fsr[, ist, num, pr] ) | ( method ) |
‣ RunFSR( fsr, ist, elmvec[, pr] ) | ( method ) |
‣ RunFSR( fsr, z, elmvec[, pr] ) | ( method ) |
‣ RunFSR( filfun, istvec[, elmvec, pr] ) | ( method ) |
Returns: A sequence of elements generated by the FSR.
All RunFSR calls perform a sequence of FSR steps. The fsr will be run for \(min(\textit{num}, Threshold(\textit{fsr}))\) number of steps: value Threshold(fsr) is used by all versions without explicit num and enforced when num exceeds Threshold (2.1-4).
The RunFSR calls where the initial state ist is passed as an argument are the load-and-run calls. As with StepFSR (2.1-9), RunFSR also exists as a regular and external run. The external runs are RunFSR calls with a vector of finite field elements elmvec passed as an argument.
There is an optional printing switch pr, with default set to false; if true then the state and the output sequence element(s) are printed in GAP shell on every step of the fsr (we call this output for RunFSR), and the currently set basis B is used for representation of elements.
RunFSR( fsr[, num, pr] ) - run fsr for num/threshold steps with/without output.
RunFSR( fsr, ist[, num, pr] ) - load fsr with ist, then run fsr for num/threshold steps with/without output (i.e., regular version).
RunFSR( fsr, ist, elmvec [, pr] ) - load fsr with ist, then run fsr for Length(elmvec) steps, whereby one element of elmvec is added to the feedback at each step (starting with elmvec[1]), with/without output (i.e., external version). NOTE: the sequence returned has length Length(elmvec)+1, because the zeroth sequence element is returned at the time of loading the FSR.
RunFSR( fsr, z, elmvec [, pr] ) - input z must be set to 0 to indicate we want to continue a run with new elmvec: run fsr for Length(elmvec) steps, whereby one element of elmvec is added to the feedback at each step (starting with elmvec[1]), with/without output (i.e., external version). NOTE: the sequence returned has length Length(elmvec).
RunFSR( filfun , istvec, [elmvec , pr] ) - for the FILFUNs only - performs a sequence of LoadStepFSR (2.1-10) calls with a new initial state on every step, with/without output. The number of LoadStepFSR (2.1-10) depends on the length of istvec. When is used with both istvec and elmvec (i.e., external version), the two vectors must be of the same length.
For the load and run versions, element seq\(_0\) is a part of the output sequence, hence the output sequence has the length num+1/ threshold+1/Length(ffevec)+1.
For versions without the loading of ist, calling RunFSR returns an error if the fsr is not loaded!
The ouput of RunFSR is:
sequence of FFEs: seq\(_0\), seq\(_1\), seq\(_2\), \(\dots ,\) for Length(OutputTap)\(=1\).
sequence of vectors, each of them with \(t\) FFEs: seq\(_0\), seq\(_1\), seq\(_2\), \(\dots ,\) where seq\(_i=(\)seq\(_{i1}\),\(\dots , \)seq\(_{it}\)) for Length(OutputTap)\(=t\).
Example of RunFSR called for an LFSR test over \(\mathbb{F}_{2^4}\), with initial state ist, print switch true, basis B, and with run length 5:
gap> K := GF(2);; x := X(K, "x");; gap> f := x^4 + x^3 + 1;; F := FieldExtension(K, f);; B := Basis(F);; gap> y := X(F, "y");; l := y^4 + y^3 + y + Z(2^4);; gap> test := LFSR(K, f, l);; gap> ist :=[0*Z(2), Z(2^4), Z(2^4)^5, Z(2)^0 ];; gap> RunFSR(test, ist, 5, true); using basis B := [ Z(2)^0, Z(2^4)^7, Z(2^4)^14, Z(2^4)^6 ] elm [ 3, ... ...,0 ] with taps [ 0 ] [ [ 0, 0, 0, 0 ], [ 0, 1, 1, 0 ], [ 1, 1, 0, 1 ], [ 1, 0, 0, 0 ] ] [ 1, 0, 0, 0 ] [ [ 1, 0, 1, 1 ], [ 0, 0, 0, 0 ], [ 0, 1, 1, 0 ], [ 1, 1, 0, 1 ] ] [ 1, 1, 0, 1 ] [ [ 1, 1, 0, 0 ], [ 1, 0, 1, 1 ], [ 0, 0, 0, 0 ], [ 0, 1, 1, 0 ] ] [ 0, 1, 1, 0 ] [ [ 0, 1, 1, 1 ], [ 1, 1, 0, 0 ], [ 1, 0, 1, 1 ], [ 0, 0, 0, 0 ] ] [ 0, 0, 0, 0 ] [ [ 1, 1, 0, 0 ], [ 0, 1, 1, 1 ], [ 1, 1, 0, 0 ], [ 1, 0, 1, 1 ] ] [ 1, 0, 1, 1 ] [ [ 1, 0, 1, 0 ], [ 1, 1, 0, 0 ], [ 0, 1, 1, 1 ], [ 1, 1, 0, 0 ] ] [ 1, 1, 0, 0 ] [ Z(2)^0, Z(2^2), Z(2^4), 0*Z(2), Z(2^4)^2, Z(2^4)^9 ]
Example of RunFSR called for an LFSR test over \(\mathbb{F}_{2^4}\), with initial state ist, print switch true, basis B, and with 5 external inputs given as elmvec:
gap> elmvec := [Z(2^4)^2, Z(2^4)^2, Z(2^2), Z(2^4)^7, Z(2^4)^6];; gap> RunFSR(test, ist, elmvec, true); using basis B := [ Z(2)^0, Z(2^4)^7, Z(2^4)^14, Z(2^4)^6 ] elm [ 3, ... ...,0 ] with taps [ 0 ] [ 0, 0, 0, 0 ] [ [ 0, 0, 0, 0 ], [ 0, 1, 1, 0 ], [ 1, 1, 0, 1 ], [ 1, 0, 0, 0 ] ] [ 1, 0, 0, 0 ] [ 1, 0, 1, 1 ] [ [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 1, 1, 0 ], [ 1, 1, 0, 1 ] ] [ 1, 1, 0, 1 ] [ 1, 0, 1, 1 ] [ [ 1, 1, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 1, 1, 0 ] ] [ 0, 1, 1, 0 ] [ 1, 1, 0, 1 ] [ [ 1, 0, 1, 0 ], [ 1, 1, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0 ] ] [ 0, 0, 0, 0 ] [ 0, 1, 0, 0 ] [ [ 1, 1, 1, 0 ], [ 1, 0, 1, 0 ], [ 1, 1, 0, 0 ], [ 0, 0, 0, 0 ] ] [ 0, 0, 0, 0 ] [ 0, 0, 0, 1 ] [ [ 0, 0, 1, 1 ], [ 1, 1, 1, 0 ], [ 1, 0, 1, 0 ], [ 1, 1, 0, 0 ] ] [ 1, 1, 0, 0 ] [ Z(2)^0, Z(2^2), Z(2^4), 0*Z(2), 0*Z(2), Z(2^4)^9 ]
In both examples above the there is a column elm, which is in first case empty, because the first example is showing the regular run, while in the second example, this column shows the element being added at each step of the external run (empty in first row - the loading step).
Also note that in the two examples above, RunFSR will call LoadFSR (2.1-7) first, which adds the elm seq\({{_0}}\) to the sequence, so both sequences above are of length num+1/Length(elmvec)+1, i.e.,6.
The last row in both examples is the actual sequence obtained from this run, and is kept in Zechs logarithm representation. To represent the elements in the first 6 rows, the basis printed out at the beginning is used; it can be changed by using ChangeBasis call and repeating RunFSR.
When FILFUNs are created, their current state is set to all zero. Calling RunFSR(fsr [, ist, num, pr]) or RunFSR( fsr, z, elmvec [, pr] ) will work, even without ist, however, it will just repeat the same computation num times. For this reason, separate RunFSR are implemented for FILFUNs only: they use a sequence of LoadStepFSR (2.1-10) calls rather than a single LoadFSR (2.1-7), followed by a sequence of StepFSR (2.1-9) calls. The example below for a FILFUN filfun over \(\mathbb{F}_{2^4}\), with two initial states istvec will perform two calls of LoadStepFSR (2.1-10). First call is without and second with an external element taken from elmvec, also of length 2.
gap> F := GF(2^4);; f := x_0*x_1+x_2;; filfun := FILFUN(F, f);; gap> istvec := [[Z(2)^0, Z(2)^0,Z(2)^0], [0*Z(2), Z(2^4)^3, Z(2^4)] ];; gap> seq:= RunFSR(filfun, istvec ); [ 0*Z(2), Z(2^4) ] gap> elmvec := [Z(2^4)^5, Z(2^4)];; gap> seq:= RunFSR(filfun, istvec, elmvec ); [ Z(2^2), 0*Z(2) ]
‣ LFSR( F, feedbackpoly[, B, tap] ) | ( function ) |
‣ LFSR( K, fieldpoly, feedbackpoly[, B, tap] ) | ( function ) |
‣ LFSR( p, m, n[, tap] ) | ( function ) |
Returns: An empty LFSR with components init, state , numsteps, basis and sym.
Function LFSR provides different ways to create an LFSR object; the main difference is in the construction of the underlying finite field. The LFSR is uniquely described with a feedback polynomial feedbackpoly. The call LFSR(p, m, n) will randomly choose a polynomial of degree n, which is primitive over the field \(\mathbb{F}_{p^m}\), and use it as feedback.
Inputs:
F - the underlying finite field (either an extension field or a prime field).
B - the basis of F over its prime subfield.
feedbackpoly - the LFSR defining polynomial.
fieldpoly - the defining polynomial of the extension field (must be irreducible).
p - the characteristic.
m - the degree of extension (degree of fieldpoly).
n - the length of the LFSR (degree of feedbackpoly).
tap - optional parameter: the output tap (must be a positive integer or a list of positive integers) and will be changed to the default S_0 if the specified integer is out of LFSR range.
Components:
init - a vector of length \(n=\)Degree(feedbackpoly), storing the initial state of the LFSR \(S_{n-1}, \dots, S_0\). Can be a vector of FFEs and/or symbols \(s_0,\dots,s_{199}\).
state - a vector of length \(n=\)Degree(feedbackpoly), storing the current state of the LFSR \(S_{n-1}^{ns}, \dots, S_0^{ns}\), where \(ns\)=numsteps. Can be a vector of FFEs and/or symbols \(s_0,\dots,s_{199}\).
numsteps - the number of steps performed thus far (initialized to -1 when created, set to 0 when loaded using LoadFSR (2.1-7) and incremented by 1 with each step (using StepFSR (2.1-9))).
basis - basis of F over its prime subfield (if no basis is given this component is set to canonical basis of F over its prime subfield) .
sym - set to false by default. This component is updated each time the LFSR is loaded or clocked. If a symbol \(s_k\) enters the state, either through loading or an external step, this component is set true.
Attributes FieldPoly (2.1-2), UnderlyingField (2.1-2), FeedbackPoly (2.2-3), FeedbackVec (2.1-2), Length (2.1-4) and OutputTap (2.1-2) and the property IsLinearFeedback (2.2-2) are set during the construction of an LFSR.
If there is something wrong with the arguments (e.g. attempting to create an extension field using a reducible poynomial), an error message appears and the function returns fail.
Example below shows how to create an empty LFSR over \(\mathbb{F}_{2^4}\) created as extension of \(\mathbb{F}_2\), called test, firstly without a specified basis (in which case the canonical basis is used), and then with basis B:
gap> test := LFSR(K, f, l); < empty LFSR over GF(2^4) given by FeedbackPoly = y^4+y^3+y+Z(2^4) > gap> WhichBasis(test); CanonicalBasis( GF(2^4) ) gap> B := Basis(F, Conjugates(Z(2^4)^3));; test := LFSR(K, f, l, B); < empty LFSR over GF(2^4) given by FeedbackPoly = y^4+y^3+y+Z(2^4) > gap> WhichBasis(test); Basis( GF(2^4), [ Z(2^4)^3, Z(2^4)^6, Z(2^4)^12, Z(2^4)^9 ] )
‣ IsLinearFeedback( lfsr ) | ( property ) |
‣ IsLFSR( lfsr ) | ( filter ) |
If we were to represent the lsfr with a multivariate polynomial, DegreeOfPolynomial would return 1 - the feedback polynomial is linear and IsLinearFeedback is set to true. (i.e., only linear terms are present: monomials with only one variable )
Filter IsLFSR is defined as and-filter of IsFSR and IsLinearFeedback.
‣ FeedbackPoly( lfsr ) | ( attribute ) |
Attribute holding the the LFSR feedback polynomial.
‣ IsPeriodic( lfsr ) | ( property ) |
‣ IsUltPeriodic( lfsr ) | ( property ) |
‣ IsMaxSeqLFSR( lfsr ) | ( property ) |
‣ Period( lfsr ) | ( attribute ) |
‣ PeriodPrimitive( lfsr ) | ( method ) |
‣ PeriodIrreducible( lfsr ) | ( method ) |
‣ PeriodReducible( lfsr ) | ( method ) |
Properties, attributes and methods concerning the periodicity of the output sequence(s), generated by the lsfr.
Properties:
IsPeriodic: true if constant term of FeedbackPoly != 0 (Theorem 8.11 [LN97]).
IsUltPeriodic: true if IsLFSR is true (Theorem 8.7 [LN97])
IsMaxSeqLFSR: true if FeedbackPoly is primitive (Definition 10.2.36 [MP13]).
Attributes:
Period: holds the period of the LFSR.
Methods to compute the period:
PeriodPrimitive: computed as \(q^n-1\), where \(\mathbb{F}_q\) is the underlying finite field and \(n=Degree(\)FeedbackPoly\((\)lfsr\())\).
PeriodIrreducible: \(Order(\omega)\) where \(\omega\) is a root of FeedbackPoly(lfsr) (Theorem 2.1.53 [MP13]).
PeriodReducible: for FeedbackPoly(lfsr) = \(a\prod {f_i}^{bi}\), the order is given by \(ep^t\), where \(p\) is the characteristic of the underlying finite field, \(e = Lcm(ord(f_i))\) and \(t\) is the smallest integer such that \(p^t\geq max(b_i)\) (Theorem 2.1.55 [MP13]).
Although the last method should compute the period correctly for all three cases, it is computationally more demanding, hence the first two methods are used when applicable.
Elxample below shows a LFSR called test using a reducible feedback polynomial \(\ell = y^4 + y + \alpha=(y^2+y+\alpha^7)(y^2+y+\alpha^9)\), where \(\alpha = Z(2^4)\), with period \((2^4)^2 - 1 = 255\). Next, the period of an LFSR test1 with a primitive feedback polynomial \(\ell=y^4+y^3+y+\alpha\), where \(\alpha = Z(2^4)\), with maximum period \((2^4)^4-1=65535\); the LFSR test1 will produce an \(m\)-sequence.
gap> l := y^4 + y + Z(2^4);; test := LFSR(K, f, l); < empty LFSR over GF(2^4) given by FeedbackPoly = y^4+y+Z(2^4) > gap> Period(test); IsMaxSeqLFSR(test); 255 false gap> l := y^4 + y^3 + y + Z(2^4);; test1 := LFSR(K, f, l, B); < empty LFSR over GF(2^4) given by FeedbackPoly = y^4+y^3+y+Z(2^4) > gap> Period(test1); IsMaxSeqLFSR(test1); 65535 true
Since FILFUN can have both linear and nonlinear filtering function, they are treated together with NLFSRs because of the structural similarities between the NLFSR feedback functions and nonlinear filtering functions.
‣ NLFSR( F, mpoly, len[, tap] ) | ( function ) |
‣ NLFSR( F, fieldpoly, mpoly, len[, tap] ) | ( function ) |
‣ NLFSR( F, clist, mlist, len[, tap] ) | ( function ) |
‣ NLFSR( F, fieldpoly, clist, mlist, len[, tap] ) | ( function ) |
Returns: An empty NLFSR with components init, state, numsteps and basis.
Function NLFSR provides different ways to create an NLFSR object; the main differences are in multivariate polynomial specification and in construction of the underlying finite field. The NLFSR is uniquely described with a a multivariate polynomial, which is either given directly as mpoly or by two lists: a list of monomials mlist, and a list of their corresponding coefficients clist, i.e. \(mpoly = clist \cdot mlist\). Both of lists must always be provided and be of same length. The creation of a random NLFSR is currently not implemented.
Inputs:
F - the underlying finite field (either an extension field or a prime field).
fieldpoly - the defifning polynomial of the extension field (must be irreducible).
mpoly - the feedback polynomial.
clist - the list of coefficients for the monomials in mlist.
mlist - the list of monomials.
len - the length of NLFSR. The range of the NLFSR is \([0, len -1]\).
tap - an optional parameter: the output tap (a positive integer or a list of positive integers), which will be changed to the default S_0 if the specified integer(s) fall out of NLFSR range.
NOTE: the lists clist and mlist must be of same length, and all elements in clist must belong to the underlying field. Monomials in mlist must not include any indeterminates that are out of range specified by len: stages of NLFSR are represented by indeterminants and the feedback is not allowed to use a stage that doesnt exist. Currently, 200 variables \(x_k\) are available, which puts the maximum length of the NLFSR too 200 stages. A second constraint on mlist (and mploy) requires that it must contain at least one monomial of degree \(>1\), otherwise we must create an LFSR. In addition, if mpoly or mlist contains only one variable, and error is triggered, suggesting to use the LFSR instead.
Components:
init - a vector of length len, storing the initial state of the NLFSR \(S_{len-1}, \dots, S_0\). Can be a vector of FFEs and/or symbols \(s_0,\dots,s_{199}\).
state - a vector of length len, storing the current state of the NLFSR \(S_{len-1}^{ns}, \dots, S_0^{ns}\), where \(ns\)=numsteps. Can be a vector of FFEs and/or symbols \(s_0,\dots,s_{199}\).
numsteps - the number of steps performed thus far (initialized to -1 when created, set to 0 when loaded using LoadFSR (2.1-7) and incremented by 1 with each step (using StepFSR (2.1-9))).
basis - basis of F over its prime subfield (if no basis is given this component is set to canonical basis of F over its prime subfield) .
sym - set to false by default. This component is updated each time the NLFSR is loaded or clocked. If a symbol \(s_k\) enters the state, either through loading or an external step, this component is set true.
Attributes FieldPoly (2.1-2), UnderlyingField (2.1-2), MultivarPoly (2.3-3), MonomialList (2.3-3), IndetList (2.3-3), FeedbackVec (2.1-2), Length (2.1-4) and OutputTap (2.1-2) and the property IsNonLinearFeedback are set during the construction of an NLFSR.
If there is something wrong with the arguments (e.g. attempting to create an extension field using a reducible poynomial), an error message appears and the function returns fail.
gap> test := NLFSR(GF(2), x_0*x_3*x_1 + x_2, 5); < empty NLFSR of length 5 over GF(2), given by MultivarPoly = x_0*x_1*x_3+x_2> gap> clist := [One(F), One(F)];; mlist := [x_0, x_1*x_2];; gap> test := NLFSR(GF(2), clist, mlist, 3); < empty NLFSR of length 3 over GF(2), given by MultivarPoly = x_1*x_2+x_0>
‣ FILFUN( F, mpoly ) | ( function ) |
‣ FILFUN( F, clist, mlist ) | ( function ) |
‣ FILFUN( F, fieldpoly, clist, mlist ) | ( function ) |
Returns: An empty FILFUN with components init, state, numsteps and basis.
Function FILFUN provides four ways to create an FILFUN object; they differ in the way the underlying finite field is constructed and/or in the way the multivariate polynomial is defined. The FILFUN is uniquely described with a a multivariate polynomial mpoly. It can also be given by two lists: a list of monomials mlist, and a list of their corresponding coefficients clist, just as is requiered by the NLFSR (2.3-1) function.
Inputs:
F - the underlying finite field (either an extension field or a prime field).
fieldpoly - the defifning polynomial of the extension field (must be irreducible).
mpoly - the multivariate polynomial.
clist - the list of coefficients for the monomials in mlist.
mlist - the list of monomials.
NOTE: the lists clist and mlist must be of same length, and all elements in clist must belong to the underlying field. Indetermincates in mlist define the length of components init and state.
Compoents: because of similarities between with the NLFSR, it is convenient to be able to reuse the allready existing functions. Hence, the FILFUN is a member of the FSRFamily
init - unused, but kept for similarity with (N)LFSRs
state - a vector of length \(n\), where \(n\) is the number of distinct indeterminates that appear in mpoly or mlist respectively, storing the current state of the FILFUN. Can be a vector of FFEs and/or symbols \(s_0,\dots,s_{199}\).
numsteps - unused, but kept for similarity with (N)LFSRs
basis - basis of F over its prime subfield. The component basis is set to the canonical basis of F over its prime subfield. None of the FILFUN calls contain the basis as argument: the basis is set to canonical basis and must be later changed by ChangeBasis (2.1-5).
sym - set to false by default. This component is updated each time the FILFUN is loaded or a step is performed. If a symbol \(s_k\) enters the state, either through loading or an external step, this component is set true.
Attributes FieldPoly (2.1-2), UnderlyingField (2.1-2), MultivarPoly (2.3-3), MonomialList (2.3-3), IndetList (2.3-3), FeedbackVec (2.1-2), Length (2.1-4) and the properties IsNonLinearFSRFilter and IsLinearFSRFilter are set during the construction of an FILFUN.
If there is something wrong with the arguments (e.g. attempting to create an extension field using a reducible poynomial), an error message appears and the function returns fail.
gap> test := FILFUN(GF(2) , x_0 +x_1*x_2); < FILFUN of length 3 over GF(2), with the MultivarPoly = x_1*x_2+x_0>
‣ MultivarPoly( x ) | ( attribute ) |
‣ MonomialList( x ) | ( attribute ) |
‣ IndetList( x ) | ( attribute ) |
These attributes are set for NLFSR and FILFUN objects at the time of their creation, i.e. x is either an NLFSR or a FILFUN.
MultivarPoly holds the multivariate function defining the feedback of the NLFSR or the FILFUN.
MonomialList holds a copy of the initial monomial list mlist used to create x.
IndetList holds all the indeterminates that are present in MultivarPoly and MonomialList. This list is needed for the computation of the feedback for the NLFSR and the output element for the FILFUN, which is in both cases computed from MultivarPoly, IndetList and state, and not from FeedbackVec.
Example below shows the values of attributes MultivarPoly, MonomialList and IndetList for an NLFSR.
gap> nlfsr := NLFSR(GF(2), x_0+x_1*x_2, 3);; gap> MultivarPoly(nlfsr); MonomialList(nlfsr); IndetList(nlfsr); x_1*x_2+x_0 [ x_1*x_2, x_0 ] [ 1, 2, 0 ]
‣ IsNonLinearFeedback( nlfsr ) | ( property ) |
‣ IsNLFSR( nlfsr ) | ( filter ) |
For the multivariate polynomial defining the NLFSR, DegreeOfPolynomialOverField (4.1-2) greter than 1 sets IsNonLinearFeedback to true. This property is set during the creation of the NLFSR using NLFSR (2.3-1), which will print an error message instructing to use the LFSR (2.2-1) constructor instead.
The filter IsNLFSR is defined as and-filter of IsFSR and IsNonLinearFeedback.
‣ IsFSRFilter( filfun ) | ( property ) |
‣ IsFILFUN( filfun ) | ( filter ) |
‣ IsLinearFSRFilter( filfun ) | ( property ) |
‣ IsNonLinearFSRFilter( filfun ) | ( filter ) |
IsFSRFilter is set to true at the creation time of the FILFUN, and at the same time, properties IsLinearFeedback and IsNonLinearFeedback are set to false to differentiate the FILFUN from LFSR and NLFSR. The filter IsFILFUN is defined as and-filter of IsFSR and IsFSRFilter.
For the multivariate polynomial given defining filfun, the DegreeOfPolynomialOverField (4.1-2) sets the values for IsNonLinearFSRFilter and IsLinearFSRFilter.
generated by GAPDoc2HTML