naive LFSR，将编程语言转换为数学
有一个数学问题，它是生成n个唯一随机数序列的问题(随机数是N{ 0，...，n }的元素，(类似于排列，但不使用内存)
最近我解决了这个问题，我确实得到了一些结果(读起来很棒，没有使用形式数学，只是通过编程)。
而这个问题过去似乎已经被伽罗瓦或其他数学家通过构造线性反馈移位寄存器( LFSR )来解决了。(我首先发现了LFSR，然后构建了我的“某种”解决方案，因为我不能理解维基上的LFSR文章，也不想只复制粘贴源代码)
问题是，我对正式数学一窍不通，我想学习它，并将我的解决方案与LFSR的解决方案进行比较，所以问题是：
你能不能把我做的东西和那个东西进行比较，然后把它转化成形式数学，反之亦然。这样我就可以理解我做了什么和正式的数学家做了什么(以及他们为什么需要它)？
记住，我的语言是编程，我只懂内存及其寻址，内存状态，0和1组成的字符串，等等，我不懂本原多项式，场论和其他数学术语。
提前谢谢你，如果你能帮我，我见到你的时候会给你买瓶啤酒。
下面是我的代码(你可以在浏览器中运行它，我不是说它是正确的，但我相信想法应该是接近的，我缺乏任何其他想法来解决它。)：
<html>
<head>
<script>
//-------------------------------------------------
function getPlacement( num ){ //; knuth permutations
var places = [];
for( var i = 0; i < num; ++i )
places.push( i );
var last_index = num-1;
for( var i = num; i > 0; --i ){
var rnd_index = Random( i );
places = swap( places, rnd_index, last_index );
last_index--;
}
return places;
}
function readNum( num, placement ){
var numstr = num.toString(2);
numstr = zeroextend( numstr, placement.length );
var numarr = numstr.split('');
var ret = [];
for( var i = 0; i < placement.length; ++i ){
ret.push( numarr[ placement[i] ] );
}
return ret.join('');
}
function UniqRndSeq( maxLength, output ){
var placesNeeded = maxLength.toString(2).length;
var randomPlacement = getPlacement( placesNeeded );
var initPosition = Random( maxLength );
var cnt = initPosition;
var rndn;
var numret = [];
do{
rndn = parseInt( readNum( cnt, randomPlacement ), 2);
output( rndn );
if( Containz( numret, rndn ) ) alert(rndn);
numret.push(rndn);
++cnt;
cnt = cnt % maxLength;
} while( cnt != initPosition );
}
//-------------------------------------------------
//; helper funs
var outp = [];
function display( num ){
outp.push( num + "<br>" );
}
function Random( x ){
return Math.floor(Math.random()*x);
}
function Containz( arr, num ){
for( var i = 0; i < arr.length; ++i ){
if( arr[i] == num ) return true;
}
return false;
}
function swap( list, a, b ){
var tmp = list[a];
list[a] = list[b];
list[b] = tmp;
return list;
}
function zeroextend( num_bin_str, length ){
while( num_bin_str.length != length ){
num_bin_str = "0" + num_bin_str;
}
return num_bin_str;
}
//-------------------------------------------------
function init(){
UniqRndSeq( 256, display);
document.body.innerHTML = outp.join('');
}
</script>
</head>
<body onload="init();">
</body>
</html>回答 1
Stack Overflow用户
发布于 2011-03-20 22:50:32
线性反馈移位寄存器(LFSR)是确定性的，即它不使用任何形式的随机数函数。因此，您的代码不太可能对LFSR进行建模。如果你对多项式环或有限域理论一无所知，就很难解释LFSR背后的数学原理。然而，正确的LFSR会产生所谓的n位数字字的m序列，其中n是LFSR中的级数。序列的长度为2^n -1个字(零字不在序列中)。一般来说，我们只关心序列中单词中的一个比特位置。(在Galois LFSR中，按照惯例，这通常是0位，但实际上所有位都具有相同的属性)。当从每个字中提取时，该单个比特形成2^n -1长度的比特序列，该序列具有以下与随机性相关的众所周知的数学特性：
平衡属性：当序列的长度接近无穷大时，序列中1的数量接近0的数量。序列中1的个数实际上总是比0的个数大1。请注意，序列长度是奇数，所以1和0的个数不能相等。
管路属性：m+1长度管路的数量是m长度管路数量的一半。M长度游程是全1或全0的m长度比特序列。
Kronecker相关特性：当序列的长度接近无穷大时，序列的自相关趋于零*更准确地说，是一个增量函数。也就是说，如果取该序列并将其与自身在时间上移位t个比特进行比较，其中t不等于序列长度，则比较相等的比特位置的数目大致等于比较不相等的位置的数目。从本质上讲，这意味着序列中没有周期性的子序列。
您可以将代码的结果与这些属性进行比较，并得出您自己的结论，即结果与LFSR有多接近。
https://stackoverflow.com/questions/5368405
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号