Digital Design

1. Digital Representation is About Bits and Codes

For a deck with 52 cards, we need 6 bits (32 < 52 < 64).

Information encoded in bits. Digital systems represent all types of information using binary digits (bits), which can be 0 or 1. The number of bits required to represent a set of distinct items is determined by the smallest power of 2 greater than or equal to the number of items. For example, representing 52 cards requires 6 bits because 2^5 = 32 (not enough) and 2^6 = 64 (enough).

Different number systems. Information can be represented in various number systems beyond base-10 decimal, including binary (base-2), octal (base-8), and hexadecimal (base-16). Conversions between these bases are fundamental, often involving polynomial expansion for converting to decimal or repeated division/multiplication for converting from decimal. Signed numbers can be represented using methods like signed magnitude, 1's complement, or 2's complement, with 2's complement being common for arithmetic operations.

Binary codes for data. Specific binary codes are used to represent decimal digits (like BCD - Binary-Coded Decimal) or characters (like ASCII). BCD uses 4 bits per decimal digit, while ASCII uses 7 or 8 bits per character, often including an extra bit for parity checking to detect errors during transmission. Understanding these codes and their properties, such as parity (even or odd), is crucial for handling data in digital systems.

2. Boolean Algebra Simplifies Logic Functions

xy + xy' = x

Algebra for logic. Boolean algebra provides a mathematical framework for analyzing and simplifying digital logic circuits. It defines operations like AND (.), OR (+), and NOT (') and includes fundamental theorems and properties such as commutativity, associativity, distributivity, identity, complementation, and DeMorgan's theorem. These rules allow complex logic expressions to be manipulated and reduced.

Simplification is key. Simplifying Boolean expressions reduces the number of logic gates required to implement a function, leading to smaller, faster, and less power-hungry circuits. For example, the identity xy + xy' = x shows how two AND gates and one OR gate can be replaced by a single wire representing x. More complex expressions can often be significantly simplified using these algebraic techniques.

Standard forms exist. Boolean functions can be expressed in standard forms like Sum of Products (SOP) and Product of Sums (POS). SOP represents the function as a sum of minterms (product terms where each variable appears once), while POS represents it as a product of maxterms (sum terms where each variable appears once). Converting between these forms and their complements is essential for different implementation styles (e.g., using only NAND or NOR gates).

3. Karnaugh Maps Minimize Gate Implementations

F = xy + x’z'

Visual simplification tool. Karnaugh maps (K-maps) provide a graphical method for simplifying Boolean functions of up to five variables. They arrange minterms in a grid such that adjacent cells differ by only one variable, allowing for easy identification of prime implicants (product terms that cannot be combined further) and essential prime implicants (prime implicants that cover a minterm not covered by any other prime implicant).

Grouping for reduction. By circling adjacent groups of 1s (for SOP) or 0s (for POS) in powers of two (2, 4, 8, etc.), designers can identify simplified product or sum terms. The goal is to cover all the 1s (or 0s) with the largest possible groups, using essential prime implicants first, to obtain a minimal expression. Don't-care conditions (inputs that never occur or whose output doesn't matter) can be included in groups to further simplify the logic.

Direct implementation. The simplified SOP or POS expression obtained from a K-map directly corresponds to a two-level logic circuit (AND gates followed by an OR gate for SOP, or OR gates followed by an AND gate for POS). This systematic minimization process is crucial for efficient hardware design, ensuring that the resulting circuit uses the fewest possible gates and inputs.

4. Combinational Circuits Perform Instantaneous Operations

assign {carry_borrow, sum_diff} = sel_diff ? A - B : A + B;

Output depends only on input. Combinational logic circuits produce outputs that are determined solely by the current values of their inputs. They have no memory elements and thus no concept of past states. Examples include basic arithmetic circuits like adders and subtractors, data selection circuits like multiplexers and demultiplexers, and code converters like decoders and encoders.

Building blocks of digital systems. Complex combinational functions are built by interconnecting basic logic gates (AND, OR, NOT, XOR, etc.). Standard combinational circuits perform common digital tasks:

• Adders (half and full adders) sum binary numbers.
• Subtractors (half and full subtractors) find the difference between binary numbers.
• Comparators determine the relationship (equal, greater than, less than) between two binary numbers.
• Decoders convert a binary code into a unique output line activation.
• Encoders perform the reverse, generating a binary code from an active input line.
• Multiplexers (Muxes) select one of several input lines based on select inputs.

Described by truth tables or Boolean expressions. The behavior of a combinational circuit can be fully described by a truth table listing all possible input combinations and their corresponding outputs, or by a set of Boolean expressions for each output in terms of the inputs. Hardware Description Languages (HDLs) like Verilog can describe these circuits using gate-level instantiations, dataflow assignments, or behavioral descriptions.

5. Sequential Logic Adds Memory and State

Signal transitions that are caused by input signals that change on the active edge of the clock race with the clock itself... the outcome is indeterminate

Output depends on input and past state. Sequential logic circuits, unlike combinational ones, include memory elements (latches or flip-flops) and their outputs depend on both the current inputs and the history of past inputs, captured in the circuit's state. These circuits are essential for building systems that perform operations over time, such as storing data, counting, or following a sequence of steps.

Flip-flops are the core memory. Flip-flops (like SR, D, JK, and T types) are fundamental one-bit memory units that store state and change their output only at specific times determined by a clock signal. Their behavior is defined by characteristic tables or equations, showing the next state based on current state and inputs. Excitation tables show the required flip-flop inputs to achieve a desired state transition.

Synchronous vs. asynchronous. Synchronous sequential circuits use a clock signal to coordinate state changes, ensuring predictable behavior. Asynchronous circuits change state based on input changes without a clock, which can lead to complex timing issues and potential metastability if inputs change too close to the clock edge. Proper synchronization of external inputs to the clock is critical in synchronous designs to avoid unpredictable outcomes.

6. Registers and Counters Store and Sequence Data

Serial data is transferred one bit at a time. Parallel data is transferred n bits at a time (n > 1).

Registers store groups of bits. Registers are collections of flip-flops used to store binary data words. They can perform various operations like loading data in parallel, shifting data left or right (serial transfer), or holding the current value. Shift registers are particularly useful for converting between serial and parallel data formats.

Counters follow a state sequence. Counters are sequential circuits specifically designed to cycle through a predefined sequence of states, typically representing binary numbers. They can be synchronous (all flip-flops clocked simultaneously) or asynchronous (ripple counters, where the clock propagates through the flip-flops). Different counter types exist, such as binary counters (up, down, or up/down), BCD counters, and ring/Johnson counters, each with a unique state sequence.

Building larger systems. Registers and counters are essential building blocks for more complex digital systems, including processors, memory controllers, and communication interfaces. Their design involves determining the required flip-flop types and the combinational logic needed to generate the flip-flop inputs based on the current state and any control signals (like load, count enable, shift direction).

7. Memory and Programmable Logic Store Information and Implement Functions

13 + 12 = 25 address lines. Memory capacity = 225 words.

Memory stores large amounts of data. Digital memory devices store binary information in large arrays of storage cells. Memory is organized into words, each with a unique address. The number of address lines determines the total memory capacity (2^(number of address lines) words). Data is accessed by providing an address and asserting read or write control signals. RAM (Random Access Memory) allows both reading and writing, while ROM (Read-Only Memory) is programmed once and primarily used for reading fixed data or implementing combinational logic functions.

Error detection and correction. For reliable data storage and transmission, especially in larger memories, error detection and correction techniques like Hamming codes are used. These codes add redundant parity bits to the data word, allowing single-bit errors to be detected and corrected, and some multiple-bit errors to be detected.

Programmable logic implements custom functions. Programmable Logic Devices (PLDs) like ROMs, PLAs (Programmable Logic Arrays), and PALs (Programmable Array Logic) offer flexible ways to implement custom combinational logic functions. ROMs implement functions by storing the truth table directly. PLAs and PALs use arrays of AND and OR gates, where the connections can be programmed to realize specific SOP expressions. These devices provide a convenient alternative to designing custom circuits with discrete gates.

8. Register Transfer Level and ASM Charts Describe System Behavior

The operations specified in a flowchart are executed sequentially... The operations specified in an ASM chart are executed concurrently...

Designing complex systems. Designing digital systems involves describing their behavior at a higher level of abstraction than individual gates or flip-flops. The Register Transfer Level (RTL) describes the flow of data between registers and the operations performed on that data. This level focuses on the system's architecture, including registers, functional units (like adders or multipliers), and the data paths connecting them.

Algorithmic State Machines (ASM). ASM charts are a graphical tool used to describe the behavior of synchronous sequential circuits, particularly those with a datapath and a control unit. Unlike traditional flowcharts, ASM charts clearly represent the concurrency of operations within a single clock cycle. Each ASM block corresponds to a state and specifies the conditional and unconditional operations performed and the transition to the next state, all occurring on the same clock edge.

Controller and Datapath. Digital systems are often partitioned into a control unit and a datapath unit. The datapath performs the data processing operations (arithmetic, logic, shifting, storage) using registers and combinational logic. The control unit, typically implemented as a finite state machine (FSM), generates the control signals that direct the operations within the datapath based on the current state and external inputs. ASM charts are ideal for designing the control unit and its interaction with the datapath.

Last updated: May 21, 2025