Switching circuit theory

Last updated

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

Contents

In an 1886 letter, Charles Sanders Peirce described how logical operations could be carried out by electrical switching circuits. [2] During 1880–1881 he showed that NOR gates alone (or alternatively NAND gates alone) can be used to reproduce the functions of all the other logic gates, but this work remained unpublished until 1933. [3] The first published proof was by Henry M. Sheffer in 1913, so the NAND logical operation is sometimes called Sheffer stroke; the logical NOR is sometimes called Peirce's arrow. [4] Consequently, these gates are sometimes called universal logic gates. [5]

In 1898, Martin Boda described a switching theory for signalling block systems. [6] [7]

Eventually, vacuum tubes replaced relays for logic operations. Lee De Forest's modification, in 1907, of the Fleming valve can be used as a logic gate. Ludwig Wittgenstein introduced a version of the 16-row truth table as proposition 5.101 of Tractatus Logico-Philosophicus (1921). Walther Bothe, inventor of the coincidence circuit, got part of the 1954 Nobel Prize in physics, for the first modern electronic AND gate in 1924. Konrad Zuse designed and built electromechanical logic gates for his computer Z1 (from 1935 to 1938).

The theory was independently established through the works of NEC engineer Akira Nakashima in Japan, [8] Claude Shannon in the United States, [9] and Victor Shestakov in the Soviet Union. [10] The three published a series of papers showing that the two-valued Boolean algebra, can describe the operation of switching circuits. [7] [11] [12] [13] [1] However, Shannon's work has largely overshadowed the other two, and despite some scholars arguing the similarities of Nakashima's work to Shannon's, their approaches and theoretical frameworks were markedly different. [14] Also implausible is that Shestakov's influenced the other two due to the language barriers and the relative obscurity of his work abroad. [14] Furthermore, Shannon and Shestakov defended their theses the same year in 1938, [15] and Shestakov did not publish until 1941. [15]

Ideal switches are considered as having only two exclusive states, for example, open or closed. In some analysis, the state of a switch can be considered to have no influence on the output of the system and is designated as a "don't care" state. In complex networks it is necessary to also account for the finite switching time of physical switches; where two or more different paths in a network may affect the output, these delays may result in a "logic hazard" or "race condition" where the output state changes due to the different propagation times through the network.

See also

Related Research Articles

<span class="mw-page-title-main">Claude Shannon</span> American mathematician and information theorist (1916–2001)

Claude Elwood Shannon was an American mathematician, electrical engineer, computer scientist and cryptographer known as the "father of information theory" and as the "father of the Information Age". Shannon was the first to describe the Boolean gates that are essential to all digital electronic circuits, and was one of the founding fathers of artificial intelligence. He is credited alongside George Boole for laying the foundations of the Information Age.

<span class="mw-page-title-main">Logical conjunction</span> Logical connective AND

In logic, mathematics and linguistics, and is the truth-functional operator of conjunction or logical conjunction. The logical connective of this operator is typically represented as or or (prefix) or or in which is the most modern and widely used.

<span class="mw-page-title-main">Logic gate</span> Device performing a Boolean function

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">George Boole</span> English mathematician, philosopher and logician (1815–1864)

George BooleJnr was a largely self-taught English mathematician, philosopher, and logician, most of whose short career was spent as the first professor of mathematics at Queen's College, Cork in Ireland. He worked in the fields of differential equations and algebraic logic, and is best known as the author of The Laws of Thought (1854) which contains Boolean algebra. Boolean logic is credited with laying the foundations for the Information Age alongside the work of Claude Shannon.

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

<span class="mw-page-title-main">Timeline of computing hardware before 1950</span>

This article presents a detailed timeline of events in the history of computing software and hardware: from prehistory until 1949. For narratives explaining the overall developments, see History of computing.

<span class="mw-page-title-main">Combinational logic</span> Type of digital logic implemented by boolean circuits

In automata theory, combinational logic is a type of digital logic that is implemented by Boolean circuits, where the output is a pure function of the present input only. This is in contrast to sequential logic, in which the output depends not only on the present input but also on the history of the input. In other words, sequential logic has memory while combinational logic does not.

<span class="mw-page-title-main">History of computing</span>

The history of computing is longer than the history of computing hardware and modern computing technology and includes the history of methods intended for pen and paper or for chalk and slate, with or without the aid of tables.

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

<span class="mw-page-title-main">Jaakko Hintikka</span> Finnish philosopher and logician

Kaarlo Jaakko Juhani Hintikka was a Finnish philosopher and logician. Hintikka is regarded as the founder of formal epistemic logic and of game semantics for logic.

<span class="mw-page-title-main">History of computer science</span>

The history of computer science began long before the modern discipline of computer science, usually appearing in forms like mathematics or physics. Developments in previous centuries alluded to the discipline that we now know as computer science. This progression, from mechanical inventions and mathematical theories towards modern computer concepts and machines, led to the development of a major academic field, massive technological advancement across the Western world, and the basis of a massive worldwide trade and culture.

In logic, a functionally complete set of logical connectives or Boolean operators is one that can be used to express all possible truth tables by combining members of the set into a Boolean expression. A well-known complete set of connectives is { AND, NOT }. Each of the singleton sets { NAND } and { NOR } is functionally complete. However, the set { AND, OR } is incomplete, due to its inability to express NOT.

Logic is the formal science of using reason and is considered a branch of both philosophy and mathematics and to a lesser extent computer science. Logic investigates and classifies the structure of statements and arguments, both through the study of formal systems of inference and the study of arguments in natural language. The scope of logic can therefore be very large, ranging from core topics such as the study of fallacies and paradoxes, to specialized analyses of reasoning such as probability, correct reasoning, and arguments involving causality. One of the aims of logic is to identify the correct and incorrect inferences. Logicians study the criteria for the evaluation of arguments.

<span class="mw-page-title-main">Boolean circuit</span> Model of computation

In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible input length.

Victor Ivanovich Shestakov (1907–1987) was a Russian/Soviet logician and theoretician of electrical engineering. In 1935 he discovered the possible interpretation of Boolean algebra of logic in electro-mechanical relay circuits. He graduated from Moscow State University (1934) and worked there in the General Physics Department almost until his death.

A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, Boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional arguments, that is, for each combination of values taken by their logical variables. In particular, truth tables can be used to show whether a propositional expression is true for all legitimate input values, that is, logically valid.

The timeline of music technology provides the major dates in the history of electric music technologies inventions from the 1800s to the early 1900s and electronic and digital music technologies from 1874 to the 2010s.

In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values true and false, usually denoted 1 and 0, whereas in elementary algebra the values of the variables are numbers. Second, Boolean algebra uses logical operators such as conjunction (and) denoted as , disjunction (or) denoted as , and negation (not) denoted as ¬. Elementary algebra, on the other hand, uses arithmetic operators such as addition, multiplication, subtraction, and division. Boolean algebra is therefore a formal way of describing logical operations in the same way that elementary algebra describes numerical operations.

<span class="mw-page-title-main">Akira Nakashima</span> Japanese electrical engineer

Akira Nakashima was a Japanese electrical engineer of the NEC.

References

  1. 1 2 Stanković, Radomir S. [in German]; Astola, Jaakko Tapio [in Finnish], eds. (2008). Reprints from the Early Days of Information Sciences: TICSP Series on the Contributions of Akira Nakashima to Switching Theory (PDF). Tampere International Center for Signal Processing (TICSP) Series. Vol. 40. Tampere University of Technology, Tampere, Finland. ISBN   978-952-15-1980-2. ISSN   1456-2774. Archived from the original (PDF) on 2021-03-08.{{cite book}}: CS1 maint: location missing publisher (link) (3+207+1 pages) 10:00 min
  2. Peirce, Charles Sanders (1993) [1886]. "Letter, Peirce to A. Marquand". Writings of Charles S. Peirce . Vol. 5. pp. 421–423. See also: Burks, Arthur Walter (1978). "Review: Charles S. Peirce, The new elements of mathematics". Bulletin of the American Mathematical Society (review). 84 (5): 913–918 [917]. doi: 10.1090/S0002-9904-1978-14533-9 .
  3. Peirce, Charles Sanders (1933) [Winter of 1880–1881]. "A Boolian Algebra with One Constant". Collected Papers (manuscript). Vol. 4. paragraphs 12–20. Reprinted in Writings of Charles S. Peirce. Vol. 4 (reprint ed.). 1989. pp. 218–221. ISBN   9780253372017. ark:/13960/t11p5r61f. See also: Roberts, Don D. (2009). The Existential Graphs of Charles S. Peirce. p. 131.
  4. Kleine Büning, Hans; Lettmann, Theodor (1999). Propositional logic: deduction and algorithms. Cambridge University Press. p. 2. ISBN   978-0-521-63017-7.
  5. Bird, John (2007). Engineering mathematics. Newnes. p. 532. ISBN   978-0-7506-8555-9.
  6. Boda, Martin (1898). "Die Schaltungstheorie der Blockwerke" [The switching theory of block systems]. Organ für die Fortschritte des Eisenbahnwesens in technischer Beziehung – Fachblatt des Vereins deutscher Eisenbahn-Verwaltungen (in German). Neue Folge XXXV (1–7). Wiesbaden, Germany: C. W. Kreidel's Verlag: 1–7, 29–34, 49–53, 71–75, 91–95, 111–115, 133–138. (NB. This series of seven articles was republished in a 91-pages book in 1899 with a foreword by Georg Barkhausen  [ de ].)
  7. 1 2 Klir, George Jiří (May 1972). "Reference Notations to Chapter 1". Introduction to the Methodology of Switching Circuits (1 ed.). Binghamton, New York, USA: Litton Educational Publishing, Inc. / D. van Nostrand Company. p. 19. ISBN   0-442-24463-0. LCCN   72-181095. C4463-000-3. p. 19: Although the possibility of establishing a switching theory was recognized by M. Boda [A] as early as in the 19th century, the first important works on this subject were published by A. Nakashima [B] and C. E. Shannon [C] shortly before World War II. (xvi+573+1 pages)
  8. Nakashima, Akira (May 1936). "Theory of Relay Circuit Composition". Nippon Electrical Communication Engineering (3): 197–226. (NB. Translation of an article which originally appeared in Japanese in the Journal of the Institute of Telegraph and Telephone Engineers of Japan (JITTEJ) September 1935, 150 731–752.)
  9. Shannon, Claude Elwood (1938). "A Symbolic Analysis of Relay and Switching Circuits". Transactions of the American Institute of Electrical Engineers . 57 (12). American Institute of Electrical Engineers (AIEE): 713–723. doi:10.1109/T-AIEE.1938.5057767. hdl: 1721.1/11173 . S2CID   51638483. (NB. Based on Shannon's master thesis of the same title at Massachusetts Institute of Technology in 1937.)
  10. Shestakov [Шестаков], Victor Ivanovich [Виктор Иванович] (1938). Некоторые математические методы кон-струирования и упрощения двухполюсных электрических схем класса А[Some mathematical methods for the construction and simplification of two-terminal electrical networks of class A] (PhD thesis) (in Russian). Lomonosov State University.
  11. Yamada [山田], Akihiko [彰彦] (2004). "History of Research on Switching Theory in Japan". IEEJ Transactions on Fundamentals and Materials. 124 (8). Institute of Electrical Engineers of Japan: 720–726. Bibcode:2004IJTFM.124..720Y. doi: 10.1541/ieejfms.124.720 . Archived from the original on 2022-07-10. Retrieved 2022-10-26.
  12. "Switching Theory/Relay Circuit Network Theory/Theory of Logical Mathematics". IPSJ Computer Museum. Information Processing Society of Japan. 2012. Archived from the original on 2021-03-22. Retrieved 2021-03-28.
  13. Stanković, Radomir S. [in German]; Astola, Jaakko Tapio [in Finnish]; Karpovsky, Mark G. (2007). Some Historical Remarks on Switching Theory (PDF). Niš, Serbia; Tampere, Finland; Boston, Massachusetts, USA. CiteSeerX   10.1.1.66.1248 . S2CID   10029339. Archived (PDF) from the original on 2022-10-25. Retrieved 2022-10-25.{{cite book}}: CS1 maint: location missing publisher (link) (8 pages)
  14. 1 2 Kawanishi, Toma (2019). "Prehistory of Switching Theory in Japan: Akira Nakashima and His Relay-circuit Theory". Historia Scientiarum. Second Series. 29 (1): 136–162. doi:10.34336/historiascientiarum.29.1_136.
  15. 1 2 Moisil, GR. C. (1969). The Algebraic Theory of Switching Circuits. Pergamon Press. pp. 12, 17. ISBN   9781483160764.

Further reading