-
-
[分享]LFSR和m序列
-
发表于: 2011-12-20 14:40 5218
-
众多的序列产生法:
http://www.newwaveinstruments.com/products/index.htm
Direct Sequence Generator
DSSS Generator
FHSS Generator
Gold Code Generator
LRS Generator
PN Generator
PN Code Generator
PN Sequence Generator
PRBS Generator
Pseudo-Noise Generator
Pseudo-Noise Code Generator
Pseudo-Noise Sequence Generator
Pseudonoise Code Generator
Pseudonoise Generator
Pseudonoise Sequence Generator
Pseudo-Random Bit Generator
Pseudo-Random Bit Sequence Generator
Pseudo-Random Code Generator
Pseudo-Random Noise Generator
Pseudo-Random Sequence Generator
Pseudorandom Bit Generator
Pseudorandom Bit Sequence Generator
Pseudorandom Code Generator
Pseudorandom Noise Generator
Pseudorandom Sequence Generator
Spread Spectrum Generator
Direct Sequence Generators
DSSS Generators
FHSS Generators
Gold Code Generators
LRS Generators
PN Generators
PN Code Generators
PN Sequence Generators
PRBS Generators
Pseudo-Noise Generators
Pseudo-Noise Code Generators
Pseudo-Noise Sequence Generators
Pseudonoise Generators
Pseudonoise Code Generators
Pseudonoise Sequence Generators
Pseudo-Random Bit Generators
Pseudo-Random Bit Sequence Generators
Pseudo-Random Code Generators
Pseudo-Random Noise Generators
Pseudo-Random Sequence Generators
Pseudorandom Bit Generators
Pseudorandom Bit Sequence Generators
Pseudorandom Code Generators
Pseudorandom Noise Generators
Pseudorandom Sequence Generators
Spread Spectrum Generators
An Awesome Generator
http://www.xilinx.com/support/documentation/application_notes/xapp210.pdf
http://homepage.mac.com/afj/lfsr.html
http://homepage.mac.com/afj/lfsr.html
B-M算法是流密码中用的一种求取LSRE,具体就是,对于二进制序列a,计算求得f(x),能够产生a序列并且级数最小的线性移位寄存器的反馈多项式
把5个寄存器的试了两种,都不是32-1=31,都不是m序列
S:= [GF(2)| 1,1,0,0,1];
S;
BerlekampMassey(S);
ConnectionPolynomial(S);
CharacteristicPolynomial(S);
C<D>, L := BerlekampMassey(S);
C;
LFSRStep(C, S);
LFSRSequence(C, S, 100);
[ 1, 1, 0, 0, 1 ]
$.1^3 + $.1^2 + 1
3
$.1^3 + $.1^2 + 1
3
$.1^3 + $.1^2 + 1
3
D^3 + D^2 + 1
[ 1, 0, 0, 1, 0 ]
[ 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1,
0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0,
1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0,
0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1 ]
S:= [GF(2)| 1,0,0,1,1];
S;
BerlekampMassey(S);
ConnectionPolynomial(S);
CharacteristicPolynomial(S);
C<D>, L := BerlekampMassey(S);
C;
LFSRStep(C, S);
LFSRSequence(C, S, 100);
[ 1, 0, 0, 1, 1 ]
$.1^3 + $.1 + 1
3
$.1^3 + $.1 + 1
3
$.1^3 + $.1 + 1
3
D^3 + D + 1
[ 0, 0, 1, 1, 1 ]
[ 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1,
1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1,
1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0,
1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0 ]
[ 1, 0, 0, 1, 0 ]
$.1^3 + 1
3
$.1^3 + 1
3
$.1^3 + 1
3
D^3 + 1
[ 0, 0, 1, 0, 0 ]
[ 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0,
0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0,
0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0,
0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1 ]
[ 1, 0, 1, 1, 0 ]
$.1^2 + $.1 + 1
2
$.1^2 + $.1 + 1
2
$.1^2 + $.1 + 1
2
D^2 + D + 1
[ 0, 1, 1, 0, 1 ]
[ 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0,
1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0,
1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0,
1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1 ]
只有这个31步=2^5-1 周期最大 可分圆多项式=特征多项式D^2 + D + 1。。。 最高次不是5????
[ 1, 1, 0, 1, 0 ]
$.1^3 + $.1 + 1
3
$.1^3 + $.1 + 1
3
$.1^3 + $.1 + 1
3
D^3 + D + 1
[ 1, 0, 1, 0, 0 ]
[ 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0,
0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1,
0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0,
1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1 ]
[ 1, 1, 1, 1, 0 ]
$.1^4 + $.1 + 1
4
$.1^4 + $.1 + 1
4
$.1^4 + $.1 + 1
4
D^4 + D + 1
[ 1, 1, 1, 0, 1 ]
[ 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0,
1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1,
1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0,
1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0 ]
=============
多项式$x^n-1$分解,它所分解得到的不可约多项式称为分圆多项式.事实上,分圆多项式的定义可以用以下的方式来得到:设ε是$x^n-1=0$的一个根,即ε是n次单位根,如果对任意的自然数k<n,ε都不是$x^k-1=0$的根,那么称ε为n次本原单位根.由所有n次本原单位根构成的多项式就称为n次分圆多项式.
n次分圆多项式=(x^n-1)/LCM(x^d-1), ,0d<n ,d|n
Zp[x]中p^n-1次分圆多项式的每个不可约式都是是n次本原的,数量为(p^n-1次分圆多项式/n)
难就是p可为2,3。。。进制上的域
试求上面周期31的反馈函数:假设已知5个寄存器(当成m)序列。。。0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1
a1a2a3 a4 a5a6 a7a8a9a10
[ 0, 1, 1, 0, 1 ]
[ 1, 0, 1, 1, 0, 1, 1, 0, 1,1,0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0,
1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0,
1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0,
1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1 ]
(a6,a7,a8,a9,a10)=(c5,c,4,c3,c2,c1)= Matrix(GF(2), 5, 5, [0, 1, 1, 0, 1, 1,1,0,1,1,1,0,1,1,0,0,1,1,0,1,1,1,0,1,1]);
X;
X^-1;
[0 1 1 0 1]
[1 1 0 1 1]
[1 0 1 1 0]
[0 1 1 0 1]
[1 1 0 1 1]
>> X^-1;
^
Runtime error in '^': Argument 1 is not invertible
没逆距阵???肯定不是m序列-----》周期能最大,可还是可能不是m序列
次数 对应的分圆多项式
1 x-1
2 x+1
3 x2+x+1 4 x2+1
5 x4+x3+x2+x+1
6 x2-x+1
7 x6+x5+x4+x3+x2+x+1
8 x4+1
9 x6+x3+1
10 x4-x3+x2-x+1
11 x10+x9+x8+x7+x6+x5+x4+x3+x2+x+1
12 x4-x2+1
http://www.newwaveinstruments.com/products/index.htm
Direct Sequence Generator
DSSS Generator
FHSS Generator
Gold Code Generator
LRS Generator
PN Generator
PN Code Generator
PN Sequence Generator
PRBS Generator
Pseudo-Noise Generator
Pseudo-Noise Code Generator
Pseudo-Noise Sequence Generator
Pseudonoise Code Generator
Pseudonoise Generator
Pseudonoise Sequence Generator
Pseudo-Random Bit Generator
Pseudo-Random Bit Sequence Generator
Pseudo-Random Code Generator
Pseudo-Random Noise Generator
Pseudo-Random Sequence Generator
Pseudorandom Bit Generator
Pseudorandom Bit Sequence Generator
Pseudorandom Code Generator
Pseudorandom Noise Generator
Pseudorandom Sequence Generator
Spread Spectrum Generator
Direct Sequence Generators
DSSS Generators
FHSS Generators
Gold Code Generators
LRS Generators
PN Generators
PN Code Generators
PN Sequence Generators
PRBS Generators
Pseudo-Noise Generators
Pseudo-Noise Code Generators
Pseudo-Noise Sequence Generators
Pseudonoise Generators
Pseudonoise Code Generators
Pseudonoise Sequence Generators
Pseudo-Random Bit Generators
Pseudo-Random Bit Sequence Generators
Pseudo-Random Code Generators
Pseudo-Random Noise Generators
Pseudo-Random Sequence Generators
Pseudorandom Bit Generators
Pseudorandom Bit Sequence Generators
Pseudorandom Code Generators
Pseudorandom Noise Generators
Pseudorandom Sequence Generators
Spread Spectrum Generators
An Awesome Generator
http://www.xilinx.com/support/documentation/application_notes/xapp210.pdf
http://homepage.mac.com/afj/lfsr.html
http://homepage.mac.com/afj/lfsr.html
B-M算法是流密码中用的一种求取LSRE,具体就是,对于二进制序列a,计算求得f(x),能够产生a序列并且级数最小的线性移位寄存器的反馈多项式
把5个寄存器的试了两种,都不是32-1=31,都不是m序列
S:= [GF(2)| 1,1,0,0,1];
S;
BerlekampMassey(S);
ConnectionPolynomial(S);
CharacteristicPolynomial(S);
C<D>, L := BerlekampMassey(S);
C;
LFSRStep(C, S);
LFSRSequence(C, S, 100);
[ 1, 1, 0, 0, 1 ]
$.1^3 + $.1^2 + 1
3
$.1^3 + $.1^2 + 1
3
$.1^3 + $.1^2 + 1
3
D^3 + D^2 + 1
[ 1, 0, 0, 1, 0 ]
[ 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1,
0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0,
1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0,
0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1 ]
S:= [GF(2)| 1,0,0,1,1];
S;
BerlekampMassey(S);
ConnectionPolynomial(S);
CharacteristicPolynomial(S);
C<D>, L := BerlekampMassey(S);
C;
LFSRStep(C, S);
LFSRSequence(C, S, 100);
[ 1, 0, 0, 1, 1 ]
$.1^3 + $.1 + 1
3
$.1^3 + $.1 + 1
3
$.1^3 + $.1 + 1
3
D^3 + D + 1
[ 0, 0, 1, 1, 1 ]
[ 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1,
1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1,
1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0,
1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0 ]
[ 1, 0, 0, 1, 0 ]
$.1^3 + 1
3
$.1^3 + 1
3
$.1^3 + 1
3
D^3 + 1
[ 0, 0, 1, 0, 0 ]
[ 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0,
0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0,
0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0,
0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1 ]
[ 1, 0, 1, 1, 0 ]
$.1^2 + $.1 + 1
2
$.1^2 + $.1 + 1
2
$.1^2 + $.1 + 1
2
D^2 + D + 1
[ 0, 1, 1, 0, 1 ]
[ 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0,
1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0,
1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0,
1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1 ]
只有这个31步=2^5-1 周期最大 可分圆多项式=特征多项式D^2 + D + 1。。。 最高次不是5????
[ 1, 1, 0, 1, 0 ]
$.1^3 + $.1 + 1
3
$.1^3 + $.1 + 1
3
$.1^3 + $.1 + 1
3
D^3 + D + 1
[ 1, 0, 1, 0, 0 ]
[ 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0,
0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1,
0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0,
1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1 ]
[ 1, 1, 1, 1, 0 ]
$.1^4 + $.1 + 1
4
$.1^4 + $.1 + 1
4
$.1^4 + $.1 + 1
4
D^4 + D + 1
[ 1, 1, 1, 0, 1 ]
[ 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0,
1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1,
1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0,
1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0 ]
=============
多项式$x^n-1$分解,它所分解得到的不可约多项式称为分圆多项式.事实上,分圆多项式的定义可以用以下的方式来得到:设ε是$x^n-1=0$的一个根,即ε是n次单位根,如果对任意的自然数k<n,ε都不是$x^k-1=0$的根,那么称ε为n次本原单位根.由所有n次本原单位根构成的多项式就称为n次分圆多项式.
n次分圆多项式=(x^n-1)/LCM(x^d-1), ,0d<n ,d|n
Zp[x]中p^n-1次分圆多项式的每个不可约式都是是n次本原的,数量为(p^n-1次分圆多项式/n)
难就是p可为2,3。。。进制上的域
试求上面周期31的反馈函数:假设已知5个寄存器(当成m)序列。。。0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1
a1a2a3 a4 a5a6 a7a8a9a10
[ 0, 1, 1, 0, 1 ]
[ 1, 0, 1, 1, 0, 1, 1, 0, 1,1,0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0,
1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0,
1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0,
1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1 ]
(a6,a7,a8,a9,a10)=(c5,c,4,c3,c2,c1)= Matrix(GF(2), 5, 5, [0, 1, 1, 0, 1, 1,1,0,1,1,1,0,1,1,0,0,1,1,0,1,1,1,0,1,1]);
X;
X^-1;
[0 1 1 0 1]
[1 1 0 1 1]
[1 0 1 1 0]
[0 1 1 0 1]
[1 1 0 1 1]
>> X^-1;
^
Runtime error in '^': Argument 1 is not invertible
没逆距阵???肯定不是m序列-----》周期能最大,可还是可能不是m序列
次数 对应的分圆多项式
1 x-1
2 x+1
3 x2+x+1 4 x2+1
5 x4+x3+x2+x+1
6 x2-x+1
7 x6+x5+x4+x3+x2+x+1
8 x4+1
9 x6+x3+1
10 x4-x3+x2-x+1
11 x10+x9+x8+x7+x6+x5+x4+x3+x2+x+1
12 x4-x2+1
[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课
赞赏
他的文章
- [推荐]FPAG+RSA/ECC的新书 4892
- [注意]最新HASH SHA3公布 4913
- [转帖]美军网络司令部的徽章 6277
- [讨论]国内最快最安全电脑天河麒麟操作系统 4292
- [推荐]17173也被盗了。。。 2991
看原图
赞赏
雪币:
留言: