ISI2020-PCB-CS: 10

Question

Suppose instead of a decoder with $n$ input bits ( $n$ is even) to access a memory of size $2^{n}$, one uses two decoders of input sizes $k$ bits and $(n-k)$ bits. Explain how these two decoders can be used to access the memory of size $2^{n}$.

Determine the value of $k$ that achieves minimum address decoding time. Justify your answer. Assume that the time complexity of the decoder is measured by the number of output lines of that decoder.

Answer 1

Assuming we use decoder/demux since we need the ENABLE to combine 2 decoders.

Let’s number bits from $(LSB \rightarrow MSB)$ as:

$\Rightarrow n-\text{bits} = \{\underline{b_0, b_1, …, b_k}, \underline{b_{k+1}, … b_n}\}$

 

Let’s use $decoder_1 = k \times 2^k$ for the $k$ least significant bits

i,e., $decoder_1$ is connected to bits $\{b_0, b_1, …, b_k\}$

Since $decoder_1$ will always be active,

$\text{ENABLE}=1$

 

Let’s use $decoder_2 = (n-k) \times 2^{n-k}$ for the $(n-k)$ most significant bits

i,e., $decoder_2$ is connected to bits $\{b_{k+1}, b_{k+2}, …, b_n\}$

Since $decoder_2$ will only be active when there is atleast one active MSB

$\text{ENABLE} = (b_{k+1} + b_{k+2} + … b_{n})$

 

At any given time, either one or both the decoders will be active.

Best Case:

There is no MSB active,  $\therefore$ only $decoder_1$ is active.

$T_n = \Omega(2^k)$

Worst Case:

There is atleast one active MSB,   $\therefore$ both $decoder_1, decoder_2$ is active

$T_n = O(max\{2^k , 2^{n-k}\})$

Average Case:

In average case, both the decoders will be active.

$T_n = \Theta(max\{2^k , 2^{n-k}\})$

 

To get minimum address decoding time, i.e., minimum worst/average time complexity,

we need to find the minimum value of $k , 0 \leq k \leq n$ such that

$max\{2^k , 2^{n-k}\}$ is minimum

which is possible when both are equal,

i.e., $2^k = 2^{n-k}$

$\Rightarrow k = n-k$

$\Rightarrow k = \frac{n}{2}$