Design query :: Combinationally count number of 1's in a 32-bit bus

Solution: The design in question is a combinational design with 32-bit input and 6-bit output as there can be maximum 32 1's and 32 stands "100000" in binary. Making a truth-table or K-map for this problem is not practical, so we have to take a modular approach. Let us divide the problem into detecting number of 1's among 4 bits and then adding the resulting numbers together providing the total count.

Let us first create a truth-table converting the number of 1's in a 4-bit stream into a 2-bit number. The resulting truth table is shown in figure 1.

Figure 1: Truth table for 4-bit count 1's circuit

Solving the above for O2, O1 and O0 using K-maps, we get the expressions as shown in figures 2, 3 and 4 below.

Figure 2: Expression for O2

Figure 3: Expression for O1



Figure 4: Expression for O0

Thus, we have 8 instances, each counting the number of ones pertaining to respective 4 bits. The next thing we need is to add these 8 three-bit numbers to obtain the resultant total number of 1's in the 32-bit number we got. For this, we can again follow modular approach to add two numbers at a time until we are left with a single number. The block diagram of the complete solution is shown below in figure 5.

Figure 5: Complete block diagram of counting number of 1's


On chip bus power reduction techniques



The process of data transmission on an on-chip bus leads to switching activity on the bus wires, which charges and discharges the capacitance associated with the wires and consequently leads to dynamic power dissipation.
Bus encoding is widely used technique to reduce dynamic switching power. For any encoding scheme the sender encoder encodes the signal, while receiver decoder decodes the signal with inverse function. The power reduction encoding techniques can be divided into 2 categories: a) self-switching power reduction b) coupling power reduction.
Self-switching is bit toggling between 0 and 1 level on a wire over time, causing this wire capacitance charging and discharging with respect to its metal layer. Following techniques are used to address this power dissipation:
1.      Address bus encoding. It exploits the high regularity associated with address streams, which is characterized by local and temporal locality.
a.       Gray code encoding. This scheme guarantees only bit flip in case of sequential addresses access.
b.      T0 code. It uses an extra signal on bus which indicates whether the currently accessed address is the sequential of the previously accessed. If yes, the address bus isn’t toggled, and the receiver is responsible to calculate the address based on the previous.
c.       T0-C code. Here the extra signal is eliminated and instead a new address is sent to indicate the address regularity finished.
2.      Data bus encoding. Data bus on the contrary to address bus doesn’t possess any regularity but rather can be considered random. Therefore, no local and temporal locality can be effectively exploited.
a.       Bus-invert code. It uses Hamming distance (the number of changed bits) computation between the current value and the next value on the bus and inverts the value if the distance is greater than half of the bit width. An additional indication signal is used to indicate the value is inverted.
b.      Transition signaling. In this scheme logical 1 is indicated by level transition from 0 to 1 or from 1 to 0, while logical 0 doesn’t cause transition. This scheme ensures the number of transitions on bus is equal to the number of 1s and is effective with data where the number of 1s is less than the number of 0s.
Coupling power is dissipated when crosstalk between different wires of the bus happens. Following techniques are used to address this power dissipation:
1.      Address bus encoding.
a.       Permutation of address bus lines is done at physical design stage to reduce coupling. It can be achieved by orthogonal layout of the wires or passing them through different metal layers.
2.      Data bus encoding.
a.       CBI (coupling bus-invert). Is very similar to previously explained bus-invert code scheme but inverts the data to achieve better cross-coupling effect.
b.      Transition pattern coding scheme (TPC). It adds signal to the bus to encode codeword patterns in which neighboring lines change in phase.

For more power reduction schemes you can refer to On-chip Communication Architectures book.

Courtesy www.shellbr.com.