Don't-care term

Last updated August 08, 2024

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 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

Don't-care terms to get minimal circuit
ba dc	00	10
00	1	1
01	0	1
11	0	1
10	1	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 ab + ac 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

"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

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]

Notes

↑ Examples of encoding schemes with don't-care states include Hertz encoding, Chen–Ho encoding and Densely packed decimal (DPD).

Related Research Articles

A logic gate is a device that performs a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gate, one that has, for instance, zero rise time and unlimited fan-out, or it may refer to a non-ideal physical device.

<span class="mw-page-title-main">Digital electronics</span> Electronic circuits that utilize digital signals

Digital electronics is a field of electronics involving the study of digital signals and the engineering of devices that use or produce them. This is in contrast to analog electronics which work primarily with analog signals. Despite the name, digital electronics designs includes important analog design considerations.

Transistor–transistor logic (TTL) is a logic family built from bipolar junction transistors. Its name signifies that transistors perform both the logic function and the amplifying function, as opposed to earlier resistor–transistor logic (RTL) and diode–transistor logic (DTL).

In automata theory, sequential logic is a type of logic circuit whose output depends on the present value of its input signals and on the sequence of past inputs, the input history. This is in contrast to combinational logic, whose output is a function of only the present input. That is, sequential logic has state (memory) while combinational logic does not.

The Quine–McCluskey algorithm (QMC), also known as the method of prime implicants, is a method used for minimization of Boolean functions that was developed by Willard V. Quine in 1952 and extended by Edward J. McCluskey in 1956. As a general principle this approach had already been demonstrated by the logician Hugh McColl in 1878, was proved by Archie Blake in 1937, and was rediscovered by Edward W. Samson and Burton E. Mills in 1954 and by Raymond J. Nelson in 1955. Also in 1955, Paul W. Abrahams and John G. Nordahl as well as Albert A. Mullin and Wayne G. Kellner proposed a decimal variant of the method.

Resistor–transistor logic (RTL), sometimes also known as transistor–resistor logic (TRL), is a class of digital circuits built using resistors as the input network and bipolar junction transistors (BJTs) as switching devices. RTL is the earliest class of transistorized digital logic circuit; it was succeeded by diode–transistor logic (DTL) and transistor–transistor logic (TTL).

The IEEE 1164 standard is a technical standard published by the IEEE in 1993. It describes the definitions of logic values to be used in electronic design automation, for the VHDL hardware description language. It was sponsored by the Design Automation Standards Committee of the Institute of Electrical and Electronics Engineers (IEEE). The standardization effort was based on the donation of the Synopsys MVL-9 type declaration.

<span class="mw-page-title-main">Boolean function</span> Function returning one of only two values

In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set. Alternative names are switching function, used especially in older computer science literature, and truth function, used in logic. Boolean functions are the subject of Boolean algebra and switching theory.

In Boolean algebra, any Boolean function can be expressed in the canonical disjunctive normal form (CDNF), minterm canonical form, or Sum of Products as a disjunction (OR) of minterms. The De Morgan dual is the canonical conjunctive normal form (CCNF), maxterm canonical form, or Product of Sums which is a conjunction (AND) of maxterms. These forms can be useful for the simplification of Boolean functions, which is of great importance in the optimization of Boolean formulas in general and digital circuits in particular.

In computer engineering, logic synthesis is a process by which an abstract specification of desired circuit behavior, typically at register transfer level (RTL), is turned into a design implementation in terms of logic gates, typically by a computer program called a synthesis tool. Common examples of this process include synthesis of designs specified in hardware description languages, including VHDL and Verilog. Some synthesis tools generate bitstreams for programmable logic devices such as PALs or FPGAs, while others target the creation of ASICs. Logic synthesis is one step in circuit design in the electronic design automation, the others are place and route and verification and validation.

Asynchronous circuit is a sequential digital logic circuit that does not use a global clock circuit or signal generator to synchronize its components. Instead, the components are driven by a handshaking circuit which indicates a completion of a set of instructions. Handshaking works by simple data transfer protocols. Many synchronous circuits were developed in early 1950s as part of bigger asynchronous systems. Asynchronous circuits and theory surrounding is a part of several steps in integrated circuit design, a field of digital electronics engineering.

The algorithmic state machine (ASM) is a method for designing finite state machines (FSMs) originally developed by Thomas E. Osborne at the University of California, Berkeley (UCB) since 1960, introduced to and implemented at Hewlett-Packard in 1968, formalized and expanded since 1967 and written about by Christopher R. Clare since 1970. It is used to represent diagrams of digital integrated circuits. The ASM diagram is like a state diagram but more structured and, thus, easier to understand. An ASM chart is a method of describing the sequential operations of a digital system.

In logic, a four-valued logic is any logic with four truth values. Several types of four-valued logic have been advanced.

In digital logic, a hazard is an undesirable effect caused by either a deficiency in the system or external influences in both synchronous and asynchronous circuits. Logic hazards are manifestations of a problem in which changes in the input variables do not change the output correctly due to some form of delay caused by logic elements This results in the logic not performing its function properly. The three different most common kinds of hazards are usually referred to as static, dynamic and function hazards.

In digital circuits, a logic level is one of a finite number of states that a digital signal can inhabit. Logic levels are usually represented by the voltage difference between the signal and ground, although other standards exist. The range of voltage levels that represent each state depends on the logic family being used. A logic-level shifter can be used to allow compatibility between different circuits.

Logic optimization is a process of finding an equivalent representation of the specified logic circuit under one or more specified constraints. This process is a part of a logic synthesis applied in digital electronics and integrated circuit design.

The Karnaugh map is a method of simplifying Boolean algebra expressions. Maurice Karnaugh introduced it in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which itself was a rediscovery of Allan Marquand's 1881 logical diagram aka Marquand diagram but now with a focus set on its utility for switching circuits. Veitch charts are also known as Marquand–Veitch diagrams, Svoboda charts -(albeit only rarely)- and even Karnaugh maps as Karnaugh–Veitch maps.

The ESPRESSO logic minimizer is a computer program using heuristic and specific algorithms for efficiently reducing the complexity of digital logic gate circuits. ESPRESSO-I was originally developed at IBM by Robert K. Brayton et al. in 1982. and improved as ESPRESSO-II in 1984. Richard L. Rudell later published the variant ESPRESSO-MV in 1986 and ESPRESSO-EXACT in 1987. Espresso has inspired many derivatives.

Switching circuit theory is the mathematical study of the properties of networks of idealized switches. Such networks may be strictly combinational logic, in which their output state is only a function of the present state of their inputs; or may also contain sequential elements, where the present state depends on the present state and past states; in that sense, sequential circuits are said to include "memory" of past states. An important class of sequential circuits are state machines. Switching circuit theory is applicable to the design of telephone systems, computers, and similar systems. Switching circuit theory provided the mathematical foundations and tools for digital system design in almost all areas of modern technology.

In electronics, flip-flops and latches are circuits that have two stable states that can store state information – a bistable multivibrator. The circuit can be made to change state by signals applied to one or more control inputs and will output its state. It is the basic storage element in sequential logic. Flip-flops and latches are fundamental building blocks of digital electronics systems used in computers, communications, and many other types of systems.

References

↑ Karnaugh, Maurice (November 1953) [1953-04-23, 1953-03-17]. "The Map Method for Synthesis of Combinational Logic Circuits" (PDF). Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics . 72 (5): 593–599. doi:10.1109/TCE.1953.6371932. S2CID 51636736. Paper 53-217. Archived from the original (PDF) on 2017-04-16. Retrieved 2017-04-16. (7 pages)
1 2 3 4 Phister, Jr., Montgomery (April 1959) [December 1958]. Logical design of digital computers. Digital Design and Applications (3rd printing, 1st ed.). New York, USA: John Wiley & Sons Inc. p. 97. ISBN 0-47168805-3. LCCN 58-6082. MR 0093930. ISBN 978-0-47168805-1. p. 97: […] These prohibited combinations will here be called redundancies (they have also been called irrelevancies, "don't cares," and forbidden combinations), and they can usually be used to simplify Boolean functions. […] (xvi+408 pages)
↑ Caldwell, Samuel Hawks (1958-12-01) [February 1958]. Written at Watertown, Massachusetts, USA. Switching Circuits and Logical Design. 5th printing September 1963 (1st ed.). New York, USA: John Wiley & Sons Inc. ISBN 0-47112969-0. LCCN 58-7896. (xviii+686 pages)
1 2 3 Moore, Edward Forrest (December 1958). "Samuel H. Caldwell. Switching circuits and logical design. John Wiley & Sons, Inc., New York 1958, and Chapman & Hall Limited, London 1958, xvii + 686 pp". The Journal of Symbolic Logic (Review). 23 (4): 433–434. doi:10.2307/2964020. JSTOR 2964020. S2CID 57495605. p. 433: […] what Caldwell calls "optional entries" […] other authors have called "invalid combinations", "don't cares", "vacuous combinations" […] (2 pages)
↑ Keister, William; Ritchie, Alistair E.; Washburn, Seth H. (1951). The Design Of Switching Circuits. The Bell Telephone Laboratories Series (1 ed.). D. Van Nostrand Company, Inc. p. 147. Archived from the original on 2020-05-09. Retrieved 2020-05-09. (2+xx+556+2 pages)
↑ Marcus, Mitchell Paul [at Wikidata] (c. 1970). "Chapter 6. Tabular method of simplification: Optional combinations". Written at IBM, Endicott / Binghampton, New York, USA. Switching circuits for engineers. Habana, Cuba: Edicion Revolucionaria, Instituto del Libro. pp. 70–72 [71]. 19 No. 1002. (xiv+2+296+2 pages)
↑ Aiken, Howard H.; Blaauw, Gerrit; Burkhart, William; Burns, Robert J.; Cali, Lloyd; Canepa, Michele; Ciampa, Carmela M.; Coolidge, Jr., Charles A.; Fucarile, Joseph R.; Gadd, Jr., J. Orten; Gucker, Frank F.; Harr, John A.; Hawkins, Robert L.; Hayes, Miles V.; Hofheimer, Richard; Hulme, William F.; Jennings, Betty L.; Johnson, Stanley A.; Kalin, Theodore; Kincaid, Marshall; Lucchini, E. Edward; Minty, William; Moore, Benjamin L.; Remmes, Joseph; Rinn, Robert J.; Roche, John W.; Sanbord, Jacquelin; Semon, Warren L.; Singer, Theodore; Smith, Dexter; Smith, Leonard; Strong, Peter F.; Thomas, Helene V.; Wang, An; Whitehouse, Martha L.; Wilkins, Holly B.; Wilkins, Robert E.; Woo, Way Dong; Little, Elbert P.; McDowell, M. Scudder (1952) [January 1951]. Synthesis of electronic computing and control circuits. The Annals of the Computation Laboratory of Harvard University. Vol. XXVII (second printing, revised ed.). Write-Patterson Air Force Base: Harvard University Press (Cambridge, Massachusetts, USA) / Geoffrey Cumberlege Oxford University Press (London). ark:/13960/t4zh1t09d. Retrieved 2017-04-16. (2+x+278+2 pages) (NB. Work commenced in April 1948.)
↑ Kautz, William H. (June 1954). "Optimized Data Encoding for Digital Computers". Convention Record of the I.R.E., 1954 National Convention, Part 4 - Electronic Computers and Information Theory. Session 19: Information Theory III - Speed and Computation. Stanford Research Institute, Stanford, California, USA: I.R.E.: 47–57. Archived from the original on 2020-07-03. Retrieved 2020-07-03. (11 pages)
↑ Rushdi, Ali Muhammad Ali; Badawi, Raid Mohammad Salih (January 2017). "Karnaugh-Map Utilization in Boolean Analysis: The Case of War Termination". Journal of Engineering and Computer Sciences. Qualitative Comparative Analysis. 10 (1). Department of Electrical and Computer Engineering, King Abdulaziz University, Jeddah, Saudi Arabi / Qassim University: 53–88 [54–55, 57, 61–63]. Rabi'II 1438H. Archived from the original on 2021-02-16. Retrieved 2021-02-17.
↑ Morris, Noel Malcolm (January 1969) [1968-12-16]. "Code and Code Converters - Part 2: Mapping techniques and code converters" (PDF). Wireless World . 75 (1399). Iliffe Technical Publications Ltd.: 34–37. Archived (PDF) from the original on 2021-03-09. Retrieved 2020-05-09.
↑ Morris, Noel Malcolm (1969). Logic Circuits. European electrical and electronic engineering series (1 ed.). London, UK: McGraw-Hill. pp. 31, 96, 114. ISBN 0-07094106-8. LCCN 72458600. ISBN 978-0-07094106-9. NCID BA12104142 . Retrieved 2021-03-28. p. 31: […] sometimes known as a can't happen condition […] (x+189 pages)
↑ Association Internationale pour le Calcul Analogique (AICA), ed. (1970) [1969-09-15]. "unknown". Colloque international / International Symposium. Systèmes logiques: Conception et applications / Design and Applications of Logical Systems. Actes / Proceedings. Bruxelles, 15–20 septembre 1969 / Brussels, September 15–20, 1969. (in English and French). Part 2. Bruxelles, Belgium: Presses Académiques Européennes: 1253. Retrieved 2021-03-28.{{cite journal}}: Cite uses generic title (help) (xxxiii+650+676 pages)
↑ Holdsworth, Brian; Woods, Clive (2002). Digital Logic Design (4 ed.). Newnes Books / Elsevier Science. pp. 55–56, 251. ISBN 0-7506-4588-2. ISBN 978-0-08047730-5 . Retrieved 2020-04-19.{{cite book}}: CS1 maint: ignored ISBN errors (link) (519 pages)
↑ Strong, John A., ed. (2013-03-12) [1991]. "Chapter 2.11 Hazards and Glitches". Basic Digital Electronics. Physics and Its Applications. Vol. 2 (reprint of 1st ed.). Chapman & Hall / Springer Science & Business Media, B.V. pp. 28–29. ISBN 978-9-40113118-6. LCCN 90-2689 . Retrieved 2020-03-30. (220 pages)
↑ Iman, Sasan; Pedram, Massoud (1998) [1997-11-30]. "Chapter 6. Logic Minimization for Low Power". Written at University of Southern California, California, USA. Logic Synthesis for Low Power VLSI Designs (1 ed.). Boston, Massachusetts, USA / New York, USA: Kluwer Academic Publishers / Springer Science+Business Media, LLC. pp. 109–148 [110]. doi:10.1007/978-1-4615-5453-0_6. ISBN 978-0-7923-8076-4. LCCN 97-042097. Archived from the original on 2024-07-26. Retrieved 2024-07-26. (xv+236 pages)
↑ Maiti, Tapas Kr.; Chattopadhyay, Santanu (2008-05-18). Don't care filling for power minimization in VLSI circuit testing. 2008 IEEE International Symposium on Circuits and Systems (ISCAS) (1 ed.). Seattle, Washington, USA: Institute of Electrical and Electronics Engineers. pp. 2637–2640. doi:10.1109/ISCAS.2008.4541998. eISSN 2158-1525. ISBN 978-1-4244-1683-7. ISSN 0271-4302.
↑ Ginsburg, Seymour (1959-04-01). "On the Reduction of Superfluous States in a Sequential Machine". Journal of the ACM . 6 (2): 259–282. doi: 10.1145/320964.320983 . S2CID 10118067.
↑ Toshiba 8 Bit Microcontroller TLCS-870/C Series TMP86PM29BUG (2 ed.). Toshiba Corporation. 2008-08-29 [2007-10-11]. p. 61. Archived from the original on 2020-04-19. p. 61: […] WDTCR1 is a write-only register and must not be used with any of read-modify-write instructions. If WDTCR1 is read, a don't care is read. […] (9+vi+190 pages)
↑ Katz, Randy Howard (1994) [May 1993]. "Chapter 2.2.4 Incompletely Specified Functions". Written at Berkeley, California, USA. Contemporary Logic Design (1 ed.). Redwood City, California, USA: The Benjamin/Cummings Publishing Company, Inc. p. 64. ISBN 0-8053-2703-7. 32703-7. p. 64: […] The output functions have the value "X" for each of the input combinations we should never encounter. When used in a truth tables, the value X is often called a don't care. Do not confuse this with the value X reported by many logic simulators, where it represents an undefined value or a don't know. Any actual implementation of the circuit will generate some output for the don't care cases. […] (2+xxviii+699+10+2 pages)
1 2 Naylor, David; Jones, Simon (May 1997). VHDL: A Logic Synthesis Approach (reprint of 1st ed.). Chapman & Hall / Cambridge University Press / Springer Science & Business Media. pp. 14–15, 219, 221. ISBN 0-412-61650-5 . Retrieved 2020-03-30. (x+327 pages)
1 2 Lind, Larry Frederick; Nelson, John Christopher Cunliffe (1977-04-01). "2.3.7. Don't cares". Analysis and Design of Sequential Digital Systems. Electrical and Electronic Engineering (1 ed.). London & Basingstoke, UK: The Macmillan Press Ltd. pp. 20, 121–122. doi:10.1007/978-1-349-15757-0. ISBN 0-333-19266-4. Archived from the original on 2020-04-30. Retrieved 2020-04-30. (4+viii+146+6 pages)
↑ Kumar, Ramayya; Kropf, Thomas, eds. (1995). "Theorem Provers in Circuit Design". Proceedings of the Second International Conference, TPCD '94, Bad Herrenalb, Germany, September 26–28, 1994. Lecture Notes in Computer Science. Vol. 901 (1st ed.). Springer-Verlag Berlin Heidelberg. p. 136. doi:10.1007/3-540-59047-1. ISBN 978-3-540-59047-7. ISSN 0302-9743. S2CID 42116934 . Retrieved 2020-03-30. (viii+312 pages)
↑ "Power-Up Don't Care logic option". Quartus Help. Intel Corporation. 2017. Archived from the original on 2020-04-19. Retrieved 2020-04-19.
↑ "Power-up level of register <name> is not specified – using unspecifed power-up level". Knowledge Base. Intel Corporation. 2020. Archived from the original on 2020-04-19. Retrieved 2020-04-19.