At the bottom is the digital logic level, which
is the computer's real hardware. This is a building block for the higher
levels. A digital circuit is one in which only two logical values are
present. A signal between 0 and 1 volt represents one value (binary 0)
and one between 2 and 5 volts represents the other value (binary 1).
Voltages outside these ranges are not permitted. Tiny electronic devices,
called gates, can compute various functions of these two-valued
signals. These gates form the hardware basis on which all digital
computers are built. Device level explains the operation of the
gates. A transistor can be made to operate as a very fast binary switch.
The figure above is a representation of a bipolar transistor (the circle) embedded in a simple circuit. A typical transistor has three connections to the outside world: the collector, the base, and the emitter. When the input voltage, Vin , is below a certain critical value, the transistor turns off and acts like an infinite resistor. This causes the output of the circuit, Vout, to take on a value close to Vcc, an externally regulated voltage, typically +5 volts. When Vin exceeds the critical value, the transistor switches on and acts like a wire, causing Vout to be pulled to ground (by convention, 0 volts). So when Vin is low, Vout is high, and vice versa. This circuit is thus an inverter, converting a logical 0 to a logical 1, and a logical 1 to a logical 0. A resistor is located in the connection to Vcc to limit the current drawn by the transistor to prevent it from burning out. The time required to switch from one state to another is a few nanoseconds. This is known as a NOT gate. Transistors can be combined. If there are two transistors, there will be two inputs V1 and V2 rather than just one Vin. If they are in series, We have a NAND gate. In this case, if both Vin and V2 are high, both transistors will conduct and Vout will be low. If either input is low, the corresponding transistor will turn off, and the output will be high. So, Vout will be low if and only if both inputs are high. If the transistors are arranged in parallel, we have a NOR gate. if either input is high, the corresponding transistor will turn on and pull the output down to the ground. If both inputs are low, the output will remain high.
These three circuits, NOT (inverters), NAND, and NOR form the three simplest gates. The convention is that "high" (Vcc volts) is a logical 1, and "low" (ground) is a logical 0. The output values can be expressed as a function of input values. In the table below, A and B are inputs, and X is the output.
|
|
Gates can combined by Boolean algebra named after George Boole
|
|
NOT |
NAND |
NOR |
AND |
OR |
XOR |
|
A |
X |
A |
B |
X |
A |
B |
X |
A |
B |
X |
A |
B |
X |
A |
B |
X |
|
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
|
|
|
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
|
|
|
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
NOT gates require one transistor, NAND and NOR gates require two transistors each. AND gates are made by combining a NAND and a NOT gate, and OR combining a NOR and a NOT gate. So AND and OR gates need three transistors each. Hence NAND and NOR gates are simpler than AND and OR gates. NOT gates have only one input. All the other gates need at least two inputs. They can have any number greater than two but in practice, the largest number of inputs is eight. XOR gates must have exactly two outputs. All gates have only one output.
The AND gate implements the Boolean AND function where the output only is
logical 1 when all inputs are logical 1.
The standard symbol and the truth table for a two input AND gate is:
|
|
B |
R |
|
0 |
0 |
0 |
|
0 |
1 |
0 |
|
1 |
0 |
0 |
|
1 |
1 |
1 |
AThe Boolean expression for the AND gate is
R=A.B
The OR gate implements the Boolean OR function where the output is logical 1
when just input is logical 1.
The standard symbol and the truth table for a two input OR gate is:
|
A |
B |
R |
|
0 |
0 |
0 |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
|
1 |
1 |
1 |
The Boolean expression for the OR gate is:
R=A+B
The NOT gate implements the Boolean NOT function where the output is the
inverse of the input
The standard symbol and the truth table for the NOT
gate is:
|
|
R |
|
0 |
1 |
|
1 |
0 |
A
The Boolean expression for the NOT gate is:
R=-A
From these three basic logical gates is it possible to
implement any Boolean expression into hardware. Some simple combination of
these gates have got there own names and symbol. Some of these are the NAND
gate and the NOR gate.
THE NAND GATE
The NAND gate is an AND gate followed by a NOT gate. The output is logical 1
when one of the inputs are logical 0
The standard symbol and the truth table for the NAND gate is:
|
A |
B |
R |
|
0 |
0 |
1 |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
|
1 |
1 |
0 |
The Boolean expression for the NAND gate is
R=-(A.B)
The NOR is a combination of an OR followed by a NOT gate. The output is
logical 1 when non of the inputs are logical 0
The standard symbol and the truth table for the NOR gate is:
|
A |
B |
R |
|
0 |
0 |
1 |
|
0 |
1 |
0 |
|
1 |
0 |
0 |
|
1 |
1 |
0 |
The Boolean expression for the NOR gate is
R=-(A+B)
POST TEXT:
The gates (except the NOT gate) just described comes with a varies numbers of
input, we have only shown the standard symbols for gates with two but you do
also get them with three and four inputs as standard components.
For more information on Boolean and digital logic, click below.
The truth table for a Boolean function of three variables showing the
majority function (0 if majority of inputs is 0, 1 otherwise) is:
|
A |
B |
C |
M |
|
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
|
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
1 |
|
1 |
0 |
0 |
0 |
|
1 |
0 |
1 |
1 |
|
1 |
1 |
0 |
1 |
|
1 |
1 |
1 |
1 |
We need 3 NOT gates, 4 AND gates, and 1 OR gate for this function. The 3 inputs A, B, and C are converted into 6 with the NOT gates. Four combinations of the inputs make M as 1. We place a bar over an input variable if its value is inverted Implied multiplication or a dot means Boolean AND and addition or + is a Boolean OR.
Component cost, printed circuit board space, power consumption, etc., can be
reduced by reducing the number of gates. Boolean algebra is used to
accomplish this. Many rules of ordinary algebra are true for Boolean
algebra, e.g., AB + AC = A(B + C) as shown below, but
is better as it contains fewer gates, 1 AND and 1 OR,
against 2 ANDs and 1 OR.
|
A |
B |
C |
AB |
AC |
AB + AC |
B + C |
A(B + C) |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
|
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Some Boolean algebra identities:
|
Name |
AND form |
OR form |
|
Identity law |
1A = A |
0 + A = A |
|
Null law |
0A = 0 |
1 + A = 1 |
|
Idempotent law |
AA = A |
A + A = A |
|
Inverse law |
A(NOT A) = 0 |
A + NOT A = 1 |
|
Commutative law |
AB = BA |
A + B = B + A |
|
Associative law |
(AB)C = A(BC) |
(A + B) + C = A + (B + C) |
|
Distributive law |
A + BC = (A + B)(A + C) |
A(B + C) = AB + AC |
|
Absorption law |
A(A + B) = A |
A + AB = A |
|
De Morgan's law |
NOT AB = NOT A + NOT B |
NOT (A + B) = (NOT A)(NOTB) |
Augustus
De Morgan
BASIC DIGITAL LOGIC CIRCUITS
Integrated Circuits
Gates are manufactured and sold in units called Integrated Circuits, ICs, or chips, a square piece of silicon about 5 mm x 5 mm on which some gates have been deposited. Small ICs are mounted in rectangular plastic or ceramic packages measuring 5 to 15 mm wide and 20 to 50 mm long. Along the long edges are two parallel rows of pins about 5 mm long that can be inserted into sockets or soldered to printed circuit boards. Each pin connects to the input or output of some gate on the chip or to power or to ground. The package with two rows of pins outside and ICs inside are known as Dual Inline Packages or DIPs, but are also called chips. Packages have 14, 16, 18, 20, 22, 24, 28, 40, 64, or 68 pins. Square packages with pins on all four sides are also used. Chips are divided into classes based on the number of gates:
SSI (Small Scale Integrated) circuit: 1
to 10 gates.
MSI (Medium Scale Integrated) circuit: 10
to 100 gates.
LSI (Large Scale Integrated) circuit: 100
to 100,000 gates.
VLSI (very Large Scale Integrated)
circuit: > 100,000 gates.
Many chips are available for a few cents each. Each SSI has a handful of gates and up to 20 or so pins. An entire CPU and a substantial amount of (cache) memory is etched on to a single chip. Gates are ideal as output appears as soon as input is applied. There is a gate delay of 1 to 10 nsec which includes both the signal propagation time through the chip and the switching time. We can put almost 10 million transistors on a chip. As any circuit can be built up by NAND gates, we could have a chip containing 5 million NAND gates. But we would need 15,000,002 pins (3 pins per gate, and 1 for power and 1 for ground). With the standard pin 0.1 inch, the chip would be 1.5 x106 inches = 23.6 miles. It is best to design circuits with a high gate to pin ratio.
A Combinational Circuit is a circuit with multiple inputs and multiple outputs in which the outputs are determined by current inputs. Non combinational circuits include circuits containing memory elements that generate outputs that depend on the stored values and input values.
Multiplexers
A multiplexer is a circuit with 2n data inputs, one data output, and n control inputs that select one of the data inputs. The selected data input is "gated" (routed) to the output. We need n NOT gates, 2n AND gates, and 1 OR gate. Each AND gate is enabled by a different combination of the control inputs. No matter what value is on the control lines, 2n - 1 AND gates will always output 0; the other one may output either 0 or 1, depending on the value of the selected input line. With 3 control lines, and 8 input lines, power and ground, it can be packaged in a 14-pin package (8 input, 3 control, 1 output, power, and ground). The multiplexer can be used for majority function. Any truth table of three variables an be implemented. The inverse of a multiplexer is a demultiplexer, which routes its single input signal to one of 2n outputs, depending on the value of the n control lines.
A decoder is a circuit that takes an n-bit number as input and uses it to select (set to 1) exactly one of the 2n output lines. This chip requires NOT gates and 2n AND gates. Each AND gate has n inputs and is enabled by a different combination of inputs.
Comparators
A Comparator compares two input words, and produces 1 if they are equal and 0 if not. If there are four words, it requires 4 XOR (Exclusive Or) gates and 1 NOR gate. In this case, 1 means equal, 0 means unequal.
Programmable Logic Arrays
Arbitrary functions (truth tables) can be constructed by computing product terms with AND gates and the ORing the products together. A very general chip for forming the sums of products is the Programmable Logic Arrays or PLAs. This chip has input lines for n variables. The complement of each input is generated internally, making 2n input signals in all. The heart of the circuit is an array of m AND gates, each of which can potentially have any subset of the 2n input signals as an input. Which input signal goes to which AND gate is determined by a 2n x m bit matrix supplied by the user. Each input to the m AND gates contains a fuse. When shipped all 2n x m fuses are intact. To program the matrix the user burns out selected fuses by applying a high voltage to the chip. The output part of the circuit consists of r OR gates, each of which has up to m inputs, corresponding to the m outputs of the AND gates. If n = 12, m = 50, and r = 6, then there are 12 input pins, 6 output pins, ground and power for a total of 20 pins.
Shifters
n bits of input are on lines D0, ... Dn. The output, which is the input shifted 1 bit is on lines S0, ... Sn. The control line, C, determines the direction of the shift, 0 for left, 1 for right. There are a pair of AND gates for all the bits except the gates on the end. When C = 1, the right member of each pair is turned on. As the right AND gate is wired to the input of the OR gate to its right, a right shift is performed. If C = 0, it is the left member of the AND gate pair that turns on, doing a left shift.
Adders
Half adder
Here there is a carry out but no carry in. The XOR gate performs the
sum and the AND gate has the carry out. The truth table is shown:
|
A |
B |
Sum |
Carry |
|
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
0 |
|
1 |
0 |
1 |
0 |
|
1 |
1 |
0 |
1 |
Full Adder
This has a carry in as well as a carry out. This has 2 XOR gates, 2
AND gate and 1 OR gate. The sum output line is 1 if an odd number of A,
B, and the Carry in are 1. The carry out is 1 if either A and B are both 1 (left input to the OR gate) or exactly
one of them is 1 and the Carry in bit is also 1. The truth table is:
|
A |
B |
Carry in |
Sum |
Carry out |
|
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
0 |
|
0 |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
1 |
|
1 |
0 |
0 |
1 |
0 |
|
1 |
0 |
1 |
0 |
1 |
|
1 |
1 |
0 |
0 |
1 |
|
1 |
1 |
1 |
1 |
1 |
An Arithmetic Logic Unit (ALU) can compute any one of four functions, A AND B, A OR B, NOT B, or A + B, depending on whether the function-select input line contain 00, 01, 10, or 11 (binary). A + B is the arithmetic sum not OR.
Clocks
The order in which events happen is critical. Sometimes one event must precede another, sometimes two events must occur simultaneously. To allow designers to achieve the timing relations, digital circuits use clocks to provide synchronization. A clock is a circuit that emits a series of pulses with a precise pulse width and a precise interval between consecutive pulses. The time interval between the corresponding edges of two consecutive pulses is the clock cycle time. Pulse frequencies are between 1 and 500 MHz, corresponding to clock cycles of 1000 nsec to 2 nsec. For high accuracy, it is controlled by a crystal oscillator.
The clock cycle is divided into subcycles. The primary clock line is first tapped, then a circuit with a known delay is inserted, generating a secondary clock signal that s phase-shifted from the primary. There are now four time references for discrete events:
1. Rising edge of the primary clock.
2. Falling edge of the primary clock.
3. Rising edge of the secondary clock.
4. Falling edge of the secondary clock.
By tying different events to the various edges, the required sequencing can be achieved.
Latches
We need a circuit that "remembers" previous input values. It can be constructed from two NOR gates. An SR latch has two inputs, S, for setting the latch, and, R, for resetting (clearing) it. It has two outputs Q, and NOT Q, which are complementary. When both S and R = 0, if Q = 0, feeding it into a NOR gate, with the output NOT Q becomes 1. Feeding this into another NOR gate causes Q to remain 0 which is consistent. If q becomes 1 when both R and S are still 0, NOT Q becomes 0 and so it is still consistent. A state with both outputs = 0 is inconsistent, as both inputs Q and NOT Q become 0. Similarly if both are 1. So for R = S = 0, there are two stable states 0 and 1 depending on Q. If S becomes 1 while Q is still 0. Not Q will also become 0. This causes the output to be 1. Thus setting S (making it 1) switches the state from 0 to 1
Clocked SR latches
The latch is prevented from changing state except at certain specified times by a clocked SR latch. With the clock 0, connected to AND gates, both output 0 independent of S and R, and the latch does not change state. When the clock is 1, the latch becomes sensitive to S and R. The terms enable and strobe are also used to mean that the clock input is 1.
Clocked D latch
If both S and R = 1, then both Q and NOT Q will become 0. The latch must jump to one of its two stable states. If either input drops back to 0 before the other, the one remaining 1 longest wins. If both inputs return to 0 simultaneously, the latch jumps to one of its stable states at random. To prevent this, S and R are replaced by D and NOT D. The circuit requires 11 transistors.
Flip-Flops
In a flip-flop, the state transition does not occur when the clock is 1, but during the clock transition from 0 to 1 (rising edge) or from 1 to 0 (falling edge) instead. So the length of the clock pulse is unimportant, as long as the transition occurs fast. A flip-flop is edge triggered while a latch is level triggered.
Consider a memory with four 3-bit words. Each operation reads or writes a full 3-bit word, with a total memory capacity of 2 bits. It has eight input lines and three output lines. Three inputs are data: I0, I1, and I2; two are for addresses: A0, and A1; and three are for control: CS for chip select, RD to distinguish between read and write, and OE for Output Enable. The three outputs are for data: O0, O1, and O2. It would require 14 pins including power and ground. CS is set high. RD is 1 for read and 0 for write. Address lines indicate which of the four 3-bit words is to be read and written. For a read operation, the data input lines are not used, nut the word select is placed on the data output lines. For a write operation, the bits present on the data input lines are loaded into the selected memory word; the data output lines are not used.
RAMs and ROMs
Random Access Memory
RAMs (Random Access Memory) come in two varieties
Static (SRAMs) and Dynamic (DRAMs). Static RAMs are
constructed internally using D flip-flop circuits. The memory is retained
as long as power is on. They are fast with an access time of a few nsec. They are popular for level 2 cache
memory. Dynamic RAM is an array of cells, each one containing oe transistor and a tiny capacitor, which can be charged or
discharged. As the electric charge leaks out, it must be refreshed (reloaded)
every few milliseconds t prevent the data from leaking away. They are
more complex but have larger capacities.
Read Only Memory
ROMs (Read Only Memory) the data
or the program cannot be changed or erased. The data is stored even when
the power is turned off. The data is inserted during manufacture by
exposing a photosensitive material through a mask containing the desired bit pattern
and then etching away the exposed (or unexposed) surface. The
only way to change the program is to replace the entire chip. PROM (Programmable
ROM) can be programmed once in the field. They contain an array of tiny
fuses. A specific fuse can be blown out by selecting its row and column,
and then applying a high voltage to a special pin on the chip. EPROM (Erasable
PROM) can in addition be field erased, when the quartz window is exposed to
strong ultraviolet light for 15 minutes All
the bits are set to 1. EEPROM can be erased by applying pulses,
and can be reprogrammed in place. But they are only 1/64 as large as EPROMs. They are 10 times slower, 100 times smaller
and more expensive than DRAMs or SRAMs.
Flash memory is block erasable and rewritable.
|
Type |
Category |
Erasure |
Byte alterable |
Volatile |
Typical use |
|
SRAM |
Read/write |
Electrical |
Yes |
Yes |
Level 2 cache |
|
DRAM |
Read/write |
Electrical |
Yes |
Yes |
Main memory |
|
ROM |
Read-only |
Not possible |
No |
No |
Large volume appliances |
|
PROM |
Read-only |
Not possible |
No |
No |
Small volume equipment |
|
EPROM |
Read-mostly |
UV light |
No |
No |
Device prototyping |
|
EEPROM |
Read-mostly |
Electrical |
Yes |
No |
Device prototyping |
|
Flash |
Read/write |
Electrical |
No |
No |
Film for digital camera |
CPU Chips
All modern CPUs are contained on a single chip, making their interaction with the rest of the system well defined. Each CPU chip has a set of pins, through which all its communication with the outside world takes place. Some pins output signals from the CPU; others accept signals from outside; some can do both. These pins are connected to similar pins on the memory and I/O chips via a collection of parallel wires called a bus. To fetch an instruction, the CPU first puts the memory address of that instruction on its address pins. Then it asserts one or more control lines to inform the memory that, for example, it wants to read a word. The memory replies by putting the requested word on the CPU's data pins and asserting a signal saying that it is done. When the CPU sees this signal, it accepts the word and carries out the instruction.
Two of the key parameters that determine the performance of the CPU are the number of address pins and the number of data pins. A chip with m address pins can address up to 2m memory locations. Common values of m are 8, 16, 32, 36, and 64. A CPU with 8 data pins will need four operations to read a 32-bit word, whereas one with 32 data pins can do it in one operation, which is faster but more expensive.
In addition a CPU has some control pins, which regulate the flow and timing of data from the CPU and also undertake miscellaneous tasks. They also have pins for power, ground, and for a clock signal. Control pins are grouped into six categories:
1. Bus control, outputs from the CPU to the bus (inputs to memory and I/O chips). The determine whether the CPU wants to read or write memory or do something else. The CPU uses these pins to control the rest of the system and tell it what it wants to d. They are two output and one input pins.
2. Interrupts are inputs from I/O devices to the CPU. The CPU can tell the I/O device to start an operation and do something else while the I/O is doing its work. When this is completed, the I/O controller chip asserts a signal on one of these pins to interrupt the CPU for its service. There are two input pins. Some may have an additional output pin to acknowledge the interrupt signal.
3. Bus arbitration needed to regulate traffic on the bus, in order to prevent two devices from trying to use it at the same time. One input and one output pin. The CPU is also considered as a device.
4. Coprocessor signaling to operate with coprocessors such as floating point chips, graphics, etc. Two input and one input pins.
5. Status to provide or accept status information. Two output pins.
6. Miscellaneous to reset the computer and for compatibility with older I/O chips. Two input pins.
A bus is a common electric pathway between multiple devices.
They could be internal to the CPU to transport data to and from the ALU, or
external to the CPU to connect it to memory ot to I/O devices. Active ones called masters
can initiate bus transfers. Passive ones called slaves wait
for requests. When the CPU orders a disk controller to read or write a
block, the CPU is the master and the disk controller is a slave. The disk
controller is a master when it commands the memory to accept the words.
Memory can never be a master.
|
Master |
Slave |
Example |
|
CPU |
Memory |
Fetching instructions and data |
|
CPU |
I/O device |
Initiating data transfer |
|
CPU |
Coprocessor |
CPU handing instruction off to coprocessor |
|
I/O |
Memory |
DMA (Direct Memory Access) |
|
Coprocessor |
CPU |
Coprocessor fetching operands from CPU |
Bus Width
The more address lines a bus has, the more memory the CPU can address directly. If a bus has n address lines, then the CPU can address 2n different memory locations. Wide buses need more wires and physical space on the motherboard than narrow ones. A system with a 64-line address bus and 232 bytes of memory will cost more than one with 32 address lines and 232 bytes of memory. The original IBM PC had a 20-bit address allowing 1 MB memory. To increase address space to 4 MB, four more bus lines were added without disturbing the original 20 for backward compatibility. Later another 8 address lines were added.
Bus Clocking
A synchronous bus has a line driven by a crystal oscillator. The signal is a square wave with a frequency between 5MHz and 100MHz. All bus activities take an integral number of these cycles called bus cycles. Everything works in multiples of the bus clock If a CPU and a memory are able to complete a transfer in 3.1 cycles, they have to stretch it to 4.0 because fractional cycles are forbidden. Once a bus cycle has been chosen, and memory and I/O cards have been built for it, it is difficult to take advantage of future improvements in technology. If a synchronous bus has a heterogeneous collection of devices, some fast and some slow, the bus has to be geared to the slowest one and the fast ones cannot use their full potential.
An Asynchronous bus does not have a master clock. Bus cycles can be of any length required and need not be the same between all pairs of devices. A set of signals interlock in what is called a full handshake which is timing independent. Each event is caused by a prior event, not by a clock pulse. If a particular master-slave pair is slow, that in no way affects a subsequent master-slave pair that is much faster.
Although there is many advantages to a synchronous bus, most buses are synchronous as they are easier to build. The CPU asserts its signal and the memory reacts. There is no feedback. Finally there is a lot of investment in synchronous bus technology.
Bus Arbitration
I/O chips have to become bus masters to read and write memory. Coprocessors also become bus masters. Bus arbitration prevent chaos if two or more devices want to become bus masters at the same time. In centralized bus arbitration, a single bus arbiter determines who goes next. The bus contains a single wired-OR request line that can be asserted by ne or more devices at any time. When the arbiter sees a bus request, it issues a grant by asserting the bus grant line. When the device physically closest to the arbiter sees the grant, it checks to see if it made a request. If so, it takes over the bus. If not, it propagates the grant to the next device in line, which behaves the same way, until some device accepts the grant and takes the bus. This scheme is called daisy chaining. Devices are assigned priorities depending on how close they are to the arbiter. Buses can have multiple priority levels. CPU gets the lowest priority. CPU can wait, but I/O devices must acquire the bus quickly or lose incoming data. For each priority level there is a bus request line and a bus grant line. Each device attaches to one of the bus request levels, with more critical devices attaching to the higher priority ones. If multiple priority levels are requested at the same time, the arbiter issues a grant only on the highest priority one. Among devices with the same priority, daisy chaining is used.
In decentralized bus arbitration, when a device wants to use the bus, it asserts its request line. All devices monitor all the request lines, so at the end of each bus cycle, each device knows whether it was the highest priority requester, and can use the bus during the next cycle. It requires more bus lines but no arbiter. It limits the number of devices to the number of request lines. Another method is to use just three lines, no matter how many devices are present. The first bus line is a wired-OR line for requesting the bus. The second bus line is called BUSY and is asserted by the current bus master. The third line is used to arbitrate the bus. It is daisy chained through all the devices. The head of this chain is held asserted by tying it to the 5-volt power supply. When no device wants the bus, the asserted line is propagated through to all the devices. To acquire the bus, a device first checks to see if the bus is idle and the arbitration signal it is receiving, IN, is asserted. If IN is negated, it may not become the bus master, and it negates OUT. If IN is asserted, the device negates OUT, which causes its downstream neighbor to see IN negated and to negate its OUT. All downstream devices follow. Only one device will have IN asserted and OUT negated. This device becomes bus master, asserts BUSY and OUT, and begins its transfer. The leftmost device that wants the bus gets it. It is similar to the daisy chain, without the arbiter, so it is cheaper, faster, and not subject to arbiter failure.
For problems and solutions, look at the first page.