Custom Search
Site Home Archive Home FAQ Home How to search the Archive How to Navigate the Archive
Compare FPGA features and resources
Threads starting:
Authors:A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
James Yeh wrote in message <379F799D.4E2BD760@uclink4.berkeley.edu>... > > >If you think you can simulate the BRAM, >Well to quote a Judas Priest song, "You gotta another thing comin." > Clarify please. Why can't I simulate? Paul Butler Paul.Butler@natinst.com National Instruments Austin, TXArticle: 17476
> Mark Grindell wrote: > > It is possible to create cross-coupled structures in which two or more logic > > cells act as an oscillator. If the feedback path is fairly complex, > > distributed over several paths in the chip, the operating frequency might be > > quite a sensitive function of the operating temperature and the chip > > manufacturing batch number, and so on. Two such oscillators set up in > > different regions of the chip might be arranged to together create a more > > complex periodic signal which could be further processed. There are several problems with this... The main problem is that an oscillator made like what you're describing (essentially an inverting buffer where the output is fed back to the input) is very noise sensitive. That is, noise on the power rails and elsewhere will have a very strong impact on the frequency of the output. To further complicate things, this type of oscillator will tend to put a lot of noise on the power rails and elsewhere. The net effect of this is that if you put two oscillators like this into the same FPGA then they will tend to phase/frequency-lock to each other. Of course, their proximity to each other and other things in the FPGA will make this locking attribute more or less strong, but it is something to consider. This is made worse when there is more things inside the FPGA. For instance, if there is a lot of logic in the FPGA then the frequency of the oscillator will be effected by that logic. In some cases, the osc frequency will lock to multiples of the "master clock", in other cases it will just speed up and slow down depending on what's going on inside the FPGA. What this means is that using this type of oscillator isn't a good source of random numbers since those numbers are going to be directly correlated to things going on inside the FPGA. To date, I have not found a good random number generator for FPGA design, or hardware implementation in general. LFSR's are OK, but not great. Integer multiply based ones take too much logic. And using a noisy diode/transistor doesn't produce numbers fast enough. Oh well... David Kessner davidk@free-ip.com http://www.free-ip.comArticle: 17477
Rickman <spamgoeshere4@yahoo.com> wrote: >Mark Grindell wrote: >> However, in some cases, it might be desirable to have non-deterministic >> behavior. One application for this might be the creation of random keys in >> an encryption circuit. ..... >> I would expect at least some comments as to this kind of design strategy >> being quite improper, and random number generation being advisable on the >> basis of algorithmic design. I'm not sure either way. >I don't know that it would be improper to use hardware to generate >random numbers, but it is very difficult. When you need random numbers, >you need them to have certain properties such as being without bias. In >practice it is very difficult to build a true random number generator >which will not introduce a bias of some sort. I have known of several >attempts that did not work correctly because of this. One was based on a >diode generating thermal noise which was amplified and then converted to >Digital to produce a number. They found that the result was slightly >more likely to produce positive numbers vs. negative numbers. Every >other attempt I have heard of had similar problems. This problem varies with the application. If you want to simulate some physical thing that you think fits a particular random distribution, it usually turns out that the parameters have to be estimated using measured random data, and beyond a certain point when you remove bias etc you are only more closely modeling the noise in the original data. The advantage of a pseudo-random algorithm is that you can predict its properties over the whole range. With a true random number generator you have to collect data to decide whether it's biased, and you can never be quite sure -- if you reach the point that you're 99.9% confident there is a bias, that's still one chance in a thousand that you just got a bad run. You could censor the output to remove the bias, to the degree that you're confident you know how much bias is there.... On the other hand I once watched a group of CS students run tests on an RNG to get "good" versus "bad" seeds. They wanted to make sure that every single run would have the right mean and variance, which of course doesn't fit reality at all. If you want random keys for encryption, a small variation from uniform might be OK. The worse it is, the more likely that someone who knew about it could use it to get a better chance to decrypt. I think the concerns would be larger for an FPGA that would get into the physical hands of people who want to decrypt it. If they could heat it or cool it until the key was mostly ones or zeroes, that would be a bad thing.Article: 17478
I've been able to simulate reads and writes to block RAM at both the RTL and gate level. I've also been able to verify power default value of data in the block RAMs using gate level simulation. Mike Paul Butler wrote: > James Yeh wrote in message <379F799D.4E2BD760@uclink4.berkeley.edu>... > > > > > >If you think you can simulate the BRAM, > >Well to quote a Judas Priest song, "You gotta another thing comin." > > > > Clarify please. Why can't I simulate? > > Paul Butler > > Paul.Butler@natinst.com > National Instruments > Austin, TXArticle: 17479
Rickman (spamgoeshere4@yahoo.com) wrote:
: >
: > However, in some cases, it might be desirable to have non-deterministic
: > behavior. One application for this might be the creation of random keys
: I don't know that it would be improper to use hardware to generate
: random numbers, but it is very difficult. When you need random numbers,
: you need them to have certain properties such as being without bias. In
: practice it is very difficult to build a true random number generator
: which will not introduce a bias of some sort. I have known of several
: attempts that did not work correctly because of this. One was based on a
: diode generating thermal noise which was amplified and then converted to
: Digital to produce a number. They found that the result was slightly
: more likely to produce positive numbers vs. negative numbers. Every
: other attempt I have heard of had similar problems.
It's trivial to take a random and uncorrelated, but lopsided probability
distribution, entropy source and make a true 50-50 random bit.
Consider a coin toss where heads and tails are not known to occur
equally. Toss it twice.
Heads-Heads --> Retry
Heads-Tails --> logic 1 output
Tails-Heads --> logic 0 output
Tails-Tails --> Retry
(No, I don't take credit for this algorithm. It's very old.)
This throws out a lot of data (entropy), in many cases you simply
feed the data stream into a cryptographically secure pseudo random
sequencer, and only take out bits at the rate you think entropy
is going in. The Linux kernel has a good example implementation.
The best source of random bits comes from techniques like this
_with_hardware_support_. In particular people like the output of
a Geiger counter next to a radioisotope source, because nobody
knows how to hack the decay rate of nuclei, so the events are
provably uncorrelated.
: I believe I read where Intel was going to add such a feature to one of
: their CPUs due out soon (or was it the PIII which is out now?) Anyone
: heard of this?
The Pentium III has this. I'm not convinced you should trust it,
but it can't hurt to add its entropy to that derived from other
sources.
- Larry Doolittle <LRDoolittle@lbl.gov>
Article: 17480Does anybod have any idea of how to enable the numeric_std library in Foundation 1.5??? I've dried the download from xilinx giving me the numeric_std.vhd file but when I try to add it to the project library it gives me a ton of errors. Any help would be appreciated. Thanks in advance. Bret Eddinger eddinger_bret@bah.comArticle: 17481
>I've added 'Marble' to my list of SoC buses at >http://www.silicore.net/uCbusum.htm under 'known, but not found'. Maybe >somebody else has some information about this one. See http://www.cs.man.ac.uk/amulet/index.html Hans.Article: 17482
Hans <nospam_ees1ht@ee.surrey.ac.uk> wrote in message news:7nspcd$ab1$1@info-server.surrey.ac.uk... > > >I've added 'Marble' to my list of SoC buses at > >http://www.silicore.net/uCbusum.htm under 'known, but not found'. Maybe > >somebody else has some information about this one. > > See http://www.cs.man.ac.uk/amulet/index.html > > Hans. > Thanks! Got it. WadeArticle: 17483
Greetings This is semimonthly announcement of Verilog FAQ. Verilog FAQ is located at http://www.angelfire.com/in/verilogfaq/ Alternate Verilog FAQ is an attempt to gather the answers to most Frequently Asked Questions about Verilog HDL in one place. It also contains list of publications, services, and products. Alternate Verilog FAQ is divided into three logical parts. Part 1 : Introduction and misc. questions Part 2 : Technical Topics Part 3 : Tools and Services What's New section outlines the changes in different versions and announcements. Links connects you to related informative links in internet. Your suggestions to make this FAQ more informative are welcome. Rajesh Bawankule (Also Visit Verilog & EDA Page : http://www.angelfire.com/in/rajesh52/verilog.html ) Sent via Deja.com http://www.deja.com/ Share what you know. Learn what you don't.Article: 17484
> To date, I have not found a good random number generator for FPGA design, > or hardware implementation in general. LFSR's are OK, but not great. > Integer multiply based ones take too much logic. And using a noisy > diode/transistor > doesn't produce numbers fast enough. Oh well... I think it's important to split random number usage into two categories: cryptographic and everything else. Crypto is a special game. You have to worry about the bad guys being able to predict your output (say, by finding the state of a LFSR) and/or smashing the state of your logic so it will make predictable patterns. What's "OK, but not great" about LFSRs? They are real easy to implement, run as fast as you want (put them in parallel if you need more bits) and have very well understood mathematical patterns. I'm pretty sure that diode type noise is very broad spectrum. You can get as many bits as you want. (I think radar guys use this.) Most computer type noise diodes do run at a low bit rate. That's because they are used for crypto applications where you only need a few bits occasionally to setup the session key. -- These are my opinions, not necessarily my employers.Article: 17485
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
Good news, fpga_editor in Xilinx 2.1 runs under wine. I will be trying
out the full suite of Xilinx tools in the next few days.
<p>I've got a Win98 installation of Xilinx 2.1. I'm running RedHat 6.0
on a Pentium II, Wine release 990704.
<p> setenv XILINX
/win98/Xilinx
<br> setenv XKEYSYMDB ${XILINX}/data/XKeysymDB
<br> set path = (${XILINX}/bin/nt $path )
<br> set path = (${XILINX}/wine $path )
<p>Where the wine directory contains a script per program of the form
<br>wine program_name.exe
<br>
<p>Josh</html>
Article: 17486Bret Eddinger wrote in message <37A1E7B1.555DC755@bah.com>... >Does anybod have any idea of how to enable the numeric_std library in >Foundation 1.5??? I've dried the download from xilinx giving me the >numeric_std.vhd file but when I try to add it to the project library it >gives me a ton of errors. Any help would be appreciated. Thanks in >advance. There's a Xilinx Answer about this at: http://www.xilinx.com/techdocs/5432.htm The problem is that it's not yet built into FPGA Express; you have to add it as a user library. So, instead of: library ieee; use ieee.numeric_std.all; you have to create a new library and compile numeric_std into the new library. As the Xilinx note indicates, you'll have to include the library like this: library myieee; use myieee.numeric_std.all; The note says to ignore warnings about assert and initial values. It's obvious what problems you'll have when trying to simulate. You have to create a simulation library called myieee and compile numeric_std in that too. Supposedly they're going to put numeric_std in the ieee library (where it belongs) whenever Foundation 2.1 comes out. Might as well wait. We've waited *this* long already. -- ---------------------------------------------------------------------------- -- Andy Peters Sr Electrical Engineer National Optical Astronomy Observatories apeters (at) noao.edu "I'm not judging you, I'm judging me." -- Mission of Burma, "Academy Fight Song"Article: 17487
If your entry is HDL, then there is no problem. If you are using schematic entry, there was no sim models under the block ram, the CLB shift register macros and a few other things which made simulation of schematic designs in virtex painful (you could sim using the vhdl output from the PAR tool). I'm not sure it got fixed in 2.1, as I haven't had a chance to look yet. Lewis, Mike wrote: > I've been able to simulate reads and writes to block RAM at both > the RTL and gate level. I've also been able to verify power default > value of data in the block RAMs using gate level simulation. > > Mike > > Paul Butler wrote: > > > James Yeh wrote in message <379F799D.4E2BD760@uclink4.berkeley.edu>... > > > > > > > > >If you think you can simulate the BRAM, > > >Well to quote a Judas Priest song, "You gotta another thing comin." > > > > > > > Clarify please. Why can't I simulate? > > > > Paul Butler > > > > Paul.Butler@natinst.com > > National Instruments > > Austin, TX -- -Ray Andraka, P.E. President, the Andraka Consulting Group, Inc. 401/884-7930 Fax 401/884-7950 email randraka@ids.net http://users.ids.net/~randrakaArticle: 17488
Luis Yanes wrote: > On Wed, 28 Jul 1999 18:00:14 -0400 Ray Andraka <randraka@ids.net> > wrote: > > >At your low data rate, you could use an iterative serial CORDIC to do the > >modulation. In my CORDIC survey paper, (available on my website) I show an > >example of a bit serial iterative CORDIC that fits in 22 CLBs in a xilinx 4K or > >spartan device. That one will handle bit rates over 100 Mb/sec in current > >devices, so the possible data rates are much higher than your 8Ks/s needs. It > >doesn't map as nicely into the 5200 series because it uses the CLB RAM for the > >shift registers. Still, I think an iterative approach may fit into the 5202. > > I supouse that I was wrong, but these 100M/s are at the carrier > frequency with the modulation. My 8K/s are the baseband modulation > signal over a carrier that I like to have better arround 5-6MHz. > Anyway low enought, I hope. > The 100Mb/sec is the bit rate. The sample rate is the bit rate divided by the number of bits times the number of iterations. The limiting factor for the bit rate is the CLB RAM cycle time. I know the design can be clocked at 96 MHz in a 40xxE-2 (that's the chip it was done in). You should do a bit better in spartan, and quite a bit better in spartan XL. That'll get you data sample rates around a megahertz. If your sample rate is 8Ks/s, then there's plenty of margin. If it is 5-6 MHz, you probably won't make it, so you'll have to go to either a bit serial unrolled pipeline (see the paper on high performance bit serial design techniques for an example of a bit serial CORDIC processor in atmel 6K), or to a bit parallel iterative design. The unrolled bit serial design needs lots of registers for the inter-stage delays, while the bit parallel design needs a carry chain and more complicated control. The bit parallel iterative design may still fit in the 5202, but you will probably need a shoehorn to get it in. > >If you use the CORDIC approach, you don't need a multiplier! The rotation mode > >CORDIC takes an input vector and rotates it by a phase angle (also an input). If > >you feed the I component of the CORDIC input with your signal and the component > >with zero, then rotation by a moving phase angle will modulate the input signal. > > Ok, right. I didn't read all last time. Its a very clever algorithm, > with amazing posibilities with very small modifications! With it I got > the sine, cosine and multiplication in a single block!. And guess that > for sin/cos the algorithm are unconditionally convergent, not like for > the hyperbolic functions. > That's right. Few people realize that multiplication by a complex exponential is just a phase rotation, and is can therefore be done using CORDIC with better than a 4:1 reduction of logic. The circular system CORDIC does converge, so double rotations are not necessary. > Now I'm learning about CORDIC. (Got your paper and some worked example > from http://devil.ece.utexas.edu/tutorial/index.html , althought seems > very oversimplified, examples to do by hand always help to understand > how it works). > If you have microsoft excel or some other spread sheet, you can set it up very quickly to do CORDIC iterations. Set up a row with the initial F,G and P values, then on each row below set up an equation using the row number for the amount of shift, and the previous row F,G and P values. Works really nice both for demos and for verifying hardware/ > >One more thing, check to make sure you can compile the 5200 series with F1.3. > >I'm not sure the 5200 series is supported under M1. You may have to use the old > >xact6 software to use it. You should be able to get the spartan parts in small > >quantities from a reseller such as hamilton avnet. Try http://www.avnet.com . > >The foundation tools are upto 1.5i. You should be able to download updates from > >the web (although I'm not sure you can with the student edition). Xilinx has > >just released 2.1 which has added capabilities and improved PAR. > > No, F1.3 doesn't support XC5200 series, that is becouse I used the > F1.4 from the school. My Foundation package aren't the student > edition, but the Foundation Base (without vhdl :-( ) that costed me > about US$ 150. > I don't think 1.4 or 1.5 support the 5200 either. You need to be under maintenance to get the next version up. You really should consider upgrading, as there are numerous bugs (did I say that? I meant "features") in 1.3 and 1.4. I just got the alliance 2.1 tools, so the foundation 2.1 is probably also either shipping or will be soon. > I searched the Xilinx site for updates, but I couldn't find any, only > patches and speed files, but none that will upgrade to F1.4 or up. > Asked the local distribuitor here, where I bought the package, told me > that I must buy another full package, the same I own but newer version > of software! Can you get under maintenence, it might be cheaper than starting new. -- -Ray Andraka, P.E. President, the Andraka Consulting Group, Inc. 401/884-7930 Fax 401/884-7950 email randraka@ids.net http://users.ids.net/~randrakaArticle: 17489
On Fri, 30 Jul 1999 10:07:47 +0100, "Mark Grindell" <petejackson7@hotmail.com> wrote: [snip] >The other scenario is where the behavior of an individual flip flop, close >to its metastable state is exploited. In this way, some sort of pseudo >random output might be achievable. I am not so sure about this method, as >without fairly precise timing analysis, it might be quite hard to operate >the flip flop in the precise region of operation neccesary. The phase detector design I posted to the "NRZ Deserializing in Virtex" thread a few days ago uses feedback to keep one of the flip flops (the second one) in this region. It needs a VCO though, and this will make the output bits (if used as a random number generator) sensitive to power supply noise. The loop filter parameters will influence the autocorrelation of the bits, too. The mean will be forced to a fixed value (= 1/2) up to some bandwidth. Regards, Allan.Article: 17490
Rickman wrote: > snip > > I don't know that it would be improper to use hardware to generate > random numbers, but it is very difficult. When you need random numbers, > you need them to have certain properties such as being without bias. In > practice it is very difficult to build a true random number generator > which will not introduce a bias of some sort. I have known of several > attempts that did not work correctly because of this. One was based on a > diode generating thermal noise which was amplified and then converted to > Digital to produce a number. They found that the result was slightly > more likely to produce positive numbers vs. negative numbers. Every > other attempt I have heard of had similar problems. you could use two diodes and subtract the noise from each of them > > snip --Lasse +------------------------------------+ |Lasse Langwadt Christensen, M.Sc.DSP| | http://langwadt.homepage.dk | +------------------------------------+Article: 17491
This is a multi-part message in MIME format. --------------A3CE376442F2F36717B3A95A Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Hal Murray wrote: > What's "OK, but not great" about LFSRs? They are real easy > to implement, run as fast as you want (put them in parallel > if you need more bits) and have very well understood mathematical > patterns. > > There are knwon deficiencies of LFSR when used to generate anything but a bit sequence. That is if you pack the bits in numbers, then the autocorrelation properties of the numbers are NOT the flat autocorelation of the but sequence. This is already discussed in Knuth e.g. with the remark that LFSR using polynomial of low weigth are worse. --------------A3CE376442F2F36717B3A95A Content-Type: text/x-vcard; charset=us-ascii; name="vcard.vcf" Content-Transfer-Encoding: 7bit Content-Description: Card for Marc Delvaux Content-Disposition: attachment; filename="vcard.vcf" begin: vcard fn: Marc Delvaux n: Delvaux;Marc org: GlobeSpan Semiconductors adr: 100 Schulz Drive;;;Red Bank;NJ;07701;USA email;internet: mdel@globespan.net title: LSI designer tel;work: +1 (732) 345 7502 tel;fax: +1 (732) 345 7592 tel;home: +1 (732) 578 9255 x-mozilla-cpt: ;0 x-mozilla-html: TRUE version: 2.1 end: vcard --------------A3CE376442F2F36717B3A95A--Article: 17492
This message is to tell you briefly about our new and
exciting company! Aesthetic Software is a group of
highly-trained software development professionals who
specialize in Java and XML. Our company is founded on
the vision that Java and XML are the future technologies
of e-commerce and web-applications. Our dual focus embraces
the development of customized solutions that take advantage
of a variety of new tools that that we have developed. By
leveraging these innovative tools and superior technologies,
we provide our customers a significant advantage over their
competitors. Please visit our web site at the following link:
http://aesthsoft.com/
Or contact us at:
E-mail: solutions@aesthsoft.com
Voice mail: 1-888-835-3268 extension 6488
Fax: 1-408-293-2266 extension 6488#
Postal mail:
Aesthetic Software
P.O. Box 108
Oak Park, IL 60303-0108
U.S.A.
Thank you!
Aesthetic Software
Article: 17493If you are using an LFSR as a random number generator, you should only take one bit per clock cycle, as the other bits are just time shifted copies of the first bit. If you insist on taking more than one bit, the newest bit should be at the MSB position to provide the least effect of the previous bits. Be warned that you end up with marked spectral coloring (the time shifted bits essentially comprise a comb filter). For a one bit random variable, the LFSR does a good job as long as the sequence is long enough that it doesn't repeat within your experiment. There is a slight bias toward a zero bit, which for long LFSRs is negligable (the ratio of one bits to zero bits is 2^(n-1)-1 : 2^(n-1). A 129 bit LFSR only takes a few CLBs in xilinx 4K or virtex FPGAs, and it won't repeat for several thousand years at 40 MHz. 129 bits works nicely for the feedback taps. If you need more than one bit, then either clock the LFSR n times per sample or use n LFSRs in parallel with different seeds. For one bit outputs, the sequence is a remarkably good uniform random variable. Using an LFSR also has the advantage in debug of being able to repeat a sequence by reloading it with the same seed. You can use a binary search of a cumulative density function of a desired distribution to convert the uniform LFSR to an arbitrary distribution. I've done that in hardware to get a Rayliegh distribution at an 11 MHz sample rate. You can also sum bits from a bunch of LFSR samples to get an approximation of a gaussian distribution using the central limit theorem. I've also done that by summing 128 LFSR samples to get a 40MHz complex gaussian distribution. The probability tails will determine how far you have to go. There is a little bit of discussion on these in the radar simulator paper (MAPLD '98) on my website. Marc Delvaux wrote: > Hal Murray wrote: > > > What's "OK, but not great" about LFSRs? They are real easy > > to implement, run as fast as you want (put them in parallel > > if you need more bits) and have very well understood mathematical > > patterns. > > > > > > There are knwon deficiencies of LFSR when used to generate > anything but a bit sequence. That is if you pack the bits in numbers, > then the autocorrelation properties of the numbers are NOT > the flat autocorelation of the but sequence. This is already > discussed in Knuth e.g. with the remark that LFSR using > polynomial of low weigth are worse. > > ------------------------------------------------------------------------ > > Marc Delvaux <mdel@globespan.net> > LSI designer > GlobeSpan Semiconductors > > Marc Delvaux > LSI designer <mdel@globespan.net> > GlobeSpan Semiconductors HTML Mail > 100 Schulz Drive Work: +1 (732) 345 7502 > Red Bank Fax: +1 (732) 345 7592 > NJ Home: +1 (732) 578 9255 > 07701 Netscape Conference Address > USA Netscape Conference DLS Server > Additional Information: > Last Name Delvaux > First Name Marc > Version 2.1 -- -Ray Andraka, P.E. President, the Andraka Consulting Group, Inc. 401/884-7930 Fax 401/884-7950 email randraka@ids.net http://users.ids.net/~randrakaArticle: 17494
On Sat, 31 Jul 1999 00:05:47 -0400 Ray Andraka <randraka@ids.net> wrote: >Luis Yanes wrote: >> >> No, F1.3 doesn't support XC5200 series, that is becouse I used the >> F1.4 from the school. My Foundation package aren't the student >> edition, but the Foundation Base (without vhdl :-( ) that costed me >> about US$ 150. > >I don't think 1.4 or 1.5 support the 5200 either. You need to be under maintenance >to get the next version up. You really should consider upgrading, as there are >numerous bugs (did I say that? I meant "features") in 1.3 and 1.4. I just got the >alliance 2.1 tools, so the foundation 2.1 is probably also either shipping or will be >soon. Yes, F1.4 have the XC5200 family. I got some patchs that should fix some bugs but anyway I'll look for F2.1. >> I searched the Xilinx site for updates, but I couldn't find any, only >> patches and speed files, but none that will upgrade to F1.4 or up. >> Asked the local distribuitor here, where I bought the package, told me >> that I must buy another full package, the same I own but newer version >> of software! > >Can you get under maintenence, it might be cheaper than starting new. The distribuitor here charges the same new or maintenence. They sell you a new one now, or tell to wait 4 weeks to get the upgrade for the same price. That is here. Ray, I like to thank you, all your valuable help. Now I must 'only' play with the tools to do it. 73's de Luis mail: melus@esi.us.es Ampr: eb7gwl.ampr.org http://www.esi.us.es/~melus/ <- Homebrewed Hardware Projects with PCBsArticle: 17495
On Wed, 28 Jul 1999 18:00:14 -0400 Ray Andraka <randraka@ids.net> wrote: > You should be able to get the spartan parts in small >quantities from a reseller such as hamilton avnet. Try http://www.avnet.com . Their online purchasing tool only allow to buy from 15 units each minimun. Yes, its less than the 26 that the Xilinx local distribuitor here want to sell me, but excesive also. 73's de Luis mail: melus@esi.us.es Ampr: eb7gwl.ampr.org http://www.esi.us.es/~melus/ <- Homebrewed Hardware Projects with PCBsArticle: 17496
I'm trying to implement a Boundary Scan interface to a Xilinx 4010XL device to do Configuration and Readback. The configuration works OK, but I've got some trouble with the Readback, Could anybody tell me what length the bitstream should be for Readback, from the xilinx datasheets it should be 178,136 bit's (Including header and all!) but I'm receiving (and configuring) 283424 bits! Tar for any info... P.S. remove NOSPAM to replyArticle: 17497
Hmmm, seems to remind me of a problem that I worked on about 20 years ago. We were designing a custom engine for Monte-Carlo simulation and needed an extremely good source of multi-bit pseudo random numbers. I developed an algorithm based on LFSR that had good properties. The mathematics of this approach was published in 'Journal of Computational Physics' in 1982 or 1983. I don't have the exact citation but the title was 'An Algorithm for Pseudo Random Number Generation Suitable for Large Scale Integration', author Robert B. Pearson. The basic idea was a coupled n-bit LSFR where the inputs to the xor are cross coupled in a specific pattern that places the msb bits as far apart as possible in the chain. Not described there is a similar pattern that has this property for both the msb and lsb bits of the numbers at the same time. The polynomial is replaced by a matrix of feedback terms with polynomial coefficients. The resulting generator has maximum length if the determinant of the matrix is a prime polynomial mod 2. It is easy to show that the resulting most significant k bits have the optimal distribution possible for the number of state bits in the generator. Several example generators are given with up to 32 bit numbers and 521 bit generators. These could be very easily implemented in an fpga and require much less space than a similar LSFR generator that replicates the state for each bit in the word. Contact me at bpearson@pmr.com if you would like a copy of the paper. Ray Andraka wrote in message <37A353EA.DBDDC700@ids.net>... >If you are using an LFSR as a random number generator, you should only take >one bit per clock cycle, as the other bits are just time shifted copies of the >first bit. If you insist on taking more than one bit, the newest bit should >be at the MSB position to provide the least effect of the previous bits. Be >warned that you end up with marked spectral coloring (the time shifted bits >essentially comprise a comb filter). > >For a one bit random variable, the LFSR does a good job as long as the >sequence is long enough that it doesn't repeat within your experiment. There >is a slight bias toward a zero bit, which for long LFSRs is negligable (the >ratio of one bits to zero bits is 2^(n-1)-1 : 2^(n-1). A 129 bit LFSR only >takes a few CLBs in xilinx 4K or virtex FPGAs, and it won't repeat for several >thousand years at 40 MHz. 129 bits works nicely for the feedback taps. If >you need more than one bit, then either clock the LFSR n times per sample or >use n LFSRs in parallel with different seeds. For one bit outputs, the >sequence is a remarkably good uniform random variable. Using an LFSR also has >the advantage in debug of being able to repeat a sequence by reloading it with >the same seed. > >You can use a binary search of a cumulative density function of a desired >distribution to convert the uniform LFSR to an arbitrary distribution. I've >done that in hardware to get a Rayliegh distribution at an 11 MHz sample >rate. You can also sum bits from a bunch of LFSR samples to get an >approximation of a gaussian distribution using the central limit theorem. >I've also done that by summing 128 LFSR samples to get a 40MHz complex >gaussian distribution. The probability tails will determine how far you have >to go. There is a little bit of discussion on these in the radar simulator >paper (MAPLD '98) on my website. > >Marc Delvaux wrote: > >> Hal Murray wrote: >> >> > What's "OK, but not great" about LFSRs? They are real easy >> > to implement, run as fast as you want (put them in parallel >> > if you need more bits) and have very well understood mathematical >> > patterns. >> > >> > >> >> There are knwon deficiencies of LFSR when used to generate >> anything but a bit sequence. That is if you pack the bits in numbers, >> then the autocorrelation properties of the numbers are NOT >> the flat autocorelation of the but sequence. This is already >> discussed in Knuth e.g. with the remark that LFSR using >> polynomial of low weigth are worse. >> >> ----------------------------------------------------------------------- - >> >> Marc Delvaux <mdel@globespan.net> >> LSI designer >> GlobeSpan Semiconductors >> >> Marc Delvaux >> LSI designer <mdel@globespan.net> >> GlobeSpan Semiconductors HTML Mail >> 100 Schulz Drive Work: +1 (732) 345 7502 >> Red Bank Fax: +1 (732) 345 7592 >> NJ Home: +1 (732) 578 9255 >> 07701 Netscape Conference Address >> USA Netscape Conference DLS Server >> Additional Information: >> Last Name Delvaux >> First Name Marc >> Version 2.1 > > > >-- >-Ray Andraka, P.E. >President, the Andraka Consulting Group, Inc. >401/884-7930 Fax 401/884-7950 >email randraka@ids.net >http://users.ids.net/~randraka > >Article: 17498
This is a multi-part message in MIME format. --------------8C19AC578A18E436D2A9B219 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit I agree with all of Ray's suggestions to avoid correlation effects when using LFSR based random number generator. I would like to expand again the subject by two other remarks: - a relatively recent article shows that trinomials based LFSR may not be so good, even when generating a bit sequence. This is only a problem for long period LFSRs. I didn't find an URL, but the article ref is "Strong deviation from randomness in m-sequences based on trinomials", Makoto Matsumoto and Yoshiharu Kurita, ACM transactions on Modeling and Computer Simulation, Vol 6, n2, April 1996, pp 99-106. - it is easy to build a circuit equivalent to a LFSR advancing n steps per clock cycle and almosy as quick as the one step per cycle. If n is relative prime to the period, the circuit has the same period than the original one. The last part of Ray's message, describing applications, is fascinating. In general, i would not recommending summing uniform to get a gaussian, but this may be the simplest way in HW. As Ray's mentions, be careful about the tails in that case. The other classical way to generate random gaussian variables is to transform two uncorrelated uniform, but this is indeed more complicated in HW. Ray Andraka wrote: > If you are using an LFSR as a random number generator, you should only take > one bit per clock cycle, as the other bits are just time shifted copies of the > first bit. If you insist on taking more than one bit, the newest bit should > be at the MSB position to provide the least effect of the previous bits. Be > warned that you end up with marked spectral coloring (the time shifted bits > essentially comprise a comb filter). > > For a one bit random variable, the LFSR does a good job as long as the > sequence is long enough that it doesn't repeat within your experiment. There > is a slight bias toward a zero bit, which for long LFSRs is negligable (the > ratio of one bits to zero bits is 2^(n-1)-1 : 2^(n-1). A 129 bit LFSR only > takes a few CLBs in xilinx 4K or virtex FPGAs, and it won't repeat for several > thousand years at 40 MHz. 129 bits works nicely for the feedback taps. If > you need more than one bit, then either clock the LFSR n times per sample or > use n LFSRs in parallel with different seeds. For one bit outputs, the > sequence is a remarkably good uniform random variable. Using an LFSR also has > the advantage in debug of being able to repeat a sequence by reloading it with > the same seed. > > You can use a binary search of a cumulative density function of a desired > distribution to convert the uniform LFSR to an arbitrary distribution. I've > done that in hardware to get a Rayliegh distribution at an 11 MHz sample > rate. You can also sum bits from a bunch of LFSR samples to get an > approximation of a gaussian distribution using the central limit theorem. > I've also done that by summing 128 LFSR samples to get a 40MHz complex > gaussian distribution. The probability tails will determine how far you have > to go. There is a little bit of discussion on these in the radar simulator > paper (MAPLD '98) on my website. > > Marc Delvaux wrote: > > > Hal Murray wrote: > > > > > What's "OK, but not great" about LFSRs? They are real easy > > > to implement, run as fast as you want (put them in parallel > > > if you need more bits) and have very well understood mathematical > > > patterns. > > > > > > > > > > There are knwon deficiencies of LFSR when used to generate > > anything but a bit sequence. That is if you pack the bits in numbers, > > then the autocorrelation properties of the numbers are NOT > > the flat autocorelation of the but sequence. This is already > > discussed in Knuth e.g. with the remark that LFSR using > > polynomial of low weigth are worse. > > > > ------------------------------------------------------------------------ > -- > -Ray Andraka, P.E. > President, the Andraka Consulting Group, Inc. > 401/884-7930 Fax 401/884-7950 > email randraka@ids.net > http://users.ids.net/~randraka --------------8C19AC578A18E436D2A9B219 Content-Type: text/x-vcard; charset=us-ascii; name="vcard.vcf" Content-Transfer-Encoding: 7bit Content-Description: Card for Marc Delvaux Content-Disposition: attachment; filename="vcard.vcf" begin: vcard fn: Marc Delvaux n: Delvaux;Marc org: GlobeSpan Semiconductors adr: 100 Schulz Drive;;;Red Bank;NJ;07701;USA email;internet: mdel@globespan.net title: LSI designer tel;work: +1 (732) 345 7502 tel;fax: +1 (732) 345 7592 tel;home: +1 (732) 578 9255 x-mozilla-cpt: ;0 x-mozilla-html: TRUE version: 2.1 end: vcard --------------8C19AC578A18E436D2A9B219--Article: 17499
Marc Delvaux wrote:
> I agree with all of Ray's suggestions to avoid correlation effects when
> using LFSR based random number generator. I would like to
> expand again the subject by two other remarks:
> - a relatively recent article shows that trinomials based LFSR may not be
> so good, even when generating a bit sequence. This is only a problem
> for long period LFSRs. I didn't find an URL, but the article ref is
> "Strong deviation from randomness in m-sequences based on trinomials",
> Makoto Matsumoto and Yoshiharu Kurita, ACM transactions on
> Modeling and Computer Simulation, Vol 6, n2, April 1996, pp 99-106.
> - it is easy to build a circuit equivalent to a LFSR advancing n steps
> per clock cycle and almosy as quick as the one step per cycle. If n
> is relative prime to the period, the circuit has the same period than the
> original one.
Clocking multiple clocks is a good way to go if you have the higher rate clock
available and the circuit is capable of being clocked that fast. In the case of my
gaussian generator, the required data output was 40 MHz. I clocked the LFSRs ar
80MHz to get two random bits per sample time. I used 64 copies of the LFSR (each
LFSR was 67 bits long), each with a unique seed and summed the outputs on each
clock, then summed the results from even and odd clock cycles to get a sum of 128
random bits. That gave us sufficient accuracy in the tail probabilities. That was
in a 4025E-2, which has a max clock rate on the CLB RAM used in the LFSRs of around
100MHz.
>
>
> The last part of Ray's message, describing applications, is fascinating.
> In general, i would not recommending summing uniform to get a
> gaussian, but this may be the simplest way in HW. As Ray's mentions,
> be careful about the tails in that case. The other classical way to
> generate random gaussian variables is to transform two uncorrelated
> uniform, but this is indeed more complicated in HW.
>
The transformation you refer to is downright ugly in hardware, as it involves square
roots, logs and sin/cos:
y1 = sqrt( - 2 ln(x1) ) cos( 2 pi x2 )
y2 = sqrt( - 2 ln(x1) ) sin( 2 pi x2 )
--
-Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930 Fax 401/884-7950
email randraka@ids.net
http://users.ids.net/~randraka
Site Home Archive Home FAQ Home How to search the Archive How to Navigate the Archive
Compare FPGA features and resources
Threads starting:
Authors:A B C D E F G H I J K L M N O P Q R S T U V W X Y Z