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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.