Skip to content

Latest commit

 

History

History
119 lines (90 loc) · 3.27 KB

0101-prbs.org

File metadata and controls

119 lines (90 loc) · 3.27 KB
Raw

prbs

This library provides a pseudo-random binary sequence generator useful for error detection in communication streams. It will be useful, if you are building own protocol over UDP, for example.

Here is how it works. There is a function which creates a sequence generator. Its result is a lambda function which can return a requested number of random bits:

POFTHEDAY> (defparameter *generator*
             (prbs:bit-gen 33 :seed (get-universal-time)))

POFTHEDAY> (funcall *generator* 10)
#*0111000101

POFTHEDAY> (funcall *generator* 10)
#*0010011100

POFTHEDAY> (funcall *generator* 10)
#*1011001110

There is also a function to check if these pieces match the desired sequence. It should be used on the “receiver” to check if the message was corrupted or some packets were lost.

Let’s simulate a situation when we send our data in 1024 bit chunks and one chunk was lost:

SENDER> (defparameter *generator*
           (prbs:bit-gen 33 :seed (get-universal-time)))

;; These chunks are generated by the sender side
SENDER> (defparameter *first-chunk*
           (funcall *generator* 1024))

SENDER> *first-chunk*
#*011100010100100111001000001001110111...

SENDER> (defparameter *second-chunk*
           (funcall *generator* 1024))

SENDER> (defparameter *third-chunk*
           (funcall *generator* 1024))

;; The reveiver creates a special tracker
;; when it receives the first chunk of data
RECEIVER> (defparameter *tracker*
             (prbs.err:prbs-lock
              *first-chunk*
              33))
RECEIVER> *tracker*
#<CLOSURE (LAMBDA (PRBS.ERR::BITS) :IN PRBS.ERR::MAKE-TRACKER) {10080FF8BB}>

;; Now let's pretend we have lost our second packet
;; and process the third right after the first one:
RECEIVER> (funcall *tracker*
             *third-chunk*)
520
2048

In case of found errors, tracker returns their number as the first value. The second value is the total number of processed bits. This way we can calculate an error rate. In this case, tracker decided there are 520 bits which have wrong values.

Let’s simulate another situation when it received the second chunk, but 10 bits were corrupted and their value was flipped:

SENDER> (defparameter *corrupted-second-chunk*
           (copy-seq *second-chunk*))

;; Accidentally, some bits were corrupted:
IN-THE-MIDDLE> (loop for i from 100 below 110
                     do (setf (bit *corrupted-second-chunk* i)
                              (logxor (bit *corrupted-second-chunk* i)
                                      1)))

RECEIVER> (defparameter *tracker*
            (prbs.err:prbs-lock
             *first-chunk*
             33))

;; Now we process the corrupted chunk:
RECEIVER> (funcall *tracker*
                    *corrupted-second-chunk*)
10
2048

;; After the processing of third chunk,
;; tracker still show us there were encountered 10
;; errors:
RECEIVER> (funcall *tracker*
                   *third-chunk*)
10
3072

So, this library will be useful if you’ll decide to implement a protocol which needs to determine if there were errors introduced into the data.