Galois-form LFSR now in trunk (r4613)


#1

An implementation of a Galois-form LFSR pseudo-random sequence generator
is now in the trunk as of r4613.

gr.glfsr_source_b(degree, repeat=True, mask=0, seed=1)

degree: The shift register length, 1-32 inclusive
repeat: whether to repeat once sequence completes (True, False)
defaults to True
mask: The LFSR polynomial mask to use. If not supplied, a suitable
one is chosen based on the degree specified.
seed: The initial shift register value. This should not be zero, and
if not supplied, defaults to 1

The block outputs a series of bytes equal to 0 or 1, forming a maximal
length sequence (m-sequence) of length 2^degree-1. The output of this
block can be further processed by other blocks to map it to other
values, pack it into bytes, etc.

The simplest use is to specify only the degree:

src = gr.glfsr_source_b(32)

This will generate a 2^32-1 length m-sequence and repeat until the the
application is exited.

M-sequences are useful as digital noise sources, as they contain energy
at every discrete frequency interval up to the Nyquist frequency, for a
given sampling rate and sequence length.


Johnathan C.
Corgan Enterprises LLC
http://corganenterprises.com


#2

2007/2/23, Johnathan C. removed_email_address@domain.invalid:

seed: The initial shift register value. This should not be zero, and

http://corganenterprises.com

Is this correct?


gr_glfsr_source_b::gr_glfsr_source_b(int degree, bool repeat, int
mask, int seed)
: gr_sync_block (“glfsr_source_b”,
gr_make_io_signature (0, 0, 0),
gr_make_io_signature (1, 1, sizeof(unsigned char))),
d_repeat(repeat),
d_index(0)
{
if (degree < 1 || degree > 32)
throw std::runtime_error(“gr_glfsr_source_b: degree must be
between 1 and 32 inclusive”);
d_length = (int)(1ULL << degree)-1;
^



Trond D.


#3

Trond D. wrote:

if (degree < 1 || degree > 32)
throw std::runtime_error(“gr_glfsr_source_b: degree must be
between 1 and 32 inclusive”);
d_length = (int)(1ULL << degree)-1;
^


Not sure I understand what you’re questioning, the formatting is messed
up. But now that I stare at it, I think I misplaced a parenthesis; the
-1 should be inside.


Johnathan C.
Corgan Enterprises LLC
http://corganenterprises.com


#4

On Fri, Feb 23, 2007 at 12:10:17PM -0800, Johnathan C. wrote:

{
if (degree < 1 || degree > 32)
throw std::runtime_error(“gr_glfsr_source_b: degree must be
between 1 and 32 inclusive”);
d_length = (int)(1ULL << degree)-1;
^


Not sure I understand what you’re questioning, the formatting is messed
up. But now that I stare at it, I think I misplaced a parenthesis; the
-1 should be inside.

Looks like this needs some QA code.

The original version probably didn’t really generate an m-sequence :wink:

Eric


#5

Eric B. wrote:

Looks like this needs some QA code.

The original version probably didn’t really generate an m-sequence :wink:

The QA code is there; it actually checks for the proper auto-correlation
properties for all sequences of degree 1 through 11, which implies the
length calculation is correct also. Since the auto-correlation is done
naively and in Python, it’s dog slow, and anything longer than 2047
starts to take many seconds to complete.

I’ll add some QA code that only instantiates the block and asks it what
length it thinks it’s going to have. The bug Trond identified would only
have created a problem with a sequence of degree 32.


Johnathan C.
Corgan Enterprises LLC
http://corganenterprises.com


#6

2007/2/23, Johnathan C. removed_email_address@domain.invalid:

{


Johnathan C.
Corgan Enterprises LLC
http://corganenterprises.com

Sorry for not expressing myself clearly. This is what I was thinking of:

d_length = (int)(1ULL << degree)-1;

A quick google search enlightened me, I have never seen the 1ULL
decimal-constant integer-suffix before. Sorry to bother you.


Trond D.


#7

Trond D. wrote:

Sorry for not expressing myself clearly. This is what I was thinking of:

d_length = (int)(1ULL << degree)-1;

That’s a 64-bit unsigned long long constant equal to 1. I need that to
be able to shift left by 32; if it were just the 1UL it would fall off
the end.

Sorry to bother you.

No, you inadvertently found a bug in my code anyway, so thanks.

After going through the work of creating a 64-bit value, I was
immediately casting it to ‘int’. It’s been fixed. The joys of having
ones “intermediate work product” on display for the world :slight_smile:


Johnathan C.
Corgan Enterprises LLC
http://corganenterprises.com