ROOT::Math::LFSR Namespace Reference

Pseudo Random Binary Sequence (PRBS) generator namespace with functions based on linear feedback shift registers (LFSR) with a periodicity of 2^n-1. More...

Functions
template<size_t k, size_t nTaps, typename Output = unsigned char>
std::vector< Output >	GenerateSequence (std::bitset< k > start, std::array< std::uint16_t, nTaps > taps, bool left=true, bool wrapping=false, bool oppositeBit=false)
	Generation of a sequence of pseudo-random bits using a linear feedback shift register (LFSR), until a register value is repeated (or maxPeriod is reached)
template<size_t k, size_t nTaps>
bool	NextLFSR (std::bitset< k > &lfsr, std::array< std::uint16_t, nTaps > taps, bool left=true)
	Generate the next pseudo-random bit using the current state of a linear feedback shift register (LFSR) and update it.

Detailed Description

Pseudo Random Binary Sequence (PRBS) generator namespace with functions based on linear feedback shift registers (LFSR) with a periodicity of 2^n-1.

Note

It should NOT be used for general-purpose random number generation or any statistical study, for those cases see e.g. std::mt19937 instead.

The goal is to generate binary bit sequences with the same algorithm as the ones usually implemented in electronic chips, so that the theoretically expected ones can be compared with the acquired sequences.

The main ingredients of a PRBS generator are a monic polynomial of maximum degree \(n\), with coefficients either 0 or 1, and a Galois linear-feedback shift register with a non-zero seed. When the monic polynomial exponents are chosen appropriately, the period of the resulting bit sequence (0s and 1s) yields \(2^n - 1\).

See also

https://gist.github.com/mattbierner/d6d989bf26a7e54e7135, https://root.cern/doc/master/civetweb_8c_source.html#l06030, https://cryptography.fandom.com/wiki/Linear_feedback_shift_register, https://www3.advantest.com/documents/11348/33b24c8a-c8cb-40b8-a2a7-37515ba4abc8, https://www.reddit.com/r/askscience/comments/63a10q/for_prbs3_with_clock_input_on_each_gate_how_can/, https://es.mathworks.com/help/serdes/ref/prbs.html, https://metacpan.org/pod/Math::PRBS, https://ez.analog.com/data_converters/high-speed_adcs/f/q-a/545335/ad9689-pn9-and-pn23

Function Documentation

GenerateSequence()

template<size_t k, size_t nTaps, typename Output = unsigned char>

std::vector< Output > ROOT::Math::LFSR::GenerateSequence	(	std::bitset< k >	start,
		std::array< std::uint16_t, nTaps >	taps,
		bool	left = true,
		bool	wrapping = false,
		bool	oppositeBit = false )

Generation of a sequence of pseudo-random bits using a linear feedback shift register (LFSR), until a register value is repeated (or maxPeriod is reached)

Template Parameters

k	the length of the LFSR, usually also the order of the monic polynomial PRBS-k (last exponent)
nTaps	the number of taps
Output	the type of the container where the bit result (0 or 1) is stored (e.g. char, bool). It's unsigned char by default, use bool instead if you want to save memory

Parameters

start	the start value (seed) of the LFSR
taps	the taps that will be XOR-ed to calculate the new bit. They are the exponents of the monic polynomial. Ordering is unimportant. Note that an exponent E in the polynom maps to bit index E-1 in the LFSR.
left	if true, the direction of the register shift is to the left <<, the newBit is set on lfsr at bit position 0 (right). If false, shift is to the right and the newBit is stored at bit position (k-1)
wrapping	if true, allow repetition of values in the LFSRhistory, until maxPeriod is reached or the repeated value == start. Enabling this option saves memory as no history is kept
oppositeBit	if true, use the high/low bit of the LFSR to store output (for left=true/false, respectively) instead of the newBit returned by NextLFSR

Returns

the array of pseudo random bits, or an empty array if input was incorrect

See also

https://en.wikipedia.org/wiki/Monic_polynomial, https://en.wikipedia.org/wiki/Linear-feedback_shift_register, https://en.wikipedia.org/wiki/Pseudorandom_binary_sequence

Definition at line 107 of file LFSR.h.

NextLFSR()

template<size_t k, size_t nTaps>

bool ROOT::Math::LFSR::NextLFSR	(	std::bitset< k > &	lfsr,
		std::array< std::uint16_t, nTaps >	taps,
		bool	left = true )

Generate the next pseudo-random bit using the current state of a linear feedback shift register (LFSR) and update it.

Template Parameters

k	the length of the LFSR, usually also the order of the monic polynomial PRBS-k (last exponent)
nTaps	the number of taps

Parameters

lfsr	the current value of the LFSR. Passed by reference, it will be updated with the next value
taps	the taps that will be XOR-ed to calculate the new bit. They are the exponents of the monic polynomial. Ordering is unimportant. Note that an exponent E in the polynom maps to bit index E-1 in the LFSR.
left	if true, the direction of the register shift is to the left <<, the newBit is set on lfsr at bit position 0 (right). If false, shift is to the right and the newBit is stored at bit position (k-1)

Returns

the new random bit

Exceptions

an	exception is thrown if taps are out of the range [1, k]

See also

https://en.wikipedia.org/wiki/Monic_polynomial, https://en.wikipedia.org/wiki/Linear-feedback_shift_register, https://en.wikipedia.org/wiki/Pseudorandom_binary_sequence

Definition at line 57 of file LFSR.h.