Naive LFSR(线性反馈移位寄存器)是什么?将编程语言翻译成数学表达式。

3
存在一个数学问题,即生成n个唯一随机数的问题(随机数是N {0,...,n}元素,类似于排列,但不使用内存)。
最近我解决了这个问题,并且得到了一些结果(在没有使用正式数学的情况下,只是通过编程)。
似乎这个问题早已被Galois或其他数学家构建的LFSR(线性反馈移位寄存器)解决过。(实际上,我首先发现了LFSR,然后构建了我的“某种”解决方案,因为我无法理解维基上的LFSR文章,也不想简单地复制粘贴源代码)
问题在于,我一字不懂正式的数学语言,想要学习并将我的解决方案与LFSR进行比较,所以问题是:
您能否将我所做的与那个东西进行比较,并以某种方式将其翻译成正式数学语言及其相反的结构,以便我可以理解我所做的事情以及正式数学家所做的事情(以及他们为什么需要它)?
请记住,我的语言是编程语言,我只理解内存及其寻址,内存状态,零和一串等,我不理解原始多项式,域理论和其他数学术语。
非常感谢您的帮助,如果您能帮助我,我将在见到您时为您买一杯啤酒。
以下是我的代码(您可以在浏览器中运行它,我不会说它是正确的,但我相信想法应该接近,我缺乏任何其他解决方法。):
<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
请使用“您”代替“你”。 - Jason S
1个回答

2
线性反馈移位寄存器(LFSR)是确定性的,即它不使用任何随机数函数。因此,您的代码很可能不模拟LFSR。如果您不知道多项式环或有限域理论的任何内容,则很难解释LFSR背后的数学。然而,一个正确的LFSR会生成所谓的m序列的n位数字单词,其中n是LFSR中级数的数量。序列的长度为2 ^ n-1个单词(零单词不在序列中)。通常,我们只关心序列中单词的一个比特位置。(在Galois LFSR中,这通常是按惯例的0位,但实际上所有位具有相同的属性)。从每个单词中提取出这个单一位,形成一个2 ^ n-1位长的比特序列,具有以下与随机性相关的著名数学特性:
平衡特性:当序列长度趋近于无穷大时,序列中的1的数量接近0的数量。序列中1的数量实际上始终比0的数量多一个。请注意,序列长度为奇数,因此1的数量和0的数量不能相等。
运行特性:m + 1长度的运行次数是m长度运行次数的一半。 m长度运行是所有1或所有0的m长度比特序列。
相关特性:随着序列长度趋近于无穷大,序列的自相关趋近于零* [*更精确地说是Kronecker delta函数]。也就是说,如果将序列与其向左或向右移动t位(其中t不等于序列长度)后进行比较,则比较相等的比特位置数大致相等于比较不相等的位置数。实质上,这意味着序列不包含周期性子序列。
您可以将代码的结果与这些特性进行比较,并得出自己的结论,以了解结果与LFSR的近似程度。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接