Ask about finding maximum and second's maximum number in arr

[phanhuyich]

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.

 

[Thomas Stanka]

On 18 Jun., 03:19, phanhuyich <khanhnguyent...@gmail.com> wrote:

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 ?

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

 

[Gabor]

On 6/18/2013 7:28 AM, Thomas Stanka wrote:

On 18 Jun., 03:19, phanhuyich <khanhnguyent...@gmail.com> wrote:
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 ?

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

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

 

[GaborSzakacs]

Gabor wrote:

On 6/18/2013 7:28 AM, Thomas Stanka wrote:
On 18 Jun., 03:19, phanhuyich <khanhnguyent...@gmail.com> wrote:
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 ?

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

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!

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

 

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

 

[rickman]

On 6/19/2013 11:40 AM, jonesandy@comcast.net wrote:

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.

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

 

[Richard Damon]

On 6/19/13 9:39 PM, rickman wrote:

On 6/19/2013 11:40 AM, jonesandy@comcast.net wrote:
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.

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.

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.

 

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

Andy

 

I did not mean to imply that the implementation needed to use stacks, but the card game usually would. In HW, only a single value ever need be retrieved 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 this really depends on what one means by "2nd highest value": is it the second 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 higher (only) comparison with 1st highest result, it would still pass the higher comparison with the 2nd. If you wanted to find the two highest unique values, more work would be required.

Andy

 

[rickman]

On 6/23/2013 5:10 PM, Richard Damon wrote:

On 6/19/13 9:39 PM, rickman wrote:
On 6/19/2013 11:40 AM, jonesandy@comcast.net wrote:
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.

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.

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.

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