Forums

"Random" Circuit Needed.

Started by Jim Thompson April 1, 2015
On Wed, 01 Apr 2015 15:31:25 -0700, Jim Thompson
<To-Email-Use-The-Envelope-Icon@On-My-Web-Site.com> wrote:

>On Thu, 02 Apr 2015 07:26:29 +1000, "David Eather" <eather@tpg.com.au> >wrote: > >>On Thu, 02 Apr 2015 05:14:13 +1000, Jim Thompson >><To-Email-Use-The-Envelope-Icon@on-my-web-site.com> wrote: >> >>> On Wed, 01 Apr 2015 15:07:54 -0400, Phil Hobbs >>> <pcdhSpamMeSenseless@electrooptical.net> wrote: >>> >>>> On 04/01/2015 02:00 PM, Jim Thompson wrote: >>>>> For a simulation situation I need a random number generator with a >>>>> twist... >>>>> >>>>> What I need to simulate is a "random" selection of one-of-16 outputs. >>>>> >>>>> Clock "speed" is 12.5kHz ;-) >>>>> >>>>> Built of 74HCxx parts is preferred... I have a full ensemble of those >>>>> device in my PSpice library. >>>>> >>>>> Thanks in advance. >>>>> >>>>> ...Jim Thompson >>>>> >>>> >>>> How random? You could use a 16-bit PRBS made from two HC299 and an >>>> HC86. Feed back Q14 XOR Q13, and tap out four stages to a HC154 demux. >>>> If you need better randomness, use four PRBSes of different length. >>>> >>>> Cheers >>>> >>>> Phil Hobbs >>> >>> I just need semi-random enough to test a fast AGC. >>> >>> ...Jim Thompson >> >>there is a bias with the 8-bit just use the last 4 bit idea. With 255 >>'clocks' all states but 0000 will occur 16 times while 0000 will only >>appear 15 - the cycle then repeats. The lack of the extra 0000 may cause >>the bias point to continually drift high. > >I was wondering about that myself... I'll see if there's a cure. > > ...Jim Thompson
--- The cure is to force the counter into the all-zeros state (the lockup state if you're using EXOR feedback) once per cycle and then to force it back out again, like this: https://www.dropbox.com/s/r7ea52axx6q6fny/LFSR.asc?dl=0 which'll give you a bias-free sequence since the counter will step through all 256 states instead of just 255 John Fields
On 4/2/2015 6:48 AM, Jasen Betts wrote:
> On 2015-04-01, rickman <gnuarm@gmail.com> wrote: >> On 4/1/2015 6:31 PM, Jim Thompson wrote: >> >> Do a search on the Xilinx web site for app notes on LFSR. Peter Alfke >> published one which adds a few gates to specifically inject the zero >> state.... > > yeah, but no LFSR visits all states.
You haven't seen the app note. Why can't it include the zero state with modification? -- Rick
On 2 Apr 2015 10:48:15 GMT, Jasen Betts <jasen@xnet.co.nz> wrote:

>On 2015-04-01, rickman <gnuarm@gmail.com> wrote: >> On 4/1/2015 6:31 PM, Jim Thompson wrote: >> >> Do a search on the Xilinx web site for app notes on LFSR. Peter Alfke >> published one which adds a few gates to specifically inject the zero >> state.... > >yeah, but no LFSR visits all states.
--- That's not true, but I've heard that position defended on semantic grounds because a "Linear Feedback Shift Register" can only include EXOR feedback. My position is that that's bogus, since by changing the name to "Pseudo Random Sequence Generator" and employing the same additional logic in the LFSR's feedback path, both circuits will be topologically identical and each will visit all states. John Fields
On 2015-04-02, John Fields <jfields@austininstruments.com> wrote:
> On 2 Apr 2015 10:48:15 GMT, Jasen Betts <jasen@xnet.co.nz> wrote: > >>On 2015-04-01, rickman <gnuarm@gmail.com> wrote: >>> On 4/1/2015 6:31 PM, Jim Thompson wrote: >>> >>> Do a search on the Xilinx web site for app notes on LFSR. Peter Alfke >>> published one which adds a few gates to specifically inject the zero >>> state.... >> >>yeah, but no LFSR visits all states. > > --- > That's not true, but I've heard that position defended on semantic > grounds because a "Linear Feedback Shift Register" can only include > EXOR feedback.
There is that: there are only three linear boolean operators, NOT, XOR,XNOR, (and they can all be derived from XOR )
> My position is that that's bogus, since by changing the name to > "Pseudo Random Sequence Generator" and employing the same additional > logic in the LFSR's feedback path, both circuits will be > topologically identical and each will visit all states.
That would make it a non-linear FSR -- umop apisdn
On 4/2/2015 4:51 PM, Jasen Betts wrote:
> On 2015-04-02, rickman <gnuarm@gmail.com> wrote: >> On 4/2/2015 6:48 AM, Jasen Betts wrote: >>> On 2015-04-01, rickman <gnuarm@gmail.com> wrote: >>>> On 4/1/2015 6:31 PM, Jim Thompson wrote: >>>> >>>> Do a search on the Xilinx web site for app notes on LFSR. Peter Alfke >>>> published one which adds a few gates to specifically inject the zero >>>> state.... >>> >>> yeah, but no LFSR visits all states. >> >> You haven't seen the app note. Why can't it include the zero state with >> modification? > > I think there's something about linear feedback that requires the > cycle length to be odd.
The key word there is "something". Technically once you make this mod it is not an LFSR anymore. But that is what the OP wants, something that is *not* an LFSR because the LFSR only covers 2^N-1 states and he wants 2^N. A rose by any other name.... -- Rick
On 4/2/2015 4:51 PM, Jasen Betts wrote:
> On 2015-04-02, rickman <gnuarm@gmail.com> wrote: >> On 4/2/2015 6:48 AM, Jasen Betts wrote: >>> On 2015-04-01, rickman <gnuarm@gmail.com> wrote: >>>> On 4/1/2015 6:31 PM, Jim Thompson wrote: >>>> >>>> Do a search on the Xilinx web site for app notes on LFSR. Peter Alfke >>>> published one which adds a few gates to specifically inject the zero >>>> state.... >>> >>> yeah, but no LFSR visits all states. >> >> You haven't seen the app note. Why can't it include the zero state with >> modification? > > I think there's something about linear feedback that requires the > cycle length to be odd. > >
Maximum length sequences of even order are perfectly possible, but they require more feedback taps. Cheers Phil Hobbs -- Dr Philip C D Hobbs Principal Consultant ElectroOptical Innovations LLC Optics, Electro-optics, Photonics, Analog Electronics 160 North State Road #203 Briarcliff Manor NY 10510 hobbs at electrooptical dot net http://electrooptical.net
On 2 Apr 2015 10:42:50 GMT, Jasen Betts <jasen@xnet.co.nz> wrote:

>On 2015-04-01, Jim Thompson <To-Email-Use-The-Envelope-Icon@On-My-Web-Site.com> wrote: >> On Thu, 02 Apr 2015 07:26:29 +1000, "David Eather" <eather@tpg.com.au> >> wrote: >> >>>On Thu, 02 Apr 2015 05:14:13 +1000, Jim Thompson >>><To-Email-Use-The-Envelope-Icon@on-my-web-site.com> wrote: >>> >>>> On Wed, 01 Apr 2015 15:07:54 -0400, Phil Hobbs >>>> <pcdhSpamMeSenseless@electrooptical.net> wrote: >>>> >>>>> On 04/01/2015 02:00 PM, Jim Thompson wrote: >>>>>> For a simulation situation I need a random number generator with a >>>>>> twist... >>>>>> >>>>>> What I need to simulate is a "random" selection of one-of-16 outputs. >>>>>> >>>>>> Clock "speed" is 12.5kHz ;-) >>>>>> >>>>>> Built of 74HCxx parts is preferred... I have a full ensemble of those >>>>>> device in my PSpice library. >>>>>> >>>>>> Thanks in advance. >>>>>> >>>>>> ...Jim Thompson >>>>>> >>>>> >>>>> How random? You could use a 16-bit PRBS made from two HC299 and an >>>>> HC86. Feed back Q14 XOR Q13, and tap out four stages to a HC154 demux. >>>>> If you need better randomness, use four PRBSes of different length. >>>>> >>>>> Cheers >>>>> >>>>> Phil Hobbs >>>> >>>> I just need semi-random enough to test a fast AGC. >>>> >>>> ...Jim Thompson >>> >>>there is a bias with the 8-bit just use the last 4 bit idea. With 255 >>>'clocks' all states but 0000 will occur 16 times while 0000 will only >>>appear 15 - the cycle then repeats. The lack of the extra 0000 may cause >>>the bias point to continually drift high. >> >> I was wondering about that myself... I'll see if there's a cure. > > r=(75*r+74)%65537 visits 0-65535 with no gaps. > >not that i'd want to build it using 74LS logic.
--- But, if you had to, what would it look like, schematic-wise? John Fields
On Thu, 02 Apr 2015 18:52:57 -0500, John Fields
<jfields@austininstruments.com> wrote:

>On 2 Apr 2015 10:42:50 GMT, Jasen Betts <jasen@xnet.co.nz> wrote: > >>On 2015-04-01, Jim Thompson <To-Email-Use-The-Envelope-Icon@On-My-Web-Site.com> wrote: >>> On Thu, 02 Apr 2015 07:26:29 +1000, "David Eather" <eather@tpg.com.au> >>> wrote: >>> >>>>On Thu, 02 Apr 2015 05:14:13 +1000, Jim Thompson >>>><To-Email-Use-The-Envelope-Icon@on-my-web-site.com> wrote: >>>> >>>>> On Wed, 01 Apr 2015 15:07:54 -0400, Phil Hobbs >>>>> <pcdhSpamMeSenseless@electrooptical.net> wrote: >>>>> >>>>>> On 04/01/2015 02:00 PM, Jim Thompson wrote: >>>>>>> For a simulation situation I need a random number generator with a >>>>>>> twist... >>>>>>> >>>>>>> What I need to simulate is a "random" selection of one-of-16 outputs. >>>>>>> >>>>>>> Clock "speed" is 12.5kHz ;-) >>>>>>> >>>>>>> Built of 74HCxx parts is preferred... I have a full ensemble of those >>>>>>> device in my PSpice library. >>>>>>> >>>>>>> Thanks in advance. >>>>>>> >>>>>>> ...Jim Thompson >>>>>>> >>>>>> >>>>>> How random? You could use a 16-bit PRBS made from two HC299 and an >>>>>> HC86. Feed back Q14 XOR Q13, and tap out four stages to a HC154 demux. >>>>>> If you need better randomness, use four PRBSes of different length. >>>>>> >>>>>> Cheers >>>>>> >>>>>> Phil Hobbs >>>>> >>>>> I just need semi-random enough to test a fast AGC. >>>>> >>>>> ...Jim Thompson >>>> >>>>there is a bias with the 8-bit just use the last 4 bit idea. With 255 >>>>'clocks' all states but 0000 will occur 16 times while 0000 will only >>>>appear 15 - the cycle then repeats. The lack of the extra 0000 may cause >>>>the bias point to continually drift high. >>> >>> I was wondering about that myself... I'll see if there's a cure. >> >> r=(75*r+74)%65537 visits 0-65535 with no gaps. >> >>not that i'd want to build it using 74LS logic. > >--- >But, if you had to, what would it look like, schematic-wise? > >John Fields
<smirk>:-} ...Jim Thompson -- | James E.Thompson | mens | | Analog Innovations | et | | Analog/Mixed-Signal ASIC's and Discrete Systems | manus | | San Tan Valley, AZ 85142 Skype: skypeanalog | | | Voice:(480)460-2350 Fax: Available upon request | Brass Rat | | E-mail Icon at http://www.analog-innovations.com | 1962 | I love to cook with wine. Sometimes I even put it in the food.
On 4/2/2015 7:52 PM, John Fields wrote:
> On 2 Apr 2015 10:42:50 GMT, Jasen Betts <jasen@xnet.co.nz> wrote: > >> On 2015-04-01, Jim Thompson <To-Email-Use-The-Envelope-Icon@On-My-Web-Site.com> wrote: >>> On Thu, 02 Apr 2015 07:26:29 +1000, "David Eather" <eather@tpg.com.au> >>> wrote: >>> >>>> On Thu, 02 Apr 2015 05:14:13 +1000, Jim Thompson >>>> <To-Email-Use-The-Envelope-Icon@on-my-web-site.com> wrote: >>>> >>>>> On Wed, 01 Apr 2015 15:07:54 -0400, Phil Hobbs >>>>> <pcdhSpamMeSenseless@electrooptical.net> wrote: >>>>> >>>>>> On 04/01/2015 02:00 PM, Jim Thompson wrote: >>>>>>> For a simulation situation I need a random number generator with a >>>>>>> twist... >>>>>>> >>>>>>> What I need to simulate is a "random" selection of one-of-16 outputs. >>>>>>> >>>>>>> Clock "speed" is 12.5kHz ;-) >>>>>>> >>>>>>> Built of 74HCxx parts is preferred... I have a full ensemble of those >>>>>>> device in my PSpice library. >>>>>>> >>>>>>> Thanks in advance. >>>>>>> >>>>>>> ...Jim Thompson >>>>>>> >>>>>> >>>>>> How random? You could use a 16-bit PRBS made from two HC299 and an >>>>>> HC86. Feed back Q14 XOR Q13, and tap out four stages to a HC154 demux. >>>>>> If you need better randomness, use four PRBSes of different length. >>>>>> >>>>>> Cheers >>>>>> >>>>>> Phil Hobbs >>>>> >>>>> I just need semi-random enough to test a fast AGC. >>>>> >>>>> ...Jim Thompson >>>> >>>> there is a bias with the 8-bit just use the last 4 bit idea. With 255 >>>> 'clocks' all states but 0000 will occur 16 times while 0000 will only >>>> appear 15 - the cycle then repeats. The lack of the extra 0000 may cause >>>> the bias point to continually drift high. >>> >>> I was wondering about that myself... I'll see if there's a cure. >> >> r=(75*r+74)%65537 visits 0-65535 with no gaps. >> >> not that i'd want to build it using 74LS logic. > > --- > But, if you had to, what would it look like, schematic-wise?
Not so bad. 75 = 64 + 8 + 2 + 1. Include the constant 74 addition that would be four adders. I assume the modulo value is a typo and should be 65536 which comes free. I don't recall any 8 bit adder chips, so using 4 bit ones that would need chips 7 since when adding 64 * r, the lower 4 bits are always zero. -- Rick
On 4/2/2015 8:25 PM, rickman wrote:
> On 4/2/2015 7:52 PM, John Fields wrote: >> On 2 Apr 2015 10:42:50 GMT, Jasen Betts <jasen@xnet.co.nz> wrote: >> >>> r=(75*r+74)%65537 visits 0-65535 with no gaps. >>> >>> not that i'd want to build it using 74LS logic. >> >> --- >> But, if you had to, what would it look like, schematic-wise? > > Not so bad. 75 = 64 + 8 + 2 + 1. Include the constant 74 addition that > would be four adders. I assume the modulo value is a typo and should be > 65536 which comes free. I don't recall any 8 bit adder chips, so using > 4 bit ones that would need chips 7 since when adding 64 * r, the lower 4 > bits are always zero.
shl(6) +----/----\ /--Just one chip on MS 4 bits | \ L | O-----\ | shl(3) / \ +----/----/ \ | \ r --+ O----\ | shl(1) / \ +----/----\ / \ | \ / O--- r' | O-----/ / | / / +---------/ 74 ----/ Each 'O' is two 4 bit adders other than the one summing shf6 and shf3. r is stored in an 8 bit register. Maybe the modulo 65537 isn't a typo. With the addition of an even number (74) the low order bit will never change unless the modulus is odd. That's a whole different animal... But then the range is 0 to 65536, a 17 bit number. Anyone know the correct formula? -- Rick