Exercises

Approach: To convert the decimal number 123 into binary, octal, and hexadecimal, divide repeatedly by the target base, collect the remainders, and read them from bottom to top.

Steps:

1. Conversion to binary:
   • 123 ÷ 2 = 61, remainder 1
   • 61 ÷ 2 = 30, remainder 1
   • 30 ÷ 2 = 15, remainder 0
   • 15 ÷ 2 = 7, remainder 1
   • 7 ÷ 2 = 3, remainder 1
   • 3 ÷ 2 = 1, remainder 1
   • 1 ÷ 2 = 0, remainder 1
   • Reading from bottom to top: 123₁₀ = 1111011₂
2. Conversion to octal:
   • 123 ÷ 8 = 15, remainder 3
   • 15 ÷ 8 = 1, remainder 7
   • 1 ÷ 8 = 0, remainder 1
   • Reading from bottom to top: 123₁₀ = 173₈
3. Conversion to hexadecimal:
   • 123 ÷ 16 = 7, remainder 11 (B)
   • 7 ÷ 16 = 0, remainder 7
   • Reading from bottom to top: 123₁₀ = 7B₁₆

Answer: 123₁₀ = 1111011₂ = 173₈ = 7B₁₆.

Approach: To convert the binary number 11010101 into decimal, expand it by place value and sum the terms.

Steps:

1. Write out the expansion by place value: 11010101₂ = 1×2⁷ + 1×2⁶ + 0×2⁵ + 1×2⁴ + 0×2³ + 1×2² + 0×2¹ + 1×2⁰
2. Evaluate each power of two: = 1×128 + 1×64 + 0×32 + 1×16 + 0×8 + 1×4 + 0×2 + 1×1
3. Sum the terms: = 128 + 64 + 0 + 16 + 0 + 4 + 0 + 1 = 213

Answer: 11010101₂ = 213₁₀.

Approach: To represent -45 in 8-bit two’s complement and then compute -45 + 23, convert the magnitude, invert and increment to obtain the two’s complement, and then add the two 8-bit patterns.

Steps:

1. Step 1: the 8-bit two’s complement of -45
   • The binary representation of 45: 00101101
   • The ones’ complement: 11010010
   • Adding 1 gives the two’s complement: 11010011
2. Step 2: the 8-bit two’s complement of 23
   • The binary representation of 23: 00010111 (the two’s complement of a positive number equals its sign-magnitude form)
3. Step 3: add them
   • 11010011 (-45)
   • • 00010111 (23)
   • = 11101010
4. Step 4: interpret the result
   • The most significant bit is 1, so the result is negative
   • The magnitude of the result: 00010110 = 22
   • So the result is -22

Answer: The 8-bit two’s complement of -45 is 11010011, and -45 + 23 = -22.

Verification: -45 + 23 = -22 ✓

Approach: To decide whether the 8-bit two’s complement addition 100 + 50 overflows, convert both operands, add them, and then check the sign of the result against the signs of the operands.

Steps:

1. Step 1: convert to 8-bit two’s complement
   • The 8-bit two’s complement of 100: 01100100
   • The 8-bit two’s complement of 50: 00110010
2. Step 2: add them
   • 01100100 (100)
   • • 00110010 (50)
   • = 10010110
3. Step 3: analyse the overflow
   • Two positive numbers added together produced a negative result (the most significant bit is 1)
   • This is a sign overflow, so an overflow has occurred
4. Step 4: verify
   • 100 + 50 = 150
   • The range of an 8-bit signed number is -128 to 127
   • 150 lies outside that range, so the overflow is real

Answer: An overflow has occurred, because two positive numbers added together produced a negative result.

Approach: To convert the decimal number 12.375 into an IEEE 754 single-precision float, convert it to binary, normalise it, and then assemble the sign, exponent, and mantissa fields.

Steps:

1. Step 1: convert to binary
   • Integer part: 12 = 1100₂
   • Fractional part: 0.375 × 2 = 0.75 → 0
   • 0.75 × 2 = 1.5 → 1
   • 0.5 × 2 = 1.0 → 1
   • So 0.375 = 0.011₂
   • And 12.375 = 1100.011₂
2. Step 2: normalise
   • 1100.011₂ = 1.100011₂ × 2³
   • Mantissa: 100011 (with the implicit leading 1 removed)
   • Exponent: 3 + 127 = 130 = 10000010₂
3. Step 3: assemble the fields
   • Sign bit: 0 (positive)
   • Exponent field: 10000010
   • Mantissa field: 10001100000000000000000
   • Result: 0 10000010 10001100000000000000000

Answer: 0 10000010 10001100000000000000000.

Approach: To convert the IEEE 754 single-precision value 0x42280000 into decimal, expand it into binary, split it into its three fields, and then evaluate the value it represents.

Steps:

1. Step 1: convert to binary
   • 0x42280000 = 01000010 00101000 00000000 00000000
2. Step 2: split the fields
   • Sign bit: 0 (positive)
   • Exponent field: 10000100 = 132
   • Mantissa field: 01010000000000000000000
3. Step 3: evaluate
   • The actual exponent: 132 - 127 = 5
   • The mantissa: 1.0101₂ (with the implicit leading 1 restored)
   • The value: 1.0101₂ × 2⁵ = 101010₂ = 42₁₀

Answer: 42.0.

Approach: To simplify the logical expression F = A’B + AB’ + AB, apply the distributive law to factor out A, use the complement law to collapse the parentheses, and then simplify the remaining sum.

Steps:

1. Step 1: apply the distributive law
   • F = A’B + AB’ + AB
   • = A’B + A(B’ + B)
2. Step 2: apply the complement law
   • B’ + B = 1
   • F = A’B + A(1)
   • F = A’B + A
3. Step 3: apply the distributive law again
   • F = A’B + A
   • = A’B + A(1)
   • = A’B + A(B + B’)
   • = A’B + AB + AB’
   • = (A’ + A)B + AB’
   • = B + AB’
4. Step 4: simplify further
   • F = B + AB’
   • = B + AB’
   • = B + AB’ + BB’ (since B = B + BB’)
   • = B + (A + B)B’
   • = B + B’ (because A + B = 1)
   • = 1

Answer: F = 1, that is, the expression is always true.

Approach: To design a parity circuit for a 3-bit binary number, define the inputs and the output, tabulate the truth table, derive the logical expression, and then implement it with XOR gates.

Steps:

1. Step 1: define the inputs and the output
   • Input: the 3-bit binary number A₂A₁A₀
   • Output: the parity bit P
2. Step 2: the truth table

3. Step 3: the logical expression
   • P = A₂ ⊕ A₁ ⊕ A₀
4. Step 4: the circuit implementation
   • Use two XOR gates:
   • The first XOR gate: A₂ ⊕ A₁
   • The second XOR gate: (A₂ ⊕ A₁) ⊕ A₀

Answer: P = A₂ ⊕ A₁ ⊕ A₀, implemented with two cascaded XOR gates.

Approach: To compute 7 × (-3) with Booth’s algorithm, convert the operands to binary, extend the multiplier with a sign bit, and then step through the algorithm, adding or subtracting the multiplicand and shifting right at each step.

Steps:

1. Step 1: convert to binary

   • 7 = 0111₂
   • The 8-bit two’s complement of -3: 11111101

2. Step 2: extend the multiplier

   • 7 = 00000111₂ (8 bits)
   • Add the sign bit: 00000111₂

3. Step 3: run the Booth algorithm

   • Initially: A = 00000000, Q = 00000111, Q₋₁ = 0

   Step	Q₀Q₋₁	Operation	Result after the right shift
   1	10	A = A − M = 00000000 − 11111101 = 00000011	A = 00000001, Q = 10000011, Q₋₁ = 1
   2	11	No operation	A = 00000000, Q = 11000001, Q₋₁ = 1
   3	11	No operation	A = 00000000, Q = 11100000, Q₋₁ = 1
   4	01	A = A + M = 00000000 + 11111101 = 11111101	A = 11111110, Q = 01110000, Q₋₁ = 0
   5	00	No operation	A = 01111111, Q = 00111000, Q₋₁ = 0
   6	00	No operation	A = 00111111, Q = 10011100, Q₋₁ = 0
   7	10	A = A − M = 00111111 − 11111101 = 01000010	A = 00100001, Q = 11001110, Q₋₁ = 0
   8	00	No operation	A = 00010000, Q = 11100111, Q₋₁ = 0

4. Step 4: the result

   • Finally A = 00010000, Q = 11100111
   • The result: 0001000011100111₂ = 11100111₂ = -21₁₀

Answer: 7 × (-3) = -21.

Verification: 7 × (-3) = -21 ✓

Approach: To design a 4-bit full adder, define the inputs and outputs, derive the equations for a single full adder, cascade four of them, and then tabulate how the carry ripples through.

Steps:

1. Step 1: define the inputs and the outputs

   • Inputs: A₃A₂A₁A₀, B₃B₂B₁B₀, C_in
   • Outputs: S₃S₂S₁S₀, C_out

2. Step 2: a single full adder

   • S_i = A_i ⊕ B_i ⊕ C_i
   • C_{i+1} = A_iB_i + (A_i ⊕ B_i)C_i

3. Step 3: cascade the four full adders

   • FA0: S₀ = A₀ ⊕ B₀ ⊕ C_in, C₁ = A₀B₀ + (A₀ ⊕ B₀)C_in
   • FA1: S₁ = A₁ ⊕ B₁ ⊕ C₁, C₂ = A₁B₁ + (A₁ ⊕ B₁)C₁
   • FA2: S₂ = A₂ ⊕ B₂ ⊕ C₂, C₃ = A₂B₂ + (A₂ ⊕ B₂)C₂
   • FA3: S₃ = A₃ ⊕ B₃ ⊕ C₃, C_out = A₃B₃ + (A₃ ⊕ B₃)C₃

4. Step 4: the circuit diagram

   • A 4-bit ripple carry adder is built by cascading FA0 through FA3, with the carry propagating from one stage to the next:

   Full Adder	Inputs	Outputs
   FA0	A₀, B₀, C_in	S₀, C₁
   FA1	A₁, B₁, C₁	S₁, C₂
   FA2	A₂, B₂, C₂	S₂, C₃
   FA3	A₃, B₃, C₃	S₃, C_out

Answer: Use four cascaded full adders, each handling one bit, with the carry output of each stage wired to the carry input of the next.

Approach: To design a simple ALU that supports addition, subtraction, AND, and OR, define the inputs and outputs, assign an operation code, build the parallel datapath, and select the result with a multiplexer.

Steps:

1. Step 1: define the inputs and the outputs
   • Inputs: A[3:0], B[3:0], OP[1:0]
   • Outputs: RESULT[3:0], ZERO, CARRY
2. Step 2: the operation code
   • OP = 00: addition
   • OP = 01: subtraction
   • OP = 10: AND operation
   • OP = 11: OR operation
3. Step 3: the logical design
   • Adder: ADD_RESULT = A + B; CARRY = (A + B) > 15
   • Subtractor: SUB_RESULT = A − B; CARRY = A < B
   • Logic unit: AND_RESULT = A & B; OR_RESULT = A | B
   • Multiplexer: RESULT = OP[1] ? (OP[0] ? OR_RESULT : AND_RESULT) : (OP[0] ? SUB_RESULT : ADD_RESULT)
   • Zero flag: ZERO = (RESULT == 0)
4. Step 4: the circuit implementation
   • Datapath: the inputs A[3:0], B[3:0] and OP[1:0] feed a 4-bit adder, a 4-bit subtractor, and the logic unit in parallel; a 4:1 multiplexer selects the result according to OP; a zero detector then produces the outputs RESULT[3:0], ZERO, and CARRY.

Answer: Combine an adder, a subtractor, a logic unit, and a multiplexer, and use the operation code to select which result is presented.

Approach: To analyse the precision problem in floating-point arithmetic, identify the sources of precision loss, work through a concrete example, trace the way the errors accumulate, and then list the techniques that control them.

Steps:

1. Step 1: the causes of precision loss
   • Binary cannot represent some decimal fractions exactly
   • Rounding error during normalisation
   • Accumulated error during a sequence of operations
2. Step 2: an example
   • 0.1₁₀ = 0.0001100110011…₂ (a repeating expansion)
   • A single-precision float can store only a finite number of bits, so precision is lost
3. Step 3: the accumulation of error
   • 0.1 + 0.1 + 0.1 ≠ 0.3
   • Each 0.1 carries a rounding error, and the errors accumulate
4. Step 4: the remedies
   • Use a data type with higher precision (double precision)
   • Adopt a specialised numerical algorithm (such as Kahan summation)
   • Use fixed-point numbers in the computations that matter most
   • Carry out error analysis and error control

Answer: Floating-point arithmetic does suffer from precision problems, so an appropriate choice of algorithm and data type is needed to keep the error small.