Chapter 4 
Digital Components
Objectives
At the end of this chapter, you should be able to:

1.	remember the function and logic circuit of a half adder;

2.	describe the function of a full adder;

3.	draw the logic circuit of a half adder with two half adders and an OR gate;

4.	distinguish the functions of an encoder and a decoder;

5.	use truth table to define the function of a specific encoder / decoder circuit.

6.	explain the operations of shift register circuits; and

7.	explain the operations of the asynchronous and synchronous counter circuits employing flip-flops.

Reference
1.	Thomas C. Bartee, "Digital Computer Fundamentals," sixth edition, McGraw-Hill Publishing Company.

2.	Richard S. Sandige, "Modern Digital Design," McGraw-Hill Publishing Company.

3.	Theodore F. Bogart Jr., "Introduction to Digital Circuits,"” McGraw-Hill Publishing Company.

1. Introduction
	In this chapter, several functional circuits commonly found in a computer will be discussed.  The adders, decoders and encoders are combinational circuits while counters and shift registers are sequential circuits.

2.	Adders
	The function of the adder circuits is to perform binary arithmetic.  It is a major component in the CPU.  Recall that multiplication is completed by multiple additions while division requires comparison and subtraction.  In addition, subtraction can be performed by addition of a negative number in 2’s complement representation.  Therefore, to reduce the complexity of binary arithmetic circuitry, adder is the only components required for binary arithmetic.

	In a binary addition process, two binary numbers are added bit by bit.  In consecutive bit additions, binary digits with same significance are added, together with a carry from the addition of the next less significant bits, to produce a sum and a carry to next more significant bits.  
2.1 Half Adder

	A half adder performs half of the one bit addition.  It adds two bits to give a sum and a carry.  Since it does not consider any carry input, i.e. it only finishes half of the job.  Therefore it called a half adder.

	Table 4.1 summarizes the different conditions for the addition of two binary digits A and B.
A	B	Carry	Sum	
0	0	0	0	
0	1	0	1	
1	0	0	1	
1	1	1	0	
Table 4.1 	

	From Table 1, one can tell that the two functions Carry and Sum can be found by two simple logic functions, i.e. logic AND, and logic XOR, respectively:

	Carry	= 	A . B
	Sum		=	A  B

	Based on this observation, we can easily find the logic circuit of the half adder as in Figure 4.1

Figure 4.1  Half Adder.	
2.2 Full Adder

	A half adder only performs half of the addition.  In order to take the carry input into account, another adder circuit is required.  This is the full adder circuit which is able to complete the full addition process.

	There are three inputs in a full adder circuit, namely the in carry, Ci, and the two binary digits, A and B.  These three inputs will give a sum, S, and an out carry, Co, at the output of the full adder.

	Table 4.2 summarizes the function of the full adder circuit.

Ci	A	B	Co	S	
0	0	0	0	0	
0	0	1	0	1	
0	1	0	0	1	
0	1	1	1	0	
1	0	0	0	1	
1	0	1	1	0	
1	1	0	1	0	
1	1	1	1	1	
Table 4.2	

	From Table 2, we can obtain the functions Co and S in standard sum of products form:

	Co 	= 	 +  +  + CiAB	(Exp. 4.1)
	S	=	 +  +  + CiAB	(Exp. 4.2)

	Rearranging the two expressions (Exp.1) and (Exp.2) gives that:

	Co 	= 	 +  + CiAB + 	
		=	Ci ( + ) + (Ci + ) AB
		=	Ci (A  B) + AB	(Exp. 4.3)
	
	S	=	 +  +  + CiAB
		=	 () + Ci (+ AB)
		=	 (A  B) + Ci ()
		=	Ci  A  B	(Exp. 4.4)

	From (Exp. 4.3) and (Exp. 4.4), we can use two half adders and an OR gate to build a full adder circuit.  (Figure 4.2)

Figure 4.2 Full Adder.	

3.	Encoder
	The function of an encoder is to give a binary output according to a group of inputs of which only one is different from all others.  

	For example, there are 10 inputs and 4 outputs in a decimal-to-binary encoder.  Each input represents a decimal digit from 0 to 9.  Only one of the 10 inputs will be at logic 1 at any one time.  The output will be a four-bit binary number corresponding to the decimal digit.  Table 4.3 shows the truth table of the encoder.

D9	D8	D7	D6	D5	D4	D3	D2	D1	D0	B3	B2	B1	B0	
0	0	0	0	0	0	0	0	0	1	0	0	0	0	
0	0	0	0	0	0	0	0	1	0	0	0	0	1	
0	0	0	0	0	0	0	1	0	0	0	0	1	0	
0	0	0	0	0	0	1	0	0	0	0	0	1	1	
0	0	0	0	0	1	0	0	0	0	0	1	0	0	
0	0	0	0	1	0	0	0	0	0	0	1	0	1	
0	0	0	1	0	0	0	0	0	0	0	1	1	0	
0	0	1	0	0	0	0	0	0	0	0	1	1	1	
0	1	0	0	0	0	0	0	0	0	1	0	0	0	
1	0	0	0	0	0	0	0	0	0	1	0	0	1	
Table 4.3 Truth table of a decimal-to-binary encoder.	

	From the truth table in Table 3, we can find out the functions of B3, B2, B1, and B0 in terms of the ten inputs, D0 to D9.  

B3 =  +  

B2 =  +   +  +  

B1 =  +   +  +  

B0 =  +   +  +  + 

Consequently, we can find out the logic circuit of the decimal-to-binary encoder.

4.	Decoder
	The function of a decoder is the reverse process of an encoder.  Based on a binary input, the decoder produces a group of outputs of which only one is different from all others.  
B3	B2	B1	B0	D9	D8	D7	D6	D5	D4	D3	D2	D1	D0	
0	0	0	0	1	1	1	1	1	1	1	1	1	0	
0	0	0	1	1	1	1	1	1	1	1	1	0	1	
0	0	1	0	1	1	1	1	1	1	1	0	1	1	
0	0	1	1	1	1	1	1	1	1	0	1	1	1	
0	1	0	0	1	1	1	1	1	0	1	1	1	1	
0	1	0	1	1	1	1	1	0	1	1	1	1	1	
0	1	1	0	1	1	1	0	1	1	1	1	1	1	
0	1	1	1	1	1	0	1	1	1	1	1	1	1	
1	0	0	0	1	0	1	1	1	1	1	1	1	1	
1	0	0	1	0	1	1	1	1	1	1	1	1	1	
1	0	1	0	1	1	1	1	1	1	1	1	1	1	
1	0	1	1	1	1	1	1	1	1	1	1	1	1	
1	1	0	0	1	1	1	1	1	1	1	1	1	1	
1	1	0	1	1	1	1	1	1	1	1	1	1	1	
1	1	1	0	1	1	1	1	1	1	1	1	1	1	
1	1	1	1	1	1	1	1	1	1	1	1	1	1	
Table 4.4 Truth table of a binary-to-decimal decoder.	

	In a binary-to-decimal decoder, there are 4 inputs representing a 4-bit binary number and the number of outputs is 10.  According to the binary combinations, one of the outputs will be different from the others.  Table 4.4 shows the truth table of a binary-to-decimal decoder.

	From the truth table, functions D9 to D0 can be found in terms of the binary inputs B3 to B0:

	D9 = 
	D8 = 
	D7 = 
	D6 = 
	D5 = 
	D4 = 
	D3 = 
	D2 = 
	D1 = 
	D0 = 

	From the expressions of D9 to D0, the decoder circuit can be found.

5 Counters
5.1 Introduction
	Counters are essential components in a digital computer. They are used for the control of sequence and program execution. 

	Counters are sequential logic circuits and made with flip-flops.  There are two categories of counters: asynchronous and synchronous counters. The asynchronous counters produce the outputs in sequence while the outputs of the synchronous counters are available at the same time.

	Both types of counters are made with either J-K or T-type flip-flops.  Consider the J-K flip-flop with all its inputs being connected to 1 (figure 4.3.)

Figure.4.3 J-K flip-flop with its inputs connected to 1.	

	If we pass a clock signal to its clock input and note the output at Q, the waveforms as in figure 4.4 will be obtained.

Figure.4.4 Input and output waveform of the negative edge-triggered J-K flip-flop with its inputs connected to 1.	

	The timing diagram, in figure 4.4, shows that the output Q produces one pulse for every two clock pulses input, i.e. The counter counts once for every two clock pulses.

	The output waveform at Q is similar to the signal at the clock input except the frequency at Q is half of that at the clock.  Therefore, a counter is sometimes called a divider because it divides the clock frequency.  A J-K flip-flop, alone with their inputs connected to logical 1, can be regarded as a divide-by-2 counter.

5.2 Divide-by-16 Ripple Counter

	Figure 4.5 shows the diagram of a divide-by-16 ripple counter employing four clocked J-K flip-flops.  In the circuit, the output of FF0 is fed to the clock input of FF1.  The output of FF1 is in turn fed to the clock input of FF2 and the output of FF2 is connected to the clock input of FF3.
	
Figure.4.5 Divide-by-16 ripple counter.	

	Since Q0 produces one clock pulse for every two input clocks, the number of clock pulses is further divided at the outputs Q1, Q2, and Q3.  At Q3, only one clock pulse is generated for every 16 input clocks as in figure 3.6.

Figure.4.6. Waveforms at the outputs of the divide-by-16 counter.	

	In addition, if we look at the outputs, we can find that the output sequence in Q3, Q2, Q1 and Q0, forms the binary numbers from 0 to 15, i.e. the counter counts the binary numbers.

	Recall that propagation delay happens in operations of flip-flops.  The clock transition in Q3 does not coincide with that in the input or other outputs.  There is time delay for all output clocks compared with their input clocks.  The clocks ripple through the different flip-flops.  That is why it is called a ripple counter.  Because the outputs are not available at the same time, it is an asynchronous counter.

	With similar configuration, a divide-by-2n counter can be built with n J-K flip-flops.

	Since the T-type flip-flops are configured with J-K flip-flops, the counter can also be built with T-type flip-flops.

	The disadvantage of the ripple counters are that their output clock transitions do not happen at the same time.  For a divide-by-2n counter, the time required for the outputs to be available is equal to n x propagation delay of one flip-flop.  In high speed circuits, the short duration of clock period with large number of cascaded flip-flops may cause unexpected results.

	To overcome such problems, we need more complicated design:  synchronous counters.
5.3 Divide-by-16 Synchronous Counter

	Synchronous counters have the advantage of making all their output clock transitions happen at the same time.

	In order to achieve the synchronization, all the clock inputs of the flip-flops must be connected together so that the outputs are available at the same time.

	The problem is now left to the connections of the inputs in different flip-flops.  Let us now look at the counting sequence in the outputs (table 3.5):

Q3	Q2	Q1	Q0		Q3	Q2	Q1	Q0	
0	0	0	0		1	0	0	0	
0	0	0	1		1	0	0	1	
0	0	1	0		1	0	1	0	
0	0	1	1		1	0	1	1	
0	1	0	0		1	1	0	0	
0	1	0	1		1	1	0	1	
0	1	1	0		1	1	1	0	
0	1	1	1		1	1	1	1	

Table 4.5 Counting sequence of a divide-by-16 counter.

	Investigation on the outputs, we find that Q0 changes state for every clock input.  Q1 changes state when Q0 changes from 1 to 0.  Q2 changes state when Q0 and Q1 both change from 1 to 0.  Finally, Q3 changes state when all other outputs change from 1 to 0.

	From the above investigation, we can design out divide-by-16 synchronous counter as in figure 4.7.

	The operation	of the synchronous counter is exact the same as the investigation above.  FF0 is configured to change output state for every transition of the clock.  It is simply a divide-by-2 counter.  FF1 has its inputs taken from the output of FF0.  Therefore, it changes output state when the output of FF0 is 1.

	The inputs of FF2 are connected to the output of an AND gate whose inputs are outputs of FF0 and FF1.  Therefore, when both Q0 and Q1 are at logical 1, the output FF2 changes state after the clock.  Finally, FF3 changes state after the clock pulse when all other outputs are at logical 1.

	
Figure.4.7. Circuit diagram of the divide-by-16 synchronous counter.	

	Figure 4.8 shows the waveforms at the different outputs of the synchronous counter.  The waveforms are similar to that in figure 3.6.  However, they are not the same.  All the outputs Q0 to Q3 change at the same time.  In reading this waveforms, readers should bear in mind that there are propagation delay in the flip-flops.  Therefore, the values of the inputs of each flip-flop should be the values before the clock transition begins.

Figure.4.8. Waveforms at the outputs of the divide-by-16 counter.	

	In general, the divide-by-2n synchronous counter can be configured in a similar way using n flip-flops and (n-2) AND gates.  The inputs of the mth flip-flop is connected to the output of an AND gate with its inputs being the outputs of the flip-flop 0 to the (m-1)th flip-flip.

6. Shift Registers
6.1 Introduction

	Shift registers are another sequential logic circuit making use of flip-flops.  A shift register is usually used to store a vector of binary digits.  It can be regarded as a simple memory array.  

	There are two ways to store a data into a shift register: parallel and serial input methods.  Serial input method shifts the data into the shift register one bit by one bit.  In addition, two directions can the data be shifted into the register, namely right-shift and left-shift.  If the least significant bit of a data is shifted first into the register and the most significant bit is the last, it is right-shifted into the register.  On the other hand, left-shifted method takes the MSB first into the register.  The parallel input method stores the data into the register all at a time.

	Similarly, the data in the shift register can be retrieved either in series or in parallel.  If the data is retrieved one bit by on bit, it is retrieved in series.  Moreover, with the direction of the shifting, it can be further regarded as right-shifted and left-shifted.  The parallel output method retrieves all digits of the data at the same time.

6.2 4-bit Left-Shift Register 

	Figure 4.9 shows a 4-bit left-shift register circuit made with J-K flip-flops with direct inputs (preset and clear).  Under normal operation, values at the direct inputs are all at logical 1, so that they have no effect on the outputs.

Figure 4.9. 4-bit left-shift register circuit.	

	Each flip-flop is configured in a way that the values at their two input terminals are always complemented to each other.  This configuration lets the input value at the J input be transferred into the output Q after the clock.
	
	Consider the waveforms in figure 4.10. The register is initially cleared to 0000 via the clear input by giving a 0 to the clear input line.

Figure 4.10. Waveforms of the shift-register.	

	The data to be stored in the register is 1101.  After the first clock pulse, the first data, 1, is shifted into FF0, i.e. Q0 is 1.  After the second clock pulse, the second data, 1, is shifted into FF0, i.e. Q0 is 1.  At the same time, the first data, previously stored in FF0, is shifted into FF1, i.e. Q1 is 1.
	
	At the end of the forth clock, the data 1011 will be shifted into the register.  Because the data are shifted into the register serially from LSB to MSB, it is a left-shifted register.  

	At this time, the data can be read from the four Q outputs in parallel.  This is called the serial in parallel out operation.
	
	The data can also be read from the Q3 serially by providing four more clock pulses.  Such operation is called serial in serial out operation.
	
	Data can also be entered in parallel using the preset terminals with suitable modifications on the circuit.  (The register is usually cleared before the data are entered.)  In that case, we can operate the register in Parallel in parallel out, and parallel in serial out modes.