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
diff --git a/.gitignore b/.gitignore
index d1a0b33..d560f19 100644
--- a/.gitignore
+++ b/.gitignore
@@ -15,6 +15,7 @@
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 @@
noinst_PROGRAMS = \
BitVectorTest \
+ PRBSTest \
InterthreadTest \
SocketsTest \
TimevalTest \
@@ -53,6 +54,7 @@
noinst_HEADERS = \
BitVector.h \
+ PRBS.h \
Interthread.h \
LinkedLists.h \
Sockets.h \
@@ -66,6 +68,8 @@
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);
+}