Pseudo Random Binary Sequences (PRBS)

[D.I....@lut.ac.uk]

Hello All,

I am trying to find a way of generating a PRBS in software to use it as an
input into a filter. Does anyone out there know if there exists an m-file
in matlab which will do this for me or if there isn't an m-file, does any
one have an algorithm which will help me generate the sequence.

Please send a reply either direct to me or on the net.

Any help is much appreciated.

Thanks in advance.

Dipesh.
(D.I....@lut.ac.uk)

[Michael Altmann]

el...@hpc.lut.ac.uk writes:

>I am trying to find a way of generating a PRBS in software to use it
as an >input into a filter. Does anyone out there know if there exists
an m-file >in matlab which will do this for me or if there isn't an
m-file, does any >one have an algorithm which will help me generate the
sequence.

There are two ways that I have found to generate an LFSR (Linear
feedback shift register), the time honored method of generating
Pseudo-Random data.

Way #1 - if the LFSR is short (less than 8 taps or so). Set up the
feedback taps as an IIR. Apply an impulse, using filt(), then modulo-2
the output (ie. rem(x,2)). As long as the taps have magnitude 0 or 1
this works very fast.

Way #2 - This is slower, but the LFSR size is only limited by memory
capacity. The for/end loop steps through all the possible states of
the LFSR. If you use a 24-tap LFSR, this means 16777215 loops (don't
bother trying this unless you have a Cray). The m-file is below.

************************* Cut Here ***********************************
% This generates a pseodo-random bitstream using an LFSR. It requires
% a polynomial generator function. Format is:
%
% out=lfsr(taps)
%
function out=lfsr(taps)
taps=taps(:);
l=length(taps);
states=2^l-1;
bin_const=flipud(logspace(0,log10(2^(l-1)),l)');
out=zeros(states,1) ;
reg_val=zeros(states,1) ;
reg=ones(size(taps));
for i=1:(states)
reg=[rem(sum(taps.*reg),2) ; reg(1:l-1)];
out(i)=reg(l) ;
reg_val(i)=sum(reg.*bin_const);
end ;
max_step=max(abs(diff(sort(reg_val))));
min_step=min(abs(diff(sort(reg_val))));
if abs(max_step-min_step)<0.5 ;
disp(['lfsr: Maximal length sequence']) ;
end ;
************************* Cut Here ***********************************

Example 'taps' vectors:

taps=[1 0 1] (length=7)
taps=[1 0 0 1] (length=15)
taps=[1 1 0 1 1] (length=31)
taps=[0 0 1 1 0 1 0 0 1] (length=511)

The taps here are specified backwards compared to most tables (sorry)
which specify the most significant (output) tap first.

.../Mike (mi...@bnr.ca)

(Un)official BNR Disclaimer:
NO guarantees that any of this will work.
Any bugs are your problem (but it works for me).

[Alexandra Schmidt]

In article <CBnD9...@lut.ac.uk> D.I....@lut.ac.uk writes:
>Hello All,
>
>I am trying to find a way of generating a PRBS in software to use it as an
>input into a filter. Does anyone out there know if there exists an m-file
>in matlab which will do this for me or if there isn't an m-file, does any
>one have an algorithm which will help me generate the sequence.

A function doing what you describe (and called prbs) is included with the Xmath
Interactive System Identification Module.

Lacking access to a copy of Xmath, you can find a discussion of the algorithm
in: "Generation and Properties of Maximum-Length Sequences', parts 1-3, W.D.T.
Davies, Control, June/July/August 1966.

Good luck!

. . .Alexandra

*----------------------------------------------------------------------*
| Alexandra Schmidt Xmath Product Engineer |
| Phone: (408) 980-1500 x345 Integrated Systems, Inc. |
| Internet: al...@isi.com 3260 Jay St. |
| Voice mail: (408) 980-1590 x345 Santa Clara, CA 95054 |
*----------------------------------------------------------------------*"

[Craig A. Blome]

In article <CBnD9...@lut.ac.uk> D.I....@lut.ac.uk writes:

>I am trying to find a way of generating a PRBS in software to use it as an
>input into a filter. Does anyone out there know if there exists an m-file

Check out "A Hybrid Design of Maximum Length Sequence Generators" by L.T. Wang
and E.J. McCluskey in the Proceedings of the 1986 IEEE Test Conference. For
your purposes, the introduction and reference list would be of interest, and
also the list of primitive polynomials included in the paper. I have
implemented an algorithm which implements "shift registers" in software by
doing a right shift on a memory location, testing the bit shifted off the end,
and if this bit is set then exclusive-OR'ing the result by a mask which is
based on a primitive polynomial for the particular register length. My code
is in horribly illegible C, but if you're interested I will attempt to clean
it up and forward it. (It's mostly interesting as evidence that this sort of
thing ought really to be done in hardware :-)

While we're here, I'll put in a plug for the book *Number Theory in Science and
Communication* by Manfred R. Schroeder, which contains an excellent intro to
the subject of Galois fields and maximum length sequences.

Regards,
Craig Blome
Electrical and Computer Engineering
The University of Texas at Austin