Data Representation and Computer Arithmetic

Introduction

A processor manipulates bit patterns, not abstract numbers or characters. The interpretation assigned to a pattern determines its meaning. For example, 11111111₂ is 255 as an unsigned integer, −1 in eight-bit two’s complement, and an invalid packed-BCD byte because each BCD nibble must lie between 0000 and 1001. Decimal 99 in packed BCD is 1001 1001₂.

Data representation therefore forms a contract among hardware, software, communication protocols, and stored data. Incorrect interpretation can cause arithmetic overflow, loss of precision, corrupted messages, unsafe control actions, and interoperability failures. This chapter develops positional number systems, signed and fixed-point numbers, IEEE 754 floating point, decimal and character codes, error detection, and the arithmetic structures that operate on them.

Learning Objectives

After studying this chapter, students should be able to:

• convert numbers among binary, octal, decimal, and hexadecimal systems;
• interpret sign-magnitude, one’s-complement, and two’s-complement integers;
• detect integer overflow and distinguish it from unsigned carry;
• select and analyze fixed-point and floating-point representations;
• apply IEEE 754 classification, rounding, and exception concepts;
• perform binary, BCD, and floating-point arithmetic;
• explain character encodings and error-detection codes;
• analyze ALU structures and arithmetic-unit trade-offs; and
• design reliable representation and arithmetic choices for embedded systems.

1. Positional Number Systems

1.1 Radix notation

In a positional number system of radix r, a digit string has the value

where r ≥ 2 is the radix, d_i is a digit satisfying 0 ≤ d_i < r, k is the highest integer position, and f is the number of fractional positions. The formula applies to ordinary unsigned positional notation.

For example,

Here hexadecimal A represents decimal 10.

1.2 Conversion from another radix to decimal

Expand the number using positional weights. For example,

1.3 Conversion from decimal to another radix

For the integer part, repeatedly divide by the target radix and read the remainders upward. Converting decimal 45 to binary gives remainders 1, 0, 1, 1, 0, 1, read in reverse as 101101₂.

For a fractional part, repeatedly multiply by the target radix and record each integer part. For 0.625₁₀, multiplication by 2 gives:

• 0.625 × 2 = 1.25 → first bit 1;
• 0.25 × 2 = 0.5 → second bit 0;
• 0.5 × 2 = 1.0 → third bit 1.

Thus 0.625₁₀ = 0.101₂. Some decimal fractions, such as 0.1, have nonterminating binary expansions and must be approximated in finite storage.

1.4 Binary–octal conversion

Each octal digit corresponds exactly to three binary bits.

Group binary digits in sets of three outward from the radix point, adding zeros only at the outer ends when necessary:

Verification gives 3(8³)+2(8²)+7(8)+5=1725. To convert octal to binary, replace every octal digit with its three-bit equivalent. Thus (572)₈=(101\ 111\ 010)₂.

For a fraction, (0.653)₈=(0.110\ 101\ 011)₂. Grouping must begin at the radix point, not at an arbitrary end.

1.5 Binary–hexadecimal conversion

Each hexadecimal digit corresponds to four bits. For example,

The same value is 1725 decimal. Hexadecimal is particularly useful because one byte is represented by exactly two hexadecimal digits.

2. Integer Representations

2.1 Unsigned integers

An unsigned n-bit word represents

where each b_i is 0 or 1. Its range is

An eight-bit unsigned integer therefore ranges from 0 to 255.

2.2 Sign-magnitude representation

The most significant bit is the sign: 0 for positive and 1 for negative. The remaining n-1 bits hold the magnitude. Its range is

It has both positive zero and negative zero. Arithmetic hardware must separately process signs and magnitudes, limiting its use for general integer arithmetic.

2.3 One’s-complement representation

A negative number is formed by complementing every bit of its positive representation. In eight bits, +5 is 00000101 and −5 is 11111010.

For n bits, the range is explicitly

Thus eight-bit one’s complement ranges from −127 to +127. It also has two zeros: 00000000 and 11111111. Addition requires an end-around carry: a carry leaving the most significant position is added to the least significant position.

2.4 Two’s-complement representation

To negate an n-bit value, complement all bits and add 1, while retaining only n bits. The represented value is

Its range is

Eight-bit two’s complement therefore ranges from −128 to +127. It has one zero and permits addition and subtraction through the same binary adder, making it the dominant signed-integer representation.

Worked example—representing −37 in eight bits

37 = 00100101₂. Complementing gives 11011010₂; adding 1 gives 11011011₂. Therefore 11011011₂ represents −37.

Sign extension preserves value when increasing word length. Extending 11011011₂ to 16 bits gives 11111111 11011011₂. Zero extension would not preserve this negative value.

2.5 Representation comparison

3. Integer Arithmetic and Overflow

3.1 Addition and subtraction

Binary addition follows the same place-value principle as decimal addition. For each bit position, an adder combines two operand bits and a carry-in, producing a sum and carry-out.

Two’s-complement subtraction is implemented as

All operations are performed at a fixed word length. Any carry beyond the word is discarded for the signed result.

3.2 Carry and signed overflow

Carry-out indicates unsigned overflow, whereas signed overflow concerns the two’s-complement range. Signed addition overflows when two operands of the same sign produce a result of the opposite sign.

If C_n-1 is the carry into the sign position and C_n is the carry out, then

where V is the signed-overflow flag and \oplus denotes exclusive OR.

Worked example—eight-bit overflow

The operands are +100 and +40, whose mathematical sum is +140. Because +140 exceeds the eight-bit maximum of +127, overflow occurs. The stored pattern would be interpreted as −116, so it is not the mathematical signed result.

By contrast, 11111111₂ + 00000001₂ produces zero with carry-out 1. As unsigned arithmetic, 255 + 1 overflows. As signed arithmetic, −1 + 1 = 0 and no signed overflow occurs.

3.3 Multiplication and division

Unsigned shift-and-add multiplication examines multiplier bits and adds appropriately shifted copies of the multiplicand. Multiplying two n-bit unsigned values may require up to 2n result bits. For example, 13 × 11 = 143, represented as 00001101₂ × 00001011₂ = 0000000010001111₂ in a 16-bit product.

Signed multiplication can use magnitude processing or algorithms such as Booth recoding. Booth recoding compresses runs of 1s in a two’s-complement multiplier and is advantageous for some operand patterns. Array, Wallace-tree, and Booth multipliers trade circuit area, delay, and power differently.

Binary long division uses shifts, comparisons, and conditional subtraction. Hardware implementations include restoring, non-restoring, and higher-radix division. Division by zero must be handled explicitly; integer instruction sets commonly trap or define architecture-specific outcomes.

4. Fixed-Point Representation

Fixed-point representation treats an integer bit pattern as scaled by a fixed power of two. Let S be an n-bit two’s-complement integer and let F be the number of fractional bits. The represented real number is

The resolution is 2^-F, and the range is

This convention states the total word length and fractional-bit count explicitly, avoiding ambiguous Q-format naming conventions.

Worked example—16-bit format with 8 fractional bits

The resolution is 2^-8=1/256=0.00390625. The range is −128 to 127.99609375. To encode 12.75,

Multiplying values with fractional counts F₁ and F₂ produces a full-precision integer product with F₁+F₂ fractional bits. Rescaling generally requires a right shift and a defined rounding rule. A double-width accumulator prevents premature loss of high-order or low-order information.

4.1 Quantization, rounding, and saturation

Mapping a real value to a fixed grid introduces quantization error. With rounding to nearest and step size \Delta=2^-F, the error satisfies

except at saturation limits. Truncation has a directional bias for many data distributions. Rounding-to-nearest reduces typical error but requires extra logic.

Wraparound retains low-order bits after overflow. Saturating arithmetic instead clamps results to the minimum or maximum representable value. Saturation is often preferred in audio, image, and control systems because a large positive value does not suddenly become negative.

5. Floating-Point Representation

5.1 Scientific binary notation

Floating point represents a sign, significand, and exponent. For a finite normalized binary value,

where s is the sign bit, f is the stored fraction, and e is the unbiased exponent. This provides a very large dynamic range at the cost of nonuniform spacing and finite precision.

5.2 IEEE 754 binary formats

For a normal number with stored exponent E,

This applies when the exponent field is neither all zeros nor all ones. For binary32, 1 ≤ E ≤ 254.

When E=0 and the fraction is nonzero, the binary32 value is subnormal:

Subnormals provide gradual underflow. The smallest positive normal binary32 number is 2^-126, while the smallest positive subnormal is 2^-149. An all-zero exponent and fraction represents signed zero. An all-one exponent with zero fraction represents infinity; an all-one exponent with nonzero fraction represents NaN, or “not a number.”

Worked example—binary32 encoding of −13.25

13.25₁₀ = 1101.01₂ = 1.10101₂ × 2³. Hence:

• sign bit = 1;
• stored exponent = 3+127=130=10000010₂;
• fraction = 10101000000000000000000.

The complete representation is 1 10000010 10101000000000000000000, or 0xC1540000.

5.3 Floating-point addition

Floating-point addition generally involves:

1. classifying operands and handling special values;
2. aligning significands by shifting the smaller-exponent operand;
3. adding or subtracting significands;
4. normalizing the result;
5. rounding to the destination precision; and
6. checking exceptional conditions.

Alignment can discard low-order bits. Subtraction of nearly equal operands can cause catastrophic cancellation: leading significant digits cancel, exposing rounding errors already present in the operands.

Floating-point arithmetic is generally not associative. Thus (a+b)+c may differ from a+(b+c). Compilers and parallel algorithms must not reorder operations when strict reproducibility is required unless the applicable language and execution mode permit it.

5.4 Rounding and exceptions

IEEE 754 defines rounding directions including round to nearest, ties to even; toward zero; toward positive infinity; and toward negative infinity. Round-to-nearest, ties-to-even limits systematic bias. Under that rule, an exact halfway value is rounded so the retained least significant bit is even.

Important exceptional conditions include invalid operation, division by zero, overflow, underflow, and inexact result. Overflow occurs when a rounded result’s magnitude is too large for the destination format. The inexact condition indicates that rounding changed the exact mathematical result.

IEEE 754 underflow must not be equated simply with “a subnormal result.” The underflow exception is generally signaled when the result is both tiny and inexact under the applicable tininess-detection rules. An exactly representable subnormal result need not raise the underflow exception.

A fused multiply-add computes a×b+c with a single final rounding rather than rounding the product first. It can improve both performance and numerical accuracy.

6. Binary-Coded Decimal and Character Data

6.1 Binary-coded decimal

In 8421 BCD, each decimal digit is encoded independently using four bits. Valid codes range from 0000 to 1001; 1010 through 1111 are invalid digit codes.

Packed BCD stores two decimal digits per byte. Decimal 99 is therefore

Unpacked BCD commonly places one digit in each byte, often with the upper nibble zero or reserved for a zone or sign convention.

Worked example—packed-BCD addition

To add 58 and 67, first add their packed patterns:

0x58 + 0x67 = 0xBF.

The low nibble F is not a valid BCD digit, so add 0x06, giving 0xC5. The high decimal position also requires correction; adding 0x60 gives 0x125, which encodes decimal 125. Decimal-adjust instructions automate such corrections on some processors.

BCD preserves decimal digits exactly and is useful in financial counters and displays, but it stores fewer numerical values per bit and usually requires more complex arithmetic than binary integers.

6.2 Character representation

ASCII is a seven-bit code representing English letters, digits, punctuation, and control characters. For example, ASCII A is 0x41, while the character 9 is 0x39; character digits are not numerically identical to binary integers.

Unicode assigns abstract code points to characters from many writing systems. Encodings such as UTF-8 and UTF-16 map those code points into byte sequences. UTF-8 is variable-length and preserves the ASCII byte values for ASCII characters. Systems must validate byte sequences and specify encoding at interfaces; otherwise text may be corrupted or security checks bypassed through inconsistent interpretation.

7. Error Detection and Correction

7.1 Parity

An even-parity bit is chosen so that the total number of 1s is even. A single-bit error changes parity and is detected. More generally, parity detects every odd number of bit errors but may fail for an even number. It identifies that corruption occurred but cannot locate the erroneous bit.

7.2 Checksums

A checksum combines blocks through arithmetic such as one’s-complement addition. Checksums are inexpensive and useful for accidental errors, but ordinary checksums are not cryptographically secure. An attacker may modify data while deliberately preserving the checksum.

7.3 Cyclic redundancy check

A CRC treats a bit string as a polynomial over the two-element field, where addition and subtraction are both XOR. If the generator polynomial G(x) has degree r, the sender appends r zeros to the message polynomial M(x), divides by G(x), and appends the remainder R(x).

The transmitted polynomial T(x) is divisible by G(x). Detection capability depends on the chosen generator and message length; a CRC is not guaranteed to detect every possible error pattern.

Worked example—CRC division

For message 1101 and generator 1011 of degree 3, append three zeros to obtain 1101000. Modulo-2 division by 1011 gives remainder 001. The transmitted codeword is therefore 1101001, which produces zero remainder when divided by the same generator in the absence of error.

7.4 Hamming distance and correction

The Hamming distance between two codewords is the number of differing bit positions. A code with minimum distance d_min can detect up to d_min-1 errors and correct up to

errors per codeword, assuming a bounded number of substitutions and nearest-codeword decoding.

For a binary Hamming code containing m data bits and r parity bits, single-error correction requires

The right side counts all bit positions plus the no-error condition. For eight data bits, four parity bits are sufficient because 2⁴=16 ≥ 8+4+1=13. Adding an overall parity bit to an appropriate Hamming code supports single-error correction and double-error detection, commonly called SECDED.

8. Arithmetic Logic Unit Organization

The ALU performs arithmetic, logical, shift, comparison, and sometimes specialized operations. It also produces status flags such as zero, negative, carry, and overflow.

Figure: Conceptual ALU organization with arithmetic, logical, shift, result, and status paths.

A ripple-carry adder is compact but its worst-case delay grows approximately with word length because each carry waits for the preceding stage. Carry-lookahead, parallel-prefix, and related adders compute carry information more rapidly at the cost of wiring, area, and power.

Dedicated multipliers provide high throughput but consume substantial silicon. Iterative shift-add multipliers reuse hardware across multiple cycles and are smaller but slower. Similar trade-offs apply to division. Pipelining increases clock frequency and throughput but adds latency, registers, control complexity, and switching energy.

9. Illustrative Case: Embedded Sensor Signal Chain

Background

Consider an illustrative industrial vibration monitor using a 12-bit ADC and a low-power microcontroller. The unit must calibrate samples, display a decimal value, and transmit reliable packets.

Problem

The processor lacks a hardware floating-point unit. The design must provide adequate precision without exceeding timing and energy limits. It must also prevent silent corruption in the communication channel.

Analysis and approach

The ADC output is first centered by subtracting 2048. For a raw sample of 3000, the signed sample is 3000-2048=952. A calibration gain of 1.125 is represented in a 16-bit fixed-point format with 12 fractional bits:

A double-width multiplication gives

Rescaling by an arithmetic right shift of 12 positions yields

The exact calibrated integer result is therefore 1071. The hexadecimal binary value is 0x042F. If the display requires 10.71 engineering units, its four decimal digits can be packed as 0x1071; the decimal point is a display attribute rather than a BCD digit. If transmitted as UTF-8 text, 10.71 uses ASCII-compatible bytes 31 30 2E 37 31 in hexadecimal.

A CRC is appended to each binary packet to detect channel errors. Intermediate products use double width, conversion points specify rounding, and extreme values are saturated rather than wrapped.

Outcome

The fixed-point implementation avoids software floating-point overhead while representing the selected gain exactly. Explicit scaling, wide intermediates, saturation, and CRC protection produce predictable real-time behavior.

Learning points

• Representation must be selected from range, precision, throughput, and interface requirements.
• Binary arithmetic, BCD display data, character text, and communication codewords are distinct interpretations.
• Intermediate word length can be as important as final word length.
• Error detection protects transmission but does not correct flawed arithmetic or malicious manipulation.

10. Reliability, Governance, and Contemporary Practice

Arithmetic behavior should be specified rather than left implicit. Interfaces must state byte order, signedness, scaling, floating-point format, character encoding, and error-code parameters. Safety-critical systems should test boundary values, NaNs, infinities, subnormals, maximum magnitudes, and overflow paths.

Silent saturation can conceal sensor failure, while wraparound can create dangerous control commands. Systems should therefore record diagnostic flags and distinguish valid clipping from hardware faults. Financial applications must define decimal rounding rules. Text-processing systems must normalize and validate Unicode consistently to reduce spoofing and comparison vulnerabilities. CRCs protect against accidental corruption, not intentional forgery; authenticated cryptographic mechanisms are required for hostile environments.

Contemporary processors increasingly support binary16, bfloat16, vector arithmetic, fused multiply-add, and mixed-precision computation for machine learning. Reduced precision improves throughput and energy efficiency but can degrade convergence or amplify accumulated error. Good practice includes range analysis, numerical testing against a higher-precision reference, explicit rounding, and reproducible arithmetic modes where results have regulatory or scientific significance.

Chapter Summary

Digital words acquire meaning through representation. Binary, octal, and hexadecimal are positional systems that enable convenient conversion through bit grouping. Unsigned, sign-magnitude, one’s-complement, and two’s-complement formats differ in range, zero representation, and arithmetic complexity; two’s complement dominates signed integer processing.

Fixed-point representation provides efficient, predictable arithmetic when scale and range are controlled. Floating point supplies broad dynamic range but introduces rounding, exceptional values, non-associativity, and possible cancellation. IEEE 754 subnormal results provide gradual underflow, while the underflow exception generally requires both tininess and inexactness.

BCD represents decimal digits directly, whereas ASCII and Unicode represent characters. Parity, checksums, CRCs, and Hamming codes offer different error-detection or correction capabilities. ALU design requires trade-offs among speed, area, power, latency, range, and precision. Reliable engineering depends on explicit formats, wide intermediates, deliberate rounding and overflow policies, boundary testing, and suitable integrity protection.

Key Terms

Radix: The number of distinct digit values used by a positional number system.

Octal: A radix-8 number system in which each digit corresponds to three binary bits.

Hexadecimal: A radix-16 system using digits 0–9 and A–F.

Two’s complement: A signed representation with one zero and a range from -2^n-1 to 2^n-1-1.

One’s complement: A signed representation formed by bitwise complementation and having two zero patterns.

Sign extension: Replication of a two’s-complement sign bit when increasing word length.

Overflow: A condition in which a mathematical result lies outside the destination format’s range.

Carry flag: A status indicator associated primarily with unsigned carry or borrow behavior.

Fixed point: A scaled-integer representation with a predetermined radix-point position.

Quantization: Mapping a value to one of a finite set of representable levels.

Saturation: Clamping an out-of-range result to the nearest representable endpoint.

Floating point: A representation using sign, significand, and exponent fields.

Subnormal number: A floating-point value with reduced leading precision that supports gradual underflow.

NaN: An IEEE 754 encoding representing an undefined or unavailable numerical result.

BCD: A representation that encodes each decimal digit separately in binary.

Unicode: A standard assigning code points to characters from many writing systems.

CRC: A polynomial-based error-detection code using modulo-2 division.

Hamming distance: The number of bit positions at which two codewords differ.

ALU: A processor unit that performs arithmetic, logic, comparison, and shift operations.

Fused multiply-add: An operation computing a multiplication and addition with one final rounding.

Review Questions

Short Answer Questions

1. Why can the same eight-bit pattern have different numerical meanings?
2. How is binary converted to octal by grouping bits?
3. Distinguish unsigned carry from two’s-complement overflow.
4. What is the purpose of subnormal floating-point numbers?
5. Why is a CRC not a substitute for cryptographic authentication?

Long Answer Questions

1. Compare sign-magnitude, one’s-complement, and two’s-complement representations, explicitly deriving their n-bit ranges and discussing their zero encodings.
2. Explain fixed-point scaling, multiplication, rounding, overflow, and saturation using a worked numerical example.
3. Describe IEEE 754 binary32 normal numbers, subnormal numbers, zeros, infinities, NaNs, rounding, and exceptions.
4. Explain packed-BCD addition and compare BCD with ordinary binary integer representation.
5. Compare ripple-carry, carry-lookahead or parallel-prefix, iterative, and pipelined arithmetic units in terms of area, delay, throughput, and power.

Analytical / Application Questions

1. A 16-bit two’s-complement sensor format has 10 fractional bits. Determine its resolution and range, encode 7.375, and state how multiplication results should be rescaled.
2. Design a packet format for a sensor that transmits signed fixed-point data and UTF-8 labels. Specify byte order, scaling, error detection, and receiver validation.
3. Analyze whether fixed point, binary32, or binary64 is most appropriate for an autonomous control loop with strict timing, large dynamic range, and safety-critical reproducibility. Justify the trade-offs.

Multiple Choice Questions with Answers

Question 1

What is the octal representation of (11010111101)₂?

A. 3157₈

B. 3275₈

C. 6535₈

D. 6BD₈

Correct Answer: B. 3275₈

Question 2

What is the range of an eight-bit one’s-complement integer?

A. −128 to +127

B. −127 to +127

C. −128 to +128

D. 0 to 255

Correct Answer: B. −127 to +127

Question 3

In eight-bit two’s-complement arithmetic, what occurs when 01100100₂ and 00101000₂ are added?

A. The result is +140 with no overflow

B. Unsigned carry occurs but signed overflow does not

C. Signed overflow occurs because two positive operands produce a negative-pattern result

D. The exact stored result is +116

Correct Answer: C. Signed overflow occurs because two positive operands produce a negative-pattern result

Question 4

A 16-bit fixed-point value has 8 fractional bits. Which stored integer represents 12.75?

A. 51

B. 816

C. 3264

D. 52224

Correct Answer: C. 3264

Question 5

Which statement correctly describes IEEE 754 underflow?

A. Every subnormal result necessarily raises underflow

B. Underflow generally requires a tiny and inexact result

C. Underflow occurs whenever the exponent is negative

D. An exact zero result always raises underflow

Correct Answer: B. Underflow generally requires a tiny and inexact result

Question 6

Which byte is the valid packed-BCD representation of decimal 99?

A. 0x63

B. 0x99

C. 0xFF

D. 0x9F

Correct Answer: B. 0x99

Question 7

How many parity bits are sufficient for a binary Hamming code containing eight data bits and providing single-error correction?

A. 2

B. 3

C. 4

D. 8

Correct Answer: C. 4

Question 8

For message 1101 and CRC generator 1011, what remainder results after appending three zeros and performing modulo-2 division?

A. 000

B. 001

C. 101

D. 111

Correct Answer: B. 001

Question 9

What is the principal benefit of a fused multiply-add operation?

A. It converts floating point into BCD

B. It eliminates all floating-point exceptions

C. It computes a×b+c with only one final rounding

D. It guarantees associative arithmetic

Correct Answer: C. It computes a×b+c with only one final rounding

Question 10

Compared with a ripple-carry adder, a parallel-prefix adder typically provides which trade-off?

A. Lower carry delay at the cost of greater wiring and hardware complexity

B. Lower carry delay with no area or power cost

C. Smaller area but necessarily longer delay

D. Decimal arithmetic without correction logic

Correct Answer: A. Lower carry delay at the cost of greater wiring and hardware complexity