Editing Many-valued logic (section)

== Applications ==

Known applications of many-valued logic can be roughly classified into two groups.<ref>Dubrova, Elena (2002). [http://dl.acm.org/citation.cfm?id=566849 Multiple-Valued Logic Synthesis and Optimization], in Hassoun S. and Sasao T., editors, ''Logic Synthesis and Verification'', Kluwer Academic Publishers, pp. 89-114</ref> The first group uses many-valued logic to solve binary problems more efficiently. For example, a well-known approach to represent a multiple-output Boolean function is to treat its output part as a single many-valued variable and convert it to a single-output [[characteristic function]] (specifically, the [[indicator function]]). Other applications of many-valued logic include design of [[programmable logic array]]s (PLAs) with input decoders, optimization of [[finite-state machine]]s, testing, and verification.

The second group targets the design of electronic circuits that employ more than two discrete levels of signals, such as many-valued memories, arithmetic circuits, and [[field programmable gate array]]s (FPGAs). Many-valued circuits have a number of theoretical advantages over standard binary circuits. For example, the interconnect on and off chip can be reduced if signals in the circuit assume four or more levels rather than only two. In memory design, storing two instead of one bit of information per memory cell doubles the density of the memory in the same [[Die (integrated circuit)|die]] size. Applications using arithmetic circuits often benefit from using alternatives to binary number systems. For example, [[residue number system|residue]] and [[Redundant binary representation|redundant number systems]]<ref name="Meher_2009">{{cite journal |first1=Pramod Kumar |last1=Meher |first2=Javier |last2=Valls |first3=Tso-Bing |last3=Juang | first4=K. |last4=Sridharan |first5=Koushik |last5=Maharatna |title=50 Years of CORDIC: Algorithms, Architectures and Applications |journal=IEEE Transactions on Circuits & Systems I: Regular Papers |volume=56 |issue=9 |pages=1893–1907 |publication-date=2009-09-09 |date=2008-08-22<!-- revised November 26, 2008-11-26, 2009-04-10, first published: 2009-06-19, current version first published: 2009-09-02 --> |url=http://core.ac.uk/download/files/34/1509903.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://core.ac.uk/download/files/34/1509903.pdf |archive-date=2022-10-09 |url-status=live |access-date=2016-01-03|doi=10.1109/TCSI.2009.2025803 |s2cid=5465045 }}<!-- ([http://www1.i2r.a-star.edu.sg/~pkmeher/papers/CORDIC-TUT-TACS-I.pdf]) --></ref> can reduce or eliminate the [[ripple-carry adder|ripple-through carries]] that are involved in normal binary addition or subtraction, resulting in high-speed arithmetic operations. These number systems have a natural implementation using many-valued circuits. However, the practicality of these potential advantages heavily depends on the availability of circuit realizations, which must be compatible or competitive with present-day standard technologies. In addition to aiding in the design of electronic circuits, many-valued logic is used extensively to test circuits for faults and defects. Basically all known [[automatic test pattern generation]] (ATG) algorithms used for digital circuit testing require a simulator that can resolve 5-valued logic (0, 1, x, D, D').<ref name="Abramovici 1994">{{cite book |last1=Abramovici |first1=Miron |last2=Breuer |first2=Melvin A. |last3=Friedman |first3=Arthur D. |date=1994 |title=Digital Systems Testing and Testable Design |url=https://archive.org/details/digitalsystemste00abra |url-access=limited |location=New York |publisher=Computer Science Press |page=[https://archive.org/details/digitalsystemste00abra/page/n196 183] |isbn=978-0-7803-1062-9 }}</ref> The additional values—x, D, and D'—represent (1) unknown/uninitialized, (2) a 0 instead of a 1, and (3) a 1 instead of a 0.