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
In article <3A550E6F.EAEF92E9@sgi.com>, Eric C. Fromm <efromm@sgi.com> writes: > OK, I get the 'multiple candidates for next state' bit. You lost me with > the 'expressive power' assertion though. What is this characteristic and > how do DFAs and NFAs compare to other constructs (and what are those > constructs)? If I recall my computability class from eons ago, I believe given a NFA, you can construct an equivalent DFA. Basically, the states of the DFA map to the sets of possible states the DFA could be in. In other words, if from state A, event 1 could take it to either states B or C, the DFA will have a state indicating the NFA is in either state B or C. -- Pete SmootArticle: 28276
In article <3A54F76B.91714F79@xilinx.com>, peter.alfke@xilinx.com wrote: > Hi, > tell us more about non-deterministic finite state machines. > What makes them non-deterministic? > Do they roll dice? ;-) > What's good about them? > > Peter Alfke, Xilinx > ============================== > "Reetinder P. S. Sidhu" wrote: > > > Hi all > > > > I'm a PhD student whose current research focuses on nondeterministic > > FSMs. It seems to me that there are interesting ways of implementing > > them efficiently in hardware. I was wondering if nondeterministic FSMs > > have previously been implemented in VLSI/programmable logic and if so, > > for what applications. > > > > I would be grateful for any info/pointers regarding above. Thanks in > > advance. > > > > Regards > > I did a search on Northern Light, and came up with some links, including these: http://www.cse.msu.edu/~torng/360Book/NFA/ http://www.netaxs.com/people/nerp/automata/nfa1.html http://www.grappa.univ-lille3.fr/tata/ The first link refers to the NFA as an "unrealistic model of computation". From a theoretical perspective, it's easy to follow how an NFA works. I don't see how you would implement this in an FPGA, without having a random number generator to produce "non-deterministic" branches. So then, the NFA would be implemented as an FSA with a random number generator output being used as an input to the state machine. I can't imagine why anyone would want to do this for a practical application, so I am also interested to see where the OP is going with this. -- Greg Neff VP Engineering *Microsym* Computers Inc. greg@guesswhichwordgoeshere.com Sent via Deja.com http://www.deja.com/Article: 28277
"Reetinder P. S. Sidhu" wrote: > > Hi all > > I'm a PhD student whose current research focuses on nondeterministic > FSMs. It seems to me that there are interesting ways of implementing > them efficiently in hardware. I was wondering if nondeterministic FSMs > have previously been implemented in VLSI/programmable logic and if so, > for what applications. > > I would be grateful for any info/pointers regarding above. Thanks in > advance. What exactly do you mean? An FSM with probablistic state transitions governed by a pseudo random sequence generator like an LFSR or a linear congruence modulo multiplier? Or governed by a truely random noise source like amplified thermal background noise? -- Paul W. DeMone The 801 experiment SPARCed an ARMs race of EPIC Kanata, Ontario proportions to put more PRECISION and POWER into demone@mosaid.com architectures with MIPSed results but ALPHA's well pdemone@igs.net that ends well.Article: 28278
> I was wondering if nondeterministic FSMs have previously been implemented Rather too often. Thomas Maslen maslen@pobox.com (Oh, you meant deliberately?)Article: 28279
In comp.arch Reetinder P. S. Sidhu <sidhu@halcyon.usc.edu> wrote: > Hi all > I'm a PhD student whose current research focuses on nondeterministic > FSMs. It seems to me that there are interesting ways of implementing > them efficiently in hardware. I was wondering if nondeterministic FSMs > have previously been implemented in VLSI/programmable logic and if so, > for what applications. > I would be grateful for any info/pointers regarding above. Thanks in > advance. Humm, A "true" nondeterministic FSA, in the theoritical computer-science sense would be novel, but I would think impossible to do "efficently." (At least without some type of quantum trick.) If you have a way that really does that I would be quite interested. It certainly would have significant applications... If you mean a FSM which randomly goes to different states based on certain probabilities, I really have no clue if it has been done, nor do any applications jump out at me. (But I'd not be shocked if there were many, even in computer architecture.) Mark > Regards -- ~~~~~~~~~~~~~~~~ http://www.cps.msu.edu/~brehob ~~~~~~~~~~~~~~~~~~ ~~~~~~Mark Brehob: Ultimate Player, Gamer, Computer Geek~~~~~~~~~~Article: 28280
Hello, I am trying to build an I/O board, with just one Altera EPM7128SLC84 (MAX7000S family) CPLD, which will be interfaced to a PC/104 (ISA) bus. The description of the setup and the problems I am seeing can be found at the following link: http://home.earthlink.net/~ashokm1/max7000_isa_bus.htm Can anyone please help? And enlighten me as to why it does not work as expected? Thank you, AshokArticle: 28281
Non-deterministic? We try pretty hard to make things deterministic. :-) Tell us more. del cecchi "Reetinder P. S. Sidhu" <sidhu@halcyon.usc.edu> wrote in message news:932ro2$j6e$1@halcyon.usc.edu... > > Hi all > > I'm a PhD student whose current research focuses on nondeterministic > FSMs. It seems to me that there are interesting ways of implementing > them efficiently in hardware. I was wondering if nondeterministic FSMs > have previously been implemented in VLSI/programmable logic and if so, > for what applications. > > I would be grateful for any info/pointers regarding above. Thanks in > advance. > > RegardsArticle: 28282
At last .... a use for metastable flipflops. -- philip On 4 Jan 2001 13:59:30 -0800, sidhu@halcyon.usc.edu (Reetinder P. S. Sidhu) wrote: > >Hi all > >I'm a PhD student whose current research focuses on nondeterministic >FSMs. It seems to me that there are interesting ways of implementing >them efficiently in hardware. I was wondering if nondeterministic FSMs >have previously been implemented in VLSI/programmable logic and if so, >for what applications. > >I would be grateful for any info/pointers regarding above. Thanks in >advance. > > Regards Philip Freidin FliptronicsArticle: 28283
In article <3A552F9E.61B88CDB@igs.net>, Paul DeMone <pdemone@igs.net> wrote: >What exactly do you mean? An FSM with probablistic state transitions >governed by a pseudo random sequence generator like an LFSR or a linear >congruence modulo multiplier? Or governed by a truely random noise >source like amplified thermal background noise? _Compilers:_Principles,_Techniques,_and_Tools_ discusses this. What you do with an NFA is that you essentially "take" all the transitions that are possible in a state, at once. Your current "state" is really the set of all the states of the NFA (Non-deterministic Finite Automaton) that you could be in. You take all the possible transitions out of all those states that you could be in. I think if one of the new states is a terminating state, you stop. You can implement these things pretty efficiently (for a fixed maximum number of states) by managing your current state as a bit-vector which indicates which of the NFA states you are currently in. You should be able to, um, use the current bit vector as enables on a set of functional units (one per state) each of which consumes the current input symbol and emits a new bit vector of possible states. Then OR the results of all the functional units together to get your new state. And the current state vector with a vector representing terminating states, if the result is non-zero, stop. Your hardware will set a Really Hard cap on the maximum number of NFA states you support. The details of how input symbols select transitions will determine the inner structure of the functional units. If, for eaxmple, you are doing string matching, there is a straightforward way to convert a regular expression into an NFA. If you support up to, say, 64 states (which will capture regular expressions up to something near 64 characters long, I think), each state (functional unit) can be a 256 element memory 64 bits wide. The input symbol is a character, and acts as the address. Address all the little RAMs at once, and use the current input state as output enables on the RAMs. This could go quite fast, though where you'd find RAMs that shape I have no idea. I guess you could do this in an FPGA and do regexp matching at 100M characters/second? Network Intrusion Detection, anyone? Why I don't get is what makes this interesting, it all seems pretty trivial to me. Am I missing something? A previous poster basically summed it up. You implement an NFA as a DFA (Deterministic Finite Automaton) whose states are collections of the NFA state. The point of doing it as an NFA is that you don't have to construct the entire DFA, you essentially "dynamically" construct that states and transitions of an equivalent DFA as you go. The NFA is generally quite a bit smaller than equivalent DFAs (I think one can construct examples where equivalent DFAs all have 2^n states). Furthermore, if you need to run a finite automaton on one input only, it is more efficient to run the NFA and (inefficiently) construct only the DFA states you NEED instead of constructing the entire DFA. The referenced book has a nice discussion of many of these issues. [ by the way, I forget, or never knew, whether one NFA can have more than one equivalent DFA. I used the plural above, because it feels right, but there may always be one DFA ]Article: 28284
"Eric C. Fromm" <efromm@sgi.com> writes: > > OK, I get the 'multiple candidates for next state' bit. You lost me with > the 'expressive power' assertion though. What is this characteristic and > how do DFAs and NFAs compare to other constructs (and what are those > constructs)? Wow -- the best answer to that question is probably to take a class in formal language theory... but here's a capsule summary. There is a standard way of describing the complexity of a program's inputs in terms of the features needed in the program to be able to tell whether the program can tell whether or not an input is valid. The set of valid inputs for a program is called a language, in analogy to a natural language (like English) or a programming language. You can describe this in terms of the class of language, the features allowed in a grammar for the language, and the features required in a machine that can recognise the language. The hierarchy of languages is called the Chomsky hierarchy. Some of the members are: Variable names can be described by regular expressions, generated by regular grammars, and recognized by finite state machines. You can program one by using an enumerated type called a State, that keeps track of where you are in the string you're trying to recognize. A FSM would be able to tell if its input was a bunch of left and right parentheses, but couldn't tell (in general) if they balanced -- if your state variable had 100 states to count how many more left parens you've seen that right parens, I could start my string with 101 left parens and it would lose count. A compiler's lexical analyzer can recognize regular expressions. Arithmetic expressions can be generated by context free grammars and recognized by pushdown automata (PDA) -- basically, finite state machines with the addition of being able to push things on a stack, and pop them off the stack. The stack can get infinitely deep (this is theory, after all). Now we can tell if we have balanced parens: every time you give me a left paren, I push it on the stack; every time you give me a right paren I pop the stack. If I ever try to pop an empty stack I've seen too many right parens; if there's anything left on the stack at the end there were too many left parens. Pushdown automata are interesting in that they can recognize more languages if they can take guesses. So, if I want to recognize palindromes with a deterministic (ie no guessing) PDA, I can only do it if i've got a distinguished character that only appears at the center of the palindrome -- in this case, I can push everything I see until I hit the center, then pop everything after that. If what I pop matches what I see all the way to the end, I've got a palindrome. Now, if I've got a nondeterministic PDA I can just guess when to start popping (it's guaranteed to make the right guess if there is a right guess to be made). That's what makes the equivalence of deterministic and nondeterministic FSMs counterintuitive: you'd think being able to guess would make it more powerful in the sense that nPDAs are more powerful than dPDAs, but it doesn't matter. The parser in a compiler implements a PDA (that's not quite true, but it'll pass in this discussion). Turing Machines are the most powerful machines in the hierarchy; they act like computers with infinite memory (the access to the memory is very primitive, but that's a detail we don't need to worry about here). One interesting thing about TMs is that it's possible to have a langauge, and a string, and not be able to determine whether the string is in the language or not! Even stranger, there are languages for which we can tell if a string is in the langauge, but not necessarily whether it's not; languages for which we can tell that a string is definitely not in the language, but we can't tell for sure whether it is; and (thankfully) languages for which can in fact tell for sure. The Halting Problem is actually an example of a language for which we can tell if a string is in the language but can't tell if it isn't: let the language in question be ``the set of all programs written in C that take no input.'' We can always tell if a program halts: just watch and see what happens. We can sometimes tell if a program doesn't halt (hmmmm, the first executable line is while(1);). But there are C programs that we just can't tell for sure whether they will ever halt (there's nothing in there that we can look at and tell whether it's going to halt, and it's been running for three years now without halting.... but is it really in a hard loop, or is it going to terminate Real Soon Now?). -- Joseph J. Pfeiffer, Jr., Ph.D. Phone -- (505) 646-1605 Department of Computer Science FAX -- (505) 646-1002 New Mexico State University http://www.cs.nmsu.edu/~pfeiffer VL 2000 Homepage: http://www.cs.orst.edu/~burnett/vl2000/Article: 28285
"Reetinder P. S. Sidhu" <sidhu@halcyon.usc.edu> wrote in message news:932ro2$j6e$1@halcyon.usc.edu... > I'm a PhD student whose current research focuses on nondeterministic > FSMs. It seems to me that there are interesting ways of implementing > them efficiently in hardware. I was wondering if nondeterministic FSMs > have previously been implemented in VLSI/programmable logic and if so, > for what applications. [NFA=nondeterministic finite state automaton / FSM DFA=deterministic finite state automaton / FSM] Perhaps someday when/if we have quantum computing machines, we can build NFAs directly, using qubit-tuples to represent states. But that is rather far off. To implement an NFA in hardware today, you could convert it to a DFA using the subset construction, that is, you build an equivalent DFA whose states are those subsets of the set of states of the NFA that are reachable by a given input sequence (and any number of epsilon-transitions). See e.g. Compilers: Principles, Techniques, and Tools, Aho, Sethi, Ullman, pp.117-121, or the google-identified lecture notes that start at http://tina.lancs.ac.uk/computing/courses/year2/230/233/L3/sld025.htm. See also my note on Regular Expressions and Parsing in FPGAs, at www.fpgacpu.org/usenet/re.html. Jan Gray, Gray Research LLC FPGA CPU News: www.fpgacpu.orgArticle: 28286
Joe Pfeiffer wrote: > > "Eric C. Fromm" <efromm@sgi.com> writes: > > > > OK, I get the 'multiple candidates for next state' bit. You lost me with > > the 'expressive power' assertion though. What is this characteristic and > > how do DFAs and NFAs compare to other constructs (and what are those > > constructs)? > > Wow -- the best answer to that question is probably to take a class in > formal language theory... but here's a capsule summary. I nominate this as 'c.a Post of the Month'. Very nice, Joe! Terje -- - <Terje.Mathisen@hda.hydro.com> Using self-discipline, see http://www.eiffel.com/discipline "almost all programming can be viewed as an exercise in caching"Article: 28287
Thanks Ray for the answer. AFAIK I'm using the latest EXEMPLAR revision (Version: v20001b.106). Unless there is a later revision. I'll try to instance the SRL16E. Probably it will work, but simulating it in the INNOVEDA Visual HDL, will be another story. Anyway, I've mailed also to EXEMPLAR support about this, but no response so far. Thanks again, Yoav Hirsch ECI TELECOM. Sent via Deja.com http://www.deja.com/Article: 28288
"Paul DeMone" <pdemone@igs.net> wrote in message news:3A552F9E.61B88CDB@igs.net... > "Reetinder P. S. Sidhu" wrote: > > > > Hi all > > > > I'm a PhD student whose current research focuses on nondeterministic > > FSMs. It seems to me that there are interesting ways of implementing > > them efficiently in hardware. I was wondering if nondeterministic FSMs > > have previously been implemented in VLSI/programmable logic and if so, > > for what applications. > > > > I would be grateful for any info/pointers regarding above. Thanks in > > advance. > > What exactly do you mean? An FSM with probablistic state transitions > governed by a pseudo random sequence generator like an LFSR or a linear > congruence modulo multiplier? Or governed by a truely random noise > source like amplified thermal background noise? "Nondeterministic" has nothing to do with randomness. A "Nondeterminsitic Finite State Machine" would not chose which transition out of a state it would take: it takes all of them : that's the "nondeterminstic" part of it. The reason such a machine is interesting is because it can solve O(NP) problems in polynomial-bounded time. However, the amount of hardware it takes to do so is pretty large. IIRC, determining whether a proposed solution to an O(NP) problem actually does solve it is a O(P) problem. That is. a deterministic FSM can test in polynomial-bounded time whether a particular proposal solves an NP problem . Therefor, one direct way to build the equivalent of a nondeterminstic FSM is to build one deterministic FSM (and we all know how to do that :) for each possible solution to the NP problem, each of which checks whether its solution is a correct one, and operate them all in parallel. If the domain of possible solutions is finite and small enough, this isn't entirely impractical, and since all the FSMs are identical except for the solution they are testing, designing such hardware would be straightforward. I imagine there might be some interesting problems where the hardware to do this might be justified by the increase in speed, and especially be the increase in worst-case time-to-solution. -- Dennis O'Connor dmoc@primenet.com Vanity Web Page: http://www.primenet.com/~dmoc/Article: 28289
Lee Weston <lee.weston@philips.com> writes:
> Hello,
>
> I'm trying to generate a FPGA compiler2 script. What I want to do is
> create user defined VHDL libraries. From the help menu the command to do
> this is:
>
> create_library -name my_library
>
> This gives the following error:
>
> Error: extra positional option 'my_library' (CMD-012)
>
> Does anyone know what I'm doing wrong?
Try:
create_library my_library
even though the man page uses the syntax you described above.
Petter
--
________________________________________________________________________
Petter Gustad 8'h2B | ~8'h2B http://www.gustad.com
#include <stdio.h>/* compile/run this program to get my email address */
int main(void) {printf ("petter\100gustad\056com\nmy opinions only\n");}
Article: 28290Hi, I have a CPLD design with a .ucf file that works with last year's version of the web-pack tools. Now using the 3.2 ISE version of the tools the .ucf is suddenly using unknown keywords - such as NET. Even compiling the design without the .ucf and then letting the lock pin function generate a .ucf does not work. Defining this self generated UCF file as the projects UCF file causes the mapper and contraints editor to throw out the same syntax errors. Any solutions please? Anthony.Article: 28291
amolitor-at@visi-dot-com.com writes: > [ by the way, I forget, or never knew, whether one NFA can have > more than one equivalent DFA. I used the plural above, because > it feels right, but there may always be one DFA ] In general, both NFAs and DFAs can have redundant states, i.e., states where the eventual outcome will be the same for any subsequent output they are given. In both cases, AFAIR, there are algorithms to reduce an automaton to the smallest possible number of states, and I think those minimal automata are unique. Authoritative answers in the dragon book, I'm sure. However, using a minimal NFA does not guarantee that the subset algorithm alone will produce a minimal DFA. Also, all of the above only applies as is to automata where you run the whole input through and see if you end up in a success state. Regular expressions are often unanchored at the right, and if you want a matcher that stops as soon as it has a match, there's a few tricks you have to use. Lars Mathiesen (U of Copenhagen CS Dep) <thorinn@diku.dk> (Humour NOT marked)Article: 28292
[Context is wanting to run a DLL at 24 MHz when the min spec is 25.] > Now, I am assuming you are not going below 0C, so there will be some > margin there. But if not, then definitely don't do it. In general, CMOS prop time is linear in temp and supply voltage. He's only off by 4% so we should be able to draw the forbidden zone on a graph with voltage on one axis and temp on the other. Does that sort of reasoning work with DLLs? > Doubling with a delay and an XOR is a common technique, and if you can > take the delay element and place it off chip, you will not have to worry > about it getting too fast due to the process/voltage/temperature > variations in the FPGA. I used to use a small RC off chip that added to > the delay and made this reliable (used in 100K+ units of a fiber optic > transmission system). I lived through three process changes of Xilinx > fpga's with this method, even though it is an asynchronous "no-no". I seem to remember an old APP note describing using an XOR for a clock doubler and promising that the circuit would work. I think the trick was to use the clock on a FF that was inside the clock generation path so the delay was sure to be long enough to clock a FF on that chip and at that temp/voltage. Try this. The clock is the XOR of the input to a FF and it's output and that clock clocks the FF. Then the pulse width will be whatever the FF needs to get clocked plus some prop time for roundup. I can't see any way that wouldn't work. Well, it might not run fast enough, but that seems unlikely if the reason we are using this hack is because the clock it too slow for the DLL. But we can check the min time (worst case) and compare that to the spec sheet. I'd call a hack/kludge like this a non-prefered solution rather than a no-no. The goal is to make designs that work solidly. Mostly, that means meeting timings and that's obviously easier to check with clean digital logic - we have tools that do most of the work for us. But there are things like metastability so you do have to think about other issues. As long as there aren't many of them and they are around the edges we can probably get the whole design right. I'll try reasonably hard to avoid things like the XOR doubler, but when I run out of alternatives AND I think I can convince myself that it will work reliabily then I'll use them. That convincing frequently involves taking advantage of temp/voltage tracking to "prove" that the worst case can't happen when it will hurt you. The reason to avoid them is not that they don't work, but that it takes time to make sure they will work. I can think of two risks when using a non-prefered technique. The first is that I'll overlook something significant. The second is that there is a flaw in my reasoning or my arithmetic. This is the time when it's great to have smart friends who are willing to look over your design and double check your reasoning. I'd probably be more worried about bypassing on the power planes than something like an XOR clock doubler. Also note that the XOR doubler trick doesn't work if the design needs the DLL to phase lock to the input clock as well as generate faster clocks. -- These are my opinions, not necessarily my employers. I hate spam.Article: 28293
thorinn@diku.dk (Lars Henrik Mathiesen) writes: >amolitor-at@visi-dot-com.com writes: >> [ by the way, I forget, or never knew, whether one NFA can have >> more than one equivalent DFA. I used the plural above, because >> it feels right, but there may always be one DFA ] >In general, both NFAs and DFAs can have redundant states, i.e., states >where the eventual outcome will be the same for any subsequent output >they are given. >In both cases, AFAIR, there are algorithms to reduce an automaton to >the smallest possible number of states, and I think those minimal >automata are unique. Minimal DFA's are unique, minimal NFA's are not. >However, using a minimal NFA does not guarantee that the subset >algorithm alone will produce a minimal DFA. Indeed. And minimizing an NFA has higher complexity than minimizing a DFA, so there is little point in doing this first. >Also, all of the above only applies as is to automata where you run >the whole input through and see if you end up in a success state. >Regular expressions are often unanchored at the right, and if you want >a matcher that stops as soon as it has a match, there's a few tricks >you have to use. Most applications want the longest matching prefix of a string, not the shortest. Torben Mogensen (torbenm@diku.dk)Article: 28294
In article <932ro2$j6e$1@halcyon.usc.edu>,
sidhu@halcyon.usc.edu (Reetinder P. S. Sidhu) wrote:
>
> Hi all
>
> I'm a PhD student whose current research focuses on nondeterministic
> FSMs. It seems to me that there are interesting ways of implementing
> them efficiently in hardware. I was wondering if nondeterministic FSMs
> have previously been implemented in VLSI/programmable logic and if so,
> for what applications.
>
> I would be grateful for any info/pointers regarding above. Thanks in
> advance.
>
> Regards
I wonder what precisely do you call non determinitic FSMs. I see at
least 3 meanings for it:
- something like what is used in the building of scanner which can
also be described as a FSM having several active states at one
moment where all possible state transition are taken at a given
time;
- something like Petri nets which, if memory serve, can also be
described as a FSM having several active states at one moment;
one arbitrary possible transition is taken at a given time; one
transition desactivate one state and activate one or more new
states (if they where not alreay activated obviously);
- a FSM having one active state where one random possible state
transition is taken.
The first two may also be described as a deterministic FSM and I see
little interest of implementing then in an other way in VLSI. Wait,
it is the other way: deterministic FSM are implemented as non
deterministic FSM in the first meaning (every flip flop correspond
to a state, all possible transitions are always taken) :-) What I want
to say is that all these kind of machines are different descriptions
for the same reality. If you have have not seen this, I wonder if your
way of implementing them are really interestingly efficient (perhaps if
you consider other constraints that the classical one, but then it is
more the constraints that are interesting than the solution).
I know of nothing about implementing the third meaning. I currently
fail to see an application as well as an efficient implementation in
VLSI.
-- Jean-Marc
Sent via Deja.com
http://www.deja.com/
Article: 28295NO, pins are better left to be picked by the place&route tool. At minimum I think you should put together a dummy design, if you don't have time for a detailed one, do a quick place and route and go with that. As for the pins 100% is 20% to many used pins, I would select a larger device or different package to get more I/O pins. This is of course just my opinion and I could be wrong, jakab Mikhail Matusov wrote: > Hi all, > > Egg-chicken kind of problem. I have to give my board design out to a layout > person but I haven't yet had chance to start my FPGA work. Usually I do some > draft FPGA design and run tools at least once to fix the pins before giving > it out to do a layout but this time the schedule is really tight and if I go > this route it will be too late. This is not a very demanding design neither > in terms of complexity nor in terms of speed and I am using Spartan II > family device. Scary part is that the pins utilization is almost 100%. > > Nonetheless, do you guys think that I can get away with pins fixed > beforehand without too much thought (I put my clocks on global clock lines)? > > Thanks in advance, > > -- > ============================ > Mikhail Matusov > Hardware Design Engineer > Square Peg Communications > Tel.: 1 (613) 271-0044 ext.231 > Fax: 1 (613) 271-3007 > http://www.squarepeg.caArticle: 28296
Terje Mathisen wrote: > > Joe Pfeiffer wrote: > > > > "Eric C. Fromm" <efromm@sgi.com> writes: > > > > > > OK, I get the 'multiple candidates for next state' bit. You lost me with > > > the 'expressive power' assertion though. What is this characteristic and > > > how do DFAs and NFAs compare to other constructs (and what are those > > > constructs)? > > > > Wow -- the best answer to that question is probably to take a class in > > formal language theory... but here's a capsule summary. > > I nominate this as 'c.a Post of the Month'. > > Very nice, Joe! > > Terje My sentiments exactly. -eric -- Eric C. Fromm efromm@sgi.com Principal Engineer Scalable Systems Division SGI - Silicon Graphics, Inc. Chippewa Falls, Wi.Article: 28297
In article <3A556794.9A41CC98@hda.hydro.com>, Terje Mathisen <terje.mathisen@hda.hydro.com> writes: |> Joe Pfeiffer wrote: |> > |> > "Eric C. Fromm" <efromm@sgi.com> writes: |> > > |> > > OK, I get the 'multiple candidates for next state' bit. You lost me with |> > > the 'expressive power' assertion though. What is this characteristic and |> > > how do DFAs and NFAs compare to other constructs (and what are those |> > > constructs)? |> > |> > Wow -- the best answer to that question is probably to take a class in |> > formal language theory... but here's a capsule summary. |> |> I nominate this as 'c.a Post of the Month'. |> |> Very nice, Joe! |> |> Terje |> |> -- |> - <Terje.Mathisen@hda.hydro.com> |> Using self-discipline, see http://www.eiffel.com/discipline |> "almost all programming can be viewed as an exercise in caching" Yes, quite informative (what I understood of it), but disappointing. I thought we would get to make state machines with little white noise generators in them to aid in the control of the state transitions. :-) -- Del Cecchi cecchi@rchlandArticle: 28298
Ashok Mahadevan <ashokm1@earthlink.net> wrote in <3A553937.7FB8DA30@earthlink.net>: >http://home.earthlink.net/~ashokm1/max7000_isa_bus.htm Nice web page! One thing that jumps out at me is that you're using different edges of IOWR for different registers. Why? For an active low write signal, one usually clocks a register on the rising edge. Your registers at 300, 301, and 303 are clocking on the falling edge of nIOWR. The 245 structure looks ok. Are you running the latest Altera software?Article: 28299
Hello everybody,
first of all I'd like to thank you for your valuable input,
special thanks to Austin and Hal.
I succeeded creating a 48MHz clock from the 24Mhz, using
an XOR and a FF. I can see the clock with my scope,
it is running at 48Mhz and is approx 4ns high (and 16ns low),
with my XC2S50-TQ144-5C. The signal I probed was CLK2x from
the code below.
I did not succeed creating a 96MHz clock from the 48MHz
using a DLL. The signal probed at CLK4x is still 48MHz,
however with a duty cycle of 50%.
I probed the DLL's LOCKED pin- it seems to be high.
Hal, you wrote:
>>>
Also note that the XOR doubler trick doesn't work if the
design needs the DLL to phase lock to the input clock
as well as generate faster clocks
<<<
I do not care about the phase of my 96MHz clock, so as
far as I understood things, everything should be fine.
Is there something obvious that I missed?
Thanks again for your suggestions,
best regards
Felix Bertram
----------------------------------------
library IEEE;
use IEEE.std_logic_1164.all;
entity Clk4x is
port(
CLKIN : in STD_LOGIC; -- driven by 24MHz quartz
CLK1x : out STD_LOGIC; -- BUFged CLKIN
CLK2x : out STD_LOGIC; -- 48MHz (small duty cycle)
CLK4x : out STD_LOGIC -- should be 96MHz...
);
end Clk4x;
architecture BHV of Clk4x is
---- Component declarations -----
component bufg
port (
I : in std_ulogic;
O : out std_ulogic
);
end component;
component clkdll
port (
CLKFB : in std_ulogic := '0';
CLKIN : in std_ulogic := '0';
RST : in std_ulogic := '0';
CLK0 : out std_ulogic := '0';
CLK180 : out std_ulogic := '0';
CLK270 : out std_ulogic := '0';
CLK2X : out std_ulogic := '0';
CLK90 : out std_ulogic := '0';
CLKDV : out std_ulogic := '0';
LOCKED : out std_ulogic := '0'
);
end component;
component fd
port (
C : in std_ulogic;
D : in std_ulogic;
Q : out std_ulogic
);
end component;
component inv
port (
I : in std_ulogic;
O : out std_ulogic
);
end component;
component xor2
port (
I0 : in std_ulogic;
I1 : in std_ulogic;
O : out std_ulogic
);
end component;
---- User defined diagram declarations -----
attribute dont_touch: STRING;
---- Constants -----
constant GND_CONSTANT : STD_LOGIC := '0';
---- Signal declarations used on the diagram ----
signal CLK1I : STD_LOGIC; -- 1x clock
signal CLK2I : STD_LOGIC; -- 2x clock
signal CLK4I : STD_LOGIC; -- 4x clock
signal DLLOUT : STD_LOGIC; -- 2x DLL output
signal Q : STD_LOGIC; -- FF Q output
signal QINV : STD_LOGIC; -- ... inverted
---- Ground signals declarations -----
signal GND : STD_LOGIC;
---- Instance attributes ----
attribute dont_touch of U2 : label is "true";
attribute dont_touch of U3 : label is "true";
attribute dont_touch of U4 : label is "true";
begin
---- Component instantiations ----
U1 : bufg
port map(
I => dllout,
O => clk4i
);
U2 : xor2
port map(
I0 => clk1i,
I1 => qinv,
O => clk2i
);
U3 : inv
port map(
I => q,
O => qinv
);
U4 : fd
port map(
C => clk2i,
D => qinv,
Q => q
);
U7 : bufg
port map(
I => CLKIN,
O => clk1i
);
U8 : clkdll
port map(
CLK2X => dllout,
CLKFB => clk4i,
CLKIN => clk2i,
RST => GND
);
---- Power , ground assignment ----
GND <= GND_CONSTANT;
---- Terminal assignment ----
CLK1x <= clk1i;
CLK2x <= clk2i;
CLK4x <= clk4i;
end BHV;
----------------------------------------
Sent via Deja.com
http://www.deja.com/
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