Electrical Engineering

First Edition, 2007

ISBN 978 81 89940 49 2

© All rights reserved.

Published by: Global Media 1819, Bhagirath Palace, Chandni Chowk, Delhi-110 006 Email: [email protected]

Table of Contents 1. General Theories 2. Resistance, Capacitance, Inductances 3. Time Constants 4. Telecommunication 5. Electrical Engineering 6. Power Engineering 7. Photodiode 8. Photomultiplier 9. Digital Circuit 10. Boolean Algebra 11. Logic Analyzer 12. Logic Gate 13. Programmable Logic Device 14. Reconfigurable Computing 15. Analogue Electronics 16. Artificial Intelligence 17. Control System 18. Control Theory 19. Control Engineering 20. Programmable Logic Controller 21. Building Automation 22. HVAC Control System 23. Signal Processing 24. LTI System Theory 25. Fourier Transform 26. Signal (Electrical Engineering)

Notation The library uses the symbol font for some of the notation and formulae. If the symbols for the letters ‘alpha beta delta’ do not appear here [α β δ] then the symbol font needs to be installed before all notation and formulae will be displayed correctly. E G I R P

voltage source conductance current resistance power

[volts, V] [siemens, S] [amps, A] [ohms, Ω] [watts]

V X Y Z

voltage drop reactance admittance impedance

[volts, V] [ohms, Ω] [siemens, S] [ohms, Ω]

Ohm’s Law When an applied voltage E causes a current I to flow through an impedance Z, the value of the impedance Z is equal to the voltage E divided by the current I. Impedance = Voltage / Current

Z=E/I

Similarly, when a voltage E is applied across an impedance Z, the resulting current I through the impedance is equal to the voltage E divided by the impedance Z. Current = Voltage / Impedance

I=E/Z

Similarly, when a current I is passed through an impedance Z, the resulting voltage drop V across the impedance is equal to the current I multiplied by the impedance Z. Voltage = Current * Impedance

V = IZ

Alternatively, using admittance Y which is the reciprocal of impedance Z: Voltage = Current / Admittance

V=I/Y

Kirchhoff’s Laws Kirchhoff’s Current Law At any instant the sum of all the currents flowing into any circuit node is equal to the sum of all the currents flowing out of that node: ΣIin = ΣIout Similarly, at any instant the algebraic sum of all the currents at any circuit node is zero: ΣI = 0 Kirchhoff’s Voltage Law At any instant the sum of all the voltage sources in any closed circuit is equal to the sum of all the voltage drops in that circuit: ΣE = ΣIZ Similarly, at any instant the algebraic sum of all the voltages around any closed circuit is zero: ΣE - ΣIZ = 0

Thévenin’s Theorem Any linear voltage network which may be viewed from two terminals can be replaced by a voltage-source equivalent circuit comprising a single voltage source E and a single series impedance Z. The voltage E is the open-circuit voltage between the two terminals and the impedance Z is the impedance of the network viewed from the terminals with all voltage sources replaced by their internal impedances.

Norton’s Theorem Any linear current network which may be viewed from two terminals can be replaced by a current-source equivalent circuit comprising a single current source I and a single shunt admittance Y. The current I is the short-circuit current between the two terminals and the admittance Y is the admittance of the network viewed from the terminals with all current sources replaced by their internal admittances.

Thévenin and Norton Equivalence The open circuit, short circuit and load conditions of the Thévenin model are: Voc = E Isc = E / Z Vload = E - IloadZ Iload = E / (Z + Zload) The open circuit, short circuit and load conditions of the Norton model are: Voc = I / Y Isc = I Vload = I / (Y + Yload) Iload = I - VloadY

Thévenin model from Norton model Voltage = Current / Admittance Impedance = 1 / Admittance

E=I/Y Z = Y -1

Norton model from Thévenin model Current = Voltage / Impedance Admittance = 1 / Impedance

I=E/Z Y = Z -1

When performing network reduction for a Thévenin or Norton model, note that: - nodes with zero voltage difference may be short-circuited with no effect on the network current distribution, - branches carrying zero current may be open-circuited with no effect on the network voltage distribution.

Superposition Theorem In a linear network with multiple voltage sources, the current in any branch is the sum of the currents which would flow in that branch due to each voltage source acting alone with all other voltage sources replaced by their internal impedances.

Reciprocity Theorem If a voltage source E acting in one branch of a network causes a current I to flow in another branch of the network, then the same voltage source E acting in the second branch would cause an identical current I to flow in the first branch.

Compensation Theorem If the impedance Z of a branch in a network in which a current I flows is changed by a finite amount δZ, then the change in the currents in all other branches of the network may be calculated by inserting a voltage source of -IδZ into that branch with all other voltage sources replaced by their internal impedances.

Millman’s Theorem (Parallel Generator Theorem) If any number of admittances Y1, Y2, Y3, ... meet at a common point P, and the voltages from another point N to the free ends of these admittances are E1, E2, E3, ... then the voltage between points P and N is: VPN = (E1Y1 + E2Y2 + E3Y3 + ...) / (Y1 + Y2 + Y3 + ...) VPN = ΣEY / ΣY The short-circuit currents available between points P and N due to each of the voltages E1, E2, E3, ... acting through the respective admitances Y1, Y2, Y3, ... are E1Y1, E2Y2, E3Y3, ... so the voltage between points P and N may be expressed as: VPN = ΣIsc / ΣY

Joule’s Law When a current I is passed through a resistance R, the resulting power P dissipated in the resistance is equal to the square of the current I multiplied by the resistance R: P = I2 R By substitution using Ohm’s Law for the corresponding voltage drop V (= IR) across the resistance: P = V2 / R = VI = I2R

Maximum Power Transfer Theorem When the impedance of a load connected to a power source is varied from open-circuit to short-circuit, the power absorbed by the load has a maximum value at a load impedance which is dependent on the impedance of the power source. Note that power is zero for an open-circuit (zero current) and for a short-circuit (zero voltage). Voltage Source When a load resistance RT is connected to a voltage source ES with series resistance RS, maximum power transfer to the load occurs when RT is equal to RS. Under maximum power transfer conditions, the load resistance RT, load voltage VT, load current IT and load power PT are: RT = RS VT = ES / 2 IT = VT / RT = ES / 2RS PT = VT2 / RT = ES2 / 4RS Current Source When a load conductance GT is connected to a current source IS with shunt conductance GS, maximum power transfer to the load occurs when GT is equal to GS. Under maximum power transfer conditions, the load conductance GT, load current IT, load voltage VT and load power PT are: GT = GS IT = IS / 2 VT = IT / GT = IS / 2GS PT = IT2 / GT = IS2 / 4GS Complex Impedances When a load impedance ZT (comprising variable resistance RT and variable reactance XT) is connected to an alternating voltage source ES with series impedance ZS (comprising resistance RS and reactance XS), maximum power transfer to the load occurs when ZT is equal to ZS* (the complex conjugate of ZS) such that RT and RS are equal and XT and XS are equal in magnitude but of opposite sign (one inductive and the other capacitive). When a load impedance ZT (comprising variable resistance RT and constant reactance XT) is connected to an alternating voltage source ES with series impedance ZS (comprising resistance RS and reactance XS), maximum power transfer to the load occurs when RT is equal to the magnitude of the impedance comprising ZS in series with XT: RT = |ZS + XT| = (RS2 + (XS + XT)2)½ Note that if XT is zero, maximum power transfer occurs when RT is equal to the magnitude of ZS: RT = |ZS| = (RS2 + XS2)½ When a load impedance ZT with variable magnitude and constant phase angle (constant power factor) is connected to an alternating voltage source ES with series impedance ZS, maximum power transfer to the load occurs when the magnitude of ZT is equal to the

magnitude of ZS: (RT2 + XT2)½ = |ZT| = |ZS| = (RS2 + XS2)½

Kennelly’s Star-Delta Transformation A star network of three impedances ZAN, ZBN and ZCN connected together at common node N can be transformed into a delta network of three impedances ZAB, ZBC and ZCA by the following equations: ZAB = ZAN + ZBN + (ZANZBN / ZCN) = (ZANZBN + ZBNZCN + ZCNZAN) / ZCN ZBC = ZBN + ZCN + (ZBNZCN / ZAN) = (ZANZBN + ZBNZCN + ZCNZAN) / ZAN ZCA = ZCN + ZAN + (ZCNZAN / ZBN) = (ZANZBN + ZBNZCN + ZCNZAN) / ZBN Similarly, using admittances: YAB = YANYBN / (YAN + YBN + YCN) YBC = YBNYCN / (YAN + YBN + YCN) YCA = YCNYAN / (YAN + YBN + YCN) In general terms: Zdelta = (sum of Zstar pair products) / (opposite Zstar) Ydelta = (adjacent Ystar pair product) / (sum of Ystar)

Kennelly’s Delta-Star Transformation A delta network of three impedances ZAB, ZBC and ZCA can be transformed into a star network of three impedances ZAN, ZBN and ZCN connected together at common node N by the following equations: ZAN = ZCAZAB / (ZAB + ZBC + ZCA) ZBN = ZABZBC / (ZAB + ZBC + ZCA) ZCN = ZBCZCA / (ZAB + ZBC + ZCA) Similarly, using admittances: YAN = YCA + YAB + (YCAYAB / YBC) = (YABYBC + YBCYCA + YCAYAB) / YBC YBN = YAB + YBC + (YABYBC / YCA) = (YABYBC + YBCYCA + YCAYAB) / YCA YCN = YBC + YCA + (YBCYCA / YAB) = (YABYBC + YBCYCA + YCAYAB) / YAB In general terms: Zstar = (adjacent Zdelta pair product) / (sum of Zdelta) Ystar = (sum of Ydelta pair products) / (opposite Ydelta) Electrical Circuit Formulae

Notation The library uses the symbol font for some of the notation and formulae. If the symbols for the letters ‘alpha beta delta’ do not appear here [α β δ] then the symbol font needs to be installed before all notation and formulae will be displayed correctly. C E

capacitance voltage source

[farads, F] [volts, V]

Q q

charge instantaneous Q

[coulombs, C] [coulombs, C]

e G I i k L M N P

instantaneous E conductance current instantaneous I coefficient inductance mutual inductance number of turns power

[volts, V] [siemens, S] [amps, A] [amps, A] [number] [henrys, H] [henrys, H] [number] [watts, W]

R T t V v W Φ Ψ ψ

resistance time constant instantaneous time voltage drop instantaneous V energy magnetic flux magnetic linkage instantaneous Ψ

[ohms, Ω] [seconds, s] [seconds, s] [volts, V] [volts, V] [joules, J] [webers, Wb] [webers, Wb] [webers, Wb]

Resistance The resistance R of a circuit is equal to the applied direct voltage E divided by the resulting steady current I: R=E/I

Resistances in Series When resistances R1, R2, R3, ... are connected in series, the total resistance RS is: RS = R1 + R2 + R3 + ...

Voltage Division by Series Resistances When a total voltage ES is applied across series connected resistances R1 and R2, the current IS which flows through the series circuit is: IS = ES / RS = ES / (R1 + R2) The voltages V1 and V2 which appear across the respective resistances R1 and R2 are: V1 = ISR1 = ESR1 / RS = ESR1 / (R1 + R2) V2 = ISR2 = ESR2 / RS = ESR2 / (R1 + R2) In general terms, for resistances R1, R2, R3, ... connected in series: IS = ES / RS = ES / (R1 + R2 + R3 + ...) Vn = ISRn = ESRn / RS = ESRn / (R1 + R2 + R3 + ...) Note that the highest voltage drop appears across the highest resistance.

Resistances in Parallel When resistances R1, R2, R3, ... are connected in parallel, the total resistance RP is: 1 / RP = 1 / R1 + 1 / R2 + 1 / R3 + ... Alternatively, when conductances G1, G2, G3, ... are connected in parallel, the total conductance GP is: GP = G1 + G2 + G3 + ... where Gn = 1 / Rn For two resistances R1 and R2 connected in parallel, the total resistance RP is: RP = R1R2 / (R1 + R2) RP = product / sum The resistance R2 to be connected in parallel with resistance R1 to give a total resistance RP is: R2 = R1RP / (R1 - RP) R2 = product / difference

Current Division by Parallel Resistances When a total current IP is passed through parallel connected resistances R1 and R2, the voltage VP which appears across the parallel circuit is: VP = IPRP = IPR1R2 / (R1 + R2) The currents I1 and I2 which pass through the respective resistances R1 and R2 are: I1 = VP / R1 = IPRP / R1 = IPR2 / (R1 + R2) I2 = VP / R2 = IPRP / R2 = IPR1 / (R1 + R2) In general terms, for resistances R1, R2, R3, ... (with conductances G1, G2, G3, ...) connected in parallel: VP = IPRP = IP / GP = IP / (G1 + G2 + G3 + ...) In = VP / Rn = VPGn = IPGn / GP = IPGn / (G1 + G2 + G3 + ...) where Gn = 1 / Rn Note that the highest current passes through the highest conductance (with the lowest resistance).

Capacitance When a voltage is applied to a circuit containing capacitance, current flows to accumulate charge in the capacitance: Q = ∫idt = CV Alternatively, by differentiation with respect to time: dq/dt = i = C dv/dt Note that the rate of change of voltage has a polarity which opposes the flow of current. The capacitance C of a circuit is equal to the charge divided by the voltage: C = Q / V = ∫idt / V Alternatively, the capacitance C of a circuit is equal to the charging current divided by the rate of change of voltage: C = i / dv/dt = dq/dt / dv/dt = dq/dv

Capacitances in Series When capacitances C1, C2, C3, ... are connected in series, the total capacitance CS is: 1 / CS = 1 / C1 + 1 / C2 + 1 / C3 + ... For two capacitances C1 and C2 connected in series, the total capacitance CS is: CS = C1C2 / (C1 + C2) CS = product / sum

Voltage Division by Series Capacitances When a total voltage ES is applied to series connected capacitances C1 and C2, the charge QS which accumulates in the series circuit is: QS = ∫iSdt = ESCS = ESC1C2 / (C1 + C2) The voltages V1 and V2 which appear across the respective capacitances C1 and C2 are: V1 = ∫iSdt / C1 = ESCS / C1 = ESC2 / (C1 + C2) V2 = ∫iSdt / C2 = ESCS / C2 = ESC1 / (C1 + C2) In general terms, for capacitances C1, C2, C3, ... connected in series: QS = ∫iSdt = ESCS = ES / (1 / CS) = ES / (1 / C1 + 1 / C2 + 1 / C3 + ...) Vn = ∫iSdt / Cn = ESCS / Cn = ES / Cn(1 / CS) = ES / Cn(1 / C1 + 1 / C2 + 1 / C3 + ...) Note that the highest voltage appears across the lowest capacitance.

Capacitances in Parallel When capacitances C1, C2, C3, ... are connected in parallel, the total capacitance CP is: CP = C1 + C2 + C3 + ...

Charge Division by Parallel Capacitances When a voltage EP is applied to parallel connected capacitances C1 and C2, the charge QP which accumulates in the parallel circuit is: QP = ∫iPdt = EPCP = EP(C1 + C2) The charges Q1 and Q2 which accumulate in the respective capacitances C1 and C2 are: Q1 = ∫i1dt = EPC1 = QPC1 / CP = QPC1 / (C1 + C2) Q2 = ∫i2dt = EPC2 = QPC2 / CP = QPC2 / (C1 + C2) In general terms, for capacitances C1, C2, C3, ... connected in parallel: QP = ∫iPdt = EPCP = EP(C1 + C2 + C3 + ...) Qn = ∫indt = EPCn = QPCn / CP = QPCn / (C1 + C2 + C3 + ...) Note that the highest charge accumulates in the highest capacitance.

Inductance When the current changes in a circuit containing inductance, the magnetic linkage changes and induces a voltage in the inductance: dψ/dt = e = L di/dt Note that the induced voltage has a polarity which opposes the rate of change of current.

Alternatively, by integration with respect to time: Ψ = ∫edt = LI The inductance L of a circuit is equal to the induced voltage divided by the rate of change of current: L = e / di/dt = dψ/dt / di/dt = dψ/di Alternatively, the inductance L of a circuit is equal to the magnetic linkage divided by the current: L=Ψ/I Note that the magnetic linkage Ψ is equal to the product of the number of turns N and the magnetic flux Φ: Ψ = NΦ = LI

Mutual Inductance The mutual inductance M of two coupled inductances L1 and L2 is equal to the mutually induced voltage in one inductance divided by the rate of change of current in the other inductance: M = E2m / (di1/dt) M = E1m / (di2/dt) If the self induced voltages of the inductances L1 and L2 are respectively E1s and E2s for the same rates of change of the current that produced the mutually induced voltages E1m and E2m, then: M = (E2m / E1s)L1 M = (E1m / E2s)L2 Combining these two equations: M = (E1mE2m / E1sE2s)½ (L1L2)½ = kM(L1L2)½ where kM is the mutual coupling coefficient of the two inductances L1 and L2. If the coupling between the two inductances L1 and L2 is perfect, then the mutual inductance M is: M = (L1L2)½

Inductances in Series When uncoupled inductances L1, L2, L3, ... are connected in series, the total inductance LS is: LS = L1 + L2 + L3 + ... When two coupled inductances L1 and L2 with mutual inductance M are connected in series, the total inductance LS is: LS = L1 + L2 ± 2M The plus or minus sign indicates that the coupling is either additive or subtractive, depending on the connection polarity.

Inductances in Parallel When uncoupled inductances L1, L2, L3, ... are connected in parallel, the total inductance LP is: 1 / LP = 1 / L1 + 1 / L2 + 1 / L3 + ...

Time Constants Capacitance and resistance The time constant of a capacitance C and a resistance R is equal to CR, and represents the time to change the voltage on the capacitance from zero to E at a constant charging current E / R (which produces a rate of change of voltage E / CR across the capacitance). Similarly, the time constant CR represents the time to change the charge on the capacitance from zero to CE at a constant charging current E / R (which produces a rate of change of voltage E / CR across the capacitance). If a voltage E is applied to a series circuit comprising a discharged capacitance C and a resistance R, then after time t the current i, the voltage vR across the resistance, the voltage vC across the capacitance and the charge qC on the capacitance are: i = (E / R)e - t / CR vR = iR = Ee - t / CR vC = E - vR = E(1 - e - t / CR) qC = CvC = CE(1 - e - t / CR) If a capacitance C charged to voltage V is discharged through a resistance R, then after time t the current i, the voltage vR across the resistance, the voltage vC across the capacitance and the charge qC on the capacitance are: i = (V / R)e - t / CR vR = iR = Ve - t / CR vC = vR = Ve - t / CR qC = CvC = CVe - t / CR Inductance and resistance The time constant of an inductance L and a resistance R is equal to L / R, and represents the time to change the current in the inductance from zero to E / R at a constant rate of change of current E / L (which produces an induced voltage E across the inductance). If a voltage E is applied to a series circuit comprising an inductance L and a resistance R, then after time t the current i, the voltage vR across the resistance, the voltage vL across the inductance and the magnetic linkage ψL in the inductance are: i = (E / R)(1 - e - tR / L) vR = iR = E(1 - e - tR / L) vL = E - vR = Ee - tR / L ψL = Li = (LE / R)(1 - e - tR / L) If an inductance L carrying a current I is discharged through a resistance R, then after time t the current i, the voltage vR across the resistance, the voltage vL across the inductance and the magnetic linkage ψL in the inductance are: i = Ie - tR / L vR = iR = IRe - tR / L vL = vR = IRe - tR / L ψL = Li = LIe - tR / L Rise Time and Fall Time The rise time (or fall time) of a change is defined as the transition time between the 10%

and 90% levels of the total change, so for an exponential rise (or fall) of time constant T, the rise time (or fall time) t10-90 is: t10-90 = (ln0.9 - ln0.1)T ≈ 2.2T The half time of a change is defined as the transition time between the initial and 50% levels of the total change, so for an exponential change of time constant T, the half time t50 is : t50 = (ln1.0 - ln0.5)T ≈ 0.69T Note that for an exponential change of time constant T: - over time interval T, a rise changes by a factor 1 - e -1 (≈ 0.63) of the remaining change, - over time interval T, a fall changes by a factor e -1 (≈ 0.37) of the remaining change, - after time interval 3T, less than 5% of the total change remains, - after time interval 5T, less than 1% of the total change remains.

Telecommunication

Copy of the original phone of Graham Bell at the Musée des Arts et Métiers in Paris Telecommunication is the transmission of signals over a distance for the purpose of communication. In modern times, this process almost always involves the sending of electromagnetic waves by electronic transmitters but in earlier years it may have involved the use of smoke signals, drums or semaphore. Today, telecommunication is widespread and devices that assist the process such as the television, radio and telephone are common in many parts of the world. There is also a vast array of networks that connect these devices, including computer networks, public telephone networks, radio networks and television networks. Computer communication across the Internet, such as e-mail and instant messaging, is just one of many examples of telecommunication. Telecommunication systems are generally designed by telecommunication engineers. Major contributors to the field of telecommunications include Alexander Bell who invented the telephone (as we know it), John Logie Baird who invented the mechanical television and Guglielmo Marconi who first demonstrated transatlantic radio communication. In recent times, optical fibre has radically improved the bandwidth available for intercontential communication helping to facilitate a faster and richer Internet experience and digital television has eliminated effects such as snowy pictures and ghosting. Telecommunication remains an important part of the world economy and the telecommunication industry’s revenue has been placed at just under 3% of the gross world product.

Key concepts The basic elements of a telecommunication system are: • • •

a transmitter that takes information and converts it to a signal for transmission a transmission medium over which the signal is transmitted a receiver that receives and converts the signal back into usable information

For example, consider a radio broadcast. In this case the broadcast tower is the transmitter, the radio is the receiver and the transmission medium is free space. Often

telecommunication systems are two-way and devices act as both a transmitter and receiver or transceiver. For example, a mobile phone is a transceiver. Telecommunication over a phone line is called point-to-point communication because it is between one transmitter and one receiver, telecommunication through radio broadcasts is called broadcast communication because it is between one powerful transmitter and numerous receivers. Signals can either be analogue or digital. In an analogue signal, the signal is varied continuously with respect to the information. In a digital signal, the information is encoded as a set of discrete values (e.g. 1’s and 0’s). A collection of transmitters, receivers or transceivers that communicate with each other is known as a network. Digital networks may consist of one or more routers that route data to the correct user. An analogue network may consist of one or more switches that establish a connection between two or more users. For both types of network, a repeater may be necessary to amplify or recreate the signal when it is being transmitted over long distances. This is to combat attenuation that can render the signal indistinguishable from noise. A channel is a division in a transmission medium so that it can be used to send multiple independent streams of data. For example, a radio station may broadcast at 96 MHz while another radio station may broadcast at 94.5 MHz. In this case the medium has been divided by frequency and each channel received a separate frequency to broadcast on. Alternatively one could allocate each channel a recurring segment of time over which to broadcast. The shaping of a signal to convey information is known as modulation. Modulation is a key concept in telecommunications and is frequently used to impose the information of one signal on another. Modulation is used to represent a digital message as an analogue waveform. This is known as keying and several keying techniques exist — these include phase-shift keying, amplitude-shift keying and minimum-shift keying. Bluetooth, for example, uses phase-shift keying for exchanges between devices (see note). However, more relevant to earlier discussion, modulation is also used to boost the frequency of analogue signals. This is because a raw signal is often not suitable for transmission over long distances of free space due to its low frequencies. Hence its information must be superimposed on a higher frequency signal (known as a carrier wave) before transmission. There are several different modulation schemes available to achieve this — some of the most basic being amplitude modulation and frequency modulation. An example of this process is a DJ’s voice being superimposed on a 96 MHz carrier wave using frequency modulation (the voice would then be received on a radio as the channel “96 FM”).

Society and telecommunication Telecommunication is an important part of many modern societies. In 2006, estimates place the telecommunication industry’s revenue at $1.2 trillion or just under 3% of the gross world product.Good telecommunication infrastructure is widely acknowledged as important for economic success in the modern world both on a micro and macroeconomic scale.And, for this reason, there is increasing worry about the digital divide.

This stems from the fact that access to telecommunication systems is not equally shared amongst the world’s population. A 2003 survey by the International Telecommunication Union (ITU) revealed that roughly one-third of countries have less than 1 mobile subscription for every 20 people and one-third of countries have less than 1 fixed line subscription for every 20 people. In terms of Internet access, roughly half of countries have less than 1 in 20 people with Internet access. From this information as well as educational data the ITU was able to compile a Digital Access Index that measures the overall ability of citizens to access and use information and communication technologies. Using this measure, countries such as Sweden, Denmark and Iceland receive the highest ranking while African countries such as Niger, Burkina Faso and Mali receive the lowest.Further discussion of the social impact of telecommunication is often considered part of communication theory.

History

A replica of one of Chappe’s semaphore towers.

Early telecommunications Early forms of telecommunication include smoke signals and drums. Drums were used by natives in Africa, New Guinea and South America whereas smoke signals were used

by natives in North America and China. Contrary to what one might think, these systems were often used to do more than merely announce the presence of a camp. In 1792, a French engineer, Claude Chappe built the first fixed visual telegraphy (or semaphore) system between Lille and Paris. However semaphore as a communication system suffered from the need for skilled operators and expensive towers often at intervals of only ten to thirty kilometres (six to nineteen miles). As a result, the last commercial line was abandoned in 1880.

Telegraph and telephone The first commercial electrical telegraph was constructed by Sir Charles Wheatstone and Sir William Fothergill Cooke and opened on 9 April 1839. Both Wheatstone and Cooke viewed their device as “an improvement to the [existing] electromagnetic telegraph” not as a new device. On the other side of the Atlantic Ocean, Samuel Morse independently developed a version of the electrical telegraph that he unsuccessfully demonstrated on 2 September 1837. Soon after he was joined by Alfred Vail who developed the register — a telegraph terminal that integrated a logging device for recording messages to paper tape. This was demonstrated successfully on 6 January 1838. The first transatlantic telegraph cable was successfully completed on 27 July 1866, allowing transatlantic telecommunication for the first time. The conventional telephone was invented by Alexander Bell in 1876. Although in 1849 Antonio Meucci invented a device that allowed the electrical transmission of voice over a line. Meucci’s device depended upon the electrophonic effect and was of little practical value because it required users to place the receiver in their mouth to “hear” what was being said. The first commercial telephone services were set-up in 1878 and 1879 on both sides of the Atlantic in the cities of New Haven and London.

Radio and television In 1832, James Lindsay gave a classroom demonstration of wireless telegraphy to his students. By 1854 he was able to demonstrate a transmission across the Firth of Tay from Dundee to Woodhaven, a distance of two miles, using water as the transmission medium. In December 1901, Guglielmo Marconi established wireless communication between Britain and the United States earning him the Nobel Prize in physics in 1909 (which he shared with Karl Braun).

On March 25, 1925, John Logie Baird was able to demonstrate the transmission of moving pictures at the London department store Selfridges. Baird’s device relied upon

the Nipkow disk and thus became known as the mechanical television. It formed the basis of experimental broadcasts done by the British Broadcasting Corporation beginning September 30, 1929. However for most of the twentieth century televisions depended upon the cathode ray tube invented by Karl Braun. The first version of such a television to show promise was produced by Philo Farnsworth and demonstrated to his family on September 7, 1927.

Computer networks and the Internet On September 11, 1940 George Stibitz was able to transmit problems using teletype to his Complex Number Calculator in New York and receive the computed results back at Dartmouth College in New Hampshire. This configuration of a centralized computer or mainframe with remote dumb terminals remained popular throughout the 1950s. However it was not until the 1960s that researchers started to investigate packet switching — a technology that would allow chunks of data to be sent to different computers without first passing through a centralized mainframe. A four-node network emerged on December 5, 1969; this network would become ARPANET, which by 1981 would consist of 213 nodes.

ARPANET’s development centred around the Request for Comment process and on April 7, 1969, RFC 1 was published. This process is important because ARPANET would eventually merge with other networks to form the Internet and many of the protocols the Internet relies upon today were specified through this process. In September 1981, RFC 791 introduced the Internet Protocol v4 (IPv4) and RFC 793 introduced the Transmission Control Protocol (TCP) — thus creating the TCP/IP protocol that much of the Internet relies upon today. However not all important developments were made through the Request for Comment process. Two popular link protocols for local area networks (LANs) also appeared in the 1970s. A patent for the Token Ring protocol was filed by Olof Soderblom on October 29, 1974. And a paper on the Ethernet protocol was published by Robert Metcalfe and David Boggs in the July 1976 issue of Communications of the ACM. These protocols are discussed in more detail in the next section.

Modern operation Telephone

Optic fibres are revolutionizing long-distance communication In a conventional telephone system, the caller is connected to the person they want to talk to by the switches at various exchanges. The switches form an electrical connection between the two users and the setting of these switches is determined electronically when the caller dials the number based upon either pulses or tones made by the caller’s telephone. Once the connection is made, the caller’s voice is transformed to an electrical signal using a small microphone in the telephone’s receiver. This electrical signal is then sent through various switches in the network to the user at the other end where it transformed back into sound waves by a speaker for that person to hear. This person also has a separate electrical connection between him and the caller which allows him to talk back.[28] Today, the fixed-line telephone systems in most residential homes are analogue — that is the speaker’s voice directly determines the amplitude of the signal’s voltage. However although short-distance calls may be handled from end-to-end as analogue signals, increasingly telephone service providers are transparently converting signals to digital before converting them back to analogue for reception.

Mobile phones have had a dramatic impact on telephone service providers. Mobile phone subscriptions now outnumber fixed line subscriptions in many markets. Sales of mobile phones in 2005 totalled 816.6 million with that figure being almost equally shared amongst the markets of Asia/Pacific (204 m), Western Europe (164 m), CEMEA (Central Europe, the Middle East and Africa) (153.5 m), North America (148 m) and Latin America (102 m). In terms of new subscriptions over the five years from 1999, Africa has outpaced other markets with 58.2% growth compared to the next largest market, Asia, which boasted 34.3% growth.[30] Increasingly these phones are being serviced by digital systems such as GSM or W-CDMA with many markets choosing to depreciate analogue

systems such as AMPS.[31] By digital it is meant the handsets themselves transmit digital not analogue signals. However there have been equally drastic changes in telephone communication behind the scenes. Starting with the operation of TAT-8 in 1988, the 1990s saw the widespread adoption of systems based upon optic fibres. The benefit of communicating with optic fibres is that they offer a drastic increase in data capacity. TAT-8 itself was able to carry 10 times as many telephone calls as the last copper cable laid at that time and today’s optic fibre cables are able to carry 25 times as many telephone calls as TAT-8.[32] This drastic increase in data capacity is due to several factors. First, optic fibres are physically much smaller than competing technologies. Second, they do not suffer from crosstalk which means several hundred of them can be easily bundled together in a single cable.[33] Lastly, improvements in multiplexing have lead to an exponential growth in the data capacity of a single fibre. This is due to technologies such as dense wavelength-division multiplexing, which at its most basic level is building multiple channels based upon frequency division as discussed in the Key concepts section.[34] However despite the advances of technologies such as dense wavelength-division multiplexing, technologies based around building multiple channels based upon time division such as synchronous optical networking and synchronous digital hierarchy remain dominant.[35] Assisting communication across these networks is a protocol known as Asynchronous Transfer Mode (ATM). As a technology, ATM arose in the 1980s and was envisioned to be part of the Broadband Integrated Services Digital Network. The network ultimately failed but the technology gave birth to the ATM Forum which in 1992 published its first standard.[36] Today, despite competitors such as Multiprotocol Label Switching, ATM remains the protocol of choice for most major long-distance optical networks. The importance of the ATM protocol was chiefly in its notion of establishing pathways for data through the network and associating a traffic contract with these pathways. The traffic contract was essentially an agreement between the client and the network about how the network was to handle the data, if the network could not meet the conditions of the traffic contract it would not accept the connection. This was important because telephone calls could negotiate a contract so as to guarantee themselves a constant bit rate, something that was essential to ensure a call could take place without the caller’s voice being delayed in parts or cut-off completely.[37]

Radio and television

Digital television standards and their adoption worldwide.

The broadcast media industry is at a critical turning point in its development, with many countries starting to move from analogue to digital broadcasts. The chief advantage of digital broadcasts is that they prevent a number of complaints with traditional analogue broadcasts. For television, this includes the elimination of problems such as snowy pictures, ghosting and other distortion. These occur because of the nature of analogue transmission, which means that perturbations due to noise will be evident in the final output. Digital transmission overcomes this problem because digital signals are reduced to binary data upon reception and hence small perturbations do not affect the final output. In a simplified example, if a binary message 1011 was transmitted with signal amplitudes [1.0 0.0 1.0 1.0] and received with signal amplitudes [0.9 0.2 1.1 0.9] it would still decode to the binary message 1011 — a perfect reproduction of what was sent. From this example, a problem with digital transmissions can also be seen in that if the noise is great enough it can significantly alter the decoded message. Using forward error correction a receiver can correct a handful of bit errors in the resulting message but too much noise will lead to incomprehensible output and hence a breakdown of the transmission.[38]

In digital television broadcasting, there are three competing standards that are likely to be adopted worldwide. These are the ATSC, DVB and ISDB standards and the adoption of these standards thus far is presented in the captioned map. All three standards use MPEG2 for video compression. ATSC uses Dolby Digital AC-3 for audio compression, ISDB uses Advanced Audio Coding (MPEG-2 Part 7) and DVB has no standard for audio compression but typically uses MPEG-1 Part 3 Layer 2.[39][40] The choice of modulation also varies between the schemes. Both DVB and ISDB use orthogonal frequency-division multiplexing (OFDM) for terrestrial broadcasts (as opposed to satellite or cable broadcasts) where as ATSC uses vestigial sideband modulation (VSB). OFDM should offer better resistance to multipath interference and the Doppler effect (which would impact reception using moving receivers).[41] However controversial tests conducted by the United States’ National Association of Broadcasters have shown that there is little difference between the two for stationary receivers.[42] In digital audio broadcasting, standards are much more unified with practically all countries (including Canada) choosing to adopt the Digital Audio Broadcasting standard (also known as the Eureka 147 standard). The exception being the United States which has chosen to adopt HD Radio. HD Radio, unlike Eureka 147, is based upon a transmission method known as in-band on-channel transmission — this allows digital information to “piggyback” on normal AM or FM analogue transmissions. Hence avoiding the bandwidth allocation issues of Eureka 147 and therefore being strongly advocated National Association of Broadcasters who felt there was a lack of new

spectrum to allocate for the Eureka 147 standard.[43] In the United States the Federal Communications Commission has chosen to leave licensing of the standard in the hands of a commercial corporation called iBiquity.[44] An open in-band on-channel standard exists in the form of Digital Radio Mondiale (DRM) however adoption of this standard is mostly limited to a handful of shortwave broadcasts. Despite the different names all standards rely upon OFDM for modulation. In terms of audio compression, DRM typically uses Advanced Audio Coding (MPEG-4 Part 3), DAB like DVB can use a variety of codecs but typically uses MPEG-1 Part 3 Layer 2 and HD Radio uses HighDefinition Coding. However, despite the pending switch to digital, analogue receivers still remain widespread. Analogue television is still transmitted in practically all countries. The United States had hoped to end analogue broadcasts by December 31, 2006 however this was recently pushed back to February 17, 2009.[45] For analogue, there are three standards in use (see a map on adoption here). These are known as PAL, NTSC and SECAM. The basics of PAL and NTSC are very similar; a quadrature amplitude modulated subcarrier carrying the chrominance information is added to the luminance video signal to form a composite video baseband signal (CVBS). On the other hand, the SECAM system uses a frequency modulation scheme on its colour subcarrier. The PAL system differs from NTSC in that the phase of the video signal’s colour components is reversed with each line helping to correct phase errors in the transmission. For analogue radio, the switch to digital is made more difficult by the fact that analogue receivers cost a fraction of the cost of digital receivers. For example while you can get a good analogue receiver for under $20 USD[46] a digital receiver will set you back at least $75 USD.[47] The choice of modulation for analogue radio is typically between amplitude modulation (AM) or frequency modulation (FM). To achieve stereo playback, an amplitude modulated subcarrier is used for stereo FM and quadrature amplitude modulation is used for stereo AM or C-QUAM (see each of the linked articles for more details).

The Internet

The OSI reference model Today an estimated 15.7% of the world population has access to the Internet with the highest concentration in North America (68.6%), Oceania/Australia (52.6%) and Europe (36.1%).[48] In terms of broadband access, countries such as Iceland (26.7%), South Korea (25.4%) and the Netherlands (25.3%) lead the world.[49]

The nature of computer network communication lends itself to a layered approach where individual protocols in the protocol stack run largely independently of other protocols. This allows lower-level protocols to be customized for the network situation while not changing the way higher-level protocols operate. A practical example of why this important is because it allows an Internet browser to run the same code regardless of whether the computer it is running on is connected to the Internet through an Ethernet or Wi-Fi connection. Protocols are often talked about in terms of their place in the OSI reference model — a model that emerged in 1983 as the first step in a doomed attempt to build a universally adopted networking protocol suite.[50] The model itself is outlined in the picture to the right. It is important to note that the Internet’s protocol suite, like many modern protocol suites, does not rigidly follow this model but can still be talked about in the context of this model. For the Internet, the physical medium and data link protocol can vary several times as packets travel between client nodes. Though it is likely that the majority of the distance travelled will be using the Asynchronous Transfer Mode (ATM) data link protocol across optical fibre this is in no way guaranteed. A connection may also encounter data link protocols such as Ethernet, Wi-Fi and the Point-to-Point Protocol (PPP) and physical media such as twisted-pair cables and free space. At the network layer things become standardized with the Internet Protocol (IP) being adopted for logical addressing. For the world wide web, these “IP addresses” are derived from the human readable form (e.g. 72.14.207.99 ) using the Domain Name System. At the moment the most widely used version of the Internet Protocol is version four but a move to version six is imminent. The main advantage of the new version is that it supports 3.40 × 1038 addresses compared to 4.29 × 109 addresses. The new version also adds support for enhanced security through IPSec as well as support for QoS identifiers.[51] At the transport layer most communication adopts either the Transmission Control Protocol (TCP) or the User Datagram Protocol (UDP). With TCP, packets are retransmitted if they are lost and placed in order before they are presented to higher layers (this ordering also allows duplicate packets to be eliminated). With UDP, packets are not ordered or retransmitted if lost. Both TCP and UDP packets carry port numbers with them to specify what application or process the packet should be handed to on the client’s computer.[52] Because certain application-level protocols use certain ports, network administrators can restrict Internet access by blocking or throttling traffic destined for a particular port.

Above the transport layer there are certain protocols that loosely fit in the session and presentation layers and are sometimes adopted, most notably the Secure Sockets Layer (SSL) and Transport Layer Security (TLS) protocols. These protocols ensure that the data transferred between two parties remains completely confidential and one or the other is in use when a padlock appears at the bottom of your web browser. Security is generally based upon the principle that eavesdroppers cannot factorize very large numbers that are the composite of two primes without knowing one of the primes. Another protocol that loosely fits in the session and presentation layers is the Real-time Transport Protocol (RTP) most notably used to stream QuickTime.[53] Finally at the application layer are many of the protocols Internet users would be familiar with such as HTTP (web browsing), POP3 (e-mail), FTP (file transfer) and IRC (Internet chat) but also less common protocols such as BitTorrent (file sharing) and ICQ (instant messaging).

sLocal area networks

A local area network. Despite the growth of the Internet, the characteristics of local area networks (computer networks that run over at most a few kilometres) remain distinct. In the mid-1980s, several protocol suites emerged to fill the gap between the data link and applications layer of the OSI reference model. These were Appletalk, IPX and NetBIOS with the dominant protocol suite during the early 90s being IPX due to its popularity with MS-DOS users. TCP/IP existed at this point but was typically only used by large government and research facilities.[54] However as the Internet grew in popularity and a larger percentage of local area network traffic became Internet-related, LANs gradually moved towards TCP/IP and today networks mostly dedicated to TCP/IP traffic are common. The move to TCP/IP was helped by technologies such as DHCP introduced in RFC 2131 that allowed TCP/IP clients to discover their own network address — a functionality that came standard with the AppleTalk/IPX/NetBIOS protocol suites. However it is at the data link layer that modern local area networks diverge from the Internet. Where as Asynchronous Transfer Mode (ATM) or Multiprotocol Label Switching (MPLS) are typical data link protocols for larger networks, Ethernet and

Token Ring are typical data link protocols for local area networks. The latter LAN protocols differ from the former protocols in that they are simpler (e.g. they omit features such as Quality of Service guarantees) and offer collision prevention. Both of these differences allow for more economic set-ups. For example, omitting Quality of Service guarantees simplifies routers and the guarantees are not really necessary for local area networks because they tend not to carry real time communication (such as voice communication). Including collision prevention allows multiple clients (as opposed to just two) to share the same cable again reducing costs. Though both Ethernet and Token Ring have different frame formats, it is in terms of collision prevention that the two present the greatest difference. With Token Ring a token circulates the network and clients only transmit when they have the token. The token must be managed to ensure it is not lost or duplicated. With Ethernet any client can transmit if it thinks the medium is idle, but clients listen for collisions and if one is detected suspend communication for a random amount of time.[55] Despite Token Ring’s modest popularity in the 80’s and 90’s, with the advent of the twenty-first century, the majority of local area networks have now settled on Ethernet. At the physical layer most Ethernet implementations use copper twisted-pair cables (including the common 10BASE-T networks). Some early implementations used coaxial cables. And some implementations (especially high speed ones) use optical fibres. Optical fibres are also likely to feature prominently in the forthcoming 10-gigabit Ethernet implementations.[56] Where optical fibre is used, the distinction must be made between multi-mode fibre and single-mode fibre. Multi-mode fibre can be thought of as thicker optical fibre that is cheaper to manufacture but that suffers from less usable bandwidth and greater attenuation.

Electrical engineering

Electrical Engineers design power systems…

… and complex electronic circuits. Electrical engineering (sometimes referred to as electrical and electronic engineering) is a professional engineering discipline that deals with the study and application of electricity, electronics and electromagnetism. The field first became an identifiable occupation in the late nineteenth century with the commercialization of the electric telegraph and electrical power supply. The field now covers a range of sub-disciplines including those that deal with power, optoelectronics, digital electronics, analog electronics, artificial intelligence, control systems, electronics, signal processing and telecommunications. The term electrical engineering may or may not encompass electronic engineering. Where a distinction is made, electrical engineering is considered to deal with the problems associated with large-scale electrical systems such as power transmission and motor control, whereas electronic engineering deals with the study of small-scale electronic systems including computers and integrated circuits.Another way of looking at

the distinction is that electrical engineers are usually concerned with using electricity to transmit energy, while electronics engineers are concerned with using electricity to transmit information.

History History of electrical engineering

Early developments Electricity has been a subject of scientific interest since at least the 17th century, but it was not until the 19th century that research into the subject started to intensify. Notable developments in this century include the work of Georg Ohm, who in 1827 quantified the relationship between the electric current and potential difference in a conductor, Michael Faraday, the discoverer of electromagnetic induction in 1831, and James Clerk Maxwell, who in 1873 published a unified theory of electricity and magnetism in his treatise on Electricity and Magnetism.

During these years, the study of electricity was largely considered to be a subfield of physics. It was not until the late 19th century that universities started to offer degrees in electrical engineering. The Darmstadt University of Technology founded the first chair and the first faculty of electrical engineering worldwide in 1882. In 1883 Darmstadt University of Technology and Cornell University introduced the world’s first courses of study in electrical engineering and in 1885 the University College London founded the first chair of electrical engineering in the United Kingdom.The University of Missouri subsequently established the first department of electrical engineering in the United States in 1886.

Thomas Edison built the world’s first large-scale electrical supply network During this period, the work concerning electrical engineering increased dramatically. In 1882, Edison switched on the world’s first large-scale electrical supply network that provided 110 volts direct current to fifty-nine customers in lower Manhattan. In 1887, Nikola Tesla filed a number of patents related to a competing form of power distribution known as alternating current. In the following years a bitter rivalry between Tesla and Edison, known as the “War of Currents”, took place over the preferred method of distribution. AC eventually replaced DC for generation and power distribution, enormously extending the range and improving the safety and efficiency of power distribution.

Nikola Tesla made long-distance electrical transmission networks possible. The efforts of the two did much to further electrical engineering—Tesla’s work on induction motors and polyphase systems influenced the field for years to come, while Edison’s work on telegraphy and his development of the stock ticker proved lucrative for his company, which ultimately became General Electric. However, by the end of the 19th century, other key figures in the progress of electrical engineering were beginning to emerge.

Modern developments Emergence of radio and electronics During the development of radio, many scientists and inventors contributed to radio technology and electronics. In his classic UHF experiments of 1888, Heinrich Hertz transmitted (via a spark-gap transmitter) and detected radio waves using electrical equipment. In 1895, Nikola Tesla was able to detect signals from the transmissions of his

New York lab at West Point (a distance of 80.4 km). In 1897, Karl Ferdinand Braun introduced the cathode ray tube as part of an oscilloscope, a crucial enabling technology for electronic television.John Fleming invented the first radio tube, the diode, in 1904. Two years later, Robert von Lieben and Lee De Forest independently developed the amplifier tube, called the triode. In 1920 Albert Hull developed the magnetron which would eventually lead to the development of the microwave oven in 1946 by Percy Spencer. In 1934 the British military began to make strides towards radar (which also uses the magnetron), under the direction of Dr Wimperis culminating in the operation of the first radar station at Bawdsey in August 1936. In 1941 Konrad Zuse presented the Z3, the world’s first fully functional and programmable computer. In 1946 the ENIAC (Electronic Numerical Integrator and Computer) of John Presper Eckert and John Mauchly followed, beginning the computing era. The arithmetic performance of these machines allowed engineers to develop completely new technologies and achieve new objectives, including the Apollo missions and the NASA moon landing. The invention of the transistor in 1947 by William B. Shockley, John Bardeen and Walter Brattain opened the door for more compact devices and led to the development of the integrated circuit in 1958 by Jack Kilby and independently in 1959 by Robert Noyce. In 1968 Marcian Hoff invented the first microprocessor at Intel and thus ignited the development of the personal computer. The first realization of the microprocessor was the Intel 4004, a 4-bit processor developed in 1971, but only in 1973 did the Intel 8080, an 8-bit processor, make the building of the first personal computer, the Altair 8800, possible.

Education Electrical engineers typically possess an academic degree with a major in electrical engineering. The length of study for such a degree is usually four or five years and the completed degree may be designated as a Bachelor of Engineering, Bachelor of Science, Bachelor of Technology or Bachelor of Applied Science depending upon the university. The degree generally includes units covering physics, mathematics, project management and specific topics in electrical engineering. Initially such topics cover most, if not all, of the sub-disciplines of electrical engineering. Students then choose to specialize in one or more sub-disciplines towards the end of the degree. Some electrical engineers also choose to pursue a postgraduate degree such as a Master of Engineering/Master of Science, a Master of Engineering Management, a Doctor of Philosophy in Engineering or an Engineer’s degree. The Master and Engineer’s degree may consist of either research, coursework or a mixture of the two. The Doctor of Philosophy consists of a significant research component and is often viewed as the entry point to academia. In the United Kingdom and various other European countries, the Master of Engineering is often considered an undergraduate degree of slightly longer duration than the Bachelor of Engineering.

Practicing engineers In most countries, a Bachelor’s degree in engineering represents the first step towards professional certification and the degree program itself is certified by a professional body. After completing a certified degree program the engineer must satisfy a range of requirements (including work experience requirements) before being certified. Once certified the engineer is designated the title of Professional Engineer (in the United States, Canada and South Africa ), Chartered Engineer (in the United Kingdom, Ireland, India and Zimbabwe), Chartered Professional Engineer (in Australia and New Zealand) or European Engineer (in much of the European Union). The advantages of certification vary depending upon location. For example, in the United States and Canada “only a licensed engineer may seal engineering work for public and private clients”. This requirement is enforced by state and provincial legislation such as Quebec’s Engineers Act. In other countries, such as Australia, no such legislation exists. Practically all certifying bodies maintain a code of ethics that they expect all members to abide by or risk expulsion. In this way these organizations play an important role in maintaining ethical standards for the profession. Even in jurisdictions where certification has little or no legal bearing on work, engineers are subject to contract law. In cases where an engineer’s work fails he or she may be subject to the tort of negligence and, in extreme cases, the charge of criminal negligence. An engineer’s work must also comply with numerous other rules and regulations such as building codes and legislation pertaining to environmental law. Professional bodies of note for electrical engineers include the Institute of Electrical and Electronics Engineers (IEEE) and the Institution of Electrical Engineers (IEE). The IEEE claims to produce 30 percent of the world’s literature in electrical engineering, has over 360,000 members worldwide and holds over 300 conferences annually. The IEE publishes 14 journals, has a worldwide membership of 120,000, and claims to be the largest professional engineering society in Europe. Obsolescence of technical skills is a serious concern for electrical engineers. Membership and participation in technical societies, regular reviews of periodicals in the field and a habit of continued learning are therefore essential to maintaining proficiency. In countries such as Australia, Canada and the United States electrical engineers make up around 0.25% of the labour force (see note). Outside of these countries, it is difficult to gauge the demographics of the profession due to less meticulous reporting on labour statistics. However, in terms of electrical engineering graduates per-capita, electrical engineering graduates would probably be most numerous in countries such as Taiwan, Japan and South Korea.

Tools and work From the Global Positioning System to electric power generation, electrical engineers are responsible for a wide range of technologies. They design, develop, test and supervise the

deployment of electrical systems and electronic devices. For example, they may work on the design of telecommunication systems, the operation of electric power stations, the lighting and wiring of buildings, the design of household appliances or the electrical control of industrial machinery.

Satellite Communications is one of many projects an electrical engineer might work on Fundamental to the discipline are the sciences of physics and mathematics as these help to obtain both a qualitative and quantitative description of how such systems will work. Today most engineering work involves the use of computers and it is commonplace to use computer-aided design programs when designing electrical systems. Nevertheless, the ability to sketch ideas is still invaluable for quickly communicating with others. Although most electrical engineers will understand basic circuit theory (that is the interactions of elements such as resistors, capacitors, diodes, transistors and inductors in a circuit), the theories employed by engineers generally depend upon the work they do. For example, quantum mechanics and solid state physics might be relevant to an engineer working on VLSI (the design of integrated circuits), but are largely irrelevant to engineers working with macroscopic electrical systems. Even circuit theory may not be relevant to a person designing telecommunication systems that use off-the-shelf components. Perhaps the most important technical skills for electrical engineers are reflected in university programs, which emphasize strong numerical skills, computer literacy and the ability to understand the technical language and concepts that relate to electrical engineering. For most engineers technical work accounts for only a fraction of the work they do. A lot of time is also spent on tasks such as discussing proposals with clients, preparing budgets and determining project schedules. Many senior engineers manage a team of technicians or other engineers and for this reason project management skills are important. Most engineering projects involve some form of documentation and strong written communication skills are therefore very important. The workplaces of electrical engineers are just as varied as the types of work they do. Electrical engineers may be found in the pristine lab environment of a fabrication plant, the offices of a consulting firm or on site at a mine. During their working life, electrical

engineers may find themselves supervising a wide range of individuals including scientists, electricians, computer programmers and other engineers.

Sub-disciplines Electrical engineering has many sub-disciplines, the most popular of which are listed below. Although there are electrical engineers who focus exclusively on one of these subdisciplines, many deal with a combination of them. Sometimes certain fields, such as electronic engineering and computer engineering, are considered separate disciplines in their own right.

Power Power engineering

Power engineering deals with the generation, transmission and distribution of electricity as well as the design of a range of related devices. These include transformers, electric generators, electric motors and power electronics. In many regions of the world, governments maintain an electrical network called a power grid that connects a variety of generators together with users of their energy. Users purchase electrical energy from the grid, avoiding the costly exercise of having to generate their own. Power engineers may work on the design and maintenance of the power grid as well as the power systems that connect to it. Such systems are called on-grid power systems and may supply the grid with additional power, draw power from the grid or do both. Power engineers may also work on systems that do not connect to the grid, called off-grid power systems, which in some cases are preferable to on-grid systems.

Control Control engineering

Control engineering focuses on the modelling of a diverse range of dynamic systems and the design of controllers that will cause these systems to behave in the desired manner. To implement such controllers electrical engineers may use electrical circuits, digital signal processors and microcontrollers. Control engineering has a wide range of applications from the flight and propulsion systems of commercial airliners to the cruise control present in many modern automobiles. It also plays an important role in industrial automation. Control engineers often utilize feedback when designing control systems. For example, in an automobile with cruise control the vehicle’s speed is continuously monitored and fed back to the system which adjusts the motor’s speed accordingly. Where there is regular feedback, control theory can be used to determine how the system responds to such feedback.

Electronics Electronic engineering

Electronic engineering involves the design and testing of electronic circuits that use the properties of components such as resistors, capacitors, inductors, diodes and transistors to achieve a particular functionality. The tuned circuit, which allows the user of a radio to filter out all but a single station, is just one example of such a circuit. Another example (of a pneumatic signal conditioner) is shown in the adjacent photograph. Prior to the second world war, the subject was commonly known as radio engineering and basically was restricted to aspects of communications and radar, commercial radio and early television. Later, in post war years, as consumer devices began to be developed, the field grew to include modern television, audio systems, computers and microprocessors. In the mid to late 1950s, the term radio engineering gradually gave way to the name electronic engineering. Before the invention of the integrated circuit in 1959, electronic circuits were constructed from discrete components that could be manipulated by humans. These discrete circuits consumed much space and power and were limited in speed, although they are still common in some applications. By contrast, integrated circuits packed a large number— often millions—of tiny electrical components, mainly transistors, into a small chip around the size of a coin. This allowed for the powerful computers and other electronic devices we see today.

Microelectronics Microelectronics

Microelectronics engineering deals with the design of very small electronic components for use in an integrated circuit or sometimes for use on their own as a general electronic component. The most common microelectronic components are semiconductor transistors, although all main electronic components (resistors, capacitors, inductors) can be created at a microscopic level. Microelectronic components are created by chemically fabricating wafers of semiconductors such as silicon (at higher frequencies, gallium arsenide and indium phosphide) to obtain the desired transport of electronic charge and control of current. The field of microelectronics involves a significant amount of chemistry and material science and requires the electronic engineer working in the field to have a very good working knowledge of the effects of quantum mechanics.

Signal processing Signal processing

Signal processing deals with the analysis and manipulation of signals. Signals can be either analog, in which case the signal varies continuously according to the information, or digital, in which case the signal varies according to a series of discrete values representing the information. For analog signals, signal processing may involve the amplification and filtering of audio signals for audio equipment or the modulation and demodulation of signals for telecommunications. For digital signals, signal processing may involve the compression, error detection and error correction of digitally sampled signals.

Telecommunications Telecommunications engineering

Telecommunications engineering focuses on the transmission of information across a channel such as a coax cable, optical fibre or free space. Transmissions across free space require information to be encoded in a carrier wave in order to shift the information to a carrier frequency suitable for transmission, this is known as modulation. Popular analog modulation techniques include amplitude modulation and frequency modulation. The choice of modulation affects the cost and performance of a system and these two factors must be balanced carefully by the engineer. Once the transmission characteristics of a system are determined, telecommunication engineers design the transmitters and receivers needed for such systems. These two are sometimes combined to form a two-way communication device known as a transceiver. A key consideration in the design of transmitters is their power consumption as this is closely related to their signal strength. If the signal strength of a transmitter is insufficient the signal’s information will be corrupted by noise.

Instrumentation engineering Instrumentation engineering

Instrumentation engineering deals with the design of devices to measure physical quantities such as pressure, flow and temperature. The design of such instrumentation requires a good understanding of physics that often extends beyond electromagnetic theory. For example, radar guns use the Doppler effect to measure the speed of oncoming vehicles. Similarly, thermocouples use the Peltier-Seebeck effect to measure the temperature difference between two points. Often instrumentation is not used by itself, but instead as the sensors of larger electrical systems. For example, a thermocouple might be used to help ensure a furnace’s temperature remains constant. For this reason, instrumentation engineering is often viewed as the counterpart of control engineering.

Computers Computer engineering

Computer engineering deals with the design of computers and computer systems. This may involve the design of new hardware, the design of PDAs or the use of computers to control an industrial plant. Computer engineers may also work on a system’s software. However, the design of complex software systems is often the domain of software engineering, which is usually considered a separate discipline. Desktop computers represent a tiny fraction of the devices a computer engineer might work on, as computerlike architectures are now found in a range of devices including video game consoles and DVD players.

Related disciplines Mechatronics is an engineering discipline which deals with the convergence of electrical and mechanical systems. Such combined systems are known as electromechanical systems and have widespread adoption. Examples include automated manufacturing systems, heating, ventilation and air-conditioning systems and various subsystems of aircraft and automobiles. The term mechatronics is typically used to refer to macroscopic systems but futurists have predicted the emergence of very small electromechanical devices. Already such small devices, known as micro electromechanical systems (MEMS), are used in automobiles to tell airbags when to deploy, in digital projectors to create sharper images and in inkjet printers to create nozzles for high-definition printing. In the future it is hoped the devices will help build tiny implantable medical devices and improve optical communication. Biomedical engineering is another related discipline, concerned with the design of medical equipment. This includes fixed equipment such as ventilators, MRI scanners and electrocardiograph monitors as well as mobile equipment such as cochlear implants, artificial pacemakers and artificial hearts.

Power engineering

Rural 3 phase distribution transformer Power engineering is the subfield of electrical engineering that deals with power systems, specifically electric power transmission and distribution, power conversion, and electromechanical devices. Out of necessity, power engineers also rely heavily on the theory of control systems. A power engineer supervises, operates, and maintains machinery and boilers that provide heat, power, refrigeration, and other utility services to heavy industry and large building complexes.

History Power engineering was one of the earliest fields to be exploited in electrical engineering. Early problems solved by engineers include efficient and safe distribution of electric power. Nikola Tesla was a notable pioneer in this field.

Power

Transmission lines transmit power across the grid. Power engineering deals with the generation, transmission and distribution of electricity as well as the design of a range of related devices. These include transformers, electric generators, electric motors and power electronics.

In many regions of the world, governments maintain an electrical network that connects a variety electric generators together with users of their power. This network is called a power grid. Users purchase electricity from the grid avoiding the costly exercise of having to generate their own. Power engineers may work on the design and maintenance of the power grid as well as the power systems that connect to it. Such systems are called on-grid power systems and may supply the grid with additional power, draw power from the grid or do both. Power engineers may also work on systems that do not connect to the grid. These systems are called off-grid power systems and may be used in preference to on-grid systems for a variety of reasons. For example, in remote locations it may be cheaper for a mine to generate its own power rather than pay for connection to the grid and in most mobile applications connection to the grid is simply not practical. Today, most grids adopt three-phase electric power with an alternating current. This choice can be partly attributed to the ease with which this type of power can be generated, transformed and used. Often (especially in the USA), the power is split before it reaches residential customers whose low-power appliances rely upon single-phase electric power. However, many larger industries and organizations still prefer to receive the three-phase power directly because it can be used to drive highly efficient electric motors such as three-phase induction motors. Transformers play an important role in power transmission because they allow power to be converted to and from higher voltages. This is important because higher voltages suffer less power loss during transmission. This is because higher voltages allow for lower current to deliver the same amount of power as power is the product of the two. Thus, as the voltage steps up, the current steps down. It is the current flowing through the components that result in both the losses and the subsequent heating. These losses, appearing in the form of heat, are equal to the current squared times the electrical resistance through which the current flows. For these reasons, electrical substations exist throughout power grids to convert power to higher voltages before transmission and to lower voltages suitable for appliances after transmission.

Components Power engineering is usually broken into three parts:

Generation Generation is converting other forms of power into electrical power. The sources of power include fossil fuels such as coal and natural gas, hydropower, nuclear power, solar power, wind power and other forms.

Transmission Transmission includes moving power over somewhat long distances, from a power station to near where it is used. Transmission involves high voltages, almost always higher than voltage at which the power is either generated or used. Transmission also includes connecting together power systems owned by various companies and perhaps in different states or countries. Transimission includes long meduim and short lines.

Distribution Distribution involves taking power from the transmission system to end users, converting it to voltages at which it is ultimately required.

Optoelectronics Optoelectronics is the study and application of electronic devices that interact with light, and thus is usually considered a sub-field of photonics. In this context, light often includes invisible forms of radiation such as gamma rays, X-rays, ultraviolet and infrared. Optoelectronic devices are electrical-to-optical or optical-to-electrical transducers, or instruments that use such devices in their operation. Electro-optics is often erroneously used as a synonym, but is in fact a wider branch of physics that deals with all interactions between light and electric fields, whether or not they form part of an electronic device. Optoelectronics is based on the quantum mechanical effects of light on semiconducting materials, sometimes in the presence of electric fields. •

•

• • •

Photoelectric or photovoltaic effect, used in: o photodiodes (including solar cells) o phototransistors o photomultipliers o integrated optical circuit (IOC) elements Photoconductivity, used in: o light-dependent resistors o photoconductive camera tubes o charge-coupled imaging devices Stimulated emission, used in: o lasers o injection laser diodes Lossev effect, or radiative recombination, used in: o light-emitting diodes or LED Photoemissivity, used in o photoemissive camera tube

Important applications of optoelectronics include:

• •

Optocoupler optical fiber communications

Photodiode

A photodiode

Photodiode closeup A photodiode is a semiconductor diode that functions as a photodetector. Photodiodes are packaged with either a window or optical fibre connection, in order to let in the light

to the sensitive part of the device. They may also be used without a window to detect vacuum UV or X-rays. A phototransistor is in essence nothing more than a bipolar transistor that is encased in a transparent case so that light can reach the base-collector junction. The phototransistor works like a photodiode, but with a much higher sensitivity for light, because the electrons that are generated by photons in the base-collector junction are injected into the base, and this current is then amplified by the transistor operation. However, a phototransistor has a slower response time than a photodiode.

Principle of operation A photodiode is a p-n junction or p-i-n structure. When light of sufficient photon energy strikes the diode, it excites an electron thereby creating a mobile electron and a positively charged electron hole. If the absorption occurs in the junction’s depletion region, these carriers are swept from the junction by the built-in field of the depletion region, producing a photocurrent. Photodiodes can be used under either zero bias (photovoltaic mode) or reverse bias (photoconductive mode). In zero bias, light falling on the diode causes a voltage to develop across the device, leading to a current in the forward bias direction. This is called the photovoltaic effect, and is the basis for solar cells — in fact, a solar cell is just a large number of big, cheap photodiodes. Diodes usually have extremely high resistance when reverse-biased. This resistance is reduced when light of an appropriate frequency shines on the junction. Hence, a reversebiased diode can be used as a detector by monitoring the current running through it. Circuits based on this effect are more sensitive to light than ones based on the photovoltaic effect. Avalanche photodiodes have a similar structure, but they are operated with much higher reverse bias. This allows each photo-generated carrier to be multiplied by avalanche breakdown, resulting in internal gain within the photodiode, which increases the effective responsivity of the device.

Materials The material used to make a photodiode is critical to defining its properties, because only photons with sufficient energy to excite an electron across the material’s bandgap will produce significant photocurrents. Materials commonly used to produce photodiodes:

Material

Wavelength range (nm)

Silicon

190–1100

Germanium

800–1700

Indium gallium arsenide 800–2600

Lead sulfide

<1000-3500

Because of their greater bandgap, silicon-based photodiodes generate less noise than germanium-based photodiodes, but germanium photodiodes must be used for wavelengths longer than approximately 1 µm.

Features Critical performance parameters of a photodiode include: responsivity The ratio of generated photocurrent to incident light power, typically expressed in A/W when used in photoconductive mode. The responsivity may also be expressed as a quantum efficiency, or the ratio of the number of photogenerated carriers to incident photons and thus a unitless quantity. dark current The current through the photodiode in the absence of any input optical signal, when it is operated in photoconductive mode. The dark current includes photocurrent generated by background radiation and the saturation current of the semiconductor junction. Dark current must be accounted for by calibration if a photodiode is used to make an accurate optical power measurement, and it is also a source of noise when a photodiode is used in an optical communication system. noise-equivalent power (NEP) The minimum input optical power to generate photocurrent, equal to the rms noise current in a 1 hertz bandwidth. The related characteristic detectivity (D) is the inverse of NEP, 1/NEP; and the specific detectivity ( ) is the detectivity normalized to the area (A) of the photodetector, . The NEP is roughly the minimum detectable input power of a photodiode. When a photodiode is used in an optical communication system, these parameters contribute to the sensitivity of the optical receiver, which is the minimum input power required for the receiver to achieve a specified bit error ratio.

Applications

Photodiode schematic symbol P-N photodiodes are used in similar applications to other photodetectors, such as photoconductors, charge-coupled devices, and photomultiplier tubes. Photodiodes are used in consumer electronics devices such as compact disc players, smoke detectors, and the receivers for remote controls in VCRs and televisions. In other consumer items such as camera light meters, clock radios (the ones that dim the display when its dark) and street lights, photoconductors are often used rather than photodiodes, although in principle either could be used. Photodiodes are often used for accurate measurement of light intensity in science and industry. They generally have a better, more linear response than photoconductors. They are also widely used in various medical applications, such as detectors for Computed tomography (coupled with scintillators) or instruments to analyze samples (immunoassay). They are also used in Blood gas monitors. PIN diodes are much faster and more sensitive than ordinary p-n junction diodes, and hence are often used for optical communications and in lighting regulation. P-N photodiodes are not used to measure extremely low light intensities. Instead, if high sensitivity is needed, avalanche photodiodes, intensified charge-coupled devices or photomultiplier tubes are used for applications such as astronomy, spectroscopy, nightvision equipment and laser range finding.

Comparison with photomultipliers Advantages compared to photomultipliers: 1. Excellent linearity of output current as a function of incident light 2. Spectral response from 190 nm to 1100 nm (silicon), longer wavelengths with other semiconductor materials 3. Low noise 4. Ruggedized to mechanical stress 5. Low cost 6. Compact and light weight

7. Long lifetime 8. High quantum efficiency, typically 80% 9. No high voltage required Disadvantages compared to photomultipliers: 1. Small area 2. No internal gain (except avalanche photodiodes, but their gain is typically 102–103 compared to up to 108 for the photomultiplier) 3. Much lower overall sensitivity 4. Photon counting only possible with specially designed, usually cooled photodiodes, with special electronic circuits 5. Response time for many designs is slower

Phototransistor The fact that traditional transistors (these days called “Bipolar Junction Transistors” or BJTs) are photosensitive has been known ever since they were invented. This is one of the reasons that they are usually sealed in light tight cans - because unwanted light is a source of noise. Phototransistors are very similar to ordinary BJTs except they are designed for use as detectors. Transistors are amplifiers and in a phototransistor the amplifier gain is controlled by the amount of light striking the device. Light arriving in the device is absorbed and creates charge carrier pairs in many different places. The action is different depending on where the charge carrier pairs are created. However, in an intentional phototransistor, absorbtion is intended to take place in the depletion zone between the emitter and the base. Creation of charge carriers here causes a current to flow in the E-B circuit which is then amplified by the transistor action of the device. These are much lower in noise and have a higher output than APDs, but are significantly less responsive than either APDs or p-i-n diodes. The major problem with phototransistors is materials. We would like to use silicon or gallium arsenide but these have too great a bandgap energy and are limited to detecting wavelengths shorter than about 1 micron. Germanium is usable in the 1300 nm band but while it is easily possible to build transistors with smaller bandgap materials (such as InP) there is no established technology to do so. This takes away much of the potential cost advantage in the 1550 region. The major use of phototransistors is in non-communications applications using visible (or near visible) light. Alarm systems (light beam detection) and remote controls for TV sets and automobiles are among the most common uses. Phototransistors are occasionally built as part of an integrated circuit. In this configuration they are referred to as Integrated Preamplifier Detectors (IPDs).

Photomultiplier Photomultiplier tubes (photomultipliers or PMTs for short) are extremely sensitive detectors of light in the ultraviolet, visible and near infrared. These detectors multiply the signal produced by incident light by as much as 108, from which single photons can be resolved. The combination of high gain, low noise, high frequency response and large area of collection have meant that these devices still find applications in nuclear and particle physics, astronomy, medical imaging and motion picture film scanning (telecine). Semiconductor devices like avalanche photodiodes have replaced photomultipliers in some applications, but photomultipliers are still used in most cases.

Structure and operating principles

Schematic of a photomultiplier tube coupled to a scintillator. Photomultipliers are constructed from a glass vacuum tube which houses a photocathode, several dynodes, and an anode. Incident photons strike the photocathode material which is present as a thin deposit on the entry window of the device, with electrons being produced as a consequence of the photoelectric effect. These electrons are directed by the focusing electrode towards the electron multiplier, where electrons are multiplied by the process of secondary emission. The electron multiplier consists of a number of electrodes, called dynodes. Each dynode is held at a more positive voltage than the previous one. The electrons leave the photocathode, having the energy of the incoming photon. As they move towards the first dynode they are accelerated by the electric field and arrive with much greater energy. On striking the first dynode, more low energy electrons are emitted and these, in turn, are accelerated toward the second dynode. The geometry of the dynode chain is such that a cascade occurs with an ever-increasing number of electrons being produced at each stage. Finally the anode is reached where the accumulation of charge results in a sharp current pulse indicating the arrival of a photon at the photocathode.

Usage considerations

Photomultiplier Photomultiplier tubes typically require 1000 to 2000 volts for proper operation. The most negative voltage is connected to the cathode, and the most positive voltage is connected to the anode. (Negative high voltage supplies are usually preferred.) Voltages are distributed to the dynodes by a resistive voltage divider, though variations such as active designs (with transistors or diodes) are possible. The divider design influences aspects such as the frequency response and rise time, and therefore may be critical to an application. While powered, photomultipliers must be shielded from ambient light to prevent their destruction through overexcitation. If used in a location with high magnetic fields (which will curve electron paths), they are usually shielded by a layer of mu-metal.

Integrated optical circuit An integrated optical circuit is one or more circuits composed of solid-state optical components on a semiconductor or dielectric substrate. Components include light

sources, optical filters, photodetectors, and thin-film optical waveguides. An example of an integrated optical circuit is an opto-isolator (or opto-coupler) which allows one circuit to interact with another while remaining electrically separated from the other. A 2005 developmentsolved a quantum noise problem that prevented silicon from being used to generate laser light, permitting new integrated optical circuits to use high-bandwidth laser light generated within the circuit itself as a signal medium

Digital circuit

A digital circuit that acts as a binary clock, hand-wired on a series of prototyping sockets. A digital circuit is based on a number of discrete voltage levels, as distinct from an analog circuit that uses continuous voltages to represent variables directly. Digital circuits are the most common mechanical representation of Boolean algebra and are the basis of all digital computers. They can also be used to process digital information without being connected up as a computer. Such circuits are referred to as “random logic”. In most cases the number of states is two, and these states are represented by two voltage levels: one near to zero volts and one at a higher level depending on the supply voltage in use. These two levels are often represented as “Low” and “High.” To most electronic engineers, the terms “digital circuit”, “digital system” and “logic” are interchangeable in the context of digital circuits.

Properties of digital circuits Digital circuits are distinct from analog circuits. In analog circuits, quantities are represented by continuously varying voltages, currents, or frequencies. The usual advantages of digital circuits when compared to analog circuits are: •

• •

Digital circuits are less affected by noise. In fact, if the noise is below a certain level (the noise margin), a digital circuit behaves as if there was no noise at all — this is a necessary and sufficient property for a circuit to be considered a digital circuit. However, if the noise exceeds this level, the digital circuit can give catastrophically wrong results. Digital signals can thus be regenerated to achieve lossless data transmission, within certain limits. Analog signal transmission and processing, by contrast, always introduces noise. Digital systems interface well with computers and are easy to control with software. It is often possible to add new features to a digital system without changing hardware, and to do this remotely, just by uploading new software.

• •

•

Design errors or bugs can be worked-around with a software upgrade, after the product is in customer hands. More digital circuitry can be fabricated per square millimeter of integrated-circuit material. Information storage can be much easier in digital systems than in analog ones. In particular, the great noise-immunity of digital systems makes it possible to store data and retrieve it later without degradation. In an analog system, aging and wear and tear will degrade the information in storage, but in a digital system, as long as the wear and tear is below a certain level, the information can be recovered perfectly. Theoretically, there is no data-loss when copying digital data. This is a great advantage over analog systems, which faithfully reproduce every bit of noise that makes its way into the signal.

The usual disadvantages include: •

•

•

Digital systems can be fragile, in that if a single piece of digital data is lost or misinterpreted, the meaning of large blocks of related data can completely change. This problem can be mitigated by designing the digital system for robustness. For example, a parity bit or other error-detecting or error-correcting code can be inserted into the signal path so that if less than a certain fraction of the data is corrupted, the system can determine that this has occurred and possibly uncorrupt the data, or ask for the corrupted data to be resent. In a state-machine, the state transition logic can be designed to catch all unused states and trigger a reset sequence or other error recovery routine. For example, it is standard practice in embedded software design to fill unused program memory with interrupt instructions that point to an error recovery routine, to help guard against a failure that corrupts the microcontroller’s instruction pointer which could otherwise cause random code to be executed. The world in which we live is analog, and signals from this world such as light, temperature, sound, electrical conductivity, electric and magnetic fields, and phenomena such as the flow of time, are for most practical purposes continuous and thus analog quantities rather than discrete digital ones. For a digital system to do useful things in the real world, translation from the continuous realm to the discrete digital realm must occur, resulting in quantization errors. This problem can usually be mitigated by designing the system to store enough digital data to represent the signal to the desired degree of fidelity. The Nyquist-Shannon sampling theorem provides an important guideline as to how much digital data is needed to accurately portray a given analog signal. Digital circuits are made from analog components, and care has to be taken in design so that the analog nature of these underlying components don’t dominate over the desired digital behavior. In particular, attention must be paid to all noise and timing margins, to parasitic inductances and capacitances, to proper filtering of power and ground connections, to electromagnetic coupling amongst datalines, and many other details. Inattention to these can cause intermittent problems such as “glitches”, vanishingly-fast pulses that may trigger some logic but not others,

•

•

•

“runt pulses” that do not reach valid switching (threshold) voltages, or unexpected (“undecoded”) combinations of logic states. A corollary of the fact that digital circuits are made from analog components is the fact that digital circuits are slower to perform calculations than analog circuits that occupy a similar amount of physical space and consume the same amount of power. However, the digital circuit will perform the calculation with much better repeatability, due to the high noise immunity of digital circuitry. Digital circuits use more energy than analog circuits to accomplish the same calculations and signal processing tasks, thus producing more heat as well. In portable or battery-powered systems this can be a major limiting factor, but in a situation where power is plentiful, a digital system is often preferred because of all the advantages listed above, especially that of (re-)programmability and ease of upgrading without requiring hardware changes. A particular example is the cellular telephone, which being a battery-powered portable device, uses a lowpower analog front-end to acquire and tune in the radio signal from the base station. The base station, being in a fixed location with access to the power grid, can afford to use power-hungry software-defined (digital) radio techniques that digitize the signal essentially at the antenna (after wideband filtering and downconversion to intermediate frequency) and performs all channelization and demodulation via software-driven calculations. Such base stations can be reprogrammed, potentially via remote control, to process the signals used in future cellular standards as those standards become available. Digital circuits are sometimes more expensive, especially in small quantities.

Logic voltage levels

Hobbyist frequency counter circuit built almost entirely of TTL logic chips. The two states of a wire are usually represented by some measurement of electric current: Voltage is the most common, but current is used in some logic families. A threshold is designed for each logic family. When below that threshold, the wire is “low,” when above “high.” Digital circuits establish a “no man’s area” or “exclusion zone” that is wider than the tolerances of the components. The circuits avoid that area, in order to avoid indeterminate results. It is usual to allow some tolerance in the voltage levels used; for example, 0 to 2 volts might represent logic 0, and 3 to 5 volts logic 1. A voltage of 2 to 3 volts would be invalid and would occur only in a fault condition or during a logic level transition, as

most circuits are not purely resistive, and therefore cannot instantly change voltage levels. However, few logic circuits can detect such a fault, and most will just choose to interpret the signal randomly as either a 0 or a 1. The levels represent the binary integers or logic levels of 0 and 1. In active-high logic, “low” represents binary 0 and “high” represents binary 1. Active-low logic uses the reverse representation.

Examples of binary logic levels:

Technology

L voltage

H voltage

Notes

CMOS

0V to VCC/2

VCC/2 to VCC VCC = supply voltage

TTL

0V to 0.8V

2V to VCC

ECL

-1.175V to -VEE .75V to 0V

VCC is 4.75V to 5.25V

VEE is about -5.2V VCC=Ground

Construction A digital circuit is often constructed from small electronic circuits called logic gates. Each logic gate represents a function of boolean logic. A logic gate is an arrangement of electrically controlled switches. The output is an electrical flow or voltage, that can, in turn, control more logic gates. Logic gates often use the fewest number of transistors in order to reduce their size, power consumption and cost, and increase their reliability. Manufactured as integrated circuits, they are the least expensive implementation when made in large volumes. They are usually designed by engineers using electronic design automation software (See below for more information). Another form of digital circuit is constructed from lookup tables, (many sold as “programmable logic devices”, though other kinds of PLDs exist). Lookup tables can perform all the same functions as machines based on logic gates, but lookup tables can be easily reprogrammed without changing the wiring. This means that a designer can often repair errors without changing the arrangement of wires. Therefore, in small volume products, programmable logic devices are often the preferred solution. They are usually designed by engineers using electronic design automation software (See below for more information).

When the volumes are medium to large, and the logic can be slow, or involves complex algorithms or sequences, often a small microcontroller is programmed to make an embedded system. These are usually programmed by software engineers. When only one digital circuit is needed, and its design is totally customized, as for a factory production line controller, the conventional solution is a programmable logic controller, or PLC. These are usually programmed by electricians, using ladder logic.

Structure of digital systems Engineers use many methods to minimize logic functions, in order to reduce the complexity, and thus the number of errors and the expense of digital circuits. The most widely used methods include Truth tables, Karnaugh Maps, and Boolean Algebra. Representations are crucial to an engineer’s design of digital circuits. Some analysis methods only work with particular representations. The classical way to represent a digital circuit is with an equivalent set of logic gates. Another way, often with the least electronics, is to construct an equivalent system of electronic switches (usually transistors). One of the easiest ways is to simply have a memory containing a Truth table. The inputs are fed into the address of the memory, and the data outputs of the memory become the outputs. For automated analysis, these representations have digital file formats that can be processed by computer programs. Most digital engineers are very careful to select computer programs (“tools”) with compatible file formats. To choose representations, engineers consider types of digital systems. Most digital systems divide into “combinatorial systems” and “sequential systems”. A combinatorial system always presents the same output when given the same inputs. It is basically a representation of a set of logic functions, as already discussed. A sequential system is a combinatorial system with some of the outputs fed back as inputs. This makes the digital machine perform a “sequence” of operations. The simplest sequential system is probably a flip flop, a mechanism that represents a binary digit or “bit”. Sequential systems are often designed as state machines. In this way, engineers can design a system’s gross behavior, and even test it in a simulation, without considering all the details of the logic functions. Sequential systems divide into two further subcategories. “Synchronous” sequential systems change state all at once, when a “clock” signal changes state. “Asynchronous” sequential systems propagate changes whenever inputs change. Synchronous sequential systems are made of well-characterized asynchronous circuits such as flip-flops, that change only when the clock changes, and which have carefully designed timing margins.

The usual way to implement a synchronous sequential state machine is divide it into a piece of combinatorial logic and a set of flip flops called a “state register.” Each time a clock signal ticks, the state register captures the feedback generated from the previous state of the combinatorial logic, and feeds it back as an unchanging input to the combinatorial part of the state machine. The fastest rate of the clock is set by the most time-consuming logic calculation in the combinatorial logic. The state register is just a representation of a binary number. If the states in the state machine are numbered (easy to arrange), the logic function is just some logic that produces the number of the next state. In comparison, asynchronous systems are very hard to design because all possible states, in all possible timings must be considered. The usual method is to construct a table of the minimum and maximum time that each such state can exist, and then adjust the circuit to minimize the number of such states, and force the circuit to periodically wait for all of its parts to enter a compatible state. (This is called “self-resynchronization.”) Without such careful design, it is easy to accidentally produce asynchronous logic that is “unstable”, that is, real electronics will have unpredictable results because of the cumulative delays caused by small variations in the values of the electronic components. Certain circuits (such as the synchronizer flip-flops, switch debouncers, and the like which allow external unsynchronized signals to enter synchronous logic circuits) are inherently asynchronous in their design and must be analyzed as such. As of now (2005), almost all digital machines are synchronous designs because it is much easier to create and verify a synchronous design. However, asynchronous logic is thought to be superior, if it can be made to work, because its speed is not constrained by an arbitrary clock; instead, it simply runs at the maximum speed permitted by the propagation rates of the logic gates from which it is constructed. Building an asynchronous circuit using faster parts implicitly makes the circuit “go” faster. More generally, many digital systems are data flow machines. These are usually designed using synchronous register transfer logic, using specialized programming languages such as VHDL or Verilog. In register transfer logic, binary numbers are stored in groups of flip flops called registers. The outputs of each register are a bundle of wires called a “bus” that carries that number to other calculations. A calculation is simply a piece of combinatorial logic. Each calculation also has an output bus, and these may be connected to the inputs of several registers. Sometimes a register will have a multiplexer on its input, so that it can store a number from any one of several buses. Alternatively, the outputs of several items may be connected to a bus through buffers that can turn off the output of all of the devices except one. A sequential state machine controls when each register accepts new data from its input. In the 1980s, some researchers discovered that almost all synchronous register-transfer machines could be converted to asynchronous designs by using first-in-first-out

synchronization logic. In this scheme, the digital machine is characterized as a set of data flows. In each step of the flow, an asynchronous “synchronization circuit” determines when the outputs of that step are valid, and presents a signal that says, “grab the data” to the stages that use that stage’s inputs. It turns out that just a few relatively simple synchronization circuits are needed. The most general-purpose register-transfer logic machine is a computer. This is basically an automatic binary abacus. The control unit of a computer is usually designed as a microprogram run by a microsequencer. A microprogram is much like a player-piano roll. Each table entry or “word” of the microprogram commands the state of every bit that controls the computer. The sequencer then counts, and the count addresses the memory or combinatorial logic machine that contains the microprogram. The bits from the microprogram control the arithmetic logic unit, memory and other parts of the computer, including the microsequencer itself. In this way, the complex task of designing the controls of a computer is reduced to a simpler task of programming a relatively independent collection of much simpler logic machines. Computer architecture is a specialized engineering activity that tries to arrange the registers, calculation logic, buses and other parts of the computer in the best way for some purpose. Computer architects have applied large amounts of ingenuity to computer design to reduce the cost and increase the speed and immunity to programming errors of computers. An increasingly common goal is to reduce the power used in a batterypowered computer system, such as a cell-phone. Many computer architects serve an extended apprenticeship as microprogrammers. “Specialized computers” are usually a conventional computer with a special-purpose microprogram.

Automated design tools To save costly engineering effort, much of the effort of designing large logic machines has been automated. The computer programs are called “electronic design automation tools” or just “EDA.” Simple truth table-style descriptions of logic are often optimized with EDA that automatically produces reduced systems of logic gates or smaller lookup tables that still produce the desired outputs. Most practical algorithms for optimizing large logic systems use algebraic manipulations or binary decision diagrams, and there are promising experiments with genetic algorithms and annealing optimizations. To automate costly engineering effort, some EDA can take state tables that describe state machines and automatically produce a truth table for the combinatorial part of a state

machine. The state table is a piece of text that lists each state, and the conditions that can exit that state. It is common for the truth tables of such computer-generated state-machines to be optimized with logic-minimization software. This is a simple example of how complex logic machines are broken into simpler parts. Often, real logic systems are designed as a series of sub-projects, which are combined using a “tool flow”. The tool flow is usually a “script”, a simplified computer language that can invoke the software design tools in the right order. Tool flows for large logic systems such as microprocessors can be thousands of commands long, and combine the work of hundreds of engineers. Writing and debugging tool flows is an established engineering specialty in companies that produce complex logic machines. The tool flow usually terminates in a detailed computer file or set of files that describe how to physically construct the logic machine. Often it consists of instructions to draw the transistors and wires on an integrated circuit or a printed circuit board. Parts of tool flows are “debugged” by testing the outputs of simulated logic machines against expected inputs. The test tools take computer files with sets of inputs and outputs, and highlight discrepancies between the simulated behavior and the expected behavior. These test data are usually called “test vectors.” Often, the test vectors are preserved and used in the factory to test that newly constructed logic machines work correctly.

Design for testability A large logic machine (say, with more than a hundred logical variables) can have an astronomical number of possible states. Obviously, in the factory, testing every state is impractical if testing each state takes a microsecond, and there are more states than the number of microseconds since the universe began. Unfortunately, this ridiculoussounding case is typical. Fortunately, large logic machines are almost always designed as assemblies of smaller logic machines. To save time, the smaller sub-machines are isolated by permanentlyinstalled “design for test” circuitry, and are tested independently. One common test scheme known as “scan design” moves test bits serially (one after another) from external test equipment through one or more serial shift registers known as “scan chains”. Serial scans have only one or two wires to carry the data, and minimize the physical size and expense of the infrequently-used test logic. After all the test data bits are in place, the design is reconfigured to be in “normal mode” and one or more clock pulses are applied, to test for faults (e.g. stuck-at low or stuck-at high) and capture the test result into flip-flops and/or latches in the scan shift register(s).

Finally, the result of the test is shifted out to the block boundary and compared against the predicted “good machine” result. In a board-test environment, serial to parallel testing has been formalized with a standard called “JTAG” (named after the “Joint Testing Acting Group” that proposed it). Another common testing scheme provides a test mode that forces some part of the logic machine to enter a “test cycle.” The test cycle usually exercises large independent parts of the machine.

Trade-offs Several numbers determine the practicality of a system of digital logic. Engineers explored numerous electronic devices to get an ideal combination of speed, low cost and reliability. The cost of a logic gate is crucial. In the 1930s, the earliest digital logic systems were constructed from telephone relays because these were inexpensive and relatively reliable. After that, engineers always used the cheapest available electronic switches that could still fulfill the requirements. The earliest integrated circuits were a happy accident. They were constructed not to save money, but to save weight, and permit the Apollo Guidance Computer to control an inertial guidance system for a spacecraft. The first integrated circuit logic gates cost nearly $50 (in 1960 dollars, when an engineer earned $10,000/year). To everyone’s surprise, by the time the circuits were mass-produced, they had become the leastexpensive method of constructing digital logic. Improvements in this technology have driven all subsequent improvements in cost. With the rise of integrated circuits, reducing the absolute number of chips used represented another way to save costs. The goal of a designer is not just to make the simplest circuit, but to keep the component count down. Sometimes this results in slightly more complicated designs with respect to the underlying digital logic but nevertheless reduces the number of components, board size, and even power consumption. For example, in some logic families, NAND gates are the simplest digital gate to build. All other logical operations can be implemented by NAND gates. If a circuit already required a single NAND gate, and a single chip normally carried four NAND gates, then the remaining gates could be used to implement other logical operations like logical and. This could eliminate the need for a separate chip containing those different types of gates. The “reliability” of a logic gate describes its mean time between failure (MTBF). Digital machines often have millions of logic gates. Also, most digital machines are “optimized” to reduce their cost. The result is that often, the failure of a single logic gate will cause a digital machine to stop working.

Digital machines first became useful when the MTBF for a switch got above a few hundred hours. Even so, many of these machines had complex, well-rehearsed repair procedures, and would be nonfunctional for hours because a tube burned-out, or a moth got stuck in a relay. Modern transistorized integrated circuit logic gates have MTBFs of nearly a trillion (1x10^12) hours, and need them because they have so many logic gates. The “fan out” describes how many logic inputs can be controlled by a single logic output. The minimum practical fan out is about five. Modern electronic logic using CMOS transistors for switches have fanouts near fifty, and can sometimes go much higher. The “switching speed” describes how many times per second an inverter (an electronic representation of a “logical not” function) can change from true to false and back. Faster logic can accomplish more operations in less time. Digital logic first became useful when switching speeds got above fifty hertz, because that was faster than a team of humans operating mechanical calculators. Modern electronic digital logic routinely switches at five gigahertz (5x109 hertz), and some laboratory systems switch at more than a terahertz (1x1012 hertz).

Non-electronic logic It is possible to construct non-electronic digital mechanisms. In principle, any technology capable of representing discrete states and representing logic operations could be used to build mechanical logic. Danny Hillis, co-author of The Connection Machine, once built a working computer from Tinker Toys, string, a brick, and a sharpened pencil, which is supposed to be in the Houston Museum of Science. Hydraulic, pneumatic and mechanical versions of logic gates exist and are used in situations where electricity cannot be used. The first two types are considered under the heading of fluidics. One application of fluidic logic is in military hardware that is likely to be exposed to a nuclear electromagnetic pulse (nuclear EMP, or NEMP) that would destroy any electrical circuits. Mechanical logic is frequently used in inexpensive controllers, such as those in washing machines. Famously, the first computer design, by Charles Babbage, was designed to use mechanical logic. Mechanical logic might also be used in very small computers that could be built by nanotechnology. Another example is that if two particular enzymes are required to prevent the construction of a particular protein, this is the equivalent of a biological “NAND” gate.

Recent developments The discovery of superconductivity has enabled the development of Rapid Single Flux Quantum (RSFQ) circuit technology, which uses Josephson junctions instead of transistors. Most recently, attempts are being made to construct purely optical computing systems capable of processing digital information using nonlinear optical elements.

Combinational logic In digital circuit theory, combinational logic (also called combinatorial logic) is a type of logic circuit whose output is a 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. Combinational logic is used in computer circuits to do boolean algebra on input signals and on stored data. Practical computer circuits normally contain a mixture of combinational and sequential logic. For example, the part of an arithmetic logic unit, or ALU, that does mathematical calculations is constructed in accord with combinational logic, although the ALU is controlled by a sequencer that is constructed in accord with sequential logic.

Boolean algebra For a basic introduction to sets, Boolean operations, Venn diagrams, truth tables, and Boolean applications, see Boolean logic. For an alternative perspective see Boolean algebras canonically defined. In abstract algebra, a Boolean algebra is an algebraic structure (a collection of elements and operations on them obeying defining axioms) that captures essential properties of both set operations and logic operations. Specifically, it deals with the set operations of intersection, union, complement; and the logic operations of AND, OR, NOT. For example, the logical assertion that a statement a and its negation ¬a cannot both be true,

Boolean lattice of subsets

parallels the set-theory assertion that a subset A and its complement AC have empty intersection,

Because truth values can be represented as binary numbers or as voltage levels in logic circuits, the parallel extends to these as well. Thus the theory of Boolean algebras has many practical applications in electrical engineering and computer science, as well as in mathematical logic. A Boolean algebra is also called a Boolean lattice. The connection to lattices (special partially ordered sets) is suggested by the parallel between set inclusion, A B, and ordering, a ≤ b. Consider the lattice of all subsets of {x,y,z}, ordered by set inclusion. This Boolean lattice is a partially ordered set in which, say, {x} ≤ {x,y}. Any two lattice elements, say p = {x,y} and q = {y,z}, have a least upper bound, here {x,y,z}, and a greatest lower bound, here {y}. Suggestively, the least upper bound (or join or supremum) is denoted by the same symbol as logical OR, p q; and the greatest lower bound (or meet or infimum) is denoted by same symbol as logical AND, p q. The lattice interpretation helps in generalizing to Heyting algebras, which are Boolean algebras freed from the restriction that either a statement or its negation must be true. Heyting algebras correspond to intuitionist (constructivist) logic just as Boolean algebras correspond to classical logic.

Formal definition A Boolean algebra is a set A, supplied with two binary operations (called AND), (called OR), a unary operation (called NOT) and two distinct elements 0 (called zero) and 1 (called one), such that, for all elements a, b and c of set A, the following axioms hold: associativity commutativity absorption distributivity complements The first three pairs of axioms above: associativity, commutativity and absorption, mean that (A, , ) is a lattice. If A is a lattice and one of the above distributivity laws holds, then the second distributivity law can be proven. Thus, a Boolean algebra can also be equivalently defined as a distributive complemented lattice. From these axioms, one can show that the smallest element 0, the largest element 1, and the complement ¬a of any element a are uniquely determined. For all a and b in A, the following identities also follow: idempotency boundedness 0 and 1 are complements De Morgan’s laws involution

Examples •

The simplest Boolean algebra has only two elements, 0 and 1, and is defined by the rules: 0 1

0 1

0 0 0

0 0 1

1 0 1

1 1 1

a 0 1 ¬a 1 0

•

•

•

•

• • •

•

•

•

It has applications in logic, interpreting 0 as false, 1 as true, as and, as or, and ¬ as not. Expressions involving variables and the Boolean operations represent statement forms, and two such expressions can be shown to be equal using the above axioms if and only if the corresponding statement forms are logically equivalent. The two-element Boolean algebra is also used for circuit design in electrical engineering; here 0 and 1 represent the two different states of one bit in a digital circuit, typically high and low voltage. Circuits are described by expressions containing variables, and two such expressions are equal for all values of the variables if and only if the corresponding circuits have the same input-output behavior. Furthermore, every possible input-output behavior can be modeled by a suitable Boolean expression. The two-element Boolean algebra is also important in the general theory of Boolean algebras, because an equation involving several variables is generally true in all Boolean algebras if and only if it is true in the two-element Boolean algebra (which can always be checked by a trivial brute force algorithm). This can for example be used to show that the following laws (Consensus theorems) are generally valid in all Boolean algebras: o (a b) (¬a c) (b c) ≡ (a b) (¬a c) o (a b) (¬a c) (b c) ≡ (a b) (¬a c) Starting with the propositional calculus with κ sentence symbols, form the Lindenbaum algebra (that is, the set of sentences in the propositional calculus modulo tautology). This construction yields a Boolean algebra. It is in fact the free Boolean algebra on κ generators. A truth assignment in propositional calculus is then a Boolean algebra homomorphism from this algebra to {0,1}. The power set (set of all subsets) of any given nonempty set S forms a Boolean algebra with the two operations := (union) and := ∩ (intersection). The smallest element 0 is the empty set and the largest element 1 is the set S itself. The set of all subsets of S that are either finite or cofinite is a Boolean algebra. For any natural number n, the set of all positive divisors of n forms a distributive lattice if we write a ≤ b for a | b. This lattice is a Boolean algebra if and only if n is square-free. The smallest element 0 of this Boolean algebra is the natural number 1; the largest element 1 of this Boolean algebra is the natural number n. Other examples of Boolean algebras arise from topological spaces: if X is a topological space, then the collection of all subsets of X which are both open and closed forms a Boolean algebra with the operations := (union) and := ∩ (intersection). If R is an arbitrary ring and we define the set of central idempotents by A = { e R : e2 = e, ex = xe, x R } then the set A becomes a Boolean algebra with the operations e f := e + f − ef and e f := ef. Certain Lindenbaum–Tarski algebras.

Order theoretic properties

Boolean lattice of subsets Like any lattice, a Boolean algebra (A, defining a ≤ b precisely when a = a

,

) gives rise to a partially ordered set (A, ≤) by

b

(which is also equivalent to b = a

b).

In fact one can also define a Boolean algebra to be a distributive lattice (A, ≤) (considered as a partially ordered set) with least element 0 and greatest element 1, within which every element x has a complement ¬x such that x

¬x = 0 and x

¬x = 1

Here and are used to denote the infimum (meet) and supremum (join) of two elements. Again, if complements in the above sense exist, then they are uniquely determined. The algebraic and the order theoretic perspective can usually be used interchangeably and both are of great use to import results and concepts from both universal algebra and order theory. In many practical examples an ordering relation, conjunction, disjunction, and negation are all naturally available, so that it is straightforward to exploit this relationship.

Principle of duality One can also apply general insights from duality in order theory to Boolean algebras. Especially, the order dual of every Boolean algebra, or, equivalently, the algebra obtained by exchanging and , is also a Boolean algebra. In general, any law valid for Boolean algebras can be transformed into another valid, dual law by exchanging 0 with 1, with , and ≤ with ≥.

Other notation The operators of Boolean algebra may be represented in various ways. Often they are simply written as AND, OR and NOT. In describing circuits, NAND (NOT AND), NOR (NOT OR) and XOR (eXclusive OR) may also be used. Mathematicians, engineers, and programmers often use + for OR and · for AND (since in some ways those operations are analogous to addition and multiplication in other algebraic structures and this notation makes it very easy to get sum of products form for people who are familiar with normal algebra) and represent NOT by a line drawn above the expression being negated. Sometimes, the symbol ~ or ! is used for NOT. Here we use another common notation with “meet” for AND, “join” for NOT.

for OR, and ¬

Homomorphisms and isomorphisms A homomorphism between the Boolean algebras A and B is a function f : A → B such that for all a, b in A: f(a b) = f(a) f(a b) = f(a) f(0) = 0 f(1) = 1

f(b) f(b)

It then follows that f(¬a) = ¬f(a) for all a in A as well. The class of all Boolean algebras, together with this notion of morphism, forms a category. An isomorphism from A to B is a homomorphism from A to B which is bijective. The inverse of an isomorphism is also an isomorphism, and we call the two Boolean algebras A and B isomorphic. From the standpoint of Boolean algebra theory, they cannot be distinguished; they differ only in the notation of their elements.

Boolean rings, ideals and filters Every Boolean algebra (A, , ) gives rise to a ring (A, +, *) by defining a + b = (a ¬b) (b ¬a) (this operation is called “symmetric difference” in the case of sets and XOR in the case of logic) and a * b = a b. The zero element of this ring coincides with the 0 of the Boolean algebra; the multiplicative identity element of the ring is the 1 of the Boolean algebra. This ring has the property that a * a = a for all a in A; rings with this property are called Boolean rings. Conversely, if a Boolean ring A is given, we can turn it into a Boolean algebra by defining x y = x + y + xy and x y = xy. Since these two operations are inverses of each other, we can say that every Boolean ring arises from a Boolean algebra, and vice versa. Furthermore, a map f : A → B is a homomorphism of Boolean algebras if and only if it is a homomorphism of Boolean rings. The categories of Boolean rings and Boolean algebras are equivalent.

An ideal of the Boolean algebra A is a subset I such that for all x, y in I we have x y in I and for all a in A we have a x in I. This notion of ideal coincides with the notion of ring ideal in the Boolean ring A. An ideal I of A is called prime if I ≠ A and if a b in I always implies a in I or b in I. An ideal I of A is called maximal if I ≠ A and if the only ideal properly containing I is A itself. These notions coincide with ring theoretic ones of prime ideal and maximal ideal in the Boolean ring A. The dual of an ideal is a filter. A filter of the Boolean algebra A is a subset p such that for all x, y in p we have x y in p and for all a in A if a x = a then a in p.

Representing Boolean algebras It can be shown that every finite Boolean algebra is isomorphic to the Boolean algebra of all subsets of a finite set. Therefore, the number of elements of every finite Boolean algebra is a power of two. Stone’s celebrated representation theorem for Boolean algebras states that every Boolean algebra A is isomorphic to the Boolean algebra of all closed-open sets in some (compact totally disconnected Hausdorff) topological space.

Axiomatics for Boolean algebras Let the unary functional symbol n be read as ‘complement’. In 1933, the American mathematician Edward Vermilye Huntington (1874–1952) set out the following elegant axiomatization for Boolean algebra: 1. Commutativity: x + y = y + x. 2. Associativity: (x + y) + z = x + (y + z). 3. Huntington equation: n(n(x) + y) + n(n(x) + n(y)) = x. Herbert Robbins immediately asked: If the Huntington equation is replaced with its dual, to wit: 4. Robbins Equation: n(n(x + y) + n(x + n(y))) = x, do (1), (2), and (4) form a basis for Boolean algebra? Calling (1), (2), and (4) a Robbins algebra, the question then becomes: Is every Robbins algebra a Boolean algebra? This question remained open for decades, and became a favorite question of Alfred Tarski and his students. In 1996, William McCune at Argonne National Laboratory, building on earlier work by Larry Wos, Steve Winker, and Bob Veroff, answered Robbins’s question in the affirmative: Every Robbins algebra is a Boolean algebra. Crucial to McCune’s proof was the automated reasoning program EQP he designed. For a simplification of McCune’s proof, see Dahn (1998).

History The term “Boolean algebra” honors George Boole (1815–1864), a self-educated English mathematician. The algebraic system of logic he formulated in his 1854 monograph The Laws of Thought differs from that described above in some important respects. For example, conjunction and disjunction in Boole were not a dual pair of operations. Boolean algebra emerged in the 1860s, in papers written by William Jevons and Charles Peirce. To the 1890 Vorlesungen of Ernst Schröder we owe the first systematic presentation of Boolean algebra and distributive lattices. The first extensive treatment of Boolean algebra in English is A. N. Whitehead’s 1898 Universal Algebra. Boolean algebra as an axiomatic algebraic structure in the modern axiomatic sense begins with a 1904 paper by Edward Vermilye Huntington. Boolean algebra came of age as serious mathematics with the work of Marshall Stone in the 1930s, and with Garrett Birkhoff’s 1940 Lattice Theory. In the 1960s, Paul Cohen, Dana Scott, and others found deep new results in mathematical logic and axiomatic set theory using offshoots of Boolean algebra, namely forcing and Boolean-valued models.

Fuzzy electronics Fuzzy electronics is an electronic technology that uses fuzzy logic, instead of the twovalue logic more commonly used in digital electronics. It has a wide range applications, including control systems and artificial intelligence.

Logic analyzer

A HP 1615A Logic Analyzer (from 1980)showing a timing diagram.

A Agilent 16801A Logic Analyzer (from 2006)showing a timing diagram with imported scope signals. A logic analyzer displays signals in a digital circuit that are too fast to be observed by a human being and presents it to a user so that the user can more easily check correct operation of the digital system. Logic analyzers are typically used for capturing data in systems that have too many channels to be examined with an oscilloscope. Software running on the logic analyzer can convert the captured data into timing diagrams, protocol decodes, state machine traces, assembly, or correlate assembly with source-level software. Current analyzers are either mainframes, which consist of a chassis containing the display, controls, control computer, and multiple slots into which the actual data capturing hardware is installed, or standalone units which integrate everything into a single package, with options installed at the factory. Recent mainframe models include the Agilent 16900 and Tek TLA7000, and recent standalone models include the Agilent 16800-series and Tek TLA5000. Agilent and Tektronix make up over 95% of the industry’s revenue.

Operation A logic analyzer can trigger on a complicated sequence of digital events, and then capture a large amount of digital data from the system under test (SUT). The best logic analyzers behave like software debuggers by showing the flow of the computer program and decoding protocols to show messages and violations.

When logic analyzers first came into use, it was common to attach several hundred “clips” to a digital system. Later, specialized connectors came into use. The evolution of logic analyzer probes has led to a common footprint that multiple vendors support, which provides added freedom to end users. Since 2004, connectorless technology, known as Soft Touch, has become popular. These probes provide a durable, reliable mechanical and electrical connection between the probe and the circuit board with less than 0.7 pF loading per signal. Once the probes are connected, the user programs the analyzer with the names of each signal, and can group several signals into groups for easier manipulation. Next, a capture mode is chosen, either timing mode, where the input signals are sampled at regular intervals based on an internal or external clock source, or state mode, where one or more of the signals are defined as “clocks,” and data is taken on the rising or falling edges of these clocks, optionally using other signals to qualify these clocks. After the mode is chosen, a trigger condition must be set. A trigger condition can range from simple (such as triggering on a rising or falling edge of a single signal), to the very complex (such as configuring the analyzer to decode the higher levels of the TCP/IP stack and triggering on a certain HTTP packet). At this point, the user sets the analyzer to “run” mode, either triggering once, or repeatedly triggering. Once the data is captured, it can be displayed several ways, from the simple (showing waveforms or state listings) to the complex (showing decoded Ethernet protocol traffic). The analyzer can also operate in a “compare” mode, where it compares each captured data set to a previously recorded data set, and stopping triggering when this data set is either matched or not. This is useful for long-term empirical testing. Recent analyzers can even be set to email a copy of the test data to the engineer on a successful trigger.

Uses Many digital designs, including those of ICs, are simulated to detect defects before the unit is constructed. The simulation usually provides logic analysis displays. Often, complex discrete logic is verified by simulating inputs and testing outputs using boundary scan. Logic analyzers can uncover hardware defects that are not found in simulation. These problems are typically too difficult to model in simulation, or too time consuming to simulate and often cross multiple clock domains. Field-programmable gate arrays have become a common measurement point for logic analyzers.

Logic gate A logic gate performs a logical operation on one or more logic inputs and produces a single logic output. The logic normally performed is Boolean logic and is most commonly found in digital circuits. Logic gates are primarily implemented electronically using diodes or transistors, but can also be constructed using electromagnetic relays, fluidics, optical or even mechanical elements.

Logic levels A Boolean logical input or output always takes one of two logic levels. These logic levels can go by many names including: on / off, high (H) / low (L), one (1) / zero (0), true (T) / false (F), positive / negative, positive / ground, open circuit / close circuit, potential difference / no difference. For consistency, the names 1 and 0 will be used below.

Logic gates A logic gate takes one or more logic-level inputs and produces a single logic-level output. Because the output is also a logic level, an output of one logic gate can connect to the input of one or more other logic gates. Two outputs cannot be connected together, however, as they may be attempting to produce different logic values. In electronic logic gates, this would cause a short circuit. In electronic logic, a logic level is represented by a certain voltage (which depends on the type of electronic logic in use). Each logic gate requires power so that it can source and sink currents to achieve the correct output voltage. In logic circuit diagrams the power is not shown, but in a full electronic schematic, power connections are required.

Background The simplest form of electronic logic is diode logic. This allows AND and OR gates to be built, but not inverters, and so is an incomplete form of logic. To build a complete logic system, valves or transistors can be used. The simplest family of logic gates using bipolar transistors is called resistor-transistor logic, or RTL. Unlike diode logic gates, RTL gates can be cascaded indefinitely to produce more complex logic functions. These gates were used in early integrated circuits. For higher speed, the resistors used in RTL were replaced by diodes, leading to diode-transistor logic, or DTL. It was then discovered that one transistor could do the job of two diodes in the space of one diode, so transistortransistor logic, or TTL, was created. In some types of chip, to reduce size and power consumption still further, the bipolar transistors were replaced with complementary fieldeffect transistors (MOSFETs), resulting in complementary metal-oxide-semiconductor (CMOS) logic.

For small-scale logic, designers now use prefabricated logic gates from families of devices such as the TTL 7400 series invented by Texas Instruments and the CMOS 4000 series invented by RCA, and their more recent descendants. These devices usually contain transistors with multiple emitters, used to implement the AND function, which are not available as separate components. Increasingly, these fixed-function logic gates are being replaced by programmable logic devices, which allow designers to pack a huge number of mixed logic gates into a single integrated circuit. The field-programmable nature of programmable logic devices such as FPGAs has removed the ‘hard’ property of hardware; it is now possible to change the logic design of a hardware system by reprogramming some of its components, thus allowing the features or function of a hardware implementation of a logic system to be changed. Electronic logic gates differ significantly from their relay-and-switch equivalents. They are much faster, consume much less power, and are much smaller (all by a factor of a million or more in most cases). Also, there is a fundamental structural difference. The switch circuit creates a continuous metallic path for current to flow (in either direction) between its input and its output. The semiconductor logic gate, on the other hand, acts as a high-gain voltage amplifier, which sinks a tiny current at its input and produces a lowimpedance voltage at its output. It is not possible for current to flow between the output and the input of a semiconductor logic gate. Another important advantage of standardised semiconductor logic gates, such as the 7400 and 4000 families, is that they are cascadable. This means that the output of one gate can be wired to the inputs of one or several other gates, and so on ad infinitum, enabling the construction of circuits of arbitrary complexity without requiring the designer to understand the internal workings of the gates. In practice, the output of one gate can only drive a finite number of inputs to other gates, a number called the ‘fanout limit’, but this limit is rarely reached in the newer CMOS logic circuits, as compared to TTL circuits. Also, there is always a delay, called the ‘propagation delay’, from a change in input of a gate to the corresponding change in its output. When gates are cascaded, the total propagation delay is approximately the sum of the individual delays, an effect which can become a problem in high-speed circuits.

Electronic logic levels The two logic levels in binary logic circuits are represented by two voltage ranges, “low” and “high”. Each technology has its own requirements for the voltages used to represent the two logic levels, to ensure that the output of any device can reliably drive the input of the next device. Usually, two non-overlapping voltage ranges, one for each level, are defined. The difference between the high and low levels ranges from 0.7 volts in Emitter coupled logic to around 28 volts in relay logic.

Logic gates and hardware NAND and NOR logic gates are the two pillars of logic, in that all other types of Boolean logic gates (i.e., AND, OR, NOT, XOR, XNOR) can be created from a suitable network of just NAND or just NOR gate(s). They can be built from relays or transistors, or any other technology that can create an inverter and a two-input AND or OR gate. These functions can be seen in the table below. OR, AND, NAND, NOR gates may have more than two inputs. All gates have exactly one output. OR

Any high input will drive the output high

NOR

Any high input will drive the output low

AND

Any low input will drive the output low

NAND Any low input will drive the output high XOR

Only 1 high input will drive the output high

XNOR Only 1 high input will drive the output low Logic gates are a vital part of many digital circuits, and as such, every kind is available as an IC. For examples, see the 4000 series of CMOS logic chips.

Symbols There are two sets of symbols in common use, both now defined by ANSI/IEEE Std 911984 and its supplement ANSI/IEEE Std 91a-1991. The “distinctive shape” set, based on traditional schematics, is used for simple drawings and is quicker to draw by hand. It is sometimes unofficially described as “military”, reflecting its origin if not its modern usage. The “rectangular shape” set, based on IEC 60617-12, has rectangular outlines for all types of gate, and allows representation of a much wider range of devices than is possible with the traditional symbols. The IEC’s system has been adopted by other standards, such as EN 60617-12:1999 in Europe and BS EN 60617-12:1999 in the United Kingdom. Type

Distinctive shape

Rectangular shape INPUT OUTPUT

AND

A

B A AND B

0

0

0

0

1

0

1

0

0

1

1

1

INPUT OUTPUT A B A OR B OR

0

0

0

0

1

1

1

0

1

1

1

1

INPUT OUTPUT A NOT A NOT

0

1

1

0

In electronics a NOT gate is more commonly called an inverter. The circle on the symbol is called a bubble, and is generally used in circuit diagrams to indicate an inverted input or output. INPUT OUTPUT A B A NAND B NAND

0

0

1

0

1

1

1

0

1

1

1

0

INPUT OUTPUT A B A NOR B NOR

0

0

1

0

1

0

1

0

0

1

1

0

In practice, the cheapest gate to manufacture is usually the NAND gate. Additionally, Charles Peirce showed that NAND gates alone (as well as NOR gates alone) can be used to reproduce all the other logic gates. Symbolically, a NAND gate can also be shown using the OR shape with bubbles on its inputs, and a NOR gate can be shown as an AND gate with bubbles on its inputs. This reflects the equivalency due to De Morgans law, but it also allows a diagram to be read more easily, or a circuit to be mapped onto available physical gates in packages easily, since any circuit node that has bubbles at both ends can be replaced by a simple bubbleless connection and a suitable change of gate. If the NAND is drawn as OR with input bubbles, and a NOR as AND with input bubbles, this gate substitution occurs automatically in the diagram (effectively, bubbles “cancel”). This is commonly seen in real logic diagrams - thus the reader must not get into the habit of associating the shapes

exclusively as OR or AND shapes, but also take into account the bubbles at both inputs and outputs in order to determine the “true” logic function indicated. Two more gates are the exclusive-OR or XOR function and its inverse, exclusive-NOR or XNOR. The two input Exclusive-OR is true only when the two input values are different, false if they are equal, regardless of the value. If there are more than two inputs, the gate generates a true at its output if the number of trues at its input is odd (). In practice, these gates are built from combinations of simpler logic gates. INPUT OUTPUT A B A XOR B XOR

0

0

0

0

1

1

1

0

1

1

1

0

INPUT OUTPUT A B A XNOR B XNOR

0

0

1

0

1

0

1

0

0

1

1

1

The 7400 chip, containing four NANDs. The two additional contacts supply power (+5 V) and connect the ground.

DeMorgan equivalent symbols By use of De Morgan’s theorem, an AND gate can be turned into an OR gate by inverting the sense of the logic at its inputs and outputs. This leads to a separate set of symbols with inverted inputs and the opposite core symbol. These symbols can make circuit diagrams for circuits using active low signals much clearer and help to show accidental connection of an active high output to an active low input or vice-versa.

Storage of bits Related to the concept of logic gates (and also built from them) is the idea of storing a bit of information. The gates discussed up to here cannot store a value: when the inputs change, the outputs immediately react. It is possible to make a storage element either through a capacitor (which stores charge due to its physical properties) or by feedback. Connecting the output of a gate to the input causes it to be put through the logic again, and choosing the feedback correctly allows it to be preserved or modified through the use of other inputs. A set of gates arranged in this fashion is known as a “latch”, and more complicated designs that utilise clocks (signals that oscillate with a known period) and change only on the rising edge are called edge-triggered “flip-flops”. The combination of multiple flip-flops in parallel, to store a multiple-bit value, is known as a register. These registers or capacitor-based circuits are known as computer memory. They vary in performance, based on factors of speed, complexity, and reliability of storage, and many different types of designs are used based on the application.

Three-state logic gates Three-state, or 3-state, logic gates have three states of the output: high (H), low (L) and high-impedance (Z). The high-impedance state plays no role in the logic, which remains strictly binary. These devices are used on buses to allow multiple chips to send data. A group of three-states driving a line with a suitable control circuit is basically equivalent to a multiplexer, which may be physically distributed over separate devices or plug-in cards. ‘Tri-state’, a widely-used synonym of ‘three-state’, is a trademark of the National Semiconductor Corporation.

Miscellaneous Logic circuits include such devices as multiplexers, registers, ALUs, and computer memory, all the way up through complete microprocessors which can contain more than a 100 million gates. In practice, the gates are made from field effect transistors (FETs), particularly metal-oxide-semiconductor FETs (MOSFETs). In reversible logic, Toffoli gates are used.

History and development The earliest logic gates were made mechanically. Charles Babbage, around 1837, devised the Analytical Engine. His logic gates relied on mechanical gearing to perform operations. Electromagnetic relays were later used for logic gates. In 1891, Almon Strowger patented a device containing a logic gate switch circuit (U.S. Patent 0447918). Strowger’s patent was not in widespread use until the 1920s. Starting in 1898, Nikola Tesla filed for patents of devices containing logic gate circuits (see List of Tesla patents). Eventually, vacuum tubes replaced relays for logic operations. Lee De Forest’s

modification, in 1907, of the Fleming valve can be used as AND logic gate. Claude E. Shannon introduced the use of Boolean algebra in the analysis and design of switching circuits in 1937. 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. Active research is taking place in molecular logic gates.

Common Basic Logic ICs CMOS TTL Function 4001 7402 Quad two-input NOR gate 4011 7400 Quad two-input NAND gate 4049 7404 Hex NOT gate (inverting buffer) 4070 7486 Quad two-Input XOR gate 4071 7432 Quad two-input OR gate 4077 74266 Quad two-input XNOR gate 4081 7408 Quad two-input AND gate For more CMOS logic ICs, including gates with more than two inputs, see 4000 series.

Glitch

Glitch City, a Pokémon programming error that creates a jumble of pixels. A glitch is a short-lived fault in a system. The term is particularly common in the computing and electronics industries, and in circuit bending, as well as among players of video games, although it is applied to all types of systems including human organizations. The term derives from the German glitschen, meaning ‘to slip.’ In electronics, a glitch is an electrical pulse of short duration that is usually the result of a fault or design error, particularly in a digital circuit. For example, many electronic components such as flip-flops are triggered by a pulse that must not be shorter than a specified minimum duration, otherwise the component may malfunction. A pulse shorter than the specified minimum is called a glitch. A related concept is the runt pulse, a pulse whose amplitude is smaller than the minimum level specified for correct operation, and a spike, a short pulse similar to glitch but often caused by ringing or crosstalk.

In video games, a glitch is a term used by players to indicate a bug or programming error of some sort. It may refer to either a helpful or harmful error, but never an intended behavior. A programming error that makes the game freeze is often referred to as a glitch, as is an error that, for example, gives the player 100 lives in a manner clearly not intended by the game’s programming. The occurrence of some glitches can be replicated deliberately by doing a series of certain tasks in a specific order; the Minus World glitch in Super Mario Bros. is a simple example. Sometimes the game’s code may be modified to create interesting glitches. For example, in the game Impossible Creatures, which focuses on combining 2 animals, making a combined animal “combinable” can result in 3 or 4-animal combinations. The practice of exploiting glitches in video games is known as “glitching.” For example, in an online game someone may use an error in the map to get an advantage. This is sometimes considered cheating, but sometimes just considered part of the game. It is often against a game’s TOS (Terms of Service) and will be punished if discovered. Sometimes glitches will be mistaken for hidden features. In the arcade version of Mortal Kombat, a rare glitch occasionally caused two characters to be mixed together. Most often, these were ninja characters, resulting in a semi-red ninja character with the name “ERMAC” (short for “error machine”). Upon discovering this, many players believed they had uncovered a secret character, when in fact they had only uncovered a programming bug. Due to the rumors surrounding the glitch, Midway did eventually include a red ninja character named Ermac as an official character in Ultimate Mortal Kombat 3, and he has subsequently appeared in other Mortal Kombat games, becoming an instant fan favorite.

Ringing Electricity In electrical circuits, ringing is an unwanted oscillation of a voltage or current. It is caused when an electrical pulse causes the parasitic capacitances and inductances in the circuit (i.e. those that are not part of the design, but just by-products of the materials used to construct the circuit) to resonate at their characteristic frequency. Ringing artifacts are also present in square waves. Ringing is undesirable because it causes extra current to flow, thereby wasting energy and causing extra heating of the components; it can cause unwanted electromagnetic radiation to be emitted; and it may cause unwanted triggering of bistable elements in digital circuits.

Programmable logic device A programmable logic device or PLD is an electronic component used to build digital circuits. Unlike a logic gate, which has a fixed function, a PLD has an undefined function at the time of manufacture. Before the PLD can be used in a circuit it must be programmed. It is impossible to discuss PLD technology without mentioning some of the companies involved in its development. However, it is not the purpose of this article to list all manufacturers of PLDs. Inclusion or omission of a particular company from this article is intended as neither a recommendation nor a criticism.

Using a ROM as a PLD Before PLDs were invented, read-only memory (ROM) chips were used to create arbitrary combinatorial logic functions of a number of inputs. Consider a ROM with m inputs (the address lines) and n outputs (the data lines). When used as a memory, the ROM contains 2m words of n bits each. Now imagine that the inputs are driven not by an m-bit address, but by m independent logic signals. Theoretically, there are 2m possible Boolean functions of these m signals, but the structure of the ROM allows just n of these functions to be produced at the output pins. The ROM therefore becomes equivalent to n separate logic circuits, each of which generates a chosen function of the m inputs. The advantage of using a ROM in this way is that any conceivable function of the m inputs can be made to appear at any of the n outputs, making this the most generalpurpose combinatorial logic device available. Also, PROMs (programmable ROMs), EPROMs (ultraviolet-erasable PROMs) and EEPROMs (electrically erasable PROMs) are available that can be programmed using a standard PROM programmer without requiring specialised hardware or software. However, there are several disadvantages:

• • • •

they are usually much slower than dedicated logic circuits, they cannot necessarily provide safe “covers” for asynchronous logic transitions, they consume more power, and because only a small fraction of their capacity is used in any one application, they often make an inefficient use of space.

Stand alone they cannot be used for sequential logic, because they contain no flip-flops. An external TTL register was often used for sequential designs such as state machines. Common EPROMs, for example the 2716, are still sometimes used in this way by hobby circuit designers, who often have some laying around. This use is sometimes called a ‘poor man’s PAL’.

Early programmable logic In 1970, Texas Instruments developed a mask-programmable IC based on the IBM readonly associative memory or ROAM. This device, the TMS2000, was programmed by altering the metal layer during the production of the IC. The TMS2000 had up to 17 inputs and 18 outputs with 8 JK flip flop for memory. TI coined the term Programmable Logic Array for this device. In 1973 National Semiconductor introduced a mask-programmable PLA device (DM7575) with 14 inputs and 8 outputs with no memory registers. This was more popular than the TI part but cost of making the metal mask limited its use. The device is significant because it was the basis for the field programmable logic array produced by Signetics in 1975, the 82S100. (Intersil actually beat Signetics to market but poor yield doomed their part.) In 1971, General Electric Company (GE) was developing a programmable logic device based on the new PROM technology. This experimental device improved on IBM’s ROAM by allowing multilevel logic. Intel had just introduced the floating-gate UV erasable PROM so the researcher at GE incorporated that technology. The GE device was the first erasable PLD ever developed, predating the Altera EPLD by over a decade. GE obtained several early patents on programmable logic devices. In 1974 GE entered into an agreement with Monolithic Memories to develop a maskprogrammable logic device incorporating the GE innovations. The device was named the ‘Programmable Associative Logic Array’ or PALA. The MMI 5760 was completed in 1976 and could implement multilevel or sequential circuits of over 100 gates. The device was supported by a GE design environment where Boolean equations would be converted to mask patterns for configuring the device. The part was never brought to market.

PAL Programmable array logic

MMI introduced a breakthrough device in 1978, the Programmable Array Logic or PAL. The architecture was simpler than that of Signetics FPLA because it omitted the programmable OR array. This made the parts faster, smaller and cheaper. They were available in 20 pin 300 mil DIP packages while the FPLAs came in 28 pin 600 mil packages. The PAL Handbook demystified the design process. The PALASM design software (PAL Assembler) converted the engineers’ Boolean equations into the fuse pattern required to program the part. The PAL devices were soon second-sourced by National Semiconductor, Texas Instruments and AMD. After MMI succeeded with the 20-pin PAL parts, AMD introduced the 24-pin 22V10 PAL with additional features. After buying out MMI (1987), AMD spun off a consolidated operation as Vantis, and that business was acquired by Lattice Semiconductor in 1999.

GALs Generic array logic

Lattice GAL 16V8 and 20V8 An innovation of the PAL was the generic array logic device, or GAL, invented by Lattice Semiconductor in 1985. This device has the same logical properties as the PAL but can be erased and reprogrammed. The GAL is very useful in the prototyping stage of a design, when any bugs in the logic can be corrected by reprogramming. GALs are programmed and reprogrammed using a PAL programmer, or by using the in-circuit programming technique on supporting chips. A similar device called a PEEL (programmable electrically erasable logic) was introduced by the International CMOS Technology (ICT) corporation.

CPLDs CPLD

PALs and GALs are available only in small sizes, equivalent to a few hundred logic gates. For bigger logic circuits, complex PLDs or CPLDs can be used. These contain the equivalent of several PALs linked by programmable interconnections, all in one

integrated circuit. CPLDs can replace thousands, or even hundreds of thousands, of logic gates. Some CPLDs are programmed using a PAL programmer, but this method becomes inconvenient for devices with hundreds of pins. A second method of programming is to solder the device to its printed circuit board, then feed it with a serial data stream from a personal computer. The CPLD contains a circuit that decodes the data stream and configures the CPLD to perform its specified logic function. Each manufacturer has a proprietary name for this programming system. For example, Lattice Semiconductor calls it “in-system programming”. However, these proprietary systems are beginning to give way to a standard from the Joint Test Action Group (JTAG).

FPGAs Field-programmable gate array

While PALs were busy developing into GALs and CPLDs (all discussed above), a separate stream of development was happening. This type of device is based on gatearray technology and is called the field-programmable gate array (FPGA). Early examples of FPGAs are the 82s100 array, and 82S105 sequencer, by Signetics, introduced in the late 1970s. The 82S100 was an array of AND terms. The 82S105 also had Flip Flop functions. FPGAs use a grid of logic gates, similar to that of an ordinary gate array, but the programming is done by the customer, not by the manufacturer. The term “fieldprogrammable” may be obscure to some, but “field” is just an engineering term for the world outside the factory, where customers live. FPGAs are usually programmed after being soldered down to the circuit board, in a manner similar to that of larger CPLDs. In most larger FPGAs the configuration is volatile, and must be re-loaded into the device whenever power is applied or different functionality is required. Configuration is typically stored in a configuration PROM or EEPROM. EEPROM versions may be in-system programmable (typically via JTAG). FPGAs and CPLDs are often equally good choices for a particular task. Sometimes the decision is more an economic one than a technical one, or may depend on the engineer’s personal preference or experience.

Other types of PLDs There is much interest in reconfigurable systems at present. These are microprocessor circuits that contain some fixed functions and other functions that can be altered by code running on the processor. Designing self-altering systems will require engineers to learn new methods, and will probably require new software tools to be developed.

PLDs are being sold now that contain a microprocessor with a fixed function (the socalled core) surrounded by programmable logic. These devices allow the designer to concentrate on adding new features to his design without having to worry about making the microprocessor work.

How PLDs retain their configuration A PLD is a combination of a logic device and a memory device. The memory is used to store the pattern that was given to the chip during programming. Most of the methods for storing data in an integrated circuit have been adapted for use in PLDs. These include: • • • •

Silicon antifuses SRAM EPROM or EEPROM cells Flash memory

Silicon antifuses are the storage elements used in the PAL, the first type of PLD. (dubious assertion—see talk page) These are connections that are made by applying a voltage across a modified area of silicon inside the chip. They are called antifuses because they work in the opposite way to normal fuses, which begin life as connections until they are broken by an electric current. SRAM, or static RAM, is a volatile type of memory, meaning that its contents are lost each time the power is switched off. SRAM-based PLDs therefore have to be programmed every time the circuit is switched on. This is usually done automatically by another part of the circuit. An EPROM cell is a MOS (metal-oxide-semiconductor) transistor that can be switched on by trapping an electric charge permanently on its gate electrode. This is done by a PAL programmer. The charge remains for many years and can only be removed by exposing the chip to strong ultraviolet light in a device called an EPROM eraser. Flash memory is non-volatile, retaining its contents even when the power is switched off. It can be erased and reprogrammed as required. This makes it useful for PLD memory. As of 2005, most CPLDs are electrically programmable and erasable, and non-volatile. This is because they are too small to justify the inconvenience of programming internal SRAM cells every time they start up, and EPROM cells are more expensive due to their ceramic package with a quartz window.

PLD programming languages Many PAL programming devices accept input in a standard file format, commonly referred to as ‘JEDEC files’. To assist the creation of such files, special computer programs have been created, called logic compilers. They are analogous to software

compilers. The languages used as source code for logic compilers are called hardware description languages, or HDLs. PALASM and ABEL are frequently used for low-complexity devices, while Verilog and VHDL are popular higher-level description languages for more complex devices. The more limited ABEL is often used for historical reasons, but for new designs VHDL is more popular, even for low-complexity designs.

Reconfigurable computing Reconfigurable computing is computer processing with highly flexible computing fabrics. The principal difference when compared to using ordinary microprocessors is the ability to make substantial changes to the data path itself in addition to the control flow.

History and characteristics The concept of reconfigurable computing has been around since the 1960s, when Gerald Estrin’s landmark paper proposed the concept of a computer consisting of a standard processor and an array of “reconfigurable” hardware. The main processor would control the behavior of the reconfigurable hardware. The reconfigurable hardware would then be tailored to perform a specific task, such as image processing or pattern matching, as quickly as a dedicated piece of hardware. Once the task was done, the hardware could be adjusted to do some other task. This resulted in a hybrid computer structure combining the flexibility of software with the speed of hardware; unfortunately this idea was way ahead of its time in terms of electronic technology. In the last decade there was a renaissance in this area of research with many proposed reconfigurable architectures developed both in industry and academia such as, Matrix, Garp, Elixent, XPP, Silicon Hive, Montium, Pleiades, Morphosys, PiCoGA. Such designs were feasible due to the relentless progress of silicon technology that allowed complex designs to be implemented on a single chip. The world’s first commercial reconfigurable computer, the Algotronix CHS2X4, was completed in 1991. It was not a commercial success, but it was promising enough that Xilinx Inc. (the inventor of the FieldProgrammable Gate Array (FPGA)) purchased the technology and hired the Algotronix staff . Currently there are a number of vendors with commercially available reconfigurable computers aimed at the high performance computing market; including Cray, SGI and SRC Computers, Inc. . Cray supercomputer company (not affiliated with SRC Computers) acquired OctigaBay and its reconfigurable computing platform, which Cray marketed as the XD1 until recently. SGI sells the RASC platform with their Altix series of supercomputers. SRC Computers, Inc. has developed a family of reconfigurable computers based on their IMPLICIT+EXPLICIT architecture and MAP processor. All of the offerings are hybrid “Estrin” computers with traditional microprocessors coupled to user-programmable FPGAs. The systems can be used as traditional cluster computers without using the FPGAs (in fact, the FPGAs are an option on the XD1 and the SGI RASC). The XD1 and SGI FPGA reconfiguration is accomplished either via the traditional Hardware Description Languages (HDL) or using a high level languages like the graphical tool Starbridge Viva or C-like languages like for example Handel-C from Celoxica, Impulse-C from Impulse Accelerated Technologies or Mitrion-C from Mitrionics. According to the XD1 programming guide, “Development of the raw FPGA logic file is a complex process that requires specialized knowledge and tools.”

SRC has developed a “Carte” compiler that takes an existing high-level languages like C or Fortran, and with a few modifications, compiles them for execution on both the FPGA and microprocessor. According to SRC literature, “...application algorithms are written in a high-level language such as C or Fortran. Carte extracts the maximum parallelism from the code and generates pipelined hardware logic that is instantiated in the MAP. It also generates all the required interface code to manage the movement of data to and from the MAP and to coordinate the microprocessor with the logic running in the MAP.” (note that SRC also allows a traditional HDL flow to be used). The XD1 communicates between microprocessor and FPGA over its RapidArray interconnection network. The SRC systems communicate via the SNAP memory interface, and/or the (optional) Hi-Bar switch. Clearly, classifications of reconfigurable architectures are still being developed and refined as new architectures are developed; no unifying taxonomy has been suggested to date. However, several recurring parameters can be used to classify these systems.

Granularity The granularity of the reconfigurable logic is defined as the size of the smallest functional unit (CLB) that is addressed by the mapping tools. Low granularity, which can also be known as fine-grained, often implies a greater flexibility when implementing algorithms into the hardware. However, there is a penalty associated with this in terms of increased power, area and delay due to greater quantity of routing required per computation. Finegrained architectures work at the bit-level manipulation level; whilst coarse grained processing elements (rDPU) are better optimised for standard data path applications. One of the drawbacks of coarse grained architectures are that they tend to lose some of their utilisation and performance if they need to perform smaller computations than their granularity provides, for example for a one bit add on a four bit wide functional unit would waste three bits. This problem can be solved by having a coarse grain array (rDPA) and a FPGA on the same chip. Coarse-grained architectures (rDPA) are intended for the implementation for algorithms needing word-width data paths (rDPU). As their functional blocks are optimized for large computations they will perform these operations more quickly and power efficiently than a smaller set of functional units connected together with some interconnect, this is due to the connecting wires are shorter, meaning less wire capacitance and hence faster and lower power designs. A potential undesirable consequence of having larger computational blocks is that when the size of operands may not match the algorithm an inefficient utilisation of resources can result. Often the type of applications to be run are known in advance allowing the logic, memory and routing resources to be tailored (for instance, see KressArray Xplorer) to enhance the performance of the device whilst still providing a certain level of flexibility for future adaptation. Examples of this are domain specific arrays aimed at gaining better performance in terms of power, area, throughput than their more generic finer grained FPGA cousins by reducing their flexibility.

Rate of reconfiguration Configuration of these reconfigurable systems can happen at deployment time, between execution phases or during execution. In a typical reconfigurable system, a bit stream is used to program the device at deployment time. Fine grained systems by their own nature requires greater configuration time than more coarse-grained architectures due to more elements needing to be addressed and programmed. Therefore more coarse-grained architectures gain from potential lower energy requirements, as less information is transferred and utilised. Intuitively, the slower the rate of reconfiguration the smaller the energy consumption as the associated energy cost of reconfiguration are amortised over a longer period of time. Partial reconfiguration aims to allow part of the device to be reprogrammed while another part is still performing active computation. Partial reconfiguration allows smaller reconfigurable bit streams thus not wasting energy on transmitting redundant information in the bit stream. Compression of the bit stream is possible but careful analysis is to be carried out to insure that the energy saved by using smaller bit streams is not outweighed by the computation needed to decompress the data.

Host coupling Often the reconfigurable array is used as a processing accelerator attached to a host processor. The level of coupling determines the type of data transfers, latency, power, throughput and overheads involved when utilising the reconfigurable logic. Some of the most intuitive designs use a peripheral bus to provide a coprocessor like arrangement for the reconfigurable array. However, there have also been implementations where the reconfigurable fabric is much closer to the processor, some are even implemented into the data path, utilising the processor registers. The job of the host processor is to perform the control functions, configure the logic, schedule data and to provide external interfacing.

Routing/interconnects The flexibility in reconfigurable devices mainly comes from their routing interconnect. One style of interconnect made popular by FPGAs vendors, Xilinx and Altera are the island style layout, where blocks are arranged in an array with vertical and horizontal routing. A layout with inadequate routing may suffer from poor flexibility and resource utilisation, therefore providing limited performance. If too much interconnect is provided this requires more transistors than necessary and thus more silicon area, longer wires and more power consumption.

Tool flow Generally, tools for configurable computing systems can be split up in two parts, CAD tools for reconfigurable array and compilation tools for CPU. The front-end compiler is an integrated tool, and will generate a structural hardware representation that is input of hardware design flow. Hardware design flow for reconfigurable architecture can be classified by the approach adopted by three main stages of design process: technology

mapping, placement algorithm and routing algorithm. The software frameworks differ in the level of the programming language. Some types of reconfigurable computers are microcoded processors where the microcode is stored in RAM or EEPROM, and changeable on reboot or on the fly. This could be done with the AMD 2900 series bit slice processors (on reboot) and later with FPGAs (on the fly). Some dataflow processors are implemented using reconfigurable computing.

A Paradigm Shift The fundamental model of the Reconfigurable Computing Machine paradigm, the datastream-based anti machine is well illustrated by the differences to other machine paradigms having been introduced earlier, as shown by Nick Tredennick’s following classification scheme of computing paradigms:

Nick Tredennick’s Paradigm Classification Scheme

Early Historic Computers:

Programming Source

Resources fixed

none

Algorithms fixed

none

von Neumann Computer:

Programming Source

Resources fixed

none

Algorithms variable

Software (instruction streams)

Reconfigurable Computing Systems:

Programming Source

Resources variable

Configware (configuration)

Algorithms variable

Flowware (data streams)

The fundamental model of a Reconfigurable Computing Machine, the data-stream-based anti machine (also called Xputer), is the counterpart of the instruction-stream-based von Neumann machine paradigm. This is illustrated by a simple reconfigurable system (not dynamically reconfigurable), which has no instruction fetch at run time. The reconfiguration (before run time) can be considered as a kind of super instruction fetch. An anti machine does not have a program counter. The anti machine has data counters instead, since it is data-stream-driven. Here the definition of the term data streams is adopted from the systolic array scene, which defines, at which time which data item has to enter or leave which port, here of the reconfigurable system, which may be finegrained (e. g. using FPGAs) or coarse-grained, or a mixture of both. The systolic array scene, originally (early 80ies) mainly mathematicians, only defined one half of the anti machine: the data path: the Systolic Array (also see Super Systolic Array). But they did not define nor model the data sequencer methodology, considering that this is not their job to to take care where the data streams come from or end up. The data sequencing part of the anti machine is modeled as distributed memory, preferrably on chip, which consists of auto-sequencing memory blocks ( ASM blocks). Each ASM block has a sequencer including a data counter. An example is the Generic Address Generator ( GAG), which is a generalization of the DMA.

Terminology FPGAs, rDPAs, and any other device whose functionality can be changed during execution. The reconfigurable device may Reconfigurable Device have a fine-grained architecture like FPGAs, or a coarsegrained architecture like rDPAs.

Bitstream

Common Memory

Compile/Compilation

Cocompilation Configware

Configuration Cycle accurate simulation Emulation/Simulation Flowware

High Performance Computing (HPC)

Hybrid

On-chip memory

If in a hardware architecture both functionalities of processing elements and interconnections between them can be modified after fabrication time then it is a reconfigurable device or architecture. The file that configures the FPGA (has a .bit extension). The Bitstream gets loaded into an FPGA when ready for execution. Obtained after place and route, final result of the place and route phase. A.k.a Shared Memory. Should refer to memory on a multiFPGA board to which all the FPGAs can communicate data to DIRECTLY and is external to the FPGA. Code segments/pieces that are meant to run on the microprocessor. This could include simulation/emulation runs, which are executing on the processor. Alternatively, this word could be used to encompass the processes of synthesis, and place and route for reconfigurable devices. Compilation for generating Software Code and Configware Code, including automatic Software / Configware partitioning. Source programs for Configuration. Being of structural nature, Configware is the counterpart of Software (being of procedural nature). Should refer to the bitstream currently loaded on an FPGA. When used loosely, it could also refer to the components/chipset making up a board or reconfigurable machine, which should not be the case. Simulation that exactly mimics the clock on the FPGA, records changes in data based on the rising/falling edge of the clock. A.k.a Simulation, Modeling. Process of mimicking the behavior of the FPGA hardware on a processor based system. in addition to configware the second programming source needed for data scheduling. A.k.a High Performance Embedded Computing, Parallel Computing. Parallel computing based on an array of microprocessors or (Reconfigurable HPC): FPGAs or rDPAs characterized by large run-times and computing resources, parallel implementations of algorithms. In this context the term “hybrid” stands for a symbiosis of procedural (instruction-stream-based) computing and reconfigurable computing (no instruction fetch at run time). A.k.a Block RAM, Cache. This term should refer to memory that is available on-chip within a single chip (whether it be BlkRAM Slices or SRAM slices). The term cache should be reserved purely for memory directly attached to processors on

Aggregate On-chip memory

Local Memory

Reconfigurable Computing

Reconfiguration System Memory/Host Memory

Reconfigurable Computer

the system/host side. Refers to total on-chip memory available for multi-FPGA systems. A.k.a DRAM, SRAM, QDR, DDR SRAMs, ZBT RAM. This term should been used purely to describe memory that is external to an FPGA or rDPA, is attached directly to an FPGA, and is not attached to any other FPGA or device on the board or outside of it. It should be called “On-chip memory” when located on board of the same chip with the FPGA or rDPA. A computing paradigm employing reconfigurable devices such as FPGAs or rDPAs to process data. A different bitstream can be loaded during the execution of a program or to run a different program on the fly. Estrin architecture reconfigurable computers include conventional von Neuman processors as main or control processors, and typically use one or more reconfigurable devices as co-processors. Newer FPGA-based architectures eliminate the need for a host processor by providing mechanisms to configure the device on boot from flash, and to directly support essential interfaces to memory and network resources via a bus configured in the device fabric. Providing a stable and stateful computational platform within a reconfigurable device requires, however, partial reconfigurability - that is, the ability to reconfigure only that portion of the device that implements an application, while leaving unchanged the portion of the device that implements the platform - the memory and network interfaces, the device drivers, and so forth. Current FPGA devices allow partial reconfiguration, but implementing designs that can effectively use this feature is still a tough exercise in system-on-chip design. Configuration, programming, re-programming (also see Configware) Should refer to memory on the microprocessor motherboard. You could also refer to it as host memory, NOT cache memory. An Estrin architecture reconfigurable computer typically pairs a comventional microprocessor host computer with a reconfigurable co-processor, such as an FPGA or rDPA board. The co-processor can be reconfigured to perform different computations during execution of a host computer program by loading appropriate bitstreams. Newer FPGA-based architectures eliminate the need for a host processor by providing mechanisms to configure the device on boot from flash, and to directly support essential interfaces to memory and network resources via a bus configured in the device

Synthesis

Place and Route

fabric. A fairly recent market has developed for low-power reconfigurable system-on-chip (SoC) devices that manufacturers can customize to their product applications, which are typically portable consumer media electronics. The devices typically incorporate one or more von Neuman processors, and provide mechanisms to extend the processor(s) instruction set and/or interface the device to other subsystems in the product. While these devices are technically “reconfigurable processors,” they are really designed to be configured once during production, or to be reconfigured as part of a field upgrade, but not to be reconfigured on-the-fly. Process of creating a netlist from a circuit description described using HDLs (Hardware Description Language), HLLs (High Level Language), GUI (Graphical User Interfaces) Process of converting a netlist into physically mapped and placed components on the FPGA or rDPA, ending in the creation of a bitstream.

Analogue electronics Analogue electronics are those electronic systems with a continuously variable signal. They differ from digital electronics in that they are not quantised. The term “analogue” originally described the relationship between a signal and a voltage or current that represented the signal.

Description Analogue is usually thought of in an electrical context, but mechanical, pneumatic, hydraulic, and other systems may also use analogue signals. The word “analogue” implies an analogy between cause and effect, voltage in and voltage out, current in and current out, sound in and sound out. Analogue circuits do not involve quantisation of information into digital format. Whatever the original quantity, whether sound, light, pressure, temperature, or an exceeded limit, the source signal information being handled by the circuit remains continuous from end to end.

Analogue signals An analogue signal uses some property of the medium to convey the signal’s information. For example, an aneroid barometer uses angular position as the signal to convey pressure information. Electrically, the property most commonly used is voltage followed closely by frequency, current, and charge. Any information may be conveyed by an analogue signal, often such a signal is a measured response to changes in physical phenomena, such as sound, light, temperature, position, or pressure, and is achieved using a transducer. They can take any value from a given range, and each unique signal value represents different information. Simply put, any change in the signal is meaningful, and each level of the signal represents a different and unique level of the phenomenon that it represents. For example, suppose the signal is being used to represent temperature, with one Volt representing one degree Celsius. In such a system 10 Volts would represent 10 degrees, and 10.1 Volts would represent 10.1 degrees. A similar digital circuit may only represent temperature to the nearest degree, so that 10.0 Volts and 10.1 Volts would both represent exactly 10 degrees. In an analogue sound recording, the variation in pressure of a sound striking a microphone creates a corresponding variation in the current passing through it or voltage across it. An increase in the volume or amplitude of the sound causes the fluctuation of the current or voltage to increase proportionally while keeping the same waveform or shape and electrical analogue.

Disadvantage of analogue signalling The primary disadvantage of analogue signalling is that any system has noise, that is random disturbances or variations in it. As the signal is copied and re-copied, or transmitted over long distances, these random variations become dominant and lead to signal degradation. Electrically these losses are lessened by shielding, good connections, and several cable types such as coax and twisted pair and using low noise amplifiers. The effects of random noise can make signal loss and distortion impossible to recover, since amplifying the signal to recover attenuated parts of the signal often generates more noise and amplifies the noise as well. Another method of conveying an analogue signal is to use modulation. In this, some base signal (e.g., a sinusoidal carrier wave) has one of its properties altered: amplitude modulation involves altering the amplitude of a sinusoidal voltage waveform by the source information, frequency modulation changes the frequency. Other techniques, such as changing the phase of the base signal do also work.

Analogue and Digital Electronics Since the information is encoded very differently in analogue and digital electronics, the way they process a signal is consequently very different. However, most operations that can be performed with an analogue signal can also be performed with a digital signal but in a different way. The first electronic devices invented and mass produced were analogue. However, as time passed, digital circuits have become predominant in electronics. It is important to note that analogue and digital devices are the same, the only difference is the way they represent and process information. The same basic components can be used for analogue or digital circuits. The main differences between analogue and digital electronics are listed below: Noise: Because the way information is encoded in analogue circuits, they are much more susceptible to noise than digital circuits, since a small change in the signal can represent a significant change in the information present in the signal and can cause the information present to be lost, corrupted or otherwise made useless. In digital electronics, because the information is quantized, as long as the signal stays inside a range of values, it represents the same information. This is one of the main reasons that digital electronic circuits are predominant. In fact, digital circuits use this principle to regenerate the signal at each logic gate, lessening or removing noise. Precision: A number of factors affect how precise a signal is, mainly the noise present in the original signal and the noise added by processing. See Signal to Noise Ratio. In digital electronics it is much easier to have high precision signals than in analogue

electronics, because of the way information is represented and how noise affects digital and analogue signals. Speed: This is where analogue electronics really outshines digital electronics. Analogue circuits are several times faster than their digital counterparts. Depending on the operation, analogue circuits can be several hundreds or hundreds of thousands of times faster than digital circuits. This is because information in digital circuits is represented by bits, while in analogue electronics it is represented by a property of the signal itself. For example, transmitting a value digitally may require sending 64 bits in succession. The same signal in analogue electronics could easily be represented by a voltage, and transmitting that voltage takes the same time to transmit one bit, so the analogue signal in this case is at least 64 times faster than digital. Bandwidth: Simply put, bandwidth is the amount of information a given circuit can cope with. Again, analogue circuits have much more bandwidth than digital, and can process/transmit more information in the same time. Design Difficulty: Digital systems are much easier and smaller to design than comparable analogue circuits. This is one of the main reasons why digital systems are more common than analogue. An analogue circuit must be designed by hand, and the process is much less automated than for digital systems. Also, because the smaller the integrated circuit (chip) the cheaper it is, and digital systems are much smaller than analogue, digital is cheaper to manufacture.

Future of Analogue Electronics The field of analogue electronics nowadays deals with high speed, high performance devices that need the unique advantages provided by analogue circuits. Also, digital circuits are an abstraction of analogue circuits, but remain analogue circuits. As technology progresses and transistors get smaller and smaller, it becomes more and more important when designing digital circuits to account for effects usually present only in analogue circuits, requiring expertise in analogue circuits. The range of applications of analogue circuits will probably continue to reduce, being replaced by digital circuits because of their smaller size, cheaper cost and easier design. Analogue circuits will never cease to exist, but will continue to exist as a speciality field for high performance circuits, or as a high performance part of a digital chip, as integrated circuits with analogue and digital circuits in the same substrate become more popular.

Artificial intelligence

Honda’s humanoid robot Artificial intelligence (AI) is a branch of computer science and engineering that deals with intelligent behavior, learning, and adaptation in machines. Research in AI is concerned with producing machines to automate tasks requiring intelligent behavior. Examples include control, planning and scheduling, the ability to answer diagnostic and consumer questions, handwriting, speech, and facial recognition. As such, it has become an engineering discipline, focused on providing solutions to real life problems, software applications, traditional strategy games like computer chess and other video games. For topics relating specifically to full human-like intelligence, see Strong AI.

Schools of thought AI divides roughly into two schools of thought: Conventional AI and Computational Intelligence (CI), also sometimes referred to as Synthetic Intelligence to highlight the differences. Conventional AI mostly involves methods now classified as machine learning, characterized by formalism and statistical analysis. This is also known as symbolic AI, logical AI, neat AI and Good Old Fashioned Artificial Intelligence (GOFAI). (Also see semantics.) Methods include: • • • •

Expert systems: apply reasoning capabilities to reach a conclusion. An expert system can process large amounts of known information and provide conclusions based on them. Case based reasoning Bayesian networks Behavior based AI: a modular method of building AI systems by hand.

Computational Intelligence involves iterative development or learning (e.g. parameter tuning e.g. in connectionist systems). Learning is based on empirical data and is associated with non-symbolic AI, scruffy AI and soft computing. Methods mainly include: • • •

Neural networks: systems with very strong pattern recognition capabilities. Fuzzy systems: techniques for reasoning under uncertainty, have been widely used in modern industrial and consumer product control systems. Evolutionary computation: applies biologically inspired concepts such as populations, mutation and survival of the fittest to generate increasingly better solutions to the problem. These methods most notably divide into evolutionary algorithms (e.g. genetic algorithms) and swarm intelligence (e.g. ant algorithms).

With hybrid intelligent systems attempts are made to combine these two groups. Expert inference rules can be generated through neural network or production rules from statistical learning such as in ACT-R. It is thought that the human brain uses multiple techniques to both formulate and cross-check results. Thus, systems integration is seen as promising and perhaps necessary for true AI.

History History of artificial intelligence

Early in the 17th century, René Descartes envisioned the bodies of animals as complex but reducible machines, thus formulating the mechanistic theory, also known as the “clockwork paradigm”. Wilhelm Schickard created the first mechanical digital calculating machine in 1623, followed by machines of Blaise Pascal (1643) and Gottfried Wilhelm von Leibniz (1671), who also invented the binary system. In the 19th century, Charles Babbage and Ada Lovelace worked on programmable mechanical calculating machines. Bertrand Russell and Alfred North Whitehead published Principia Mathematica in 19101913, which revolutionized formal logic. In 1931 Kurt Gödel showed that sufficiently powerful consistent formal systems contain true theorems unprovable by any theoremproving AI that is systematically deriving all possible theorems from the axioms. In 1941 Konrad Zuse built the first working program-controlled computers. Warren McCulloch and Walter Pitts published A Logical Calculus of the Ideas Immanent in Nervous Activity (1943), laying the foundations for neural networks. Norbert Wiener’s Cybernetics or Control and Communication in the Animal and the Machine (MIT Press, 1948) popularizes the term “cybernetics”.

1950s The 1950s were a period of active efforts in AI. In 1950, Alan Turing introduced the “Turing test” as a way of operationalizing a test of intelligent behavior. The first working AI programs were written in 1951 to run on the Ferranti Mark I machine of the

University of Manchester: a draughts-playing program written by Christopher Strachey and a chess-playing program written by Dietrich Prinz. John McCarthy coined the term “artificial intelligence” at the first conference devoted to the subject, in 1956. He also invented the Lisp programming language. Joseph Weizenbaum built ELIZA, a chatterbot implementing Rogerian psychotherapy. The birthdate of AI is generally considered to be July 1956 at the Dartmouth Conference, where many of these people met and exchanged ideas. At the same time, John von Neumann, who had been hired by the RAND Corporation, developed the game theory, which would prove invaluable in the progress of AI research.

1960s-1970s During the 1960s and 1970s, Joel Moses demonstrated the power of symbolic reasoning for integration problems in the Macsyma program, the first successful knowledge-based program in mathematics. Leonard Uhr and Charles Vossler published “A Pattern Recognition Program That Generates, Evaluates, and Adjusts Its Own Operators” in 1963, which described one of the first machine learning programs that could adaptively acquire and modify features and thereby overcome the limitations of simple perceptrons of Rosenblatt. Marvin Minsky and Seymour Papert published Perceptrons, which demonstrated the limits of simple neural nets. Alain Colmerauer developed the Prolog computer language. Ted Shortliffe demonstrated the power of rule-based systems for knowledge representation and inference in medical diagnosis and therapy in what is sometimes called the first expert system. Hans Moravec developed the first computercontrolled vehicle to autonomously negotiate cluttered obstacle courses.

1980s In the 1980s, neural networks became widely used due to the backpropagation algorithm, first described by Paul Werbos in 1974. The team of Ernst Dickmanns built the first robot cars, driving up to 55 mph on empty streets. The 1990s marked major achievements in many areas of AI and demonstrations of various applications. In 1995, one of Dickmanns’ robot cars drove more than 1000 miles in traffic at up to 110 mph. Deep Blue, a chess-playing computer, beat Garry Kasparov in a famous six-game match in 1997. DARPA stated that the costs saved by implementing AI methods for scheduling units in the first Persian Gulf War have repaid the US government’s entire investment in AI research since the 1950s. Honda built the first prototypes of humanoid robots like the one depicted above.

1990s & Turn of the Century During the 1990s and 2000s AI has become very influenced by probability theory and statistics. Bayesian networks are the focus of this movement, providing links to more rigorous topics in statistics and engineering such as Markov models and Kalman filters, and bridging the divide between ‘neat’ and ‘scruffy’ approaches. The last few years have also seen a big interest in game theory applied to AI decision making. This new school of

AI is sometimes called ‘machine learning’. After the September 11, 2001 attacks there has been much renewed interest and funding for threat-detection AI systems, including machine vision research and data-mining. However despite the hype, excitment about Bayesian AI is perhaps now fading again as successful Bayesian models have only appeared for tiny statistical tasks (such as finding principal components probabalistically) and appear to be intractable for general perception and decision making.

Challenge & Prize The DARPA Grand Challenge is a race for a $2 million prize where cars drive themselves across several hundred miles of challenging desert terrain without any communication with humans, using GPS, computers and a sophisticated array of sensors. In 2005 the winning vehicles completed all 132 miles of the course in just under 7 hours. Unfortunately, there will be no prize money awarded to the winners of the 2007 race due to a re-allocation of DARPA funds through a bill signed by George W. Bush in which Congress switched the authority from DARPA to its boss, the Director of Defense Engineering and Research.

AI in Philosophy Philosophy of artificial intelligence

The strong AI vs. weak AI debate (“can a man-made artifact be conscious?”) is still a hot topic amongst AI philosophers. This involves philosophy of mind and the mind-body problem. Most notably Roger Penrose in his book The Emperor’s New Mind and John Searle with his “Chinese room” thought experiment argue that true consciousness cannot be achieved by formal logic systems, while Douglas Hofstadter in Gödel, Escher, Bach and Daniel Dennett in Consciousness Explained argue in favour of functionalism. In many strong AI supporters’ opinion, artificial consciousness is considered as the holy grail of artificial intelligence. Edsger Dijkstra famously opined that the debate had little importance: “The question of whether a computer can think is no more interesting than the question of whether a submarine can swim.” Epistemology, the study of knowledge, also makes contact with AI, as engineers find themselves debating similar questions to philosophers about how best to represent and use knowledge and information. (e.g. semantic networks).

AI in business Banks use artificial intelligence systems to organize operations, invest in stocks, and manage properties. In August 2001, robots beat humans in a simulated financial trading competition (BBC News, 2001).A medical clinic can use artificial intelligence systems to organize bed schedules, make a staff rotation, and to provide medical information. Many

practical applications are dependent on artificial neural networks — networks that pattern their organization in mimicry of a brain’s neurons, which have been found to excel in pattern recognition. Financial institutions have long used such systems to detect charges or claims outside of the norm, flagging these for human investigation. Neural networks are also being widely deployed in homeland security, speech and text recognition, medical diagnosis (such as in Concept Processing technology in EMR software), data mining, and e-mail spam filtering. Robots have also become common in many industries. They are often given jobs that are considered dangerous to humans. Robots have also proven effective in jobs that are very repetitive which may lead to mistakes or accidents due to a lapse in concentration, and other jobs which humans may find degrading. General Motors uses around 16,000 robots for tasks such as painting, welding, and assembly. Japan is the leader in using robots in the world. In 1995, 700,000 robots were in use worldwide; over 500,000 of which were from Japan (Encarta, 2006).

AI in fiction In science fiction AI — almost always strong AI — is commonly portrayed as an upcoming power trying to overthrow human authority as in HAL 9000, Skynet, Colossus and The Matrix or as service humanoids like C-3PO, Marvin, Data, KITT and KARR, the Bicentennial Man, the Mechas in A.I., Cortana from the Halo series or Sonny in I, Robot. A notable exception is Mike in Robert A. Heinlein’s The Moon Is a Harsh Mistress: a supercomputer that becomes aware and aids in a local revolution. The inevitability of world domination by out-of-control AI is also argued by some fiction writers like Kevin Warwick. In works such as the Japanese manga Ghost in the Shell, the existence of intelligent machines questions the definition of life as organisms rather than a broader category of autonomous entities, establishing a notional concept of systemic intelligence. See list of fictional computers and list of fictional robots and androids. Some fiction writers, such as Vernor Vinge and Ray Kurzweil, have also speculated that the advent of strong AI is likely to cause abrupt and dramatic societal change. The period of abrupt change is sometimes referred to as “the Singularity”. Author Frank Herbert explored the idea of a time when mankind might ban clever machines entirely. His Dune series makes mention of a rebellion called the Butlerian Jihad in which mankind defeats the smart machines of the future and then imposes a death penalty against any who would again create thinking machines. Often quoted from the Orange Catholic Bible, “Thou shalt not make a machine in the likeness of a human mind.”

Control system A control system is a device or set of devices to manage, command, direct or regulate the behavior of other devices or systems. There are two common classes of control systems, with many variations and combinations: logic or sequential controls, and feedback or linear controls. There is also fuzzy logic, which attempts to combine some of the design simplicity of logic with the utility of linear control. Some devices or systems are inherently not controllable. The term “control system” may be applied to the essentially manual controls that allow an operator to, for example, close and open a hydraulic press, where the logic requires that it cannot be moved unless safety guards are in place. An automatic sequential control system may trigger a series of mechanical actuators in the correct sequence to perform a task. For example various electric and pneumatic transducers may fold and glue a cardboard box, fill it with product and then seal it in an automatic packaging machine. In the case of linear feedback systems, a control loop, including sensors, control algorithms and actuators, is arranged in such a fashion as to try to regulate a variable at a setpoint or reference value. An example of this may increase the fuel supply to a furnace when a measured temperature drops. PID controllers are common and effective in cases such as this . Control systems that include some sensing of the results they are trying to achieve are making use of feedback and so can, to some extent, adapt to varying circumstances. Open-loop control systems do not directly make use of feedback, but run only in pre-arranged ways.

Logic controls Pure logic controls were historically implemented by electricians with networks of relays, and designed with a notation called ladder logic. Nowadays, most such systems are constructed with programmable logic controllers. Logic controllers may respond to switches, light sensors, pressure switches etc and cause the machinery to perform some operation. Logic systems are used to sequence mechanical operations in many applications. Examples include elevators, washing machines and other systems with interrelated stop-go operations. Logic systems are quite easy to design, and can handle very complex operations. Some aspects of logic system design make use of Boolean logic.

Linear controls Linear controls use negative feedback to keep some desired process within an acceptable range. For example, a thermostat is a simple negative feedback control: when the temperature goes below a threshold, a heater is switched on. Another example is a refrigerator, where the mechanism is switched on when the internal temperature rises. However, a simple logic control like a home thermostat doesn’t respond smoothly. In industrial furnaces, it’s often better to turn the fuel valve open proportionally to the coldness of the furnace. This avoids sudden shocks to the furnace and applies heat more smoothly. A simple proportional feedback system can either be slow to respond, or can tend to oscillate. In the furnace example, the valve may open and shut indefinitely in a cycle as the furnace heats, and then overruns the target temperature. This is bad because it stresses the system. In a furnace, the constantly turning valve will quickly wear out. More expensively, the fluctuating temperature causes expansion and contraction all through the furnace, causing unnecessary, very expensive mechanical wear. Most systems have similar problems. If the sensitivity of such a simple proportional control system is reduced enough to prevent oscillation, the system responds much slower than it could under skillful manual control. To resolve this problem, the most common feedback control scheme has mathematical extensions to cope with the future and the past. This type of control is called a proportional-integral-derivative control, or PID control (pronounced pee-eye-dee). The derivative part is concerned with the rate-of-change of the error: If the measured variable is approaching the setpoint rapidly, then the actuator is backed off to allow it to coast to the required level; conversely if the measured value begins to fall away rapidly, extra effort is applied in proportion to that rapidity to try to maintain it. The integral term magnifies the effect of long-term steady-state errors, applying ever-increasing effort until these reduce to zero. When correctly tuned to the time-constants of the controlled system, a PID control loop can be surprisingly effective at maintaining effortless control. In many real cases, control system designers have to be concerned about practicalities like wearing out control machinery such as valves, by adjusting them too frequently. Therefore, control systems may have a “deadband,” a region around the current value in which no control action occurs. In commercial controls, the deadband is programmable. Another common technique is to filter the feedback loop. A filter may reduce the response of the system to undesirable frequencies, to help eliminate instability or oscillations. Most feedback systems will oscillate at just one frequency. By filtering out that frequency, one can use very “stiff” feedback and the system can be very responsive without shaking itself apart.

Some feedback controls operate through complex indirect effects. For example, in an airplane’s autopilot, the flight plan in the autopilot determines the desired numbers (where to move) that drive everything. The direction of the airplane is controlled by ailerons, elevators, rudders, etc. Each mechanical control has a differential equation that takes the desired movement in six different axes (roll, pitch, yaw, forward, right and down), and calculates the control’s position. Usually each input and output number is filtered for particular oscillations of the aircraft or the control part. Military aircraft can be designed so that the system can adjust to the loss of control surfaces when they are shot away. The most complex linear control systems developed to date are in oil refineries (model predictive control). The chemical reaction paths and control systems are normally designed together using specialized computer-aided-design software. When the automated control-system design techniques pioneered by oil refinery controls were applied to aircraft control systems, they caused a revolution, speeding design times by a hundred-fold or more. Now, the core codes of many modern aircraft autopilots are actually themselves coded by computer programs. Feedback loops can be combined and modified in many ways. Usually if a system has several measurements to be controlled, a feedback loop will be present for each of them.

Fuzzy logic Fuzzy logic is an attempt to get the easy design of logic controllers and yet control continuously-varying systems. Basically, a measurement in a fuzzy logic system can be partly true, that is if yes is 1 and no is 0, a fuzzy measurement can be between 0 and 1. The rules of the system are written in natural language and translated into fuzzy logic. For example, the design for a furnace would start with: “If the temperature is too high, reduce the fuel to the furnace. If the temperature is too low, increase the fuel to the furnace.” Measurements from the real world (such as the temperature of a furnace) are converted to values between 0 and 1 by seeing where they fall on a triangle. Usually the tip of the triangle is the maximum possible value which translates to “1.” Fuzzy logic then modifies Boolean logic to be arithmetical. Usually the “not” operation is “output = 1 - input,” the “and” operation is “output = input.1 multiplied by input.2,” and “or” is “output = 1 - ((1 - input.1) multiplied by (1 - input.2)).” The last step is to “defuzzify” an output. Basically, the fuzzy calculations make a value between zero and one. That number is used to select a value on a line whose slope and height converts the fuzzy value to a real-world output number. The number then controls real machinery.

If the triangles are defined correctly and rules are right the result can be a good control system. When a robust fuzzy design is reduced into a single, quick calculation, it begins to resemble a conventional feedback loop solution. For this reason, many control engineers think one should not bother with it. However, the fuzzy logic paradigm may provide scalability for large control systems where conventional methods become unwieldy or costly to derive. Fuzzy electronics is an electronic technology that uses fuzzy logic instead of the twovalue logic more commonly used in digital electronics.

How are these really made? Since modern small microcontrollers are so cheap (often less than $1 US), it’s very common to implement control systems, including feedback loops, with computers, often in an embedded system. The feedback controls are simulated by having the computer make periodic measurements and then calculating from this stream of measurements (see digital signal processing). Computers emulate logic devices by making measurements of switch inputs, calculating a logic function from these measurements and then sending the results out to electronicallycontrolled switches. Logic systems and feedback controllers are usually implemented with programmable logic controllers which are devices available from electrical supply houses. They include a little computer and a simplified system for programming. Most often they are programmed with personal computers. Logic controllers have also been constructed from relays, hydraulic and pneumatic devices, and electronics using both transistors and vacuum tubes (feedback controllers can also be constructed in this manner).

Control theory In engineering and mathematics, control theory deals with the behavior of dynamical systems. The desired output of a system is called the reference. When one or more output variables of a system need to follow a certain reference over time, a controller manipulates the inputs to a system to obtain the desired effect on the output of the system.

An example Consider an automobile’s cruise control, which is a device designed to maintain a constant vehicle speed. The output variable of the system is vehicle speed. The input variable is the engine’s torque output, which is regulated by the throttle. A simple way to implement cruise control is to lock the throttle position when the driver engages cruise control. However, on hilly terrain, the vehicle will slow down going uphill and accelerate going downhill. This type of controller is called an open-loop controller because there is no direct connection between the output of the system and its input. In a closed-loop control system, a feedback control monitors the vehicle’s speed and adjusts the throttle as necessary to maintain the desired speed. This feedback compensates for disturbances to the system, such as changes in slope of the ground or wind speed.

History Although control systems of various types date back to antiquity, a more formal analysis of the field began with a dynamics analysis of the centrifugal governor, conducted by the famous physicist J.C. Maxwell in 1868 entitled “On Governors.” This described and analyzed the phenomenon of “hunting” in which lags in the system can lead to overcompensation and unstable behavior. This caused a flurry of interest in the topic, which was followed up by Maxwell’s classmate, E.J. Routh, who generalized the results of Maxwell for the general class of linear systems. This result is called the RouthHurwitz Criterion. A notable application of dynamic control was in the area of manned flight. The Wright Brothers made their first successful test flights on December 17, 1903 and were distinguished by their ability to control their flights for substantial periods (more so than the ability to produce lift from an airfoil, which was known). Control of the airplane was necessary for safe flight. By World War II, control theory was an important part of fire control, guidance systems, and cybernetics. The Space Race to the Moon depended on accurate control of the spacecraft. But control theory is not only useful in technological applications, and is meeting an increasing use in fields such as economics and sociology.

For a list of active and historical figures who have made a significant contribution to control theory, see People in systems and control.

Classical control theory: the closed-loop controller To avoid the problems of the open-loop controller, control theory introduces feedback. A closed-loop controller uses feedback to control states or outputs of a dynamical system. Its name comes from the information path in the system: process inputs (e.g. voltage applied to a motor) have an effect on the process outputs (e.g. velocity or position of the motor), which is measured with sensors and processed by the controller; the result (the control signal) is used as input to the process, closing the loop. Closed-loop controllers have the following advantages over open-loop controllers: • • • • •

disturbance rejection (such as unmeasured friction in a motor) guaranteed performance even with model uncertainties, when the model structure does not match perfectly the real process and the model parameters are not exact unstable processes can be stabilized reduced sensitivity to parameter variations improved reference tracking performance

The only disadvantage of closed loop control system over open loop control is that the closed loop system reduces the overall gain of the system. To obtain good performance, closed-loop and open-loop are used simultaneously; open-loop improves set-point (the value desired for the output) tracking. The most popular closed-loop controller architecture, by far, is the PID controller. One example is a fuel injection system using an oxygen sensor to control the fuel/air mixture.

The output of the system y(t) is fed back to the reference value r(t), through the measurement performed by a sensor. The controller C then takes the difference between the reference and the output, the error e, to change the inputs u to the system under control P. This is shown in the figure. This kind of controller is a closed-loop controller or feedback controller. This is a so-called single-input-single-output (SISO) control system: example where one or more variables can contain more than one value (MIMO, i.e. Multi-Input-Multi-Output - for example when outputs to be controlled are two or more) are frequent. In such cases variables are represented through vectors instead of simple scalar values. For some distributed parameter systems the vectors may be infinite-dimensional (typically functions).

A simple feedback control loop If we assume the controller C and the plant P are linear and time-invariant (i.e.: elements of their transfer function C(s) and P(s) do not depend on time), we can analyze the system above by using the Laplace transform on the variables. This gives us the following relations:

Solving for Y(s) in terms of R(s), we obtain:

The term is referred to as the transfer function of the system. Where the numerator is the forward gain from r to y, and the denominator is one plus the loop gain of the feedback loop. If we can ensure , i.e. it has very great norm with each value of s, then Y(s) is approximately equal to R(s). This means we control the output by simply setting the reference.

Stability Stability (in control theory) often means that for any bounded input over any amount of time, the output will also be bounded. This is known as BIBO stability. If a system is BIBO stable then the output cannot “blow up” if the input remains finite. Mathematically, this means that for a causal linear continuous-time system to be stable all of the poles of its transfer function must •

lie in the closed left half of the complex plane if the Laplace transform is used (i.e. its real part is less than or equal to zero)

OR •

lie on or inside the unit circle if the Z-transform is used (i.e. its modulus is less than or equal to one)

In the two cases, if respectively the pole has a real part strictly smaller than zero or a modulus strictly smaller than one, we speak of asymptotic stability: the variables of an asymptotically stable control system always decrease from their initial value and do not show permanent oscillations, which are instead present if a pole has exactly a real part equal to zero (or a modulus equal to one). If a simply stable system response neither decays nor grows over time, and has no oscillations, it is referred to as marginally stable: in this case it has non-repeated poles along the vertical axis (i.e. their real and complex component is zero). Oscillations are present when poles with real part equal to zero have imaginary part not equal to zero. Difference between the two cases are not a contradiction. The Laplace transform is in Cartesian coordinates and the Z-transform is in circular coordinates and it can be shown that • •

the negative-real part in the Laplace domain can map onto the interior of the unit circle the positive-real part in the Laplace domain can map onto the exterior of the unit circle

If the system in question has an impulse response of x[n] = 0.5nu[n] and considering the Z-transform (see this example), it yields

which has a pole in z = 0.5 (zero imaginary part). This system is BIBO (asymptotically) stable since the pole is inside the unit circle. However, if the impulse response was x[n] = 1.5nu[n] then the Z-transform is

which has a pole at z = 1.5 and is not BIBO stable since the pole has a modulus strictly greater than one. Numerous tools exist for the analysis of the poles of a system. These include graphical systems like the root locus , Bode plots or the Nyquist plots.

Controllability and observability Controllability and observability are main issues in the analysis of a system before deciding the best control strategy to be applied. Controllability is related to the possibility of forcing the system into a particular state by using an appropriate control signal. If a state is not controllable, then no signal will ever be able to force the system to reach a level of controllability. Observability instead is related to the possibility of “observing”, through output measurements, the state of a system. If a state is not observable, the controller will never be able to correct the closed-loop behaviour if such a state is not desirable. From a geometrical point of view, if we look at the states of each variable of the system to be controlled, every “bad” state of these variables must be controllable and observable to ensure a good behaviour in the closed-loop system. That is, if one of the eigenvalues of the system is not both controllable and observable, this part of the dynamics will remain untouched in the closed-loop system. If such an eigenvalue is not stable, the dynamics of this eigenvalue will be present in the close-loop system which therefore will be unstable. Unobservable poles are not present in the transfer function realization of a state-space representation, which is why sometimes the latter is preferred in dynamical systems analysis. Solutions to problems of uncontrollable or unobservable system include adding actuators and sensors.

Control specifications Several different control strategies have been devised in the past years. These vary from extremely general ones (PID controller), to others devoted to very particular classes of systems (es. Robotics or Aircraft cruise control). A control problem can have several specifications. Stability, of course, is always present: the controller must ensure that the closed-loop system is stable: this both if the open-loop is stable or not. An inaccurate choice of the controller, indeed, can even worsen the stability properties of the open-loop system. This must normally be avoided. Sometimes it would be desired to obtain particular dynamics in the closed loop: i.e. that the poles have , where simply ask that Re[λ] < 0.

is a fixed value strictly greater than zero, instead of

Another typical specification is the rejection of a step disturbance: this can be easily obtained by including an integrator in the open-loop chain (i.e. directly before the system under control). Other classes of disturbances need different types of sub-systems to be included. Other “classical” control theory specifications regard the time-response of the closedloop system: these include the rise time (the time needed by the control system to reach the desired value after a perturbation), peak overshoot (the highest value reached by the response before reaching the desired value) and others (settling time, quarter-decay). Frequency domain specifications are usually related to robustness (see after). Modern performance assessments use some variation of integrated tracking error (IAE,ISA,CQI).

Model identification and robustness System identification

A control system must always have some robustness property. A robust controller is such that its properties do not change much if applied to a system slightly different from the mathematical one used for its synthesis. This specification is important: no real physical system truly behaves like the series of differential equations used to represent it in mathematical way. Sometimes a simpler mathematical model can be chosen in order to simplify calculations. Otherwise the true system dynamics can be so complicated that a complete model is impossible. System identification The process of determining the equations that govern the model’s dynamics is called system identification. This can be done off-line: for example, executing a series of measures from which to calculate an approximated mathematical model, typically its transfer function or matrix. Such identification from the output, however, cannot take account of unobservable dynamics. Sometimes the model is built directly starting from known physical equations: for example, in the case of a mass-spring-damper system we know that . Even assuming that a “complete” model is used in designing the controller, all the parameters included in these equations (called “nominal parameters”) are never known with absolute precision; the control system will have to behave correctly even when connected to physical system with true parameter values away from nominal. Some advanced control techniques include an “on-line” identification process (see later). The parameters of the model are calculated (“identified”) while the controller itself is running: in this way, if a drastic variation of the parameters ensues (for example, if the robot’s arm releases a weight), the controller will adjust itself consequently in order to ensure the correct performance.

Analysis Analysis of the robustness of a SISO control system can be performed in the frequency domain, considering the system’s transfer function and using Nyquist and Bode diagrams. Topics include Phase margin and Amplitude margin. For MIMO and, in general, more complicated control systems one must consider the theoretical results devised for each control technique (see next section): i.e., if particular robustness qualities are needed, the engineer must shift his attention to a control technique including them in its properties. Constraints A particular robustness issue is the requirement for a control system to perform properly in the presence of input and state constraints. In the physical world every signal is limited. It could happen that a controller will send control signals that cannot be followed by the physical system: for example, trying to rotate a valve at excessive speed. This can produce undesired behavior of the closed-loop system, or even break actuators or other subsystems. Specific control techniques are available to solve the problem: model predictive control (see later), and anti-wind up systems. The latter consists of an additional control block that ensures that the control signal never exceeds a given threshold.

Main control strategies Every control system must guarantee first the stability of the closed-loop behaviour. For linear systems, this can be obtained by directly placing the poles. Non-linear control systems use specific theories (normally based on Lyapunov’s Theory) to ensure stability without regard to the inner dynamics of the system. The possibility to fulfill different specifications varies from the model considered and the control strategy chosen. Here a summary list of the main control techniques is shown:

PID controllers PID controller

The so-called PID controller is probably the most-used feedback control design, being the simplest one. “PID” means Proportional-Integral-Derivative, referring to the three terms operating on the error signal to produce a control signal. If u(t) is the control signal sent to the system, y(t) is the measured output and r(t) is the desired output, and tracking error e(t) = r(t) − y(t), a PID controller has the general form

The desired closed loop dynamics is obtained by adjusting the three parameters KP, KI and KD, often iteratively by “tuning” and without specific knowledge of a plant model.

Stability can often be ensured using only the proportional term. The integral term permits the rejection of a step disturbance (often a striking specification in process control). The derivative term is used to provide damping or shaping of the response. PID controllers are the most well established class of control systems: however, they cannot be used in several more complicated cases, especially if MIMO systems are considered.

Direct pole placement State space (controls) For MIMO systems, pole placement can be performed mathematically using a State space representation of the open-loop system and calculating a feedback matrix assigning poles in the desired positions. In complicated systems this can require computer-assisted calculation capabilities, and cannot always ensure robustness. Furthermore, all system states are not in general measured and so observers must be included and incorporated in pole placement design.

Optimal control Optimal control

Optimal control is a particular control technique in which the control signal optimizes a certain “cost index”: for example, in the case of a satellite, the jet thrusts needed to bring it to desired trajectory that consume the least amount of fuel. Two optimal control design methods have been widely used in industrial applications, as it has been shown they can guarantee closed-loop stability. These are Model Predictive Control (MPC) and LinearQuadratic-Gaussian control (LQG). The first can more explicitly take into account constraints on the signals in the system, which is an important feature in many industrial processes. However, the “optimal control” structure in MPC is only a means to achieve such a result, as it does not optimize a true performance index of the closed-loop control system. Together with PID controllers, MPC systems are the most widely used control technique in process control. • • •

Model predictive control H infinity Coefficient diagram method

Adaptive control Adaptive control

Adaptive control uses on-line identification of the process parameters, or modification of controller gains, thereby obtaining strong robustness properties. Adaptive controls were applied for the first time in the Aerospace industry in the 1950s, and have found particular success in that field.

Non-linear control systems Non-linear control

Processes in industries like Robotics and the Aerospace industry typically have strong non-linear dynamics. In control theory it is sometimes possible to linearize such classes of systems and apply linear techniques: but in many cases it can be necessary to devise from scratch theories permitting control of non-linear systems. These normally take advantage of results based on Lyapunov’s theory. Differential geometry has been widely used as a tool for generalizing well-known linear control concepts to the non-linear case, as well as showing the subtleties that make it a more challenging problem.

Distributed control system This article, image, template or category should belong in one or more categories. Please categorize it so it may be associated with related articles, images, templates or categories. Thank you. Please remove this template after categorizing. This article has been tagged since November 2006.

A distributed control system (DCS) refers to a control system usually of a manufacturing system or process, in which the controller element is not central in location (like the brain) but are distributed throughout the system with each component sub-system under the control of one or more controllers. The entire system may be networked for communication and monitoring. Distributed control systems (DCS) are used in industrial and civil engineering applications to monitor and control distributed equipment with or without remote human intervention; the nomenclature for the former ‘manual control’ and the latter ‘automated control’. A DCS typically uses computers (usually custom designed processers) as controllers and use both proprietary interconnections and protocols for communication. Input & output modules form component parts of the DCS. The processor receives information from input modules and sends information to output modules. The input modules receive information from input instruments in the process (aka field) and output modules transmits to the output instruments in the field. Computer buses or electrical buses connect the processor and modules through multiplexer/demultiplexers. They also connect the distributed controllers with the central controller and finally to the HumanMachine Interface (HMI) or control consoles. See PAS. DCS is a very broad term that describes solutions across a large variety of industries, including: • •

Electrical power grids and electrical generation plants Environmental control systems

• • • •

Traffic signals Water management systems Refining and chemical plants Pharmaceutical manufacturing

The broad architecture of a solution involves either a direct connection to physical equipment such as switches, pumps and valves or connection via a secondary system such as a SCADA system. A DCS solution does not require operator intervention for its normal operation, but with the line between SCADA and DCS merging, systems claiming to offer DCS may actually permit operator interaction via a SCADA system. Distributed Control Systems (DCSs) are dedicated systems used to control manufacturing processes that are continuous or batch-oriented, such as oil refining, petrochemicals, central station power generation, pharmaceuticals, food & beverage manufacturing, cement production, steelmaking, and papermaking. DCSs are connected to sensors and actuators and use setpoint control to control the flow of material through the plant. The most common example is a setpoint control loop consisting of a pressure sensor, controller, and control valve. Pressure or flow measurements are transmitted to the controller, usually through the aid of a signal conditioning Input/Output (I/O) device. When the measured variable reaches a certain point, the controller instructs a valve or actuation device to open or close until the fluidic flow process reaches the desired setpoint. Large oil refineries have many thousands of I/O points and employ very large DCSs. Processes are not limited to fluidic flow through pipes, however, and can also include things like paper machines and their associated variable speed drives and motor control centers, cement kilns, mining operations and ore processing facilities, and many others. A typical DCS consists of functionally and/or geographically distributed digital controllers capable of executing from 1 to 256 or more regulatory control loops in one control box. The input/output devices (I/O) can be integral with the controller or located remotely via a field network. Today’s controllers have extensive computational capabilities and, in addition to proportional, integral, and derivative (PID) control, can generally perform logic and sequential control. DCSs may employ one or several workstations and can be configured at the workstation or by an off-line personal computer. Local communication is handled by a control network with transmission over twisted pair, coaxial, or fiber optic cable. A server and/or applications processor may be in-cluded in the system for extra computational, data collection, and reporting capability.

History The DCS was introduced in 1975. Both Honeywell and Japanese electrical engineering firm Yokogawa introduced their own independently produced DCSs at roughly the same

time, with the TDC 2000 and CENTUM systems, respectively. US-based Bristol also introduced their UCS 3000 universal controller in 1975. In 1980, Bailey (now part of ABB ) introduced the NETWORK 90 system. The DCS largely came about due to the increased availability of microcomputers and the proliferation of microprocessors in the world of process control. Computers had already been applied to process automation for some time in the form of Set Point Control, where process computers supervised clusters of analog controllers. The proliferation of microprocessors allowed suppliers to take this mode to the next step by deploying minicomputers in a supervisory role, controlling several digital loop controllers. A CRTbased workstation provided visibility into the process using text and crude character graphics. Availability of a fully functional graphical user interface was a long way away. Central to the DCS model was the inclusion of control function blocks, which were introduced by the Foxboro company. One of the first embodiments of object-oriented software, function blocks were self contained “blocks” of code that emulated analog hardware control components and performed tasks that were essential to process control, such as execution of PID algorithms. Function blocks continue to endure as the predominant method of control for DCS suppliers, and are supported by key technologies such as Foundation Fieldbus today. Digital communication between controllers and supervisory computers was one of the primary advantages of the DCS, and attention was duly focused on the networks, which provided the all-important lines of communication that, for process applications, had to incorporate specific functions such as determinism and redundancy. As a result, many suppliers embraced the IEEE 802.4 networking standard. This decision set the stage for the wave of migrations necessary when information technology moved into process automation and IEEE 802.3 rather than IEEE 802.4 prevailed as the control LAN. The Network Centric Era of the 1980s The DCS brought distributed intelligence to the plant and established the presence of computers and microprocessors in process control, but it still did not provide the reach and openness necessary to unify plant resource requirements. In many cases, the DCS was merely a digital replacement of the same functionality provided by analog controllers and a panelboard display. This was embodied in The Perdue Reference Model (PRM) that was developed to define Manufacturing Operations Management relationships. PRM later formed the basis for ISA95 standards activities today. In the 1980s, users began to look at DCSs as more than just basic process control. It was believed that if openness could be achieved and greater amounts of data could be shared throughout the enterprise that good things could be achieved, although few were sure what these benefits would be. The first attempts to increase the openness of DCSs resulted in the adoption of the predominant operating system of the day—UNIX. UNIX and its companion networking technology TCP-IP were developed by the Department of

Defense for openness, which was precisely the issue the process industries were looking to resolve. As a result suppliers also began to adopt Ethernet-based networks with their own proprietary protocol layers. The full TCP/IP standard was not implemented, but the use of Ethernet made it possible to implement the first instances of object management and global data access technology. The 1980s also witnessed the first PLCs integrated into the DCS infrastructure. Plant-wide historians also emerged to capitalize on the extended reach of automation systems. The first DCS supplier to adopt UNIX and Ethernet networking technologies was Foxboro, who introduced the I/A Series system in 1987. The Application Centric Era of the 1990s The drive toward openness in the 1980s gained momentum through the 1990s with the increased adoption of Commercial-Off-The-Shelf (COTS) components and IT standards. Probably the biggest transition undertaken during this time was the move from the UNIX operating system to the Windows environment. While the realm of the real time operating system (RTOS) for control applications remains dominated by real time commercial variants of UNIX or proprietary operating systems, everything above real-time control has made the transition to Windows. The invasion of Microsoft at the desktop and server layers resulted in the development of technologies such as OLE for Process Control (OPC), which is now a de facto industry connectivity standard. Internet technology also began to make its mark in automation and the DCS world, with most DCS HMI supporting Internet connectivity. The ‘90s were also known for the “Fieldbus Wars”, where rival organizations competed to define what would become the IEC fieldbus standard for digital communication with field instrumentation instead of 4-20 milliamp analog communications. The first fieldbus installations occurred in the 1990s. Towards the end of the decade, the technology began to develop significant momentum, with the market consolidated around Foundation Fieldbus and Profibus PA for process automation applications. Some suppliers built new systems from the ground up to maximize functionality with fieldbus, such as Emerson with the DeltaV control system. The impact of COTS, however, was most pronounced at the hardware layer. For years, the primary business of DCS suppliers had been the supply of large amounts of hardware, particularly I/O and controllers. The initial proliferation of DCSs required the installation of prodigious amounts of this hardware, most of it manufactured from the bottom up by DCS suppliers. Standard computer components from manufacturers such as Intel and Motorola, however, made it cost prohibitive for DCS suppliers to continue making their own components, workstations, and networking hardware. As the suppliers made the transition to COTS components, they also discovered that the hardware market was shrinking fast. COTS not only resulted in lower manufacturing costs for the supplier, but also steadily decreasing prices for the end users, who were also becoming increasingly vocal over what they perceived to be unduly high hardware costs.

Some suppliers that were previously stronger in the PLC business, such as Rockwell Automation and Siemens , were able to leverage their expertise in manufacturing control hardware to enter the DCS marketplace with cost effective offerings. To compound the issue, suppliers were also realizing that the hardware market was becoming saturated. The lifecycle of hardware components such as I/O and wiring is also typically in the range of 15 to over 20 years, making for a challenging replacement market. Many of the older systems that were installed in the 1970s and 1980s are still in use today, and there is a considerable installed base of systems in the market that are approaching the end of their useful life. Developed industrial economies in North America, Europe, and Japan already had many thousands of DCSs installed, and with few if any new plants being built, the market for new hardware was shifting rapidly to smaller, albeit faster growing regions such as China, Latin America, and Eastern Europe. Because of the shrinking hardware business, suppliers began to make the challenging transition from a hardware-based business model to one based on software and valueadded services. It is a transition that is still being made today. The applications portfolio offered by suppliers expanded considerably in the ‘90s to include areas such as production management, model-based control, real-time optimization, Plant Asset Management (PAM), Real Time Performance Management (RPM) tools, alarm management, and many others. To obtain the true value from these applications, however, often requires a considerable service content, which the suppliers also provide. DCS supplier services have also expanded in scope to the point where many suppliers can act as Main Automation Contractors (MACs), providing a single point of responsibility for all automation-related facets of a project.

Control engineering Control engineering is the engineering discipline that focuses on the mathematical modelling systems of a diverse nature, analysing their dynamic behaviour, and using control theory to create a controller that will cause the systems to behave in a desired manner.

Background Modern control engineering is closely related to electrical and computer engineering, as electronic circuits can often be easily described using control theory techniques. At many universities, control engineering courses are primarily taught by E&CE faculty members. Previous to modern electronics, process control devices were devised by mechanical engineers using mechanical feedback along with pneumatic and hydraulic control devices, some of which are still in use today. The field of control within chemical engineering is often known as process control. It deals primarily with the control of variables in a chemical process in a plant. It is taught as part of the undergraduate curriculum of any chemical engineering program, and employs many of the same principles in control engineering. Other engineering disciplines also overlap with control engineering, as it can be applied to any system for which a suitable model can be derived. Control engineering has diversified applications that include science, finance management, and even human behaviour. Students of control engineering may start with a linear control system course which requires elementary mathematics and Laplace transforms (called classical control theory). In linear control, the student does frequency and time domain analysis. Digital control and non-linear control courses require Z Transformations and algebra respectively, and could be said to complete a basic control education. From here onwards there are several sub branches.

Control systems

Control systems play a critical role in space flight Control engineering is the engineering discipline that focuses on the modelling of a diverse range of dynamic systems (e.g mechanical systems) and the design of controllers that will cause these systems to behave in the desired manner. Although such controllers need not be electrical many are and hence control engineering is often viewed as a subfield of electrical engineering. Electrical circuits, digital signal processors and microcontrollers can all be used to implement Control systems. Control engineering has a wide range of applications from the flight and propulsion systems of commercial airliners to the cruise control present in many modern automobiles. Control engineers often utilize feedback when designing control systems. For example, in an automobile with cruise control the vehicle’s speed is continuously monitored and fed back to the system which adjusts the motor’s speed accordingly. Where there is regular feedback, control theory can be used to determine how the system responds to such feedback. In practically all such systems stability is important and control theory can help ensure stability is achieved. Although feedback is an important aspect of control engineering, control engineers may also work on the control of systems without feedback. This is known as open loop control. A classic example of open loop control is a washing machine that runs through a pre-determined cycle without the use of sensors.

Programmable logic controller

PLC & input/output arrangements A Programmable Logic Controller, PLC, or Programmable Controller is a small computer used for automation of real-world processes, such as control of machinery on factory assembly lines. The PLC usually uses a microprocessor. The program can often control complex sequencing and is often written by engineers. The program is stored in battery-backed memory and/or EEPROMs. Unlike general-purpose computers, the PLC is packaged and designed for extended temperature ranges, dirty or dusty conditions, immunity to electrical noise, and is mechanically more rugged and resistant to vibration and impact.

Features The main difference from other computers are the special input/output arrangements. These connect the PLC to sensors and actuators. PLCs read limit switches, temperature indicators and the positions of complex positioning systems. Some even use machine vision. On the actuator side, PLCs drive any kind of electric motor, pneumatic or hydraulic cylinders or diaphragms, magnetic relays or solenoids. The input/output arrangements may be built into a simple PLC, or the PLC may have external I/O modules attached to a proprietary computer network that plugs into the PLC. PLCs were invented as less expensive replacements for older automated systems that would use hundreds or thousands of relays and cam timers. Often, a single PLC can be programmed to replace thousands of relays. Programmable controllers were initially adopted by the automotive manufacturing industry, where software revision replaced the re-wiring of hard-wired control panels. The earliest PLCs expressed all decision making logic in simple ladder logic inspired from the electrical connection diagrams. The electricians were quite able to trace out circuit problems with schematic diagrams using ladder logic. This was chosen mainly to reduce the apprehension of the existing technicians. The functionality of the PLC has evolved over the years to include typical relay control, sophisticated motion control, process control, distributed control systems and complex

networking. Today, the line between a general purpose programmable computer and a PLC is thinning. The data handling, storage, processing power and communication capabilities of some modern PLCs are approximately equivalent to desk-top computers. PLC-like functionality, combined with remote I/O hardware, allow a general-purpose desktop computer to overlap some PLCs in certain applications. With the IEC 61131-3 standard, it is now possible to program PLCs using structured programming languages, and logic elementary operations. A graphical programming notation called Sequential Function Charts is available on certain programmable controllers.

PLC compared with other control systems PLCs are well-adapted to a certain range of automation tasks. These are typically industrial processes in manufacturing where the cost of developing and maintaining the automation system is high relative to the total cost of the automation, and where changes to the system would be expected during its operational life. PLCs contain everything needed to handle high power loads right out of the box; very little electrical design is required and the design problem centers on expressing the desired sequence of operations in ladder logic (or function chart) notation. PLC applications are typically highly customized systems so the cost of a PLC is low compared to the cost of contracting a designer for a specific, one-time only design. On the other hand, in the case of massproduced goods, customized control systems quickly pay for themselves due to the lower cost of the components, which can be optimally chosen instead of a “generic” solution. However, it should be noted that some PLCs no longer have a very high cost. Modern PLCs with full capabilities are available for a few hundred USD. For high volume or very simple fixed automation tasks, different techniques are used. For example, a consumer dishwasher would be controlled by an electromechanical cam timer costing only a few dollars in production quantities. A microcontroller-based design would be appropriate where hundreds or thousands of units will be produced and so the development cost (design of power supplies and input/output hardware) can be spread over many sales, and where the end-user would not need to alter the control. Automotive applications are an example; millions of units are built each year, and very few end-users alter the programming of these controllers. (However, some specialty vehicles such as transit busses economically use PLCS instead of custom-designed controls, because the volumes are low and the development cost would be uneconomic.) Very complex process control, such as used in the chemical industry, may require algorithms and performance beyond the capability of even high-performance PLCs. Very high speed controls may also require customised solutions; for example, aircraft flight controls.

Digital vs. analog signals Digital or Discrete signals behave as switches, yielding simply an On or Off signal (1 or 0, True or False, respectively). Pushbuttons, limit switches, and photo-eyes are examples of devices providing a discrete signal. Discrete signals are judged using either voltage or current, where a specific range is denominated as On and another as Off. A PLC might use 24 V DC I/O, with values above 22 V DC representing On and values below 2VDC representing Off. Initially, PLCs had only discrete I/O. Analog signals are like volume controls, with a range of values between zero and fullscale. These are typically interpreted as integer values (counts) by the PLC, with various ranges of accuracy depending on the device and the number of bits available to store the data. Pressure, temperature and weight are often analog signals. Analog signals can use voltage or current, but do not have discrete ranges for On or Off. Instead they work in a defined range of values that are reliable for a particular device. Typically an analog 4-20 mA or 0 - 10 V signal would be converted into an integer value of 0 - 32767. Current inputs are less sensitive to electrical noise (i.e. from welders or electric motor starts) than voltage inputs.

Example As an example, say the facility needs to store water in a tank. The water is drawn from the tank by another system, as needed and our example system must manage the water level in the tank. Using only digital signals, the PLC has two digital inputs from float switches (tank empty and tank full). The PLC uses a digital output to open and close the inlet valve into the tank. If both float switches are off (down) or only the ‘tank empty’ switch is on, the PLC will open the valve to let more water in. If only the ‘tank full’ switch is on, the valve turns off. Both switches being on would signal that something is wrong with one of the switches, as the tank cannot be both full and empty at the same time. Two float switches are used to prevent a ‘flutter’ condition where any water usage activates the pump for a very short time causing the system to wear out faster. An analog system might use a load cell (scale) that weighs the tank, and a rate valve. The PLC could use a PID feedback loop (see section below) to control the rate valve. The load cell is connected to one of the PLC’s analog inputs and the rate valve is connected to another of the PLC’s analog outputs. This system fills the tank faster when there is less water in the tank. If the water level drops rapidly, the rate valve can be opened wide. If water is only dripping out of the tank, the rate valve adjusts to slowly drip water back into the tank. In this system, to avoid ‘flutter’ adjustments that can wear out the valve, many PLCs have a “deadband”. A technician adjusts this deadband so the valve moves only for a

significant change in rate. This will in turn minimize the motion of the valve, and reduce its wear. A real system might combine both approaches, using float switches and simple valves to prevent spills, and a rate sensor and rate valve to optimize refill rates. Backup and maintenance methods can make a real system very complicated.

How PLCs package I/O capabilities: Modular, Rack, P2P Modular PLCs have a limited number of connections built in for inputs and outputs. Typically, expansions are available if the base model does not have enough I/O. Rack-style PLCs have processor modules with separate [optional] I/O modules, which may occupy many racks. These often have thousands of discrete and analog inputs and outputs. Often a special high speed serial I/O link is used so that racks can be remotely mounted from the processor, reducing the wiring costs for large plants. Some of today’s PLCs can communicate over a wide range of media including RS-485, Coaxial, and even Ethernet for I/O control at network speeds up to 100Mbps. PLCs used in larger I/O systems may have peer-to-peer (P2P) communication between processors. This allows separate parts of a complex process to have individual control while allowing the subsystems to co-ordinate over the communication link. These communication links are also often used for HMI devices such as keypads or PC-type workstations. A rule-of thumb is that the average number of inputs installed is three times that of outputs for both analog and digital. The ‘extra’ inputs arise from the need to have redundant methods to monitor an instrument to appropriately control another, and from the need to use both manual command inputs to the system and feedback from the controlled system itself.

Programming Early PLCs, up to the mid-1980s, were programmed using proprietary programming panels or special-purpose programming terminals, which often had dedicated function keys representing the various logical elements of PLC programs. Programs were stored on cassette tape cartridges. Facilities for printing and documentation were very minimal due to lack of memory capacity. More recently, PLC programs are typically written in a special application on a personal computer, then downloaded by a direct-connection cable or over a network to the PLC. The very oldest PLCs used non-volatile magnetic core memory but now the program is stored in the PLC either in battery-backed-up RAM or some other non-volatile flash memory. Early PLCs were designed to be used by electricians who would learn PLC programming on the job. These PLCs were programmed in “ladder logic”, which strongly resembles a schematic diagram of relay logic. Modern PLCs can be programmed in a variety of ways,

from ladder logic to more traditional programming languages such as BASIC and C. Another method is State Logic, a Very High Level Programming Language designed to program PLCs based on State Transition Diagrams. Recently, the International standard IEC 61131-3 has become popular. IEC 61131-3 currently defines five programming languages for programmable control systems: FBD (Function block diagram), LD (Ladder diagram), ST (Structured text, similar to the Pascal programming language), IL (Instruction list, similar to assembly language) and SFC (Sequential function chart). These techniques emphasize logical organization of operations. While the fundamental concepts of PLC programming are common to all manufacturers, differences in I/O addressing, memory organization and instruction set mean that PLC programs are never perfectly interchangeable between different makers. Even within the same product line of a single manufacturer, different models may not be directly compatible.

PID loops PLCs may include logic for single-variable generic industrial feedback loop, a “proportional, integral, derivative” loop, or “PID controller.” A PID loop is the standard solution to many industrial process control processes that require proportional, integral(“improve errors”) or derivative (“faster response”) control techniques. A PID loop could be used to control the temperature of a manufacturing process, for example.

User interface PLCs may need to interact with people for the purpose of configuration, alarm reporting or everyday control. A Human-Machine Interface (HMI) is employed for this purpose. A simple system may use buttons and lights to interact with the user. Text displays are available as well as graphical touch screens. Most modern PLCs can communicate over a network to some other system, such as a computer running a SCADA(Supervisory Control And Data Acquisition) system or web browser.

Communications PLCs usually have built in communications ports for at least RS232, and optionally for RS485 and ethernet. Modbus is the lowest common denominator communications protocol. Others are various fieldbuses such as Profibus.

History The PLC was invented in response to the needs of the American automotive industry. Before the PLC, control, sequencing, and safety interlock logic for manufacturing automobiles was accomplished using relays, timers and dedicated closed-loop controllers. The process for updating such facilities for the yearly model change-over was very time consuming and expensive, as the relay systems needed to be rewired by skilled electricians. In 1968 GM Hydramatic (the automatic transmission division of General Motors) issued a request for proposal for an electronic replacement for hard-wired relay systems. The winning proposal came from Bedford Associates of Boston, Massachusetts. The first PLC, designated the 084 because it was Bedford Associates eighty-fourth project, was the result. Bedford Associates started a new company dedicated to developing, manufacturing, selling, and servicing this new product: Modicon, which stood for MOdular DIgital CONtroller. One of the people who worked on that project was Dick Morley, who is considered to be the “father” of the PLC. The Modicon brand was sold in 1977 to Gould Electronics, and later acquired by German Company AEG and then by Schneider Electric, the current owner. One of the very first 084 models built is now on display at Modicon’s headquarters in North Andover, Massachusetts. It was presented to Modicon by GM, when the unit was retired after nearly twenty years of uninterrupted service. The automotive industry is still one of the largest users of PLCs, and Modicon still numbers some of its controller models such that they end with eighty-four. PLCs are used in many different industries and machines such as packaging and semiconductor machines. Well known PLC brands are ABB Ltd., Koyo, Honeywell, Siemens, Modicon, Omron, Allen-Bradley, General Electric, Tesco Controls, Panasonic (Matsushita), and Mitsubishi.

Building automation “Building automation” can also refer to Build automation, the practice of programmatically compiling software programs. Building automation is a programmed, computerized, “intelligent” network of electronic devices that monitor and control the mechanical and lighting systems in a building. The intent is to create an intelligent building and reduce energy and maintenance costs.

Parts of the system Controller The controller is normally one or more programmable logic controllers, often with custom programming. PLCs come in a wide range of sizes and capabilities to control devices that are common in buildings. Usually the primary and secondary buses are chosen based on what the PLCs provide. Most PLCs provide general purpose feedback loops, as well as digital circuits.

Occupancy sensors Occupancy is usually based on time of day schedules. Override is possible through different means. Some buildings can sense occupancy in their internal spaces by an override switch or sensor.

Lighting Lighting can be turned on and off with a building automation system based on time of day, or the occupancy sensors and timers. One typical example is to turn the lights in a space on for a half hour since the last motion was sensed. A photocell placed outside a building can sense darkness, and the time of day, and modulate lights in outer offices and the parking lot.

Air handlers Most air handlers mix return and outside air so less temperature change is needed. This can save money by using less chilled or heated water (not all AHUs use chilled/hot water circuits). Some external air is needed to keep the building’s air healthy. Analog or digital temperature sensors may be placed in the space or room, the return and supply air ducts, and sometimes the external air. Actuators are placed on the hot and chilled water valves, the outside air and return air dampers. The supply fan (and return if applicable) is started and stopped based on either time of day, temperatures, building pressures or a combination. Constant Volume Air-Handling Units The less efficient type of air-handler is a “Constant Volume Air Handling Unit,” or CAV. The fans in CAVs do not have variable-speed controls. Instead, CAVs open and close dampers and water-supply valves to maintain temperatures in the building’s spaces. They heat or cool the spaces by opening or closing chilled or hot water valves that feed their internal heat exchangers. Generally one CAV serves several spaces, but large buildings may have many CAVs. Variable Volume Air-Handling Units A more efficient unit is a “Variable Air Volume (VAV) Air-Handling Unit,” or VAV. VAVs supply pressurized air to VAV boxes, usually one box per room or area. A VAV air handler can change the pressure to the VAV boxes by changing the speed of a fan or blower with a variable frequency drive or (less efficiently) by moving inlet guide vanes to a fixed-speed fan. The amount of air is determined by the needs of the spaces served by the VAV boxes. Each VAV box supply air to a small space, like an office. Each box has a damper that is opened or closed based on how much heating or cooling is required in its space. The

more boxes are open, the more air is required, and a greater amount of air is supplied by the VAV air-handling unit. Some VAV boxes also have hot water valves and an internal heat exchanger. The valves for hot and cold water are opened or closed based on the heat demand for the spaces it is supplying. These heated VAV boxes are sometimes used on the perimeter only and the interior zones are cooling only. A minimum and maximum CFM must be set on VAV boxes to assure adaquate ventilation and proper air balance. VAV Hybrid Systems Another variation is a hybrid between VAV and CAV systems. In this system, the interior zones operate as in a VAV system. The outer zones differ in that the heating is supplied by a heating fan in a central location usually with a heating coil fed by the building boiler. The heated air is ducted to the exterior dual duct mixing boxes and dampers controlled by the zone thermostat calling for either cooled or heated air as needed.

Central plant A central plant is needed to supply the air-handling units with water. It may supply a chilled water system, hot water system and a condenser water system, as well as transformers and emergency power. If well managed, these can often help each other. For example, some plants generate electric power at period with peak demand, using a gas turbine, and then use the turbine’s hot exhaust to heat water or power an absorptive chiller. Chilled water system Chilled water is often used to cool a building’s air and equipment. The chilled water system will have chiller(s) and pumps. Analog temperature sensors measure the chilled water supply and return lines. The chiller(s) are sequenced on and off to chill the chilled water supply. Condenser water system Cooling tower(s) and pumps are used to supply cool condenser water to the chillers. The condenser water supply to the chillers has to be constant so, speed drives are commonly used on the cooling tower fans to control temperature. Proper cooling tower temperature assures the proper refrigerant head pressure in the chiller. The cooling tower set point used depends upon the refrigerant being used. Analog temperature sensors measure the condenser water supply and return lines. Hot water system

The hot water system supplies heat to the building’s air-handling units or VAV boxes. The hot water system will have a boiler(s) and pumps. Analog temperature sensors are placed in the hot water supply and return lines. Some type of mixing valve is usually used to control the heating water loop temperature. The boiler(s) and pumps are sequenced on and off to maintain supply.

Alarms and security Many building automation systems have alarm capabilities. If an alarm is detected, it can be programmed to notify someone. Notification can be through a computer, pager or audible alarm. • • • • • • •

Common temperature alarms are Space, Supply Air, Chilled Water Supply and Hot Water Supply. Differential pressure switches can be placed on the filter to determine if it is dirty. Status alarms are common. If a mechanical device like a pump is requested to start, and the status input indicates it is off. This can indicate a mechanical failure. Some valve actuators have end switches to indicate if the valve has opened or not. Carbon monoxide and carbon dioxide sensors can be used to alarm if levels are too high. Refrigerant sensors can be used to indicate a possible refrigerant leak. Amperage sensors can be used to detect low amperage conditions caused by slipping fan belts, or clogging strainers at pumps.

At sites with several buildings, momentary power failures can cause hundreds or thousands of alarms from equipment that has shutdown. Some sites are programmed so that critical alarms are automatically re-sent at varying intervals. For example, a repeating critical alarm (of a uninterruptible power supply in ‘by pass’) might resound at 10 minutes, 30 minutes, and every 2 to 4 hours there after until the alarms are resolved. Security systems can be interlocked to a building automation system. If occupancy sensors are present, they can also be used as burglar alarms. Fire and smoke alarm systems can be hard-wired to override building automation. For example: if the smoke alarm is activated, all the outside air dampers close to prevent air coming into the building. Life safety applications are normally hard-wired to a mechanical device to override building automation control.

Topology Most building automation networks consist of a primary and secondary bus which contain programmable logic controllers, input/outputs and a user interface (also known as a human interface device). The primary and secondary bus can be optical fiber, ethernet, ARCNET, RS-232, RS-485 or a wireless network.

Most controllers are proprietary. Each company has its own controllers for specific applications. Some are designed with limited controls: for example, a simple Packaged Roof Top Unit. Others are designed to be flexible. Most have proprietary software that will work with BACnet, LonTalk and ASHRAE standards. Inputs and outputs are either analog or digital (some companies say binary). Analog inputs are used to read a variable measurement. Examples are temperature, humidity and pressure sensor which could be thermistor, 4-20 mA, 0-10 Volt or Platinum RTD (resistance temperature detector), or wireless sensors. A digital input indicates if a device is turned on or not. Some examples of a digital input would be a 24VDC relay or air flow switch. Analog outputs control the speed or position of a device, such as a variable frequency drive, a I-P (current to pneumatics) transducer, or an actuator. An example is a hot water valve opening up 25% to maintain a setpoint. Digital outputs are used to open and close relays and switches. An example would be to turn on the parking lot lights when a photocell indicates it is dark outside.

Protocols and Industry Standards • • • • • • •

•

ASHRAE (American Society of Heating, Refrigerating and Air Conditioning Engineers) is an international organization for people involved in heating, ventilation, air conditioning, or refrigeration (HVAC&R). BACnet is a network communications protocol for building automation and control systems. DALI DSI Dynet Energy Star is program created by the United States government to promote energy efficient consumer products. KNX standard, a system for Home and Building Controls (promoted by “Konnex Association”)is truly open (no royalties for Konnex members) and platform independent; guarantees multi-vendor and cross-discipline interoperability, ensured via certification and symbolized by the KNX trademark; supports many configuration methods (PC tools, device configurators and plug+play) and media (TP, PL, RF, Ethernet) LonTalk is a protocol created by Echelon Corporation for networking devices.

HVAC control system A HVAC control system is a computerized system for climate control in buildings. HVAC stands for heating, ventilation , air-conditioning. Often, these integrate fire, security, and lighting controls into one system. These systems typically use one or more central controllers to command and monitor the remote terminal unit controllers, and they communicate with one or more personal computers that are used as the operator interface. These control systems are typically used on large commercial and industrial buildings to allow central control of many HVAC units around the building(s). The latest systems use the building ethernet for communications between central controllers, and allow operator access from a web browser.

Direct digital control Central controllers and most terminal unit controllers are programmable, meaning the direct digital control program code may be customized for the intended use. The program features include time schedules, setpoints, controllers, logic, timers, trend logs, and alarms. The unit controllers typically have analog and digital inputs, that allow measurement of the variable (temperature, humidity, or pressure) and analog and digital outputs for control of the medium (hot/cold water and/or steam). Digital inputs are typically (dry) contacts from a control device, and analog inputs are typically a voltage or current measurement from a variable (temperature, humidity, velocity, or pressure) sensing device. Digital outputs are typically relay contacts used to start and stop equipment, and analog outputs are typically voltage or current signals to control the movement of the medium (air/water/steam) control devices.(Valves/dampers/motor speed)

History It was only natural that the first HVAC controllers would be pneumatic, as the engineers understood fluid control. Thus mechanical engineers could use their experience with the properties of steam and air to control the flow of heated or cooled air. To this day, there is pneumatic HVAC equipment in operation, which can be a century old, in some buildings, such as schools and offices. After the control of air flow and temperature was standardized, the use of electromechanical relays in ladder logic, to switch dampers became standardized. Eventually, the relays became electronic switches, as transistors eventually could handle greater current loads. By 1985, pneumatic control could no longer compete with this new technology. By the year 2000, computerized controllers were common. Today, some of these controllers can even be accessed by web browsers, which need no longer be in the same

building as the HVAC equipment. This allows some economies of scale, as a single operations center can easily monitor thousands of buildings.

Signal processing Signal processing is the processing, amplification and interpretation of signals, and deals with the analysis and manipulation of signals. Signals of interest include sound, images, biological signals such as ECG, radar signals, and many others. Processing of such signals includes storage and reconstruction, separation of information from noise (e.g., aircraft identification by radar), compression (e.g., image compression), and feature extraction (e.g., speech-to-text conversion).

Signal classification Signals can be either analog or digital, and may come from various sources. There are various sorts of signal processing, depending on the nature of the signal, as in the following examples. For analog signals, signal processing may involve the amplification and filtering of audio signals for audio equipment or the modulation and demodulation of signals for telecommunications. For digital signals, signal processing may involve the compression, error checking and error detection of digital signals. • • • • • • • •

Analog signal processing—for signals that have not been digitized, as in classical radio, telephone, radar, and television systems Digital signal processing—for signals that have been digitized. Processing is done by digital circuits such as ASICs, FPGAs, general-purpose microprocessors or computers, or specialized digital signal processor chips. Statistical signal processing—analyzing and extracting information from signals based on their statistical properties Audio signal processing—for electrical signals representing sound, such as music Speech signal processing—for processing and interpreting spoken words Image processing—in digital cameras, computers, and various imaging systems Video signal processing—for interpreting moving pictures Array processing—for processing signals from arrays of sensors

Topics in signal processing • • • •

Sampling (signal processing) Quantization (signal processing) LTI system theory Fourier transform

Sampling (signal processing)

In signal processing, sampling is the reduction of a continuous signal to a discrete signal. A common example is the conversion of a sound wave (a continuous-time signal) to a sequence of samples (a discrete-time signal).

Theory Nyquist–Shannon sampling theorem

For convenience, we will discuss signals which vary with time. However, the same results can be applied to signals varying in space or in any other dimension. Let x(t) be a continuous signal which is to be sampled, and that sampling is performed by measuring the value of the continuous signal every T seconds. Thus, the sampled signal x[n] is given by x[n] = x(nT) with n = 0,1,2,3,.... The sampling frequency or sampling rate fs is defined as the number of samples obtained in one second, or fs = 1 / T. The sampling rate is measured in Hertz or in samples per second. We can now ask: under what circumstances is it possible to reconstruct the original signal completely and exactly (perfect reconstruction)? A partial answer is provided by the Nyquist–Shannon sampling theorem, which provides a sufficient (but not always necessary) condition under which perfect reconstruction is possible. The sampling theorem guarantees that bandlimited signals (i.e., signals which have a maximum frequency) can be reconstructed perfectly from their sampled version, if the sampling rate is more than twice the maximum frequency. Reconstruction in this case can be achieved using the Whittaker–Shannon interpolation formula. The frequency equal to one-half of the sampling rate is therefore a bound on the highest frequency that can be unambigiously represented by the sampled signal. This frequency (half the sampling rate) is called the Nyquist frequency of the sampling system. Frequencies above the Nyquist frequency fN can be observed in the sampled signal, but their frequency is ambiguous. That is, a frequency component with frequency f cannot be distinguished from other components with frequencies NfN + f and NfN − f for nonzero integers N. This ambiguity is called aliasing. To handle this problem as gracefully as possible, most analog signals are filtered with an anti-aliasing filter (usually a low-pass filter with cutoff near the Nyquist frequency) before conversion to the sampled discrete representation. A more general statement of the Nyquist–Shannon sampling theorem says more or less that the signals with frequencies higher than the Nyquist frequency can be sampled

without loss of information, provided their bandwidth (non-zero frequency band) is small enough to avoid ambiguity, and the bandlimits are known.

Sampling interval The sampling interval is the interval T = 1 / fs corresponding to the sampling frequency.

Observation period The observation period is the span of time during which a series of data samples are collected at regular intervals.More broadly, it can refer to any specific period during which a set of data points is gathered, regardless of whether or not the data is periodic in nature. Thus a researcher might study the incidence of earthquakes and tsunamis over a particular time period, such as a year or a century. The observation period is simply the span of time during which the data is studied, regardless of whether data so gathered represents a set of discrete events having arbitrary timing within the interval, or whether the samples are explicitly bound to specified subintervals.

Practical implications In practice, the continuous signal is sampled using an analog-to-digital converter (ADC), a non-ideal device with various physical limitations. This results in deviations from the theoretically perfect reconstruction capabilities, collectively referred to as distortion. Various types of distortion can occur, including: •

•

• • •

Aliasing. A precondition of the sampling theorem is that the signal be bandlimited. However, in practice, no time-limited signal can be bandlimited. Since signals of interest are almost always time-limited (e.g., at most spanning the lifetime of the sampling device in question), it follows that they are not bandlimited. However, by designing a sampler with an appropriate guard band, it is possible to obtain output that is as accurate as necessary. Integration effect or aperture effect. This results from the fact that the sample is obtained as a time average within a sampling region, rather than just being equal to the signal value at the sampling instant. The integration effect is readily noticeable in photography when the exposure is too long and creates a blur in the image. An ideal camera would have an exposure time of zero. In a capacitorbased sample and hold circuit, the integration effect is introduced because the capacitor cannot instantly change voltage thus requiring the sample to have nonzero width. Jitter or deviation from the precise sample timing intervals. Noise, including thermal sensor noise, analog circuit noise, etc. Slew rate limit error, caused by an inability for an ADC output value to change sufficiently rapidly.

• •

Quantization as a consequence of the finite precision of words that represent the converted values. Error due to other non-linear effects of the mapping of input voltage to converted output value (in addition to the effects of quantization).

The conventional, practical digital-to-analog converter (DAC) does not output a sequence of dirac impulses (such that, if ideally low-pass filtered, result in the original signal before sampling) but instead output a sequence of piecewise constant values or rectangular pulses. This means that there is an inherent effect of the zero-order hold on the effective frequency response of the DAC resulting in a mild roll-off of gain at the higher frequencies (a 3.9224 dB loss at the Nyquist frequency). This zero-order hold effect is a consequence of the hold action of the DAC and is not due to the sample-andhold that might precede a conventional ADC as is often misunderstood. The DAC can also suffer errors from jitter, noise, slewing, and non-linear mapping of input value to output voltage. Jitter, noise, and quantization are often analyzed by modeling them as random errors added to the sample values. Integration and zero-order hold effects can be analyzed as a form of low-pass filtering. The non-linearities of either ADC or DAC are analyzed by replacing the ideal linear function mapping with a proposed nonlinear function.

Applications Audio sampling Audio waveforms are commonly sampled at 44.1k samples/s (CD) or 48k samples/s (professional audio). This is usually sufficient for any practical purpose, since the human auditory system is capable of discerning sounds up to about 15-20 kHz. The recent trend towards higher sampling rates, at two or four times this basic requirement, has not been justified theoretically, or shown to make any audible difference, even under the most critical listening conditions. Nevertheless, a lot of 96kHz equipment is now used in studio recording, and ‘superaudio’ formats are being promised to consumers, mostly as a DVD option. Most articles purporting to justify a need for more than 48 kHz state that the ‘dynamic range’ of 16-bit audio is 96dB, a figure commonly derived from the simple ratio of quantizing level to full-scale level, which is 216, or 65536. This calculation fails to take into account the fact that peak level is not maximum permitted sine-wave signal level, and quantizing step size is not rms noise level, and even if it were it would not represent loudness, without the application of the ITU-R 468 noise weighting function. A proper analysis of typical programme levels throughout the audio chain reveals the fact that the capabilities of well engineered 16-bit material far exceed those of the very best hi-fi systems, with the microphone noise and loudspeaker headroom being the real limiting factors.

Speech sampling Speech signals, i.e., signals intended to carry only human speech, can usually be sampled at a much lower rate. For most phonemes, almost all of the energy is contained in the 0-4 kHz range, allowing a sampling rate of 8 kHz. This is the sampling rate used by nearly all telephony systems, which use the G.711 sampling and quantization specifications.

Video sampling Standard-definition television (SDTV) uses 704 by 576 pixels (UK PAL 625-line) for the visible picture area. High-definition television (HDTV) is currently moving towards two standards referred to as 720p (progressive) and 1080i (interlaced), which all ‘HD-Ready’ sets will be able to display. Video reconstruction filtering Most TV sets do not achieve basic SDTV quality, because they do not reconstruct the vertically sampled image properly. Digital video produces a 2-dimensional set of samples of each frame, which requires a 2-dimensional ‘brick-wall’ reconstruction filter for proper reproduction of the image. CRT displays produce a raster scan of horizontal lines, and the digital signal is low-pass filtered along the horizontal lines, giving good resolution of vertical lines without aliasing, but reconstruction is not usually attempted vertically, so that the resulting picture contains very visible artifacts (loss of resolution, staircasing effects, fringing pattern, sampling harmonics, and other adverse effects). Proper 2-dimensional reconstruction requires a final display with many more pixels than the signal format, and modern HDTV sets can provide this, producing much better resolution pictures than even a top studio monitor can from SDTV signals (though they are not so good regarding grey-level accuracy, especially near black level). As with audio, this theoretical need for reconstruction is not commonly realised, though it was recognised by the BBC who then backed off from broadcasting HDTV but started to record programmes in HDTV. To get a true HDTV image you really need a ‘super HDTV’ display, with at least twice as many pixels again (3840 x 2160)!! Worth bearing in mind though not currently practical. Nevertheless, HDTV does a very significant increase in resolution over SDTV when both are compared on a HDTV set, the higher Nyquist frequency bringing improvements despite the fact that the image is not properly reconstructed on currently available displays.

IF/RF sampling

Plot of allowed sample rates (gray areas) versus the upper edge frequency for a band of width W = 1. The darker gray areas correspond to the condition with n = 0 in the equations of this section. For sampling a non-baseband signal, such as a radio’s intermediate-frequency (IF) or radio-frequency (RF) signal, the Nyquist–Shannon conditions to avoid aliasing can be restated as follows. Let 0 < fL < fH be the lower and higher boundaries of a frequency band and W = fH − fL be the bandwidth. Then there is a non-negative integer N with

In addition, we define the remainder r as . Any real-valued signal x(t) with a spectrum limited to this frequency band, that is with for

outside the interval

,

is uniquely determined by its samples obtained at a sampling rate of fs, if this sampling rate satisfies one of the following conditions:

•

for one value of n

= { 0, 1, ..., N-1 } OR the usual Nyquist condition: •

.

If N > 0, then the first conditions result in what is sometimes referred to as undersampling, or using a sampling rate less than the Nyquist rate 2fH obtained from the upper bound of the spectrum. See aliasing for a simpler formulation of this Nyquist criterion that specifies the lower bound on sampling rate (but is incomplete because it does not specify the gaps above that bound, in which aliasing will occur). Alternatively,

for the case of a given sampling frequency, simpler formulae for the constraints on the signal’s spectral band are given below.

Spectrum of the FM radio band (88–108 MHz) and its baseband alias under 44 MHz (N– n = 4) sampling. An anti-alias filter quite tight to the FM radio band is required, and there’s not room for stations at nearby expansion channels such as 87.9 without aliasing.

Spectrum of the FM radio band (88–108 MHz) and its baseband alias under 56 MHz (N– n = 3) sampling, showing plenty of room for bandpass anti-aliasing filter transition bands. The baseband image is frequency-reversed in this case (odd N–n). Example: Consider FM radio to illustrate the idea of undersampling. In the US, FM radio operates on the frequency band from fL = 88 MHz to fH = 108 MHz. The bandwidth is given by

The sampling conditions are satisfied for

Therefore N=4, r=8 MHz and n = 0,1,2,3. The value n = 0 gives the lowest sampling frequencies interval and this is a scenario of undersampling. In this case, the signal spectrum fits between and 2 and 2.5 times the sampling rate (higher than 86.4–108 but lower than 88-110 MHz). A lower value of N will also lead to a useful sampling rate, equivalent to picking a nonzero n. For example, using N–n = 3, the FM band spectrum fits easily between 1.5 and 2.0 times the sampling rate, for a sampling rate near 56 MHz (multiples of the Nyquist frequency being 28, 56, 84, 112, etc.). See the illustrations at the right.

When undersampling a real-world signal, the sampling circuit must be fast enough to capture the highest signal frequency of interest. Theoretically, each sample should be taken during an infinitesimally short interval, but this is not practically feasible. Instead, the sampling of the signal should be made in a short enough interval that it can represent the instantaneous value of the signal with the highest frequency. This means that in the FM radio example above, the sampling circuit must be able to capture a signal with a frequency of 108 MHz, not 43.2 MHz. Thus, the sampling frequency may be only a little bit greater than 43.2 MHz, but the input bandwidth of the system must be at least 108 MHz. If the sampling theorem is interpreted as requiring twice the highest frequency, then the required sampling rate would be assumed to be greater than the Nyquist rate 216 MHz. While this does satisfy the last condition on the sampling rate, it is grossly oversampled. Note that if a band is sampled with a nonzero N, then a band-pass filter is required for the anti-aliasing filter, instead of a lowpass filter. As we have seen, the normal baseband condition for reversible sampling is that outside the open interval: And the reconstructive interpolation function, or lowpass filter impulse response, is . To accommodate undersampling, the generalized condition is that the union of open positive and negative frequency bands

outside

for some nonnegative integer . which includes the normal baseband condition as case N=0 (except that where the intervals come together at 0 frequency, they can be closed). And the corresponding interpolation function is the bandpass filter given by this difference of lowpass impulse responses:

. On the other hand, reconstruction is not usually the goal with sampled IF or RF signals. Rather, the sample sequence can be treated as ordinary samples of the signal frequencyshifted to near baseband, and digital demodulation can proceed on that basis.

Quantization (signal processing)

Quantized signal

Digital signal In digital signal processing, quantization is the process of approximating a continuous range of values (or a very large set of possible discrete values) by a relatively-small set of discrete symbols or integer values. More specifically, a signal can be multi-dimensional and quantization need not be applied to all dimensions. Discrete signals (a common mathematical model) need not be quantized, which can be a point of confusion. See ideal sampler. A common use of quantization is in the conversion of a discrete signal (a sampled continuous signal) into a digital signal by quantizing. Both of these steps (sampling and quantizing) are performed in analog-to-digital converters with the quantization level specified in bits. A specific example would be compact disc (CD) audio which is sampled at 44,100 Hz and quantized with 16 bits (2 bytes) which can be one of 65,536 (i.e. 216) possible values per sample.

Mathematical description The simplest and best-known form of quantization is referred to as scalar quantization, since it operates on scalar (as opposed to multi-dimensional vector) input data. In general, a scalar quantization operator can be represented as

where •

x is a real number to be quantized,

•

•

is the floor function, yielding an integer result referred to as the quantization index, f(x) and g(i) are arbitrary real-valued functions.

that is sometimes

The integer-valued quantization index i is the representation that is typically stored or transmitted, and then the final interpretation is constructed using g(i) when the data is later interpreted. In computer audio and most other applications, a method known as uniform quantization is the most common. There are two common variations of uniform quantization, called mid-rise and mid-tread uniform quantizers. If x is a real-valued number between -1 and 1, a mid-rise uniform quantization operator that uses M bits of precision to represent each quantization index can be expressed as

. In this case the f(x) and g(i) operators are just multiplying scale factors (one multiplier being the inverse of the other) along with an offset in g(i) function to place the representation value in the middle of the input region for each quantization index. The value 2 − (M − 1) is often referred to as the quantization step size. Using this quantization law and assuming that quantization noise is approximately uniformly distributed over the quantization step size (an assumption typically accurate for rapidly varying x or high M) and further assuming that the input signal x to be quantized is approximately uniformly distributed over the entire interval from -1 to 1, the signal to noise ratio (SNR) of the quantization can be computed as

. From this equation, it is often said that the SNR is approximately 6 dB per bit. For mid-tread uniform quantization, the offset of 0.5 would be added within the floor function instead of outside of it. Sometimes, mid-rise quantization is used without adding the offset of 0.5. This reduces the signal to noise ratio by approximately 6.02 dB, but may be acceptable for the sake of simplicity when the step size is small. In digital telephony, two popular quantization schemes are the ‘A-law’ (dominant in Europe) and ‘µ-law’ (dominant in North America and Japan). These schemes map discrete analog values to an 8-bit scale that is nearly linear for small values and then increases logarithmically as amplitude grows. Because the human ear’s perception of

loudness is roughly logarithmic, this provides a higher signal to noise ratio over the range of audible sound intensities for a given number of bits.

Quantization and data compression Quantization plays a major part in lossy data compression. In many cases, quantization can be viewed as the fundamental element that distinguishes lossy data compression from lossless data compression, and the use of quantization is nearly always motivated by the need to reduce the amount of data needed to represent a signal. In some compression schemes, like MP3 or Vorbis, compression is also achieved by selectively discarding some data, an action that can be analyzed as a quantization process (e.g., a vector quantization process) or can be considered a different kind of lossy process. One example of a lossy compression scheme that uses quantization is JPEG image compression. During JPEG encoding, the data representing an image (typically 8-bits for each of three color components per pixel) is processed using a discrete cosine transform and is then quantized and entropy coded. By reducing the precision of the transformed values using quantization, the number of bits needed to represent the image can be reduced substantially. For example, images can often be represented with acceptable quality using JPEG at less than 3 bits per pixel (as opposed to the typical 24 bits per pixel needed prior to JPEG compression). Even the original representation using 24 bits per pixel requires quantization for its PCM sampling structure. In modern compression technology, the entropy of the output of a quantizer matters more than the number of possible values of its output (the number of values being 2M in the above example). In order to determine how many bits are necessary to effect a given precision, logarithms are used. Suppose, for example, that it is necessary to record six significant digits, that is to say, millionths. The number of values that can be expressed by N bits is equal to two to the Nth power. To express six decimal digits, the required number of bits is determined by rounding (6 / log 2)—where log refers to the base ten, or common, logarithm—up to the nearest integer. Since the logarithm of 2, base ten, is approximately 0.30102, the required number of bits is then given by (6 / 0.30102), or 19.932, rounded up to the nearest integer, viz., 20 bits. This type of quantization—where a set of binary digits, e.g., an arithmetic register in a CPU, are used to represent a quantity—is called Vernier quantization. It is also possible, although rather less efficient, to rely upon equally spaced quantization levels. This is only practical when a small range of values is expected to be captured: for example, a set of eight possible values requires eight equally spaced quantization levels—which is not unreasonable, although obviously less efficient than a mere trio of binary digits (bits)— but a set of, say, sixty-four possible values, requiring sixty-four equally spaced quantization levels, can be expressed using only six bits, which is obviously far more efficient.

Relation to quantization in nature At the most fundamental level, all physical quantities are quantized. This is a result of quantum mechanics (see Quantization (physics)). Signals may be treated as continuous for mathematical simplicity by considering the small quantizations as negligible. In any practical application, this inherent quantization is irrelevant for two reasons. First, it is overshadowed by signal noise, the intrusion of extraneous phenomena present in the system upon the signal of interest. The second, which appears only in measurement applications, is the inaccuracy of instruments. Thus, although all physical signals are intrinsically quantized, the error introduced by modeling them as continuous is vanishingly small.

LTI system theory In electrical engineering, specifically in circuits, signal processing, and control theory, LTI system theory investigates the response of a linear, time-invariant system to an arbitrary input signal. Though the standard independent variable is time, it could just as easily be space (as in image processing and field theory) or some other coordinate. Thus a better, albeit less common, term is linear translation-invariant. The term linear shiftinvariant is the corresponding concept for a discrete-time (sampled) system.

Overview The defining properties of any linear time-invariant system are, of course, linearity and time invariance: •

Linearity means that the relationship between the input and the output of the system satisfies the scaling and superposition properties. Formally, a linear system is a system which exhibits the following property: if the input of the system is

then the output of the system will be for any constants A and B, where yi(t) is the output when the input is xi(t). •

Time invariance means that whether we apply an input to the system now or T seconds from now, the output will be identical, except for a time delay of the T seconds. More specifically, an input affected by a time delay should effect a corresponding time delay in the output, hence time-invariant.

The fundamental result in LTI system theory is that any LTI system can be characterized entirely by a single function called the system’s impulse response. The output of the system is simply the convolution of the input to the system with the system’s impulse response. This method of analysis is often called the time domain point-of-view. The same result is true of discrete-time linear shift-invariant systems, in which signals are discrete-time samples, and convolution is defined on sequences.

Relationship between the time domain and the frequency domain Equivalently, any LTI system can be characterized in the frequency domain by the system’s transfer function, which is the Laplace transform of the system’s impulse response (or Z transform in the case of discrete-time systems). As a result of the properties of these transforms, the output of the system in the frequency domain is the product of the transfer function and the transform of the input. In other words, convolution in the time domain is equivalent to multiplication in the frequency domain. For all LTI systems, the eigenfunctions, and the basis functions of the transforms, are complex exponentials. This is, if the input to a system is the complex waveform Aexp(st) for some complex amplitude A and complex frequency s, the output will be some complex constant times the input, say Bexp(st) for some new complex amplitude B. The ratio B / A is the transfer function at frequency s. Because sinusoids are a sum of complex exponentials with complex-conjugate frequencies, if the input to the system is a sinusoid, then the output of the system will also be a sinusoid, perhaps with a different amplitude and a different phase, but always with the same frequency. LTI system theory is good at describing many important systems. Most LTI systems are considered “easy” to analyze, at least compared to the time-varying and/or nonlinear case. Any system that can be modeled as a linear homogeneous differential equation with constant coefficients is an LTI system. Examples of such systems are electrical circuits made up of resistors, inductors, and capacitors (RLC circuits). Ideal spring–mass–damper systems are also LTI systems, and are mathematically equivalent to RLC circuits.

Most LTI system concepts are similar between the continuous-time and discrete-time (linear shift-invariant) cases. In image processing, the time variable is replaced with 2 space variables, and the notion of time invariance is replaced by two-dimensional shift invariance. When analyzing filter banks and MIMO systems, it is often useful to consider vectors of signals.

Continuous-time systems Time invariance and linear transformation Let us start with a time-varying system whose impulse response is a 2-dimensional function and see how the condition of time invariance helps us reduce it to one dimension. For example, suppose the input signal is x(t) where its index set is the real line, i.e., . The linear operator represents the system operating on the input signal. The appropriate operator for this index set is a 2-dimensional function

Since is a linear operator, the action of the system on the input signal x(t) is a linear transformation represented by the following superposition integral

If the linear operator

is also time-invariant, then

If we let

then it follows that

We usually drop the zero second argument to h(t1,t2) for brevity of notation so that the superposition integral now becomes the familiar convolution integral used in filtering

Thus, the convolution integral represents the effect of a linear, time-invariant system on any input function. For a finite-dimensional analog, see the article on a circulant matrix.

Impulse response If we input a Dirac delta function to this system, the result of the LTI transformation is known as the impulse response because the delta function is an ideal impulse. We illustrate this idea as follows:

(by the sifting property of the delta function). Note that

so that h(t) is the impulse response of the system. The impulse response can be used to find the response of any input in the following way. Again using the sifting property of the δ(t), we can write any input as a superposition of deltas:

Applying the system to the input,

(because

is linear and can pass inside the integral)

(because x(τ) is constant in t and

is linear)

(by definition of h(t)) All information about the system is contained in the impulse response h(t).

Exponentials as eigenfunctions An eigenfunction is a function for which the output of the operator is the same function, just scaled by some amount. In symbols,

, where f is the eigenfunction and λ is the eigenvalue, a constant. The exponential functions est, where , are eigenfunctions of a linear, timeinvariant operator. A simple proof illustrates this concept. Suppose the input is x(t) = est. The output of the system with impulse response h(t) is then

which is equivalent to the following by the commutative property of convolution

, where

is dependent only on the parameter s. So, est is an eigenfunction of an LTI system because the system response is the same as the input times the constant H(s).

Fourier and Laplace transforms The eigenfunction property of exponentials is very useful for both analysis and insight into LTI systems. The Laplace transform

is exactly the way to get the eigenvalues from the impulse response. Of particular interest are pure sinusoids, i.e. exponentials of the form exp(jωt) where and . These are generally called complex exponentials even though the argument is purely imaginary. The Fourier transform

gives the eigenvalues

for pure complex sinusoids. Both of H(s) and H(jω) are called the system function, system response, or transfer function. The Laplace transform is usually used in the context of one-sided signals, i.e. signals that are zero for all values of t less than some value. Usually, this “start time” is set to zero, for convenience and without loss of generality, with the transform integral being taken from zero to infinity (the transform shown with lower limit of integration of negative infinity is formally known as the bilateral Laplace transform). The Fourier transform is used for analyzing systems that process signals that are infinite in extent, such as modulated sinusoids, even though it can not be directly applied to input and output signals that are not square integrable. The Laplace transform actually works directly for these signals if they are zero before a start time, even if they are not square integrable, for stable systems. The Fourier transform is often applied to spectra of infinite signals via the Wiener–Khinchin theorem even when Fourier transforms of the signals do not exist. Due to the convolution property of both of these transforms, the convolution that gives the output of the system can be transformed to a multiplication in the transform domain, given signals for which the transforms exist

Not only is it often easier to do the transforms, multiplication, and inverse transform than the original convolution, but one can also gain insight into the behavior of the system from the system response. One can look at the modulus of the system function |H(s)| to see whether the input exp(st) is passed (let through) the system or rejected or attenuated by the system (not let through).

Examples A simple example of an LTI operator is the derivative:

When the Laplace transform of the derivative is taken, it transforms to a simple multiplication by the Laplace variable s.

That the derivative has such a simple Laplace transform partly explains the utility of the transform. Another simple LTI operator is an averaging operator

. It is linear because of the linearity of integration

. It is time invariant too

. Indeed,

can be written as a convolution with the box function Π(t).

, where the box function is

.

Important system properties Some of the most important properties of a system are causality and stability. It is more or less necessary for a system to be causal in order for it to be implemented in the real world. Non-stable systems can be built and can be useful in many circumstances. Even non-real systems can be built and are very useful in many contexts. Causality Causal system

A system is causal if the output depends only on present and past inputs. A necessary and sufficient condition for causality is

where h(t) is the impulse response. It is not possible in general to determine causality from the Laplace transform, because the inverse transform is not unique. When a region of convergence is specified, then causality can be determined. Stability BIBO stability

A system is bounded input, bounded output stable (BIBO stable) if, for every bounded input, the output is finite. Mathematically, if

and

(i.e., the maximum absolute values of x(t) and y(t) are finite), then the system is stable. A necessary and sufficient condition is that h(t), the impulse response, satisfies

In the frequency domain, the region of convergence must contain the imaginary axis s = jω.

Discrete-time systems Almost everything in continuous-time systems has a counterpart in discrete-time systems.

Discrete-time systems from continuous-time systems In many contexts, a discrete time (DT) system is really part of a larger continuous time (CT) system. For example, a digital recording system takes an analog sound, digitizes it, possibly processes the digital signals, and plays back an analog sound for people to listen to. Formally, the DT signals studied are almost always uniformly sampled versions of CT signals. If x(t) is a CT signal, then an analog to digital converter will transform it to the DT signal x[n], with x[n] = x(nT), where T is the sampling period. It is very important to limit the range of frequencies in the input signal for faithful representation in the DT signal. Due to the sampling theorem, a DT signal can only contain a frequency range of 1 / (2T). Other frequencies are aliased to the same range.

Time invariance and linear transformation Let us start with a time-varying system whose impulse response is a two dimensional function and see how the condition of time-invariance helps us reduce it to one dimension. For example, suppose the input signal is x[n] where its index set is the integers, i.e., . The linear operator represents the system operating on the input signal. The appropriate operator for this index set is a two-dimensional function

Since is a linear operator, the action of the system on the input signal x[n] is a linear transformation represented by the following superposition sum

If the linear operator

If we let

then it follows that

is also time-invariant, then

We usually drop the zero second argument to h[n1,n2] for brevity of notation so that the superposition integral now becomes the familiar convolution sum used in filtering

Thus, the convolution sum represents the effect of a linear, time-invariant system on any input function. For a finite-dimensional analog, see the article on a circulant matrix.

Impulse response If we input a discrete delta function to this system, the result of the LTI transformation is known as the impulse response because the delta function is an ideal impulse. We illustrate this idea as follows:

(by the sifting property of the delta function). Note that

so that h[n] is the impulse response of the system. The impulse response can be used to find the response of any input in the following way. Again using the sifting property of the δ[n], we can write any input as a superposition of deltas:

Applying the system to the input,

(because

is linear and can pass inside the sum)

(because x[m] is constant in n and

is linear)

(by definition of h[n]) All information about the system is contained in the impulse response h[n].

Exponentials as eigenfunctions An eigenfunction is a function for which the output of the operator is the same function, just scaled by some amount. In symbols, , where f is the eigenfunction and λ is the eigenvalue, a constant. The exponential functions zn = esTn, where

, are eigenfunctions of a linear, time-

invariant operator. is the sampling interval, and simple proof illustrates this concept. Suppose the input is then

. The output of the system with impulse response h[n] is

which is equivalent to the following by the commutative property of convolution

, where

.A

is dependent only on the parameter z. So, zn is an eigenfunction of an LTI system because the system response is the same as the input times the constant H(z).

Z and discrete-time Fourier transforms The eigenfunction property of exponentials is very useful for both analysis and insight into LTI systems. The Z transform

is exactly the way to get the eigenvalues from the impuse response. Of particular interest are pure sinusoids, i.e. exponentials of the form ejωn, where . These can also be written as zn with z = ejω. These are generally called complex exponentials even though the argument is purely imaginary. The Discrete-time Fourier transform (DTFT) gives the eigenvalues of pure sinusoids. Both of H(z) and H(ejω) are called the system function, system response, or transfer function. The Z transform is usually used in the context of one-sided signals, i.e. signals that are zero for all values of t less than some value. Usually, this “start time” is set to zero, for convenience and without loss of generality. The Fourier transform is used for analyzing signals that are infinite in extent. Due to the convolution property of both of these transforms, the convolution that gives the output of the system can be transformed to a multiplication in the transform domain.

Not only is it often easier to do the transforms, multiplication, and inverse transform than the original convolution, one can gain insight into the behavior of the system from the system response. One can look at the modulus of the system function |H(z)| to see whether the input zn is passed (let through) by the system, or rejected or attenuated by the system (not let through).

Examples A simple example of an LTI operator is the delay operator D{x}[n]: = x[n − 1].

When the Z transform of the difference is taken, it transforms to a simple multiplication by z:

That the difference has such a simple Z transform partly explains the utility of the transform. Another simple LTI operator is an averaging operator

. It is linear because of the linearity of sums:

. It is time invariant too:

.

Important system properties Some of the most important properties of a system are causality and stability. Unlike CT systems, non-causal DT systems can be realized. It is trivial to make an acausal FIR system causal by adding delays. It is even possible to make acausal IIR systems (See Vaidyanathan and Chen, 1995). Non-stable systems can be built and can be useful in

many circumstances. Even non-real systems can be built and are very useful in many contexts. Causality Causal system

A system is causal if the output depends only on present and past inputs. A necessary and sufficient condition for causality is

where h[n] is the impulse response. It is not possible in general to determine causality from the Z transform, because the inverse transform is not unique. When a region of convergence is specified, then causality can be determined. Stability BIBO stability

A system is bounded input, bounded output stable (BIBO stable) if, for every bounded input, the output is finite. Mathematically, if

and

(i.e., the maximum absolute values of x[n] and y[n] are finite), then the system is stable. A necessary and sufficient condition is that h[n], the impulse response, satisfies

In the frequency domain, the region of convergence must contain the unit circle | z | = 1.

Fourier transform In mathematics, the Fourier transform is a certain linear operator that maps functions to other functions. Loosely speaking, the Fourier transform decomposes a function into a continuous spectrum of its frequency components, and the inverse transform synthesizes a function from its spectrum of frequency components. In mathematical physics, the Fourier transform of a signal can be thought of as that signal in the “frequency domain.” This is similar to the basic idea of the various other Fourier transforms including the Fourier series of a periodic function.

Definition Suppose is a complex-valued Lebesgue integrable function. The Fourier transform to the frequency domain, , is given by the function:

, for every real number

.

When the independent variable t represents time (with SI unit of seconds), the transform variable ω represents angular frequency (in radians per second).

Other notations for this same function are: and complex-valued in general. ( represents the imaginary unit.)

. The function is

If is defined as above, and is sufficiently smooth, then it can be reconstructed by the inverse transform:

, for every real number . The interpretation of

is aided by expressing it in polar coordinate form, , where: the amplitude the phase

Then the inverse transform can be written:

which is a recombination of all the frequency components of complex sinusoid of the form initial phase (at t = 0) is

. Each component is a

whose amplitude is proportional to

and whose

.

Normalization factors and alternative forms

The factors before each integral ensure that there is no net change in amplitude when one transforms from one domain to the other and back. The actual requirement is that their product be . When they are chosen to be equal, the transform is referred to as unitary. A common non-unitary convention is shown here:

As a rule of thumb, mathematicians generally prefer the unitary transform (for symmetry reasons), and physicists use either convention depending on the application.

The non-unitary form is preferred by some engineers as a special case of the bilateral Laplace transform. And the substitution: , where is ordinary frequency (hertz), results in another unitary transform that is popular in the field of signal processing and communications systems:

We note that the table below.

and

represent different, but related, functions, as shown in

Variations of all three forms can be created by conjugating the complex-exponential kernel of both the forward and the reverse transform. The signs must be opposites. Other than that, the choice is (again) a matter of convention.

Summary of popular forms of the Fourier transform

unitary angular frequency

(rad/s)

ordinary frequency

nonunitary

unitary

(hertz)

Generalization There are several ways to define the Fourier transform pair. The “forward” and “inverse” transforms are always defined so that the operation of both transforms in either order on a function will return the original function. In other words, the composition of the transform pair is defined to be the identity transformation. Using two arbitrary real constants a and b, the most general definition of the forward 1-dimensional Fourier transform is given by:

and the inverse is given by:

Note that the transform definitions are symmetric; they can be reversed by simply changing the signs of a and b.

The convention adopted in this article is (a,b) = (0,1). The choice of a and b is usually chosen so that it is geared towards the context in which the transform pairs are being used. The non-unitary convention above is (a,b) = (1,1). Another very common definition is (a,b) = (0,2π) which is often used in signal processing applications. In this case, the angular frequency ω becomes ordinary frequency f. If f (or ω) and t carry units, then their product must be dimensionless. For example, t may be in units of time, specifically seconds, and f (or ω) would be in hertz (or radian/s).

Properties In this section, all the results are derived for the following definition (normalization) of the Fourier transform:

Completeness We define the Fourier transform on the set of compactly-supported complex-valued functions of and then extend it by continuity to the Hilbert space of square-integrable functions with the usual inner-product. Then is a unitary operator. That is. and the transform preserves inner-products (see Parseval’s theorem, also described below). Note that, refers to adjoint of the Fourier Transform operator. Moreover we can check that,

where

and

is the Time-Reversal operator defined as,

is the Identity operator defined as,

Extensions The Fourier transform can also be extended to the space integrable functions defined on

where,

and

is the space of continuous functions on

.

In this case the definition usually appears as

where

and

is the inner product of the two vectors ω and x.

One may now use this to define the continuous Fourier transform for compactly supported smooth functions, which are dense in

The Plancherel theorem then

allows us to extend the definition of the Fourier transform to functions on (even those not compactly supported) by continuity arguments. All the properties and formulas listed on this page apply to the Fourier transform so defined. Unfortunately, further extensions become more technical. One may use the HausdorffYoung inequality to define the Fourier transform for

for

. The

p

Fourier transform of functions in L for the range requires the study of distributions, since the Fourier transform of some functions in these spaces is no longer a function, but rather a distribution.

The Plancherel theorem and Parseval’s theorem It should be noted that depending on the author either of these theorems might be referred to as the Plancherel theorem or as Parseval’s theorem. If f(x) and g(x) are square-integrable and F(ω) and G(ω) are their Fourier transforms, then we have the Parseval’s theorem:

where the bar denotes complex conjugation. Therefore, the Fourier transformation yields an isometric automorphism of the Hilbert space

.

The Plancherel theorem, a special case of the Parseval’s theorem, states that

This theorem is usually interpreted as asserting the unitary property of the Fourier transform. See Pontryagin duality for a general formulation of this concept in the context of locally compact abelian groups.

Localization property As a rule of thumb: the more concentrated f(x) is, the more spread out is F(ω). In particular, if we “squeeze” a function in x, it spreads out in ω and vice-versa; and we cannot arbitrarily concentrate both the function and its Fourier transform. Therefore a function which equals its Fourier transform strikes a precise balance between being concentrated and being spread out. It is easy in theory to construct examples of such functions (called self-dual functions) because the Fourier transform has order 4 (that is, iterating it four times on a function returns the original function). The sum of the four iterated Fourier transforms of any function will be self-dual. There are also some explicit examples of self-dual functions, the most important being constant multiples of the Gaussian function

This function is related to Gaussian distributions, and in fact, is an eigenfunction of the Fourier transform operators. The trade-off between the compaction of a function and its Fourier transform can be formalized. Suppose f(x) and F(ω) are a Fourier transform pair. Without loss of generality, we assume that f(x) is normalized:

It follows from Parseval’s theorem that F(ω) is also normalized. Define the expected value of a function A(x) as:

and the expectation value of a function B(ω) as:

Also define the variance of A(x) as:

and similarly define the variance of B(ω). Then it can be shown that

The equality is achieved for the Gaussian function listed above, which shows that the gaussian function is maximally concentrated in “time-frequency”. The most famous practical application of this property is found in quantum mechanics. The momentum and position wave functions are Fourier transform pairs to within a factor of and are normalized to unity. The above expression then becomes a statement of the Heisenberg uncertainty principle. The Fourier transform also translates between smoothness and decay: if f(x) is several times differentiable, then F(ω) decays rapidly towards zero for .

Analysis of differential equations Fourier transforms, and the closely related Laplace transforms are widely used in solving differential equations. The Fourier transform is compatible with differentiation in the following sense: if f(x) is a differentiable function with Fourier transform F(ω), then the Fourier transform of its derivative is given by iω F(ω). This can be used to transform differential equations into algebraic equations. Note that this technique only applies to problems whose domain is the whole set of real numbers. By extending the Fourier transform to functions of several variables (as outlined below), partial differential equations with domain ) can also be translated into algebraic equations.

Convolution theorem Convolution theorem The Fourier transform translates between convolution and multiplication of functions. If f(x) and h(x) are integrable functions with Fourier transforms F(ω) and H(ω) respectively, and if the convolution of f and h exists and is absolutely integrable, then the Fourier transform of the convolution is given by the product of the Fourier transforms F(ω)H(ω) (possibly multiplied by a constant factor depending on the Fourier normalization convention). In the current normalization convention, this means that if

where * denotes the convolution operation; then

The above formulas hold true for functions defined on both one- and multi-dimension real space. In linear time invariant (LTI) system theory, it is common to interpret h(x) as the impulse response of an LTI system with input f(x) and output g(x), since substituting the unit impulse for f(x) yields g(x) = h(x). In this case, H(ω) represents the frequency response of the system. Conversely, if f(x) can be decomposed as the product of two other functions p(x) and q(x) such that their product p(x)q(x) is integrable, then the Fourier transform of this product is given by the convolution of the respective Fourier transforms P(ω) and Q(ω), again with a constant scaling factor. In the current normalization convention, this means that if

then

Cross-correlation theorem In an analogous manner, it can be shown that if g(x) is the cross-correlation of f(x) and h(x):

then the Fourier transform of g(x) is:

where capital letters are again used to denote the Fourier transform.

Tempered distributions The most general and useful context for studying the continuous Fourier transform is given by the tempered distributions; these include all the integrable functions mentioned

above and have the added advantage that the Fourier transform of any tempered distribution is again a tempered distribution and the rule for the inverse of the Fourier transform is universally valid. Furthermore, the useful Dirac delta is a tempered distribution but not a function; its Fourier transform is the constant function . Distributions can be differentiated and the above mentioned compatibility of the Fourier transform with differentiation and convolution remains true for tempered distributions.

Table of important Fourier transforms The following table records some important Fourier transforms. G and H denote Fourier transforms of g(t) and h(t), respectively. g and h may be integrable functions or tempered distributions. Note that the two most common unitary conventions are included.

Functional relationships

Signal

Fourier transform unitary, angular frequency

Fourier transform unitary, ordinary frequency

Remarks

1

Linearity

2

Shift in time domain

3

Shift in frequency domain, dual of 2

If 4

is large, then

is concentrated around 0 and

spreads out and flattens. It is interesting to consider the limit of this as | a | tends to infinity - the delta function

5

Duality property of the Fourier transform. Results from swapping “dummy” variables of and .

6

Generalized derivative property of the Fourier transform

7

This is the dual of 6

8

denotes the convolution of and — this rule is the convolution theorem

9

This is the dual of 8

Square-integrable functions Signal

Fourier transform

Fourier transform

Remark

unitary, angular frequency

unitary, ordinary frequency

10

The rectangula pulse and t normalized sinc functi

11

Dual of rul 10. The rectangula function is idealized low-pass filter, and t sinc functi is the noncausal impulse response o such a filte

12

tri is the triangular function

13

Dual of rul 12.

14

Shows that the Gaussi function ex

− αt2) is its own Fouri transform. For this to integrable must have Re(α) > 0.

15

common in optics

16

17

18

a>0

19

the transfo is the function it

20

J0(t) is the Bessel function of first kind o order 0

21

it’s the generalizat of the previous

transform; (t) is the Chebyshev polynomia the first kin

Un (t) is th Chebyshev polynomia the second kind

22

Distributions

Signal

23

Fourier transform unitary, angular frequency

Fourier transform unitary, ordinary frequency

Remarks

δ(ω) denotes the Dirac delta distribution. This rule shows why the Dirac delta is important: it shows up as the Fourier transform of a constant function.

24

Dual of rule 23.

25

This follows from and 3 and 24.

26

Follows from rules 1 and 25 using Euler’s formula: cos(at) = (eiat + e − iat) / 2.

27

Also from 1 and 25.

28

Here, n is a natural number. δn(ω) is the n-th distribution derivative of the Dirac delta. This rule follows from rules 7 and 24. Combining this rule with 1, we can transform all polynomials.

29

Here sgn(ω) is the sign function; note that this is

consistent with rules 7 and 24.

30

Generalization of rule 29.

31

The dual of rule 29.

32

Here u(t) is the Heaviside unit step function; this follows from rules 1 and 31.

33

u(t) is the Heaviside unit step function and a > 0.

34

The Dirac comb — helpful for explaining or understanding the transition from continuous to discrete time.

Fourier transform properties Notation: Conjugation

denotes that f(x) and F(ω) are a Fourier transform pair.

Scaling

Time reversal Time shift Modulation (multiplication by complex exponential)

Multiplication by sin ω0t

Multiplication by cos ω0t

Integration

Parseval’s theorem

Signal (electrical engineering) In the fields of communications, signal processing, and in electrical engineering more generally, a signal is any time-varying quantity. Signals are often scalar-valued functions of time (waveforms), but may be vector valued and may be functions of any other relevant independent variable. The concept is broad, and hard to define precisely. Definitions specific to subfields are common. For example, in information theory, a signal is a codified message, ie, the sequence of states in a communications channel that encodes a message. In a communications system, a transmitter encodes a message into a signal, which is carried to a receiver by the communications channel. For example, the words “Mary had a little lamb” might be the message spoken into a telephone. The telephone transmitter converts the sounds into an electrical voltage signal. The signal is transmitted to the receiving telephone by wires; and at the receiver it is reconverted into sounds. Signals can be categorized in various ways. The most common distinction is between discrete and continuous spaces that the functions are defined over, for example discrete and continuous time domains. Discrete-time signals are often referred to as time series in other fields. Continuous-time signals are often referred to as continuous signals even when the signal functions are not continuous; an example is a square-wave signal. A second important distinction is between discrete-valued and continuous-valued. Digital signals are discrete-valued, but are often derived from an underlying continuous-valued physical process.

Discrete-time and continuous-time signals If for a signal, the quantities are defined only on a discrete set of times, we call it a discrete-time signal. In other words, a discrete-time real (or complex) signal can be seen as a function from the set of integers to the set of real (or complex) numbers. A continuous-time real (or complex) signal is any real-valued (or complex-valued) function which is defined for all time t in an interval, most commonly an infinite interval.

Analog and digital signals Less formally than the theoretical distinctions mentioned above, two main types of signals encountered in practice are analog and digital. In short, the difference between them is that digital signals are discrete and quantized, as defined below, while analog signals possess neither property.

Discretization Discrete signal One of the fundamental distinctions between different types of signals is between continuous and discrete time. In the mathematical abstraction, the domain of a continuous-time (CT) signal is the set of real numbers (or some interval thereof), whereas the domain of a discrete-time signal is the set of integers (or some interval). What these integers represent depends on the nature of the signal. DT signals often arise via of CT signals. For instance, sensors output data continuously, but since a continuous stream may be difficult to record, a discrete-time signal is often used as an approximation. Computers and other digital devices are restricted to discrete time.

Quantization Quantization (signal processing) If a signal is to be represented as a sequence of numbers, it is impossible to maintain arbitrarily high precision - each number in the sequence must have a finite number of digits. As a result, the values of such a signal are restricted to belong to a finite set; in other words, it is quantized.

Examples of signals •

•

•

•

•

Motion. The motion of a particle through some space can be considered to be a signal, or can be represented by a signal. The domain of a motion signal is onedimensional (time), and the range is generally three-dimensional. Position is thus a 3-vector signal; position and orientation is a 6-vector signal. Sound. Since a sound is a vibration of a medium (such as air), a sound signal associates a pressure value to every value of time and three space coordinates. A microphone converts sound pressure at some place to just a function of time, using a voltage signal as an analog of the sound signal. Compact discs (CDs). CDs contain discrete signals representing sound, recorded at 44,100 samples per second. Each sample contains data for a left and right channel, which may be considered to be a 2-vector (since CDs are recorded in stereo). Pictures. A picture assigns a color value to each of a set of points. Since the points lie on a plane, the domain is two-dimensional. If the picture is a physical object, such as a painting, it’s a continuous signal. If the picture a digital image, it’s a discrete signal. It’s often convenient to represent color as the sum of the intensities of three primary colors, so that the signal is vector-valued with dimension three. Videos. A video signal is a sequence of images. A point in a video is identified by its position (two-dimensional) and by the time at which it occurs, so a video signal has a three-dimensional domain. Analog video has one continuous domain dimension (across a scan line) and two discrete dimensions (frame and line).

•

Biological membrane potentials. The value of the signal is a straightforward electric potential (“voltage”). The domain is more difficult to establish. Some cells or organelles have the same membrane potential throughout; neurons generally have different potentials at different points. These signals have very low energies, but are enough to make nervous systems work; they can be measured in aggregate by the techniques of electrophysiology.

Frequency analysis Frequency domain It is often useful to analyze the frequency spectrum of a signal. This technique is applicable to all signals, both continuous-time and discrete-time. For instance, if a signal is passed through an LTI system, the frequency spectrum of the resulting output signal is the product of the frequency spectrum of the original input signal and the frequency response of the system.

Entropy Another important property of a signal (actually, of a statistically defined class of signals) is its entropy or information content.