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
Lathi.Tan@gmail.com wrote: > I am having a very stange problem with my state machine. The state > machine turns dead after some uncertain time(20min ~ 2 days) and all > outputs of the statemachine are 0. All other logics in the chips work > properly at the same time. The state machine is very simple, only with > 8 states. I tried with StateCAD and programming manually with VHDL and > they behave the same. Anybody know what's possibly the problem? I have > been working on this for a week and really cannot find a way out. > Thanks. Lathi, the most common problem with state machines is an (or several) input signals that are not synchronous with the clock. When an asynchronous signal goes to several flip-flop inputs, it might arrive at one flip-flop before,and at another after the clock, so that what should be one input becomes two inputs, and the machine can get totally confused. Remedy: Never run an asynchronous input into more than one flip-flop. Best method: Pre-synchronize all asynchronous inputs before they reach the state machine. I am 95% sure that this is your problem. When you use one-hot encoding for 8 states, you have 8 flip-flops, which might of course have 256 different states. They might accidentally get into one of the 248 illegal states... That's the remaining 4% You might also have a dirty clock (double edges, slow risetime etc) That's the last percent. Peter Alfke, Xilinx (from home)Article: 109376
thx =E3=80=82 Antti wrote: > lzh08 schrieb: > > > who can give me source code about ISA BUS ?thx > > http://www.mesanet.com/ > > browse there, look into all ZIP archives > I think there are some ISA related stuff inside >=20 > AnttiArticle: 109377
Adnan wrote: > I am a final year student and working on my senior design project. I > need PCI Master core and unfortunately I cannot buy any licensed core > because of their high price. I have seen opencores.org PCI bridge but > it has few problems > 1. Its test bench is too complex to understand. I was expecting some > black box sort of interface. > 2. Its driver is written in linux, but I have developed my software > part in MS Visual C-6, soI need windows driver. 1. If you spent a little more time trying to understand how it works, you'll see that it's not that complex at all. It's simply that the tests are quite comprehensive and hence covers quite a large number of cases. In fact, we stripped out the 'core' functions of the testbench to create a library of routines that allowed us to write testbench scripts for higher-level PCI functionality and there really isn't a lot of code in there. 2. As Kolja said differently, there's no such thing as an "opencores PCI driver". The core out-of-the-box does absolutely *nothing* useful other than appear as a PCI bridge to bios and/or low-level OS probing routines. It's not until you add peripherals to the back end that you require a "driver" and this is dependent not on the bridge itself but your chosen configuration of PCI space and the peripherals you implement. IMHO implementing the opencores PCI bridge and writing some software to talk to back-end peripherals is quite nicely weighted as a final-year design project. It's not as if you're implementing the bridge yourself. Regards, -- Mark McDougall, Engineer Virtual Logic Pty Ltd, <http://www.vl.com.au> 21-25 King St, Rockdale, 2216 Ph: +612-9599-3255 Fax: +612-9599-3266Article: 109378
Peter, It's great to know that. I've never heard of this. Can you give me more information about the first case(links, examples)? I am thinking about adding a flip-flop to all input signals but shall I used a clock edge to synchronize them different from those flip-flops in the statemachine? I do see asynchronous inputs to parallel flip flops on RTL schematic. Should StateCAD prevent this? I use user defined encoding: The Xilinx tool gave me the following information: Optimizing FSM <XLXI_5/XLXI_126/CurrState> on signal <CurrState[1:3]> with user encoding. ------------------- State | Encoding ------------------- s000 | 000 s001 | 001 s010 | 010 s011 | 011 s100 | 100 s101 | 101 s110 | 110 s111 | 111 ------------------- So I guess there shouldn't be other states. I also have a 'when others' line in the statemachine. Is there any simple way to clean up the clock in Xilinx tool, such as a buffer? Thanks a lot. Wei Peter Alfke wrote: > Lathi.Tan@gmail.com wrote: > > I am having a very stange problem with my state machine. The state > > machine turns dead after some uncertain time(20min ~ 2 days) and all > > outputs of the statemachine are 0. All other logics in the chips work > > properly at the same time. The state machine is very simple, only with > > 8 states. I tried with StateCAD and programming manually with VHDL and > > they behave the same. Anybody know what's possibly the problem? I have > > been working on this for a week and really cannot find a way out. > > Thanks. > Lathi, > the most common problem with state machines is an (or several) input > signals that are not synchronous with the clock. When an asynchronous > signal goes to several flip-flop inputs, it might arrive at one > flip-flop before,and at another after the clock, so that what should be > one input becomes two inputs, and the machine can get totally confused. > Remedy: Never run an asynchronous input into more than one flip-flop. > Best method: Pre-synchronize all asynchronous inputs before they reach > the state machine. > I am 95% sure that this is your problem. > > When you use one-hot encoding for 8 states, you have 8 flip-flops, > which might of course have 256 different states. They might > accidentally get into one of the 248 illegal states... > That's the remaining 4% > You might also have a dirty clock (double edges, slow risetime etc) > That's the last percent. > Peter Alfke, Xilinx (from home)Article: 109379
the systemverilog is a power tools used in verification,i want to learn it.Article: 109380
John Larkin wrote: > > > An opamp-based allpass 90 degree phase shifter is pretty simple; 8 > opamp sections, 8 caps, 24 resistors gives nice quadrature signals > over the voice range. And simulating a R-C section in an FPGA is > trivial. So it seems to me that one could do a nice Hilbert with a > fairly small amount of FPGA resources by just mimicing the opamp > circuit in discrete time. That would be a lot smaller than a FIR > implementation. > > Anybody done it this way? > > John > That's an IIR implementation. Generally speaking, IIR filters do not have the phase linearity required by many of the modern modulation schemes. They are fine for AM/FM, but when you start dealing with phase modulation, the non-linearity can make it extremely difficult to demodulate the signal.Article: 109381
On 25 Sep 2006 19:23:08 -0700, Lathi.Tan@gmail.com wrote: >Peter, > >It's great to know that. I've never heard of this. Can you give me more >information about the first case(links, examples)? I am thinking about >adding a flip-flop to all input signals but shall I used a clock edge >to synchronize them different from those flip-flops in the >statemachine? I have an article on my site called, appropriately enough, "Synchronizing FSM Inputs." http://www.cambriandesign.com/2006/02/synchronizing-fsm-inputs.html Bob Perlman Cambrian Design Works http://www.cambriandesign.comArticle: 109382
I suspect "Professional Edition" and "Special Edition", since, looking at the comparison chart (compare.pdf) that can be found on the Xilinx website (or maybe the ModelSim website at http://www.model.com), SE has more features. I sure wish organizations would include glossaries or acronym pages or FAQs to explain their acronyms. I complained directly today via both the Xilinx and the ModelSim websites about that. DUANWKWYM*. Cheers, -James * "Don't Use Acronyms; Nobody Will Know What You Mean."Article: 109383
Arthur J. O'Dwyer wrote:
> On Sun, 24 Sep 2006, Weng Tianxiang wrote:
> > eKo1 wrote:
> >>
> >> Let V' be a subset of V. V' is a vertex cover if it satisfies the
> >> following test:
> >>
> >> E' =3D =D8
> >> for each v in V'
> >> for each edge e in E
> >> if v is incident to e then
> >> add e to E'
> >> end if
> >> end for
> >> end for
> >> if |E| =3D |E'| then
> >> return true // V' is a vertex cover
> >> end if
> >> return false
> >>
> >> Would this be correct?
> >
> > Hi eKo1,
> > The algorithm you mentioned for a vertex cover is right.
>
> Yes, that's right. (And it suggests a trivial brute-force algorithm
> to find a minimum vertex cover:
>
> M =3D V
> for each V' in V
> if (V' is a vertex cover of G) then
> if |V'| < |M| then
> M =3D V
> end if
> end if
> end for
> return M
>
> Now M is a minimum vertex cover.)
>
>
> > Here is my full new algorithm that can get minimum vertex cover:
> >
> > To make discussion simpler, we assume that every vertex has a positive
> > integer, starting with 1 to n and input cells have the following
> > structure:
> > (edge count, edge starting vertex, edge ending vertexes).
> >
> > For example vertex 1 has edges: (1, 2), (1, 3), (1, 4), then its input
> > cell has the following representation: (3, 1, 2, 3, 4). Cell length
> > vary dependent on the cell's degree, or the number of edges which is
> > incident on the cell.
>
> Whoof, that's a clumsy representation! Next time, consider using a
> more natural representation, such as "Each vertex has a list of
> neighbors. For example, vertex 1 has neighbors {2,3,4}."
>
> > Here is new full algorithm to get minimum vertex cover:
> > 1. Count =3D 0.
> > 2. If input cell is empty, algorithm ends, otherwise
> > Sort the input cell serials based on count in increasing order.
>
> What are the "input cell serials"? I'm guessing you mean to sort the
> cells in increasing order by degree, i.e., the cells with lower degree
> come first in the list. Okay, but let me know if I'm wrong.
>
> > 3. for all vertexes with edge count =3D 1, do following:
> > a. Set original starting vertex;
>
> What?
>
> > b. Count++;
> > c. Print out its edge ending vertex #; (only one)
> > d. Delete its input cell;
> > e. In the edge ending vertex cell, do the followings:
> > a. delete the original starting vertex in edge ending
> > vertexes area;
>
> What?
>
> > b. edge count is decreased by 1;
> > c. if edge count =3D 1, set current ending vertex as new
> > original starting vertex and go to b.
> > d. if edge count =3D 0, delete the cell;
> > 4. If input cell is empty, algorithm ends, otherwise
> > sort the input cell serials based on count in decreasing order.
>
> What? What is the "input cell"? What is an "empty" cell --- is ()
> the only empty cell, or could (0, 5) be considered empty too?
>
> > 5. If there is only one cell that has the largest degree, select the
> > cell
> > and go to 6. If there are more than one cell that have the equal
> > largest degree, select the cell that has not been the end vertex
> > of the last selected cell with the largest degree, or select any of
> > them
> > if all of them have have been the end vertexes of last selected cell
>
> What? What?
>
> (snip much more gibberish)
>
> > Manually I tried more than 20 graphs and get the right answers for
> > every graph.
>
> Good for you.
>
> > Do you have any smart tips?
>
> Yes. Stop trying to find a polynomial algorithm for minimum vertex
> cover until you've read at least one existing (non-polynomial) algorithm
> and understand how it works. Also, try to write in plain English, or,
> failing that, some common programming language.
>
> > If you can find a graph that fails the algorithm, please let me know.
>
> Yes, I can. So now you know.
>
> -Arthur
Hi Arthur,
I cannot read the page. Can you please post the page on the group or
send me an email?
My email address is wtxwtx at gmail dot com (without space).
I don't know if my algorithm is the same as the one you mentioned.
Actually I checked my algorithm with more than 20 hand-drawn graphs and
all results generated are the minimum vertex cover, no exception!!!
Otherwise I couldn't publish my 2nd version so quickly. If another
error is found, I can also quickly change my design to correct the
error without destroying the full design.
The key point is:
1=2E First delete all claws until there are no any claws; (Claw is a
vertex of degree 1).
2=2E Next delete the vertex with largest degree and mark its neighbors to
keep them from being selected next time unless next time all vertexes
that have the largest degree are its neighbors. Later if a vertex's
edge is deleted, the vertex's neighbor mark should be deleted too if
any.
3=2E Repeat 1. and 2. until all input cells are deleted.
I will start writing a program in C and write some programs to generate
random graphs to check if there are any violations:
1=2E Randomly generate a graph;
2=2E Generate its minimum vertex cover, m=3D |V'| by my program.
3=2E Check C(n, m-1) choices to see if any of them meets the minimum
vertex cover.
I have "An introduction to Algorithm" written by Thomas H. Cormen etc.
It has a problem 35.1-3:
Professor Nixon proposes the following heuristic to solve the
vertex-cover problem. Repeatedly select a vertex of highest degree, and
remove all of its incident edges. Give an example to show that the
professor's heuristic doesn't not have an approximation ratio of 2.
(Hint: Try a bipartite graph with vertexes of uniform degree on the
left and vertexes of varying degree on the right. )
That is exactly what I suggested in my first version. But with the
problem exposed, I changed my strategy to delete any claws first, then
do the selection.
If you can post a graph that fails my algorithm, it will be great!!!
Thank you.
Weng
Article: 109384Thank you all. I haven't tried it yet, but it must be the solution. Will let you know when the problem is fixed. Lathi Bob Perlman wrote: > On 25 Sep 2006 19:23:08 -0700, Lathi.Tan@gmail.com wrote: > > >Peter, > > > >It's great to know that. I've never heard of this. Can you give me more > >information about the first case(links, examples)? I am thinking about > >adding a flip-flop to all input signals but shall I used a clock edge > >to synchronize them different from those flip-flops in the > >statemachine? > > I have an article on my site called, appropriately enough, > "Synchronizing FSM Inputs." > > http://www.cambriandesign.com/2006/02/synchronizing-fsm-inputs.html > > Bob Perlman > Cambrian Design Works > http://www.cambriandesign.comArticle: 109385
Weng Tianxiang wrote: ... > The key point is: > 1. First delete all claws until there are no any claws; (Claw is a > vertex of degree 1). > 2. Next delete the vertex with largest degree and mark its neighbors to > keep them from being selected next time unless next time all vertexes > that have the largest degree are its neighbors. Later if a vertex's > edge is deleted, the vertex's neighbor mark should be deleted too if > any. > 3. Repeat 1. and 2. until all input cells are deleted. At some stages in all this deleting, you presumably tag some vertices as being members of the resulting cover. Could you restate the algorithm making it clear which they are? Thanks, PatriciaArticle: 109386
Thanks a lot.Thats more than enough. markus wrote: > Hi Vits, > > I tested the I2C master with the testbench. The signals generated were > correct. I also implemented the cores in an FPGA. I've managed to use > the core to communicate with slave devices using FPGA as the master. > So, I do believe that the I2C master is correct. > > I didn't use any microprocessor or microcontroller to control the I2C > master. Instead, I created a state machine that takes in my > instructions and decode it for the I2C master to process. The state > machine also waits for the nack/ack signals that the I2C master > receives from the slave (this, I noticed, took the longest in > hardware). > > Hope this helps. > > -Markus > > > vits wrote: > > Hi markus, > > O ya ,that has helped me a lot. actually i tried to test with a eeprom > > slave. > > But the test is not giving the correct results.may be there may be > > something wrong with the > > eeprom model.i got it from net. > > vitsArticle: 109387
On Mon, 25 Sep 2006 22:26:56 -0400, Ray Andraka <ray@andraka.com> wrote: >John Larkin wrote: > >> >> >> An opamp-based allpass 90 degree phase shifter is pretty simple; 8 >> opamp sections, 8 caps, 24 resistors gives nice quadrature signals >> over the voice range. And simulating a R-C section in an FPGA is >> trivial. So it seems to me that one could do a nice Hilbert with a >> fairly small amount of FPGA resources by just mimicing the opamp >> circuit in discrete time. That would be a lot smaller than a FIR >> implementation. >> >> Anybody done it this way? >> >> John >> > >That's an IIR implementation. Generally speaking, IIR filters do not >have the phase linearity required by many of the modern modulation >schemes. They are fine for AM/FM, but when you start dealing with phase >modulation, the non-linearity can make it extremely difficult to >demodulate the signal. Maybe so, but my trusty old Williams filter book has, for a 10-element opamp-based allpass network, 26:1 frequency range, 0.007 degree error 57:1, 0.026 286:1, 0.21 1146:1, 0.66 which look pretty good. And a digital implementation should nail the pole/zero locations exactly. I do lowpass filters this way some times... just design an active analog filter, and simulate it digitally. JohnArticle: 109388
Handy link for this entire thread: http://groups.google.com/group/comp.arch.fpga/browse_thread/thread/6d594b2ab04beb4b/e39055a323c18cd6#e39055a323c18cd6 Hi KJ, Thanks for your information and moral support. About ModelSim not seeming to work, I think I was just tired. I wasn't expanding the waveform window pane to look at the whole view. Without doing that, I was just looking at the initial "offset" time of 100 ns in which nothing was happening. It's also possible I was tired and not remembering that I have to wait for the simulation to complete; I recall seeing the final output was 'U' - Uninitialized, and that may be the reason. Next time I should record screenshots so that I can prove I was not hallucinating, or, alternatively, while I'm at it, give me time to realize what is going on. "input setup/hold time" is the time required before a clock edge to setup and hold an input signal so that the receiving FF will successfully register it, is that right? I am using the "Test Bench WaveForm" GUI feature (Xilinx ISE ver 8.2.03i, now) and in the clock timing input window that comes up automatically when I create a tbw file, there are settings for "Input setup time" and "output valid delay", that I have to fill in. "Input setup time" is the time duration that the testbench will place my input signal transitions before its clock edges, is that right? For example, I have a "load" pulse that I draw in the GUI and the testbench will make sure to activate its edges 1ns before the matching clock edges if I set "input setup time" to 1ns, is that right? Does "output valid delay" mean the time duration after a clock edge at which output data becomes valid? If so, I don't understand what that tells the testbench to do. Since that seems to be dependent upon the device under test and yet it is a testbench entry parameter, I am confused as to the meaning of that and must be understanding it wrong. So I have to make sure that my "Input setup time" that I specify has got to satisfy all input setup/hold times required by the mapper timing report, is that right? What do I look at to specify the "output valid delay" (it must be some kind of data in the timing report. I'll take a look)? Does that mean I'm telling the testbench not to "look" at data before that time period after a clock pulse just for reporting and display purposes? I am synthesizing and translating and getting correct operation in simulation but then mapping and getting incorrect operation -- I have an initial load into a submodule of 128 bits and a simple subsequent output from the submodule of that separated into its four 32-bit words. In that, post-map, the lower three bytes of the second register are being duplicated into the third register, both in the signals used in the calling module and in the signals used in the submodule. It looks like logic is getting optimized away incorrectly, but could that really be happening by violating setup and hold times in the testbench? I am getting seven warnings of the following type from ModelSim when it does post-map simulation: # ** Warning: /X_SFF SETUP High VIOLATION ON CE WITH RESPECT TO CLK; # Expected := 0.74 ns; Observed := 0.583 ns; At : 291.975 ns # Time: 291975 ps Iteration: 3 Instance: /user_logic_tb/uut/slv_reg0_7 Is that just a slight difference as compared to the behavioral simulation? I think that the simulator compares results, is that right? To clarify what was meant by levels of logic, here is what the Xilinx tech support engineer wrote: ----------------------------- I looked at your code and I have some suggestions for you. You have registered your design, but you haven't pipelined the design which will more or less fix the issue you are having. What you did was place a register on the output, but the output is not being optimized, the combinational logic in-between is. This is what needs to be registered. In one example of your code you have 4 logic levels. w2(31 downto 24) <= wsav0(31 downto 24) xor wsav2(31 downto 24) xor wsav1(31 downto 24) xor subwordsav(31 downto 24) xor rconsav; In a fully pipelined design, you would only have one logic level per register. Meaning you will xor two signals, register it and then xor it with the next, register it and so on. This should fix your problem. Map is optimizing all your combinational logic in look-up tables (LUTs) and its removing the duplicate XOR gates. Placing the registers between the logic levels will stop that. In regards to your other questions, due to the tools behaving correctly [THAT HAS NOT BEEN ESTABLISHED], this has become a design issue and no longer a support issue. Unfortunately, the technical support team doesn't have the resources to help you further with your case. We do have other options available though. If you go to the Design and Education Services page (linked below) there are a couple of options in which you can get help. http://www.xilinx.com/support/gsd/ We have the Titanium Engineering group as well as Xilinx Design Services. This is in addition to possible help from the local FAE. I'm sorry I am no longer able to help you with your issues, but I hope my information has pointed you in the right direction toward solving your problem. I will go ahead and close this case; if you have any other support issues please open another Webcase and our team will be happy to assist you. ----------------------------- I did the above suggestion and my job of combining only pairs of signals at a time at alternate clock edges was a work of art, but it produced the exact same results. I have produced screenshots of the simulations that show correct operation in behavioral and the flaw in post-map and sent that to Xilinx. The way I worded it was to ask for the correct VHDL coding style to prevent that kind of optimization and I complained about undocumented mapper coding requirements. So now the problem doesn't look like VHDL coding style any more. A while ago I removed my one boolean signal and replaced it with std_logic that I can test in "if" statements just as well, so I haven't had anything but std_logic in my design during the last couple of weeks or so. I'm getting back to Xilinx and I'll try your approach of getting them to explain what is going on, use your wording, and try not to accept anything less than working with me until the issue is solved. What is that post-map design file that I can look at? I do have six unconnected signals being reported as nets that have no load in the map report, but the FAE (Field Application Engineer) says he never has any problems with that type of thing. However, he agrees that it wouldn't hurt to look at the "Technology Schematic", produced post-translate, identify those nets that map is complaining about and see if they are actually intended to have loads (I thought everything in my design is connected up). That's what I'm going to do next, now that I've removed a bunch of VHDL code that doesn't change anything and just adds complexity. Best regards, -JamesArticle: 109389
Handy link for this entire thread: http://groups.google.com/group/comp.arch.fpga/browse_thread/thread/6d594b2ab04beb4b/e39055a323c18cd6#e39055a323c18cd6 Here are the ISE project settings that I changed from the defaults: Synthesize properties: "Keep Hierarchy" on. (Left "Equivalent Register Removal" on). Translate properties: "Preserve Hierarchy on Sub Module" on. Mapper: "Trim unconnected signals" off (left "Allow logic opt. across hierarchy" off). Opt. strategy: speed Generate detailed Map report By default, equivalent register removal is on, so I had to turn on global optimization mode (-global_opt on) in order to turn it off. Trim unconnected signals (-u) - I had to turn it on, according to the mapper output, as long as I use global optimization mode. (-u is known as "(Do Not Remove Unused Logic)" on pg 141 of dev.pdf ver 8.2i.) -r map option (no register ordering)Article: 109390
Handy link for this entire thread: http://groups.google.com/group/comp.arch.fpga/browse_thread/thread/6d594b2ab04beb4b/e39055a323c18cd6#e39055a323c18cd6 Here are the definitions: >From the installed help files at C:\Xilinx\doc\usenglish\help\iseguide\mergedProjects\xsim\html\xs_hidd_initialize_timing_dialog.htm The Input Setup Time is the minimum amount of time between the arrival of an input pulse and a clock pulse for that input pulse to be considered valid. The Output Valid Delay is the maximum amount of time allowed for an output to change states for it to be considered valid when used in a self-checking test bench. The Test Bench Waveform Editor can write out a self-checking test bench. For more information see Generating Expected Simulation Results. Time units are determined by the Time Scale drop-down menu at the lower right.Article: 109391
Hi Duth, thank you for your help. After exchanging the ld-files (/usr/bin --> $XILINX/gnu ..) the simulator runs. <<"DUTH wrote:"No worries. I checked with our ISE Simulator team and they said that our ISE 9.1i could potentially work, as we had to change some of the ld libraries to be Fedora 5.0 compatible as well. The solution is to remove the version of ld which ships with ISIM and replace it with the installed system ld. Hence in ISE install area, we need to rename the following two copies of ld to something like ld.old ./gnu/gcc/3.2.3/lin/i686-pc-linux-gnu/bin/ld ./gnu/gcc/3.2.3/lin/bin/ld >>Article: 109392
Weng Tianxiang wrote:
> Arthur J. O'Dwyer wrote:
>
>>On Sun, 24 Sep 2006, Weng Tianxiang wrote:
>>
>>>eKo1 wrote:
>>>
>>>>Let V' be a subset of V. V' is a vertex cover if it satisfies the
>>>>following test:
>>>>
>>>>E' = Ø
>>>>for each v in V'
>>>> for each edge e in E
>>>> if v is incident to e then
>>>> add e to E'
>>>> end if
>>>> end for
>>>>end for
>>>>if |E| = |E'| then
>>>> return true // V' is a vertex cover
>>>>end if
>>>>return false
>>>>
>>>>Would this be correct?
>>>
>>>Hi eKo1,
>>>The algorithm you mentioned for a vertex cover is right.
>>
>> Yes, that's right. (And it suggests a trivial brute-force algorithm
>>to find a minimum vertex cover:
>>
>> M = V
>> for each V' in V
>> if (V' is a vertex cover of G) then
>> if |V'| < |M| then
>> M = V
>> end if
>> end if
>> end for
>> return M
>>
>>Now M is a minimum vertex cover.)
>>
>>
>>
>>>Here is my full new algorithm that can get minimum vertex cover:
>>>
>>>To make discussion simpler, we assume that every vertex has a positive
>>>integer, starting with 1 to n and input cells have the following
>>>structure:
>>>(edge count, edge starting vertex, edge ending vertexes).
>>>
>>>For example vertex 1 has edges: (1, 2), (1, 3), (1, 4), then its input
>>>cell has the following representation: (3, 1, 2, 3, 4). Cell length
>>>vary dependent on the cell's degree, or the number of edges which is
>>>incident on the cell.
>>
>> Whoof, that's a clumsy representation! Next time, consider using a
>>more natural representation, such as "Each vertex has a list of
>>neighbors. For example, vertex 1 has neighbors {2,3,4}."
>>
>>
>>>Here is new full algorithm to get minimum vertex cover:
>>>1. Count = 0.
>>>2. If input cell is empty, algorithm ends, otherwise
>>> Sort the input cell serials based on count in increasing order.
>>
>> What are the "input cell serials"? I'm guessing you mean to sort the
>>cells in increasing order by degree, i.e., the cells with lower degree
>>come first in the list. Okay, but let me know if I'm wrong.
>>
>>
>>>3. for all vertexes with edge count = 1, do following:
>>> a. Set original starting vertex;
>>
>> What?
>>
>>
>>> b. Count++;
>>> c. Print out its edge ending vertex #; (only one)
>>> d. Delete its input cell;
>>> e. In the edge ending vertex cell, do the followings:
>>> a. delete the original starting vertex in edge ending
>>> vertexes area;
>>
>> What?
>>
>>
>>> b. edge count is decreased by 1;
>>> c. if edge count = 1, set current ending vertex as new
>>> original starting vertex and go to b.
>>> d. if edge count = 0, delete the cell;
>>>4. If input cell is empty, algorithm ends, otherwise
>>> sort the input cell serials based on count in decreasing order.
>>
>> What? What is the "input cell"? What is an "empty" cell --- is ()
>>the only empty cell, or could (0, 5) be considered empty too?
>>
>>
>>>5. If there is only one cell that has the largest degree, select the
>>>cell
>>> and go to 6. If there are more than one cell that have the equal
>>> largest degree, select the cell that has not been the end vertex
>>> of the last selected cell with the largest degree, or select any of
>>>them
>>> if all of them have have been the end vertexes of last selected cell
>>
>> What? What?
>>
>>(snip much more gibberish)
>>
>>
>>>Manually I tried more than 20 graphs and get the right answers for
>>>every graph.
>>
>> Good for you.
>>
>>
>>>Do you have any smart tips?
>>
>> Yes. Stop trying to find a polynomial algorithm for minimum vertex
>>cover until you've read at least one existing (non-polynomial) algorithm
>>and understand how it works. Also, try to write in plain English, or,
>>failing that, some common programming language.
>>
>>
>>>If you can find a graph that fails the algorithm, please let me know.
>>
>> Yes, I can. So now you know.
>>
>>-Arthur
>
>
> Hi Arthur,
> I cannot read the page. Can you please post the page on the group or
> send me an email?
>
> My email address is wtxwtx at gmail dot com (without space).
>
> I don't know if my algorithm is the same as the one you mentioned.
>
> Actually I checked my algorithm with more than 20 hand-drawn graphs and
> all results generated are the minimum vertex cover, no exception!!!
>
> Otherwise I couldn't publish my 2nd version so quickly. If another
> error is found, I can also quickly change my design to correct the
> error without destroying the full design.
>
> The key point is:
> 1. First delete all claws until there are no any claws; (Claw is a
> vertex of degree 1).
> 2. Next delete the vertex with largest degree and mark its neighbors to
> keep them from being selected next time unless next time all vertexes
> that have the largest degree are its neighbors. Later if a vertex's
> edge is deleted, the vertex's neighbor mark should be deleted too if
> any.
> 3. Repeat 1. and 2. until all input cells are deleted.
>
> I will start writing a program in C and write some programs to generate
> random graphs to check if there are any violations:
> 1. Randomly generate a graph;
> 2. Generate its minimum vertex cover, m= |V'| by my program.
> 3. Check C(n, m-1) choices to see if any of them meets the minimum
> vertex cover.
>
> I have "An introduction to Algorithm" written by Thomas H. Cormen etc.
> It has a problem 35.1-3:
> Professor Nixon proposes the following heuristic to solve the
> vertex-cover problem. Repeatedly select a vertex of highest degree, and
> remove all of its incident edges. Give an example to show that the
> professor's heuristic doesn't not have an approximation ratio of 2.
> (Hint: Try a bipartite graph with vertexes of uniform degree on the
> left and vertexes of varying degree on the right. )
>
> That is exactly what I suggested in my first version. But with the
> problem exposed, I changed my strategy to delete any claws first, then
> do the selection.
>
> If you can post a graph that fails my algorithm, it will be great!!!
>
> Thank you.
>
> Weng
>
Weng,
Did you mean to post this to comp.arch.fpga?
It's an interesting problem and all, but...?
-Dave
--
David Ashley http://www.xdr.com/dash
Embedded linux, device drivers, system architecture
Article: 109393james7uw@yahoo.ca wrote: Handy link for this entire thread: http://groups.google.com/group/comp.arch.fpga/browse_thread/thread/6d594b2ab04beb4b/e39055a323c18cd6#e39055a323c18cd6 Mapper warnings are: WARNING:LIT:243 - Logical network u0/N0 has no load. WARNING:LIT:243 - Logical network u0/N1 has no load. WARNING:LIT:243 - Logical network u0/r0/N01 has no load. WARNING:LIT:243 - Logical network u0/r0/N11 has no load. WARNING:LIT:243 - Logical network Bus2IP_Clk_BUFGP/N2 has no load. WARNING:LIT:243 - Logical network Bus2IP_Clk_BUFGP/N3 has no load. Can't find these in the technology schematic (post-translate). There is a u0/r0/N0 and u0/r0/N1 and a u0/r0/N21 and u0/r0/N31 in the Technology schematic. Many u0/Ns followed by three digit numbers. Nothing named "N" anything in the RTL schematic. Saw Bus2IP_Clk_BUFGP, but no /N2 or /N3 (nothing after Bus2IP_Clk_BUFGP). I could try a new project before doing map and see if map is going back and removing those. Did that. Made a new project and did only up to synthesize and translate. There is N0 and N1 in the top level in the Technology schematic. There is a u0/r0/N0 and u0/r0/N1 and u0/r0/N31. Saw Bus2IP_Clk_BUFGP, but no /N2 or /N3 (nothing after Bus2IP_Clk_BUFGP). Plenty of N's at the top level. Map *does* seem to be going back and adding to or changing the Technology schematic, but not taking away the above, which never seemed to be there. Not good.Article: 109394
Hi All, currently I'm working with the Altera QuartusII 6.0sp1 and I can't find a way to find out ALL the instances of a given module (of which I can see the corresponding VHDL file in the Project Navigator pane) through my whole design, i.e. without having to browse all the design blocks one-by-one to look if that module is instantiated. It seems a quite simple task, but I can't manage how to do it... Could someone give me some hints? Thank you in advance. Regards, ClaudioArticle: 109395
Hi, I'm investigating the possibility to replace an Spartan-2E (xc2s400e) with an Spartan-3E (xc3s1200e) device on a PCB. The core voltage drops from 1.8V to 1.2V. Has anyone experience regarding the footprint differences (easy/hard/impossible to adapt) and any other differences which must be taken into account? Regards, StefanArticle: 109396
Use the Hierarchy tab in the Project Navigator pane. Totti10@hotmail.com wrote: > Hi All, > currently I'm working with the Altera QuartusII 6.0sp1 and I can't find > a way to find out ALL the instances of a given module (of which I can > see the corresponding VHDL file in the Project Navigator pane) through > my whole design, i.e. without having to browse all the design blocks > one-by-one to look if that module is instantiated. > It seems a quite simple task, but I can't manage how to do it... > Could someone give me some hints? Thank you in advance. > > Regards, > ClaudioArticle: 109397
Quote( > IMHO implementing the opencores PCI bridge and writing some software to > talk to back-end peripherals is quite nicely weighted as a final-year > design project. It's not as if you're implementing the bridge yourself. (Unquote) No, Its actually a software/hardware distributed solution for OC-48 media gateway controller (A research project won from CISCO). We have implemented a software part and hardware part. Now we need a talking interface. One thing more do any one of you guys have PCI core without wishbone, as I think I am supposed to implement wishbone master to talk with wishbone slave and wishbone slave to talk with wishbone master (Please correct me if I am wrong). Thanks alot for your valuable opionion, I am trying hard with the testbench. I need test bench because first we need to run simulation after integrating PCI core with our logic. So that things could run smoothly on FPGA. with best regards and a bundle of thanks AdnanArticle: 109398
Antti wrote: > David R Brooks schrieb: > >> The Virtex-4 data sheet states that the BSCAN module can support 4 >> user-data registers. >> >> However there is an Errata sheet which states that early (ES) parts only >> supported one register. >> >> The "Virtex-4 Libraries Guide for HDL Designs" shows a BSCAN_VIRTEX4 >> element supporting only one user register (although it mentions USER1 & >> USER2 instructions, suggesting two registers). >> >> The library unisim_VCOMP.vhd shows: >> >> component BSCAN_VIRTEX -- This drives two user registers >> port >> ( >> DRCK1 : out std_ulogic := 'H'; >> DRCK2 : out std_ulogic := 'H'; >> RESET : out std_ulogic := 'H'; >> SEL1 : out std_ulogic := 'L'; >> SEL2 : out std_ulogic := 'L'; >> SHIFT : out std_ulogic := 'L'; >> TDI : out std_ulogic := 'L'; >> UPDATE : out std_ulogic := 'L'; >> TDO1 : in std_ulogic := 'X'; >> TDO2 : in std_ulogic := 'X' >> ); >> end component; >> >> component BSCAN_VIRTEX4 -- This drives one user register >> generic >> ( >> JTAG_CHAIN : integer := 1 >> ); >> port >> ( >> CAPTURE : out std_ulogic := 'H'; >> DRCK : out std_ulogic := 'H'; >> RESET : out std_ulogic := 'H'; >> SEL : out std_ulogic := 'L'; >> SHIFT : out std_ulogic := 'L'; >> TDI : out std_ulogic := 'L'; >> UPDATE : out std_ulogic := 'L'; >> TDO : in std_ulogic := 'X' >> ); >> end component; >> >> >> >> So I am confused :) >> Can anyone tell me just how many JTAG user registers V4 does support? > > there are 4 > but the way of using them is different then other families > if for others there was one BSCAN primitive that allowed > access to two user instructions, then V4 has > > 1 primitive > where >> JTAG_CHAIN : integer := 1 > > chain number selects which USERx instruction the bscan is linked to > > so to access all 4 USERx you instantiate 4 times the same prim > with different generic for chain num > > now as of some V4-ES, only chain 1 is useable, others dont work > so they are probably there but can not be used. > > notice that on some V4-ES RESET output of the BSCAN has wrong > polarity that also may need special handling. > > the 1 chain only issue caused most problems with MDM in the v4-lx25es > where defautl MDM was using non-working chain 2, so there was special > workaround to set MDM ip to use chain 1 and have matching XMD also > > Antti > http://www.microfpga.com > Many thanks!Article: 109399
Patricia Shanahan wrote:
> Weng Tianxiang wrote:
> ...
> > The key point is:
> > 1. First delete all claws until there are no any claws; (Claw is a
> > vertex of degree 1).
> > 2. Next delete the vertex with largest degree and mark its neighbors to
> > keep them from being selected next time unless next time all vertexes
> > that have the largest degree are its neighbors. Later if a vertex's
> > edge is deleted, the vertex's neighbor mark should be deleted too if
> > any.
> > 3. Repeat 1. and 2. until all input cells are deleted.
>
> At some stages in all this deleting, you presumably tag some vertices as
> being members of the resulting cover. Could you restate the algorithm
> making it clear which they are?
>
> Thanks,
>
> Patricia
Hi Patricia,
Yes.
1. First delete all claws until there are no any claws; (Claw is a
vertex of degree 1).
output claws's only neighbor vertexes as members of the minimum vertex
cover;
1--2--3--4--5--6--7
|
8
|
9
Vertex 1 is a claw and deleted, output vertex 2 because it is vertex
1's neighbor, and vertex 2 is deleted. When one edge of vertex 2 is
deleted, vertex 3 become a claw and is deleted, then output vertex 4,
vertex 3's neighbor; vertex 8 become a claw and is deleted, output
vertex 9; vertex 5 is a claw, output vertex 6.
So the minimum vertex cover is:
2, 4, 6, 9. |V'| = 4.
2. Next delete the vertex with the largest degree, output the vertex as
a member of the minimum vertex cover and mark its neighbors to keep
them from being selected next time unless next time all vertexes that
have the largest degree are its neighbors. Later if a vertex's edge is
deleted, the vertex's neighbor mark should be deleted too if any.
(5, 1, 2, 3, 4, 5, 6)
(5, 2, 1, 3, 5, 6, 7)
(5, 3, 1, 2, 4, 5, 6)
Select any one of above 3 vertexes, delete it, it become (when the
first is selected):
(4, 2, 3, 5, 6, 7)+
(4, 3, 2, 4, 5, 6)+
'+' means it is a neighbor of the deleted vertex with the largest
degree. On next selectiono, If one of vertexes of the largest degree
has a neighbor mark, it must not selected unless all vertexes of the
largest degree are the neighbors of deleted vertexes of the largest
degree.
Now any of the two above vertexes can be deleted and output because
both are the neighbors.
3. Repeat 1. and 2. until all input cells are deleted.
If you can list a graph that fails my algorithm, you beat me.
Thank you.
Weng
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