Shop OBEX P1 Docs P2 Docs Learn Events
LFSR pseudo random generator (PRNG) — Parallax Forums

LFSR pseudo random generator (PRNG)

virtuPICvirtuPIC Posts: 193
edited 2012-02-22 23:16 in Propeller 1
The last recent days I participated in technical, philosophical, funny discussion on random numbers, pseudo random numbers, one time pads and how to generate them. Here I've got an LFSR as a pseudo random generator.
  • It handles one word. Up to 32 bit SR length.
  • You have to configure it with the feedback tap sequence.
  • Period depends on the feedback tap sequence and can be up to 2n-1.
  • LFSR sequences have good properties for simulation.
  • LFSR sequences are very good test data for random tests.
  • LFSR sequences have a very flat frequency spectrum.
  • LFSR are extremely weak in cryptography.
  • LFSR state gives a pseudo random number from 1 to 2n - 1. But do not use the bits generated for more than one generated number since this would introduce statistical correlation.
Okay, I confess that the threads on (pseudo) random have not been my motivation to write this code. I simply need some test data with certain peculiariteis:
  • several Mbits size
  • reproducible
  • unsorted
  • uncorrelated
LFSR are predestined for this task. I'll use one of 32 bit length and generate a sequence of length required.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Airspace V - international hangar flying!
www.airspace-v.com/ggadgets for tools & toys
spin
spin
lfsr.spin
3K

Comments

  • heaterheater Posts: 3,370
    edited 2010-06-08 13:36
    virtuPC: That's odd, no replies to this post yet.

    Well I just used this in a RAM test for Bill's VMCog. No idea how well it works as a PRNG but it the output looks messy enough[noparse]:)[/noparse] Another test to the battery.

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    For me, the past is not over yet.
  • pullmollpullmoll Posts: 817
    edited 2010-06-08 14:38
    To test the randomness of a pseudo random number generator there are various tools. One that is free and gives a good measure AFAICS is John Walker's ENT. You can find the source here, together with a description how to use the little tool. A precompiled Windows executable is included. For Linux or other POSIXish OSes you just need a C compiler.

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    Pullmoll's Propeller Projects

    Post Edited (pullmoll) : 6/8/2010 2:43:23 PM GMT
  • heaterheater Posts: 3,370
    edited 2010-06-08 15:36
    Pullmoll, I was going to but now you have prompted me to want to do some tests on this.

    There is always diehard and dieharder tests www.phy.duke.edu/~rgb/General/dieharder.php

    Never heard of ent before though.

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    For me, the past is not over yet.
  • AribaAriba Posts: 2,690
    edited 2010-06-09 01:02
    Spin has an integrated pseudo random generator, which I think, works with 32bit LFSR:
      state := default_seed

  state?   'next LFSR value
  ?state   'previous LFSR value



    Andy
  • heaterheater Posts: 3,370
    edited 2010-06-09 04:54
    Ariba, I really am getting tired, I used to know that [noparse]:)[/noparse]

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    For me, the past is not over yet.
  • cessnapilotcessnapilot Posts: 182
    edited 2010-06-11 05:23
    Sorry being slightly off-topic, but you can·make a true random number generator with SPIN, not just PRNG. (http://obex.parallax.com/objects/501/)

    Cheers,

    Istvan

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔


    Intentionally Left Blank
  • ElectricAyeElectricAye Posts: 4,561
    edited 2010-06-11 14:00
    cessnapilot said...
    Sorry being slightly off-topic, but you can make a true random number generator with SPIN, not just PRNG. (http://obex.parallax.com/objects/501/)

    Cheers,

    Istvan

    Istvan,

    I'm getting a "File not found" message when I click on that link. cry.gif
  • kuronekokuroneko Posts: 3,623
    edited 2010-06-11 14:04
    ElectricAye said...
    I'm getting a "File not found" message when I click on that link. cry.gif
    Remove the closing bracket from the URI.
  • wai-tnwai-tn Posts: 1
    edited 2012-02-22 12:08
    Hi,

    As virtuPIC, I am also interested on PRNGs, these days, particularly on LFSRs.
    As reminder I 'll add that every sequence on an LFSR is outputted depending on an inner state and a characteristic polynomial (primitive) of the form Xn + Xk + 1. (n is the length of the LFSR, as described earlier)
    I see in some documentations that there is a probability for each generated bit of the sequence that depends on the characteristic polynomial or a group of chracteristic polynomials used with a fixed inner state

    Have someone an idea about how knowing that information or calculating this probability?

    looking forward to hear from you
  • Heater.Heater. Posts: 21,230
    edited 2012-02-22 13:14
    Boy is this an old thread.
    Spin has an in built LFSR as it's random operator.
    However I have found that if you run a sequence of a million or so of it's output through a test of randomness program like ENT, mentioned above, it fails miserably.
    Fot this reason I implemented rather better pseudo random number generators in Spin. Have a search for recent threads on MWC256 for example.
  • Heater.Heater. Posts: 21,230
    edited 2012-02-22 23:16
    Also look for the JKISS32 PRNG.

    I cannot fathom what it is you are trying to do with LFSR.
Sign In or Register to comment.