0
\$\begingroup\$

I'm working on a project, where we need to generate random numbers between 1-5. After researching a bit I figure out generally LFSR (Linear-feedback shift register) is used for generating random numbers (more preciously Pseudo-random).

So, I used 3 bit LFSR with polynomial \$x^3 + x + 1\$, which generates \$2^3 - 1 = 7\$ numbers {1, 2, 3, 4, 5, 6, 7}. Now I need to somehow map {6, 7} to one of the number {1, 2, 3, 4, 5}.

I can not use a mod circuit as it will be deterministic. So, How can I randomly (or Pseudo randomly) map {6, 7} to {1, 2, 3, 4, 5}.

I'm not a electronics student, so pardon me If the question seems silly.

\$\endgroup\$
8
  • 2
    \$\begingroup\$ You can't. But you can roll the dice again if you get 6 or 7. More problematic is that a 3-bit LFSR will always generate the same sequence of 7 numbers. Use a 16 or 32 or (some other large number) bit LFSR and use the 3 LSBs of it instead. \$\endgroup\$
    – user16324
    Feb 12, 2017 at 15:00
  • 4
    \$\begingroup\$ "I can not use a mod circuit as it will be deterministic" - An LFSR is completely deterministic. It will always produce exactly the same sequence. \$\endgroup\$ Feb 12, 2017 at 15:01
  • \$\begingroup\$ Truly random numbers generators use expensive equipment which are out of the realm of the casual user (or undergraduate student w/o grant money). Processor based pseudo random generators are easy. What is your application / needs? \$\endgroup\$
    – st2000
    Feb 12, 2017 at 15:07
  • \$\begingroup\$ Can you use a second LSFR in the feedback loop of the first LSFR just to handle the {6, 7}, thus adding a non deterministic outcome to your Pseudo Random output. Or leave them out of the feedback loop altogether. \$\endgroup\$ Feb 12, 2017 at 15:13
  • \$\begingroup\$ Might want to read this. Maybe a HW solution isn't as expensive as I thought. Or, there may be a spectrum of HW solutions from cheap to expensive depending on how random the results are. \$\endgroup\$
    – st2000
    Feb 12, 2017 at 15:14

3 Answers 3

2
\$\begingroup\$

There are a lot of circuits around advertised as "digital dice". The usual approach is to use a counter which runs at high speed, for a time determined by how long the user presses the button. Since a human can't press a button repeatably for the same number of microseconds, this produces acceptably random numbers.

The purist approach is to use a genuine noise source such as a silicon junction (diodes, especially Zeners), and amplify it. In a suitably shielded case this will produce "real" noise which you can use for cryptographic purposes.

\$\endgroup\$
5
  • \$\begingroup\$ And don't forget lava lamps. \$\endgroup\$ Feb 12, 2017 at 20:58
  • \$\begingroup\$ @pjc50 Have you heard of any method which samples noise from the keyboard. \$\endgroup\$
    – Atinesh
    Mar 2, 2017 at 3:16
  • \$\begingroup\$ @WhatRoughBeast Weren't those pseudo random number generators with a hardware derived seed? \$\endgroup\$
    – Paul Uszak
    Apr 22, 2017 at 12:31
  • \$\begingroup\$ @PaulUszak - Yes, but that doesn't do it justice. The "hardware derived seed" was the hash of a real-time digital image of a Lava Lamp(TM). As I recall, Silicon Graphics had a bank of 6 lava lamps, each of a different color. See en.wikipedia.org/wiki/Lavarand \$\endgroup\$ Apr 22, 2017 at 12:46
  • \$\begingroup\$ @Atinesh The Linux operating system does in it's implementation of \dev\random. See how, but in essence it's analogue quantization noise. Linus just calls it 'jiffies' instead. \$\endgroup\$
    – Paul Uszak
    Dec 26, 2020 at 17:04
1
\$\begingroup\$

I can not use a mod circuit as it will be deterministic.

the whole algorithm you are using is deterministic - it is a pseudo random number generator. PSNGs are quite useful as they are typically fast and light weight (code size). But they are 100% deterministic.

there are many ways to generate truly random numbers, bot analog or digital. In the digital domain, using adc's lsb is quite popular, as is taking advantage of phase differentials of two oscillators (mostly relaxation oscillators).

i experimented some here: https://dannyelectronics.wordpress.com/2016/03/19/true-random-number-generators/

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Not only requires the page login (at least for me) you should also add the vital parts of it to you post so that this post is still useful even if your blog goes down some day. \$\endgroup\$ Feb 12, 2017 at 15:13
1
\$\begingroup\$

The LSFR you are using is completely determinisitic.

However, if you wish to generate 1 to 5 with equal probability in a pseudo random way using an LSFR, you could use a 4 state one that has 15 states, and map 3 states to each output number. As this counts through 15 states before repeating, the sequence of 5 outputs will not repeat every 5.

Many maximal length LSFR sequences have a number of states that's divisible by 5. 2^8 gives you 255 for instance, 2^12 gives you 4095.

\$\endgroup\$
2
  • \$\begingroup\$ I didn't get you can you please elaborate. \$\endgroup\$
    – Atinesh
    Feb 21, 2017 at 15:01
  • \$\begingroup\$ I'm not sure I can think of anything clearer than what I've written. Perhaps you could help me by pointing out what you do understand, so I can spot what you don't. It looks like you already know an n stage LFSR generates (or can, with the right polynomial) 2^n-1 states. You understand the concept of 15 or 4095 being multiples of 5? In the case of 12 stage, mapping 20% of the 4095 states to one of the outcomes, another 20% to another outcome, would, I hope, be obvious? So we have 5 equally likely outcomes. Using a 3 stage 7 state LFSR results in two states being more likely than the other 3. \$\endgroup\$
    – Neil_UK
    Feb 21, 2017 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.