Number Systems, Codes, and Digital Arithmetic

Introduction

Digital systems represent information using discrete signals. In most modern computers and embedded systems, the two signal states are represented by the binary digits 0 and 1. Although users normally work with decimal numbers, digital hardware processes binary patterns. A sound understanding of number systems and codes is therefore essential for designing circuits, interpreting processor data, debugging software–hardware interfaces, and assessing arithmetic behavior in digital systems.

This chapter develops methods for converting among decimal, binary, octal, and hexadecimal systems; explains unsigned and signed representations; presents binary arithmetic and overflow detection; and introduces fixed-point, BCD, Gray, ASCII, parity, and error-control codes.

Learning Objectives

After studying this chapter, you should be able to:

• convert numbers among binary, decimal, octal, and hexadecimal forms;
• explain positional notation and radix-based representation;
• represent signed integers using signed-magnitude, one’s-complement, and two’s-complement notation;
• perform binary addition, subtraction, multiplication, and division;
• identify carry, borrow, and signed overflow;
• distinguish fixed-point representation from floating-point representation;
• encode and decode BCD, Gray, ASCII, and parity codes;
• explain how error-detecting and error-correcting codes support reliable digital communication;
• select an appropriate representation for a practical digital application.

1. Positional Number Systems

A positional number system assigns each digit a value determined by both the digit and its position. If the radix, or base, is r, a number with digits dₙdₙ₋₁…d₁d₀ to the left of the radix point and fractional digits d₋₁d₋₂… is represented by

Here, r is the base, dᵢ is a digit satisfying 0 ≤ dᵢ < r, n is the position of the most significant integer digit, and m is the number of fractional digits. The formula applies to ordinary positional systems and assumes each position has a fixed power of the radix.

The decimal system has radix 10 and uses digits 0 through 9. Binary has radix 2 and uses 0 and 1. Octal has radix 8 and uses 0 through 7. Hexadecimal has radix 16 and uses 0 through 9 and A through F, where A represents 10 and F represents 15.

For example,

The subscript identifies the radix. When the radix is clear from context, the subscript may be omitted.

1.1 Binary, Octal, and Hexadecimal Relationships

Because 8 = 2³, every octal digit corresponds exactly to three binary bits. Because 16 = 2⁴, every hexadecimal digit corresponds exactly to four binary bits.

Binary-to-octal conversion groups bits in sets of three from the radix point outward. Binary-to-hexadecimal conversion groups bits in sets of four. Leading or trailing zeros may be added to complete a group, but these zeros do not change the value.

Example: binary to hexadecimal and octal.

Convert (11010110)₂ to octal and hexadecimal.

Grouping in threes gives 011 010 110, so the octal result is (326)₈. Grouping in fours gives 1101 0110, so the hexadecimal result is (D6)₁₆.

2. Conversion Methods

2.1 Decimal Integer to Binary

Repeated division by 2 produces the binary digits as remainders. The first remainder is the least significant bit; therefore, the remainders are read from bottom to top.

Example: convert 45₁₀ to binary.

Reading upward gives (101101)₂. Verification: 32 + 8 + 4 + 1 = 45.

The same repeated-division method applies to conversion from decimal to octal or hexadecimal, using division by 8 or 16 respectively.

2.2 Decimal Fraction to Binary

For a fraction between 0 and 1, repeatedly multiply by 2. The integer part of each product is the next binary fractional digit. The method terminates when the fractional part becomes zero or when the required precision has been reached.

Example: convert 0.625₁₀ to binary.

0.625 × 2 = 1.250 → first digit 1

0.250 × 2 = 0.500 → second digit 0

0.500 × 2 = 1.000 → third digit 1

Thus, (0.625)₁₀ = (0.101)₂. Not every decimal fraction terminates in binary. For example, 0.1₁₀ has a repeating binary representation, so practical systems store an approximation when a finite word length is used.

2.3 Binary to Decimal

Multiply each bit by its positional weight and sum the products. For fractional positions, the weights are negative powers of 2:

2.4 Decimal to Hexadecimal

Repeated division by 16 is efficient for integer values. For example, 254₁₀ divided by 16 gives quotient 15 and remainder 14, followed by quotient 0 and remainder 15. Reading remainders upward gives (FE)₁₆.

3. Ranges and Word Length

An n-bit unsigned number has 2ⁿ possible patterns, ranging from 0 to 2ⁿ − 1. For example, an 8-bit unsigned value ranges from 0 to 255.

A representation with n bits has exactly 2ⁿ distinct codewords, regardless of how those codewords are interpreted. Signed formats allocate some patterns to negative values, reducing the positive range.

The range formulas assume a fixed word length of n bits and no additional scaling factor.

4. Signed Number Representations

4.1 Signed-Magnitude Representation

The most significant bit is the sign bit: 0 denotes positive and 1 denotes negative. The remaining n − 1 bits represent the magnitude. In an 8-bit system, +13 is 00001101 and −13 is 10001101.

Signed magnitude is conceptually straightforward, but arithmetic requires separate treatment of signs and magnitudes. It also contains both positive zero, 00000000, and negative zero, 10000000.

4.2 One’s Complement

To form the negative of a number in one’s-complement notation, invert every bit. For example:

+13 = 00001101

−13 = 11110010

One’s complement also has two zeros. Addition may produce a carry out of the most significant position; this carry is added back to the least significant position, a process called end-around carry.

4.3 Two’s Complement

Two’s complement is the standard signed-integer representation in most processors. To negate a number, invert every bit and add 1.

For 8 bits:

+13 = 00001101

Invert = 11110010

Add 1 = 11110011, representing −13.

The value of an n-bit two’s-complement word bₙ₋₁bₙ₋₂…b₀ is

The leading bit has negative weight, while all other bits have positive weights. Two’s complement has one zero and an asymmetric range: one additional negative value exists because the pattern 1000…000 cannot be paired with a positive counterpart.

Example: interpret 11101010₂ as an 8-bit two’s-complement value.

The sign bit is 1, so the value is negative. Invert the bits: 00010101. Add 1: 00010110 = 22. Therefore, the original value is −22.

4.4 Sign Extension

When a signed value is moved to a larger word length, the sign bit is copied into the new positions. For example, 8-bit −22, 11101010, becomes 16-bit 11111111 11101010. This preserves the numerical value. Unsigned values are extended by inserting zeros on the left.

5. Binary Arithmetic

5.1 Addition

Binary addition follows four basic rules:

For multiple-bit addition, each column includes the carry from the preceding column.

Example:

01011101   (93)
 + 00100111   (39)
 -----------
   10000100   (132)

As an 8-bit unsigned result, 132 is valid. As a signed two’s-complement operation, however, two positive operands produced a negative-looking result, indicating signed overflow. The mathematical sum 132 exceeds the signed 8-bit maximum of 127.

5.2 Subtraction Using Two’s Complement

To calculate A − B, add A to the two’s complement of B. Any carry beyond the fixed word length is discarded.

Example: 25 − 37 using 8 bits.

25 = 00011001

37 = 00100101

Two’s complement of 37: 11011011

00011001
 + 11011011
 ----------
   11110100

11110100 is negative. Invert and add 1: 00001011 + 1 = 00001100 = 12. Therefore, the result is −12.

5.3 Multiplication and Division

Binary multiplication uses the same principle as decimal long multiplication, but each multiplier digit is either 0 or 1. A partial product is either zero or a shifted copy of the multiplicand.

For unsigned values, left shifting by k positions multiplies by 2ᵏ, provided no significant bit is lost. Right shifting by k positions performs integer division by 2ᵏ, discarding fractional remainders. For signed two’s-complement values, an arithmetic right shift replicates the sign bit and approximately divides by powers of two, with rounding behavior for negative odd values requiring care.

Example:

1011   (11)
 ×    0110   (6)
 --------
     0000
    1011
   1011
  0000
 --------
  1000010   (66)

6. Overflow and Range Errors

Overflow occurs when the mathematical result cannot be represented in the selected number format and word length. It is not the same as a carry out in every context.

For unsigned addition, overflow occurs when a carry leaves the most significant bit. For n-bit unsigned arithmetic, the result is interpreted modulo 2ⁿ; the discarded carry represents the amount beyond the available range.

For two’s-complement addition, overflow occurs when two operands with the same sign produce a result with the opposite sign. Equivalently, overflow occurs when the carry into the sign bit differs from the carry out of the sign bit.

The sign-based test is:

• positive + positive → negative: overflow;
• negative + negative → positive: overflow;
• operands with different signs: no signed addition overflow.

Subtraction has overflow when operands with different signs produce a result whose sign differs from the sign of the minuend. Hardware commonly detects this using exclusive-OR relationships among operand, result, and carry signs.

Overflow is a correctness issue in software and hardware. It can cause incorrect array indexes, financial totals, control-system decisions, security checks, or memory addresses. Programmers should select sufficient widths and use explicit overflow checks where safety is important.

7. Fixed-Point Representation

Fixed-point notation assigns a fixed number of bits to the integer portion and a fixed number to the fractional portion. If a stored unsigned integer V is interpreted with F fractional bits, the represented value is

where F is a nonnegative integer and x has the application’s chosen unit. For signed two’s-complement fixed-point values, V is first interpreted as a signed integer, then divided by 2ᶠ.

For example, with 8 total bits and 4 fractional bits, the stored pattern 00111000 has integer value 56. Its fixed-point value is 56 ÷ 16 = 3.5. The resolution is 2⁻⁴ = 0.0625, and the representable range depends on whether the stored word is unsigned or signed.

Fixed-point arithmetic is attractive in microcontrollers and digital signal processing because it can be faster, cheaper, and more energy-efficient than floating-point arithmetic. Its limitations include restricted range, scaling requirements, quantization error, and possible overflow during multiplication or accumulation.

8. Binary-Coded Decimal

Binary-coded decimal (BCD) encodes each decimal digit separately using four bits. Valid BCD codes range from 0000 through 1001. The patterns 1010 through 1111 are invalid for ordinary 8421 BCD.

For example, decimal 59 is encoded as 0101 1001, not as the binary representation of 59, which is 00111011. BCD is useful in calculators, digital clocks, financial displays, and systems where exact decimal digit representation is important.

BCD addition requires correction when a four-bit digit exceeds 9 or generates a carry. Add 0110 to that digit to produce a valid BCD digit and propagate the carry.

Example: 8 + 7 in BCD.

1000
+ 0111
------
  1111

1111 is invalid BCD, so add 0110:

1111
+ 0110
------
1 0101

The result is 0001 0101, representing decimal 15.

BCD uses more bits than pure binary. The trade-off is simpler decimal display and exact representation of decimal digits.

9. Gray Code

Gray code is a nonweighted code in which adjacent codewords differ in exactly one bit. This property reduces ambiguity during transitions, particularly in rotary encoders and position sensors.

To convert binary to Gray code, retain the most significant binary bit and XOR each adjacent pair of binary bits:

for i from n − 2 down to 0. Here, bᵢ are binary bits, gᵢ are Gray bits, and XOR denotes exclusive OR.

Example: binary 1011 converts to Gray as follows:

• first Gray bit: 1;
• 1 XOR 0 = 1;
• 0 XOR 1 = 1;
• 1 XOR 1 = 0.

Thus, 1011₂ corresponds to 1110 in Gray code. Gray code is not normally used for arithmetic because its bit positions do not have ordinary positional weights.

10. Character Codes: ASCII and Unicode Context

ASCII, the American Standard Code for Information Interchange, originally uses 7 bits and provides 128 code positions. It represents control characters, digits, uppercase letters, lowercase letters, and punctuation. For example, uppercase A is decimal 65, hexadecimal 41, and binary 1000001 in 7-bit ASCII.

ASCII is important in legacy systems and remains a subset of many modern encodings. Unicode extends character representation to support writing systems worldwide. UTF-8 is a variable-length encoding in which ASCII characters retain their one-byte form, while other characters use multiple bytes. This illustrates an important distinction: a character code identifies a symbol, whereas an encoding specifies how code points are stored as bits and bytes.

11. Parity and Error-Control Codes

Digital signals can be altered by noise, interference, attenuation, or hardware faults. Error-control codes add structured redundancy so that a receiver can detect or correct some errors.

11.1 Parity

A parity bit is selected so that the total number of 1 bits is either even or odd. In even parity, the parity bit makes the total count even; in odd parity, it makes the total count odd.

For data 1011001, there are four 1s. The even-parity bit is 0, while the odd-parity bit is 1. A single-bit error changes the parity and can be detected. However, an even number of bit errors may leave parity unchanged, so a single parity bit cannot guarantee detection of all errors and cannot identify which bit is wrong.

Two-dimensional parity applies parity checks across rows and columns. It can detect many multiple-bit errors and may locate some single-bit errors, but its capabilities depend on the error pattern.

11.2 Hamming Distance

The Hamming distance between two codewords is the number of bit positions in which they differ. A code with minimum distance dₘᵢₙ can detect up to dₘᵢₙ − 1 errors. It can correct up to

errors, where t is the guaranteed correction capability and floor means rounding downward to the nearest integer.

Thus, minimum distance 3 guarantees detection of two errors and correction of one error. These guarantees assume errors are within the stated number and that the decoder uses the code’s designed decoding method.

Hamming codes place parity bits at positions that are powers of two. The parity-check results form a syndrome that identifies the position of a single-bit error. More advanced systems use cyclic redundancy checks (CRCs), convolutional codes, Reed–Solomon codes, turbo codes, and low-density parity-check codes. CRCs are especially common for detecting burst errors in networks and storage, while modern wireless systems often combine powerful codes with interleaving and retransmission protocols.

12. Worked Application: A Sensor-Controlled Temperature Unit

Background

Consider an illustrative embedded temperature controller in a laboratory incubator. A sensor reports temperature to a microcontroller, which displays the value, activates a heater, and transmits status over a digital link.

Problem

The design must represent a temperature of 25.375 °C, display decimal digits, communicate a status byte, and detect transmission errors. The engineer must choose appropriate representations rather than treating every value as an ordinary unsigned binary integer.

Analysis and Approach

A fixed-point format with three fractional bits stores temperature in units of 1/8 °C. The scaled value is

25.375 × 8 = 203.

Therefore, the stored unsigned integer is 203₁₀ = 11001011₂. The receiver divides by 8 to recover 25.375 °C. This representation is efficient because the resolution is exactly 0.125 °C.

For display, the decimal digits 2, 5, 3, 7, and 5 can be encoded in BCD as:

0010 0101 0011 0111 0101.

BCD is preferable for a decimal display because each digit directly drives decimal-oriented display logic. The fixed-point binary representation is preferable for arithmetic in the microcontroller.

Suppose the status byte is 01101001. Under even parity, the data contains four 1s, so the parity bit is 0. If a receiver observes five 1s including the parity bit, it detects a parity error. It cannot, however, determine the faulty bit or reliably detect two simultaneous bit changes.

If a rotary control is used to select the temperature set point, Gray code can reduce errors while the mechanical sensor moves between adjacent positions. If the controller transmits packets over a noisy cable, a CRC is more appropriate than a single parity bit because it provides stronger detection of burst errors.

Outcome

The system uses fixed-point binary for computation, BCD for display, Gray code for position sensing, and CRC or parity according to communication requirements. This division of responsibilities improves efficiency and reliability.

Learning Points

• A code should be selected according to the operation it must support.
• Binary is efficient for arithmetic, while BCD simplifies decimal presentation.
• Fixed-point scaling must be documented so that all components interpret the stored value consistently.
• Error detection improves reliability but does not automatically provide error correction.
• Representation limits must be analyzed before hardware and software are integrated.

13. Best Practices and Limitations

1. Always state the radix and word length when ambiguity is possible.
2. Preserve leading zeros when they carry structural meaning, such as in bytes, BCD, or instruction fields.
3. Separate bit patterns from their interpretations; the same pattern may represent an unsigned number, signed number, character, or control field.
4. Check range before arithmetic and check overflow after arithmetic.
5. Document fixed-point scaling, units, rounding, and saturation behavior.
6. Use two’s complement consistently for signed processor arithmetic unless a specific interface requires another format.
7. Validate BCD digits before processing them.
8. Do not confuse parity detection with correction.
9. Use authenticated and integrity-protected communication when data manipulation is a security concern; error detection alone does not establish trust or authenticity.
10. Test boundary values, including zero, maximum positive values, minimum negative values, and transitions across sign boundaries.

Digital arithmetic also has governance and safety implications. Incorrect overflow handling can produce unsafe actuator commands, corrupt financial values, or undermine security controls. In safety-critical systems, requirements should specify numeric ranges, diagnostics, fault responses, and independent verification. AI-based tools can assist with code conversion or test generation, but every generated result must be independently verified because a plausible-looking bit pattern may use the wrong radix, signed interpretation, or scaling convention.

Chapter Summary

Positional notation assigns each digit a value based on its radix and position. Binary is fundamental to digital hardware; octal and hexadecimal provide compact representations because their bases are powers of two. Decimal conversion uses positional expansion, repeated division, or repeated multiplication.

Unsigned n-bit values range from 0 to 2ⁿ − 1. Signed-magnitude and one’s-complement representations contain two zeros, whereas two’s complement contains one zero and supports efficient arithmetic. Two’s-complement n-bit values range from −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1. Binary addition and subtraction must be interpreted within the selected word length, and overflow must be distinguished from an ordinary carry.

Fixed-point representation provides efficient scaled arithmetic but requires explicit scaling and range management. BCD encodes decimal digits individually, Gray code limits changes between adjacent codewords, and ASCII encodes common characters. Parity detects certain errors, while Hamming distance provides general rules for error detection and correction. Practical digital systems often combine several representations, choosing each according to computational, display, sensing, communication, or reliability requirements.

Key Terms

Radix: The base of a number system.

Positional notation: A representation in which digit value depends on position and radix.

Bit: A binary digit whose value is 0 or 1.

Nibble: A group of four bits.

Word length: The number of bits used to store a value or field.

Unsigned representation: A representation in which all bits contribute nonnegative positional weights.

Signed magnitude: A signed format with a separate sign bit and magnitude field.

One’s complement: A signed format in which a negative value is formed by inverting every bit.

Two’s complement: A signed format in which a negative value is formed by inversion followed by addition of one.

Sign extension: Copying a signed value’s sign bit into higher-order positions.

Overflow: A condition in which a mathematical result lies outside the representable range.

Fixed point: A numeric format with a fixed binary-point position.

BCD: Binary-coded decimal, in which each decimal digit uses four bits.

Gray code: A code in which adjacent codewords differ by one bit.

ASCII: A character code originally based on seven bits and 128 code positions.

Parity bit: A redundancy bit used to enforce even or odd parity.

Hamming distance: The number of differing bit positions between two codewords.

CRC: Cyclic redundancy check, a polynomial-based error-detection method.

Syndrome: A pattern of parity-check results used to identify error conditions.

Quantization: The representation of a continuous or high-precision value using discrete levels.

Review Questions

Short Answer Questions

1. Why can binary digits be grouped directly into octal and hexadecimal digits?
2. What is the range of an 8-bit unsigned number?
3. How is a negative two’s-complement number formed?
4. Why does BCD use more bits than pure binary for many decimal values?
5. What limitation does a single parity bit have?

Long Answer Questions

1. Explain decimal-to-binary conversion for both integer and fractional values, including the possibility of nonterminating binary fractions.
2. Compare signed-magnitude, one’s-complement, and two’s-complement representations in terms of range, zero representations, and arithmetic.
3. Describe binary subtraction using two’s complement and illustrate the method with a suitable example.
4. Explain fixed-point representation, including scaling, resolution, range, and sources of error.
5. Compare BCD, Gray code, ASCII, parity, and CRC in terms of purpose and application.

Analytical / Application Questions

1. An 8-bit system adds 01111100₂ and 00000101₂. Interpret the result as unsigned and as signed two’s complement. Determine whether overflow occurs in each interpretation.
2. A sensor stores temperature using a 12-bit unsigned fixed-point format with four fractional bits. Determine the stored integer for 37.5 °C and calculate the resolution.
3. Design a representation strategy for a digital weighing instrument that must calculate measurements, display decimal digits, transmit data over a noisy link, and detect sensor-position transitions. Justify the code selected for each function.

Multiple Choice Questions with Answers

Question 1

What is the decimal value of (101101)₂?

A. 45

B. 43

C. 53

D. 37

Correct Answer: A. 45

Question 2

What is the hexadecimal representation of (11010110)₂?

A. C6

B. D6

C. E6

D. DB

Correct Answer: B. D6

Question 3

What is the 8-bit two’s-complement representation of −13?

A. 10001101

B. 11110010

C. 11110011

D. 00001101

Correct Answer: C. 11110011

Question 4

Which condition indicates signed overflow in two’s-complement addition?

A. Two operands with different signs produce zero

B. Two positive operands produce a negative result

C. A carry is discarded after every addition

D. A negative and a positive operand produce a positive result

Correct Answer: B. Two positive operands produce a negative result

Question 5

What decimal value is represented by the 8-bit unsigned fixed-point pattern 00111000 with four fractional bits?

A. 3.5

B. 5.6

C. 56

D. 0.35

Correct Answer: A. 3.5

Question 6

Which statement about BCD is correct?

A. Each decimal digit is encoded using four bits

B. It always uses fewer bits than pure binary

C. The pattern 1111 represents decimal digit 15

D. It is primarily designed for arithmetic multiplication

Correct Answer: A. Each decimal digit is encoded using four bits

Question 7

What is the Gray-code equivalent of binary 1011?

A. 1001

B. 1110

C. 1101

D. 1010

Correct Answer: B. 1110

Question 8

A single parity bit can reliably detect which error pattern?

A. Every possible two-bit error

B. A single-bit error

C. Only errors in the most significant bit

D. No transmission errors

Correct Answer: B. A single-bit error

Question 9

A code has minimum Hamming distance 3. What capability is guaranteed?

A. Correction of one error

B. Correction of three errors

C. Detection of no errors

D. Correction of two errors

Correct Answer: A. Correction of one error

Question 10

Which representation is generally most suitable for efficient signed integer arithmetic in modern processors?

A. Signed magnitude

B. One’s complement

C. Two’s complement

D. Gray code

Correct Answer: C. Two’s complement