[MERGED] osmo-trx[master]: PRBS: a Pseudo-random binary sequence (PRBS) generator class.

This is merely a historical archive of years 2008-2021, before the migration to mailman3.

A maintained and still updated list archive can be found at https://lists.osmocom.org/hyperkitty/list/gerrit-log@lists.osmocom.org/.

Tom Tsou gerrit-no-reply at lists.osmocom.org
Thu Jun 8 18:34:26 UTC 2017


Tom Tsou has submitted this change and it was merged.

Change subject: PRBS: a Pseudo-random binary sequence (PRBS) generator class.
......................................................................


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
---
M .gitignore
M CommonLibs/Makefile.am
A CommonLibs/PRBS.h
A CommonLibs/PRBSTest.cpp
4 files changed, 157 insertions(+), 0 deletions(-)

Approvals:
  Tom Tsou: Looks good to me, approved
  Jenkins Builder: Verified



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 at 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 at 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);
+}

-- 
To view, visit https://gerrit.osmocom.org/2764
To unsubscribe, visit https://gerrit.osmocom.org/settings

Gerrit-MessageType: merged
Gerrit-Change-Id: Ib5331ba5d0b5819929541686fdd87905e2177b74
Gerrit-PatchSet: 2
Gerrit-Project: osmo-trx
Gerrit-Branch: master
Gerrit-Owner: Alexander Chemeris <Alexander.Chemeris at gmail.com>
Gerrit-Reviewer: Alexander Chemeris <Alexander.Chemeris at gmail.com>
Gerrit-Reviewer: Harald Welte <laforge at gnumonks.org>
Gerrit-Reviewer: Jenkins Builder
Gerrit-Reviewer: Tom Tsou <tom at tsou.cc>



More information about the gerrit-log mailing list