NAME
Math::PRBS - Generate Pseudorandom Binary Sequences using an iterator-based Linear Feedback Shift Register
SYNOPSIS
use Math::PRBS;
my $x3x2 = Math::PRBS->new( taps => [3,2] );
my $prbs7 = Math::PRBS->new( prbs => 7 );
my ($i, $value) = $x3x2t->next();
my @p7 = $prbs7->generate_all();
my @ints = $prbs7->generate_all_int();
DESCRIPTION
This module will generate various Pseudorandom Binary Sequences (PRBS). This module creates a iterator object, and you can use that object to generate the sequence one value at a time, or en masse.
The generated sequence is a series of 0s and 1s which appears random for a certain length, and then repeats thereafter. (You can also convert the bitstream into a sequence of integers using the generate_int
and generate_all_int
methods.)
It is implemented using an XOR-based Linear Feedback Shift Register (LFSR), which is described using a feedback polynomial (or reciprocal characteristic polynomial). The terms that appear in the polynomial are called the 'taps', because you tap off of that bit of the shift register for generating the feedback for the next value in the sequence.
FUNCTIONS AND METHODS
Initialization
$seq = Math::PRBS-
new( key => value )>-
Creates the sequence iterator
$seq
using one of thekey => value
pairs described below.prbs => n
-
prbs
needs an integer n to indicate one of the "standard" PRBS polynomials.# example: PRBS7 = x**7 + x**6 + 1 $seq = Math::PRBS->new( prbs => 7 );
The "standard" PRBS polynomials implemented are
polynomial | prbs | taps | poly (string) ------------------+------------+-----------------+--------------- x**7 + x**6 + 1 | prbs => 7 | taps => [7,6] | poly => '1100000' x**15 + x**14 + 1 | prbs => 15 | taps => [15,14] | poly => '110000000000000' x**23 + x**18 + 1 | prbs => 23 | taps => [23,18] | poly => '10000100000000000000000' x**31 + x**28 + 1 | prbs => 31 | taps => [31,28] | poly => '1001000000000000000000000000000'
taps => [ tap, tap, ... ]
-
taps
needs an array reference containing the powers in the polynomial that you tap off for creating the feedback. Do not include the0
for thex**0 = 1
in the polynomial; that's automatically included.# example: x**3 + x**2 + 1 # 3 and 2 are taps, 1 is not tapped, 0 is implied feedback $seq = Math::PRBS->new( taps => [3,2] );
poly => '...'
-
poly
needs a string for the bitsx**k
downtox**1
, with a 1 indicating the power is included in the list, and a 0 indicating it is not.# example: x**3 + x**2 + 1 # 3 and 2 are taps, 1 is not tapped, 0 is implied feedback $seq = Math::PRBS->new( poly => '110' );
$seq->reset()
-
Reinitializes the sequence: resets the sequence back to the starting state. The next call to
next()
will be the initial$i,$value
again.
Iteration
$value = $seq->next()
($i, $value) = $seq->next()
-
Computes the next value in the sequence. (Optionally, in list context, also returns the current value of the i for the sequence.)
$seq->rewind()
-
Rewinds the sequence back to the starting state. The subsequent call to
next()
will be the initial$i,$value
again. (This is actually an alias forreset()
). $i = $seq->tell_i()
-
Return the current
i
position. The subsequent call tonext()
will return thisi
. $state = $seq->tell_state()
-
Return the current internal state of the feedback register. Useful for debug, or plugging into
->seek_to_state($state)
to get back to this state at some future point in the program. $seq->seek_to_i( $n )
$seq->ith( $n )
-
Moves forward in the sequence until
i
reaches$n
. Ifi > $n
already, will internallyrewind()
first. If$n > period
, it will stop at the end of the period, instead. $seq->seek_to_state( $lfsr )
-
Moves forward in the sequence until the internal LFSR state reaches
$lfsr
. It will wrap around, if necessary, but will stop once the internal state returns to the starting point. $seq->seek_forward_n( $n )
-
Moves forward in the sequence
$n
steps. $seq->seek_to_end()
$seq->seek_to_end( limit => $n )
-
Moves forward until it's reached the end of the the period. (Will start in the first period using
tell_i % period
.)If
limit =
$n> is used, will not seek beyondtell_i == $n
. @all = $seq->generate( n )
-
Generates the next n values in the sequence, wrapping around if it reaches the end. In list context, returns the values as a list; in scalar context, returns the string concatenating that list.
@all = $seq->generate_all( )
@all = $seq->generate_all( limit => $max_i )
-
Returns the whole sequence, from the beginning, up to the end of the sequence; in list context, returns the list of values; in scalar context, returns the string concatenating that list. If the sequence is longer than the default limit of 65535, or the limit given by
$max_i
if the optionallimit => $max_i
is provided, then it will stop before the end of the sequence. @all = $seq->generate_to_end( )
@all = $seq->generate_to_end( limit => $max_i )
-
Returns the remaining sequence, from whatever state the list is currently at, up to the end of the sequence; in list context, returns the list of values; in scalar context, returns the string concatenating that list. The limits work just as with
generate_all()
. @all = $seq->generate_int( $n )
-
Generates the next $n integers in the sequence, wrapping around if it reaches the end (it will generate just one if $n is missing). In list context, returns the values as a list; in scalar context, returns the string concatenating that list.
@all = $seq->generate_all_int( )
@all = $seq->generate_all_int( limit => $max_i )
-
Returns the whole sequence of
k
-bit integers, from the beginning, up to the end of the sequence; in list context, returns the list of values; in scalar context, returns the string concatenating that list. If the sequence is longer than the default limit of 65535, or the limit given by$max_i
if the optionallimit => $max_i
is provided, then it will stop before the end of the sequence.
Information
$i = $seq->description
-
Returns a string describing the sequence in terms of the polynomial.
$prbs7->description # "PRBS from polynomial x**7 + x**6 + 1"
$n = $seq->polynomial_degree
$n = $seq->k_bits
-
Returns the highest power
k
from the PRBS polynomial. As described in the "Theory" section, if you group a maximum length sequence sequence into groups ofk
bits, you will produce all thek
-bit numbers from1
to2**k - 1
.$seq = Math::PRBS->new( taps => [6,7] ); $k = $seq->k_bits(); # 7
When using
generate_int()
to generate the next integer in the sequence, it is consumingk_bits()
bits from the sequence to create the decimal integer.@integers = $seq->generate_int($num_ints); # consumes $seq->k_bits() bits of the sequence per integer generated
$i = $seq->taps
-
Returns an array-reference containing the list of tap identifiers, which could then be passed to
->new(taps => ...)
.my $old_prbs = ...; my $new_prbs = Math::PRBS->new( taps => $old_prbs->taps() );
$i = $seq->period( force => 'estimate' | $n | 'max' )
-
Returns the period of the sequence.
Without any arguments, will return undef if the period hasn't been determined yet (ie, haven't travelled far enough in the sequence):
$i = $seq->period(); # unknown => undef
If force is set to 'estimate', will return
period = 2**k - 1
if the period hasn't been determined yet:$i = $seq->period(force => 'estimate'); # unknown => 2**k - 1
If force is set to an integer
$n
, it will try to generate the whole sequence (up totell_i <= $n
), and return the period if found, or undef if not found.$i = $seq->period(force => $n); # look until $n; undef if sequence period still not found
If force is set 'max', it will loop thru the entire sequence (up to
i = 2**k - 1
), and return the period that was found. It will still return undef if still not found, but all sequences should find the period within2**k-1
. If you find a sequence that doesn't, feel free to file a bug report, including theMath::PRBS->new()
command listing the taps array or poly string; ifk
is greater than32
, please include a code that fixes the bug in the bug report, as development resources may not allow for debug of issues whenk > 32
.$i = $seq->period(force => 'max'); # look until 2**k - 1; undef if sequence period still not found
$i = $seq->oeis_anum
-
For known polynomials, return the On-line Encyclopedia of Integer Sequences "A" number. For example, you can go to https://oeis.org/A011686 to look at the sequence A011686.
Not all maximum-length PRBS sequences (binary m-sequences) are in OEIS. Of the four "standard" PRBS (7, 15, 23, 31) mentioned above, only PRBS7 is there, as A011686. If you have the A-number for other m-sequences that aren't included below, please let the module maintainer know.
Polynomial | Taps | OEIS ----------------------------------------------+-----------------------+--------- x**2 + x**1 + 1 | [ 2, 1 ] | A011655 x**3 + x**2 + 1 | [ 3, 2 ] | A011656 x**3 + x**1 + 1 | [ 3, 1 ] | A011657 x**4 + x**3 + x**2 + x**1 + 1 | [ 4, 3, 2, 1 ] | A011658 x**4 + x**1 + 1 | [ 4, 1 ] | A011659 x**5 + x**4 + x**2 + x**1 + 1 | [ 5, 4, 2, 1 ] | A011660 x**5 + x**3 + x**2 + x**1 + 1 | [ 5, 3, 2, 1 ] | A011661 x**5 + x**2 + 1 | [ 5, 2 ] | A011662 x**5 + x**4 + x**3 + x**1 + 1 | [ 5, 4, 3, 1 ] | A011663 x**5 + x**3 + 1 | [ 5, 3 ] | A011664 x**5 + x**4 + x**3 + x**2 + 1 | [ 5, 4, 3, 2 ] | A011665 x**6 + x**5 + x**4 + x**1 + 1 | [ 6, 5, 4, 1 ] | A011666 x**6 + x**5 + x**3 + x**2 + 1 | [ 6, 5, 3, 2 ] | A011667 x**6 + x**5 + x**2 + x**1 + 1 | [ 6, 5, 2, 1 ] | A011668 x**6 + x**1 + 1 | [ 6, 1 ] | A011669 x**6 + x**4 + x**3 + x**1 + 1 | [ 6, 4, 3, 1 ] | A011670 x**6 + x**5 + x**4 + x**2 + 1 | [ 6, 5, 4, 2 ] | A011671 x**6 + x**3 + 1 | [ 6, 3 ] | A011672 x**6 + x**5 + 1 | [ 6, 5 ] | A011673 x**7 + x**6 + x**5 + x**4 + x**3 + x**2 + 1 | [ 7, 6, 5, 4, 3, 2 ] | A011674 x**7 + x**4 + 1 | [ 7, 4 ] | A011675 x**7 + x**6 + x**4 + x**2 + 1 | [ 7, 6, 4, 2 ] | A011676 x**7 + x**5 + x**2 + x**1 + 1 | [ 7, 5, 2, 1 ] | A011677 x**7 + x**5 + x**3 + x**1 + 1 | [ 7, 5, 3, 1 ] | A011678 x**7 + x**6 + x**4 + x**1 + 1 | [ 7, 6, 4, 1 ] | A011679 x**7 + x**6 + x**5 + x**4 + x**2 + x**1 + 1 | [ 7, 6, 5, 4, 2, 1 ] | A011680 x**7 + x**6 + x**5 + x**3 + x**2 + x**1 + 1 | [ 7, 6, 5, 3, 2, 1 ] | A011681 x**7 + x**1 + 1 | [ 7, 1 ] | A011682 x**7 + x**5 + x**4 + x**3 + x**2 + x**1 + 1 | [ 7, 5, 4, 3, 2, 1 ] | A011683 x**7 + x**4 + x**3 + x**2 + 1 | [ 7, 4, 3, 2 ] | A011684 x**7 + x**6 + x**3 + x**1 + 1 | [ 7, 6, 3, 1 ] | A011685 x**7 + x**6 + 1 | [ 7, 6 ] | A011686 x**7 + x**6 + x**5 + x**4 + 1 | [ 7, 6, 5, 4 ] | A011687 x**7 + x**5 + x**4 + x**3 + 1 | [ 7, 5, 4, 3 ] | A011688 x**7 + x**3 + x**2 + x**1 + 1 | [ 7, 3, 2, 1 ] | A011689 x**7 + x**3 + 1 | [ 7, 3 ] | A011690 x**7 + x**6 + x**5 + x**2 + 1 | [ 7, 6, 5, 2 ] | A011691 x**8 + x**6 + x**4 + x**3 + x**2 + x**1 + 1 | [ 8, 6, 4, 3, 2, 1 ] | A011692 x**8 + x**5 + x**4 + x**3 + 1 | [ 8, 5, 4, 3 ] | A011693 x**8 + x**7 + x**5 + x**3 + 1 | [ 8, 7, 5, 3 ] | A011694 x**8 + x**7 + x**6 + x**5 + x**4 + x**2 + 1 | [ 8, 7, 6, 5, 4, 2 ] | A011695 x**8 + x**7 + x**6 + x**5 + x**4 + x**3 + 1 | [ 8, 7, 6, 5, 4, 3 ] | A011696 x**8 + x**4 + x**3 + x**2 + 1 | [ 8, 4, 3, 2 ] | A011697 x**8 + x**6 + x**5 + x**4 + x**2 + x**1 + 1 | [ 8, 6, 5, 4, 2, 1 ] | A011698 x**8 + x**7 + x**5 + x**1 + 1 | [ 8, 7, 5, 1 ] | A011699 x**8 + x**7 + x**3 + x**1 + 1 | [ 8, 7, 3, 1 ] | A011700 x**8 + x**5 + x**4 + x**3 + x**2 + x**1 + 1 | [ 8, 5, 4, 3, 2, 1 ] | A011701 x**8 + x**7 + x**5 + x**4 + x**3 + x**2 + 1 | [ 8, 7, 5, 4, 3, 2 ] | A011702 x**8 + x**7 + x**6 + x**4 + x**3 + x**2 + 1 | [ 8, 7, 6, 4, 3, 2 ] | A011703 x**8 + x**6 + x**3 + x**2 + 1 | [ 8, 6, 3, 2 ] | A011704 x**8 + x**7 + x**3 + x**2 + 1 | [ 8, 7, 3, 2 ] | A011705 x**8 + x**6 + x**5 + x**2 + 1 | [ 8, 6, 5, 2 ] | A011706 x**8 + x**7 + x**6 + x**4 + x**2 + x**1 + 1 | [ 8, 7, 6, 4, 2, 1 ] | A011707 x**8 + x**7 + x**6 + x**3 + x**2 + x**1 + 1 | [ 8, 7, 6, 3, 2, 1 ] | A011708 x**8 + x**7 + x**2 + x**1 + 1 | [ 8, 7, 2, 1 ] | A011709 x**8 + x**7 + x**6 + x**1 + 1 | [ 8, 7, 6, 1 ] | A011710 x**8 + x**7 + x**6 + x**5 + x**2 + x**1 + 1 | [ 8, 7, 6, 5, 2, 1 ] | A011711 x**8 + x**7 + x**5 + x**4 + 1 | [ 8, 7, 5, 4 ] | A011712 x**8 + x**6 + x**5 + x**1 + 1 | [ 8, 6, 5, 1 ] | A011713 x**8 + x**4 + x**3 + x**1 + 1 | [ 8, 4, 3, 1 ] | A011714 x**8 + x**6 + x**5 + x**4 + 1 | [ 8, 6, 5, 4 ] | A011715 x**8 + x**7 + x**6 + x**5 + x**4 + x**1 + 1 | [ 8, 7, 6, 5, 4, 1 ] | A011716 x**8 + x**5 + x**3 + x**2 + 1 | [ 8, 5, 3, 2 ] | A011717 x**8 + x**6 + x**5 + x**4 + x**3 + x**1 + 1 | [ 8, 6, 5, 4, 3, 1 ] | A011718 x**8 + x**5 + x**3 + x**1 + 1 | [ 8, 5, 3, 1 ] | A011719 x**8 + x**7 + x**4 + x**3 + x**2 + x**1 + 1 | [ 8, 7, 4, 3, 2, 1 ] | A011720 x**8 + x**6 + x**5 + x**3 + 1 | [ 8, 6, 5, 3 ] | A011721 x**9 + x**4 + 1 | [ 9, 4 ] | A011722 x**10 + x**3 + 1 | [ 10, 3 ] | A011723 x**11 + x**2 + 1 | [ 11, 2 ] | A011724 x**12 + x**7 + x**4 + x**3 + 1 | [ 12, 7, 4, 3 ] | A011725 x**13 + x**4 + x**3 + x**1 + 1 | [ 13, 4, 3, 1 ] | A011726 x**14 + x**12 + x**11 + x**1 + 1 | [ 14, 12, 11, 1 ] | A011727 x**15 + x**1 + 1 | [ 15, 1 ] | A011728 x**16 + x**5 + x**3 + x**2 + 1 | [ 16, 5, 3, 2 ] | A011729 x**17 + x**3 + 1 | [ 17, 3 ] | A011730 x**18 + x**7 + 1 | [ 18, 7 ] | A011731 x**19 + x**6 + x**5 + x**1 + 1 | [ 19, 6, 5, 1 ] | A011732 x**20 + x**3 + 1 | [ 20, 3 ] | A011733 x**21 + x**2 + 1 | [ 21, 2 ] | A011734 x**22 + x**1 + 1 | [ 22, 1 ] | A011735 x**23 + x**5 + 1 | [ 23, 5 ] | A011736 x**24 + x**4 + x**3 + x**1 + 1 | [ 24, 4, 3, 1 ] | A011737 x**25 + x**3 + 1 | [ 25, 3 ] | A011738 x**26 + x**8 + x**7 + x**1 + 1 | [ 26, 8, 7, 1 ] | A011739 x**27 + x**8 + x**7 + x**1 + 1 | [ 27, 8, 7, 1 ] | A011740 x**28 + x**3 + 1 | [ 28, 3 ] | A011741 x**29 + x**2 + 1 | [ 29, 2 ] | A011742 x**30 + x**16 + x**15 + x**1 + 1 | [ 30, 16, 15, 1 ] | A011743 x**31 + x**3 + 1 | [ 31, 3 ] | A011744 x**32 + x**28 + x**27 + x**1 + 1 | [ 32, 28, 27, 1 ] | A011745
THEORY
A pseudorandom binary sequence (PRBS) is the sequence of N unique bits, in this case generated from an LFSR. Once it generates the N bits, it loops around and repeats that seqence. While still within the unique N bits, the sequence of N bits shares some properties with a truly random sequence of the same length. The benefit of this sequence is that, while it shares statistical properites with a random sequence, it is actually deterministic, so is often used to deterministically test hardware or software that requires a data stream that needs pseudorandom properties.
In an LFSR, the polynomial description (like x**3 + x**2 + 1
) indicates which bits are "tapped" to create the feedback bit: the taps are the powers of x in the polynomial (3 and 2). The 1
is really the x**0
term, and isn't a "tap", in the sense that it isn't used for generating the feedback; instead, that is the location where the new feedback bit comes back into the shift register; the 1
is in all characteristic polynomials, and is implied when creating a new instance of Math::PRBS.
If the largest power of the polynomial is k
(ie, a polynomial of degree k
), there are k+1
bits in the register (one for each of the powers k
down to 1
and one for the x**0 = 1
's feedback bit). For any given k
, the largest sequence that can be produced is N = 2^k - 1
, and any sequence with that length is called a "maximum length sequence" or m-sequence; there can be more than one m-sequence for a given k
.
One useful feature of an m-sequence is that if you divide it into every possible partial sequence that's k
bits long (wraping from N-1 to 0 to make the last few partial sequences also k
bits), you will generate every possible combination of k
bits (*), except for k
zeroes in a row. (It then includes the binary representation of every k-bit integer from 1
to 2**k - 1
.) For example,
# x**3 + x**2 + 1 = "1011100"
"_101_1100 " -> 101 (5)
"1_011_100 " -> 011 (3)
"10_111_00 " -> 111 (7)
"101_110_0 " -> 110 (6)
"1011_100_ " -> 100 (4)
"1_0111_00 " -> 001 (1) (requires wrap to get three digits: 00 from the end of the sequence, and 1 from the beginning)
"10_1110_0 " -> 010 (2) (requires wrap to get three digits: 0 from the end of the sequence, and 10 from the beginning)
The Wikipedia:LFSR article lists some polynomials that create m-sequence for various register sizes, and links to Philip Koopman's complete list up to k=64
(see "REFERENCES" for links to both).
If you want to create your own polynonial to find a long m-sequence, here are some things to consider: 1) the number of taps for the feedback (remembering not to count the feedback bit as a tap) must be even; 2) the entire set of taps must be relatively prime; 3) those two conditions are necesssary, but not sufficient, so you may have to try multiple polynomials to find an m-sequence; 4) keep in mind that the time to compute the period (and thus determine if it's an m-sequence) doubles every time k
increases by 1; as the time increases, it makes more sense to look at the complete list up to k=64
), and pure-perl is probably tpp wrong language for searching k>64
.
(*) Since a maximum length sequence contains every k-bit combination (except all zeroes), it can be used for verifying that software or hardware behaves properly for every possible sequence of k-bits.
REFERENCES
Wikipedia:Linear-feedback Shift Register (LFSR) at https://en.wikipedia.org/wiki/Linear-feedback_shift_register
Article includes a list of some maximum length polynomials
Article links to Philip Koopman's complete list of maximum length polynomials, up to
k = 64
at https://users.ece.cmu.edu/~koopman/lfsr/index.html
Wikipedia:Pseudorandom Binary Sequence (PRBS) at https://en.wikipedia.org/wiki/Pseudorandom_binary_sequence
The underlying algorithm in Math::PRBS is based on the C code in this article's "Practical Implementation"
Wikipedia:Maximum Length Sequence (m-sequence) at https://en.wikipedia.org/wiki/Maximum_length_sequence
Article describes some of the properties of m-sequences
INSTALLATION
To install this module, use your favorite CPAN client.
For a manual install, type the following:
perl Makefile.PL
make
make test
make install
(On Windows machines, you may need to use "dmake" or "gmake" instead of "make", depending on your setup.)
SEE ALSO
Math::NumSeq - an iterator-based sequence generator, with a variety of numeric sequences that can be generated
The primary API for Math::PRBS was based on Math::NumSeq, but it was decided to not make Math::PRBS dependent on it, because Math::NumSeq does not seem to install on Windows.
Math::Sequence and Math::Series - generate sequences using symbolic forumla
Math::PSRG - Implements a (159, 31, 0) LFSR
AUTHOR
Peter C. Jones <petercj AT cpan DOT org>
Please report any bugs or feature requests thru the web interface at https://github.com/pryrt/Math-PRBS/issues
COPYRIGHT
Copyright (C) 2016,2018 Peter C. Jones
LICENSE
This program is free software; you can redistribute it and/or modify it under the terms of either: the GNU General Public License as published by the Free Software Foundation; or the Artistic License.
See http://dev.perl.org/licenses/ for more information.