Site Home   Archive Home   FAQ Home   How to search the Archive   How to Navigate the Archive   
Compare FPGA features and resources   

Threads starting:
1994JulAugSepOctNovDec1994
1995JanFebMarAprMayJunJulAugSepOctNovDec1995
1996JanFebMarAprMayJunJulAugSepOctNovDec1996
1997JanFebMarAprMayJunJulAugSepOctNovDec1997
1998JanFebMarAprMayJunJulAugSepOctNovDec1998
1999JanFebMarAprMayJunJulAugSepOctNovDec1999
2000JanFebMarAprMayJunJulAugSepOctNovDec2000
2001JanFebMarAprMayJunJulAugSepOctNovDec2001
2002JanFebMarAprMayJunJulAugSepOctNovDec2002
2003JanFebMarAprMayJunJulAugSepOctNovDec2003
2004JanFebMarAprMayJunJulAugSepOctNovDec2004
2005JanFebMarAprMayJunJulAugSepOctNovDec2005
2006JanFebMarAprMayJunJulAugSepOctNovDec2006
2007JanFebMarAprMayJunJulAugSepOctNovDec2007
2008JanFebMarAprMayJunJulAugSepOctNovDec2008
2009JanFebMarAprMayJunJulAugSepOctNovDec2009
2010JanFebMarAprMayJunJulAugSepOctNovDec2010
2011JanFebMarAprMayJunJulAugSepOctNovDec2011
2012JanFebMarAprMayJunJulAugSepOctNovDec2012
2013JanFebMarAprMayJunJulAugSepOctNovDec2013
2014JanFebMarAprMayJunJulAugSepOctNovDec2014
2015JanFebMarAprMayJunJulAugSepOctNovDec2015
2016JanFebMarAprMayJunJulAugSepOctNovDec2016
2017JanFebMarAprMayJunJulAugSepOctNovDec2017
2018JanFebMarAprMayJunJulAugSepOctNovDec2018
2019JanFebMarAprMayJunJulAugSepOctNovDec2019
2020JanFebMarAprMay2020

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

Custom Search

Messages from 28275

Article: 28275
Subject: Re: Nondeterministic FSMs in hardware?
From: psmoot@pinnaclesys.com (Pete Smoot)
Date: Thu, 4 Jan 2001 16:44:21 -0800
Links: << >>  << T >>  << A >>
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 Smoot


Article: 28276
Subject: Re: Nondeterministic FSMs in hardware?
From: Greg Neff <gregneff@my-deja.com>
Date: Fri, 05 Jan 2001 01:10:41 GMT
Links: << >>  << T >>  << A >>
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
Subject: Re: Nondeterministic FSMs in hardware?
From: Paul DeMone <pdemone@igs.net>
Date: Thu, 04 Jan 2001 21:21:18 -0500
Links: << >>  << T >>  << A >>


"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
Subject: Re: Nondeterministic FSMs in hardware?
From: Thomas Maslen <maslen@pobox.com>
Date: 5 Jan 01 02:33:59 GMT
Links: << >>  << T >>  << A >>
> I was wondering if nondeterministic FSMs have previously been implemented 

Rather too often.

   Thomas Maslen
   maslen@pobox.com
   (Oh, you meant deliberately?)

Article: 28279
Subject: Re: Nondeterministic FSMs in hardware?
From: Mark W Brehob <brehob@cse.msu.edu>
Date: 5 Jan 2001 02:49:57 GMT
Links: << >>  << T >>  << A >>
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
Subject: HELP: Problem with interfacing an Altera MAX7000 device to the ISA bus
From: Ashok Mahadevan <ashokm1@earthlink.net>
Date: Fri, 05 Jan 2001 03:02:22 GMT
Links: << >>  << T >>  << A >>
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,
Ashok


Article: 28281
Subject: Re: Nondeterministic FSMs in hardware?
From: "del cecchi" <dcecchi@msn.com>
Date: Thu, 4 Jan 2001 21:45:49 -0600
Links: << >>  << T >>  << A >>
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.
>
>      Regards



Article: 28282
Subject: Re: Nondeterministic FSMs in hardware?
From: Philip Freidin <philip@fliptronics.com>
Date: Thu, 04 Jan 2001 19:50:16 -0800
Links: << >>  << T >>  << A >>
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
Fliptronics

Article: 28283
Subject: Re: Nondeterministic FSMs in hardware?
From: amolitor-at@visi-dot-com.com
Date: Fri, 05 Jan 2001 03:57:39 GMT
Links: << >>  << T >>  << A >>
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
Subject: Re: Nondeterministic FSMs in hardware?
From: Joe Pfeiffer <pfeiffer@cs.nmsu.edu>
Date: 04 Jan 2001 22:25:08 -0700
Links: << >>  << T >>  << A >>
"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
Subject: Re: Nondeterministic FSMs in hardware?
From: "Jan Gray" <jsgray@acm.org>
Date: Fri, 05 Jan 2001 05:31:36 GMT
Links: << >>  << T >>  << A >>
"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.org




Article: 28286
Subject: Re: Nondeterministic FSMs in hardware?
From: Terje Mathisen <terje.mathisen@hda.hydro.com>
Date: Fri, 05 Jan 2001 07:20:04 +0100
Links: << >>  << T >>  << A >>
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
Subject: Re: XILINX SRL16E - FIFO
From: hirsch_yoav@my-deja.com
Date: Fri, 05 Jan 2001 06:47:57 GMT
Links: << >>  << T >>  << A >>
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
Subject: Re: Nondeterministic FSMs in hardware?
From: "Dennis O'Connor" <dmoc@primenet.com>
Date: Fri, 5 Jan 2001 00:22:30 -0700
Links: << >>  << T >>  << A >>
"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
Subject: Re: FPGA Compiler2 question
From: Petter Gustad <spam@gustad.com>
Date: 05 Jan 2001 10:01:09 +0100
Links: << >>  << T >>  << A >>
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: 28290
Subject: WebPack-ISE .ucf problem?
From: "Anthony Ellis - LogicWorks" <a.ellis@logicworks.co.za>
Date: Fri, 5 Jan 2001 11:20:06 +0200
Links: << >>  << T >>  << A >>
Hi,

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
Subject: Re: Nondeterministic FSMs in hardware?
From: thorinn@diku.dk (Lars Henrik Mathiesen)
Date: 5 Jan 2001 10:38:50 +0100
Links: << >>  << T >>  << A >>
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
Subject: Re: Spartan-II DLL Usage
From: murray@pa.dec.com (Hal Murray)
Date: 5 Jan 2001 09:50:38 GMT
Links: << >>  << T >>  << A >>

[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
Subject: Re: Nondeterministic FSMs in hardware?
From: torbenm@diku.dk (Torben AEgidius Mogensen)
Date: 5 Jan 2001 12:51:09 +0100
Links: << >>  << T >>  << A >>
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
Subject: Re: Nondeterministic FSMs in hardware?
From: Jean-Marc Bourguet <bourguet@my-deja.com>
Date: Fri, 05 Jan 2001 13:26:10 GMT
Links: << >>  << T >>  << A >>
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: 28295
Subject: Re: Fixing pins on Spartan II
From: Jakab Tanko <jtanko@ics-ltd.com>
Date: Fri, 05 Jan 2001 13:41:41 GMT
Links: << >>  << T >>  << A >>

NO, 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.ca


Article: 28296
Subject: Re: Nondeterministic FSMs in hardware?
From: "Eric C. Fromm" <efromm@sgi.com>
Date: Fri, 05 Jan 2001 08:04:28 -0600
Links: << >>  << T >>  << A >>
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
Subject: Re: Nondeterministic FSMs in hardware?
From: cecchi@signa.rchland.ibm.com (Del Cecchi)
Date: 5 Jan 2001 14:44:03 GMT
Links: << >>  << T >>  << A >>
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@rchland

Article: 28298
Subject: Re: HELP: Problem with interfacing an Altera MAX7000 device to the ISA bus
From: shiva@well.com (Kenneth Porter)
Date: Fri, 05 Jan 2001 15:01:35 -0000
Links: << >>  << T >>  << A >>
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
Subject: Re: Spartan-II DLL Usage
From: felix_bertram@my-deja.com
Date: Fri, 05 Jan 2001 15:37:35 GMT
Links: << >>  << T >>  << A >>
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:
1994JulAugSepOctNovDec1994
1995JanFebMarAprMayJunJulAugSepOctNovDec1995
1996JanFebMarAprMayJunJulAugSepOctNovDec1996
1997JanFebMarAprMayJunJulAugSepOctNovDec1997
1998JanFebMarAprMayJunJulAugSepOctNovDec1998
1999JanFebMarAprMayJunJulAugSepOctNovDec1999
2000JanFebMarAprMayJunJulAugSepOctNovDec2000
2001JanFebMarAprMayJunJulAugSepOctNovDec2001
2002JanFebMarAprMayJunJulAugSepOctNovDec2002
2003JanFebMarAprMayJunJulAugSepOctNovDec2003
2004JanFebMarAprMayJunJulAugSepOctNovDec2004
2005JanFebMarAprMayJunJulAugSepOctNovDec2005
2006JanFebMarAprMayJunJulAugSepOctNovDec2006
2007JanFebMarAprMayJunJulAugSepOctNovDec2007
2008JanFebMarAprMayJunJulAugSepOctNovDec2008
2009JanFebMarAprMayJunJulAugSepOctNovDec2009
2010JanFebMarAprMayJunJulAugSepOctNovDec2010
2011JanFebMarAprMayJunJulAugSepOctNovDec2011
2012JanFebMarAprMayJunJulAugSepOctNovDec2012
2013JanFebMarAprMayJunJulAugSepOctNovDec2013
2014JanFebMarAprMayJunJulAugSepOctNovDec2014
2015JanFebMarAprMayJunJulAugSepOctNovDec2015
2016JanFebMarAprMayJunJulAugSepOctNovDec2016
2017JanFebMarAprMayJunJulAugSepOctNovDec2017
2018JanFebMarAprMayJunJulAugSepOctNovDec2018
2019JanFebMarAprMayJunJulAugSepOctNovDec2019
2020JanFebMarAprMay2020

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

Custom Search