# Linear Feedback Shift Register Generator (M-series)

A pseudo-random number generator based on a recursive binary sequence:

${b}_{i}=({a}_{p}{b}_{i-p}+{a}_{p-1}{b}_{i-p+1}+\dots +{a}_{1}{b}_{i-1})\mathit{mod}2$ with constant coefficients $\underset{}{{a}_{p}}$ as well as sequence terms ${b}_{i}$ restricted to binary values. In practical applications most $\underset{}{{a}_{p}}$ are set to zero. In order to obtain an $l$ -bit pseudo-random integer, the binary sequence ${b}_{i}$ is iterated forward $l$ times and successive bits ${b}_{i}$ , ${b}_{i-1}$ , $\dots $ , ${b}_{i-l+1}$ form a binary representation of an $l$ -bit integer number. To obtain a pseudo-random floating-point number in the range [ $\mathrm{0,1}$ ) , the $l$ -bit integer must be further divided by $\underset{}{{2}^{l}}$ .

In practice the following simplified recursive sequence is used:

Since terms ${b}_{i}$ are binary this is equivalent to peforming the exclusive-OR (XOR) operation (in some implementations XOR has been replaced by XNOR):

▲Back to this TOP