Data Representation and Digital Logic

Introduction

Computers do not manipulate numbers, text, images, or instructions in their human-readable forms. They store and process patterns of bits—binary digits whose values are 0 or 1. Data representation explains how these patterns encode information; digital logic explains how electronic circuits transform them. Together, these topics provide the conceptual foundation for processors, memory, communication systems, embedded devices, databases, and artificial intelligence hardware.

At postgraduate level, it is important to distinguish three related ideas:

1. Information is the meaning conveyed by data.
2. Representation is the encoding used to store or communicate that information.
3. Operation is the transformation performed on the representation.

The same bit pattern can have different meanings depending on its type. For example, the eight-bit pattern 01000001 may represent the unsigned integer 65, the character “A” in ASCII, part of an instruction, or a pixel intensity. Interpretation is therefore determined by representation rules and context.

Learning Objectives

After completing this chapter, a student should be able to:

• explain positional number systems and convert among binary, octal, decimal, and hexadecimal;
• represent signed integers using sign-magnitude, one’s complement, and two’s complement;
• analyze overflow, precision, range, and error in numeric representations;
• describe character, image, audio, and floating-point representations;
• apply Boolean algebra and truth tables to digital systems;
• simplify logic expressions using algebraic and Karnaugh-map techniques;
• design and analyze combinational and sequential circuits;
• evaluate reliability, security, accessibility, and implementation trade-offs in digital representation.

1. Positional Number Systems

A positional numeral system with radix (base) b represents a number using powers of b. For digits d_n d_n-1 ... d₀ . d_-1 ..., the value is

where each digit satisfies 0 ≤ d_i < b. The binary system has b = 2, decimal has b = 10, octal has b = 8, and hexadecimal has b = 16. Hexadecimal digits A–F represent decimal values 10–15.

Conversion examples

To convert 101101₂ to decimal:

101101₂ = 1×2⁵ + 0×2⁴ + 1×2³ + 1×2² + 0×2¹ + 1×2⁰ = 45₁₀.

To convert decimal 45 to binary, repeatedly divide by 2 and read remainders from bottom to top:

Thus 45₁₀ = 101101₂. Binary-to-hexadecimal conversion is efficient because one hexadecimal digit corresponds exactly to four bits: 1011₂ = B₁₆ and 0101₂ = 5₁₆, so 101101₂ = 2D₁₆.

For a fixed-width unsigned representation of n bits, the range is:

This assumes every bit contributes a non-negative positional weight and no metadata reserves values for other purposes.

2. Units of Digital Information

A bit is a binary digit. A group of eight bits is a byte. Common larger units are traditionally based on powers of 2 in memory contexts: 1 KiB = 2¹0 bytes, 1 MiB = 2²0 bytes, and 1 GiB = 2³0 bytes. Storage manufacturers often use decimal units: 1 kB = 1,000 bytes and 1 MB = 10⁶ bytes. Technical writing should state which convention is intended.

A word is a processor-dependent group of bits, such as 32 or 64 bits. Word size affects address space, register capacity, arithmetic range, and instruction design, but it does not alone determine overall system performance.

3. Integer Representation

Unsigned integers

An n-bit unsigned integer uses all bits for magnitude and represents 2ⁿ distinct values. For example, an 8-bit unsigned integer ranges from 0 to 255.

Sign-magnitude representation

The most significant bit indicates sign: 0 for positive and 1 for negative; the remaining bits represent magnitude. An n-bit sign-magnitude system has two representations of zero, +0 and −0, and its range is approximately −(2ⁿ⁻¹−1) to +(2ⁿ⁻¹−1). The duplicated zero complicates arithmetic and comparison.

One’s complement

A negative number is formed by complementing every bit of its positive counterpart. It also has positive and negative zero and requires end-around carry in some addition operations.

Two’s complement

Modern processors predominantly use two’s complement. To negate a value, invert all bits and add one. For n bits, the range is:

There is one representation of zero, and ordinary binary addition works for both positive and negative operands. For 8 bits, the range is −128 to +127.

Worked example. Represent −18 using eight-bit two’s complement. First, 18₁₀ = 00010010₂. Invert: 11101101. Add one: 11101110. Therefore −18 is 11101110₂. Interpreting this result: invert and add one to 11101110, obtaining 00010010, so its magnitude is 18.

Overflow

Overflow occurs when an exact result is outside the representable range. In two’s-complement addition, adding two positive numbers and obtaining a negative result, or adding two negative numbers and obtaining a positive result, indicates overflow. A carry out of the most significant bit alone is not a sufficient criterion.

For example, in 8-bit arithmetic, 100 + 50 = 150, but the maximum positive value is 127. The bit result wraps to a negative representation, signaling signed overflow. In safety-critical software, unchecked overflow can produce incorrect array bounds, financial values, or security decisions.

4. Fixed-Point and Floating-Point Representation

A fixed-point number assigns a fixed number of bits to the fractional part. If f bits are fractional, the smallest positive step is 2^-f, assuming binary scaling. Fixed-point is predictable and efficient in embedded control, but its range and precision are limited by the predetermined split between integer and fraction.

Floating-point represents a number approximately as

where s is the sign bit, m is the significand (or mantissa), and e is the exponent. In the widely used IEEE 754 binary formats, fields encode sign, biased exponent, and fraction. Special encodings include positive and negative zero, subnormal numbers, positive and negative infinity, and NaN (not a number).

Floating-point provides a large dynamic range but introduces rounding. If a real number is rounded to the nearest representable value, the error is the difference between the stored approximation and the exact value. Arithmetic is not generally associative: (a+b)+c may differ from a+(b+c). Algorithms involving sums should consider ordering, compensation, scaling, and tolerance-based comparisons.

The machine epsilon is format- and definition-dependent. In one common definition, it is the distance from 1 to the next larger representable number. It should not be confused with the smallest positive number representable by the format.

5. Text, Images, and Audio

Character encoding

ASCII encodes a limited set of Latin characters and control codes using seven bits, commonly stored in eight-bit bytes. Unicode provides a much larger abstract character repertoire. UTF-8 is a variable-length encoding in which common ASCII characters occupy one byte and other characters occupy multiple bytes. A program must distinguish characters, code points, and encoded byte sequences; assuming one byte per character causes internationalization errors.

Images

A raster image is represented as a grid of pixels. Each pixel may contain a grayscale value or several color components, such as red, green, and blue. For an uncompressed image with width W, height H, and d bits per pixel, storage is approximately:

This assumes no compression, metadata, padding, or color-management overhead. A 1920 × 1080 image with 24 bits per pixel requires approximately 6,220,800 bytes before such overhead.

Audio

Digital audio samples an analog waveform. If the sampling frequency is f_s samples per second and quantization uses q bits per sample, uncompressed monaural bit rate is:

For stereo, multiply by two channels. The Nyquist–Shannon sampling principle states that a band-limited signal with highest frequency f_max can be reconstructed from ideal samples when f_s > 2f_max. Practical systems use anti-aliasing filters and margins because real signals and filters are not ideal.

6. Boolean Algebra and Logic Gates

Boolean variables take values 0 or 1. The basic operations are AND, OR, and NOT, written respectively as A·B, A+B, and Ā. Their meanings are:

NOT changes 0 to 1 and 1 to 0. NAND and NOR are universal gates because any Boolean function can be constructed from either type alone. XOR produces 1 when inputs differ:

A ⊕ B = ĀB + A B̄.

Important identities include:

• Identity: A+0=A, A·1=A
• Null: A+1=1, A·0=0
• Complement: A+Ā=1, AĀ=0
• Idempotent: A+A=A, AA=A
• De Morgan: overline{AB}=Ā+B̄ and overline{A+B}=ĀB̄

A truth table specifies output for every input combination. With n binary inputs, it has 2ⁿ rows. Boolean simplification can reduce gate count, propagation delay, power consumption, and hardware cost, although a minimal expression in gate count is not always optimal under real technology constraints.

7. Combinational Circuit Design

A combinational circuit’s output depends only on current inputs. Typical circuits include adders, multiplexers, decoders, encoders, comparators, and arithmetic logic units.

A half-adder adds two one-bit inputs. Its sum is S=A⊕B and carry is C=AB. A full-adder adds A, B, and carry-in C_in:

S=A⊕B⊕C_in

C_out=AB + C_in(A⊕B).

An n-bit ripple-carry adder chains full-adders. It is simple but its worst-case delay grows with carry propagation. Carry-lookahead and prefix adders reduce delay by computing carry relationships in parallel, at the cost of additional hardware.

A multiplexer selects one of several inputs using control lines. A 2-to-1 multiplexer with inputs I₀ and I₁ and select S has output:

Y=S̄I₀ + SI₁.

This illustrates that multiplexers can implement Boolean functions and are central to datapath construction.

8. Sequential Logic and State

A sequential circuit depends on present inputs and stored state. State is held in latches or flip-flops. A synchronous design updates state on a clock edge, simplifying timing analysis. A state-transition model defines states, inputs, next-state rules, and outputs.

A D flip-flop ideally satisfies Q_next=D at the active clock edge. Real circuits have setup time, hold time, clock-to-Q delay, and propagation delay. If an input changes near the sampling edge, metastability may occur: the output may take an unpredictable time to settle. Synchronizer circuits reduce, but do not absolutely eliminate, the probability of metastability when crossing clock domains.

Finite-state machines (FSMs) are used in communication protocols, controllers, lexical analyzers, and embedded systems. In a Moore machine, outputs depend on state; in a Mealy machine, outputs depend on state and input. Mealy machines may respond faster but require careful handling of input glitches.

9. Karnaugh Maps and Hazard Awareness

A Karnaugh map arranges truth-table values so adjacent cells differ in exactly one variable. Groups of 1s yield sum-of-products simplifications; groups should contain powers of two cells and may wrap around edges. Don’t-care conditions can be assigned as 0 or 1 to obtain a simpler implementation.

Logical equivalence does not guarantee identical physical behavior. Unequal gate delays can produce temporary glitches called hazards. In asynchronous control signals, such glitches may cause incorrect transitions. Designers may add consensus terms, register outputs, or use hazard-aware timing constraints. Thus, circuit design requires both Boolean correctness and temporal correctness.

10. Memory, Error Detection, and Reliability

Memory systems use representations at several levels: cells store bits, words group bits, addresses identify locations, and buses transfer encoded values. Endianness determines byte order for multi-byte values. A little-endian system stores the least significant byte at the lowest address; a big-endian system stores the most significant byte there. Endianness is a representation issue, not a measure of computational quality.

Parity adds one bit so that the number of 1s is even or odd. It detects any odd number of bit errors but cannot reliably correct errors and may miss an even number of errors. More advanced error-correcting codes add structured redundancy. A code’s minimum Hamming distance determines its detection and correction capability: a code with minimum distance d_min can detect up to d_min−1 errors and correct up to ⌊(d_min−1)/2⌋ errors, under the standard bounded-error model.

Applied Case: Reliable Sensor Controller

Background

Consider an illustrative industrial temperature controller. A sensor produces an analog voltage, an analog-to-digital converter (ADC) samples it, a microcontroller evaluates a threshold, and a digital output activates a cooling relay.

Problem

The controller must avoid unsafe activation caused by electrical noise, represent measurements accurately, and guarantee that a temporary input transition does not damage the actuator.

Analysis

The ADC’s resolution determines the voltage step per code. For an ideal n-bit ADC with reference voltage V_ref, the nominal step size is approximately:

This assumes an ideal converter and expresses nominal quantization spacing, not total measurement accuracy. Sensor tolerance, reference error, noise, nonlinearity, and calibration also matter.

A single threshold can cause relay chatter when the measured value fluctuates around it. The design therefore uses hysteresis: cooling turns on at a higher threshold and turns off at a lower threshold. The controller is implemented as an FSM with states NORMAL, COOLING, and FAULT. A watchdog detects software failure, while a synchronizer handles asynchronous fault inputs.

Approach and outcome

The design combines filtered sampling, range checks, two’s-complement or unsigned values selected consistently throughout the software, and fail-safe output logic. A parity or CRC-protected communication link detects corrupted sensor frames. Testing includes boundary values, ADC saturation, reset behavior, clock-domain crossings, and injected bit errors.

Learning points

Representation choices affect safety. A correct threshold formula cannot compensate for overflow, ambiguous units, an incorrectly interpreted byte order, or an unsynchronized signal. Robust engineering treats encoding, logic, timing, and fault response as one system.

Contemporary and Professional Considerations

Modern processors increasingly combine general-purpose CPUs with GPUs, neural-processing units, programmable logic, and specialized accelerators. These devices may use reduced-precision formats such as 16-bit floating point or integer arithmetic to improve throughput and energy efficiency. Reduced precision is acceptable only when error bounds and application risks are understood.

Representation also has ethical and governance implications. Quantization and compression may reduce medical or scientific fidelity; inaccessible character encoding can exclude users; poorly specified rounding can alter financial outcomes; and silent overflow can undermine safety. Engineers should document units, ranges, encodings, rounding modes, byte order, error behavior, and assumptions. Standards such as IEEE 754, Unicode, and hardware interface specifications improve interoperability, but conformance must be tested rather than presumed.

Best practice includes:

• specify type, width, signedness, units, and byte order explicitly;
• test minimum, maximum, zero, negative, NaN, infinity, and malformed inputs where applicable;
• distinguish exact integer arithmetic from approximate floating-point arithmetic;
• use assertions and static analysis for overflow and range violations;
• synchronize asynchronous signals and analyze timing constraints;
• prefer error detection and fail-safe behavior in safety-critical systems;
• document encoding and version assumptions at system boundaries.

Chapter Summary

Digital systems represent information as bit patterns, but meaning depends on encoding and context. Positional notation explains binary, octal, decimal, and hexadecimal values. Unsigned and two’s-complement representations determine integer range and overflow behavior. Fixed-point and floating-point formats trade range, precision, cost, and predictability. Text, images, and audio require domain-specific encodings, with sampling, quantization, compression, and interoperability as central concerns.

Boolean algebra provides the formal basis for digital logic. Combinational circuits transform current inputs, whereas sequential circuits store state and depend on clocking and timing. Adders, multiplexers, FSMs, Karnaugh maps, error-detecting codes, and synchronizers connect abstract logic to real hardware. Reliable systems must consider not only logical equivalence but also delay, hazards, metastability, noise, faults, security, accessibility, and documented representation conventions.

Key Terms

Bit: A binary digit with value 0 or 1.

Byte: A group of eight bits.

Radix: The base of a positional number system.

Unsigned integer: An integer representation with no sign bit.

Two’s complement: A signed representation formed by bit inversion and addition of one.

Overflow: A result outside the representable numeric range.

Fixed point: A numeric format with a predetermined fractional-bit position.

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

Unicode: A universal character repertoire and encoding framework.

UTF-8: A variable-length Unicode encoding.

Sampling: Measuring a continuous signal at discrete time intervals.

Quantization: Mapping continuous or high-resolution values to discrete levels.

Boolean algebra: Algebra of binary-valued variables and logical operations.

Truth table: A table listing outputs for all input combinations.

Combinational circuit: A circuit whose output depends on current inputs.

Sequential circuit: A circuit whose output depends on inputs and stored state.

Flip-flop: A clocked storage element for a binary value.

Metastability: An uncertain temporary state caused by a timing violation.

Endianness: The byte order used to store multi-byte values.

Hamming distance: The number of differing positions between codewords.

Review Questions

Short Answer Questions

1. Why can the same bit pattern have multiple meanings?
2. State the range of an n-bit two’s-complement integer.
3. What is the difference between a character and its UTF-8 encoding?
4. Distinguish combinational and sequential circuits.
5. What problem does a synchronizer address?

Long Answer Questions

1. Explain unsigned, sign-magnitude, one’s-complement, and two’s-complement representations, including their ranges and limitations.
2. Describe floating-point representation and explain why floating-point arithmetic is not always associative.
3. Explain the design process for a combinational circuit from specification to gate-level implementation.
4. Discuss sampling, quantization, and storage requirements for digital audio.
5. Explain how FSMs, flip-flops, clocking, setup time, hold time, and metastability interact in synchronous design.

Analytical / Application Questions

1. Design an 8-bit temperature representation for a system measuring −40 °C to 125 °C. Justify the encoding, resolution, range, and overflow policy.
2. A communication frame contains a multi-byte integer and a parity bit. Propose tests that detect byte-order mistakes and characterize the limits of parity-based error detection.
3. Design a fault-tolerant controller for a sensor-driven actuator. Specify data representation, threshold hysteresis, state transitions, timing protections, and error responses.

Multiple Choice Questions with Answers

Question 1

What is the decimal value of 101101₂?

A. 41

B. 43

C. 45

D. 47

Correct Answer: C. 45

Question 2

What is the range of an 8-bit two’s-complement integer?

A. −127 to 127

B. −128 to 127

C. 0 to 255

D. −128 to 128

Correct Answer: B. −128 to 127

Question 3

Which representation has exactly one representation of zero?

A. Sign-magnitude

B. One’s complement

C. Two’s complement

D. BCD

Correct Answer: C. Two’s complement

Question 4

In an ideal n-bit ADC with reference voltage V_ref, the nominal voltage step is:

A. V_ref × 2ⁿ

B. V_ref / 2ⁿ

C. 2ⁿ / V_ref

D. V_ref − 2ⁿ

Correct Answer: B. V_ref / 2ⁿ

Question 5

Which gate is 1 exactly when two binary inputs differ?

A. AND

B. OR

C. XNOR

D. XOR

Correct Answer: D. XOR

Question 6

A combinational circuit’s output depends on:

A. Current inputs only

B. Previous clock edges only

C. Stored state only

D. Random noise only

Correct Answer: A. Current inputs only

Question 7

What is the principal purpose of a synchronizer in a digital system?

A. Increase numeric precision

B. Reduce metastability risk when sampling an asynchronous signal

C. Compress image data

D. Perform floating-point rounding

Correct Answer: B. Reduce metastability risk when sampling an asynchronous signal

Question 8

For an uncompressed image, which expression estimates storage when width is W, height is H, and color depth is d bits per pixel?

A. W+H+d

B. W×H×d/8 bytes

C. W×H/ d bytes

D. 8W×H×d bytes

Correct Answer: B. W×H×d/8 bytes

Question 9

A code with minimum Hamming distance 3 can, under the standard bounded-error model:

A. Detect no errors

B. Correct three errors

C. Detect up to two errors and correct one error

D. Correct two errors and detect one error

Correct Answer: C. Detect up to two errors and correct one error

Question 10

Which statement about parity is correct?

A. It corrects all single-bit errors

B. It detects every even number of bit errors

C. It detects any odd number of bit errors but may miss an even number

D. It eliminates the need for error correction

Correct Answer: C. It detects any odd number of bit errors but may miss an even number