QUESTIONS CARRY 2 MARKS EACH
Consider a fully associative cache with 8 cache blocks(numbered 0-7) and the following sequence of memory block requests:
4, 3, 25, 8, 19, 6, 25, 8, 16, 35, 45, 22, 8, 3, 16, 25, 7
If LRU replacement policy is used, which cache block will have memory block 7?
-
Solution
QUESTIONS CARRY 2 MARKS EACH
Consider a pipeline processor with 4 stages S1 to S4. We want to execute the following loop: for (i = 1; i< = 1000; i ++)(I1, I2, I3, I4)where the time taken (in ns) by instructions I1 to I4 for stages S1 to S4 are given below:
S1 S2 S3 S4
I1: 1 2 1 2
I2: 2 1 2 1
I3: 1 1 2 1
I4: 2 1 2 1
The output of I1 for i =2 will be available after
-
Solution
time 1 2 3 4 5 6 7 8 9 10 11 12 13
I1 s1 s2 s2 s3 s4 s4
I2 s1 s1 s2 s3 s3 s4
I3 s1 s2 - s3 s3 s4
I4 s1 s1 s2 - s3 s3 s4
I1 s1 - s2 s2 s3 s4 s4
so total time would be = 13 ns
QUESTIONS CARRY 2 MARKS EACH
A serial transmission T1 uses 8 information bits,2 start bits,1 stop bit and 1 parity bit for each character. A synchronous trans mission T2 uses 3 eight-bit sync characters followed by 30 eight bit information characters. If the bit rate is 1200bits/second in both cases, what are the transfer rates of T1 and T2?
QUESTIONS CARRY 2 MARKS EACH
Let M = (K,∑,δ,s,F) be a finite state automaton, where
K = {A, B},∑ = (a,b),s= A, F = {B},
δ(A,a) = A ,δ=(A,b)=B, ,δ=(B,a)=B and δ(B,b)=A
A grammar to generate the language accepted by M can be specified as G=(V,∑,R,S), where V = K ∪ ∑ and S = A
Which one of the following set of rules will make L(G) =L(M)?
QUESTIONS CARRY 2 MARKS EACH
What is the number of vertices in an undirected connected graph with 27 edges, 6 vertices of degree 2, 3 vertices of degree 4 and remaining of degree 3?
-
Solution
The idea is to use Hand shaking Lemma :- In any graph, the sum of all the vertex-degree is equal to twice the number of edges.
Let x = Number of vertices of degree 3.
By Handshaking Lemma
sum of degree of all the vertices = 2* number of edges
2*6 + 4*3 + 3*x = 27*2 x = 10.
Number of vertices = 6 + 3 + x = 19
QUESTIONS CARRY 2 MARKS EACH
Consider the following circuit composed of XOR gates and non-inverting buffers.
The non-inverting buffers have delays d1= 2ns and d2= 4ns as shown in the figure. Both XOR gates and all wires have zero delay. Assume that all gate inputs, outputs and wires are stable at logic level 0 at time 0. If the following wave form is applied at input A, how many transition(s)(change of logic levels) occur(s) at B during the interval from 0 to 10 ns?
-
Solution
INPUT OUTPUT
A B A XOR B
0 0 0
0 1 1
1 0 1
1 1 0Means, for XOR gate output is 1 when inputs are different.
Here notice that first delay is 2nS while second delay in 4nS. Anon-inverting buffer with delay ? means, whatever is the input of the buffer that will be output after time ?
In the first interval A1 becomes one but A2 will become one after 2nS as there is a delay of 2nS.Interval A A1 A2 O B1 B2 B
0 0 0 0 0 0 0 0
1 1 1 0 1 1 0 1
2 1 1 0 1 1 0 1
3 1 1 1 0 0 0 0
4 1 1 1 0 0 0 0
5 1 1 1 0 0 1 1
6 1 1 1 0 0 1 1
7 1 1 1 0 0 0 0
8 1 1 1 0 0 0 0
9 1 1 1 0 0 0 0
10 1 1 1 0 0 0 0Hence, we have 4 transitions. These are in 1st, 3rd, 5th and 7th interval.
QUESTIONS CARRY 2 MARKS EACH
Consider the ALU shown below.
If the operands are in 2’s complement representation, which of the following operations can be performed by suitably setting the control lines K and C0 only (+ and – denote addition and subtraction respectively)?
-
Solution
We can set value of k and c as 0 or 1
Two things we need to know-
1.If we take xor of any number with 1 we get it in its complement form.
2.If we take xor of any number with 0 we get that number itself.
So on setting k=1 we can get -B and c will work like select signal
Like c=0 means
add C=1 means subtract
Hence with k=1 c=1
we get A-B With K=0 c=0 we get A+B We need b=1 to get A+1 which we can't set with the help of k and c only
So Ans is (a) part.
QUESTIONS CARRY 2 MARKS EACH
The literal count of a boolean expression is the sum of the number of times each literal appears in the expression. For example,the literal count of(xy + xz’) is 4. What are the minimum possible literal counts of the product-of-sum and sum-of-product representations respectively of the function given by the following Karnaugh map? Here,x denotes “don’t care”
-
Solution
Analyzing both POS as well as SOP
QUESTIONS CARRY 2 MARKS EACH
The following is a scheme for floating point number representation using 16 bits.
Bit position
Let s, e and m be the numbers represented in binary in the sign, exponent, and mantissa fields respectively.Then the floating point number represented is:
\(\left\{\begin{matrix} (-1)^{s}(1+m\times 2^{-9})2^{e-31},if\: the\: exponet\neq 111111 & \\ 0\: otherwise& \end{matrix}\right.\)What is the maximum difference between two successive real numbers represent able in this system ?
-
Solution
QUESTIONS CARRY 2 MARKS EACH
Consider the following recurrence relation
T(1) = 1
T(n +1) = T(n) + \(\left \lfloor \sqrt{n+1} \right \rfloor\) for all n ≥ 1
The value of T(m2) for m ≥ 1 is