Hubbry Logo
Don't-care termDon't-care termMain
Open search
Don't-care term
Community hub
Don't-care term
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Don't-care term
Don't-care term
from Wikipedia

In digital logic, a don't-care term[1][2] (abbreviated DC, historically also known as redundancies,[2] irrelevancies,[2] optional entries,[3][4] invalid combinations,[5][4][6] vacuous combinations,[7][4] forbidden combinations,[8][2] unused states or logical remainders[9]) for a boolean function is an input-sequence (a series of bits) for which the function output does not matter. An input that is known never to occur is a can't-happen term.[10][11][12][13] Both these types of conditions are treated the same way in logic design and may be referred to collectively as don't-care conditions for brevity.[14] The designer of a logic circuit to implement the function need not care about such inputs, but can choose the circuit's output arbitrarily, usually such that the simplest, smallest, fastest or cheapest circuit results (minimization) or the power-consumption is minimized.[15][16]

Don't-care terms are important to consider in minimizing logic circuit design, including graphical methods like Karnaugh–Veitch maps and algebraic methods such as the Quine–McCluskey algorithm. In 1958, Seymour Ginsburg proved that minimization of states of a finite-state machine with don't-care conditions does not necessarily yield a minimization of logic elements. Direct minimization of logic elements in such circuits was computationally impractical (for large systems) with the computing power available to Ginsburg in 1958.[17]

Examples

[edit]
Don't-care terms to get minimal circuit
ba
dc
00 01 11 10
00 1 0 0 1
01 0 0 0 1
11 0 0 0 1
10 1 0 0 1
Karnaugh map for lower left segment
ba
dc
00 01 11 10
00 1 0 0 1
01 0 0 0 1
11 x x x x
10 1 0 x x
Digits in 7-segment display
ba
dc
00 01 11 10
00
01
11
10

Examples of don't-care terms are the binary values 1010 through 1111 (10 through 15 in decimal) for a function that takes a binary-coded decimal (BCD) value, because a BCD value never takes on such values (so called pseudo-tetrades); in the pictures, the circuit computing the lower left bar of a 7-segment display can be minimized to a b + a c by an appropriate choice of circuit outputs for dcba = 1010…1111.

Write-only registers, as frequently found in older hardware, are often a consequence of don't-care optimizations in the trade-off between functionality and the number of necessary logic gates.[18]

Don't-care states can also occur in encoding schemes and communication protocols.[nb 1]

X value

[edit]

"Don't care" may also refer to an unknown value in a multi-valued logic system, in which case it may also be called an X value or don't know.[19] In the Verilog hardware description language such values are denoted by the letter "X". In the VHDL hardware description language such values are denoted (in the standard logic package) by the letter "X" (forced unknown) or the letter "W" (weak unknown).[20]

An X value does not exist in hardware. In simulation, an X value can result from two or more sources driving a signal simultaneously, or the stable output of a flip-flop not having been reached. In synthesized hardware, however, the actual value of such a signal will be either 0 or 1, but will not be determinable from the circuit's inputs.[20]

Power-up states

[edit]

Further considerations are needed for logic circuits that involve some feedback. That is, those circuits that depend on the previous output(s) of the circuit as well as its current external inputs. Such circuits can be represented by a state machine. It is sometimes possible that some states that are nominally can't-happen conditions can accidentally be generated during power-up of the circuit or else by random interference (like cosmic radiation, electrical noise or heat). This is also called forbidden input.[21] In some cases, there is no combination of inputs that can exit the state machine into a normal operational state. The machine remains stuck in the power-up state or can be moved only between other can't-happen states in a walled garden of states. This is also called a hardware lockup or soft error. Such states, while nominally can't-happen, are not don't-care, and designers take steps either to ensure that they are really made can't-happen, or else if they do happen, that they create a don't-care alarm indicating an emergency state[21] for error detection, or they are transitory and lead to a normal operational state.[22][23][24]

See also

[edit]

Notes

[edit]

References

[edit]

Further reading

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia
from Grokipedia
In digital logic design, a don't-care term, also known as a don't-care condition, refers to specific input combinations in a where the output value is unspecified or irrelevant, allowing the term to be flexibly assigned as either 0 or 1 to facilitate the simplification of logic expressions. These conditions typically arise in scenarios involving invalid or unused states, such as certain binary codes in representations where inputs like 1010 to 1111 are not valid decimal digits. Don't-care terms play a crucial role in logic minimization techniques, particularly in Karnaugh maps (K-maps), by enabling the formation of larger groupings of adjacent cells, which reduces the number of variables and literals in the resulting sum-of-products (SOP) or product-of-sums (POS) expressions. In a K-map, these terms are represented by symbols such as 'X', 'd', '-', or an asterisk (*), and they are not required to be included in every grouping but can be treated as 1s (for SOP minimization) or 0s (for POS) when it benefits simplification, or ignored entirely if unnecessary. This flexibility often leads to more efficient circuit implementations with fewer gates and reduced complexity, as demonstrated in examples where don't-cares bridge isolated 1s to form octets or quads in multi-variable maps. The use of don't-care terms extends beyond K-maps to other optimization methods like Quine-McCluskey algorithms, enhancing overall digital circuit design by accommodating real-world constraints where not all input combinations need defined outputs. By leveraging these conditions, designers can achieve parsimonious logic that balances functionality with hardware efficiency, a principle fundamental to fields like VLSI and FPGA programming.

Fundamentals

Definition

A don't-care term, also known as a don't-care condition, refers to an input in a or where the corresponding output value is irrelevant to the overall functionality of the digital system. These terms occur when certain inputs are impossible, improbable, or do not affect the desired behavior, providing designers with the option to assign the output as either 0 or 1 during logic synthesis. By treating don't-care terms flexibly, they enable the simplification of Boolean expressions, which reduces circuit complexity, gate count, and potentially power consumption or propagation delay, without altering the outputs for specified input conditions. This approach is particularly valuable in optimization processes where complete truth tables are not fully defined. The application of Boolean algebra to switching circuit design was pioneered by Claude Shannon in his seminal 1938 thesis on relay and switching circuits. The notion of don't-care terms gained prominence in the 1950s with the formalization of logic minimization for incompletely specified functions, including the Quine-McCluskey algorithm developed by Willard V. Quine in 1952 and extended by Edward J. McCluskey in 1956, which explicitly incorporated don't-cares to achieve minimal representations. Don't-cares commonly stem from incomplete design specifications, such as unused states in finite state machines or invalid input codes in decoders, where the system's operation does not depend on those scenarios. This allows for broader applicability in computer-aided design tools that exploit such conditions to generate efficient implementations.

Notation and Representation

In truth tables for Boolean functions, don't-care terms are commonly denoted by the symbol 'X' or 'd' to indicate input combinations where the output value is irrelevant or unspecified. This notation allows designers to leave these entries unspecified, as they do not affect the circuit's required behavior for valid inputs. In Karnaugh maps and minterm lists, don't-care conditions are typically represented by a dash '-' or 'X', signifying that the cell or term can be treated flexibly during simplification without impacting functionality. For instance, in a 3-variable function, the entry f(110) = X denotes a don't-care at that minterm, which may be assigned 0 or 1 to enlarge implicants in sum-of-products or product-of-sums expressions. Across design tools, notations vary to suit simulation and synthesis needs. In hardware description languages like Verilog, don't-cares are handled via 'x' (unknown) or 'z' (high-impedance) in case statements, particularly with casex constructs that treat these as wildcards for pattern matching. In logic minimization software such as Espresso, don't-cares appear in PLA input files as '-' or '2' within cubes to specify the DC-set, enabling optional coverage during optimization. To ensure clarity, guidelines emphasize distinguishing don't-cares from undefined states (e.g., simulation unknowns) or erroneous conditions; don't-cares should be explicitly marked only for verifiable irrelevant inputs, avoiding confusion with uninitialized or invalid behaviors that require separate handling. Consistent use of standardized symbols within a design flow prevents misinterpretation during verification and synthesis.

Applications in Logic Design

Boolean Minimization Techniques

Boolean minimization techniques leverage don't-care terms to simplify Boolean functions by expanding the set of possible prime implicants, enabling larger groupings of minterms in sum-of-products (SOP) or product-of-sums (POS) forms without constraining the output for unspecified input combinations. This approach treats don't-cares as flexible values (assigned as 1 or 0 as beneficial) during the identification of prime implicants, which are the largest possible product terms that cover subsets of the function's minterms. By including don't-cares in the generation of implicants, the minimization process can merge more terms, reducing the overall complexity of the expression while ensuring all specified 1's (for SOP) are covered and 0's are not violated. In SOP form, a key technique involves assigning don't-cares to 1 to facilitate merging of adjacent minterms, thereby eliminating variables (literals) from the product terms. For instance, in a 4-variable Boolean function with don't-cares, appropriate treatment can reduce the number of literals and terms in the expression. This assignment does not affect the function's behavior for specified inputs but allows for broader implicant coverage. The process relies on systematic comparison of binary representations, where don't-cares help bridge differences in bit positions to form larger cubes. The Quine-McCluskey algorithm, a tabular method for minimization, explicitly incorporates don't-cares by listing them alongside minterms in the initial grouping by number of 1's, using them to generate prime implicants through iterative pairwise combinations (differing in one bit). However, during the final implicant chart construction and selection of the minimal cover, don't-cares are not required to be covered, only used to expand potential implicants that subsume specified minterms. This separation ensures completeness while exploiting flexibility, making the algorithm suitable for automation in computer-aided design tools. Exploiting don't-cares in these techniques yields significant benefits, including reduced hardware costs through fewer logic gates, lower power consumption due to simplified circuitry, and decreased propagation delay from shorter signal paths. For example, in finite state machine synthesis, incorporating don't-cares can achieve significant reductions in total gate count. These gains are particularly pronounced in incompletely specified functions common in practical digital designs. A limitation arises from potential overuse of don't-cares, which may lead to unintended output behaviors if the original specifications evolve or if assumptions about unspecified conditions prove incorrect, necessitating re-minimization or verification steps.

Karnaugh Map Usage

In Karnaugh maps, don't-care terms are placed in the cells corresponding to input combinations where the output is unspecified, typically marked with an 'X' or 'd' to distinguish them from definite 0s and 1s. This notation signals that these cells can be flexibly assigned a value of 0 or 1 during grouping to optimize simplification, as the combinations do not occur in the actual system. The process of incorporating don't-cares into K-map simplification follows a structured approach. First, populate the map with the required 1s and 0s from the function specification. Next, insert 'X's in the don't-care cells. Then, form the largest possible rectangular groupings (powers of two, such as 1, 2, 4, or 8 cells) that cover all 1s, including 'X's only if they enlarge the groups and reduce literals; avoid including 'X's if they do not aid coverage. Finally, derive the minimized sum-of-products (SOP) or product-of-sums (POS) expression from the implicants, treating included 'X's as 1s (for SOP) or 0s (for POS) without adding separate terms for them. For instance, in a 4-variable K-map, an isolated 'X' adjacent to a pair of 1s can expand the group to four cells, eliminating two variables and yielding a single product term instead of two. Key rules ensure correct application: don't-cares cannot serve as independent implicants on their own, as they do not represent required function values; instead, they must augment groupings of actual 1s (or 0s) to cover essential prime implicants without over-specifying the function. Uncovered don't-cares remain unspecified in the final expression, defaulting to values that maintain minimality, since they never arise in operation. A representative example demonstrates the impact: consider the 4-variable function F(A,B,C,D)=m(1,3,7,11,15)F(A, B, C, D) = \sum m(1, 3, 7, 11, 15) with don't-cares at d(0,2,5)\sum d(0, 2, 5). Marking the 'X's allows grouping the 1s at positions 1, 3, 0, 2 into a quad yielding ABA' B', and positions 3, 7, 11, 15 into another quad yielding CDC D, resulting in the simplified SOP F=AB+CDF = A' B' + C D. Without the don't-cares (treating them as 0s), the expression simplifies to ABD+CDA' B' D + C D, maintaining two terms but increasing literals from four to five total. Don't-care handling in K-maps is supported in various computer-aided design (CAD) tools for automated generation and analysis, such as Logisim, which permits entry of truth tables with don't-care indicators and outputs minimized expressions alongside visual maps.

Practical Examples

Combinational Circuit Simplification

Don't-care terms play a crucial role in simplifying combinational circuits by allowing designers to treat unspecified input combinations as either 0 or 1 to form larger groups in Karnaugh maps, thereby reducing the number of logic gates required. This approach is particularly useful in partial decoders, where only a subset of input codes is valid, and the circuit behavior for invalid inputs can be ignored. A representative case study involves a partial 3-to-8 decoder circuit with 3-bit inputs (A, B, C), where only three input combinations are valid, leading to specified outputs for those cases and don't-cares (denoted as X) for the remaining five invalid combinations. The truth table excerpt for the output function F is as follows:
ABCF
0001
0010
0101
---X
The full truth table includes X for inputs 011, 100, 101, 110, and 111. Without considering don't-cares, the sum-of-products expression for F would require two product terms: AˉBˉCˉ+AˉBCˉ\bar{A}\bar{B}\bar{C} + \bar{A}B\bar{C}, implemented using two 3-input AND gates and one 2-input OR gate (plus inverters for complemented literals), totaling approximately 8 primitive gates when counting internal transistors or basic components in early designs. Using a Karnaugh map, the don't-care terms enable larger groupings of 1s. The K-map for F(A, B, C) is:

\ C 0 1 AB \ 00 1 (000) 0 (001) 01 1 (010) X (011) 11 X (110) X (111) 10 X (100) X (101)

\ C 0 1 AB \ 00 1 (000) 0 (001) 01 1 (010) X (011) 11 X (110) X (111) 10 X (100) X (101)

The 1s at minterms m0 (000) and m2 (010) form a 2-cell group covering AˉCˉ\bar{A}\bar{C}, as the adjacent cells allow this simplification while excluding the specified 0 at m1 (001). Don't-cares at other cells are not needed for this group but confirm no conflicts. The resulting minimized expression is F=AˉCˉF = \bar{A}\bar{C}, implemented with a single 2-input AND gate (plus one inverter), reducing the gate count to 4 primitive components. Verification of the simplified circuit involves simulation: for valid inputs, F=1 at ABC=000 (0ˉ0ˉ=1\bar{0}\bar{0}=1), F=0 at ABC=001 (0ˉ1ˉ=0\bar{0}\bar{1}=0), and F=1 at ABC=010 (0ˉ0ˉ=1\bar{0}\bar{0}=1); outputs for invalid inputs are ignored, as they match don't-care conditions regardless of the assigned values. In real-world applications, such simplifications using don't-cares are common in multiplexers, where not all select lines correspond to used data inputs, or in priority encoders, where higher-order codes may be invalid and their logic can be optimized away to minimize hardware.

Quine-McCluskey Algorithm Integration

The Quine-McCluskey algorithm adapts to don't-care terms by incorporating them into the prime implicant generation process as if they were minterms (1s), which enables the formation of larger implicants that simplify the coverage of required minterms, while excluding don't-cares from mandatory coverage during the final selection to ensure the function outputs are unspecified only where intended. This tailored integration begins with separate listings of minterms (e.g., denoted as Σm(...)) and don't-cares (e.g., denoted as Σd(...)) for clarity, followed by combining both sets in the tabular columns grouped by the number of 1s in their binary forms; pairs differing in exactly one bit are merged by replacing the differing bit with a dash (-), and this iteration continues across columns until no further combinations are possible, yielding all prime implicants. The subsequent selection phase constructs an implicant chart with required minterms as columns and prime implicants as rows, marking coverage with X's and treating don't-care positions as optional (allowable but not required); if multiple covers exist, Petrick's method resolves the minimal set by forming a consensus product-of-sums expression from uncovered minterms and minimizing it to identify the lowest-cost sum-of-products. This method, originally outlined in its tabular form by McCluskey, systematically handles don't-cares to achieve exact minimization without heuristic approximations. A worked example demonstrates this integration for a 4-variable function F(A, B, C, D) = Σm(0, 2, 5) + Σd(8, 10, 12, 13), where the binary minterms are 0000 (0), 0010 (2), 0101 (5), and don't-cares are 1000 (8), 1010 (10), 1100 (12), 1101 (13). Treating don't-cares as 1s for grouping and combining yields prime implicants including \bar{B}\bar{D} (covering 0, 2, 8, 10), B\bar{C}D (covering 5, 13), A\bar{C}\bar{D} (covering 8, 12), and AB\bar{C} (covering 12, 13); these represent the maximal cubes that cannot be enlarged further while only encompassing specified 1s and don't-cares. The process reduces the initial 7 terms (3 minterms + 4 don't-cares) through successive mergers, avoiding exhaustive enumeration. In the implicant chart, columns for required minterms 0, 2, 5 show \bar{B}\bar{D} covering 0 and 2, and B\bar{C}D covering 5, with don't-cares (e.g., 8, 10, 12, 13) marked as optional X's under relevant rows but not requiring dedicated terms; this yields a minimal cover of \bar{B}\bar{D} + B\bar{C}D, as no single implicant covers all required minterms, and Petrick's method confirms no cheaper alternative by evaluating the expression (implicants covering 0 or 2) · (implicant covering 5), which simplifies to the selected pair. Without don't-cares, the prime implicants would be limited to smaller cubes like \bar{A}\bar{B}\bar{D} (covering 0, 2) and \bar{A}B\bar{C}D (covering 5), potentially generating up to 5 distinct implicants in more fragmented cases, but here don't-cares consolidate to 4 prime implicants and a 2-term cover with fewer literals overall (5 versus 7), illustrating reduced complexity in derivation steps. Compared to Karnaugh maps, the Quine-McCluskey integration of don't-cares excels in scalability for functions with 6 or more variables, where visual mapping becomes impractical, and supports automation in tools like ABC (from UC Berkeley), which implements exact Quine-McCluskey-based minimization for two-level logic, and its predecessor SIS, both widely used in VLSI design flows for handling large-scale don't-care optimization.

Advanced Considerations

Power-Up and Initial States

Upon power-up, flip-flops and other clocked sequential elements in digital circuits often enter unpredictable states due to varying internal thresholds influenced by supply voltage ramps, temperature, and manufacturing variations. These initial states are typically modeled as unknown or don't-care conditions (denoted as X in simulation languages like Verilog) until a valid reset or clock edge establishes a defined logic level. For instance, devices such as the CD74HC4094 shift register require multiple clock edges to flush out indeterminate data before outputs become reliable. To manage these indeterminate initial conditions, designers incorporate power-on reset (POR) circuits that generate a pulse to asynchronously or synchronously force flip-flops and memories into known states, such as all zeros, shortly after supply voltage stabilizes. In FPGA implementations, tools like Intel's Quartus Compiler offer a "Power-Up Don't Care" option, which assigns an indeterminate (X) level to registers without explicit initialization, enabling area optimizations by allowing the synthesis tool to select the most efficient logic value (0 or 1) for power-up. However, for critical paths, explicit resets are recommended to ensure deterministic behavior, as relying on don't-cares can introduce variability in third-party synthesis flows. During simulation, don't-care conditions (X) are leveraged to represent this power-up uncertainty, allowing verification to focus on post-initialization functionality without enumerating all possible transient combinations, thus accelerating the process. In ASIC and FPGA design flows, treating power-up transients as don't-cares facilitates faster verification by permitting static timing analysis and formal checks to ignore short-lived indeterminate states, provided they do not propagate to observable outputs. For example, potential metastable conditions during initial clock synchronization—where flip-flop outputs hover between logic levels—are often analyzed using don't-care modeling to evaluate resolution times without assuming specific outcomes, focusing instead on mean time between failures (MTBF). The IEEE 1149.6 standard, an extension to IEEE 1149.1 (JTAG), provides guidelines for boundary-scan testing, where test receiver outputs in AC-coupled pins are considered don't-cares outside specific capture windows during initial EXTEST instructions, ensuring robust handling of indeterminate boundary conditions without affecting overall test integrity. If initial don't-care states are not properly managed, they can lead to glitches or unintended logic transitions that propagate through the circuit, potentially causing system-level failures during startup. Mitigation involves explicit initialization logic, such as dedicated reset networks or POR supervisors, to override indeterminacy and enforce a safe starting point before normal operation begins.

Implications in Sequential Logic

In finite state machines (FSMs), don't-care terms arise from unused or invalid states, which occur when the number of required states does not fully utilize the encoding space provided by the flip-flops. These unused states can be treated as don't-cares in the next-state logic and output functions, allowing for simplification of the combinational circuitry without affecting the behavior of valid states. For instance, in Moore machines, where outputs depend solely on the current state, arbitrary output assignments can be made for invalid states to further optimize the logic. This approach exploits the fact that the FSM should never reach these states under normal operation, thereby reducing gate count and improving performance. State minimization techniques leverage don't-cares to merge equivalent states, where two states are considered equivalent if they produce the same outputs and transition to equivalent successor states for all inputs. Methods such as partitioning iteratively refine state groups by examining 0- and 1-successors, incorporating don't-cares from unused states to enlarge compatible classes and reduce the total number of states. For example, an FSM initially requiring four states might be minimized to three by assigning don't-cares in implication charts, which decreases the number of flip-flops needed and simplifies the overall circuit. This process ensures that the minimized machine covers all valid behaviors while treating unreachable states opportunistically. A practical illustration is a traffic light controller FSM with six valid states (e.g., green and yellow phases for two directions, plus transitions based on sensors), encoded using three D flip-flops that provide eight possible states total, leaving two unused states as don't-cares. In the transition table, these unused states are marked with don't-cares (X) for next-state and output entries, enabling Karnaugh map simplification of the flip-flop input equations, such as deriving compact expressions for D1 = Q2' + J' · Q1 · Q3' + Q1' · Q3 (where J is a junction sensor input). This results in fewer logic terms compared to assigning specific values to unused states, while maintaining correct sequencing for valid paths. Synthesis tools like Synopsys Design Compiler automatically incorporate don't-cares during HDL processing by using directives such as full_case in Verilog, which treats unspecified case conditions as covered and optimizes away unnecessary logic for unused states in FSMs. Similarly, historical tools like StateCAD (integrated in older Xilinx ISE environments) facilitated graphical FSM modeling with built-in don't-care handling for state tables and transitions. These tools assign don't-cares to invalid states during compilation, streamlining next-state logic generation. Despite these benefits, don't-cares in sequential logic pose challenges, as improper handling of unused states can lead to deadlocks where the FSM enters a trap state that loops indefinitely without external recovery. To mitigate this, self-correcting designs route transitions from unused states back to valid ones, ensuring eventual return to functional behavior even if glitches or faults cause deviation; for example, in sequence detectors, unused states are explicitly mapped to reset to a known valid state. Verification techniques, such as checking for unreachable traps, are essential to prevent such issues in safety-critical applications.

References

Add your contribution
Related Hubs
User Avatar
No comments yet.