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.orgTom 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>