Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronic Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

Register Log in

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

Status
Not open for further replies.

pnnavigator0915

Member level 3
Joined
Feb 4, 2006
Messages
62
Helped
1
Reputation
2
Reaction score
0
Trophy points
1,286
Activity points
1,900
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..

 

khaila

Full Member level 2
Joined
Jan 13, 2007
Messages
121
Helped
5
Reputation
10
Reaction score
1
Trophy points
1,298
Activity points
2,105
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.
 

sohiltri

Member level 5
Joined
Dec 16, 2006
Messages
81
Helped
6
Reputation
12
Reaction score
1
Trophy points
1,288
Activity points
1,750
Re: Hey Guys One Interview Question! Beat the hell out of Me

It could be some kind of comparator....
 

Aryan Nayar

Newbie level 1
Joined
Sep 9, 2007
Messages
1
Helped
0
Reputation
0
Reaction score
0
Trophy points
1,281
Activity points
1,285
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
 

links104

Newbie level 4
Joined
Feb 12, 2006
Messages
7
Helped
2
Reputation
4
Reaction score
1
Trophy points
1,283
Activity points
1,329
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
 

phutanesv

Full Member level 3
Joined
Apr 26, 2007
Messages
151
Helped
19
Reputation
38
Reaction score
7
Trophy points
1,298
Activity points
2,233
Re: Hey Guys One Interview Question! Beat the hell out of Me

links104 said:
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
 

avimit

Banned
Joined
Nov 16, 2005
Messages
413
Helped
91
Reputation
182
Reaction score
23
Trophy points
1,298
Location
Fleet, UK
Activity points
0
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
 

pnnavigator0915

Member level 3
Joined
Feb 4, 2006
Messages
62
Helped
1
Reputation
2
Reaction score
0
Trophy points
1,286
Activity points
1,900
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??
 

nikhilindia85

Member level 4
Joined
Feb 28, 2007
Messages
78
Helped
3
Reputation
6
Reaction score
3
Trophy points
1,288
Activity points
1,712
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
 

rufeng70

Newbie level 3
Joined
Sep 24, 2005
Messages
4
Helped
0
Reputation
0
Reaction score
0
Trophy points
1,281
Activity points
1,303
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.
 

maxsnail

Member level 5
Joined
Sep 29, 2004
Messages
85
Helped
6
Reputation
28
Reaction score
1
Trophy points
1,288
Activity points
584
Re: Hey Guys One Interview Question! Beat the hell out of Me

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

calm

Full Member level 4
Joined
Oct 17, 2005
Messages
217
Helped
9
Reputation
18
Reaction score
4
Trophy points
1,298
Activity points
2,156
comparator must be
 

sarokrk

Newbie level 1
Joined
Aug 16, 2007
Messages
1
Helped
0
Reputation
0
Reaction score
0
Trophy points
1,281
Activity points
1,283
ya well .it is a simple 16:1 mutiplexer.
 

amitjagtap

Full Member level 5
Joined
Jan 10, 2007
Messages
304
Helped
42
Reputation
84
Reaction score
36
Trophy points
1,308
Activity points
3,273
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.
 

pnnavigator0915

Member level 3
Joined
Feb 4, 2006
Messages
62
Helped
1
Reputation
2
Reaction score
0
Trophy points
1,286
Activity points
1,900
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 :cry: 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!!!

Added after 7 minutes:

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

Added after 1 minutes:

sarokrk said:
ya well .it is a simple 16:1 mutiplexer.
Sorry dude, no LSI blocks can be used, only simple logic gates..

Added after 12 minutes:

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

zia.roghani

Member level 1
Joined
Sep 13, 2006
Messages
37
Helped
1
Reputation
2
Reaction score
1
Trophy points
1,288
Activity points
1,514
Re: Hey Guys One Interview Question! Beat the hell out of Me

links 104 is right


u can design in the said way
 

ship_baba

Member level 4
Joined
Aug 9, 2007
Messages
70
Helped
6
Reputation
12
Reaction score
5
Trophy points
1,288
Activity points
1,592
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
 

nand_gates

Advanced Member level 3
Joined
Jul 19, 2004
Messages
892
Helped
174
Reputation
348
Reaction score
51
Trophy points
1,308
Activity points
6,803
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)
 #define MASK_00110011 (((unsigned int)(-1))/5)
 #define MASK_00001111 (((unsigned int)(-1))/17)

 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.
Toggle Sidebar

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Top