Linear feedback shift registers (LFSRs), or their software implementations, are used to generate pseudo-random binary sequences (PRBS, also referred to as pseudo-random bit sequences) which are largely used in telecommunication (data scrambling, sync and/or test patterns, field delimiter markers, jamming, stream ciphers, bit-error rate tests, ...).

The feedback is formed by XORing or XNORing the outputs of selected stages of the shift register - referred to as

LFSRs are described by their characteristic polynomial: for example a tap sequence of 4, 3 describes the polynomial x^4+x^3+1 (a 4-bit shift-register):

Below a table of the polynomials you may find in this blog is shown along with the systems where they are employed; the LFSR polynomials used in STANAG, MIL-STD, and FED standards are not listed.

The feedback is formed by XORing or XNORing the outputs of selected stages of the shift register - referred to as

*taps*- and then inputting this to the least significant bit (stage 0). The list of the taps is known as the*tap sequence*. It is this feedback that causes the register to loop through repetitive sequences of pseudo-random value.LFSRs are described by their characteristic polynomial: for example a tap sequence of 4, 3 describes the polynomial x^4+x^3+1 (a 4-bit shift-register):

Below a table of the polynomials you may find in this blog is shown along with the systems where they are employed; the LFSR polynomials used in STANAG, MIL-STD, and FED standards are not listed.

```
```

polynomial
m-sequence
referring post *(used as)*
x^31+x^3+1

KW-46 encryption *(sync)*
x^11+x^9+1 Y CIS 81-81 T-206 *(scrambler?)*
x^9+x^5+1 Y 100-50Bd/500 FSK-2 *(sync/test pattern)*

CIS-12 (T-230) *(sync/test pattern)*
x^8+x^6+x+1

SAAB GRINTEG MHF 50

CIS-75 (128-bit)
x^7+x^6+1 Y CIS-75 126-bit *(sync/test pattern, one bit in error)*

French-Ny 50Bd/850 FSK-2 *(marker)*
x^7+x^5+x+1

50Bd/500 FSK-2
x^7+x^3+1

Swiss Army TC-535 *(PN sequence generator)*
x^6+x^5+1 Y French-Ny 50Bd/850 FSK-2 *(marker*)

300Bd/500 FSK-2 *(scrambler?)*
x^5+x^4+x+1 50Bd/500 FSK-2
x^5+x^4+1 CIS-11 idle signal β
x^4+x^3+1 Y CIS-Ny "Akula" *(scrambler)*
x^3+x^2+1 Y CIS-11 idle signal α *(used as sync/test in d0-d4,s0-s1 bits)*

Some notes (...remember, google is your friend).

Any PRBSn sequence will have a word length of n bits and a max sequence length of 2^n - 1 bits (also termed period T). The maximum periodicity of the sequence can only be achieved through XOR-ing only some combinations of a few particular stages of the LFSR: if the produced sequence has the maximum periodicity (T=2^n -1) then that sequence is known as *m-sequence *and its characteristic polynomial is termed* primitive polynomial.*

Properties of m-sequences:

1) Balance property. In every period, the number of zeros is nearly equal to the number of ones (the disparity does not exceed 1);

2) Run property. In every period, half of the run have length 1, one fourth have length 2, one eighth have length 3, and so on. For each of these lengths there are the same number of runs of 0’s and runs of 1’s;

3) Two level autocorrelation. The autocorrelation function (ACF) is two-valued.

For example, the sequence generated by x^6+x^5+1:

s=[0 0 0 0 1 1];

t=[6 5];

1. BALANCE PROPERTY

The Code satisfies Balance Property

number of 1s and 0s are 32 31

2. RUN LENGTH PROPERTY

The code satisfies RUN LENGTH property

The run length is as follow

16 8 4 2 1 1

3. AUTOCORRELATION PROPERTY

The Code satisfies the Autocorrelation Property

* *

Verifications are performed using the GNU Octave script *LFSR_test.m* downloadable from here:

https://yadi.sk/d/BcSqKC4irswK3g

Obviously, initaliting the LFSR stages with one of the the possible initial states (also termed as *seeds*) the m-sequence is always the same: just change the "starting point". Below the 63-bit m-sequence generated by the 6,5 LFSR (x^6+x^5+1) in case of four different initial states (000001, 100001, 100100, 101010):

With short sequence lengths the pattern is repeated many times, which has the effect of reducing the randomness of the signal, especially at higher bit rates. Long sequence lengths offer more randomness, however they have the disadvantage of taking a longer time to complete the entire sequence, which can be a issue at lower bit rates.
Notice that although a PRBS sequence demonstrates random behaviour, it is in fact generated deterministically and the bit sequence (short or long) will always be the same when repeated. By the way, a truly random sequence would be unusable, since receiving equipment would have no idea what was actually sent.

## No comments:

## Post a comment