The prbs Reference Manual

Table of Contents

Next: , Previous: , Up: (dir)   [Contents][Index]

The prbs Reference Manual

This is the prbs Reference Manual, version 0.1.0, generated automatically by Declt version 2.3 "Robert April" on Tue Jan 09 15:31:56 2018 GMT+0.


Next: , Previous: , Up: Top   [Contents][Index]

1 Introduction

prbs

Library of pseudo-random binary sequence generators (LFSR-2 and LFSR-4) and related functions in Common Lisp.

Overview

This is a library of higher-order functions that will generate PRBS sequences of degree 3 through 786, 1024, 2048, and 4096. The closures produced by these functions will generate sequences as bitvectors, byte arrays, lists of bit-vectors, or lists of unsigned integers.

Other functions are included for detecting and tracking errors in PRBS data and finding the degree of unknown PRBS data.

Sequence Generation

The smallest PRBS sequence is PRBS-3, which is only 21 bits long.

(ql:quickload :prbs)
(use-package :prbs)

(funcall (bit-gen 3) 21)
=> #*010101011111110100001

Once a generator is created, subsequent calls to it will generate more data. Sequences repeat once they reach the end.

(defvar gen (num-gen 5))
=> GEN

(funcall gen 20)
=> (2 5 11 22 13 26 21 10 20 8 17 3 7 14 29 27 23 15 31 30)

(funcall gen 20)
=> (28 25 18 4 9 19 6 12 24 16 1 2 5 11 22 13 26 21 10 20)

Generators can be seeded with an integer value such as the current time in seconds. Otherwise they are seeded with the value 2, which makes the final value in the sequence always be 1. This is convenient for testing purposes but it makes early values in the sequence "zero heavy".

(defvar bytes (byte-gen 31))
=> BYTES

(funcall bytes 20)
=> #(0 0 0 4 0 0 0 16 0 0 0 64 0 0 1 0 0 0 4 0)

(setq bytes (byte-gen 31 :seed (get-universal-time)))
=> #<CLOSURE (LAMBDA (&OPTIONAL (PRBS::C 1)) :IN BYTE-GEN) {10030EA65B}>

(funcall bytes 20)
=> #(181 114 141 52 213 202 52 215 87 40 211 85 92 163 77 85 114 141 53 85)

Bit Error Detection

PRBS sequences are often used to characterize the error rate in communication links. If you generate packets of PRBS data and send them across an unreliable link, the received packets can be analyzed to determine the error rate of the comm link.

Assume that you have created packets of data for transmission:

(let ((gen (byte-gen 33 :seed (get-universal-time))))
     ...
     (transmit (funcall gen 40))
     ...
     (transmit (funcall gen 40))
     ...

In this case, 40-byte packets from PRBS-33 are being transmitted. Across the link, once any packet is received it can be used to "lock" on the PRBS sequence:

(ql:quickload :prbs)
(use-package :prbs.err)

(let ((tracker (prbs-lock (receive-packet-data ...) 33)))

The prbs-lock function will use the available data to locate where it is in the sequence and initialize a PRBS generator of its own that it uses to predict future data. Any arriving data that does not match the prediction is considered an error.

       (funcall tracker (receive-packet-data ...))
=> total-errors total-bits
       ...
       (funcall tracker (receive-packet-data ...))
=> total-errors total-bits
       ...

See sender.ros and recv.ros in the test folder for an example that does this with UDP datagrams.

Sequence Detection

Someday you might encounter some data that you suspect is from a PRBS, but you are not sure which one.

(ql:quickload :prbs)
(use-package '(prbs prbs.err prbs.util) :cl-user)

(prbs-detect (bytes->bits (loop repeat 75 collect (random 255))) :max 100)
=> NIL

(prbs-detect (take 600 (bit-gen 45 :seed (get-universal-time) :start 11)) :max 100)
=> (45)

As expected, a 75-byte sample of random data does not match any PRBS sequence. However, a 75-byte sample (600 bits) from PRBS-45 taken at an arbitrary non-aligned bit offset is enough to uniquely identify the sequence -- not bad considering the full PRBS-45 sequence is almost 200 terabytes long.

API Reference

API Reference

License

MIT


Next: , Previous: , Up: Top   [Contents][Index]

2 Systems

The main system appears first, followed by any subsystem dependency.


Previous: , Up: Systems   [Contents][Index]

2.1 prbs

Author

Jason Lowdermilk <jlowdermilk@gmail.com>

License

MIT

Description

A library of higher-order functions for generating Pseudo-Random Binary Sequences of (practically) any degree

Version

0.1.0

Source

prbs.asd (file)

Component

src (module)


Next: , Previous: , Up: Top   [Contents][Index]

3 Modules

Modules are listed depth-first from the system components tree.


Previous: , Up: Modules   [Contents][Index]

3.1 prbs/src

Parent

prbs (system)

Location

src/

Components

Next: , Previous: , Up: Top   [Contents][Index]

4 Files

Files are sorted by type and then listed depth-first from the systems components trees.


Previous: , Up: Files   [Contents][Index]

4.1 Lisp


Next: , Previous: , Up: Lisp files   [Contents][Index]

4.1.1 prbs.asd

Location

prbs.asd

Systems

prbs (system)


Next: , Previous: , Up: Lisp files   [Contents][Index]

4.1.2 prbs/src/taps.lisp

Parent

src (module)

Location

src/taps.lisp

Packages

prbs.taps

Exported Definitions

taps (function)

Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

4.1.3 prbs/src/util.lisp

Parent

src (module)

Location

src/util.lisp

Packages

prbs.util

Exported Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

4.1.4 prbs/src/prbs.lisp

Parent

src (module)

Location

src/prbs.lisp

Packages

prbs

Exported Definitions
Internal Definitions

prbs-n (function)


Previous: , Up: Lisp files   [Contents][Index]

4.1.5 prbs/src/err.lisp

Parent

src (module)

Location

src/err.lisp

Packages

prbs.err

Exported Definitions
Internal Definitions

make-tracker (function)


Next: , Previous: , Up: Top   [Contents][Index]

5 Packages

Packages are listed by definition order.


Next: , Previous: , Up: Packages   [Contents][Index]

5.1 prbs.taps

Source

taps.lisp (file)

Use List

common-lisp

Used By List

prbs

Exported Definitions

taps (function)

Internal Definitions

Next: , Previous: , Up: Packages   [Contents][Index]

5.2 prbs.util

Source

util.lisp (file)

Use List

common-lisp

Used By List
Exported Definitions

Next: , Previous: , Up: Packages   [Contents][Index]

5.3 prbs

Source

prbs.lisp (file)

Use List
Used By List

prbs.err

Exported Definitions
Internal Definitions

prbs-n (function)


Previous: , Up: Packages   [Contents][Index]

5.4 prbs.err

Source

err.lisp (file)

Use List
Exported Definitions
Internal Definitions

make-tracker (function)


Next: , Previous: , Up: Top   [Contents][Index]

6 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


Next: , Previous: , Up: Definitions   [Contents][Index]

6.1 Exported definitions


Previous: , Up: Exported definitions   [Contents][Index]

6.1.1 Functions

Function: bit-gen N &key SEED START

=> lambda (x)

Create a closure representing PRBS-‘N‘. The lambda takes a single argument which is the number of the next bits to generate from the sequence (default 1 bit). The bits will be returned as a bitvector. ‘SEED‘ can be provided as the integer value of the initial vector. If ‘START‘ is provided, the generator will be initialized to that bit offset.

Package

prbs

Source

prbs.lisp (file)

Function: bitbv N

Turn a 1 or 0 into a single-bit bitvector.

Package

prbs.util

Source

util.lisp (file)

Function: bv->num B &optional M A

Convert a bitvector into an integer.

Package

prbs.util

Source

util.lisp (file)

Function: bvlist-gen N &key SEED

=> lambda (x)

Create a closure representing PRBS-‘N‘. The lambda takes a single argument which is the number of the next ‘N‘-bit bitvectors to generate from the sequence (default 1 value), which will be returned in a list. ‘SEED‘ can be provided as the integer value of the initial vector.

Package

prbs

Source

prbs.lisp (file)

Function: byte-gen N &key SEED

=> lambda (x)

Create a closure representing PRBS-‘N‘. The lambda takes a single argument which is the number of the next byte values to generate from the sequence (default 1 byte), which will be returned as a simple array of type (unsigned-byte 8). ‘SEED‘ can be provided as the integer value of the initial vector.

Package

prbs

Source

prbs.lisp (file)

Function: bytes->bits B

Convert a list of integer values into a single bytevector.

Package

prbs.util

Source

util.lisp (file)

Function: make-prbs N &key SEED

=> lambda ()

Create a closure representing PRBS-‘N‘. Each call to the lambda will return the next bitvector of length ‘N‘ in the prbs-‘N‘ sequence. ‘SEED‘ can be provided as the integer value of the initial vector.

Package

prbs

Source

prbs.lisp (file)

Function: num->bv VAL &optional SIZE

Convert an integer into a bitvector. Specify ‘SIZE‘ if you want something other than 8 bits per value.

Package

prbs.util

Source

util.lisp (file)

Function: num-gen N &key SEED

=> lambda (x)

Create a closure representing PRBS-‘N‘. The lambda takes a single argument which is the number of the next integer values to generate from the sequence (default 1 value), which will be returned in a list. ‘SEED‘ can be provided as the integer value of the initial vector.

Package

prbs

Source

prbs.lisp (file)

Function: prbs-detect P &key MAX

Attempt to identify which PRBS sequences the bitvector ‘P‘ belongs to. Return a list of all candidate polynomial degrees (up to ‘MAX‘) that can generate ‘P‘.

Package

prbs.err

Source

err.lisp (file)

Function: prbs-lock P N &optional REM

=> lambda (x)

Attempt to lock on a PRBS-‘N‘ sequence using the bitvector ‘P‘. If successful, return a lambda that tracks bit errors for subsequent data in the sequence, or nil if unable to lock. The lambda can be repeatedly called with a bitvector containing subsequent data, and it will return the total number of bit errors detected and the total number of bits it has seen.

Package

prbs.err

Source

err.lisp (file)

Function: seq-length N

return the number of bits in PRBS-‘N‘

Package

prbs

Source

prbs.lisp (file)

Function: sfind P N

=> bit offset where ‘P‘ occurs in PRBS-‘N‘, or nil if not found

Brute-force search a PRBS-‘N‘ sequence for an arbitrary bit pattern.

Package

prbs.err

Source

err.lisp (file)

Function: sfind-all P N

=> list of all bit offsets where ‘P‘ occurs in PRBS-‘N‘

Brute-force search a PRBS-‘N‘ sequence for all matches of an arbitrary bit pattern.

Package

prbs.err

Source

err.lisp (file)

Function: take N GEN

=> ‘N‘ values from ‘GEN‘

‘GEN‘ can be a lambda returned from any of the *-gen functions.

Package

prbs

Source

prbs.lisp (file)

Function: taps N

return a list of register taps (counting from the left) for a polynomial of order n, favoring LFSR-4 taps over LFSR-2.

Package

prbs.taps

Source

taps.lisp (file)


Previous: , Up: Definitions   [Contents][Index]

6.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

6.2.1 Special variables

Special Variable: *lfsr2*
Package

prbs.taps

Source

taps.lisp (file)

Special Variable: *lfsr4*
Package

prbs.taps

Source

taps.lisp (file)


Previous: , Up: Internal definitions   [Contents][Index]

6.2.2 Functions

Function: make-tracker GEN TOTAL-BITS &optional ERROR-BITS
Package

prbs.err

Source

err.lisp (file)

Function: prbs-n BV TAPS &optional LEN

=> bit-vector

left-shift ‘BV‘ by one bit and apply ‘TAPS‘ to generate a new right-side bit.

Package

prbs

Source

prbs.lisp (file)


Previous: , Up: Top   [Contents][Index]

Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts

Jump to:   F   L   M   P  
Index Entry  Section

F
File, Lisp, prbs.asd: The prbs<dot>asd file
File, Lisp, prbs/src/err.lisp: The prbs/src/err<dot>lisp file
File, Lisp, prbs/src/prbs.lisp: The prbs/src/prbs<dot>lisp file
File, Lisp, prbs/src/taps.lisp: The prbs/src/taps<dot>lisp file
File, Lisp, prbs/src/util.lisp: The prbs/src/util<dot>lisp file

L
Lisp File, prbs.asd: The prbs<dot>asd file
Lisp File, prbs/src/err.lisp: The prbs/src/err<dot>lisp file
Lisp File, prbs/src/prbs.lisp: The prbs/src/prbs<dot>lisp file
Lisp File, prbs/src/taps.lisp: The prbs/src/taps<dot>lisp file
Lisp File, prbs/src/util.lisp: The prbs/src/util<dot>lisp file

M
Module, prbs/src: The prbs/src module

P
prbs.asd: The prbs<dot>asd file
prbs/src: The prbs/src module
prbs/src/err.lisp: The prbs/src/err<dot>lisp file
prbs/src/prbs.lisp: The prbs/src/prbs<dot>lisp file
prbs/src/taps.lisp: The prbs/src/taps<dot>lisp file
prbs/src/util.lisp: The prbs/src/util<dot>lisp file

Jump to:   F   L   M   P  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   B   F   M   N   P   S   T  
Index Entry  Section

B
bit-gen: Exported functions
bitbv: Exported functions
bv->num: Exported functions
bvlist-gen: Exported functions
byte-gen: Exported functions
bytes->bits: Exported functions

F
Function, bit-gen: Exported functions
Function, bitbv: Exported functions
Function, bv->num: Exported functions
Function, bvlist-gen: Exported functions
Function, byte-gen: Exported functions
Function, bytes->bits: Exported functions
Function, make-prbs: Exported functions
Function, make-tracker: Internal functions
Function, num->bv: Exported functions
Function, num-gen: Exported functions
Function, prbs-detect: Exported functions
Function, prbs-lock: Exported functions
Function, prbs-n: Internal functions
Function, seq-length: Exported functions
Function, sfind: Exported functions
Function, sfind-all: Exported functions
Function, take: Exported functions
Function, taps: Exported functions

M
make-prbs: Exported functions
make-tracker: Internal functions

N
num->bv: Exported functions
num-gen: Exported functions

P
prbs-detect: Exported functions
prbs-lock: Exported functions
prbs-n: Internal functions

S
seq-length: Exported functions
sfind: Exported functions
sfind-all: Exported functions

T
take: Exported functions
taps: Exported functions

Jump to:   B   F   M   N   P   S   T  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.3 Variables

Jump to:   *  
S  
Index Entry  Section

*
*lfsr2*: Internal special variables
*lfsr4*: Internal special variables

S
Special Variable, *lfsr2*: Internal special variables
Special Variable, *lfsr4*: Internal special variables

Jump to:   *  
S  

Previous: , Up: Indexes   [Contents][Index]

A.4 Data types

Jump to:   P   S  
Index Entry  Section

P
Package, prbs: The prbs package
Package, prbs.err: The prbs<dot>err package
Package, prbs.taps: The prbs<dot>taps package
Package, prbs.util: The prbs<dot>util package
prbs: The prbs system
prbs: The prbs package
prbs.err: The prbs<dot>err package
prbs.taps: The prbs<dot>taps package
prbs.util: The prbs<dot>util package

S
System, prbs: The prbs system

Jump to:   P   S