As with the decoder , the multiplexer circuit is not inherently hazard free , but , with a maximum of one inverter signal path difference , no glitches should be seen and the advantages of flexibility and design speed still apply .sx For a logic system where many outputs are formed from the same set of input signals , a decoder-based system requires one OR gate for each output and one decoder to supply all the basic addresses .sx With a multiplexer circuit , a separate MUX is needed for each function .sx 3.6 PARITY .sx The parity of a binary word is defined as even if the number of bits set to 1 is even , and odd if the number of bits set to 1 is odd .sx A parity bit is a bit added to a binary word to make the parity of the word plus the bit the same for all words in the data set .sx Parity bits are added to data before storage or transmission so that the integrity of the data can be checked and corrected on retrieval or reception ; if the parity has changed then an error has occurred .sx For systems which transfer or store data as parallel words it is normal to add a parity bit which makes the combined word odd parity as this ensures that at least one bit is 1 , and it is easy to detect the difference between a data value of 0 and no data .sx For serial transmission or storage , start and stop bits are used to delimit a data word , and so either parity type can be employed .sx Table 3.1 lists the parity of binary numbers from 0 to 9 and the codes for the numbers plus parity bits to produce odd and even parity words .sx Most systems which use parity assume that any errors are single-bit errors and that they occur only rarely .sx In the simplest scheme , one parity bit is added to each word , so that if an error occurs ( a 1 is changed to a 0 , or a 0 to a 1 ) , the parity of the word is changed and this can be detected ; no correction is possible in this case .sx To allow the correction of single errors and the detection of multiple errors , several parity bits are added to each word where each parity bit checks the parity of part of the word ; such a scheme is known as a Hamming code .sx table&figure&captions .sx Where error rates are expected to be very low , a simple , single-error correction method is possible for a block of data containing m words of n bits .sx One parity bit is generated for each of the m words , so that an error indicates which word is faulty , and one parity bit is generated for each bit position of the n bit words , so that an error indicates which bit position is faulty .sx An error is therefore pinpointed and may be corrected by inverting the faulty bit .sx A circuit to measure or check the parity of an eight-bit word is shown in Fig. 3.11 ; the output is 1 if the parity of the input word is odd and 0 if the parity is even .sx The output of an XOR gate is 1 if the inputs are different , i.e. odd parity .sx If the outputs of two XOR gates are used as inputs to a third XOR , then an odd parity input produces a 1 at the output and an even parity input results in a 0 output .sx This XOR tree structure may be expanded ( or reduced ) to accommodate any number of bits .sx As a parity generating circuit , the combined output of the eight-bit input word and the parity checking circuit is a nine-bit even parity word .sx To obtain odd parity for the combined word the output of the parity checking circuit should be inverted .sx 3.7 MEMORIES AS LOGIC ELEMENTS .sx A memory consists of an array of elements in which single bits of digital information can be stored .sx To access a particular element , the position ( or address ) of that element is required , and then data may be written into or read from it .sx ( Memories are discussed in more detail in Chapter 6 .sx ) Each row of a truth table has a unique address given by the state of the input signals .sx If , therefore , the input signals are connected to the address lines of the memory , and the memory elements already contain the truth table for the function to be generated , reading the memory at the selected address results in an output of the required state .sx For the table in Fig. 3.9 , addresses 0 , 3 , 4 and 5 must contain 0 and addresses 1 , 2 , 6 and 7 must contain 1 for the memory to produce the correct function .sx To change the logic function performed by the memory it is only necessary to change the contents of the memory .sx As no interconnection changes are required to do this a memory seems ideal in providing a flexible logic system , but a number of problems arise in trying to provide this flexibility .sx If the memory is volatile , which means that when the power is switched off the information in the memory is lost , the data must be reloaded into the memory every time the system is switched on .sx This is tedious by hand and complex by computer .sx Non-volatile memories are either permanent ( read-only memories or ROMs ) , in which case they must be replaced to change the logic function , or relatively slow ( erasable programmable read-only memories or EPROMs) .sx In most cases non-volatile devices require special circuits or systems to alter the data stored in them .sx Memories have significant advantages over the devices described earlier in systems with a large number of inputs or where the logic must be adaptable during use .sx The size of modern memories means that single-bit logic functions of 16 to 20 signals can be produced by a single chip with access times in the range 25 to 150 ns and eight-bit output functions of 12 to 14 inputs in similar times .sx As such functions correspond to truth tables with between 4096 ( 12 bits ) and approximately one million ( 20 bits ) rows , construction of any but the most trivial with basic gates , decoders or multiplexers could not be contemplated because of the vast number of chips they would need .sx The ability to change the logic function can be a requirement of the system and , in that case , there is no alternative but to use a device that can be reprogrammed , e.g. a memory .sx An example of this is where , if one input signal stops working , it may be necessary to stop the system unless the logic can be reconfigured to allow for that signal failure .sx 3.8 PROGRAMMABLE LOGIC .sx The increasing complexity of integrated circuits has allowed manufacturers to produce circuits which can be programmed to perform random logic functions .sx By using these devices to replace basic gates , the number of integrated circuits used to produce the random logic can be reduced by about a factor of ten .sx A number of designs exist for these devices with different names for different designs .sx Most names are a selection from the list :sx array ; device ; gate ; logic ; programmable .sx Although some devices are capable of performing sequential as well as combinational logic , this section will concentrate on programmable devices for combinational logic .sx To make the device programmable , the manufacturer includes fusible links into the signal paths .sx If the link is left intact , then the signal is transmitted from one stage to the next ; if the fuse is blown , then the signal path is broken .sx To program one of these devices it is necessary to retain all the links on the signal paths required and to blow all the other fuses .sx Special equipment is needed to provide the correct waveforms to blow the fuses without destroying the device .sx In Chapter 2 it was seen that combinational logic functions could be produced by generating only the terms corresponding to ones in the truth table ( or by generating the zero terms and inverting the output) .sx As described above , a memory generates an output ( 0 or 1 ) for every row of the truth table and , therefore , at least half the memory is being used inefficiently .sx For the example based on Fig. 3.9 , a circuit which outputs a one for addresses 1 , 2 , 6 and 7 is all that is needed since the other input combinations will then automatically generate a zero .sx For sparse truth tables ( those with only a few rows set to one logic state and the vast majority set to the other state ) , or tables with many don't care/can't happen states , a memory is very inefficient .sx This is not necessarily a problem for circuits made from individual chips but , for the design of very large-scale integration ( VLSI ) devices , where all the logic for a system has to fit on to one chip , it is important to use space effectively .sx Basically , programmable logic implements a sum-of-products form for the logic function or functions required and the programming of these devices can be considered as logic minimization on a grand scale .sx The most general design is the programmable logic array ( PLA ) where both the connections to the AND gates , to form the product terms , and the AND gate to OR gate connections , to form the sum of products , contain fuses and can , therefore , be programmed .sx Note that a programmable read-only memory ( PROM ) fully decodes all inputs and therefore contains a fixed AND array ( the input decoder) .sx The data in a PROM is stored by programming the OR array .sx In a PLA each input signal is buffered and connected to every AND gate in both normal and inverted form through a fusible link ( Fig. ) .sx For each AND gate , fuses are blown so that it receives only the signals for one of the product terms in the minimized expression .sx Each AND gate output is connected to every OR gate through a link so that the product terms to be summed by an OR gate can be selected .sx The internal design of the chip ensures that the input to a gate with the fuse blown is set to the appropriate logic level ; high for an AND gate and low for an OR gate input .sx For the example given , the top AND gate remains connected only to A , unch and unch ; the second to unch and B ; the third to B and C ; the bottom gate is connected only to unch and C. The top OR gate sums the top three product terms and the lower gate sums the bottom two terms .sx Note that the term B dot C is common to both OR gates .sx The OR gate output is connected to the output pin of the PLA through an XOR gate so that the output can be produced in normal or complemented form .sx This circuit would occupy only a small fraction of a standard PLA compared with three packages if simple gates were used .sx A typical field programmable device ( one that can be programmed by the user ) has 16 inputs , forms 48 product terms and produces eight outputs .sx It becomes impossible to draw a circuit diagram in the way used up to now as the device contains 32 inverters , 48 32-in AND gates , eight 48-in OR gates and eight XOR gates .sx A shorthand method is needed to show which fuses are to remain intact .sx A common method of doing this is shown in the lower half of Fig. 3.12. One line is used to represent all the ( separate ) inputs to a gate and crosses are used to show the connections to those inputs ( i.e. a cross marks where a fuse is to be left intact) .sx It is emphasized that there is no direct connection between the signals marked with a cross on that line .sx The AND gate inputs line can be termed a product line and the OR gate inputs line a sum line .sx To keep the diagram as simple as possible , the input buffers/inverters are not shown .sx The XOR gates on the outputs are shown explicitly as they must be programmed to give a normal or complemented output .sx