detecting number of 1's in a 8 bit data line

[senthilos]

Hi,

Yesterday I got this design question in an interview. How do you detect the number of 1's in a 8 bit data line? There is a clock running. At each clock, the output should display the number of 1's(the count) in the data line.

The interviewer expected me to design a hardware circuit at gate level to achieve this functionality. Can anyone give me a hint on how to go about this?


Thanks
Senthil

 

[GrandAlf]

You need to elaborate what you are trying to achieve. The obvious answer is to read and convert/display as binary, and count them. Though I do not think that is what you probably mean, please enlighten!

 

[fcfusion]

I found this on another forum:

We actually ask this as an interview question. Assuming you have an 8 bit char, you can use a 256 element lookup table.

https://cboard.cprogramming.com/c-programming/108033-number-1s-byte.html

Designing this at gate level seems too dificult.

I'm curious too. I wonder if theres is a easier way to implement it.

 

[senthilos]

Hi fcfusion,

You have posted a link to a software solution which is good. My question is to find a solution at the gate level (using adders, mux, FlipFlops, etc).

Thanks
Senthil

 

[GrandAlf]

It would be diffiucult to do without using msi logic, counters/decoders etc. How are you wanting to display the the result, leds, display etc. Possibly something like eight 2 input and gates, one input from byte, and the other enabled in turn by a counter. If you common the outputs, you will get the number of pulsed equal to the number of high bits. There are a few different solutions, depends on how you want it presented.

 

[senthilos]

Hi GrandAlf,

I don't understand what is meant by "common the outputs". Can you please brief a little more on that.

Thanks
Senthil

 

[AMK1971]

Check this

https://www.freepatentsonline.com/3634658.pdf

 

[FvM]

The purpose of an interview question is to check general understanding rather than to ask for a detailed solution. The said requirements
are more or less arbitrary. You may want to opt either for a sequential (clocked) or a combinational solution. Among the combinational
solutions, lookup table or cascaded adder of 8 one bit numbers can be expected most popular, I think.

 

[senthilos]

Hi FVM,

The combinational logic options looks good. Can there really be a sequential logic solution for this, because the o/p is expected for each clock cycle.

Thanks
Senthil

 

[GrandAlf]

Sorry I did not explain better. I meant connect the outputs of all the 8 AND gates together to one common point that is in effect a serial output of the parallel data. Suppose you had 5 ones and 3 zeros. You would clock each of the 8 other AND gate inputs from a counter, you would get 5 output pulses from the common output, these of course would then need to be counted. Combinational may be a more elegant solution though, as with the sequencial you would need a clock sourch and a counter that would need to be stopped after 8 clock cycles, just more logic. You could also use 2x nibble to bcd decoders and input to a 7 seg decoder to get a hex display. I am sure googling will produce a few ideas. Good luck with this.