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.

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 follo=
wing content:
>
> =A0I 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 cyc=
les. The question is find the maximum number and second maximum number in t=
his array after 10 clock cycle.
> =A0Anyone 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

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

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 

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

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 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.=20

Andy

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

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