Don't-care term

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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] vacuous combinations,[6][4] forbidden combinations,[2] or unused states) 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.[7][8] 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.[9] 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 circuit results (minimization).

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.

Examples[edit]

Don't-care terms chosen 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 Dígito c0.svg Dígito c1.svg Dígito c3.svg Dígito c2.svg
01 Dígito c4.svg Dígito c5.svg Dígito c7.svg Dígito c6.svg
11
10 Dígito c8.svg Dígito c9.svg

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.[10]

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.[11] 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).[12]

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.[12]

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.[13] 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[13] for error detection, or they are transitory and lead to a normal operational state.[14][15][16]

See also[edit]

Notes[edit]

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

References[edit]

  1. ^ 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. Paper 53-217. Archived from the original (PDF) on 2017-04-16. Retrieved 2017-04-16. (7 pages)
  2. ^ a b c d 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. […] 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)
  3. ^ 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)
  4. ^ a b c 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. […] what Caldwell calls "optional entries" […] other authors have called "invalid combinations", "don't cares", "vacuous combinations" […] (2 pages)
  5. ^ 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. [1] (2+xx+556+2 pages)
  6. ^ 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. XXVII (second printing, revised ed.). Write-Patterson Air Force Base: Harvard University Press (Cambridge, Massachusetts, USA) / Geoffrey Cumberlege Oxford University Press (London). Retrieved 2017-04-16. (2+x+278+2 pages) (NB. Work commenced in April 1948.)
  7. ^ "Minimisation using the map method". Wireless World. I.P.C. Business Press Limited. 75 (Part 2): 72. 1969. Archived from the original on 2020-05-09. Retrieved 2020-05-09.
  8. ^ 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.CS1 maint: ignored ISBN errors (link) (519 pages) [2]
  9. ^ Strong, John A., ed. (2013-03-12) [1991]. "Chapter 2.11 Hazards and Glitches". Basic Digital Electronics. Physics and Its Applications. 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)
  10. ^ 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. […] 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)
  11. ^ 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. […] 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)
  12. ^ a b 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)
  13. ^ a b 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)
  14. ^ Kumar, Ramayya; Kropf, Thomas, eds. (1995). Theorem Provers in Circuit Design: Theory, Practice and Experience. Proceedings of the Second International Conference, TPCD '94, Bad Herrenalb, Germany, September 26–28, 1994. Lecture Notes in Computer Science. 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. Retrieved 2020-03-30. (viii+312 pages)
  15. ^ "Power-Up Don't Care logic option". Quartus Help. Intel Corporation. 2017. Archived from the original on 2020-04-19. Retrieved 2020-04-19.
  16. ^ "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.