two most random outputs from six stage counter

Discussion in 'General Electronics Chat' started by PeteHL, Jun 10, 2015.

  1. PeteHL

    Thread Starter Member

    Dec 17, 2014
    59
    0
    six-stage_counter.png six-stage_counter.png The counter, as shown in the schematic, is six D-type flip-flops connected in cascade, with feedback to the input of the first in-the-series flip-flop via a two input exclusive or gate. This results in a pseudo-random sequence of zeroes and ones at the serial output terminal. There are six parallel outputs and one serial output. What I want to do is to select two outputs from the seven available outputs that will produce a sequence of pairs of zeroes and ones with the greatest possible randomness. So the question is, which pair of outputs should I choose, and why?
     
    Last edited: Jun 10, 2015
  2. AnalogKid

    Distinguished Member

    Aug 1, 2013
    4,535
    1,251
    It doesn't matter; they're all the same. What you have is a LFSR - Linear Feedback Shift Register. Because there is no feedback injection in the middle of the string, all bits go through all stages after the first six clock cycles after power up. Starting with P0/P1, all six register outputs have the same serial bit pattern as the "serial output", each one one clock period delayed from the previous.

    All LFSRs repeat their output cycle eventually. This one is short enough to calculate and print out the entire bit pattern in one cycle, either as a table of 63 6-bit binary words or one 63-bit binary string. There are 15 possible output pair combinations. With that table or string you can scan it for the output combinations you want and just count them.

    As the LFSR gets longer you approach the point where the output pattern is so random that there is no bias in any of the 2-bit combinations either.

    EDIT - There are only five unique output pair combinations, not 15. Calculate a table with the 63 possible 6-bit output patterns in the order they occur. Count the number of times bits 1 and 2 both are ones. Count the number of times bits 1 and 3 both are ones, etc. Compare the five totals and pick the largest.

    ak
     
    Last edited: Jun 11, 2015
  3. PeteHL

    Thread Starter Member

    Dec 17, 2014
    59
    0
    AK, thanks for your reply. As I don't have a lot of experience with this subject, you are losing me some.

    I agree with what you say at the start of your post that "all six register outputs have the same serial bit pattern as the serial output, each one one clock period delayed from the previous". But what I'm looking at is the state of a pair of outputs immediately after the clock goes from low to high (shifting data), and I think that the randomness of those pairs is going to be different depending on which pair of outputs I choose to look at.

    I've tried setting the clock rate at 0.5 Hz and connected the clock and outputs to LEDs to attempt to see if there is more randomness or less randomness depending on which pair of outputs that I monitor. This is certainly not very scientific, but I'm befuddled in trying to draw a conclusion.

    Regards,
    Pete
     
  4. nsaspook

    AAC Fanatic!

    Aug 27, 2009
    2,908
    2,168
  5. AnalogKid

    Distinguished Member

    Aug 1, 2013
    4,535
    1,251
    Your clock rate is in the seconds arena, and these parts shift in nanoseconds - that's a billion-to-one difference in timing. Yes, in theory it takes a finite amount of time for the six outputs to stabilize after a clock edge, but that time is, well, impossible to say because you didn't give us a part number for the registers. But it is almost certainly under 50 ns, and probably more like 5-10 ns. So except for this 5 ns, "immediately" has nothing to do with the randomness of the outputs.

    Because the LFSR is so short, the randomness of some pairs might be better/worse than other pairs. But that has nothing to do with the clock frequency or when in a clock cycle you examine them. For all practical purposes, the six output change instantaneously and simultaneously.

    ak
     
  6. PeteHL

    Thread Starter Member

    Dec 17, 2014
    59
    0
    Thanks for the link to Okawara's lecture, nsaspook. It is very clear and straightforward.

    AK, I think that you are correct in saying that any two outputs will exhibit the same randomness of pairs of bits. Working with the shift reg. pattern of bits in Fig. 1 of Okawara's piece, the number of (0,0), (0,1) or (1,0), and (1,1) is the same irregardless of the outputs of a given pair of shift registers taken. I suppose that there may be a difference in the sequence of the bit pairs depending on the outputs selected though which might make a difference for what I want to do. I haven't examined that yet.

    By "immediately" I was trying to convey almost instantaneously in a broad sense. For judging the randomness of bit pairs, you would want to "check" the outputs for convenience after the registers have completed shifting the data to the output terminals.

    Regards,
    Pete
     
  7. atferrari

    AAC Fanatic!

    Jan 6, 2004
    2,648
    762
    That clock was set slow as 0.5 Hz so you could actually watch something?

    I would use a MUCH faster one and a scope. Have you got one?

    Have you heard of noise used to generate random output?
     
  8. PeteHL

    Thread Starter Member

    Dec 17, 2014
    59
    0
    Initially I had LEDs driven by the outputs so that I could watch the outcome. But also, in conjunction with CMOS 4000 series gates, I plan to use the LFSR to do some slow switching.

    I do have a CRO, but it is dual channel so then I couldn't monitor any more than two outputs at a time.

    Yes, I did run across random number generation using noise. I prefer the LFSR as I plan to use it in conjunction with audio analog circuitry. A noise source could possibly be isolated from the audio circuitry, I don't know. My hunch is that I could achieve the random switching that I'm after with a software program and less hardware, but that would be way beyond my present knowledge.
     
  9. AnalogKid

    Distinguished Member

    Aug 1, 2013
    4,535
    1,251
    Every computer language I've seen since IBM-PC BASIC has a built-in random number generator. Like an LFSR, it will return the same number sequence if given the same seed. I don't think the type of noise source (analog vs. digital) has anything to do with isolation from sensitive circuits.

    ak
     
Loading...