Forum: GNU Radio Galois-form LFSR now in trunk (r4613)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Cec0a4bf0e0575f3a3171892e6097e59?d=identicon&s=25 Johnathan Corgan (Guest)
on 2007-02-23 19:49
(Received via mailing list)
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 Corgan
Corgan Enterprises LLC
http://corganenterprises.com
Bb3ff9c86361ea921a64632a4c46e824?d=identicon&s=25 Trond Danielsen (Guest)
on 2007-02-23 21:03
(Received via mailing list)
2007/2/23, Johnathan Corgan <jcorgan@aeinet.com>:
> 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 Danielsen
Cec0a4bf0e0575f3a3171892e6097e59?d=identicon&s=25 Johnathan Corgan (Guest)
on 2007-02-23 21:11
(Received via mailing list)
Trond Danielsen 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 Corgan
Corgan Enterprises LLC
http://corganenterprises.com
745d8202ef5a58c1058d0e5395a78f9c?d=identicon&s=25 Eric Blossom (Guest)
on 2007-02-23 21:24
(Received via mailing list)
On Fri, Feb 23, 2007 at 12:10:17PM -0800, Johnathan Corgan 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 ;)

Eric
Cec0a4bf0e0575f3a3171892e6097e59?d=identicon&s=25 Johnathan Corgan (Guest)
on 2007-02-23 21:31
(Received via mailing list)
Eric Blossom wrote:

> Looks like this needs some QA code.
>
> The original version probably didn't _really_ generate an m-sequence ;)

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 Corgan
Corgan Enterprises LLC
http://corganenterprises.com
Bb3ff9c86361ea921a64632a4c46e824?d=identicon&s=25 Trond Danielsen (Guest)
on 2007-02-23 21:41
(Received via mailing list)
2007/2/23, Johnathan Corgan <jcorgan@aeinet.com>:
> > {
>
> --
> Johnathan Corgan
> 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 Danielsen
Cec0a4bf0e0575f3a3171892e6097e59?d=identicon&s=25 Johnathan Corgan (Guest)
on 2007-02-23 21:48
(Received via mailing list)
Trond Danielsen 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 :-)

--
Johnathan Corgan
Corgan Enterprises LLC
http://corganenterprises.com
This topic is locked and can not be replied to.