Hi! I`ve got this homework and can`t find an answer (asked everyone).
max_pass circuit filters an array of 32 bits such that the blocks of bits 1 of maximum length remain on position and everything else becomes 0.
A block/set is consisted of minimum 2 bits of 1.
The circuit has to be combinational and the interface of the max_pass module is:
input array named "din" ->32bits
output array name "dout" ->32bits
The circuit has no memory. Output immediately sees any changes in input.
So, I have to implement this in Verilog, but first of all I need to find an algorithm.

Examples
Example 1
input: 01011100111111111111011100101010
output: 00000000111111111111000000000000
The maximum length of a block is 12.

Example 2
input: 00100111111001001011111100101101
output: 00000111111000000011111100000000
Two blocks of maximum length of 6.

Example 3
input: 11011011011011011011011011011011
output: 11011011011011011011011011011011
Eleven blocks of maximum length of 2.

Using Combinational Logic only!

What I`ve tried so far :
Using a MUX-DMUX circuit I can compare 2 numbers of 2 bits, let's say M,N and the function return 1 if M>N (it can be modified to return 1 if M=N=11 also ).

M=ab, N=cd.
I`m not sure how to find the maximum block.

I am in a learning process and any idea is welcome!
Thank you!

 

Try to break it down into pieces.

Let's say that you have somehow identified that bits 7 and 23 are located somewhere within the two max blocks. Could you take the input vector and a vector having those two bits set and produce the desired output vector?

If so, then you have reduced the problem down to identifying at least one bit within each max block.

 

@WBahn
Let`s assume max length of a block is M.
I think that if we take the vector having those two bits set, we have to apply AND gate with the input vector until we find first 1. Then apply OR gate for the next M bits and then repeat the process until we find next 1. Doing so, it is possible to produce desired output vector.

But how to find max length and how to identify first bit of every max block.

 

By the way, I am not sure if I can use another vector, because it says the circuit has no memory. Only combinational logic implementation.

 

By the way, I am not sure if I can use another vector, because it says the circuit has no memory. Only combinational logic implementation.

Your combinatorial circuit would filter the input to produce the second vector and then another combinatorial circuit would use both to produce the final output.

 

@WBahn
Let`s assume max length of a block is M.
I think that if we take the vector having those two bits set, we have to apply AND gate with the input vector until we find first 1. Then apply OR gate for the next M bits and then repeat the process until we find next 1. Doing so, it is possible to produce desired output vector.

But how to find max length and how to identify first bit of every max block.

Let's not get ahead of ourselves. If you think you know how to solve the first problem, then solve it and test it out. Your description above does not make me feel very comfortable that you have a viable solution to this part. Play around with a smaller problem consisting of, say, 16 bits.

Input = 0111011101101110

Now let's say that your filter produces the following

Location = 0100001000000010

Can you devise a circuit that will combine these two to yield

Output = 0111011100001110

 

Can you devise a circuit that will combine these two to yield

Output = 0111011100001110

Can you please give me a hint or a starting point?

 

You know that there will be a 1 bit in the input that aligns with the 1 bit in the Location vector. You know that you want that bit position to be a 1 in the output vector.

What about the bits adjacent to that bit? Do you want them to be a 1 or a 0? What determines the answer to that question?

 

@WBahn
I am not sure how to devise this circuit using only logic gates. I mean, adjacent bits to that bit could be 0 or 1.

 

@WBahn
I am not sure how to devise this circuit using only logic gates. I mean, adjacent bits to that bit could be 0 or 1.

And what should the output be in that bit position if that bit is a 0? What should it be if it is a 1?

 

And what should the output be in that bit position if that bit is a 0? What should it be if it is a 1?

@WBahn
If that bit is a 0 , the output should be 0 in that position, else if that bit is a 1 , the output should be 1, I get this.


To be clear, Location vector suggests with a 1 bit where the maximum block in the input vector is. This 1 bit is placed on the same position in the output vector and the other bits(in the output) are 0 . But what I don`t get is that I don't know how long is the block in order to transfer it to the output. Also this 1 bit in the location vector can indicate to the first, to the last or to any other bit in that block.

I am a bit confused, to be honest.

 

Let's assume that there is only a single bit in the location vector that is a 1 and let's further assume that it is aligned with the left-most 1 bit of the max block.

Let's say that the 1 bit in the location vector is at position 10.

We know that the output at position 12 needs to be a one regardless of anything else, right? We may have other things that say that this position in the output should be 1, but those don't matter if there is a 1 at that position in the location vector. What logical operation does that suggest?

The output in the next position (position 13) is a 1 if and only if the output in position 12 is a 1 and the input vector has a 1 in position 13. What logical operation does this imply?

The output in the next position (position 14) is a 1 if and only if the output in position 13 is a 1 and the input vector has a 1 in position 13.

Do you see how this will cascade the max block bits to the output? In essence, the bit in the location vector serves as a trigger and the bits in the input vector serve to sustain a pulse of 1 bits to the output as long as they last.

Do you see how to support multiple 1 bits in the location vector? (Hint: the above description should handle this automatically).

To handle allowing the location bits to be anywhere within the max blocks we can simply duplicate this circuit in reverse and combine the outputs (using which logic operation?). But, IF we can produce the location bits so that they are always at the left (or right) edge of a max block then this isn't necessary.

 

@WBahn
I got the idea now. But where should I start from ? It looks easy on paper. Do I have to use basic gates (&,|,^,~) or something like MUX,DMUX?

 

@WBahn
I got the idea now. But where should I start from ? It looks easy on paper. Do I have to use basic gates (&,|,^,~) or something like MUX,DMUX?

That's a question for your instructor. You can probably write it in behavioral code pretty readily, though I'm just guessing at that. If you write it structurally, then you will need to follow whatever guidelines your instructor imposes. But remember that you can write your own modules using low-level constructs and then use those higher-level modules in your implementation.

 

That's a question for your instructor. You can probably write it in behavioral code pretty readily, though I'm just guessing at that. If you write it structurally, then you will need to follow whatever guidelines your instructor imposes. But remember that you can write your own modules using low-level constructs and then use those higher-level modules in your implementation.

Definitely it is a behavioral code. Problem is I am on my own. Lab assistant doesn't even know how to solve it. He admitted. The homework was given by the course professor who does not offer instruction or any kind of advice.
The difficult part I think is to find the max block and generate location vector with a 1 at starting position of that block.
Thank you for your effort!

 

The difficult part I think is to find the max block and generate location vector with a 1 at starting position of that block.
Thank you for your effort!

Actually, I think that is probably pretty straight forward.

Take your input vector and shift it left by one. Now compare the two and see if you can't figure out a way to combine them so that it filters out any blocks of length one. Then see if you can repeat this so that you filter out any blocks of length two.

 

Actually, I think that is probably pretty straight forward.

Take your input vector and shift it left by one. Now compare the two and see if you can't figure out a way to combine them so that it filters out any blocks of length one. Then see if you can repeat this so that you filter out any blocks of length two.

I did it and it works. But how do I know when to stop shifting. I mean, to obtain location vector it is necessary to shift MaxLength-1 times I believe. That means I need to know MaxLength

 

Notice that, after each shift, there are fewer 1 bits. As soon as you step one too far all of the bits become zero. That's what you look for and use that to mux the output of the shift stage that you need into the prior circuit.