Ask about finding maximum and second's maximum number in array is given.

I am starting to study VHDL. Now, I have to do an exercise with the following content:

I have to define an array of 10 elements ( 8 bit range) ([3,4,2,8,9,0,1,5,7,6] for example). And 10 elements were imported to within 10 clock cycles. The question is find the maximum number and second maximum number in this array after 10 clock cycle. Anyone help to show me the method to solve it using VHDL ?

Thank you.

Reply to
phanhuyich
Loading thread data ...

wing content:

1,5,7,6] for example). And 10 elements were imported to within 10 clock cyc les. The question is find the maximum number and second maximum number in t his array after 10 clock cycle.

No problem. Just write down your sollution to that problem in "not VHDL". Then ask what part of the algorithm is hard for you transfer in VHDL and why so we can help.

HInt it helps to think about the RTL and draw a picture about how the data flow might be than it is easy to write it down in VHDL.

regards Thomas

Reply to
Thomas Stanka

content:

([3,4,2,8,9,0,1,5,7,6] for example). And 10 elements were imported to within 10 clock cycles. The question is find the maximum number and second maximum number in this array after 10 clock cycle.

I often try to think of exercises like this in a completely different setting. For example, suppose you have ten ordinary playing cards from a standard deck of 52. You agree that there is a standard order of these cards where the lowest for this exercise is Ace of Clubs, then Ace of Diamonds, Ace of Hearts, Ace of Spades, Two of Clubs, Two of Diamonds, . . . with King of Spades being highest.

Now you're going to flip one card at a time (this is the same way you get your input, one item per clock cycle). With each flip you get to make one decision. For example if you only cared about the highest card of the ten, you could have a single stack where you place the new card if it is higher than the card already showing (or if the stack has no cards), and discard any card that is not higher.

Now my first thought was that you could use this same approach to find the two highest cards, but there's one case where it doesn't work - if the highest card comes out first. Then your stack will only have one card in it so you can't just dig one card down to find the second highest.

So you need to think how you'd arrange cards to be certain to know the top two at the end of the exercise. Then it's a simple matter of translating this procedure to a VHDL process.

Have fun!

--
Gabor
Reply to
Gabor

I posted that last night when the brain was foggy. I should have said that the simple algorithm won't work for finding the second highest card if the highest card comes before the second highest.

In any case you need to think of a good algorithm for finding both.

--
Gabor
Reply to
GaborSzakacs

To borrow Gabor's card game analogy...

You have two stacks, (highest and 2nd highest)

If the drawn card is same or higher than the highest stack, then

move the top card from the highest stack to the 2nd highest stack, move the drawn card to the highest stack.

else if the drawn card is same or higher than the 2nd highest stack, then

move the drawn card to the 2nd highest stack.

draw another card and repeat.

Andy

Reply to
jonesandy

They don't need to be stacks. You just need to have two holding spots (registers) and initialize them to something less than anything you will have on the input. Then on each draw of a card (or sample on the input) you compare to both spots, if the input is higher than the "highest" spot you save it there and put the old highest on the "second highest" spot. If not, but it is higher than the "second highest" you put it there.

Gabor was using a stack because he thought it would get him both the highest and the second highest with one compare operation, but it didn't work. Two compares are needed for each input.

In your approach your compare is "higher or same", why do you need to do anything if they are the same? Not that it is a big deal, but in some situations this could require extra work.

--

Rick
Reply to
rickman

You actually only need to compare most of the entries to the second highest register, if it isn't higher, than you can discard the item. Only if it is higher than the second highest, do you need to compare it to the highest to see if the new item goes into the highest or second highest. I.E.

Compare drawn card to 2nd highest stack, if not higher, discard and repeat if higher (same doesn't really matter), discard the 2nd highest stack and compare the new card to the highest stack.

if not higher, new card goes into 2nd highest stack, if higher, item in highest goes to 2nd highest, and new goes to highest.

Reply to
Richard Damon

From a SW point of view, avoiding extra comparisons when not needed is valu able. From a HW point of view, that is not necessarily so. Unless the compa risons are (or can be) at different times and reuse the same comparison log ic, there is no benefit to avoiding a comparison if it might have to be don e. The logic to decide whether a comparison needs to be done needlessly add s to the complexity of the circuit.

Andy

Reply to
jonesandy

I did not mean to imply that the implementation needed to use stacks, but t he card game usually would. In HW, only a single value ever need be retriev ed from a stack, so each stack is only one deep (a single register).

You may be right about the same or higher. The results are the same, but th is really depends on what one means by "2nd highest value": is it the secon d of the two highest values seen, or is it the second highest unique value? If I draw two kings and a deuce, is the "second highest card" a king or a deuce?

Either comparison gives the same result, since if the 2nd king failed a hig her (only) comparison with 1st highest result, it would still pass the high er comparison with the 2nd. If you wanted to find the two highest unique va lues, more work would be required.

Andy

Reply to
jonesandy

This is being done in hardware not software. Your description is sequential while the hardware is concurrent. The control logic is simple if you just code it in a simple way. Do both compares and you get two bits as a result. Then load the max and second max registers based on those two compare results.

The only fly in the ointment that I see is the initial condition. You can either initialize the two registers to values which you know will always be the min values possible, or you can have a flag for the first clock cycle that loads both registers with the first value read. I think the initial state flag would be the simplest. So the register control logic has a third input bit and of course an enable from the 10 counter.

--

Rick
Reply to
rickman

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.