how to find min and 2nd min and its positon in a row

[nitin sapre]

I need to find Postions of minimun and 2nd minimum in a row excluding zero





for example



[ 0 -3 2 1 5 8 ] min is 1 and 2nd min is 2 and position of minimum is 3

can anyone please help me to do it in verilog?

 

[Kevin Neilson]

On Thursday, January 30, 2020 at 2:01:00 AM UTC-7, nitin sapre wrote:

I need to find Postions of minimun and 2nd minimum in a row excluding zero





for example



[ 0 -3 2 1 5 8 ] min is 1 and 2nd min is 2 and position of minimum is 3

can anyone please help me to do it in verilog?

This is all very dependent on how many clock cycles you have. If you have 6 clock cycles and can do this serially, you'd use a software algorithm: Start with two holding registers, each initialized with infinity, and then look at each sample, one at a time, and if it is smaller than either of the two minimum holding registers, replace one of the values.

If you have to do full-parallel, this becomes more difficult. Finding the minimum requires a binary tree; the location as well as the value is passed through each node of the tree. I had to create such a structure recently.

Finding the second-smallest value is more difficult in a full-parallel situation. You might look at the bitonic sort; this would sort all input values. You could just use the minimum two values and let the synthesizer prune the rest of the logic. I'm not sure if this is optimal, but it's probably close.

 

[Rick C]

On Saturday, February 8, 2020 at 6:56:36 PM UTC-5, Kevin Neilson wrote:

On Thursday, January 30, 2020 at 2:01:00 AM UTC-7, nitin sapre wrote:
I need to find Postions of minimun and 2nd minimum in a row excluding zero





for example



[ 0 -3 2 1 5 8 ] min is 1 and 2nd min is 2 and position of minimum is 3

can anyone please help me to do it in verilog?

This is all very dependent on how many clock cycles you have. If you have 6 clock cycles and can do this serially, you'd use a software algorithm: Start with two holding registers, each initialized with infinity, and then look at each sample, one at a time, and if it is smaller than either of the two minimum holding registers, replace one of the values.

If you have to do full-parallel, this becomes more difficult. Finding the minimum requires a binary tree; the location as well as the value is passed through each node of the tree. I had to create such a structure recently.

I don't know that it has to be a binary tree. In fact, a tree "feels" complex to me for such a simple problem. A more simple way to code this is a linear arrangement of compares. So a simple loop will generate the logic required. The only question is whether this is in a clocked process or a combinatorial process. I'm not conversant in Verilog and am thinking in VHDL, so please correct me if there is no equivalent in Verilog.


> Finding the second-smallest value is more difficult in a full-parallel situation. You might look at the bitonic sort; this would sort all input values. You could just use the minimum two values and let the synthesizer prune the rest of the logic. I'm not sure if this is optimal, but it's probably close.

Second smallest can be found by simply saving the old value of the smallest each time it is updated. The case of the smallest being the first item in the list must be dealt with however as there would be nothing in the second result if the first result is never updated. That can be handled by a second compare on each sample with the second result which provides a value for the second result if the first result is never updated.

Initial values would be the first item to the first result register and the second item to the second result register. The compares start with the second item in the list. The first result register is updated any time the "current" item being compared is smaller than the contents of the first result register. The second result register is updated to the current list item any time the current list item is smaller than the second result... until there is an update to the first result register. Then the first result register is saved in the second result and the second result compares are no longer done.

Hard to describe, but easier to code. One pass, maximum two compares per item other than the first.

--

Rick C.

- Get 1,000 miles of free Supercharging
- Tesla referral code - https://ts.la/richard11209

 

[Kevin Neilson]

I don't know that it has to be a binary tree. In fact, a tree "feels" complex to me for such a simple problem. A more simple way to code this is a linear arrangement of compares. So a simple loop will generate the logic required. The only question is whether this is in a clocked process or a combinatorial process. I'm not conversant in Verilog and am thinking in VHDL, so please correct me if there is no equivalent in Verilog.

If latency isn't a problem, then you could use a linear arrangement. For a recent design I had to find the minimum of 64 values (on every clock cycle), so had I used a linear arrangement that would have a delay of 64 compares, but if you use a binary tree it's a delay of log2(64)=6 compares. I ended up with a pipeline stage in the middle, so I did 3 levels of comparison in the first cycle and 3 levels in the second.

 

[Rick C]

On Sunday, February 9, 2020 at 12:57:44 PM UTC-5, Kevin Neilson wrote:

I don't know that it has to be a binary tree. In fact, a tree "feels" complex to me for such a simple problem. A more simple way to code this is a linear arrangement of compares. So a simple loop will generate the logic required. The only question is whether this is in a clocked process or a combinatorial process. I'm not conversant in Verilog and am thinking in VHDL, so please correct me if there is no equivalent in Verilog.

If latency isn't a problem, then you could use a linear arrangement. For a recent design I had to find the minimum of 64 values (on every clock cycle), so had I used a linear arrangement that would have a delay of 64 compares, but if you use a binary tree it's a delay of log2(64)=6 compares. I ended up with a pipeline stage in the middle, so I did 3 levels of comparison in the first cycle and 3 levels in the second.

Latency is a design specification which we don't have. This is pretty clearly a homework assignment where simplicity is paramount since if you don't get it right, you don't get a second chance to fix the problem. So I would code the linear solution.

The only specification is an example with just six samples which is five compares with a linear solution (for the first minimum) and three compares with a tree. The real issue is how do you find the second minimum with the tree, a second separate tree with the first minimum removed? That makes six compares. In the linear tree finding the second minimum adds no delay in compares. At the end of the algorithm and 5 compare times both answers will be known.

There are many applications where the delay time of finding a solution to a problem is not the overriding factor in choosing a solution algorithm.

--

Rick C.

+ Get 1,000 miles of free Supercharging
+ Tesla referral code - https://ts.la/richard11209