diff options
author | Alexander Chemeris <Alexander.Chemeris@gmail.com> | 2017-04-02 12:45:36 +0200 |
---|---|---|
committer | Tom Tsou <tom@tsou.cc> | 2017-06-08 18:33:47 +0000 |
commit | 082bbbf8feec0a9a86d7484476e768971fe3b646 (patch) | |
tree | 0cc22d2755a560ce4109a81bcbc6fab412cdbdf8 | |
parent | 3bd763d2a10e19980505c90242a2eae9e2f6b4cb (diff) |
PRBS: a Pseudo-random binary sequence (PRBS) generator class.
Implemeted with a Galois LFSR for speed and flexibility compared to Fibonacci version.
Aliases for three popular PRBS' are added for convenience - PRBS9, PRBS15 and PRBS64.
Note that we can't test PRBS64 completely, because the sequence is too long to
be generated.
Change-Id: Ib5331ba5d0b5819929541686fdd87905e2177b74
-rw-r--r-- | .gitignore | 1 | ||||
-rw-r--r-- | CommonLibs/Makefile.am | 4 | ||||
-rw-r--r-- | CommonLibs/PRBS.h | 110 | ||||
-rw-r--r-- | CommonLibs/PRBSTest.cpp | 42 |
4 files changed, 157 insertions, 0 deletions
@@ -15,6 +15,7 @@ CommonLibs/SocketsTest CommonLibs/TimevalTest CommonLibs/URLEncodeTest CommonLibs/VectorTest +CommonLibs/PRBSTest # automake/autoconf *.in diff --git a/CommonLibs/Makefile.am b/CommonLibs/Makefile.am index f0f1061..18ec2f7 100644 --- a/CommonLibs/Makefile.am +++ b/CommonLibs/Makefile.am @@ -42,6 +42,7 @@ libcommon_la_SOURCES = \ noinst_PROGRAMS = \ BitVectorTest \ + PRBSTest \ InterthreadTest \ SocketsTest \ TimevalTest \ @@ -53,6 +54,7 @@ noinst_PROGRAMS = \ noinst_HEADERS = \ BitVector.h \ + PRBS.h \ Interthread.h \ LinkedLists.h \ Sockets.h \ @@ -66,6 +68,8 @@ noinst_HEADERS = \ BitVectorTest_SOURCES = BitVectorTest.cpp BitVectorTest_LDADD = libcommon.la $(SQLITE3_LIBS) +PRBSTest_SOURCES = PRBSTest.cpp + InterthreadTest_SOURCES = InterthreadTest.cpp InterthreadTest_LDADD = libcommon.la InterthreadTest_LDFLAGS = -lpthread diff --git a/CommonLibs/PRBS.h b/CommonLibs/PRBS.h new file mode 100644 index 0000000..0b7bbc3 --- /dev/null +++ b/CommonLibs/PRBS.h @@ -0,0 +1,110 @@ +/* + * Copyright (C) 2017 Alexander Chemeris <Alexander.Chemeris@fairwaves.co> + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#ifndef PRBS_H +#define PRBS_H + +#include <stdint.h> +#include <assert.h> + +/** Pseudo-random binary sequence (PRBS) generator (a Galois LFSR implementation). */ +class PRBS { +public: + + PRBS(unsigned wLen, uint64_t wCoeff, uint64_t wState = 0x01) + : mCoeff(wCoeff), mStartState(wState), mState(wState), mLen(wLen) + { assert(wLen<=64); } + + /**@name Accessors */ + //@{ + uint64_t coeff() const { return mCoeff; } + uint64_t state() const { return mState; } + void state(uint64_t state) { mState = state & mask(); } + unsigned size() const { return mLen; } + //@} + + /** + Calculate one bit of a PRBS + */ + unsigned generateBit() + { + const unsigned result = mState & 0x01; + processBit(result); + return result; + } + + /** + Update the generator state by one bit. + If you want to synchronize your PRBS to a known state, call this function + size() times passing your PRBS to it bit by bit. + */ + void processBit(unsigned inBit) + { + mState >>= 1; + if (inBit) mState ^= mCoeff; + } + + /** Return true when PRBS is wrapping through initial state */ + bool isFinished() const { return mStartState == mState; } + +protected: + + uint64_t mCoeff; ///< polynomial coefficients. LSB is zero exponent. + uint64_t mStartState; ///< initial shift register state. + uint64_t mState; ///< shift register state. + unsigned mLen; ///< number of bits used in shift register + + /** Return mask for the state register */ + uint64_t mask() const { return (mLen==64)?0xFFFFFFFFFFFFFFFFUL:((1<<mLen)-1); } + +}; + +/** + A standard 9-bit based pseudorandom binary sequence (PRBS) generator. + Polynomial: x^9 + x^5 + 1 +*/ +class PRBS9 : public PRBS { + public: + PRBS9(uint64_t wState = 0x01) + : PRBS(9, 0x0110, wState) + {} +}; + +/** + A standard 15-bit based pseudorandom binary sequence (PRBS) generator. + Polynomial: x^15 + x^14 + 1 +*/ +class PRBS15 : public PRBS { +public: + PRBS15(uint64_t wState = 0x01) + : PRBS(15, 0x6000, wState) + {} +}; + +/** + A standard 64-bit based pseudorandom binary sequence (PRBS) generator. + Polynomial: x^64 + x^63 + x^61 + x^60 + 1 +*/ +class PRBS64 : public PRBS { +public: + PRBS64(uint64_t wState = 0x01) + : PRBS(64, 0xD800000000000000ULL, wState) + {} +}; + +#endif // PRBS_H diff --git a/CommonLibs/PRBSTest.cpp b/CommonLibs/PRBSTest.cpp new file mode 100644 index 0000000..b83e93d --- /dev/null +++ b/CommonLibs/PRBSTest.cpp @@ -0,0 +1,42 @@ +/* + * Copyright (C) 2017 Alexander Chemeris <Alexander.Chemeris@fairwaves.co> + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include "PRBS.h" +#include <iostream> +#include <cstdlib> +#include <assert.h> + +void testPrbs(PRBS &prbs, uint64_t expectedPeriod) +{ + uint64_t period = 0; + do { + std::cout << prbs.generateBit(); + period++; + } while (!prbs.isFinished()); + std::cout << std::endl; + std::cout << "Period: " << period << std::endl; + assert(period == expectedPeriod); +} + +int main(int argc, char *argv[]) +{ + PRBS9 prbs9(0x01); + testPrbs(prbs9, (1<<9)-1); + PRBS15 prbs15(0x01); + testPrbs(prbs15, (1<<15)-1); +} |