Continue to Site

# Hey Guys One Interview Question! Beat the hell out of Me!!

Status
Not open for further replies.

#### pnnavigator0915

##### Member level 3
lsi interview question

Hey guys!..

I got this question in an Online interview..

May be I might be dumb enough not to figure it out..

But i've been thinking since 48 hours, but still I am not able to figure out!..

Qs: Design a digital circuit (only basic logic gates AND, OR, XOR, NOT, XNOR, etc.)

such that it takes in 16 bits as input and 1 bit output.

Output is HIGH only if ANY OF EXACTLY 5 bits are HIGH.

Neither 4 nor 6.. exactly 5!!!

That was the question to give me reject i guess!..

But if you can figure it out.. that'd be great..

Re: Hey Guys One Interview Question! Beat the hell out of Me

Is it possible to implement Full Adder from that gates as an intermediate step then I can use the FA as component????

If yes, so I have a solution. Else, I will continue to think about it.

Re: Hey Guys One Interview Question! Beat the hell out of Me

It could be some kind of comparator....

Re: Hey Guys One Interview Question! Beat the hell out of Me

guess dats rite....a full addder will giv u d answer....and obviously ...yes..the FA can be built from basic gates using AND,OR and XOR

Re: Hey Guys One Interview Question! Beat the hell out of Me

it can be designed very easily
1)just make the truth table with 16 inputs and one output
2)apply the condition that output is only high when 5 inputs are high otherwise low
3)now implement that truthtable using gates
thats it

Re: Hey Guys One Interview Question! Beat the hell out of Me

it can be designed very easily
1)just make the truth table with 16 inputs and one output
2)apply the condition that output is only high when 5 inputs are high otherwise low
3)now implement that truthtable using gates
thats it

dear Dudes

What has Link104 said is correct.

Its a nice way.

phutane

Re: Hey Guys One Interview Question! Beat the hell out of Me

Hi,
what links104 is only theoritically correct. I dont advice this answer, rather I would strongly advice against it, becuase it is not practically possible to do a truth table of 16 inputs. It will take ages.
So a simple solution can be add all the 16 bits and if the result is 5, the output is '1' else the output is '0'
Kr
Avi
http://www.vlsiip.com

Re: Hey Guys One Interview Question! Beat the hell out of Me

Well.. But to detect the output is five!!.. Wont we need.. more than one outputs??

Re: Hey Guys One Interview Question! Beat the hell out of Me

u design an adder circuit which adds all the 16 inputs.then the result will be in binary 101(5) provided only five 1's.then connect these three bits to an and gate,remember invert the middle bit

Re: Hey Guys One Interview Question! Beat the hell out of Me

Yes you need to somehow use adder. But you do not need a complete adder to find the exact number of ones. Here is one possible solution:

1) first you need to construct a basic 2 bit adder, using an and gate and an xor gate as shown in the figure a) (Sorry the diagram is messy )

2) use the adder to construct your logic as shown in figure b). where each square is a basic adder. Notice that for the adders in the first stage (first column from left), the weight of each sum output (i.e. S output of the basic adder) is one, the weight of each carry output ( C output of the basic adder) is two. For the adders in the second stage, the weights are 2 and 4 respectively, and for the third stage, the weights are 4 and 8.

Since you only need to know if there are exactly five ones, you do not need to construct a full adder. So you stop at the third column, and you want to make sure all the wires of weight 8 are zero otherwise you can not get 5, right? So that is how figure b is achieved.

Re: Hey Guys One Interview Question! Beat the hell out of Me

16　inputs　add　together,　and　compare　with　5,
if　equal　output　a　high　pulse.
now　design　an　adder　,and　a　comparator.

comparator must be

ya well .it is a simple 16:1 mutiplexer.

hi pnnavigator0915,

Adding all 16 bits for detection of 5 1's is ok.
but will require PISO shift register and clk to add 16 bits serially.
So the question is we should use only gates as mentioned or some sequential components can be used.
If sequentilal components can be used in design then
i have other solution which uses counters,latch and gates.

Re: Hey Guys One Interview Question! Beat the hell out of Me

amitjagtap said:
hi pnnavigator0915,

Adding all 16 bits for detection of 5 1's is ok.
but will require PISO shift register and clk to add 16 bits serially.
So the question is we should use only gates as mentioned or some sequential components can be used.
If sequentilal components can be used in design then
i have other solution which uses counters,latch and gates.

No man that's the problem.. His first condition was not to use any kind of register...
Any How I got a reject from that company May be this question was the reason. I really missed a great opportunity, to get into a Communication Giant!!..

Still i'd like to find the answer...
I guess adder can be used but once again i dont really understand how!!!

rufeng70 said:
Yes you need to somehow use adder. But you do not need a complete adder to find the exact number of ones. Here is one possible solution:

1) first you need to construct a basic 2 bit adder, using an and gate and an xor gate as shown in the figure a) (Sorry the diagram is messy )

2) use the adder to construct your logic as shown in figure b). where each square is a basic adder. Notice that for the adders in the first stage (first column from left), the weight of each sum output (i.e. S output of the basic adder) is one, the weight of each carry output ( C output of the basic adder) is two. For the adders in the second stage, the weights are 2 and 4 respectively, and for the third stage, the weights are 4 and 8.

Since you only need to know if there are exactly five ones, you do not need to construct a full adder. So you stop at the third column, and you want to make sure all the wires of weight 8 are zero otherwise you can not get 5, right? So that is how figure b is achieved.

What are the big globule like structures? Can you expound a bit more please?
Well, can you do this with a bit neat diagram..
I guess you have got the answer!..

Thanks man..

sarokrk said:
ya well .it is a simple 16:1 mutiplexer.

Sorry dude, no LSI blocks can be used, only simple logic gates..

rufeng70 said:
Yes you need to somehow use adder. But you do not need a complete adder to find the exact number of ones. Here is one possible solution:

1) first you need to construct a basic 2 bit adder, using an and gate and an xor gate as shown in the figure a) (Sorry the diagram is messy )

2) use the adder to construct your logic as shown in figure b). where each square is a basic adder. Notice that for the adders in the first stage (first column from left), the weight of each sum output (i.e. S output of the basic adder) is one, the weight of each carry output ( C output of the basic adder) is two. For the adders in the second stage, the weights are 2 and 4 respectively, and for the third stage, the weights are 4 and 8.

Since you only need to know if there are exactly five ones, you do not need to construct a full adder. So you stop at the third column, and you want to make sure all the wires of weight 8 are zero otherwise you can not get 5, right? So that is how figure b is achieved.

I think i figured out your answer dude.. I think you got it..
Man amazing You da Man.. Great.. Extraordinary..
Guys i think this man has got it..

Re: Hey Guys One Interview Question! Beat the hell out of Me

Re: Hey Guys One Interview Question! Beat the hell out of Me

hi dude, it is a simple "Parity Check Code", it will always detect odd no of ones in the bit stream.

got it..

regards,

baba

Re: Hey Guys One Interview Question! Beat the hell out of Me

We can also try following algorithum...
Three 32 bit adders are required!
Nifty Parallel Count
Code:
#define MASK_01010101 (((unsigned int)(-1))/3)

int bitcount (unsigned int n)
{
n = (n & MASK_01010101) + ((n >> 1) & MASK_01010101) ;
n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011) ;
n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111) ;
return n % 255 ;
}

Status
Not open for further replies.