From: Stromeko@nexgo.de (Achim Gratz) Newsgroups: comp.arch.fpga Subject: Pseudorandom Bitstream Date: 6 Feb 2002 10:37:41 -0800 Organization: http://groups.google.com/ Lines: 25 Message-ID: <73b09d4c.0202061037.4d30d8a6@posting.google.com> NNTP-Posting-Host: 212.144.59.78 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: posting.google.com 1013020662 9020 127.0.0.1 (6 Feb 2002 18:37:42 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: 6 Feb 2002 18:37:42 GMT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!cyclone.bc.net!newsfeed.stanford.edu!postnews1.google.com!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:14009 [I posted a similar message earlier, but it seems it didn't get through. My apologies if you see this twice.] Hello, I would like to know if there are efficient methods, easily implementable with high speed in an FPGA, to produce a pseudorandom bitstream with a known and finely, at runtime adjustable density of 1s or 0s. The density would be below 1/8 or 1/32, this excludes densities around 0.5 that are easily obtained with LSFR. If several such bitstreams could be produced that have no correlation amongst each other that would be great. The randomness really is only a requirement as far as the correlation/autocorrelation properties go and that the bandlimited spectrum of the integral of the signal must be white. I have found a few leads on LFSR implementations that yield pink instead of white noise, but AFAIK noone figured out how to obtain arbitrary let alone continuously adjustable frequency responses. Plus the pink noise, to the best of my knowledge, is not obtained from the bitstream, but some code the LFSR outputs. Any hints in which directions I might search? Achim. ###### From: Mike Treseler Newsgroups: comp.arch.fpga Subject: Re: Pseudorandom Bitstream Date: Wed, 06 Feb 2002 10:45:37 -0800 Organization: Fluke Networks Lines: 12 Message-ID: <3C6179D1.789F47C4@flukenetworks.com> References: <73b09d4c.0202061037.4d30d8a6@posting.google.com> NNTP-Posting-Host: slick.tc.fluke.com Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: Mozilla 4.77 [en] (X11; U; Linux 2.4.7-4GB i686) X-Accept-Language: en Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!fr.clara.net!heighliner.fr.clara.net!news.tele.dk!small.news.tele.dk!129.250.35.146!iad-peer.news.verio.net!news.verio.net!washdc3-snh1.gtei.net!evrtwa1-snf1.gtei.net!news.gtei.net!fluke!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:13998 Achim Gratz wrote: > I would like to know if there are efficient methods, easily > implementable with high speed in an FPGA, to produce a pseudorandom > bitstream with a known and finely, at runtime adjustable density of 1s > or 0s. How about one LFSR for the basic bitstream and another to pick the bit positions to zero out for the required density setting. -- Mike Treseler ###### Message-ID: <3C617D80.98BA6DF5@andraka.com> From: Ray Andraka Organization: Andraka Consulting Group, Inc X-Mailer: Mozilla 4.77 [en] (WinNT; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: Pseudorandom Bitstream References: <73b09d4c.0202061037.4d30d8a6@posting.google.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 63 Date: Wed, 06 Feb 2002 18:55:25 GMT NNTP-Posting-Host: 24.13.238.93 X-Complaints-To: abuse@cox.net X-Trace: news2.east.cox.net 1013021725 24.13.238.93 (Wed, 06 Feb 2002 13:55:25 EST) NNTP-Posting-Date: Wed, 06 Feb 2002 13:55:25 EST Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed.wirehub.nl!64.154.60.70.MISMATCH!newsfeeds-atl2!newsfeeds-atl1.usenetserver.com!cox.net!news2.east.cox.net.POSTED!53ab2750!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:13991 One technique for a uniform distribution is to run the LFSR at a faster rate and use groups of bits to generate your density. For example, for a 1 in 8 density you could use 3 consecutive bits out of an LFSR, if they are all '0' then the output is '1', otherwise it is zero. You have to advance the LFSR by 3 bits per output sample in order to make this work. You can't just take multiple bits out of the LFSR on each clock because the additional bits are just time shifted copies of the first bit. ALternatively you could use parallel LFSRs each seeded at a different place in the sequence so that you can get a new output on every clock. If you used, say 16 uniquely seeded long LFSRs, you could get an arbitrary threshold on a uniform variable that could be set at anywhere from 0 to 65535/65536. If you do this in xilinx, the individual LFSRs can be made very compact (1 CLB) using the SRL16 shift registers (and they could easily be long enough not to repeat within your lifetime once seeded). Another technique, which allows you to get at arbitrary distributions, is to use the LFSR value as a key to search a cdf table. (you could address the table directly if it is small enough). This technique is discussed briefly in my paper, "An FPGA Based Processor Yields a Real Time High Fidelity Radar Environment Simulator" which is available on my website. In that case a binary search engine used a 32 bit LFSR as a key to a 32 bit wide by 128 word deep table containing the CDF of the distribution (in that case it was a modified Rayleigh distribution). Achim Gratz wrote: > [I posted a similar message earlier, but it seems it didn't get > through. My apologies if you see this twice.] > > Hello, > > I would like to know if there are efficient methods, easily > implementable with high speed in an FPGA, to produce a pseudorandom > bitstream with a known and finely, at runtime adjustable density of 1s > or 0s. The density would be below 1/8 or 1/32, this excludes densities > around 0.5 that are easily obtained with LSFR. If several such > bitstreams could be produced that have no correlation amongst each > other that would be great. The randomness really is only a requirement > as far as the correlation/autocorrelation properties go and that the > bandlimited spectrum of the integral of the signal must be white. > > I have found a few leads on LFSR implementations that yield pink > instead of white noise, but AFAIK noone figured out how to obtain > arbitrary let alone continuously adjustable frequency responses. Plus > the pink noise, to the best of my knowledge, is not obtained from the > bitstream, but some code the LFSR outputs. > > Any hints in which directions I might search? > > Achim. -- --Ray Andraka, P.E. President, the Andraka Consulting Group, Inc. 401/884-7930 Fax 401/884-7950 email ray@andraka.com http://www.andraka.com "They that give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." -Benjamin Franklin, 1759 ###### From: Stromeko@nexgo.de (Achim Gratz) Newsgroups: comp.arch.fpga Subject: Re: Pseudorandom Bitstream Date: 7 Feb 2002 03:37:02 -0800 Organization: http://groups.google.com/ Lines: 36 Message-ID: <73b09d4c.0202070337.58808aaf@posting.google.com> References: <73b09d4c.0202061037.4d30d8a6@posting.google.com> <3C617D80.98BA6DF5@andraka.com> NNTP-Posting-Host: 192.35.17.233 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: posting.google.com 1013081823 742 127.0.0.1 (7 Feb 2002 11:37:03 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: 7 Feb 2002 11:37:03 GMT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.ifi.unizh.ch!30795!news.imp.ch!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed.stanford.edu!sn-xit-01!sn-xit-02!supernews.com!postnews1.google.com!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:14057 Ray Andraka wrote in message news:<3C617D80.98BA6DF5@andraka.com>... > One technique for a uniform distribution is to run the LFSR at a faster > rate and use groups of bits to generate your density. That was the source of my problem, I need to run the LFSR at the maximum speed I can get because I need it to dither another bitstream that is produced at 1...5MHz. > For example, for a > 1 in 8 density you could use 3 consecutive bits out of an LFSR, if they > are all '0' then the output is '1', otherwise it is zero. You have to > advance the LFSR by 3 bits per output sample in order to make this work. > You can't just take multiple bits out of the LFSR on each clock because > the additional bits are just time shifted copies of the first bit. > ALternatively you could use parallel LFSRs each seeded at a different > place in the sequence so that you can get a new output on every clock. I was under the impression that while the bitstream of an LFSR is a very good approximation to being random, codes built in that way might not be that good. Any papers on how to know in advance, without fooling around with the feedback taps? > If you used, say 16 uniquely seeded long LFSRs, you could get an arbitrary > threshold on a uniform variable that could be set at anywhere from 0 to > 65535/65536. If you do this in xilinx, the individual LFSRs can be made > very compact (1 CLB) using the SRL16 shift registers (and they could > easily be long enough not to repeat within your lifetime once seeded). That sounds wonderful, I was thinking to use Spartan-II or Virtex-II devices. [...] I'll look up your paper later. Thanks for your suggestions. Achim. ###### From: vt313@comsys.ntu-kpi.kiev.ua Newsgroups: comp.arch.fpga Subject: Re: Pseudorandom Bitstream Date: Thu, 07 Feb 2002 15:31:37 +0200 Organization: NTUU "KPI" Lines: 31 Message-ID: <3C6281B9.4EB0B636@comsys.ntu-kpi.kiev.ua> References: <73b09d4c.0202061037.4d30d8a6@posting.google.com> <3C617D80.98BA6DF5@andraka.com> <73b09d4c.0202070337.58808aaf@posting.google.com> NNTP-Posting-Host: pm000-2.comsys.ntu-kpi.kiev.ua Mime-Version: 1.0 Content-Type: text/plain; charset=EUC-KR Content-Transfer-Encoding: 7bit X-Trace: igloo.uran.net.ua 1013088808 376 10.18.48.13 (7 Feb 2002 13:33:28 GMT) X-Complaints-To: newsmaster@news.ntu-kpi.kiev.ua NNTP-Posting-Date: Thu, 7 Feb 2002 13:33:28 +0000 (UTC) X-Mailer: Mozilla 4.72 [en] (Win98; I) X-Accept-Language: en Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news-ge.switch.ch!newsfeed00.sul.t-online.de!t-online.de!newsfeed.gamma.ru!Gamma.RU!carrier.kiev.ua!news.uran.net.ua!news.ntu-kpi.kiev.ua!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:14047 Achim Gratz wrote: > > Ray Andraka wrote in message news:<3C617D80.98BA6DF5@andraka.com>... > > One technique for a uniform distribution is to run the LFSR at a faster > > rate and use groups of bits to generate your density. > > That was the source of my problem, I need to run the LFSR at the > maximum speed I can get because I need it to dither another bitstream > that is produced at 1...5MHz. > In the LSFR bitstream the bytes of neighboring bits, considered as signed vectors, are practically uncorrelated, and belong to the interval (-1.0 : 1.0). Therefore LSFR generator at 100 MHz provides the byte stream at 100 MHz. If you add couples of neigboring sampling bytes from LSFR, then you get the approximation of the "triangle" distribution. If you want the Gaussian distribution, then you would add n>10 neigboring sampling bytes from LSFR, and get the rather exact approximation of the Gaussian distribution. Anatoli S. ###### Message-ID: <3C628594.E7CCC966@andraka.com> From: Ray Andraka Organization: Andraka Consulting Group, Inc X-Mailer: Mozilla 4.77 [en] (WinNT; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: Pseudorandom Bitstream References: <73b09d4c.0202061037.4d30d8a6@posting.google.com> <3C617D80.98BA6DF5@andraka.com> <73b09d4c.0202070337.58808aaf@posting.google.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 61 Date: Thu, 07 Feb 2002 13:44:39 GMT NNTP-Posting-Host: 68.9.153.21 X-Complaints-To: abuse@cox.net X-Trace: news1.east.cox.net 1013089479 68.9.153.21 (Thu, 07 Feb 2002 08:44:39 EST) NNTP-Posting-Date: Thu, 07 Feb 2002 08:44:39 EST Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.imp.ch!news.imp.ch!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed.wirehub.nl!64.154.60.70.MISMATCH!newsfeeds-atl2!newsfeeds-atl1.usenetserver.com!cox.net!news1.east.cox.net.POSTED!53ab2750!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:14031 The thing you need to be careful with an LFSR is that you can only take one bit per clock. If you take more than one bit, the second bit is highly correlated (it is a time shifted copy of the first bit) to the first, so you lose the randomness. A common mistake is to take several bits broadside out of the LFSR and then clock it only once per sample. The LFSR by itself is not a good way for producing a cryptographic bit stream because you can reconstruct the polynomial from just N+1 bits where N is the length of the LFSR. Once you know the polynomial and the current state (which you also discover in those N+1 bits), you can predict the rest of the sequence. Cryptographic systems use considerably more elaborate techniques to make it harder to recover the key stream. Achim Gratz wrote: > Ray Andraka wrote in message news:<3C617D80.98BA6DF5@andraka.com>... > > One technique for a uniform distribution is to run the LFSR at a faster > > rate and use groups of bits to generate your density. > > That was the source of my problem, I need to run the LFSR at the > maximum speed I can get because I need it to dither another bitstream > that is produced at 1...5MHz. > > > For example, for a > > 1 in 8 density you could use 3 consecutive bits out of an LFSR, if they > > are all '0' then the output is '1', otherwise it is zero. You have to > > advance the LFSR by 3 bits per output sample in order to make this work. > > You can't just take multiple bits out of the LFSR on each clock because > > the additional bits are just time shifted copies of the first bit. > > ALternatively you could use parallel LFSRs each seeded at a different > > place in the sequence so that you can get a new output on every clock. > > I was under the impression that while the bitstream of an LFSR is a > very good approximation to being random, codes built in that way might > not be that good. Any papers on how to know in advance, without > fooling around with the feedback taps? > > > If you used, say 16 uniquely seeded long LFSRs, you could get an arbitrary > > threshold on a uniform variable that could be set at anywhere from 0 to > > 65535/65536. If you do this in xilinx, the individual LFSRs can be made > > very compact (1 CLB) using the SRL16 shift registers (and they could > > easily be long enough not to repeat within your lifetime once seeded). > > That sounds wonderful, I was thinking to use Spartan-II or Virtex-II > devices. > > [...] > I'll look up your paper later. Thanks for your suggestions. > > Achim. -- --Ray Andraka, P.E. President, the Andraka Consulting Group, Inc. 401/884-7930 Fax 401/884-7950 email ray@andraka.com http://www.andraka.com "They that give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." -Benjamin Franklin, 1759 ###### Message-ID: <3C62A21F.C8BFFA23@andraka.com> From: Ray Andraka Organization: Andraka Consulting Group, Inc X-Mailer: Mozilla 4.77 [en] (WinNT; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: Pseudorandom Bitstream References: <73b09d4c.0202061037.4d30d8a6@posting.google.com> <3C617D80.98BA6DF5@andraka.com> <73b09d4c.0202070337.58808aaf@posting.google.com> <3C6281B9.4EB0B636@comsys.ntu-kpi.kiev.ua> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 62 Date: Thu, 07 Feb 2002 15:46:26 GMT NNTP-Posting-Host: 68.9.153.21 X-Complaints-To: abuse@cox.net X-Trace: news1.east.cox.net 1013096786 68.9.153.21 (Thu, 07 Feb 2002 10:46:26 EST) NNTP-Posting-Date: Thu, 07 Feb 2002 10:46:26 EST Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.imp.ch!news.imp.ch!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!jfk3-feed1.news.digex.net!intermedia!newsfeed.wirehub.nl!64.154.60.70.MISMATCH!newsfeeds-atl2!newsfeeds-atl1.usenetserver.com!cox.net!news1.east.cox.net.POSTED!53ab2750!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:14032 No. The neighboring bits, when taken a byte at a time from an LFSR are time shifted copies of previous bits. If you take more than 1 bit per clock from an LFSR, you lose the uniform white properties. Consider the 4 bit LFSR X^3+X^2+1: 0000 0001 0011 0111 1110 1101 1011 0110 1100 1001 0010 0101 1010 0100 1000 0000 Note that only the right most bit is random, the other bits are the same as the rightmost but delayed by 1,2 and 3 clocks. If you use more than one bit per clock from an LFSR, you wind up with a correlation that colors the output and destroys the uniform random properties. The bottom line is that an LFSR at 100MHz produces a random BIT stream at 100 MHz, not a byte stream. To get a random byte stream, you need to clock the LFSR 8 times between samples so as to get new bit values (uncorrelated to any bits in previous sample) in all 8 bits, which gives you a random byte stream of 100/8= 12.5 MHz. vt313@comsys.ntu-kpi.kiev.ua wrote: > In the LSFR bitstream the bytes of neighboring bits, > considered as signed vectors, are practically > uncorrelated, and belong to the interval (-1.0 : 1.0). > Therefore LSFR generator at 100 MHz > provides the byte stream at 100 MHz. > > If you add couples of neigboring > sampling bytes from LSFR, > then you get the approximation > of the "triangle" distribution. > > If you want the Gaussian distribution, > then you would add n>10 neigboring > sampling bytes from LSFR, > and get the rather exact approximation > of the Gaussian distribution. > > Anatoli S. -- --Ray Andraka, P.E. President, the Andraka Consulting Group, Inc. 401/884-7930 Fax 401/884-7950 email ray@andraka.com http://www.andraka.com "They that give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." -Benjamin Franklin, 1759 ###### From: vt313@comsys.ntu-kpi.kiev.ua Newsgroups: comp.arch.fpga Subject: Re: Pseudorandom Bitstream Date: Thu, 07 Feb 2002 18:10:03 +0200 Organization: NTUU "KPI" Lines: 42 Message-ID: <3C62A6DB.9A443EA2@comsys.ntu-kpi.kiev.ua> References: <73b09d4c.0202061037.4d30d8a6@posting.google.com> <3C617D80.98BA6DF5@andraka.com> <73b09d4c.0202070337.58808aaf@posting.google.com> <3C6281B9.4EB0B636@comsys.ntu-kpi.kiev.ua> <3C62A21F.C8BFFA23@andraka.com> NNTP-Posting-Host: pm000-2.comsys.ntu-kpi.kiev.ua Mime-Version: 1.0 Content-Type: text/plain; charset=EUC-KR Content-Transfer-Encoding: 7bit X-Trace: igloo.uran.net.ua 1013098317 6497 10.18.48.13 (7 Feb 2002 16:11:57 GMT) X-Complaints-To: newsmaster@news.ntu-kpi.kiev.ua NNTP-Posting-Date: Thu, 7 Feb 2002 16:11:57 +0000 (UTC) X-Mailer: Mozilla 4.72 [en] (Win98; I) X-Accept-Language: en Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!fr.clara.net!heighliner.fr.clara.net!isdnet!news.internetia.pl!news.nask.pl!news.uar.net!carrier.kiev.ua!news.uran.net.ua!news.ntu-kpi.kiev.ua!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:14048 Ray Andraka wrote: > > No. The neighboring bits, when taken a byte at a time from an LFSR are time shifted copies > of previous bits. If you take more than 1 bit per clock from an LFSR, you lose the uniform > white properties. Consider the 4 bit LFSR X^3+X^2+1: > > 0000 > 0001 > 0011 > 0111 > 1110 > 1101 > 1011 > 0110 > 1100 > 1001 > 0010 > 0101 > 1010 > 0100 > 1000 > 0000 > > Note that only the right most bit is random, the other bits are the same as the rightmost > but delayed by 1,2 and 3 clocks. If you use more than one bit per clock from an LFSR, you > wind up with a correlation that colors the output and destroys the uniform random > properties. The bottom line is that an LFSR at 100MHz produces a random BIT stream at 100 > MHz, not a byte stream. To get a random byte stream, you need to clock the LFSR 8 times > between samples so as to get new bit values (uncorrelated to any bits in previous sample) > in all 8 bits, which gives you a random byte stream of 100/8= 12.5 MHz. > You are right, if you consider the similarity of words as the correlation. But if you calculate the autocorrelation function for this sequence for the rather long period N of LSFR (but exactly N elements) then you get 1 dirac impulse and other zeros. Anatoli .S. ###### From: jrcinnh@yahoo.com (jrc) Newsgroups: comp.arch.fpga Subject: Re: Pseudorandom Bitstream Date: 7 Feb 2002 13:00:02 -0800 Organization: http://groups.google.com/ Lines: 102 Message-ID: <48d2564d.0202071300.367a69aa@posting.google.com> References: <73b09d4c.0202061037.4d30d8a6@posting.google.com> <3C617D80.98BA6DF5@andraka.com> <73b09d4c.0202070337.58808aaf@posting.google.com> <3C6281B9.4EB0B636@comsys.ntu-kpi.kiev.ua> <3C62A21F.C8BFFA23@andraka.com> NNTP-Posting-Host: 12.105.64.190 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: posting.google.com 1013115603 17403 127.0.0.1 (7 Feb 2002 21:00:03 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: 7 Feb 2002 21:00:03 GMT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!cyclone.bc.net!newsfeed.stanford.edu!postnews1.google.com!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:14092 It is pretty easy to contruct a state-machine to mimic the effects of a LFSR shift register that has been clocked an arbitrary number of times. To use your example the normal logic for X^3+X^2+1 using four flip-flops is: ff0=ff3^ff2^1 (xnor the last two flip-flops in the shift register) ff1=ff0 (shift) ff2=ff1 (shift) ff3=ff2 (shift) For each clock, the following design will produce the same four bit sequence produced by clocking the orignal design four times: ff0=ff3^ff2^ff0 (three term xor) ff1=ff1^ff0^1 (xnor) ff2=ff2^ff1^1 (xnor) ff3=ff3^ff2^1 (xnor) So the bit sequence for ff0 the upper design is: 0111011001010000111... The bit sequence for the four flip-flops on second design is: 3210 ---- 0111 0110 0101 0000 1110 ... I always called this generating pseudorandom in parallel. It is used a lot in communications work. Once you get the knack you can generate any sequence in any width. If you add flip-flops you can actually generate this sequence 8 bits at a time or even wider. JRC Ray Andraka wrote in message news:<3C62A21F.C8BFFA23@andraka.com>... > No. The neighboring bits, when taken a byte at a time from an LFSR are time shifted copies > of previous bits. If you take more than 1 bit per clock from an LFSR, you lose the uniform > white properties. Consider the 4 bit LFSR X^3+X^2+1: > > 0000 > 0001 > 0011 > 0111 > 1110 > 1101 > 1011 > 0110 > 1100 > 1001 > 0010 > 0101 > 1010 > 0100 > 1000 > 0000 > > Note that only the right most bit is random, the other bits are the same as the rightmost > but delayed by 1,2 and 3 clocks. If you use more than one bit per clock from an LFSR, you > wind up with a correlation that colors the output and destroys the uniform random > properties. The bottom line is that an LFSR at 100MHz produces a random BIT stream at 100 > MHz, not a byte stream. To get a random byte stream, you need to clock the LFSR 8 times > between samples so as to get new bit values (uncorrelated to any bits in previous sample) > in all 8 bits, which gives you a random byte stream of 100/8= 12.5 MHz. > > vt313@comsys.ntu-kpi.kiev.ua wrote: > > > In the LSFR bitstream the bytes of neighboring bits, > > considered as signed vectors, are practically > > uncorrelated, and belong to the interval (-1.0 : 1.0). > > Therefore LSFR generator at 100 MHz > > provides the byte stream at 100 MHz. > > > > If you add couples of neigboring > > sampling bytes from LSFR, > > then you get the approximation > > of the "triangle" distribution. > > > > If you want the Gaussian distribution, > > then you would add n>10 neigboring > > sampling bytes from LSFR, > > and get the rather exact approximation > > of the Gaussian distribution. > > > > Anatoli S. > > -- > --Ray Andraka, P.E. > President, the Andraka Consulting Group, Inc. > 401/884-7930 Fax 401/884-7950 > email ray@andraka.com > http://www.andraka.com > > "They that give up essential liberty to obtain a little > temporary safety deserve neither liberty nor safety." > -Benjamin Franklin, 1759 ###### Message-ID: <3C630AD6.7FD04150@andraka.com> From: Ray Andraka Organization: Andraka Consulting Group, Inc X-Mailer: Mozilla 4.77 [en] (WinNT; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: Pseudorandom Bitstream References: <73b09d4c.0202061037.4d30d8a6@posting.google.com> <3C617D80.98BA6DF5@andraka.com> <73b09d4c.0202070337.58808aaf@posting.google.com> <3C6281B9.4EB0B636@comsys.ntu-kpi.kiev.ua> <3C62A21F.C8BFFA23@andraka.com> <48d2564d.0202071300.367a69aa@posting.google.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 120 Date: Thu, 07 Feb 2002 23:13:12 GMT NNTP-Posting-Host: 68.9.153.21 X-Complaints-To: abuse@cox.net X-Trace: news1.east.cox.net 1013123592 68.9.153.21 (Thu, 07 Feb 2002 18:13:12 EST) NNTP-Posting-Date: Thu, 07 Feb 2002 18:13:12 EST Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.ifi.unizh.ch!news.imp.ch!news.imp.ch!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed.wirehub.nl!64.154.60.70.MISMATCH!newsfeeds-atl2!newsfeeds-atl1.usenetserver.com!cox.net!news1.east.cox.net.POSTED!53ab2750!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:14075 Exactly. In fact, all the LFSR is is a special case of the CRC hardware. I did't want to confuse the issue, but as you say, you can create a parallel version of the LFST that appears at the outputs to advance N clocks in a single clock. jrc wrote: > It is pretty easy to contruct a state-machine to mimic the effects of > a LFSR shift register that has been clocked an arbitrary number of > times. To use your example the normal logic for X^3+X^2+1 using four > flip-flops is: > > ff0=ff3^ff2^1 (xnor the last two flip-flops in the shift register) > ff1=ff0 (shift) > ff2=ff1 (shift) > ff3=ff2 (shift) > > For each clock, the following design will produce the same four bit > sequence produced by clocking the orignal design four times: > > ff0=ff3^ff2^ff0 (three term xor) > ff1=ff1^ff0^1 (xnor) > ff2=ff2^ff1^1 (xnor) > ff3=ff3^ff2^1 (xnor) > > So the bit sequence for ff0 the upper design is: > > 0111011001010000111... > > The bit sequence for the four flip-flops on second design is: > > 3210 > ---- > 0111 > 0110 > 0101 > 0000 > 1110 > ... > > I always called this generating pseudorandom in parallel. It is used a > lot in communications work. Once you get the knack you can generate > any sequence in any width. If you add flip-flops you can actually > generate this sequence 8 bits at a time or even wider. > > JRC > > Ray Andraka wrote in message news:<3C62A21F.C8BFFA23@andraka.com>... > > No. The neighboring bits, when taken a byte at a time from an LFSR are time shifted copies > > of previous bits. If you take more than 1 bit per clock from an LFSR, you lose the uniform > > white properties. Consider the 4 bit LFSR X^3+X^2+1: > > > > 0000 > > 0001 > > 0011 > > 0111 > > 1110 > > 1101 > > 1011 > > 0110 > > 1100 > > 1001 > > 0010 > > 0101 > > 1010 > > 0100 > > 1000 > > 0000 > > > > Note that only the right most bit is random, the other bits are the same as the rightmost > > but delayed by 1,2 and 3 clocks. If you use more than one bit per clock from an LFSR, you > > wind up with a correlation that colors the output and destroys the uniform random > > properties. The bottom line is that an LFSR at 100MHz produces a random BIT stream at 100 > > MHz, not a byte stream. To get a random byte stream, you need to clock the LFSR 8 times > > between samples so as to get new bit values (uncorrelated to any bits in previous sample) > > in all 8 bits, which gives you a random byte stream of 100/8= 12.5 MHz. > > > > vt313@comsys.ntu-kpi.kiev.ua wrote: > > > > > In the LSFR bitstream the bytes of neighboring bits, > > > considered as signed vectors, are practically > > > uncorrelated, and belong to the interval (-1.0 : 1.0). > > > Therefore LSFR generator at 100 MHz > > > provides the byte stream at 100 MHz. > > > > > > If you add couples of neigboring > > > sampling bytes from LSFR, > > > then you get the approximation > > > of the "triangle" distribution. > > > > > > If you want the Gaussian distribution, > > > then you would add n>10 neigboring > > > sampling bytes from LSFR, > > > and get the rather exact approximation > > > of the Gaussian distribution. > > > > > > Anatoli S. > > > > -- > > --Ray Andraka, P.E. > > President, the Andraka Consulting Group, Inc. > > 401/884-7930 Fax 401/884-7950 > > email ray@andraka.com > > http://www.andraka.com > > > > "They that give up essential liberty to obtain a little > > temporary safety deserve neither liberty nor safety." > > -Benjamin Franklin, 1759 -- --Ray Andraka, P.E. President, the Andraka Consulting Group, Inc. 401/884-7930 Fax 401/884-7950 email ray@andraka.com http://www.andraka.com "They that give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." -Benjamin Franklin, 1759 ###### From: Stromeko@nexgo.de (Achim Gratz) Newsgroups: comp.arch.fpga Subject: Re: Pseudorandom Bitstream Date: 8 Feb 2002 08:04:40 -0800 Organization: http://groups.google.com/ Lines: 27 Message-ID: <73b09d4c.0202080804.4f7a69a0@posting.google.com> References: <73b09d4c.0202061037.4d30d8a6@posting.google.com> <3C617D80.98BA6DF5@andraka.com> <73b09d4c.0202070337.58808aaf@posting.google.com> <3C6281B9.4EB0B636@comsys.ntu-kpi.kiev.ua> <3C62A21F.C8BFFA23@andraka.com> <48d2564d.0202071300.367a69aa@posting.google.com> <3C630AD6.7FD04150@andraka.com> NNTP-Posting-Host: 192.35.17.233 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: posting.google.com 1013184283 11695 127.0.0.1 (8 Feb 2002 16:04:43 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: 8 Feb 2002 16:04:43 GMT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news-out.spamkiller.net!propagator-maxim!news-in.spamkiller.net!feed.newsfeeds.com!news-hog.berkeley.edu!ucberkeley!newsfeed.stanford.edu!sn-xit-01!sn-xit-02!supernews.com!postnews1.google.com!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:14094 [...] OK, let me summarize to see if I got everything correct: 1. From a uniformly distributed sequence of n-bit numbers one can generate a non-uniformly distributed single-bitstream by squashing the n-bit by a comparator, allowing for densities to be chosen from 0 to 1 in 1/2^n increments. Interestingly (and in relation to my original question) this seems to mean that I can partition the n-bit into (j+k)-bit and obtain 2^j completely uncorrelated sequences in 1/2^k increments and densities ranging from 0 to 1/2^j by using 2^j two-sided comparators with non-overlapping ranges. Using the binary partition scheme from above that simplifies to just a one-sided comparator in k bits and a decoder that enables/disables the output based on j bits. 2. Pseudorandom n-bitstreams may be produced in various ways, which relate to polynomials in GF2 (esp. CRC polynomials). A parallel output can be implemented by unrolling and pipelining an LFSR for instance or you may just go for the polynomial directly. (I seem to remember that some/most of these polynomials are cryptographically weak, but that isn't an issue for the application I have in mind. I just need a white spectrum.) Achim. ###### Message-ID: <3C642D8B.BF55AD50@andraka.com> From: Ray Andraka Organization: Andraka Consulting Group, Inc X-Mailer: Mozilla 4.77 [en] (WinNT; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: Pseudorandom Bitstream References: <73b09d4c.0202061037.4d30d8a6@posting.google.com> <3C617D80.98BA6DF5@andraka.com> <73b09d4c.0202070337.58808aaf@posting.google.com> <3C6281B9.4EB0B636@comsys.ntu-kpi.kiev.ua> <3C62A21F.C8BFFA23@andraka.com> <48d2564d.0202071300.367a69aa@posting.google.com> <3C630AD6.7FD04150@andraka.com> <73b09d4c.0202080804.4f7a69a0@posting.google.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 58 Date: Fri, 08 Feb 2002 19:53:32 GMT NNTP-Posting-Host: 68.9.153.21 X-Complaints-To: abuse@cox.net X-Trace: news1.east.cox.net 1013198012 68.9.153.21 (Fri, 08 Feb 2002 14:53:32 EST) NNTP-Posting-Date: Fri, 08 Feb 2002 14:53:32 EST Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.imp.ch!news.imp.ch!fr.clara.net!heighliner.fr.clara.net!news-hub.siol.net!newsfeeds-atl2!newsfeeds-atl1.usenetserver.com!cox.net!news1.east.cox.net.POSTED!53ab2750!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:14079 Achim Gratz wrote: > [...] > > OK, let me summarize to see if I got everything correct: > > 1. From a uniformly distributed sequence of n-bit numbers one can > generate a non-uniformly distributed single-bitstream by squashing the > n-bit by a comparator, allowing for densities to be chosen from 0 to 1 > in 1/2^n increments. Interestingly (and in relation to my original > question) this seems to mean that I can partition the n-bit into > (j+k)-bit and obtain 2^j completely uncorrelated sequences in 1/2^k > increments and densities ranging from 0 to 1/2^j by using 2^j > two-sided comparators with non-overlapping ranges. Using the binary > partition scheme from above that simplifies to just a one-sided > comparator in k bits and a decoder that enables/disables the output > based on j bits. Hadn't looked at it that way, but yeah, that sounds about right. > > > 2. Pseudorandom n-bitstreams may be produced in various ways, which > relate to polynomials in GF2 (esp. CRC polynomials). A parallel output > can be implemented by unrolling and pipelining an LFSR for instance or > you may just go for the polynomial directly. Yep. > > > (I seem to remember that some/most of these polynomials are > cryptographically weak, but that isn't an issue for the application I > have in mind. I just need a white spectrum.) An LFSR by itself is cryptographically weak regardless of the polynomial because you only need N+1 bits to recover the key and initial state, and therefore the plain text stream. Nevertheless, LFSRs do fall into the class of GF2 algorithms. > > > Achim. -- --Ray Andraka, P.E. President, the Andraka Consulting Group, Inc. 401/884-7930 Fax 401/884-7950 email ray@andraka.com http://www.andraka.com "They that give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." -Benjamin Franklin, 1759 ###### From: Stromeko@nexgo.de (Achim Gratz) Newsgroups: comp.arch.fpga Subject: Re: Pseudorandom Bitstream Date: 12 Feb 2002 03:05:37 -0800 Organization: http://groups.google.com/ Lines: 34 Message-ID: <73b09d4c.0202120305.6cf0ed93@posting.google.com> References: <73b09d4c.0202061037.4d30d8a6@posting.google.com> <3C617D80.98BA6DF5@andraka.com> NNTP-Posting-Host: 192.35.17.233 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: posting.google.com 1013511937 32420 127.0.0.1 (12 Feb 2002 11:05:37 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: 12 Feb 2002 11:05:37 GMT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed.stanford.edu!postnews1.google.com!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:14187 Ray Andraka wrote in message news:<3C617D80.98BA6DF5@andraka.com>... > If you do this in xilinx, the individual LFSRs can be made > very compact (1 CLB) using the SRL16 shift registers (and they could > easily be long enough not to repeat within your lifetime once seeded). I installed the WEBpack software and tried a few implementations. Currently the shift register (SRL16 based implementation inferred from VHDL) limits the speed even though it's listed as zero levels of logic. Even so, it looks like I can get the design (it is quite a bit larger than just the LFSR) to run at about 300MHz (post PAR)in a Spartan-II. With the LFSR speed problem lifted and a few more pipeline registers added I think I can up that to 350...380MHz. Not bad, considering that this is about twice the minimum speed that I targeted. As a sidenote, I started doing this in VHDL (I have done my designs in schematic so far and have a few hours of Verilog experience) to maybe learn something. VHDL is a bit too verbose for my tastes and currently I'm stuck trying to find all the Xilinx specific attributes that I would need to attach to guide the PAR process. Another question: do you really need to write all the conversion functions from STD_LOGIC_VECTOR to integer and back? I would guess that was a standard library function, but I can't look since they are all compiled (or I didn't find the sources, whatever). Achim Gratz. ###### From: "Tim" Newsgroups: comp.arch.fpga Subject: Re: Pseudorandom Bitstream Date: Tue, 12 Feb 2002 12:43:55 -0000 Message-ID: <1013521410.18149.1.nnrp-07.9e9832fa@news.demon.co.uk> References: <73b09d4c.0202061037.4d30d8a6@posting.google.com> <3C617D80.98BA6DF5@andraka.com> <73b09d4c.0202120305.6cf0ed93@posting.google.com> NNTP-Posting-Host: tile.demon.co.uk X-NNTP-Posting-Host: tile.demon.co.uk:158.152.50.250 X-Trace: news.demon.co.uk 1013521410 nnrp-07:18149 NO-IDENT tile.demon.co.uk:158.152.50.250 X-Complaints-To: abuse@demon.net X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2600.0000 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 Lines: 14 Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!newscore.univie.ac.at!newsfeed.online.be!skynet.be!skynet.be!dispose.news.demon.net!news.demon.co.uk!demon!tile.demon.co.uk!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:14194 Achim Gratz wrote > Currently > the shift register (SRL16 based implementation inferred from VHDL) > limits > the speed even though it's listed as zero levels of logic. You can make them faster by always including the flop. This makes your shhift register a 17-bit object (16-bit SRL16, followed by 1-bit FF) ###### Message-ID: <3C69215D.E69A4215@andraka.com> From: Ray Andraka Organization: Andraka Consulting Group, Inc X-Mailer: Mozilla 4.77 [en] (WinNT; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: Pseudorandom Bitstream References: <73b09d4c.0202061037.4d30d8a6@posting.google.com> <3C617D80.98BA6DF5@andraka.com> <73b09d4c.0202120305.6cf0ed93@posting.google.com> <1013521410.18149.1.nnrp-07.9e9832fa@news.demon.co.uk> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 40 Date: Tue, 12 Feb 2002 14:02:43 GMT NNTP-Posting-Host: 68.9.153.21 X-Complaints-To: abuse@cox.net X-Trace: news1.east.cox.net 1013522563 68.9.153.21 (Tue, 12 Feb 2002 09:02:43 EST) NNTP-Posting-Date: Tue, 12 Feb 2002 09:02:43 EST Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!cyclone2.usenetserver.com!usenetserver.com!newsfeeds-atl1.usenetserver.com!cox.net!news1.east.cox.net.POSTED!53ab2750!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:14159 Be careful with the SRL16 timing. There is a minimum pulse width on the WE pin that is not reported by the timing anaylzer. In VirtexE-7, for example the minimum pulse width for the SRL16 write limits the clock to about 235 MHz even though the routing would allow it to go considerably faster. Also, as Tim says, always follow the SRL16 with the associated flip-flop. The clock to Q of the SRL16 is really slow compared to that of the flip-flop. Buffering the output with a flip-flop avoids putting that long clock to Q in series with the prop delay thorugh a LUT and the routing. For the VHDL, include the ieee.numeric_std library. WIth that you can use the signed and unsigned types instead of integers. These are bit vectors closely related to std_logic_vector but since the format is defined you can do math on them. Tim wrote: > Achim Gratz wrote > > > Currently > > the shift register (SRL16 based implementation inferred from VHDL) > > limits > > the speed even though it's listed as zero levels of logic. > > You can make them faster by always including the flop. > This makes your shhift register a 17-bit object > (16-bit SRL16, followed by 1-bit FF) -- --Ray Andraka, P.E. President, the Andraka Consulting Group, Inc. 401/884-7930 Fax 401/884-7950 email ray@andraka.com http://www.andraka.com "They that give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." -Benjamin Franklin, 1759 ###### From: Stromeko@nexgo.de (Achim Gratz) Newsgroups: comp.arch.fpga Subject: Re: Pseudorandom Bitstream Date: 12 Feb 2002 13:38:02 -0800 Organization: http://groups.google.com/ Lines: 43 Message-ID: <73b09d4c.0202121338.1f036669@posting.google.com> References: <73b09d4c.0202061037.4d30d8a6@posting.google.com> <3C617D80.98BA6DF5@andraka.com> <73b09d4c.0202120305.6cf0ed93@posting.google.com> <1013521410.18149.1.nnrp-07.9e9832fa@news.demon.co.uk> <3C69215D.E69A4215@andraka.com> NNTP-Posting-Host: 212.144.59.72 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: posting.google.com 1013549883 17954 127.0.0.1 (12 Feb 2002 21:38:03 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: 12 Feb 2002 21:38:03 GMT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!out.nntp.be!propagator-SanJose!in.nntp.be!nntp-relay.ihug.net!ihug.co.nz!news-hog.berkeley.edu!ucberkeley!newsfeed.stanford.edu!postnews1.google.com!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:14229 Ray Andraka wrote in message news:<3C69215D.E69A4215@andraka.com>... > Be careful with the SRL16 timing. There is a minimum pulse width on the > WE pin that is not reported by the timing anaylzer. In VirtexE-7, for > example the minimum pulse width for the SRL16 write limits the clock to > about 235 MHz even though the routing would allow it to go considerably > faster. Eeew, ugly. Well I guess I can use two interleaved LFSR and still come out ahead of an FF only implementation. > Also, as Tim says, always follow the SRL16 with the associated > flip-flop. The clock to Q of the SRL16 is really slow compared to that > of the flip-flop. Buffering the output with a flip-flop avoids putting > that long clock to Q in series with the prop delay thorugh a LUT and the > routing. I checked the floorplan and the SRL16 are mapped with an FF at their end. However the taps were placed in strategically dubious positions so that a lot of routing was going on to keep the number of SRL16 minimal. Spacing the taps by 17 fixed that particular problem. I have no idea if that is going to be a good LFSR, this is just to see how the mapping works. Result: post PAR the timing analyzer now claims a clock rate of 320MHz for a -6 Spartan-II ... > For the VHDL, include the ieee.numeric_std library. WIth that you can > use the signed and unsigned types instead of integers. These are bit > vectors closely related to std_logic_vector but since the format is > defined you can do math on them. Thanks, that seemed to do the trick. I'm still at loss assigning literals, the compiler wants to get bitstrings or arithmetic expressions with some unsigned signal. BTW, what is IEEE.std_logic_unsigned for? I could not get that to work so far. Aside#2: I plan on getting a CoolRunner-II and Spartan-II(E) dev kit from Insight. Any caveats or opinions on these (preferrably from someone who has used them)? Any other dev kit (must be available _now_ and have a distributor in Germany) that I should have a look at? PCI cards are no-go, I'm strictly notebook based at the moment. Achim Gratz. ###### Message-ID: <3C69B198.C52EA024@andraka.com> From: Ray Andraka Organization: Andraka Consulting Group, Inc X-Mailer: Mozilla 4.77 [en] (WinNT; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: Pseudorandom Bitstream References: <73b09d4c.0202061037.4d30d8a6@posting.google.com> <3C617D80.98BA6DF5@andraka.com> <73b09d4c.0202120305.6cf0ed93@posting.google.com> <1013521410.18149.1.nnrp-07.9e9832fa@news.demon.co.uk> <3C69215D.E69A4215@andraka.com> <73b09d4c.0202121338.1f036669@posting.google.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 98 Date: Wed, 13 Feb 2002 00:18:05 GMT NNTP-Posting-Host: 68.9.153.21 X-Complaints-To: abuse@cox.net X-Trace: news1.east.cox.net 1013559485 68.9.153.21 (Tue, 12 Feb 2002 19:18:05 EST) NNTP-Posting-Date: Tue, 12 Feb 2002 19:18:05 EST Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!newscore.univie.ac.at!news-hub.siol.net!newsfeeds-atl2!newsfeeds-atl1.usenetserver.com!cox.net!news1.east.cox.net.POSTED!53ab2750!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:14208 Achim Gratz wrote: > Ray Andraka wrote in message news:<3C69215D.E69A4215@andraka.com>... > > Be careful with the SRL16 timing. There is a minimum pulse width on the > > WE pin that is not reported by the timing anaylzer. In VirtexE-7, for > > example the minimum pulse width for the SRL16 write limits the clock to > > about 235 MHz even though the routing would allow it to go considerably > > faster. > > Eeew, ugly. Well I guess I can use two interleaved LFSR and still come > out ahead of an FF only implementation. Yep. > > > > Also, as Tim says, always follow the SRL16 with the associated > > flip-flop. The clock to Q of the SRL16 is really slow compared to that > > of the flip-flop. Buffering the output with a flip-flop avoids putting > > that long clock to Q in series with the prop delay thorugh a LUT and the > > routing. > > I checked the floorplan and the SRL16 are mapped with an FF at their > end. However the taps were placed in strategically dubious positions > so that a lot of routing was going on to keep the number of SRL16 > minimal. Spacing the taps by 17 fixed that particular problem. I have > no idea if that is going to be a good LFSR, this is just to see how > the mapping works. Result: post PAR the timing analyzer now claims a > clock rate of 320MHz for a -6 Spartan-II ... Like I said, that is the speed of the routing. From page 16 of the Spartan-II 2.5v FPGA Family:DC and Switching Characteristics (http://www.xilinx.com/partinfo/ds001_3.pdf) the minimum pulse width, high (Tsrph) and Low(Tsrpl) are both 2.9ns for the -6 SpartanII. That means the max clock frequency for the SRL16 is about 172 MHz. This is one of those things not reported by the timing analyzer. Generally speaking you don't want to just pull convenient taps, especially evenly spaced ones as most combinations will result in truncated LFSR sequences. Refer to xilinx app note xapp052 for a table of taps for maximal lenght sequences. You can set the lengths of the SRL16s by setting the address to get taps out at places you need them without going to extremes. I think all the polynomials listed in the xilinx note use either 2 or 4 feedback taps. In most cases, you can pick the length for a convenient tap arrangement -- for example chose the next longer one if it means 2 taps instead of 4. Xilinx: Perhaps a good thing to do would be to add a note in the timing reports when the period constraint on a clock that clocks an SRL16 is less than the minimum period dictated by the min pulse widths. Same for the minimum and maximum clocks for the clkdlls. Several people I am aware of have missed these limitations in recent designs. > > > > For the VHDL, include the ieee.numeric_std library. WIth that you can > > use the signed and unsigned types instead of integers. These are bit > > vectors closely related to std_logic_vector but since the format is > > defined you can do math on them. > > Thanks, that seemed to do the trick. I'm still at loss assigning > literals, the compiler wants to get bitstrings or arithmetic > expressions with some unsigned signal. BTW, what is > IEEE.std_logic_unsigned for? I could not get that to work so far. Std_logic_unsigned and std_logic_signed were synopsis libraries. They generally cannot coexist in the same entity because they have conflicting declarations. Despite the name, they are also not standard among different vendors. For the assignments, you can use casts for related types. Std_logic_vector, unsigned, and signed are related types so; Numeric_std is an IEEE standard library. Us it instead of wrestling with all the problems of std_logic_unsigned, std_logic_arith and std_logic_signed. slv_signal<= std_logic_vector(unsigned_signal); unsigned_signal<= unsigned(slv_signal); Does that answer your question? > > > Aside#2: I plan on getting a CoolRunner-II and Spartan-II(E) dev kit > from Insight. Any caveats or opinions on these (preferrably from > someone who has used them)? Any other dev kit (must be available _now_ > and have a distributor in Germany) that I should have a look at? PCI > cards are no-go, I'm strictly notebook based at the moment. > > Achim Gratz. -- --Ray Andraka, P.E. President, the Andraka Consulting Group, Inc. 401/884-7930 Fax 401/884-7950 email ray@andraka.com http://www.andraka.com "They that give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." -Benjamin Franklin, 1759 ###### From: Stromeko@nexgo.de (Achim Gratz) Newsgroups: comp.arch.fpga Subject: Re: Pseudorandom Bitstream Date: 13 Feb 2002 02:18:15 -0800 Organization: http://groups.google.com/ Lines: 51 Message-ID: <73b09d4c.0202130218.2ee19f63@posting.google.com> References: <73b09d4c.0202061037.4d30d8a6@posting.google.com> <3C617D80.98BA6DF5@andraka.com> <73b09d4c.0202120305.6cf0ed93@posting.google.com> <1013521410.18149.1.nnrp-07.9e9832fa@news.demon.co.uk> <3C69215D.E69A4215@andraka.com> <73b09d4c.0202121338.1f036669@posting.google.com> <3C69B198.C52EA024@andraka.com> NNTP-Posting-Host: 192.35.17.233 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: posting.google.com 1013595495 3085 127.0.0.1 (13 Feb 2002 10:18:15 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: 13 Feb 2002 10:18:15 GMT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!feeder.qis.net!sn-xit-02!supernews.com!postnews1.google.com!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:14234 Ray Andraka wrote in message news:<3C69B198.C52EA024@andraka.com>... > Like I said, that is the speed of the routing. [...] Sure, I took notice (as I said, I will probably interleave two LFSR as the FF only implementation takes too many CLB). I just did a quick hack to ascertain that the extra delay was really coming from routing. Of course I'll need to do this optimization again when I've settled on an LFSR polynomial (downloaded XAPP052 a few days ago, still waiting for time to read it). > Xilinx: Perhaps a good thing to do would be to add a note in the timing reports when the > period constraint on a clock that clocks an SRL16 is less than the minimum period dictated > by the min pulse widths. Same for the minimum and maximum clocks for the clkdlls. > Several people I am aware of have missed these limitations in recent designs. I second that. I would have fallen into that trap and been burned quite badly. Especially worrysome is that with default settings the synthesis will automatically infer SRL16 for shift registers that the user might think should have been instantiated as FF chains. I wonder if it would be possible to "fix" that by a timing constraint. Is it possible to put constraints on all instances of some particular primitive (that is invisible to the original HDL nonetheless) instead of on specific nets? > Std_logic_unsigned and std_logic_signed were synopsis libraries. They generally cannot > coexist in the same entity because they have conflicting declarations. Despite the name, > they are also not standard among different vendors. For the assignments, you can use > casts for related types. Std_logic_vector, unsigned, and signed are related types so; > Numeric_std is an IEEE standard library. Us it instead of wrestling with all the problems > of std_logic_unsigned, std_logic_arith and std_logic_signed. > > slv_signal<= std_logic_vector(unsigned_signal); > unsigned_signal<= unsigned(slv_signal); > > Does that answer your question? Not fully. I get errors for constructs like: unsigned_signal <= 0; -- compiler wants bitstring for literal unsigned_signal <= unsigned(0); -- compiler: can not be converted to unsigned These must have a simple solution, as for instance unsigned_signal <= unsigned_signal*0; -- works like a charm doesn't pose any problems. Achim Gratz. ###### Message-ID: <3C6A7349.759199BA@andraka.com> From: Ray Andraka Organization: Andraka Consulting Group, Inc X-Mailer: Mozilla 4.77 [en] (WinNT; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: Pseudorandom Bitstream References: <73b09d4c.0202061037.4d30d8a6@posting.google.com> <3C617D80.98BA6DF5@andraka.com> <73b09d4c.0202120305.6cf0ed93@posting.google.com> <1013521410.18149.1.nnrp-07.9e9832fa@news.demon.co.uk> <3C69215D.E69A4215@andraka.com> <73b09d4c.0202121338.1f036669@posting.google.com> <3C69B198.C52EA024@andraka.com> <73b09d4c.0202130218.2ee19f63@posting.google.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 84 Date: Wed, 13 Feb 2002 14:04:29 GMT NNTP-Posting-Host: 68.9.153.21 X-Complaints-To: abuse@cox.net X-Trace: news1.east.cox.net 1013609069 68.9.153.21 (Wed, 13 Feb 2002 09:04:29 EST) NNTP-Posting-Date: Wed, 13 Feb 2002 09:04:29 EST Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!btnet-peer1!btnet!newsfeeds-atl2!newsfeeds-atl1.usenetserver.com!cox.net!news1.east.cox.net.POSTED!53ab2750!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:14206 Achim Gratz wrote: > Ray Andraka wrote in message news:<3C69B198.C52EA024@andraka.com>... > > Like I said, that is the speed of the routing. [...] > > Sure, I took notice (as I said, I will probably interleave two LFSR as > the FF only implementation takes too many CLB). I just did a quick > hack to ascertain that the extra delay was really coming from routing. > Of course I'll need to do this optimization again when I've settled on > an LFSR polynomial (downloaded XAPP052 a few days ago, still waiting > for time to read it). > > > Xilinx: Perhaps a good thing to do would be to add a note in the timing reports when the > > period constraint on a clock that clocks an SRL16 is less than the minimum period dictated > > by the min pulse widths. Same for the minimum and maximum clocks for the clkdlls. > > Several people I am aware of have missed these limitations in recent designs. > > I second that. I would have fallen into that trap and been burned > quite badly. Especially worrysome is that with default settings the > synthesis will automatically infer SRL16 for shift registers that the > user might think should have been instantiated as FF chains. I wonder > if it would be possible to "fix" that by a timing constraint. Is it > possible to put constraints on all instances of some particular > primitive (that is invisible to the original HDL nonetheless) instead > of on specific nets? Problem is the xilinx tools will not change a netlist consisting of only primitives. The fix has to be in the synthesis tool so that it instantiates FF's instead of SRL16s. You can force the issue by putting a reset on your shift register, since the SRL16 has no reset. I think there may be a syn_register_style attribute in some tools that can be used to prevent inference of an SRL16. > > > > Std_logic_unsigned and std_logic_signed were synopsis libraries. They generally cannot > > coexist in the same entity because they have conflicting declarations. Despite the name, > > they are also not standard among different vendors. For the assignments, you can use > > casts for related types. Std_logic_vector, unsigned, and signed are related types so; > > Numeric_std is an IEEE standard library. Us it instead of wrestling with all the problems > > of std_logic_unsigned, std_logic_arith and std_logic_signed. > > > > slv_signal<= std_logic_vector(unsigned_signal); > > unsigned_signal<= unsigned(slv_signal); > > > > Does that answer your question? > > Not fully. I get errors for constructs like: > > unsigned_signal <= 0; -- compiler wants bitstring for > literal > unsigned_signal <= unsigned(0); -- compiler: can not be converted to > unsigned > That is because it is expecting a bit vector. Casting only works for closely relted types. Use the to_unsigned function: unsigned_signal <= (others=>'0'); unsigned_signal<= to_unsigned(10,bits); > > These must have a simple solution, as for instance > > unsigned_signal <= unsigned_signal*0; -- works like a charm > > doesn't pose any problems. > > Achim Gratz. -- --Ray Andraka, P.E. President, the Andraka Consulting Group, Inc. 401/884-7930 Fax 401/884-7950 email ray@andraka.com http://www.andraka.com "They that give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." -Benjamin Franklin, 1759 ###### From: Mike Treseler Newsgroups: comp.arch.fpga Subject: Re: Pseudorandom Bitstream Date: Wed, 13 Feb 2002 09:07:25 -0800 Organization: Fluke Networks Lines: 32 Message-ID: <3C6A9D4D.FF3B4417@flukenetworks.com> References: <73b09d4c.0202061037.4d30d8a6@posting.google.com> <3C617D80.98BA6DF5@andraka.com> <73b09d4c.0202120305.6cf0ed93@posting.google.com> <1013521410.18149.1.nnrp-07.9e9832fa@news.demon.co.uk> <3C69215D.E69A4215@andraka.com> <73b09d4c.0202121338.1f036669@posting.google.com> <3C69B198.C52EA024@andraka.com> <73b09d4c.0202130218.2ee19f63@posting.google.com> NNTP-Posting-Host: slick.tc.fluke.com Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: Mozilla 4.77 [en] (X11; U; Linux 2.4.7-4GB i686) X-Accept-Language: en Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!iad-peer.news.verio.net!news.verio.net!washdc3-snh1.gtei.net!evrtwa1-snf1.gtei.net!news.gtei.net!fluke!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:14223 Achim Gratz wrote: > Not fully. I get errors for constructs like: > > unsigned_signal <= 0; > -- compiler wants bitstring for literal numeric_std only covers numeric operations +,-,abs,< etc. between ints and unsigned vectors. Assignments are not overloaded, so the left and right sides must be the same type. > unsigned_signal <= unsigned(0); > -- compiler: can not be converted to unsigned unsigned cast only works on vectors. numeric_std provides a to_unsigned(length,vec) function for this case. > These must have a simple solution, as for instance > > unsigned_signal <= unsigned_signal*0; > -- works like a charm This works because numeric_std overloads the function "*" to return an unsigned vector. It's not much more work to say: unsigned_signal <= (unsigned_signal'range => '0'); -- works like a charm and intent is clear. -- Mike Treseler ###### From: Stromeko@nexgo.de (Achim Gratz) Newsgroups: comp.arch.fpga Subject: Re: Pseudorandom Bitstream Date: 13 Feb 2002 14:35:04 -0800 Organization: http://groups.google.com/ Lines: 34 Message-ID: <73b09d4c.0202131435.2da02b8d@posting.google.com> References: <73b09d4c.0202061037.4d30d8a6@posting.google.com> <3C617D80.98BA6DF5@andraka.com> <73b09d4c.0202120305.6cf0ed93@posting.google.com> <1013521410.18149.1.nnrp-07.9e9832fa@news.demon.co.uk> <3C69215D.E69A4215@andraka.com> <73b09d4c.0202121338.1f036669@posting.google.com> <3C69B198.C52EA024@andraka.com> <73b09d4c.0202130218.2ee19f63@posting.google.com> <3C6A7349.759199BA@andraka.com> NNTP-Posting-Host: 212.144.48.27 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: posting.google.com 1013639704 24423 127.0.0.1 (13 Feb 2002 22:35:04 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: 13 Feb 2002 22:35:04 GMT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!fr.usenet-edu.net!usenet-edu.net!freenix!sn-xit-01!sn-xit-02!supernews.com!postnews1.google.com!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:14319 Ray Andraka wrote > Problem is the xilinx tools will not change a netlist consisting of only primitives. The fix > has to be in the synthesis tool so that it instantiates FF's instead of SRL16s. You can force > the issue by putting a reset on your shift register, since the SRL16 has no reset. I think > there may be a syn_register_style attribute in some tools that can be used to prevent inference > of an SRL16. There is a global switch that prevents SRL16's to be inferred. That fixes the problem of the wrong timing report and creates a new one, CLB usage. I'll try the attribute route later, but the same goes for that. As for fixing the problem with at the source with a proper timing constraint on WE of the SRL: I can see the net for each SRL16 WE in the floorplanner, but I can't get at it in the Timing Analyzer nor the Constraints editor. The files that may contain the timing information are binary. :-( > That is because it is expecting a bit vector. Casting only works for closely related types. > Use the to_unsigned function: > > unsigned_signal <= (others=>'0'); > unsigned_signal<= to_unsigned(10,bits); Many thanks. All things I tried and that one didn't come to my mind ... Mike Treseler wrote in message > It's not much more work to say: > unsigned_signal <= (unsigned_signal'range => '0'); > -- works like a charm and intent is clear. Thanks to you, too. I knew the multiplication was a hack, but I'm still trying to wrap my head around VHDL ... Achim Gratz. ###### From: Stromeko@nexgo.de (Achim Gratz) Newsgroups: comp.arch.fpga Subject: Re: Pseudorandom Bitstream Date: 18 Feb 2002 05:08:46 -0800 Organization: http://groups.google.com/ Lines: 41 Message-ID: <73b09d4c.0202180508.67262c1a@posting.google.com> References: <73b09d4c.0202061037.4d30d8a6@posting.google.com> <3C617D80.98BA6DF5@andraka.com> <73b09d4c.0202070337.58808aaf@posting.google.com> <3C6281B9.4EB0B636@comsys.ntu-kpi.kiev.ua> <3C62A21F.C8BFFA23@andraka.com> <48d2564d.0202071300.367a69aa@posting.google.com> <3C630AD6.7FD04150@andraka.com> <73b09d4c.0202080804.4f7a69a0@posting.google.com> NNTP-Posting-Host: 192.35.17.233 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: posting.google.com 1014037727 9778 127.0.0.1 (18 Feb 2002 13:08:47 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: 18 Feb 2002 13:08:47 GMT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!newsfeed.wirehub.nl!btnet-peer!btnet!feeder.qis.net!sn-xit-02!supernews.com!postnews1.google.com!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:14384 Stromeko@nexgo.de (Achim Gratz) wrote in message news:<73b09d4c.0202080804.4f7a69a0@posting.google.com>... > [...] As an addition to the earlier summary for those interested: As it turned out that you need to have a uniformly distributed stream of integer numbers, I conducted another search in that direction. Generally you'll get lots of hits on (software) implementations for general computers and the tricks required to produce floating point numbers out of integers and vice versa plus appplications to cryptography and/or Monte Carlo simulation. Some of the successful search terms: PRNG QRNG RNG LFSR GFSR Tausworthe (PRBS parallel) A site with lots of useful references: http://www.ciphersbyritter.com In there it is briefly mentioned that you should collect the bits for your output from equally distributed places in the sequence, which seems to relate to Ray Andrakas remark that one could use several LFSR seeded at different places to get a multibit output. I have not found an efficient way to compute the required seed values for really long sequences, however. Notes: I found a hint in an earlier article in this group on how to efficiently describe an "unrolled" LFSR that behaves like it is clocked n times per tick. It involves writing up the original state machine inside a for...loop in VHDL and collecting the outputs and the new shift bits in the appropriate registers. If anybody is interested I can post the code. There is also an easy way to prevent the synthesis from infering SRL16 on Xilinx if you desire: Ray Andraka mentioned that a RESET will do the trick, you can also copy the LFSR state to a variable, change that and assign the changed state back to the LFSR registers. Look Ma, everything done with FF now ... Achim. ###### From: Lasse Langwadt Christensen Newsgroups: comp.arch.fpga Subject: Re: Pseudorandom Bitstream Date: Mon, 18 Feb 2002 22:10:52 +0100 Organization: Cybercity Lines: 136 Message-ID: <3C716DDC.836D571@ieee.org> References: <73b09d4c.0202061037.4d30d8a6@posting.google.com> <3C617D80.98BA6DF5@andraka.com> <73b09d4c.0202070337.58808aaf@posting.google.com> <3C6281B9.4EB0B636@comsys.ntu-kpi.kiev.ua> <3C62A21F.C8BFFA23@andraka.com> <48d2564d.0202071300.367a69aa@posting.google.com> <3C630AD6.7FD04150@andraka.com> NNTP-Posting-Host: port15.cvx1-abc.ppp.cybercity.dk Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Trace: news.cybercity.dk 1014066405 67638 217.157.84.16 (18 Feb 2002 21:06:45 GMT) X-Complaints-To: abuse@cybercity.dk NNTP-Posting-Date: Mon, 18 Feb 2002 21:06:45 +0000 (UTC) X-Mailer: Mozilla 4.5 [en] (Win98; I) X-Accept-Language: en Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news-out.spamkiller.net!propagator-maxim!news-in.spamkiller.net!feed.newsfeeds.com!news-hog.berkeley.edu!ucberkeley!news.maxwell.syr.edu!newsfeed1.uni2.dk!news.cybercity.dk!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:14390 Ray Andraka wrote: > > Exactly. In fact, all the LFSR is is a special case of the CRC hardware. I did't want to > confuse the issue, but as you say, you can create a parallel version of the LFST that appears at > the outputs to advance N clocks in a single clock. > I'm wondering if it in a VirtexII would makes sense to use a multiplier, AFIAR a normal way to generate random numbers in SW is something like x[n+1] = (x[n]*a + b) % c -Lasse > jrc wrote: > > > It is pretty easy to contruct a state-machine to mimic the effects of > > a LFSR shift register that has been clocked an arbitrary number of > > times. To use your example the normal logic for X^3+X^2+1 using four > > flip-flops is: > > > > ff0=ff3^ff2^1 (xnor the last two flip-flops in the shift register) > > ff1=ff0 (shift) > > ff2=ff1 (shift) > > ff3=ff2 (shift) > > > > For each clock, the following design will produce the same four bit > > sequence produced by clocking the orignal design four times: > > > > ff0=ff3^ff2^ff0 (three term xor) > > ff1=ff1^ff0^1 (xnor) > > ff2=ff2^ff1^1 (xnor) > > ff3=ff3^ff2^1 (xnor) > > > > So the bit sequence for ff0 the upper design is: > > > > 0111011001010000111... > > > > The bit sequence for the four flip-flops on second design is: > > > > 3210 > > ---- > > 0111 > > 0110 > > 0101 > > 0000 > > 1110 > > ... > > > > I always called this generating pseudorandom in parallel. It is used a > > lot in communications work. Once you get the knack you can generate > > any sequence in any width. If you add flip-flops you can actually > > generate this sequence 8 bits at a time or even wider. > > > > JRC > > > > Ray Andraka wrote in message news:<3C62A21F.C8BFFA23@andraka.com>... > > > No. The neighboring bits, when taken a byte at a time from an LFSR are time shifted copies > > > of previous bits. If you take more than 1 bit per clock from an LFSR, you lose the uniform > > > white properties. Consider the 4 bit LFSR X^3+X^2+1: > > > > > > 0000 > > > 0001 > > > 0011 > > > 0111 > > > 1110 > > > 1101 > > > 1011 > > > 0110 > > > 1100 > > > 1001 > > > 0010 > > > 0101 > > > 1010 > > > 0100 > > > 1000 > > > 0000 > > > > > > Note that only the right most bit is random, the other bits are the same as the rightmost > > > but delayed by 1,2 and 3 clocks. If you use more than one bit per clock from an LFSR, you > > > wind up with a correlation that colors the output and destroys the uniform random > > > properties. The bottom line is that an LFSR at 100MHz produces a random BIT stream at 100 > > > MHz, not a byte stream. To get a random byte stream, you need to clock the LFSR 8 times > > > between samples so as to get new bit values (uncorrelated to any bits in previous sample) > > > in all 8 bits, which gives you a random byte stream of 100/8= 12.5 MHz. > > > > > > vt313@comsys.ntu-kpi.kiev.ua wrote: > > > > > > > In the LSFR bitstream the bytes of neighboring bits, > > > > considered as signed vectors, are practically > > > > uncorrelated, and belong to the interval (-1.0 : 1.0). > > > > Therefore LSFR generator at 100 MHz > > > > provides the byte stream at 100 MHz. > > > > > > > > If you add couples of neigboring > > > > sampling bytes from LSFR, > > > > then you get the approximation > > > > of the "triangle" distribution. > > > > > > > > If you want the Gaussian distribution, > > > > then you would add n>10 neigboring > > > > sampling bytes from LSFR, > > > > and get the rather exact approximation > > > > of the Gaussian distribution. > > > > > > > > Anatoli S. > > > > > > -- > > > --Ray Andraka, P.E. > > > President, the Andraka Consulting Group, Inc. > > > 401/884-7930 Fax 401/884-7950 > > > email ray@andraka.com > > > http://www.andraka.com > > > > > > "They that give up essential liberty to obtain a little > > > temporary safety deserve neither liberty nor safety." > > > -Benjamin Franklin, 1759 > > -- > --Ray Andraka, P.E. > President, the Andraka Consulting Group, Inc. > 401/884-7930 Fax 401/884-7950 > email ray@andraka.com > http://www.andraka.com > > "They that give up essential liberty to obtain a little > temporary safety deserve neither liberty nor safety." > -Benjamin Franklin, 1759 -- ---------------------------- - Lasse Langwadt Christensen - Aalborg - Danmark ###### Message-ID: <3C73DA54.31FE206F@andraka.com> From: Ray Andraka Organization: Andraka Consulting Group, Inc X-Mailer: Mozilla 4.77 [en] (WinNT; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.arch.fpga Subject: Re: Pseudorandom Bitstream References: <73b09d4c.0202061037.4d30d8a6@posting.google.com> <3C617D80.98BA6DF5@andraka.com> <73b09d4c.0202070337.58808aaf@posting.google.com> <3C6281B9.4EB0B636@comsys.ntu-kpi.kiev.ua> <3C62A21F.C8BFFA23@andraka.com> <48d2564d.0202071300.367a69aa@posting.google.com> <3C630AD6.7FD04150@andraka.com> <3C716DDC.836D571@ieee.org> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 152 Date: Wed, 20 Feb 2002 17:13:57 GMT NNTP-Posting-Host: 68.14.84.212 X-Complaints-To: abuse@cox.net X-Trace: news2.east.cox.net 1014225237 68.14.84.212 (Wed, 20 Feb 2002 12:13:57 EST) NNTP-Posting-Date: Wed, 20 Feb 2002 12:13:57 EST Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.mailgate.org!out.nntp.be!propagator-SanJose!in.nntp.be!nntp-relay.ihug.net!ihug.co.nz!hub1.nntpserver.com!peer1-sjc1.usenetserver.com!usenetserver.com!newsfeeds-atl1.usenetserver.com!cox.net!news2.east.cox.net.POSTED!53ab2750!not-for-mail Xref: chonsp.franklin.ch comp.arch.fpga:14439 Depends if a) the multiplier is fast enough (it is quite a bit slower than what you can do in the fabric), and b) if you need the multiplier for something else that might be harder to do than random number generates. It is a game of resource allocation to get the most efficient overall design. Lasse Langwadt Christensen wrote: > Ray Andraka wrote: > > > > Exactly. In fact, all the LFSR is is a special case of the CRC hardware. I did't want to > > confuse the issue, but as you say, you can create a parallel version of the LFST that appears at > > the outputs to advance N clocks in a single clock. > > > > I'm wondering if it in a VirtexII would makes sense to use a multiplier, > AFIAR a > normal way to generate random numbers in SW is something like x[n+1] = > (x[n]*a + b) % c > > -Lasse > > > jrc wrote: > > > > > It is pretty easy to contruct a state-machine to mimic the effects of > > > a LFSR shift register that has been clocked an arbitrary number of > > > times. To use your example the normal logic for X^3+X^2+1 using four > > > flip-flops is: > > > > > > ff0=ff3^ff2^1 (xnor the last two flip-flops in the shift register) > > > ff1=ff0 (shift) > > > ff2=ff1 (shift) > > > ff3=ff2 (shift) > > > > > > For each clock, the following design will produce the same four bit > > > sequence produced by clocking the orignal design four times: > > > > > > ff0=ff3^ff2^ff0 (three term xor) > > > ff1=ff1^ff0^1 (xnor) > > > ff2=ff2^ff1^1 (xnor) > > > ff3=ff3^ff2^1 (xnor) > > > > > > So the bit sequence for ff0 the upper design is: > > > > > > 0111011001010000111... > > > > > > The bit sequence for the four flip-flops on second design is: > > > > > > 3210 > > > ---- > > > 0111 > > > 0110 > > > 0101 > > > 0000 > > > 1110 > > > ... > > > > > > I always called this generating pseudorandom in parallel. It is used a > > > lot in communications work. Once you get the knack you can generate > > > any sequence in any width. If you add flip-flops you can actually > > > generate this sequence 8 bits at a time or even wider. > > > > > > JRC > > > > > > Ray Andraka wrote in message news:<3C62A21F.C8BFFA23@andraka.com>... > > > > No. The neighboring bits, when taken a byte at a time from an LFSR are time shifted copies > > > > of previous bits. If you take more than 1 bit per clock from an LFSR, you lose the uniform > > > > white properties. Consider the 4 bit LFSR X^3+X^2+1: > > > > > > > > 0000 > > > > 0001 > > > > 0011 > > > > 0111 > > > > 1110 > > > > 1101 > > > > 1011 > > > > 0110 > > > > 1100 > > > > 1001 > > > > 0010 > > > > 0101 > > > > 1010 > > > > 0100 > > > > 1000 > > > > 0000 > > > > > > > > Note that only the right most bit is random, the other bits are the same as the rightmost > > > > but delayed by 1,2 and 3 clocks. If you use more than one bit per clock from an LFSR, you > > > > wind up with a correlation that colors the output and destroys the uniform random > > > > properties. The bottom line is that an LFSR at 100MHz produces a random BIT stream at 100 > > > > MHz, not a byte stream. To get a random byte stream, you need to clock the LFSR 8 times > > > > between samples so as to get new bit values (uncorrelated to any bits in previous sample) > > > > in all 8 bits, which gives you a random byte stream of 100/8= 12.5 MHz. > > > > > > > > vt313@comsys.ntu-kpi.kiev.ua wrote: > > > > > > > > > In the LSFR bitstream the bytes of neighboring bits, > > > > > considered as signed vectors, are practically > > > > > uncorrelated, and belong to the interval (-1.0 : 1.0). > > > > > Therefore LSFR generator at 100 MHz > > > > > provides the byte stream at 100 MHz. > > > > > > > > > > If you add couples of neigboring > > > > > sampling bytes from LSFR, > > > > > then you get the approximation > > > > > of the "triangle" distribution. > > > > > > > > > > If you want the Gaussian distribution, > > > > > then you would add n>10 neigboring > > > > > sampling bytes from LSFR, > > > > > and get the rather exact approximation > > > > > of the Gaussian distribution. > > > > > > > > > > Anatoli S. > > > > > > > > -- > > > > --Ray Andraka, P.E. > > > > President, the Andraka Consulting Group, Inc. > > > > 401/884-7930 Fax 401/884-7950 > > > > email ray@andraka.com > > > > http://www.andraka.com > > > > > > > > "They that give up essential liberty to obtain a little > > > > temporary safety deserve neither liberty nor safety." > > > > -Benjamin Franklin, 1759 > > > > -- > > --Ray Andraka, P.E. > > President, the Andraka Consulting Group, Inc. > > 401/884-7930 Fax 401/884-7950 > > email ray@andraka.com > > http://www.andraka.com > > > > "They that give up essential liberty to obtain a little > > temporary safety deserve neither liberty nor safety." > > -Benjamin Franklin, 1759 > > -- > ---------------------------- > - Lasse Langwadt Christensen > - Aalborg - Danmark -- --Ray Andraka, P.E. President, the Andraka Consulting Group, Inc. 401/884-7930 Fax 401/884-7950 email ray@andraka.com http://www.andraka.com "They that give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." -Benjamin Franklin, 1759