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

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}$

1 vote