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]

In digital circuit theory, combinational logic is a type of digital logic which 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.

In digital circuit theory, sequential logic is a type of logic circuit whose output depends not only on the present value of its input signals but on the sequence of past inputs, the input history as well. 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.

Digital electronics or digital (electronic) circuits are electronics that operate on digital signals. In contrast, analog circuits manipulate analog signals whose performance is more subject to manufacturing tolerance, signal attenuation and noise. Digital techniques are helpful because it is a lot easier to get an electronic device to switch into one of a number of known states than to accurately reproduce a continuous range of values.

Contents

From 1934 to 1936, NEC engineer Akira Nakashima published a series of papers showing that the two-valued Boolean algebra, which he discovered independently, can describe the operation of switching circuits. [2] [3] [4] [1] His work was later cited and elaborated on in Claude Shannon's seminal 1938 paper "A Symbolic Analysis of Relay and Switching Circuits". [4] The principles of Boolean algebra are applied to switches, providing mathematical tools for analysis and synthesis of any switching system.

NEC Corporation is a Japanese multinational provider of information technology (IT) services and products, headquartered in Minato, Tokyo, Japan. It provides IT and network solutions to business enterprises, communications services providers and to government agencies, and has also been the biggest PC vendor in Japan since the 1980s. The company was known as the Nippon Electric Company, Limited, before rebranding in 1983 as NEC.

In mathematics and abstract algebra, the two-element Boolean algebra is the Boolean algebra whose underlying setB is the Boolean domain. The elements of the Boolean domain are 1 and 0 by convention, so that B = {0, 1}. Paul Halmos's name for this algebra "2" has some following in the literature, and will be employed here.

Claude Elwood Shannon was an American mathematician, electrical engineer, and cryptographer known as "the father of information theory". Shannon is noted for having founded information theory with a landmark paper, A Mathematical Theory of Communication, that he published in 1948.

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.

In digital logic, a hazard in a system is an undesirable effect caused by either a deficiency in the system or external influences. 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.

A race condition or race hazard is the behavior of an electronics, software, or other system where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events. It becomes a bug when one or more of the possible behaviors is undesirable.

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

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

The Muller C-element is a small digital block widely used in design of asynchronous circuits and systems. It has been specified formally in 1955 by David E. Muller and first used in ILLIAC II computer. In terms of the theory of lattices, the C-element is a semimodular distributive circuit, whose operation in time is described by a Hasse diagram. The C-element is closely related to the rendezvous and join elements, where an input is not allowed to change twice in succession. In some cases, when relations between delays are known, the C-element can be realized as a sum-of-product (SOP) circuit ,. Earlier techniques for implementing the C-element include Schmidt trigger, Eccles-Jordan flip-flop and last moving point flip-flop.

Notes

1. Radomir S. Stanković, Jaakko Astola (2008), Reprints from the Early Days of Information Sciences: TICSP Series On the Contributions of Akira Nakashima to Switching Theory, TICSP Series #40, Tampere International Center for Signal Processing, Tampere University of Technology
2. History of Research on Switching Theory in Japan, IEEJ Transactions on Fundamentals and Materials, Vol. 124 (2004) No. 8, pp. 720-726, Institute of Electrical Engineers of Japan
3. Radomir S. Stanković (University of Niš), Jaakko T. Astola (Tampere University of Technology), Mark G. Karpovsky (Boston University), Some Historical Remarks on Switching Theory, 2007, DOI 10.1.1.66.1248

Related Research Articles

In logic, mathematics and linguistics, And (∧) is the truth-functional operator of logical conjunction; the and of a set of operands is true if and only if all of its operands are true. The logical connective that represents this operator is typically written as or .

In electronics, a logic gate is an idealized or physical device implementing a Boolean function; that is, it performs a logical operation on one or more binary inputs and 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.

Ladder logic was originally a written method to document the design and construction of relay racks as used in manufacturing and process control. Each device in the relay rack would be represented by a symbol on the ladder diagram with connections between those devices shown. In addition, other items external to the relay rack such as pumps, heaters, and so forth would also be shown on the ladder diagram.

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

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.

In mathematics and logic, a (finitary) Boolean function is a function of the form ƒ : Bk → B, where B = {0, 1} is a Boolean domain and k is a non-negative integer called the arity of the function. In the case where k = 0, the "function" is essentially a constant element of B.

A Symbolic Analysis of Relay and Switching Circuits is the title of a master's thesis written by computer science pioneer Claude E. Shannon while attending the Massachusetts Institute of Technology (MIT) in 1937. In his thesis, Shannon, a dual degree graduate of the University of Michigan, proved that Boolean algebra could be used to simplify the arrangement of the relays that were the building blocks of the electromechanical automatic telephone exchanges of the day. Shannon went on to prove that it should also be possible to use arrangements of relays to solve Boolean algebra problems.

The history of computer science began long before our 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 Western Society, and the basis of a massive worldwide trade and culture.

Logic is the formal science of using reason and is considered a branch of both philosophy and mathematics. 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.

Relay logic is a method of implementing combinational logic in electrical control circuits by using several electrical relays wired in a particular configuration.

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.

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 1917 and electric music technologies to the 2010s.

In mathematics and mathematical logic, Boolean algebra is the branch of algebra in which the values of the variables are the truth values true and false, usually denoted 1 and 0 respectively. Instead of elementary algebra where the values of the variables are numbers, and the prime operations are addition and multiplication, the main operations of Boolean algebra are the conjunction and denoted as ∧, the disjunction or denoted as ∨, and the negation not denoted as ¬. It is thus a formalism for describing logical relations in the same way that elementary algebra describes numeric relations.

Boolean differential calculus (BDC) is a subject field of Boolean algebra discussing changes of Boolean variables and Boolean functions.

Akira Nakashima was the NEC engineer who introduced switching circuit theory in papers from 1934 to 1936, laying the foundations for digital circuit design, in digital computers and other areas of modern technology.

References

• Keister, William; Ritchie, Alistair E.; Washburn, Seth H. (1963) [1951]. The Design of Switching Circuits. The Bell Telephone Laboratories Series. Princeton, NJ: D. Van Nostrand Company.
• Caldwell, Samuel H. (1965) [1958]. Switching Circuits and Logical Design. New York: John Wiley & Sons.
• Shannon, C. E. (1938). "A Symbolic Analysis of Relay and Switching Circuits". Trans. AIEE. 57 (12): 713–723. doi:10.1109/T-AIEE.1938.5057767.

Samuel Hawks Caldwell was an American electrical engineer, known for his contributions to the early computers.

In computing, a Digital Object Identifier orDOI is a persistent identifier or handle used to uniquely identify objects, standardized by the International Organization for Standardization (ISO). An implementation of the Handle System, DOIs are in wide use mainly to identify academic, professional, and government information, such as journal articles, research reports and data sets, and official publications though they also have been used to identify other types of information resources, such as commercial videos.