4
$\begingroup$

I find confusing some examples I have seen. Maybe you can help me to determine what is going on with them.

A Generalized Feedback Shift Register (GFSR) sequence defines a sequence $\{W_{i}\}$ satisfying the equation

$$W_{k+p}=c_{0}W_{k}\bigoplus c_{1}W_{k+1}\bigoplus...\bigoplus c_{p-1}W_{k+p-1} \qquad \qquad (1)$$

where $\bigoplus$ is the binary exclusive-or operation.

If the polynomial $f(x)=c_{0}+c_{1}x+c_{2}x^{2}+...+c_{p-1}x^{p-1}+x^{p}$ is a primitive polynomial over $GF(2)$, then the sequence $\{W_{i}\}$ will have maximal sequence $2^{p}-1$.

Example 1: Let's consider the trinomial $1+x+x^{4}$ and a bit sequence $1, 0, 1, 0$. For the polynomial we have $c_{0}=1$, $c_{1}=1$, $c_{2}=0$, $c_{3}=0$ and $p=4$. Therefore, the equation $(1)$ should be $W_{k+4}=W_{k}\bigoplus W_{k+1}$. According to this, we calculate the values for $W_{5}, W_{6},...$ etc (since we already know that $W_{1}=1, W_{2}=0, W_{3}=1, W_{4}=0$).

This procedure generates the following sequence

$$1,0,1,0,1,1,1,1,0,0,0,1,0,0,1$$

Then the example takes 4 bit chunks (changing to decimal representation):

$1010=10, 1111=15, 0001=1, 0011=3, 1010+1111=0101=5, 0001+0011=0010=2$ and so on. So a '4-wise decimation' using the recurrence yields the numbers

$$10, 15, 1, 3, 5, 2, ...$$

Is this a standard way to generate a bigger sequence?

Example 2:

By the using the bit stream from the trinomial $1+x+x^{4}$ and the starting sequence $1,0,1,0$, and... forming 4-bit words by putting the bits into a fixed binary position with a delay of 3 between binary positions, we have $$1010=10, 1110=14, 0011=3, 0101=5, 1111=15, 0001 = 1, 0010=2, 0111=7,...$$

Well, both examples are dealing with exactly the same problem. However, they lead to different sequences. I don't even know how the second example generates its sequence (it looks like it is taking the first bit sequence $1, 0, 1, 0$ and applying the binary exclusive-or operation for the first two terms $1 \bigoplus 0 = 1$ which is the first term of the following bit sequence, then take the second and third terms $0 \bigoplus 1=1$ which is the second term of the new sequence and so on). However, I don't know how it gets the last term. Such a pattern works for all the sequences of the Example 2, which makes me thing that I'm not seeing the full picture.

Ideas?

1 Answers 1

1

I just read "Generalized Feedback Shift Register Pseudorandom Number Algorithm" by T. G. Lewis and W. H. Payne. I think that paper settles the question I was raising (going to the source, right?). In essence, the question is "What is the correct procedure to use the Generalized Feedback Shift Register Algorithm (GFSR)?".

1.- Start with a sequence and a primitive polynomial $x^{p}+x^{q}+1$. For example, $a_{0}=a_{1}=a_{2}=a_{3}=a_{4}=1$ and $x^{5}+x^{2}+1$.

2.- Elements of the sequence follow $a_{k}=a_{k-p+q}\bigoplus a_{k-p}$ with $k=p, p+1,...$. In this example, since we have the first 5 elements of the sequence and according to the polynomial, we are given that $p=5, q=2$. Therefore, we can know the next elements of the sequence

\begin{matrix} a_{6}=a_{3}\bigoplus a_{1}=0 \\ a_{7}=a_{4}\bigoplus a_{2}=0 \\ a_{8}=a_{5}\bigoplus a_{3}=1 \\ a_{9}=a_{6}\bigoplus a_{4}=1 \\ ... \\ \end{matrix}

So, in this way we construct the rest of the sequence:

$\{a_{i}\}_{0}^{30}={1111100011011101010000100101100}$

In order to produce a better random sequence, we apply Kendall's algorithm. Although there are several variations of Kendall's algorithm, the point is to shift the original sequence $1111100011011101010000100|101100$ forwards by 6 bits, that is, $1011001111100011011101010|000100$. And again three times more (until we are back with the original sequence). This process gives the following sequence

\begin{matrix} \text{Key} & \text{Sequence} \\ 0 & \|11111\|00011011101010000100|101100\\ 1 & 1011001111100011011101010|000100\\ 2 & 0001001011001111100011011|101010\\ 3 & 101010000100101100111100|011011\\ 4 & 0110111010100001001011001|111100 \end{matrix}

Finally, we take n-tuples (in this example, 5-tuples are used) which are positioned as the columns of a new array:

\begin{matrix} W_{0}: & \|1\|1010 & W_{10}: & 01001& W_{20}: & 00111\\ W_{1}: & \|1\|0001 & W_{11}: & 10000& W_{21}: & 01111\\ W_{2}: & \|1\|1011 & W_{12}:& 10110& W_{22}: & 10010\\ W_{3}: & \|1\|1100 & W_{13}:& 10100& W_{23}: & 01100\\ W_{4}: & \|1\|0011 & W_{14}:& 01110& W_{24}: & 00101\\ W_{5}: & 00001 & W_{15}:& 11111& W_{25}: & 10101\\ W_{6}: & 01101 & W_{16}:& 00100& W_{26}: & 00011\\ W_{7}: & 01000 & W_{17}:& 11000& W_{27}: & 10111\\ W_{8}: & 11101 & W_{18}:& 01011& W_{28}: & 11001\\ W_{9}: & 11110 & W_{19}:& 01010& W_{29}: & 00110 \end{matrix}

Each $W_{i}$ is called a 'word'.

Since each column obeys the recurrence $a_{k}=a_{k-p+q}\bigoplus a_{k-p}$, each word must also obey $W_{k}=W_{k-p+q}\bigoplus W_{k-p}$.

As far as I know, that's the correct procedure for using the GFSR algorithm.

Corrections or comments will be appreciated.