Digital Logic & Computer Organization exam preparation.
Practice questions for every unit in the style of the R23 end exam, a model answer for each, and a one-page revision summary. Built on the official syllabus units.
- Practice questions in the exam's style
- Drafted with AI and checked by a second AI pass. Doubtful points were verified against public sources. Report a mistake
- Units
- 5
- Questions
- 60
- 2-mark
- 30
- 10-mark
- 30
- Done
- Checked on
Exam guide
Paper pattern
Semester-end theory paper, 70 marks, from the JNTUK B.Tech R23 Regulations, end-examination pattern for theory subjects.
- Question 1 · 20 marksTen compulsory short-answer questions of 2 marks each (two from every unit).
- Questions 2 to 6 · 50 marksFive either/or questions of 10 marks each, one per unit. You answer one of the two in each.
- The semester-end examination carries 70 marks; internal assessment carries 30.
- Mid-semester examinations are separate: a 20-minute objective paper (10 marks) and a 90-minute subjective paper with three either/or questions of 10 marks (condensed to 15 marks).
- The regulations text does not state the length of the end examination. Use the duration printed on your hall ticket or question paper.
How to split your time
This plan assumes a 3-hour paper. If yours is different, keep the same proportions. Marks per minute stay roughly even across Question 1 and the 10-mark answers.
- 10 minRead the paper and choose one option in each either/or question
- 30 minQuestion 1: ten short answers (about 3 minutes each)
- 130 minQuestions 2 to 6: one 10-mark answer per unit (about 26 minutes each)
- 10 minFinal check of numbering, calculations and diagrams
Study tips for Digital Logic & Computer Organization
- Practise K-map simplification daily with 3- and 4-variable functions, including don't-care conditions, and verify each simplified expression by checking a few rows of the truth table against the original function.
- For number systems, work conversions (binary, octal, hexadecimal, BCD) and signed 1's and 2's complement addition and subtraction by hand, writing every carry and checking for overflow so that each step is visible to the examiner.
- When studying flip-flops, counters and registers, draw the logic diagram, characteristic table, excitation table and timing waveform together, and practise designing a counter from its state table through to the final flip-flop input equations.
- For computer arithmetic, trace each algorithm by hand: carry-lookahead generate and propagate terms, Booth's multiplication of signed operands, restoring and non-restoring division, and floating-point addition and multiplication. Write every register value (A, Q, M) after each cycle and check the final result in decimal.
- Sketch neat labelled block diagrams with data-flow arrows for functional units, bus structures, single- and multiple-bus datapaths, hardwired versus microprogrammed control units, the memory hierarchy, and interrupt and DMA transfers, and write the control steps for executing a complete instruction.
- Solve small numerical problems from the organization units, such as the basic performance equation, cache tag/index/offset bit splitting, average memory access time from the hit ratio, and memory chip and address-line calculations.
Data Representation and Combinational Logic
Syllabus: Binary numbers; Fixed-point representation; Floating-point representation; Number base conversions; Octal and hexadecimal numbers; Complements of numbers; Signed binary numbers; Binary codes; Basic logic functions and logic gates; Universal logic gates; Minimisation of logic expressions; K-map simplification; Combinational circuits; Decoders; Multiplexers
One-page revision summary
- Binary is a base-2 positional system: a digit in position i has weight 2^i, and digits after the binary point have weights 2^−1, 2^−2 and so on.
- To convert a decimal number to base r, divide the integer part repeatedly by r (remainders read bottom to top) and multiply the fraction repeatedly by r (integer parts read top to bottom).
- Octal and hexadecimal are shorthand for binary: group 3 bits per octal digit and 4 bits per hex digit, starting from the binary point, with hex digits A–F standing for 10–15.
- For base r there are two complements, the (r−1)'s complement and the r's complement; for decimal these are the 9's and 10's complements, and for binary the 1's and 2's complements.
- Signed numbers use sign-magnitude, 1's complement or 2's complement; only 2's complement has a single zero and an n-bit range of −2^(n−1) to 2^(n−1) − 1.
- Fixed-point numbers keep the binary point at a fixed place, while floating-point numbers store a sign, a normalised mantissa and a biased exponent to cover a far wider range.
- BCD (8421) codes each decimal digit in 4 bits, excess-3 is BCD + 0011 and is self-complementing, Gray code changes one bit between successive values, and ASCII is a 7-bit alphanumeric code.
- The basic gates are AND (AB), OR (A + B) and NOT (A'); the derived gates are NAND (AB)', NOR (A + B)', XOR (A ⊕ B = A'B + AB') and XNOR (A ⊕ B)'.
- NAND and NOR are universal gates: a two-level SOP circuit maps directly to NAND-NAND form, and a two-level POS circuit maps directly to NOR-NOR form.
- Algebraic minimisation uses the identity, idempotent, absorption (A + AB = A), consensus and De Morgan laws to reduce the number of literals.
- In a K-map, adjacent cells (including wrap-around edges) differ in one variable; group 1s in powers of two, make groups as large as possible, and use don't cares only when they enlarge a group.
- Combinational circuits have no memory: their outputs depend only on present inputs, and they are designed by the steps specification → truth table → simplified expressions → logic diagram.
- A half adder gives S = A ⊕ B and C = AB, while a full adder adds a carry-in as well.
- An n-to-2^n decoder activates one output per input code, so each output is a minterm; with OR gates added, it can realise any function.
- A 2^n-to-1 multiplexer uses n select lines to route one data input to the output and can generate any function of n + 1 variables.
- Gate outputs: AND gives 1 only when all inputs are 1, OR gives 1 when any input is 1, XOR gives 1 when the inputs differ, XNOR gives 1 when they are equal, and NAND and NOR are the complements of AND and OR.
- Decimal complements: the 9's complement of a digit d is 9 − d and the 10's complement is that plus 1, so for 47 they are 52 and 53. To find 85 − 47, add 85 + 53 = 138 and discard the carry, giving 38.
- Code examples: (45)10 is 0100 0101 in BCD and 0111 1000 in excess-3 (each digit plus 0011). Inverting the bits of an excess-3 digit gives the code of its 9's complement, so the code is self-complementing. ASCII A is 65 = 1000001.
Learn these by heart
- 2's complement = 1's complement + 1; the n-bit 2's complement range is −2^(n−1) to 2^(n−1) − 1.
- IEEE 754 single precision: value = (−1)^S × 1.F × 2^(E − 127), with 1 sign bit, 8 exponent bits and 23 fraction bits (double precision uses bias 1023 and 52 fraction bits).
- De Morgan's laws: (A·B)' = A' + B' and (A + B)' = A'·B'.
- Binary to Gray: g(n−1) = b(n−1), and gi = b(i+1) ⊕ bi for the remaining bits.
- Full adder: S = A ⊕ B ⊕ Cin and Cout = AB + BCin + ACin.
- 4-to-1 MUX: Y = S1'S0'I0 + S1'S0I1 + S1S0'I2 + S1S0I3.
- 2's complement overflow = carry into MSB ⊕ carry out of MSB.
2-mark questions
1 Convert (156)10 into binary, octal and hexadecimal. 2 marks
156 = 128 + 16 + 8 + 4, so (156)10 = (10011100)2.
Octal: group 3 bits from the right, 010 011 100 = (234)8.
Hexadecimal: group 4 bits, 1001 1100 = (9C)16.
Check: 2×64 + 3×8 + 4 = 156 and 9×16 + 12 = 156.
2 Find the 1's complement and the 2's complement of (01011000)2. 2 marks
1's complement: invert every bit of 01011000, giving 10100111.
2's complement: add 1 to the 1's complement. 10100111 + 1 = 10101000.
Shortcut check: keep the bits from the right up to and including the first 1 (1000). Invert the remaining bits (0101 becomes 1010). This gives 10101000.
3 Represent −23 in 8-bit sign-magnitude, 1's complement and 2's complement forms. 2 marks
+23 = 00010111.
- Sign-magnitude: set the MSB to 1, giving 10010111.
- 1's complement: invert all bits of +23, giving 11101000.
- 2's complement: add 1 to the 1's complement, giving 11101001.
In all three forms the MSB is 1, which shows the number is negative.
4 Why are NAND and NOR called universal gates? Show how a NOT gate is obtained from a NAND gate. 2 marks
NAND and NOR are called universal gates because AND, OR and NOT can each be built from only one of these gate types. Since every Boolean function uses only these three operations, any function can be built this way.
Tying both inputs of a NAND together gives (A·A)' = A', which is a NOT gate.
5 What is Gray code? Convert binary 1011 to Gray code. 2 marks
Gray code is an unweighted code in which successive values differ in exactly one bit. This reduces reading errors in shaft encoders, and the same one-bit-change ordering is used for the rows and columns of a K-map.
Conversion rule: keep the MSB, then each Gray bit is the XOR of adjacent binary bits.
- g3 = 1
- g2 = 1⊕0 = 1
- g1 = 0⊕1 = 1
- g0 = 1⊕1 = 0
Gray code = 1110.
6 Distinguish between fixed-point and floating-point representation. 2 marks
In fixed-point representation the binary point sits at a fixed position, for example to the right of the LSB for integers. Precision is uniform, but the range is small.
Floating-point stores a number as a sign, a mantissa and an exponent (±M × 2^E), so the point 'floats'. This gives a very wide range with relative precision, but needs more complex hardware.
10-mark questions
1 Explain the IEEE 754 single-precision floating-point format. Represent (−13.625)10 in this format and give the result in hexadecimal. 10 marks
The IEEE 754 standard fixes how real numbers are stored in floating-point form, so that very large and very small values can be handled with a fixed number of bits. A number is first written in normalised form ±1.F × 2^e. Only the sign, a biased exponent and the fraction F are stored.
Single-precision format (32 bits):
- Sign S (1 bit, bit 31): 0 for positive, 1 for negative.
- Biased exponent E (8 bits, bits 30 to 23): E = e + 127, where 127 is the bias. Biasing lets exponents be compared as unsigned numbers.
- Fraction F (23 bits, bits 22 to 0): the bits after the binary point of the normalised mantissa. The leading 1 is not stored (hidden bit), giving 24 bits of precision.
Value = (−1)^S × 1.F × 2^(E − 127) for 1 ≤ E ≤ 254.
Special cases:
- E = 0, F = 0: zero.
- E = 0, F ≠ 0: denormalised number.
- E = 255, F = 0: infinity.
- E = 255, F ≠ 0: NaN (not a number).
Representing −13.625:
Step 1. Sign: the number is negative, so S = 1.
Step 2. Integer part: 13 = 8 + 4 + 1 = (1101)2.
Step 3. Fractional part by repeated multiplication by 2:
- 0.625 × 2 = 1.25, digit 1
- 0.25 × 2 = 0.50, digit 0
- 0.50 × 2 = 1.00, digit 1
So 0.625 = (0.101)2.
Step 4. Combine the two parts: 13.625 = (1101.101)2.
Step 5. Normalise by moving the point 3 places left: 1101.101 = 1.101101 × 2^3, so e = 3.
Step 6. Biased exponent: E = 3 + 127 = 130 = (10000010)2.
Step 7. Fraction: the bits after the point are 101101. Pad with 17 zeros to make 23 bits: 10110100000000000000000.
Step 8. Assemble the fields: 1 | 10000010 | 10110100000000000000000.
Step 9. Group into nibbles: 1100 0001 0101 1010 0000 0000 0000 0000 = (C15A0000)16.
Check: 1.101101 = 1 + 0.5 + 0.125 + 0.0625 + 0.015625 = 1.703125. Then 1.703125 × 8 = 13.625, and the sign is negative. The result is correct.
Conclusion: in IEEE 754 single precision, −13.625 is stored as 1 10000010 10110100000000000000000, which is C15A0000 in hexadecimal. Double precision uses the same idea with 1 sign bit, 11 exponent bits (bias 1023) and 52 fraction bits.
2 Explain the three methods of representing signed binary numbers. Using 8-bit 2's complement arithmetic, compute (45 − 28) and (28 − 45), and explain overflow with an example. 10 marks
Computers store signed integers in fixed-point form, with the binary point understood to be to the right of the least significant bit. The most significant bit (MSB) shows the sign: 0 for positive, 1 for negative. Three conventions are used for negative numbers.
1. Sign-magnitude: the MSB is the sign and the remaining bits hold the magnitude. Example: −6 = 10000110. The range for n bits is −(2^(n−1) − 1) to +(2^(n−1) − 1). It has two zeros (00000000 and 10000000), and addition needs separate sign logic.
2. 1's complement: a negative number is formed by inverting every bit of the positive number. Example: −6 = 11111001. The range is the same as sign-magnitude. It still has two zeros, and addition needs an end-around carry.
3. 2's complement: the 1's complement plus 1. Example: −6 = 11111010. The range is −2^(n−1) to +2^(n−1) − 1, which is −128 to +127 for 8 bits. There is only one zero, and subtraction becomes ordinary addition, so almost all processors use this form.
Rule for A − B: add A to the 2's complement of B and discard any carry out of the MSB.
(a) 45 − 28
- +45 = 00101101 and +28 = 00011100.
- −28: the 1's complement of +28 is 11100011; adding 1 gives 11100100.
- 00101101 + 11100100 = 1 00010001.
- Discard the end carry. The result is 00010001 = +17, which is correct since 45 − 28 = 17.
(b) 28 − 45
- −45: the 1's complement of 00101101 is 11010010; adding 1 gives 11010011.
- 00011100 + 11010011 = 11101111, with no end carry.
- The MSB is 1, so the result is negative.
- Its magnitude is the 2's complement of 11101111: 00010000 + 1 = 00010001 = 17.
- The result is −17, which is correct.
Overflow: an 8-bit 2's complement register holds only −128 to +127, so a sum outside this range overflows. Overflow can occur only when both operands have the same sign. It is detected in either of two equivalent ways:
- the sign of the result differs from the sign of the operands, or
- the carry into the MSB differs from the carry out of the MSB (overflow = Cin(MSB) ⊕ Cout(MSB)).
Example: 100 + 50
- 01100100 + 00110010 = 10010110.
- The carry into the MSB is 1 and the carry out of the MSB is 0, so overflow = 1 ⊕ 0 = 1.
- The result 10010110 reads as −106 instead of +150, because 150 exceeds +127.
Conclusion: 2's complement gives a single zero, the widest range and simple adder-based subtraction. Overflow is flagged by the XOR of the last two carries.
3 Simplify F(A,B,C,D) = Σm(0,1,2,5,8,9,10) using a Karnaugh map and implement the minimal expression using only NAND gates. 10 marks
A Karnaugh map arranges the minterms of a function so that adjacent cells differ in only one variable. Grouping adjacent 1s in blocks of 1, 2, 4 or 8 removes the variables that change within each group, which gives a minimal sum of products (SOP).
Step 1. Draw the 4-variable map with AB on the rows and CD on the columns, both in Gray order (00, 01, 11, 10). Place 1s for the given minterms; the minterm number is shown in brackets.
CD=00 CD=01 CD=11 CD=10
AB=00 1(0) 1(1) 0(3) 1(2)
AB=01 0(4) 1(5) 0(7) 0(6)
AB=11 0(12) 0(13) 0(15) 0(14)
AB=10 1(8) 1(9) 0(11) 1(10)Step 2. Form the largest groups.
- Quad 1: cells 0, 1, 8 and 9. These are rows 00 and 10, which are adjacent because the map wraps around, and columns 00 and 01. A and D change and B = 0, C = 0, so the term is B'C'.
- Quad 2: the four corners 0, 2, 8 and 10. Here B = 0 and D = 0, so the term is B'D'.
- Pair: cells 1 and 5. Here A = 0, C = 0, D = 1 and B changes, so the term is A'C'D.
Step 3. All seven minterms are covered and each group is an essential prime implicant. Minimal SOP: F = B'C' + B'D' + A'C'D
Step 4. Convert to NAND-NAND form. Complement F twice and apply De Morgan's law: F = ((B'C' + B'D' + A'C'D)')' = ((B'C')' · (B'D')' · (A'C'D)')' Each product term becomes a NAND gate, and the OR becomes a final NAND gate.
Step 5. Gate list:
- If complemented inputs are not available, four NAND gates with inputs tied together produce A', B', C' and D'.
- G1 = NAND(B', C').
- G2 = NAND(B', D').
- G3 = NAND(A', C', D).
- F = NAND(G1, G2, G3).
In total there are 4 + 3 + 1 = 8 NAND gates.
Conclusion: the K-map reduces seven minterms to F = B'C' + B'D' + A'C'D. A two-level SOP maps directly onto a two-level NAND-NAND circuit, which shows the universality of the NAND gate.
4 (a) Simplify F = AB + A(B + C) + B(B + C) using Boolean algebra. (b) Using a K-map, simplify F(A,B,C,D) = Σm(1,3,7,11,15) + d(0,2,5) in both SOP and POS forms. 10 marks
Minimisation reduces the number of literals and gates needed to build a function. It can be done with Boolean algebra theorems or with a Karnaugh map, which is easier when there are don't-care conditions.
(a) Algebraic simplification
Step 1. Distribute: F = AB + AB + AC + BB + BC.
Step 2. Idempotent law (X + X = X and X·X = X): F = AB + AC + B + BC.
Step 3. Factor B from the terms that contain it: F = B(A + 1 + C) + AC.
Step 4. Since 1 + anything = 1: F = B·1 + AC = B + AC.
Result: F = B + AC, which uses one OR gate and one AND gate.
(b) K-map with don't cares
Step 1. Plot 1 for each minterm, X for each don't care and 0 elsewhere (AB on rows, CD on columns, both in Gray order).
CD=00 CD=01 CD=11 CD=10
AB=00 X(0) 1(1) 1(3) X(2)
AB=01 0(4) X(5) 1(7) 0(6)
AB=11 0(12) 0(13) 1(15) 0(14)
AB=10 0(8) 0(9) 1(11) 0(10)A don't care may be treated as 1 or as 0, whichever gives larger groups.
Step 2. SOP grouping of the 1s:
- The whole column CD = 11 (cells 3, 7, 15, 11) forms a quad, giving CD.
- Minterm 1 is still uncovered. Taking d5 as 1 gives the quad 1, 3, 5, 7 (rows 00 and 01, columns 01 and 11), giving A'D.
- d0 and d2 are not needed and are taken as 0.
Minimal SOP: F = CD + A'D. An equally minimal alternative is CD + A'B', which uses d0 and d2 instead.
Step 3. POS grouping of the 0s. The 0 cells are 4, 6, 8, 9, 10, 12, 13 and 14.
- Taking d0 and d2 as 0, every cell with D = 0 (0, 2, 4, 6, 8, 10, 12, 14) forms an octet, giving the complement term D'.
- Cells 8, 9, 12 and 13 (A = 1, C = 0) form a quad, giving AC'.
So F' = D' + AC'. Applying De Morgan's law: F = D · (A' + C).
Step 4. Check consistency: D(A' + C) = A'D + CD, which is the same as the SOP result. Both forms treat d5 as 1 and d0, d2 as 0.
Conclusion: algebra gives F = B + AC for part (a). The K-map with don't cares gives F = CD + A'D in SOP and F = D(A' + C) in POS. The POS form needs only one OR gate and one AND gate.
5 Explain the design procedure for combinational circuits. Design a 3-to-8 line decoder and use it to implement a full adder. 10 marks
A combinational circuit is one whose outputs depend only on the present inputs, with no memory. Adders, decoders, multiplexers and code converters are examples.
Design procedure: 1. Read the specification and decide the number of inputs and outputs, giving each a name. 2. Write the truth table relating inputs to outputs. 3. Obtain a simplified Boolean expression for each output using a K-map or algebra. 4. Draw the logic diagram with the available gates or MSI blocks. 5. Verify the design by simulation or by checking the truth table.
3-to-8 line decoder:
A decoder converts an n-bit code into 2^n output lines and activates exactly one output for each input combination. With inputs A, B, C (A is the MSB), each output is one minterm:
- D0 = A'B'C'
- D1 = A'B'C
- D2 = A'BC'
- D3 = A'BC
- D4 = AB'C'
- D5 = AB'C
- D6 = ABC'
- D7 = ABC
The circuit uses three NOT gates and eight 3-input AND gates. An optional enable input E can be added to every AND gate, so that Di = E·mi.
Full adder using the decoder:
A full adder adds bits x, y and carry-in z to give sum S and carry-out Cout.
x y z | S Cout
0 0 0 | 0 0
0 0 1 | 1 0
0 1 0 | 1 0
0 1 1 | 0 1
1 0 0 | 1 0
1 0 1 | 0 1
1 1 0 | 0 1
1 1 1 | 1 1From the table:
- S = Σm(1, 2, 4, 7)
- Cout = Σm(3, 5, 6, 7)
Since the decoder already produces every minterm, each output needs only an OR gate:
- S = D1 + D2 + D4 + D7, which equals x ⊕ y ⊕ z.
- Cout = D3 + D5 + D6 + D7, which equals xy + yz + xz.
Conclusion: because a decoder produces all 2^n minterms, any n-variable function in sum-of-minterms form can be built with one decoder and one OR gate per output. The full adder is a neat example of this.
6 Explain the working of a 4-to-1 multiplexer with its logic diagram. Implement F(A,B,C) = Σm(1,2,6,7) using a 4-to-1 multiplexer. 10 marks
A multiplexer (MUX) is a combinational circuit that selects one of 2^n data inputs and routes it to a single output, using n select lines. It acts as a digital rotary switch, and it can also be used as a function generator.
Working of a 4-to-1 MUX:
It has data inputs I0 to I3, select lines S1 and S0, and output Y. The selection rule is:
S1 S0 | Y
0 0 | I0
0 1 | I1
1 0 | I2
1 1 | I3Boolean equation: Y = S1'S0'I0 + S1'S0I1 + S1S0'I2 + S1S0I3
Only one product term can be true at a time, so the output follows the selected input.
Logic structure: two NOT gates produce S1' and S0'. Four 3-input AND gates each combine one data input with the matching select combination. A 4-input OR gate collects the four AND outputs.
Implementing F(A,B,C) = Σm(1,2,6,7):
Step 1. Choose A and B as the select lines (A to S1, B to S0). The remaining variable C is used, with constants, at the data inputs.
Step 2. For each select combination, compare the two minterms that differ only in C:
- AB = 00: m0 (C=0) gives F = 0 and m1 (C=1) gives F = 1, so F = C and I0 = C.
- AB = 01: m2 (C=0) gives F = 1 and m3 (C=1) gives F = 0, so F = C' and I1 = C'.
- AB = 10: m4 and m5 both give F = 0, so I2 = 0.
- AB = 11: m6 and m7 both give F = 1, so I3 = 1.
Implementation table (the first row holds the minterms with C = 0, the second row those with C = 1):
I0 I1 I2 I3
C=0 m0 m2 m4 m6
C=1 m1 m3 m5 m7
Input C C' 0 1Step 3. Connections: A to S1, B to S0, C to I0, C through an inverter to I1, logic 0 (ground) to I2, logic 1 (VCC) to I3. The output Y = F.
Step 4. Verify using the MUX equation: Y = A'B'C + A'BC' + AB'·0 + AB·1 = A'B'C + A'BC' + AB. A'B'C is m1, A'BC' is m2, and AB covers m6 and m7, so the minterms are 1, 2, 6 and 7, which is correct.
Conclusion: a 2^n-to-1 multiplexer can realise any function of n + 1 variables. n variables drive the select lines, and the last variable, its complement, 0 or 1 feeds the data inputs. Here a single 4-to-1 MUX and one inverter realise the three-variable function.
Sequential Circuits and Basic Structure of Computers
Syllabus: Sequential circuits; Flip-flops; Binary counters; Registers and shift registers; Ripple counters; Computer types; Functional units; Basic operational concepts; Bus structures; Software; Performance; Multiprocessors and multicomputers; Computer generations; Von Neumann architecture
One-page revision summary
- A sequential circuit combines combinational logic with memory elements. Synchronous circuits change state only at clock edges, while asynchronous circuits respond directly to input changes.
- The SR, JK, D and T flip-flops each store one bit; edge triggering or master-slave construction removes the race-around problem of the JK flip-flop.
- An n-bit binary counter uses n flip-flops, has 2^n states, and each stage divides the clock frequency by 2.
- A ripple counter clocks each stage from the previous stage's output, so it is simple but slow; a synchronous counter clocks all stages together and uses gating logic.
- A mod-N ripple counter is formed by detecting state N with a NAND gate and applying its output to the asynchronous clear inputs.
- Shift registers come in SISO, SIPO, PISO and PIPO types; a universal shift register can hold, shift left, shift right or load in parallel under two select lines.
- Computer types: personal computers (desktops and notebooks) serve one user, workstations add high-performance graphics and computing, enterprise systems and servers handle many users and network requests, supercomputers run large numerical tasks such as weather forecasting, and embedded computers are dedicated controllers inside appliances and vehicles.
- The five functional units are input, memory, ALU, output and control, and the ALU together with the control unit forms the processor.
- The PC, IR, MAR and MDR registers carry out the fetch-decode-execute cycle that runs every instruction.
- A bus is a shared set of data, address and control lines; a single bus is cheap but allows only one transfer at a time, while multiple buses permit concurrent transfers.
- Software is divided into system software (operating system, compiler, assembler, linker, loader, editor) and application software that solves user problems.
- The operating system manages processor time, memory, files and I/O devices, and the compiler translates high-level language programs into machine instructions.
- Performance is measured by program execution time T = N × S / R and is improved by a faster clock, pipelining, superscalar execution, cache memory, better compilers and a suitable instruction set.
- A multiprocessor has many processors sharing one memory and communicating through shared variables, so it is tightly coupled.
- A multicomputer is a set of independent computers, each with private memory, that communicate by message passing over a network, so it is loosely coupled.
- The first computer generation used vacuum tubes and machine language; the second used transistors, magnetic core memory and early high-level languages.
- The third generation used integrated circuits and multiprogramming operating systems; the fourth used VLSI microprocessors and personal computers; later systems use ULSI, parallel processing and intelligent applications.
- The von Neumann architecture stores instructions and data in one memory and executes instructions sequentially, so the shared processor-memory path forms the von Neumann bottleneck; the Harvard design uses separate instruction and data memories.
- Program translation flow: a compiler translates high-level source code into object code, an assembler translates assembly language, the linker combines object modules and library routines into one executable, and the loader places it in memory to run.
Learn these by heart
- Characteristic equations: SR: Q(t+1) = S + R'Q with SR = 0; JK: Q(t+1) = JQ' + K'Q; D: Q(t+1) = D; T: Q(t+1) = T ⊕ Q.
- JK excitation table: 0→0: J=0, K=X; 0→1: J=1, K=X; 1→0: J=X, K=1; 1→1: J=X, K=0.
- Counters: n flip-flops give mod 2^n; a mod-N counter needs the smallest n with 2^n ≥ N; the output frequency of stage k is f/2^k.
- Maximum clock frequency of an n-stage ripple counter: fmax = 1/(n × tpd).
- Synchronous binary up counter: Ji = Ki = Q0·Q1·...·Q(i-1), with J0 = K0 = 1.
- Basic performance equation: T = (N × S)/R, where N is instructions executed, S is average cycles per instruction and R is the clock rate.
- SPEC rating = reference running time / test machine running time; the overall rating is the geometric mean over the suite.
2-mark questions
1 Define a sequential circuit and state how it differs from a combinational circuit. 2 marks
A sequential circuit is a logic circuit whose output depends on the present inputs and on the present state stored in memory elements such as flip-flops. A combinational circuit has no memory, so its output depends only on the current inputs. Sequential circuits use feedback and are usually controlled by a clock.
2 What is the race-around condition in a JK flip-flop, and how is it avoided? 2 marks
In a level-triggered JK flip-flop with J = K = 1, the output toggles repeatedly while the clock stays high if the pulse is longer than the propagation delay. The final state is then unpredictable. It is avoided by master-slave construction or edge triggering, so the output changes only once per clock pulse.
3 A 5-bit ripple counter is driven by a 64 kHz clock. Find its modulus and the frequency at the MSB output. 2 marks
Modulus = 2^5 = 32 states. Each flip-flop divides its input frequency by 2. The MSB (fifth stage) frequency is therefore 64 kHz / 2^5 = 64 kHz / 32 = 2 kHz.
4 A program executes 2 × 10^8 instructions with an average of 2.5 clock cycles per instruction on a 1 GHz processor. Find the execution time. 2 marks
Use T = (N × S)/R, where N is the instruction count, S is the cycles per instruction and R is the clock rate.
T = (2 × 10^8 × 2.5)/(1 × 10^9) = (5 × 10^8)/(10^9) = 0.5 seconds.
5 Distinguish between a multiprocessor and a multicomputer. 2 marks
A multiprocessor has several processors that share a common main memory and communicate through shared variables, so it is tightly coupled. A multicomputer is a set of complete computers, each with its own private memory, joined by a network. They communicate by exchanging messages, so it is loosely coupled.
6 What is the stored-program concept of the von Neumann architecture, and what is the von Neumann bottleneck? 2 marks
In the von Neumann architecture, instructions and data are held together in the same read-write memory and are fetched one after another for execution. A single path carries both instructions and data between processor and memory. The rate of transfer on this path limits processor speed, and this limitation is called the von Neumann bottleneck.
10-mark questions
1 Explain the SR, JK, D and T flip-flops with their characteristic tables and characteristic equations. Also give the general block diagram of a sequential circuit. 10 marks
A sequential circuit is a logic circuit whose outputs depend on the present inputs and on the past history of inputs. That history is stored as the present state in memory elements. In clocked (synchronous) sequential circuits the memory element is the flip-flop. A flip-flop stores one bit and changes state only at a clock edge.
1. SR flip-flop (inputs S = set, R = reset):
- S=0, R=0: Q(t+1) = Q(t), no change
- S=0, R=1: Q(t+1) = 0, reset
- S=1, R=0: Q(t+1) = 1, set
- S=1, R=1: not allowed, indeterminate
Characteristic equation: Q(t+1) = S + R'Q, with the condition SR = 0.
2. JK flip-flop (removes the forbidden input of SR):
- J=0, K=0: no change
- J=0, K=1: reset to 0
- J=1, K=0: set to 1
- J=1, K=1: toggle, Q(t+1) = Q'(t)
Characteristic equation: Q(t+1) = JQ' + K'Q. In a level-triggered JK with J = K = 1, the output may toggle many times within one clock pulse (race-around). Edge triggering or master-slave construction prevents this.
3. D flip-flop (single data input; the output copies D at the clock edge):
- D=0: Q(t+1) = 0
- D=1: Q(t+1) = 1
Characteristic equation: Q(t+1) = D. It is obtained from an SR flip-flop by applying D to S and D' (through an inverter) to R. The invalid combination therefore never occurs.
4. T flip-flop (obtained from JK by joining J and K into one input T):
- T=0: no change
- T=1: toggle
Characteristic equation: Q(t+1) = T ⊕ Q = TQ' + T'Q.
5. Excitation tables give the inputs needed for each transition Q → Q(t+1), and are used in design. For JK:
- 0→0: J=0, K=X
- 0→1: J=1, K=X
- 1→0: J=X, K=1
- 1→1: J=X, K=0
For D, the input simply equals the next state. For T, the input is 1 whenever the state must change.
Conclusion: All four flip-flops store one bit. SR is the basic form, and JK is the most versatile because it has no invalid input. D is the natural choice for registers and T is the natural choice for counters.
2 What is a shift register? Explain the SISO, SIPO, PISO and PIPO shift registers and the universal shift register, with an example of serial data entry. 10 marks
A register is a group of flip-flops sharing a common clock, each storing one bit, so an n-bit register needs n flip-flops. A shift register is a register whose stored bits move one position left or right on every clock pulse. The output of each flip-flop feeds the input of its neighbour. D flip-flops are normally used.
Types, classified by how data enters and leaves: 1. SISO (serial-in serial-out): data enters one bit per clock and leaves from the last stage. An n-bit SISO delays data by n clock periods. 2. SIPO (serial-in parallel-out): data enters serially and all n bits are read together. It is used for serial-to-parallel conversion in receivers. 3. PISO (parallel-in serial-out): all bits are loaded in one clock and then shifted out one by one. It is used in transmitters. 4. PIPO (parallel-in parallel-out): data is loaded and read in parallel, so it acts as a simple storage register. 5. Bidirectional and universal registers: these can shift left or right. A universal register can also hold its contents and load in parallel.
Worked example: a 4-bit right shift, initial state Q3Q2Q1Q0 = 0000, with serial bits 1, 0, 1, 1 applied in that order. On each clock: Q3 ← SI, Q2 ← Q3, Q1 ← Q2, Q0 ← Q1.
- Clock 1, SI=1: 1000
- Clock 2, SI=0: 0100
- Clock 3, SI=1: 1010
- Clock 4, SI=1: 1101
After four clocks the whole word is stored. It can be read in parallel (SIPO) or shifted out further through Q0 (SISO).
Universal shift register: each stage has a 4-to-1 multiplexer in front of its D input, controlled by select lines S1S0.
- 00: hold (D receives its own Q)
- 01: shift right (D receives Q of the left neighbour; the leftmost stage receives the serial right input)
- 10: shift left (D receives Q of the right neighbour; the rightmost stage receives the serial left input)
- 11: parallel load (D receives the external bit Ii)
Applications: serial communication, multiplying or dividing binary numbers by 2 through left or right shifts, time delays, ring and Johnson counters, and sequence generators.
Conclusion: The same chain of D flip-flops can act as storage, data converter, delay line or counter depending on how bits enter and leave. The universal shift register combines all these modes under two select lines.
3 Explain the construction and working of a 4-bit ripple (asynchronous) up counter. Show how a mod-10 ripple counter is obtained, and compare ripple and synchronous counters. 10 marks
A counter is a sequential circuit that passes through a fixed sequence of states on successive clock pulses. In a ripple (asynchronous) counter, only the first flip-flop receives the external clock. Every other flip-flop is clocked by the output of the previous stage, so a change ripples through the chain.
1. Construction: a 4-bit ripple up counter uses four negative-edge-triggered JK flip-flops with J = K = 1 (equivalently, T flip-flops with T = 1). Each one toggles on every falling edge at its clock input.
2. Working: FF0 toggles on every falling clock edge. FF1 toggles whenever Q0 falls from 1 to 0, FF2 whenever Q1 falls, and FF3 whenever Q2 falls. Reading Q3Q2Q1Q0, the count goes 0000, 0001, 0010, ..., 1111 and back to 0000, giving 16 states (mod-16). Each stage halves the frequency, so Q0, Q1, Q2 and Q3 run at f/2, f/4, f/8 and f/16. At the change 0111 → 1000, all four stages toggle one after another.
3. Down counter: if each stage is clocked by Q' of the previous stage, the sequence becomes 1111, 1110, ..., 0000.
4. Mod-10 (decade) ripple counter: four flip-flops are needed because 2^3 = 8 < 10 ≤ 16 = 2^4. The first state with both Q3 = 1 and Q1 = 1 is 1010 (decimal 10). A two-input NAND gate fed by Q3 and Q1 drives the active-low asynchronous CLEAR of all flip-flops. State 1010 therefore lasts only momentarily, and the counter shows 0000 to 1001.
5. Speed limit: each stage adds its propagation delay tpd, so the last output settles only after n × tpd. Hence fmax = 1/(n × tpd). For n = 4 and tpd = 20 ns, the settling time is 80 ns and fmax = 1/(80 × 10^-9 s) = 12.5 MHz.
6. Ripple versus synchronous counter:
- Clock: ripple applies it only to the first stage; synchronous applies it to all stages together.
- Hardware: ripple needs no extra gates; synchronous needs AND gating logic.
- Speed: ripple is slow and its delay grows with n; synchronous is fast.
- Glitches: ripple produces brief false states while bits ripple; synchronous does not.
Conclusion: Ripple counters are simple and economical for low-speed uses such as frequency division. Synchronous counters suit high-speed systems.
4 Design a 3-bit synchronous binary up counter using JK flip-flops. Show the excitation table, state table, simplified input equations and logic diagram. 10 marks
In a synchronous (parallel) counter, a common clock is applied to every flip-flop. Combinational logic at the flip-flop inputs decides which of them change at each edge. The design follows a standard procedure: state table, excitation table, simplification and logic diagram.
Step 1: Number of flip-flops. A 3-bit binary up counter has 8 states (000 to 111), so three flip-flops are needed: Q2 (MSB), Q1 and Q0 (LSB).
Step 2: JK excitation table.
- 0 → 0: J = 0, K = X
- 0 → 1: J = 1, K = X
- 1 → 0: J = X, K = 1
- 1 → 1: J = X, K = 0
Step 3: State table, written as present Q2Q1Q0 → next state : J2K2, J1K1, J0K0.
- 000 → 001 : 0X, 0X, 1X
- 001 → 010 : 0X, 1X, X1
- 010 → 011 : 0X, X0, 1X
- 011 → 100 : 1X, X1, X1
- 100 → 101 : X0, 0X, 1X
- 101 → 110 : X0, 1X, X1
- 110 → 111 : X0, X0, 1X
- 111 → 000 : X1, X1, X1
Step 4: Simplification with 3-variable K-maps (X = don't care).
- J0 and K0 are 1 or X in every state, so J0 = K0 = 1.
- J1 is 1 at 001 and 101, 0 at 000 and 100, and X elsewhere, so J1 = Q0.
- K1 is 1 at 011 and 111 and 0 at 010 and 110, so K1 = Q0.
- J2 is 1 only at 011 and X at 100 to 111. Grouping 011 with 111 gives J2 = Q1Q0.
- K2 is 1 only at 111 and X at 000 to 011. Grouping 111 with 011 gives K2 = Q1Q0.
Step 5: Logic diagram.
Step 6: Check.
- From 011: J0 = K0 = 1 toggles Q0 to 0; J1 = K1 = Q0 = 1 toggles Q1 to 0; J2 = K2 = Q1Q0 = 1 toggles Q2 to 1. The next state is 100, as required.
- From 111: all three flip-flops toggle, giving 000.
General rule: stage i toggles only when all lower bits are 1, so Ji = Ki = Q0·Q1·...·Q(i-1). A 4-bit counter adds J3 = K3 = Q2Q1Q0. With T flip-flops the result is T0 = 1, T1 = Q0, T2 = Q1Q0.
Conclusion: All flip-flops change together, so the settling time is about one flip-flop delay plus one AND-gate delay. This makes the synchronous counter faster than a ripple counter and free of ripple glitches.
5 Describe the functional units of a computer. Using the processor registers, explain the basic operational steps in executing an instruction such as Add LOCA, R0. 10 marks
A digital computer is built from five functional units that work on the stored-program (von Neumann) principle. Program instructions and data are held together in the same memory, and the instructions are fetched and executed one at a time.
1. Input unit: accepts coded information from devices such as a keyboard, mouse, scanner or network, and passes it in binary form to memory or the processor. 2. Memory unit: stores programs and data. Primary memory (RAM) consists of addressable words, each reachable in equal time. Cache is a small, fast memory close to the processor. Secondary memory (disks, SSDs) holds large volumes cheaply. 3. Arithmetic and logic unit (ALU): performs arithmetic and logic operations on operands kept in fast processor registers. 4. Output unit: sends results to monitors, printers, speakers and similar devices. 5. Control unit: produces the timing and control signals that coordinate all other units. It fetches, decodes and sequences instructions. The ALU and the control unit together form the processor (CPU).
Registers used:
- PC holds the address of the next instruction.
- IR holds the instruction being executed.
- MAR holds the address of the memory location to be accessed.
- MDR holds the word being read or written.
- R0 to Rn-1 are general-purpose registers that hold operands.
Steps for Add LOCA, R0 (R0 ← R0 + [LOCA]): 1. The contents of PC are copied to MAR, and a Read signal is sent to memory. 2. The instruction arrives in MDR and is moved to IR. PC is incremented to point to the next instruction. 3. The control unit decodes the instruction in IR. 4. Address LOCA is placed in MAR and a Read is issued. The operand arrives in MDR. 5. The ALU adds the contents of MDR and R0, and the sum is stored in R0. If a result had to be stored in memory, its address would go to MAR, the data to MDR, and a Write signal would be issued.
An I/O device may raise an interrupt. The processor then saves PC and its status, runs the interrupt-service routine, and resumes the program.
Conclusion: The five units, linked through registers and the stored-program idea, run every program as a repeated fetch-decode-execute cycle. Because instructions and data share one memory path, this design also suffers from the von Neumann bottleneck.
6 Explain single-bus and multiple-bus structures. Discuss the basic performance equation and the factors that improve computer performance, with a numerical example. 10 marks
The functional units of a computer must exchange data, addresses and control information. The group of lines that carries this information is called a bus, and the bus arrangement strongly affects performance.
1. Bus lines: a bus contains data lines, address lines and control lines (read/write, timing, interrupt). Only one unit can place information on a bus at a time.
2. Single-bus structure: the processor, memory, input and output units all share one common bus.
- Advantages: low cost, simple design, and new devices are easy to attach.
- Disadvantage: only two units can communicate at a time, so the bus becomes a bottleneck.
3. Multiple-bus structures: separate buses, such as a processor-memory bus and an I/O bus, or two or three internal CPU buses, allow several transfers at once. Speed rises, but so do cost and complexity.
4. Speed mismatch: devices differ greatly in speed. Buffer registers in the device interfaces hold data during transfers, so the fast processor does not have to wait for a slow device.
5. Performance: the key measure is the time taken to execute a program. The basic performance equation is T = (N × S)/R, where:
- N = number of machine instructions executed
- S = average clock cycles per instruction
- R = clock rate in cycles per second
6. Ways to improve performance:
- Raise R through better IC technology.
- Lower S through pipelining (overlapping fetch, decode and execute) and superscalar issue of several instructions per cycle.
- Lower N through a good compiler and a suitable instruction set. RISC uses simple instructions (larger N, smaller S); CISC uses complex ones (smaller N, larger S).
- Use cache memory so that most accesses avoid slow main memory.
7. Worked example: N = 5 × 10^8, S = 4, R = 2 GHz.
- T = (5 × 10^8 × 4)/(2 × 10^9) = (2 × 10^9)/(2 × 10^9) = 1 s.
- With pipelining, the effective S falls to 1.25: T = (5 × 10^8 × 1.25)/(2 × 10^9) = (6.25 × 10^8)/(2 × 10^9) = 0.3125 s.
- Speed-up = 1/0.3125 = 3.2.
8. Benchmarks: SPEC rating = running time on the reference computer / running time on the computer under test. The overall rating is the geometric mean of the ratings for all programs in the suite.
Conclusion: Bus organisation decides how many transfers can proceed at once. N, S and R together decide execution time, and a good design improves all three.
Computer Arithmetic and Processor Organization
Syllabus: Addition and subtraction of signed numbers; Design of fast adders; Multiplication of positive numbers; Signed-operand multiplication; Fast multiplication; Integer division; Floating-point numbers and operations; Fundamental concepts of processor organization; Execution of a complete instruction; Multiple-bus organization; Hardwired control; Microprogrammed control
One-page revision summary
- Addition and subtraction of signed numbers: in two's complement, X − Y is computed on the same n-bit adder by inverting Y with XOR gates and setting c0 = 1, giving X + Y′ + 1.
- Addition and subtraction of signed numbers: overflow can occur only when the two numbers added have the same sign, and it is detected when the carry into the sign bit differs from the carry out of it, V = c(n) ⊕ c(n−1).
- Design of fast adders: a ripple-carry adder makes c(n) available only after about 2n gate delays, whereas a 4-bit carry-lookahead block uses generate G(i) and propagate P(i) functions to form all carries in 3 gate delays and all sum bits in 4.
- Design of fast adders: for 16 or more bits, block generate and block propagate signals from 4-bit lookahead adders feed a second-level lookahead circuit, so wide adders stay fast without needing gates with very large fan-in.
- Multiplication of positive numbers: unsigned multiplication is shift-and-add, where each multiplier bit selects either the suitably shifted multiplicand or zero as a partial product, and two n-bit operands give a 2n-bit product.
- Multiplication of positive numbers (array multiplier): AND gates form each partial-product bit m(j)·q(i), and rows of full adders add these rows, so the whole product appears combinationally once the carries settle.
- Multiplication of positive numbers (sequential multiplier): with registers C and A cleared, M holding the multiplicand and Q the multiplier, each of n cycles adds M to A if q0 = 1 and then shifts C, A and Q right one bit, leaving the product in A and Q.
- Signed-operand multiplication: when the multiplicand is negative each partial product is sign-extended to 2n bits before adding, and when the multiplier is negative both operands can be complemented or Booth recoding can be used.
- Signed-operand multiplication (Booth algorithm): scanning the multiplier from right to left, the rightmost 1 of a run of 1s is recoded as −1 and the 0 just left of the run as +1, so a long run needs only one subtraction and one addition.
- Fast multiplication (bit-pair recoding): pairing Booth-recoded digits gives multiplier digits from −2 to +2, so at most n/2 summands are needed, each being 0, ±M or ±2M.
- Fast multiplication (carry-save addition): a row of full adders reduces three summands to a sum vector and a carry vector without carry propagation, and a tree of such levels reduces many summands to two, which one carry-lookahead adder then adds.
- Integer division (restoring): in each of n cycles A and Q are shifted left together, M is subtracted from A, and if A becomes negative q0 is set to 0 and M is added back, otherwise q0 is set to 1.
- Integer division (non-restoring): the restore step is removed by adding M instead of subtracting it in the next cycle whenever A is negative, with q0 set to 1 if A ≥ 0 and to 0 otherwise.
- Floating-point numbers: IEEE 754 single precision has a 1-bit sign S, an 8-bit exponent E′ stored in excess-127 form so that the actual exponent is E = E′ − 127, and a 23-bit fraction M with a hidden leading 1.
- Floating-point operations: add and subtract align exponents by shifting the smaller mantissa right, operate on the mantissas, then normalize and round using guard bits, while multiply adds exponents (removing one bias) and multiplies mantissas.
- Fundamental concepts of processor organization: the basic steps are register transfer, ALU operation, memory read and memory write, each controlled by gating signals such as Riin and Riout, with WMFC making the processor wait for slow memory.
- Execution of a complete instruction: every instruction begins with a common fetch phase (PC to MAR, PC incremented by 4, MDR to IR) followed by decode and execute steps; in a branch instruction the offset in IR is added to the updated PC, conditionally for conditional branches.
- Multiple-bus organization: a register file with two output ports and one input port, three buses A, B and C, and a separate PC incrementer let two operands be read and a result written in one clock cycle, reducing the number of control steps.
- Hardwired control: a step counter with step decoder, an instruction decoder and an encoder combine the timing step, the instruction in IR, condition codes and external inputs to produce control signals, which is fast but hard to modify.
- Microprogrammed control: control signals are stored as microinstructions (control words) in a control store and read in sequence using a microprogram counter μPC and a starting-address generator, which is flexible and easy to change but slower than hardwired control.
Learn these by heart
- Full adder: s(i) = x(i) ⊕ y(i) ⊕ c(i) and c(i+1) = x(i)y(i) + x(i)c(i) + y(i)c(i).
- Carry lookahead: G(i) = x(i)y(i), P(i) = x(i) ⊕ y(i), and c(i+1) = G(i) + P(i)c(i).
- Two's-complement overflow flag: V = c(n) ⊕ c(n−1).
- Booth recoding of bit pair (q(i), q(i−1)): 00 gives 0, 01 gives +1, 10 gives −1, 11 gives 0, with q(−1) = 0.
- Bit-pair recoded multiplier digits take only the values −2, −1, 0, +1 and +2.
- Carry-save adder cell: a full adder takes three bits of equal weight and outputs a sum bit of the same weight and a carry bit of the next higher weight.
- Non-restoring division: if A is negative after the last cycle, add M once more to obtain the correct remainder.
- After n division cycles the quotient is in register Q and the remainder is in register A.
- IEEE 754 single precision value = (−1)^S × 1.M × 2^(E′ − 127), where E′ is the stored biased exponent, and E′ = 0 and E′ = 255 are reserved for special values.
- IEEE 754 double precision uses a 1-bit sign, an 11-bit exponent with bias 1023 and a 52-bit mantissa.
- Single-bus fetch steps: PCout, MARin, Read, Select4, Add, Zin; then Zout, PCin, Yin, WMFC; then MDRout, IRin.
2-mark questions
1 When does overflow occur in two's-complement addition? Check whether 0101 + 0100 overflows in 4 bits. 2 marks
Overflow occurs when two operands of the same sign produce a result of the opposite sign. In hardware this is detected as c4 ⊕ c3 = 1, where c3 is the carry into the sign bit and c4 the carry out. Here 0101 (+5) + 0100 (+4) = 1001, which reads as −7. Since c3 = 1 and c4 = 0, overflow has occurred.
2 Define the generate and propagate functions used in a carry-lookahead adder. 2 marks
For bit stage i, the generate function Gi = xi·yi is 1 when the stage produces a carry by itself. The propagate function Pi = xi ⊕ yi (xi + yi also works) is 1 when an incoming carry is passed on. The carry is c(i+1) = Gi + Pi·ci, which can be expanded so that every carry depends only on the G and P terms and c0.
3 Multiply the unsigned numbers 1101 and 1011 by the shift-and-add method and state the product. 2 marks
The multiplier 1011 has 1s in positions 0, 1 and 3. So the multiplicand shifted by those amounts is added: 1101 + 11010 + 1101000, that is 13 + 26 + 104 = 143. The product is 10001111, which fits in 2n = 8 bits for n = 4-bit operands.
4 What is bit-pair recoding of the multiplier? 2 marks
Bit-pair recoding is a fast-multiplication technique. The Booth-recoded multiplier digits are grouped in pairs, and each pair is replaced by one equivalent digit from {−2, −1, 0, +1, +2}. An n-bit multiplier therefore needs at most n/2 summands (shifted multiples of ±M or ±2M), which halves the number of partial products.
5 State the roles of MAR and MDR in a processor. 2 marks
The Memory Address Register (MAR) holds the address of the memory location being accessed and drives the memory address lines. The Memory Data Register (MDR) holds the word being read from or written to memory. It connects both to the internal processor bus and to the memory data lines.
6 Distinguish horizontal and vertical microinstructions. 2 marks
In a horizontal microinstruction each control signal has its own bit. Words are long, little decoding is needed, and many operations can happen in parallel. In a vertical microinstruction, mutually exclusive signals are encoded into short fields that must be decoded. Words are compact but offer less parallelism and need extra decoder delay.
10-mark questions
1 Explain Booth's algorithm for signed-operand multiplication and show how it speeds up multiplication. Multiply M = +7 by Q = −3 using 4-bit two's-complement operands, showing every step. 10 marks
Booth's algorithm multiplies two's-complement numbers directly, without converting them to magnitudes. It also reduces the number of additions when the multiplier contains runs of 1s, so it serves both signed-operand multiplication and fast multiplication.
1. Recoding rule. Each multiplier bit Q0 is examined together with the bit on its right, Q−1. Q−1 is an extra flip-flop that is initially 0.
- Q0 Q−1 = 0 0 or 1 1: no arithmetic (digit 0)
- Q0 Q−1 = 1 0: A ← A − M (digit −1)
- Q0 Q−1 = 0 1: A ← A + M (digit +1)
After the arithmetic, A, Q and Q−1 are shifted right arithmetically by one place, copying the sign bit of A. For n-bit operands, n steps leave the 2n-bit product in A,Q.
2. Why it is faster. A run of 1s from bit i to bit j is worth 2^(j+1) − 2^i. The whole run therefore costs one subtraction and one addition instead of one addition per 1. Bit-pair recoding goes further: it merges Booth digits into single digits from {−2, −1, 0, +1, +2}, so at most n/2 summands are needed.
3. Worked example: M = 0111 (+7), −M = 1001, Q = 1101 (−3).
- Start: A = 0000, Q = 1101, Q−1 = 0
- Step 1: bits 1 0, so A = 0000 + 1001 = 1001. Shifting gives A = 1100, Q = 1110, Q−1 = 1.
- Step 2: bits 0 1, so A = 1100 + 0111 = 0011 (carry out dropped). Shifting gives A = 0001, Q = 1111, Q−1 = 0.
- Step 3: bits 1 0, so A = 0001 + 1001 = 1010. Shifting gives A = 1101, Q = 0111, Q−1 = 1.
- Step 4: bits 1 1, so no operation. Shifting gives A = 1110, Q = 1011, Q−1 = 1.
The product is A Q = 11101011. Its two's complement is 00010100 + 1 = 00010101 = 21, so the product is −21 = (+7) × (−3).
4. Check. 1101 with an appended 0 recodes to the digits 0, −1, +1, −1. Their value is −4 + 2 − 1 = −3, which matches the operations performed.
Conclusion: Booth's method treats positive and negative multipliers alike. Its recoding, and the bit-pair extension, reduces the number of summands, which makes it the basis of fast signed multipliers.
2 Describe the restoring division algorithm with its hardware arrangement. Divide 8 by 3 using 4-bit operands, showing each cycle, and explain how non-restoring division improves on it. 10 marks
Integer division of unsigned numbers is done in hardware by repeated shift and subtract, imitating long division. Restoring division is the simplest form of this method.
1. Hardware. An n-bit register Q holds the dividend and finally the quotient. An (n+1)-bit register A starts at 0 and finally holds the remainder. An (n+1)-bit register M holds the divisor; the extra bit is for the sign. An (n+1)-bit adder/subtractor and a control sequencer complete the unit.
2. Algorithm, repeated n times:
- Shift A and Q left by one bit.
- Compute A ← A − M.
- If A is negative (sign bit 1), set q0 = 0 and restore A ← A + M. Otherwise set q0 = 1.
3. Example: 8 ÷ 3 with n = 4. Start with Q = 1000, M = 00011, −M = 11101, A = 00000.
- Cycle 1: shift gives A = 00001, Q = 000_. A − M = 00001 + 11101 = 11110, which is negative, so q0 = 0 and A is restored to 00001. Q = 0000.
- Cycle 2: shift gives A = 00010, Q = 000_. A − M = 11111, which is negative, so q0 = 0 and A is restored to 00010. Q = 0000.
- Cycle 3: shift gives A = 00100, Q = 000_. A − M = 00100 + 11101 = 00001 (carry discarded), which is positive, so q0 = 1. Q = 0001 and A = 00001.
- Cycle 4: shift gives A = 00010, Q = 001_. A − M = 11111, which is negative, so q0 = 0 and A is restored to 00010. Q = 0010.
Result: quotient = 0010 = 2 and remainder = 00010 = 2. Check: 3 × 2 + 2 = 8.
4. Non-restoring division. The restore step wastes an addition. Restoring A and then shifting and subtracting gives 2(A + M) − M = 2A + M. That is the same as shifting the negative A and adding M, so the restore can be skipped:
- If A ≥ 0, shift A,Q left and subtract M. If A < 0, shift A,Q left and add M.
- Set q0 = 1 if the new A ≥ 0, else q0 = 0.
- After n cycles, if A is negative, add M once to correct the remainder.
Each cycle now needs exactly one addition or subtraction.
Conclusion: Restoring division produces one quotient bit per cycle using shift, subtract and a possible restore. Non-restoring division removes the restore operation and is therefore faster.
3 Explain how one n-bit adder performs both addition and subtraction of signed two's-complement numbers, including overflow detection. Then design a 4-bit carry-lookahead adder and compare its delay with a ripple-carry adder. 10 marks
In two's-complement form, X − Y = X + Y′ + 1, so one binary adder can both add and subtract. The speed of the adder is limited by carry propagation, and carry-lookahead logic reduces this delay.
1. Adder/subtractor. An n-bit ripple-carry adder is a chain of n full adders. Each bit yi passes through an XOR gate whose other input is the Add/Sub control line.
- Add/Sub = 0 passes yi unchanged and makes c0 = 0, so the circuit adds.
- Add/Sub = 1 inverts every yi and makes c0 = 1, so the circuit computes X + Y′ + 1 = X − Y.
2. Overflow. The result is wrong only when both operands have the same sign and the sum has the other sign. The hardware detects this as Overflow = c(n) ⊕ c(n−1). Example: 0110 (+6) + 1101 (−3) = 1 0011. The carry out is ignored, giving 0011 = +3. Here c4 = 1 and c3 = 1, so there is no overflow.
3. Ripple delay. Each full adder needs 2 gate delays to form its carry, so c(n) is ready after 2n gate delays. In a 4-bit adder, s3 appears after 7 delays and c4 after 8.
4. Lookahead equations. With Gi = xi·yi and Pi = xi ⊕ yi, c(i+1) = Gi + Pi·ci. Expanding this gives:
- c1 = G0 + P0c0
- c2 = G1 + P1G0 + P1P0c0
- c3 = G2 + P2G1 + P2P1G0 + P2P1P0c0
- c4 = G3 + P3G2 + P3P2G1 + P3P2P1G0 + P3P2P1P0c0
Each carry is a two-level AND-OR function of G, P and c0, so no carry waits for another.
5. Delay. All Gi and Pi take 1 gate delay. Every carry takes 2 more, so c1 to c4 are ready at 3 delays. Each sum si = Pi ⊕ ci takes 1 more, at 4 delays. This compares with 8 delays for c4 in the ripple design.
6. Larger adders. Each 4-bit block also outputs block signals P0^I = P3P2P1P0 and G0^I = G3 + P3G2 + P3P2G1 + P3P2P1G0. A second-level lookahead unit combines four such blocks. It produces c16 after 5 gate delays and s15 after 8, compared with 32 delays for c16 in a 16-bit ripple-carry adder.
Conclusion: An XOR-controlled adder handles signed addition and subtraction, with overflow given by c(n) ⊕ c(n−1). Carry-lookahead makes the addition time nearly independent of word length.
4 Explain the IEEE 754 single-precision floating-point format, including special values, and the steps for floating-point addition/subtraction and multiplication. Add 6.5 and 2.75 in binary floating point and give the IEEE single-precision bit pattern of the result. 10 marks
Floating-point representation stores very large and very small real numbers as a sign, a biased exponent and a normalized mantissa. The IEEE 754 standard fixes the layout of these fields.
1. Single-precision format (32 bits):
- Sign S: 1 bit (0 = positive, 1 = negative)
- Exponent E′: 8 bits in excess-127 form, so the actual exponent is E = E′ − 127
- Mantissa M: 23 bits; the leading 1 of the normalized significand is hidden
Value = (−1)^S × 1.M × 2^(E′ − 127). Normal numbers use E′ = 1 to 254, so E ranges from −126 to +127. Double precision uses 1, 11 (bias 1023) and 52 bits.
2. Special values:
- E′ = 0, M = 0: ±0
- E′ = 0, M ≠ 0: denormal number 0.M × 2^−126
- E′ = 255, M = 0: ±∞
- E′ = 255, M ≠ 0: NaN (not a number)
3. Addition and subtraction:
- Compare the exponents and shift the mantissa of the smaller number right by the difference.
- Use the larger exponent as the result exponent.
- Add or subtract the mantissas according to the signs, and set the result sign.
- Normalize the result, adjusting the exponent and checking for overflow or underflow.
- Round the mantissa to 23 bits.
4. Multiplication and division:
- Multiplication: add the exponents and subtract the bias (E′ = E′1 + E′2 − 127), multiply the mantissas, set sign = S1 ⊕ S2, then normalize and round.
- Division: subtract the exponents and add the bias, divide the mantissas, then normalize and round.
5. Guard bits and rounding. Extra bits are kept to the right of the mantissa during alignment and arithmetic. The result is then rounded by one of three methods:
- truncation;
- von Neumann rounding, which sets the LSB to 1 if any discarded bit is 1;
- round-to-nearest-even, which is the most accurate and is the IEEE default.
6. Example: 6.5 + 2.75.
- 6.5 = 110.1 = 1.1010 × 2^2
- 2.75 = 10.11 = 1.0110 × 2^1
- The exponent difference is 1, so 2.75 is aligned to 0.1011 × 2^2.
- Adding mantissas: 1.1010 + 0.1011 = 10.0101, giving 10.0101 × 2^2.
- Normalizing: 1.00101 × 2^3 = 1001.01 = 9.25, which is correct.
IEEE pattern: S = 0, E′ = 3 + 127 = 130 = 10000010, and M = 00101 followed by 18 zeros. The bits are 0 10000010 00101000000000000000000, which is 41140000 in hexadecimal.
Conclusion: Floating-point operations work on exponents and mantissas separately. Alignment, normalization and rounding are the key steps, and the hidden 1 and the bias make the format compact.
5 With a diagram, explain the single-bus organization of a processor and write the control sequence for executing Add (R3), R1. Show how a three-bus organization shortens execution of Add R4, R5, R6. 10 marks
An instruction is executed as a sequence of steps. In each step, control signals open register gates and select ALU and memory operations.
1. Fundamental operations. Every instruction is built from four basic operations:
- transferring a word between registers;
- performing an ALU operation and storing the result;
- fetching a word from memory into a register;
- storing a register into memory.
Memory access time varies, so the control step WMFC makes the processor wait for the Memory Function Completed (MFC) signal.
2. Single-bus organization.
Only one register may place data on the bus in a cycle.
3. Control sequence for Add (R3), R1, which performs R1 ← R1 + memory[R3]:
- Step 1: PCout, MARin, Read, Select4, Add, Zin
- Step 2: Zout, PCin, Yin, WMFC
- Step 3: MDRout, IRin
- Step 4: R3out, MARin, Read
- Step 5: R1out, Yin, WMFC
- Step 6: MDRout, SelectY, Add, Zin
- Step 7: Zout, R1in, End
Steps 1 to 3 fetch the instruction and add 4 to PC; they are the same for every instruction. Steps 4 to 7 fetch the operand, add it to R1 and store the result.
4. Three-bus organization. Buses A and B carry the source operands to the ALU, and bus C carries the result to its destination. The register file has two output ports and one input port, so two registers can be read and one written in a single cycle. PC has its own incrementer, and the ALU can pass either input straight through (R=A or R=B).
Control sequence for Add R4, R5, R6, which performs R6 ← R4 + R5:
- Step 1: PCout, R=B, MARin, Read, IncPC
- Step 2: WMFC
- Step 3: MDRoutB, R=B, IRin
- Step 4: R4outA, R5outB, SelectA, Add, R6in, End
The execute phase takes only one step, because both operands and the result move at the same time.
Conclusion: The single-bus design is simple and cheap but slow, since only one transfer happens per cycle. Multiple buses, a multi-port register file and a separate PC incrementer allow parallel transfers and reduce the number of steps per instruction.
6 Compare hardwired and microprogrammed control units. Explain the organization of each with diagrams, how control signals are generated, and the merits and drawbacks of each. 10 marks
The control unit generates the control signals for every step of every instruction. These signals can be produced by fixed logic circuits (hardwired control) or read from a memory of control words (microprogrammed control).
1. Hardwired control.
Each control signal is a sum-of-products expression of timing and instruction signals. For example:
- Zin = T1 + T6·ADD + T4·BR + ...
- End = T7·ADD + T5·BR + ...
When WMFC is active, Run becomes 0 and the counter freezes until MFC arrives.
2. Microprogrammed control.
A control word holds one bit, or one encoded field, for each control signal. The sequence of control words for one machine instruction is its microroutine. μPC normally increments, but it is loaded with a new address in three cases:
- when a new instruction is loaded into IR;
- when a branch microinstruction is met;
- when End is reached, which returns control to the fetch routine.
Microinstructions may be horizontal (long and parallel) or vertical (encoded and compact). Some designs place a next-address field in every microinstruction.
3. Comparison:
- Speed: hardwired control is faster; microprogrammed control needs a control-store read in every step.
- Flexibility: a microprogram can be changed by rewriting the control store, whereas hardwired logic must be redesigned.
- Complexity: hardwired logic grows complex and irregular for large instruction sets; microprogrammed control is systematic.
- Adding instructions: easy and cheap with microprogramming, costly with hardwired logic.
- Error correction: microcode errors are fixed in the store; hardwired errors need circuit changes.
- Typical use: hardwired control suits RISC processors with simple instructions; microprogramming suits CISC processors with complex instructions.
Conclusion: Hardwired control gives maximum speed at the cost of flexibility. Microprogrammed control gives a regular, easily modified design at some cost in speed, so the choice depends on instruction-set complexity and performance goals.
Memory Organization
Syllabus: Basic concepts of memory; Semiconductor RAM memories; Read-only memories; Speed, size and cost; Cache memories; Performance considerations; Virtual memories; Memory management requirements; Secondary storage
One-page revision summary
- A processor with a k-bit address can reach 2^k memory locations; data moves between the processor and memory through the MAR, the MDR and the control lines.
- Access time, cycle time and bandwidth are the basic measures of memory speed.
- SRAM uses latch cells that need no refresh and is used for caches; DRAM uses one-transistor-one-capacitor cells that need periodic refresh and is used for main memory.
- SDRAM works with a clock, and DDR SDRAM transfers data on both clock edges for higher bandwidth.
- ROM is non-volatile and holds firmware such as boot programs; in each ROM cell, the presence or absence of a connection decides whether it reads 0 or 1.
- PROM is programmed once, EPROM is erased by UV light, and EEPROM is erased electrically; flash memory is erased in blocks and is used in memory cards and SSDs.
- Moving down the hierarchy from registers through cache and main memory to disk, cost per bit falls, size grows and access time increases.
- Locality of reference, both temporal and spatial, is what makes the memory hierarchy and caches effective.
- Cache mapping can be direct, associative or set-associative; LRU, FIFO or random policies choose the block to replace.
- A write-through cache updates main memory on every write; a write-back cache uses a dirty bit and updates memory only when the block is evicted.
- Performance improves by raising the hit rate and lowering the miss penalty, using interleaving, load-through, write buffers, prefetching and multi-level caches.
- Virtual memory uses paging, page tables and a TLB to translate virtual addresses; a page fault makes the OS load the missing page from disk.
- Memory management must provide relocation, protection, sharing, logical organization and physical organization.
- Disk access time is the sum of seek time, rotational latency and transfer time; optical discs, tapes and SSDs are other forms of secondary storage.
Learn these by heart
- Average access time: tavg = hC + (1 − h)M, where h is the hit rate, C the cache access time and M the miss penalty.
- Two-level cache: tavg = h1C1 + (1 − h1)h2C2 + (1 − h1)(1 − h2)M.
- Direct mapping: cache block = j mod (number of cache blocks); set-associative mapping: set = j mod (number of sets); word field = log2(block size).
- Disk access time = seek time + rotational latency + transfer time; average rotational latency = half a revolution = 30/rpm seconds.
- Physical address = page frame number concatenated with the page offset; offset bits = log2(page size).
- A k-bit address gives 2^k addressable locations.
2-mark questions
1 Define memory access time and memory cycle time. 2 marks
Memory access time is the time between the start of a read operation and the moment the requested data is available at the memory output. Memory cycle time is the minimum time between the starts of two successive memory operations. Cycle time is usually longer than access time because the memory needs some recovery time after each access.
2 Differentiate between static RAM and dynamic RAM. 2 marks
SRAM stores each bit in a latch of cross-coupled inverters (about six transistors). It keeps data as long as power is on and is fast but costly, so it is used for caches. DRAM stores a bit as charge on a capacitor with one transistor. It needs periodic refreshing and is slower, but it is denser and cheaper, so it is used for main memory.
3 What are PROM, EPROM and EEPROM? 2 marks
A PROM can be programmed once by the user, by blowing fuses. An EPROM can be erased by exposing the chip to ultraviolet light and then reprogrammed. An EEPROM can be erased and rewritten electrically while it stays in the circuit, and individual cells can be erased selectively. Flash memory is a variant of EEPROM that is erased in blocks.
4 A cache has an access time of 10 ns and main memory has an access time (miss penalty) of 100 ns. If the hit ratio is 0.9, find the average memory access time. 2 marks
Use tavg = hC + (1 − h)M, where h is the hit ratio, C is the cache access time and M is the miss penalty.
tavg = 0.9 × 10 + 0.1 × 100 = 9 + 10 = 19 ns.
The average memory access time is 19 ns.
5 What is a translation lookaside buffer (TLB)? 2 marks
A TLB is a small, fast associative cache inside the memory management unit. It holds recently used page-table entries, each mapping a virtual page number to a page frame number. When the virtual page number is found in the TLB, the physical address is formed at once, so the slow page-table access in main memory is avoided.
6 A magnetic disk spins at 7200 rpm. Find its average rotational latency. 2 marks
One rotation takes 60/7200 s = 8.33 ms. On average the required sector is half a revolution away from the head.
Average rotational latency = 8.33/2 ≈ 4.17 ms.
Rotational latency is the time spent waiting for the required sector to rotate under the read/write head.
10-mark questions
1 Explain the basic concepts of memory and the memory hierarchy. Discuss how speed, size and cost influence the design of the memory system. 10 marks
A memory unit stores the programs and data that the processor works on. This answer first explains the basic concepts of memory. It then shows why a hierarchy is built from devices that differ in speed, size and cost.
Basic concepts: 1. Addressable space: with a k-bit address the processor can reach 2^k locations. In a byte-addressable machine a 32-bit address gives 2^32 bytes = 4 GB. The word length is the number of bits moved in one transfer, which equals the n lines of the data bus. 2. Processor–memory link: the processor places the address in the MAR, which drives the address bus. Data moves through the MDR over the data bus. Control lines carry the Read/Write signal and a Memory-Function-Completed (MFC) signal. 3. Speed measures: memory access time is the time from a request until the data is available. Memory cycle time is the minimum gap between two successive operations. Bandwidth is the number of bits transferred per second. 4. Random access: any location can be reached in the same time whatever its address. Sequential devices such as tape do not have this property.
Speed, size and cost:
- Fast memories cost more per bit, so they are built small.
- SRAM is the fastest and the most expensive.
- DRAM is slower but dense and cheap.
- Disks and SSDs are very cheap per bit, but their access times are in microseconds to milliseconds.
No single technology is fast, large and cheap at once, so a hierarchy is used.
Working of the hierarchy: 1. Registers hold the operands of the current instruction. 2. The L1 cache inside the processor holds recently used instructions and data. The L2 and L3 caches are larger and slightly slower. 3. Main memory holds the active parts of programs. 4. Secondary storage holds all programs and files. With virtual memory it also holds the pages that are not currently in main memory. 5. Blocks move automatically between adjacent levels. Hardware handles cache–memory transfers, and the operating system handles memory–disk transfers.
The hierarchy works because of locality of reference:
- Temporal locality: a recently used item is likely to be used again soon.
- Spatial locality: items near a used item are likely to be used soon.
Because of locality, most accesses are satisfied by the fast upper levels.
Conclusion: The memory hierarchy gives the processor an apparent memory that is almost as fast as the cache and almost as large and cheap per bit as the disk.
2 Explain the internal organization of a semiconductor RAM chip with a 1K × 1 example. Describe the working of a static RAM cell and a dynamic RAM cell. 10 marks
A semiconductor RAM chip stores bits in an array of cells, one bit per cell. Decoders and sense/write circuits on the chip select the cells and access them.
1. Array organization: the cells are arranged in rows and columns.
- All cells in a row share a word line, which is driven by the address decoder.
- All cells in a column share a pair of bit lines, which lead to a sense/write circuit.
- In a read, the selected word line is activated and the sense circuits output the stored bits.
- In a write, the sense/write circuits drive the input data onto the bit lines.
2. Example 16 × 8 chip: 16 words of 8 bits need 4 address lines and 8 data lines, plus R/W and Chip Select (CS). Adding power and ground, the chip has 4 + 8 + 2 + 2 = 16 pins.
3. Example 1K × 1 chip: the 1024 cells are placed as a 32 × 32 array, and the 10-bit address is split into two parts.
- 5 bits select one of 32 rows through a row decoder.
- 5 bits select one of 32 columns through a multiplexer.
- Pins: 10 address + 1 data + R/W + CS + power + ground = 15.
4. Static RAM cell: two cross-coupled inverters form a latch. The latch connects to bit lines b and b′ through transistors T1 and T2, whose gates are driven by the word line.
- When the word line is low, T1 and T2 are off and the latch holds its state.
- To read, the word line is raised and the sense circuit compares b with b′.
- To write, b is driven to the new value and b′ to its complement, and then the word line is raised.
SRAM needs no refresh and is very fast, so it is used for caches.
5. Dynamic RAM cell: one transistor and one capacitor.
- Writing turns the transistor on, which charges or discharges the capacitor.
- Reading turns the transistor on. A sense amplifier checks whether the charge is above a threshold and then rewrites the full value.
- The charge leaks away, so every row must be refreshed periodically, within a period of tens of milliseconds (typically every 64 ms or less in standard modern DRAM).
- To save pins, row and column addresses share the same lines and are latched by the RAS and CAS strobes.
- Synchronous DRAMs work with a clock. DDR SDRAMs transfer data on both clock edges.
Conclusion: SRAM gives speed and DRAM gives density at low cost. The row–column organization lets large memories be built from these simple cells.
3 Explain direct, associative and set-associative mapping functions of a cache. A main memory has 64K words and a cache of 2K words with a block size of 16 words. Show the address format for each mapping (use 4-way for set-associative) and locate the address 1234 (hex). 10 marks
A cache is a small, fast memory placed between the processor and main memory. A mapping function decides where a main-memory block may be placed in the cache. The processor address is divided into fields according to that function.
Given data:
- Main memory = 64K words, so the address is 16 bits.
- Block = 16 words, so the word field = log2 16 = 4 bits.
- Cache blocks = 2048/16 = 128.
- Main-memory blocks = 65536/16 = 4096.
- The address 1234h lies in memory block 1234h/16 = 123h = 291, at word 4.
1. Direct mapping: block j of main memory can go only to cache block (j mod 128).
- Block field = 7 bits, so Tag = 16 − 7 − 4 = 5 bits.
- Format: Tag 5 | Block 7 | Word 4.
- For 1234h: cache block = 291 mod 128 = 35 and tag = 291 div 128 = 2.
- The tag stored with cache block 35 is compared with 2. A match with valid bit = 1 is a hit.
- This method is simple and cheap. However, blocks that map to the same cache block keep evicting each other.
2. Associative mapping: any block can be placed in any cache block.
- Format: Tag 12 | Word 4.
- All 128 stored tags are compared in parallel. For 1234h the tag is 291.
- This gives the best flexibility and hit rate, but the parallel comparison hardware is costly.
3. 4-way set-associative mapping: the 128 blocks form 128/4 = 32 sets of 4 blocks each. Block j may occupy any block of set (j mod 32).
- Set field = 5 bits, so Tag = 16 − 5 − 4 = 7 bits.
- Format: Tag 7 | Set 5 | Word 4.
- For 1234h: set = 291 mod 32 = 3 and tag = 291 div 32 = 9. Only the 4 tags of set 3 are compared.
- Direct mapping is the 1-way case of this scheme, and associative mapping is the 128-way case.
4. Control bits and replacement:
- Each cache block has a valid bit.
- A write-back cache also keeps a dirty bit for each block.
- When a set is full, the block to be replaced is chosen by LRU, FIFO or random replacement.
- Direct mapping needs no such choice, because each block has only one possible place.
Conclusion: Set-associative mapping keeps the comparison hardware small while removing most of the conflicts of direct mapping. This balance is why it is widely used.
4 What is virtual memory? Explain address translation using paging, the page table and the TLB, and the handling of a page fault. Relate the scheme to the requirements of memory management. 10 marks
Virtual memory lets programs use an address space larger than the physical main memory. The processor generates virtual addresses, and the memory management unit (MMU) translates them into physical addresses. Parts of a program that are not in main memory stay on disk and are brought in when needed.
Memory management requirements:
- Relocation: a program may be placed anywhere in physical memory, so addresses must be translated at run time.
- Protection: a process must not access another process's area, so access-rights bits are checked on each reference.
- Sharing: processes may share code or data pages in a controlled way.
- Logical organization: memory should support program modules, such as segments.
- Physical organization: transfers between memory and disk must be automatic, not left to the programmer.
Paging and address translation: 1. Virtual and physical memory are divided into equal-sized pages and page frames, for example 4 KB each. 2. A virtual address consists of a virtual page number (the high bits) and an offset (the low bits). With 32-bit addresses and 4 KB pages, the offset is 12 bits and the page number is 20 bits, so the page table can have 2^20 entries. 3. The page table base register holds the start of the page table. The page number added to this base locates the page table entry. 4. Each entry holds the page frame number and control bits: a valid bit, a modified (dirty) bit and access-rights bits. 5. The physical address is the frame number joined with the unchanged offset. 6. The page table is in main memory, so reading it is slow. A small associative cache, the TLB, keeps recent entries. A TLB hit supplies the frame number at once.
7. Page fault: if the valid bit is 0, the following steps take place.
- The MMU raises an exception and the OS suspends the process.
- The OS selects a frame, using an LRU-like policy, and writes the old page back to disk if it is dirty.
- The OS reads the required page from disk and updates the page table.
- The faulting instruction is restarted.
Conclusion: Paging with a TLB meets the requirements of relocation, protection, sharing and automatic physical organization while keeping address translation fast.
5 Discuss the performance considerations of a memory system. A cache uses 8-word blocks. Sending an address to main memory takes 1 clock cycle. The first word of a block is accessed in 6 cycles and each later word from the same module in 3 cycles, and one word is transferred to the cache in 1 cycle. Find the block-load time without interleaving and with four interleaved modules. With a hit rate of 0.95 and a cache access time of 1 cycle, find the average access time in each case. 10 marks
Memory performance depends on how quickly the processor receives instructions and data. Two quantities are central:
- The hit rate h, the fraction of accesses found in the cache.
- The miss penalty M, the time to bring a block from main memory.
With cache access time C, the average access time is tavg = hC + (1 − h)M.
Ways to improve performance:
- Memory interleaving: consecutive words are placed in different modules, so their accesses overlap.
- Larger caches and a suitable block size raise h.
- Load-through: the requested word is forwarded to the processor as soon as it arrives.
- Write buffers, prefetching and lockup-free caches hide memory delay.
- Two-level caches: tavg = h1C1 + (1 − h1)h2C2 + (1 − h1)(1 − h2)M.
Calculation:
(a) One module, no interleaving: 1. Send the address: 1 cycle. 2. Access the first word: 6 cycles. 3. Access the remaining 7 words: 7 × 3 = 21 cycles. Each word's transfer overlaps with the access of the next word. 4. Transfer the last word: 1 cycle.
M = 1 + 6 + 21 + 1 = 29 cycles.
(b) Four interleaved modules, each supplying 2 words: 1. Send the address: 1 cycle. 2. All four modules access their first word in parallel: 6 cycles. 3. Transfer these 4 words: 4 cycles. Meanwhile, each module accesses its second word in 3 cycles, which is within this period. 4. Transfer the second 4 words: 4 cycles.
M = 1 + 6 + 4 + 4 = 15 cycles.
(c) Average access time with h = 0.95 and C = 1:
- Without interleaving: tavg = 0.95 × 1 + 0.05 × 29 = 0.95 + 1.45 = 2.40 cycles.
- With interleaving: tavg = 0.95 × 1 + 0.05 × 15 = 0.95 + 0.75 = 1.70 cycles.
- Improvement = 2.40/1.70 ≈ 1.41 times.
Conclusion: Interleaving cuts the miss penalty from 29 to 15 cycles, which lowers the average access time from 2.40 to 1.70 cycles. Good performance therefore needs both a high hit rate and a small miss penalty.
6 Describe the organization of a magnetic disk and the components of disk access time. A disk has 4 platters (8 recording surfaces), 20,000 tracks per surface, 400 sectors per track and 512 bytes per sector. It rotates at 6000 rpm and has an average seek time of 6 ms. Find its capacity, the average time to read one sector, and the maximum transfer rate. Also mention other secondary storage devices. 10 marks
Magnetic disks are the main form of secondary storage. They are non-volatile, large and very cheap per bit, but much slower than main memory.
Organization: 1. One or more platters are fixed to a spindle that rotates at constant speed. Each surface is magnetically coated and has its own read/write head on an access arm. 2. Each surface is divided into concentric tracks, and each track into sectors separated by gaps. A sector holds a header, the data and an error-correcting code. 3. The tracks at the same arm position on all surfaces form a cylinder. Data within one cylinder can be read without moving the arm. 4. A disk controller handles commands, buffering, error checking and DMA transfers to memory.
Access time = seek time (moving the head to the track) + rotational latency (waiting for the sector to arrive) + transfer time.
Calculation:
(a) Capacity = 8 × 20,000 × 400 × 512 bytes = 64,000,000 sectors × 512 bytes = 32,768,000,000 bytes ≈ 32.8 GB.
The disk has 20,000 cylinders of 8 tracks each.
(b) Time to read one sector:
- One revolution = 60/6000 s = 10 ms.
- Average rotational latency = 10/2 = 5 ms.
- Time to transfer one sector = 10 ms/400 = 0.025 ms.
- Average access time = 6 + 5 + 0.025 = 11.025 ms.
(c) Maximum transfer rate:
- Bytes per track = 400 × 512 = 204,800.
- One track passes under the head in one revolution, so the rate = 204,800 bytes/10 ms = 20,480,000 bytes/s ≈ 20.48 MB/s.
Other secondary storage:
- Optical discs (CD, DVD, Blu-ray): data is stored as pits and lands along a single spiral track and read by a laser. They are cheap and removable but slow.
- Magnetic tape: sequential access only, used for backup and archives.
- Flash-based SSDs: no moving parts, so there is no seek time or rotational latency. They are faster and more rugged but cost more per bit.
Conclusion: In a disk access, the seek time and rotational latency of about 11 ms are far larger than the 0.025 ms transfer time. Data should therefore be read in large sequential blocks, and caching and SSDs are used to hide this delay.
Input/Output Organization
Syllabus: Accessing I/O devices; Interrupts; Processor examples; Direct memory access; Buses; Interface circuits; Standard I/O interfaces
One-page revision summary
- I/O devices connect to a shared bus through interface circuits that decode addresses and hold data and status registers.
- In memory-mapped I/O, device registers share the memory address space; isolated I/O uses a separate space with IN/OUT instructions.
- Program-controlled I/O polls status flags such as SIN and SOUT, which wastes processor time in busy waiting.
- An interrupt suspends the current program after the current instruction, saves the PC and PS, and runs an interrupt-service routine.
- Interrupts are controlled by an enable bit in the processor status register and by enable bits in each device interface.
- The source of an interrupt is found by polling or by vectored interrupts, and priority is set by separate levels or a daisy chain.
- Exceptions include I/O interrupts as well as error recovery, debugging (trace and breakpoints) and privilege violations.
- ARM provides IRQ and FIQ inputs masked by the I and F bits of the CPSR, with vectors at 0x18 and 0x1C and banked registers for FIQ.
- The 68000 uses a 3-bit interrupt mask with seven priority levels, level 7 being non-maskable.
- IA-32 processors use the IF flag (CLI/STI), a 256-entry interrupt table and the IRET instruction.
- A DMA controller moves blocks between a device and memory using starting-address, word-count and status/control registers, and interrupts the processor at the end.
- DMA works either by cycle stealing (single bus cycles) or in burst mode (the bus is held for a whole block).
- Bus arbitration chooses one master at a time, either centrally with BR, BG and BBSY or in a distributed way by comparing device IDs.
- A synchronous bus uses a common clock, while an asynchronous bus uses a Master-ready/Slave-ready full handshake.
- Parallel interfaces use DATAIN/DATAOUT with SIN/SOUT flags; serial interfaces add shift registers and double buffering.
- PCI is a processor-independent burst bus with multiplexed address/data lines and a configuration space for plug-and-play.
- SCSI connects storage devices as initiators and targets, with arbitration, selection and disconnect/reselect phases.
- USB is a polled, hot-pluggable tree of hubs with 7-bit addresses and speeds of 1.5, 12 and 480 Mb/s.
Learn these by heart
- Polling rule: wait until SIN = 1, then read DATAIN (which clears SIN); wait until SOUT = 1, then write DATAOUT (which clears SOUT).
- Interrupt sequence: finish the current instruction → save PC and PS → disable interrupts → acknowledge → jump to the ISR → return restores PC and PS.
- Interrupt latency = the time from activation of the interrupt request to the start of the interrupt-service routine.
- DMA controller registers: starting address, word count, and status/control (R/W, Done, IE, IRQ).
- Asynchronous full handshake: Master-ready ↑ → Slave-ready ↑ → Master-ready ↓ → Slave-ready ↓.
- ARM: IRQ vector 0x18 and FIQ vector 0x1C; the I and F bits of the CPSR mask them; return from IRQ with SUBS PC, LR, #4.
- USB address = 7 bits, so 2^7 − 1 = 127 devices; speeds 1.5, 12 and 480 Mb/s.
2-mark questions
1 Distinguish between memory-mapped I/O and I/O-mapped (isolated) I/O. 2 marks
In memory-mapped I/O, device registers occupy addresses in the memory address space, so ordinary load, store or move instructions access them. In I/O-mapped I/O, devices have a separate address space. Special IN and OUT instructions, together with a control signal, select it. Memory space is not reduced, but extra instructions are needed.
2 What is a vectored interrupt? 2 marks
In a vectored interrupt, the interrupting device identifies itself by sending a code, the interrupt vector, to the processor over the bus. The processor uses this code to locate the starting address of that device's interrupt-service routine directly. It therefore does not need to poll every device to find the source.
3 Define cycle stealing in DMA. 2 marks
Cycle stealing is a DMA transfer mode in which the DMA controller takes the memory bus for one bus cycle at a time to move a single word. Its memory accesses are interleaved with those of the processor. The processor is slowed slightly but is never stopped for a long period.
4 Differentiate between a synchronous bus and an asynchronous bus. 2 marks
A synchronous bus times every transfer step from a common clock line, so each step takes a fixed number of clock periods. It is simple, but the slowest device and clock skew limit its speed. An asynchronous bus has no common clock. It uses Master-ready and Slave-ready handshake signals, so each transfer adapts to the delays of the device.
5 List the main functions of an I/O interface circuit. 2 marks
An I/O interface circuit performs these functions:
- It decodes the address lines to recognise its own addresses.
- It provides data registers (DATAIN, DATAOUT) to buffer data.
- It holds status flags such as SIN and SOUT for the processor to test.
- It generates bus control and timing signals.
- It performs any format conversion, for example parallel-to-serial.
6 State any four features of the Universal Serial Bus (USB). 2 marks
Four features of USB are:
- It is hot pluggable, so devices can be connected or removed while the computer runs.
- It is plug-and-play, so devices are configured automatically.
- It uses a tree of hubs with a 7-bit address, allowing up to 127 devices.
- It supports low (1.5 Mb/s), full (12 Mb/s) and high (480 Mb/s) speeds, and the cable can supply power to small devices.
10-mark questions
1 Explain how a processor accesses I/O devices. Distinguish memory-mapped I/O from I/O-mapped I/O, and describe program-controlled I/O with an example that reads characters from a keyboard and echoes them to a display. 10 marks
A computer exchanges data with keyboards, displays, disks and printers. To do this, the processor must be able to address each device, check whether it is ready, and move data to or from it. Together these operations are called accessing I/O devices.
1. Single-bus organisation. The processor, the main memory and all I/O devices share one bus made of address, data and control lines. Each device is connected through an interface circuit. The interface watches the address lines, recognises its own address and responds to the command on the control lines.
2. Memory-mapped I/O. Device registers such as DATAIN and DATAOUT are given addresses inside the memory address space. Ordinary Move or Load/Store instructions therefore access them, and no special instructions are needed. The cost is that part of the address space is used up.
3. I/O-mapped (isolated) I/O. Devices have their own address space. Special IN and OUT instructions activate a control line that tells the interfaces the address refers to I/O. Memory space is not reduced, and address decoding needs fewer lines.
4. Program-controlled I/O. The processor repeatedly tests a status flag until the device is ready.
- For a keyboard, SIN = 1 means a character is waiting in DATAIN, and reading DATAIN clears SIN.
- For a display, SOUT = 1 means it can accept a character, and writing DATAOUT clears SOUT.
READ: if SIN = 0 go to READ ; wait for a key
R0 ← DATAIN ; SIN cleared
WRITE: if SOUT = 0 go to WRITE ; wait for display
DATAOUT ← R0 ; echo character
[R1] ← R0 ; R1 ← R1 + 1 ; store in buffer
if R0 ≠ CR go to READ ; stop at carriage return5. Drawback. While it waits in the loops, the processor does no useful work. This is called busy waiting. Because devices are much slower than the processor, most of its time is wasted.
In conclusion, devices are reached either through the memory address space or through a separate I/O space. The simplest transfer method is program-controlled I/O with status polling. Its inefficiency is what leads to the use of interrupts and direct memory access.
2 What is an interrupt? Explain the steps in handling an interrupt request, how interrupts are enabled and disabled, and how several devices are handled. Illustrate with the interrupt mechanism of the ARM processor. 10 marks
An interrupt is a hardware signal, the interrupt request (IRQ), that a device sends to the processor to ask for service. With interrupts, the processor does useful work and attends to a device only when the device is ready, instead of polling it.
1. Handling one interrupt.
- The device activates the interrupt-request line.
- The processor completes the instruction it is currently executing.
- If interrupts are enabled, it saves the program counter and the processor status register.
- It disables interrupts, sends an interrupt-acknowledge signal and loads the PC with the address of the interrupt-service routine (ISR).
- The ISR services the device and makes it remove its request, for example by reading its data register.
- A return-from-interrupt instruction restores the PS and PC, and the interrupted program resumes.
The delay between the request and the start of the ISR is called the interrupt latency.
2. Enabling and disabling. An interrupt-enable bit in the processor status register is cleared automatically when an interrupt is accepted and restored on return. This stops a request that is still active from causing endless repeated interrupts. Edge-triggered request lines give the same protection. Each device interface also has its own enable bit, so software can choose which devices may interrupt.
3. Several devices.
- Polling: the ISR reads the IRQ bit in each device's status register to find the source.
- Vectored interrupts: the device sends a code that selects its ISR directly.
- Priority: separate request lines can be provided for each priority level. Alternatively, a daisy chain on the acknowledge line gives priority to the device electrically nearest the processor.
- Nesting: a higher-priority device may interrupt a lower-priority ISR.
4. Example: the ARM processor. ARM has two interrupt inputs, IRQ (normal) and FIQ (fast). The I and F bits in the current program status register (CPSR) mask them. On accepting an IRQ, the processor:
- copies CPSR into SPSR_irq and the return address into the banked link register LR_irq,
- switches to IRQ mode and sets I = 1,
- branches to the vector address 0x18 (FIQ uses 0x1C).
FIQ mode has its own banked registers R8 to R14, so a fast handler can work without saving them. An IRQ handler returns with SUBS PC, LR, #4, which also restores CPSR from SPSR.
Other processors use similar ideas:
- The 68000 uses a 3-bit priority mask with seven interrupt levels.
- IA-32 uses the IF flag and a table of 256 interrupt vectors.
In conclusion, interrupts remove busy waiting. Correct operation needs context saving, controlled enabling, identification of the source and priority resolution, as the ARM design shows.
3 Explain Direct Memory Access (DMA). Describe the registers of a DMA controller, the sequence of a DMA block transfer, cycle stealing and burst mode, and the bus arbitration needed when several masters share the bus. 10 marks
Fast devices such as disks and network interfaces move large blocks of data. Passing each word through the processor, with an interrupt per word, is too slow. In direct memory access (DMA), a DMA controller transfers the whole block directly between the device and main memory. The processor is involved only at the start and the end of the block.
1. Registers of a DMA controller.
- Starting-address register: the memory address of the next word to transfer.
- Word-count register: the number of words still to be transferred.
- Status and control register: an R/W bit for the direction, a Done flag, an interrupt-enable (IE) bit, and an IRQ bit set when the controller has requested an interrupt.
2. Sequence of a transfer.
- The operating system writes the starting address, the word count and the direction into the controller, then starts it.
- The controller requests the bus. When the bus is granted, it puts addresses on the bus and moves words, incrementing the address and decrementing the count after each word.
- When the count reaches zero, it sets Done and, if IE = 1, interrupts the processor.
- Meanwhile the processor executes other programs.
3. Cycle stealing and burst mode. DMA requests usually have priority over processor accesses to memory.
- Cycle stealing: the controller takes single bus cycles between processor accesses, so the processor is only slightly slowed.
- Burst (block) mode: the controller keeps the bus for a whole block and transfers it at full speed, while the processor waits for memory.
4. Bus arbitration. The processor and the DMA controllers can all become bus masters, so one must be chosen at a time.
- Centralised arbitration: a device asserts Bus-Request (BR). The arbiter, often inside the processor, asserts Bus-Grant, which passes along a daisy chain. The first requesting device keeps the grant, asserts Bus-Busy (BBSY) while it uses the bus, and then releases it.
- Distributed arbitration: each device has a unique ID. Competing devices drive their IDs onto shared open-collector lines and compare them bit by bit. A device that sees a 1 where it has a 0 withdraws its lower bits, so the highest ID wins without a central arbiter.
In conclusion, DMA moves blocks with very little processor overhead, and bus arbitration lets the processor and DMA controllers share the bus in an orderly way.
4 Explain the operation of synchronous and asynchronous buses with the help of timing descriptions for an input (read) transfer. Compare the two schemes. 10 marks
A bus is a set of shared data, address and control lines that connects the processor, memory and I/O devices. The bus protocol fixes when each signal is placed on the bus and when it is sampled. There are two schemes, synchronous and asynchronous.
1. Synchronous bus. All devices take their timing from a common clock line. A read transfer completed in one clock cycle, from t0 to t2, proceeds as follows.
- At t0 the master places the device address and the Read command on the bus.
- The signals propagate and are decoded, and the addressed slave places its data on the data lines.
- At t2 the master strobes the data into its input buffer.
The clock period must allow for propagation delay, decoding and set-up time of the slowest device, so fast devices are held back. A common improvement spreads a transfer over several clock cycles. The slave then asserts a Slave-ready signal when its data is valid, so devices of different speeds can share the bus.
2. Asynchronous bus. There is no common clock. A handshake between the Master-ready and Slave-ready lines times each step of a read.
- t0: the master puts the address and command on the bus.
- t1: after allowing for skew and decoding, the master asserts Master-ready.
- t2: the addressed slave puts its data on the bus and asserts Slave-ready.
- t3: when Slave-ready arrives, and after a skew allowance, the master strobes the data and negates Master-ready.
- t4: the master removes the address and command.
- t5: seeing Master-ready drop, the slave removes the data and negates Slave-ready.
Each change on one side answers a change on the other side, so this is called a full handshake.
3. Comparison.
- Timing: a synchronous bus uses a clock; an asynchronous bus uses handshake signals.
- Speed: a synchronous bus is fast for short buses and simple logic, but is limited by the slowest device and by clock skew. An asynchronous bus adapts to each device's speed, but every transfer needs signals to travel both ways.
- Hardware: a synchronous bus has simpler interfaces. An asynchronous bus needs extra control lines and more complex interfaces.
- Flexibility: an asynchronous bus tolerates varying delays and device technologies better.
In conclusion, synchronous buses suit fast, closely matched devices, while asynchronous buses favour mixed device speeds. Many practical buses combine a clock with ready signals to get the advantages of both.
5 Explain the design and working of interface circuits for a parallel input device (keyboard), a parallel output device (printer) and a serial port. 10 marks
An interface circuit connects an I/O device to the bus. It decodes addresses, holds data and status, produces control signals and may convert data formats. A parallel interface moves several bits at a time over a short distance. A serial interface moves one bit at a time over a single line.
1. Parallel input interface (keyboard).
- The key switches feed an encoder with a debouncing circuit. When a key is pressed, it produces an 8-bit character code and a Valid pulse.
- Valid loads the code into the DATAIN register and sets the status flip-flop SIN.
- The processor reads the status register, where SIN is bit 0. When SIN = 1, it reads DATAIN.
- The address decoder and the Read signal gate DATAIN or the status bits onto the data lines through tri-state drivers. Reading DATAIN clears SIN.
- If interrupts are enabled, SIN = 1 can also activate the interrupt-request line.
2. Parallel output interface (printer).
- The processor writes a character into DATAOUT. This clears the SOUT flag and activates a New-data signal to the printer.
- When the printer has taken the character and is ready again, it asserts Idle, which sets SOUT.
- The processor tests SOUT before writing the next character, so SOUT plays the same role for output that SIN plays for input.
3. Serial interface.
- An input shift register receives bits one at a time. When a full character has arrived, it is transferred in parallel to DATAIN and SIN is set.
- For output, the processor loads DATAOUT. The character is copied to an output shift register and sent bit by bit, and SOUT is set when DATAOUT is free.
- Double buffering lets the next character shift in while the previous one waits in DATAIN. The processor therefore has a whole character time to read it.
- In asynchronous serial transmission, as in a UART, each character is framed by a start bit and stop bits, and both ends must use the same baud rate.
In conclusion, interface circuits hide device details from the processor behind simple data and status registers. Parallel ports give speed over short distances, while serial ports save wires over longer links.
6 Discuss the standard I/O interfaces PCI, SCSI and USB, explaining the organisation and main features of each. 10 marks
Standard interfaces let devices from many manufacturers be connected to a computer without custom design. In a typical system, the processor bus connects through a bridge to a PCI bus. SCSI and USB controllers sit on the PCI bus and lead to further devices.
1. PCI (Peripheral Component Interconnect).
- It is processor-independent, so it can be used with different processor families.
- Address and data share multiplexed AD lines, 32 or 64 bits wide. The original clock is 33 MHz.
- Transfers are bursts: one address followed by many data words.
- The initiator (master) asserts FRAME# and IRDY#. The target answers with DEVSEL# and TRDY#. C/BE# carries the command and the byte enables.
- There are three address spaces: memory, I/O and configuration.
- It is plug-and-play. At start-up, software reads each device's configuration information and assigns addresses and interrupt lines.
2. SCSI (Small Computer System Interface).
- It is a bus for disks, tapes, optical drives and scanners. Narrow SCSI has 8 data lines and allows up to 8 devices; wide SCSI has 16 data lines and allows up to 16 devices.
- The controller acts as the initiator, and devices act as targets. The bus passes through the phases arbitration (the highest ID wins), selection, command, data and status.
- A target can disconnect while it performs a slow seek and later reselect the initiator, which leaves the bus free for others.
- Transfers are done in blocks, and the controller uses DMA into main memory.
3. USB (Universal Serial Bus).
- Devices form a tree. The host's root hub connects to hubs, and functions (devices) are at the leaves.
- A 7-bit address allows up to 127 devices.
- The host polls the devices, which never transmit unrequested. Traffic consists of token, data and handshake packets.
- Isochronous transfers give guaranteed bandwidth for audio and video.
- It supports speeds of 1.5, 12 and 480 Mb/s, hot plugging, plug-and-play and power over the cable.
In conclusion, PCI gives a fast internal expansion bus, SCSI serves high-performance storage, and USB offers a simple, cheap and expandable connection for many peripherals.
Public sources that settled doubtful points
Only the points the second AI pass doubted were looked up. These are the pages that confirmed or contradicted them; nothing here is copied from them.
Further reading
Titles only, for your own study. Nothing on this page is copied from them. The units follow the official JNTUK R23 CSE syllabus (PDF) ↗.
- Computer Organization · Carl Hamacher, Zvonko Vranesic and Safwat Zaky
- Digital Design · M. Morris Mano
- Computer Organization and Architecture · William Stallings
- Computer System Architecture · M. Morris Mano
- Computer Organization and Design · David A. Patterson and John L. Hennessy
- Fundamentals of Logic Design · Charles H. Roth