Chapter 9 Notes

9.1 Binary Decoders - Acts much like a switch statement in the C language. Decoders have n-inputs and 2n outputs, each input combination results in a single output line having a 1, all other lines have a 0 on the output. Examples of use are decoding CPU instructions and memory addresses. Decoders typically have an enable that when 1 enables decoding the input to 1 on a single output, when not enabled all outputs are 0. The switching function for an enabled two-input binary decoder is:
      
    Switching function
    Enabled x1 x0 | y3 y2 y1 y0  
   1     0  0|  0  0  0  1         
   1     0  1|  0  0  1  0
   1     1  0|  0  1  0  0
   1     1  1|  1  0  0  0
   0     -  -|  0  0  0  0
    		 
    Switching expressions
    y0 = Enabled x1'x0'    
y1 = Enabled x1'x0 
y2 = Enabled x1x0'
y3 = Enabled x1x0





    Corresponding C 

switch (Enabled x1x0 ) {
 case 100 : y3=0; y2=0; y1=0; y0=1;
 case 101 : y3=0; y2=0; y1=1; y0=0;
 case 110 : y3=0; y2=1; y1=0; y0=0;
 case 111 : y3=1; y2=0; y1=0; y0=0;
 default  : y3=0; y2=0; y1=0; y0=0;
}
The 2 to 4 decoder representation is:

Instruction Operation Decoding - Consider decoding CPU instructions where there are only 16 possible instructions. The binary encoding for some of the CPU instructions is:

     
    Instruction
    Operation 
    Code
    Encoding
    DCBA
    		 Expression
    Decoding
    Load
    0
    0000
    		 D'C'B'A'
    Store
    1
    0001
    		 D'C'B'A
    Add
    2
    0010
    		 D'C'BA'
    ...
    ...
    ...
    ...
    Jump
    15
    1111
    		 DCBA
The format of the machine instruction below would include an operation code part and other fields for addressing data variables, branching addresses, registers, etc.
Memory Address Decoding - Figure 9.4 of the text illustrates a 16K by 1 bit word memory (8 bit words are implemented by selecting 8 bits as a group, for example). Since 214 is approximately 16K, a single decoder would require 14 inputs and 214 outputs. In reality a device with this number of pins, over 214 is not practical but it does present a simple example of memory implementation.
The memory decoder is connected to the CPU by the address bus. Each memory cell is connected to an input and output data bus, a read/write control, and the decoder which enables the memory cell when the appropriate address appears. The decoder ensures that only a single memory cell is activated at a time for either input or output.

Cascaded decoders - Because of the large pin requirements of decoders (2n), they are often cascaded in the form of a tree similar to multiplexers or the decoder results are ANDed. For example, a 4 to 16 tree decoder can be constructed as below from 2 to 4 decoders.

ANDed decoders - The same results can be accomplished more efficiently by ANDing the results of decoder groups. The basic idea is that a single address can be determined by ANDing the address lines. For example address 10012=9 can be determined by the expression x3x2'x1'x0. For memory addressing, it is generally impractical to use this method since 1 Mb memory would require each memory cell (word, byte, etc.) to have a 20 input AND gate, not an efficient use of limited space on a chip.

A more efficient approach is given in the following diagram using decoders. For input x3x2x1x0=10012=9, y9 =1 with all other outputs 0. Generally, the result is yn= 22*x3x2 + x1x0, where y9 = 4*2+1, since x3x2=102=2 and x1x0=012=1. Consider the address x3x2x1x0=10002=8,  the bottom decoder y2 output and top decoder y0 is connected to the y8 AND. The  y2 output results from the high 2 bits of the address (2=102),  the  y0 results from the low 2 bits of the address (0=002).
 

The AND decoder form has advantages when used in memory address decoding, where generally each memory word is addressed in a two dimensional matrix (row, column) and the memory cell itself contains an AND gate. The above decoder cascaded tree scheme with 4 input address lines addresses 16 memory words using 16 decoding lines (24=16). The above decoder-AND scheme addresses 16 memory words, each with an internal 2 input AND gate, with 8 decoding lines.

For 64K, the cascaded tree scheme requires 216=65,535 decoding lines with no AND gates. Addressing could be done directly using 16 input AND gates (with NOTs) and no decoders. The following table gives different designs using the decoder-AND scheme for 64K:
 

Decoder
Gates		 Decoding
Lines		 AND 
Gates
8 2-input 4-output 32 65535 8-input
4 4-input 16-output 64 65535 4-input
2 8-input 256-output 512 65535 2-input

9.2, 9.3 Binary Encoders - Performs the inverse of the decoder, having 2n inputs and n outputs. However, a strict analogy with the decoder requires that only a single one of the 2n inputs be active at a time. Since the encoder cannot control its inputs to have a single input one, encoders nearly always occur as priority encoders. The following diagrams contrast parallel and iterative encoders. The primary difference being the iterative is inherently slower due to the longer propagation through the longer series of devices. Note that input x3 has the highest priority, and disables all lower priority inputs when it is active or z3=x3=1.

An example use of a priority encoder is as an interrupt controller. When two devices, a printer and a disk drive, both signal an interrupt simultaneously the encoder should give highest priority to the device requiring the most immediate response, the disk. The following table illustrates the use of a priority encoder that controls which of 4 devices interrupt the CPU, when more than one device requires CPU action the highest numbered device is always selected.
  
E x3 x2 x1 x0 | y | y1 y0 | Active
0 -  -  -  - | - | -  -  |  0        Interrupts disabled
1 0  0  0  1 | 0 | 0  0  |  1        Device 0 - Mouse
1 0  0  1  0 | 1 | 0  1  |  1        Device 1 - Printer
1 0  1  0  0 | 2 | 1  0  |  1        Device 2 - Disk
1 1  0  0  0 | 3 | 1  1  |  1        Device 3 - Power Failure
The general steps followed when a device requires service is:
  1. Device requiring service signals priority encoder by setting the encoder input true, x3 =1.
  2. Priority encoder signals CPU with number of highest priority device requesting service. It also signals CPU that an interrupt request is present.
  3.  CPU inputs the device number code from the priority encoder. On many systems, including the Intel processors, the code is in the form of a machine instruction (e.g. Int 7) that is then directly executed by the CPU.
9.4.1 Multiplexers as Universal Combinational Module (See Chapter 6 Notes also)
Any switching function of n variables can be implemented using a 2n input multiplexer. Consider implementing the AND and OR logic using a multiplexer. The truth table for AND and OR logic of two variables and the corresponding 4-input multiplexer implementations of each is:
        
      AND
         a  b|  z 
0  0  0|  0         
1  0  1|  0
2  1  0|  0
3  1  1|  1
      		 
      OR
         a  b|  z 
0  0  0|  0 
1  0  1|  1
2  1  0|  1
3  1  1|  1
The switching function for the f segment of a 7 segment LED requires 4 (a,b,c,d) input variables and would require a 16 input multiplexer to implement directly. By recoding the selector d variable as an input an 8 input multiplexer will suffice. The essential insight is to recode f(a,b,c,d) as f(a,b,c) by recognizing how input d is related to f(a,b,c). For example, for m0, f(0,0,0)=d', so multiplexer position 0 has d' for input. For m2, d does not matter, f(0,1,0)=1 so multiplexer position 2 has a 1 as input.
        
       Inputs    |  Output 
   a b c d |f(a, b, c)
0  0 0 0 0 | 1          m0
   0 0 0 1 | 0      d'
1  0 0 1 0 | 0          m1
   0 0 1 1 | 0      0 
2  0 1 0 0 | 1          m2
   0 1 0 1 | 1      1 
3  0 1 1 0 | 1          m3
   0 1 1 1 | 0      d' 
4  1 0 0 0 | 1          m4
   1 0 0 1 | 1      1 
5  1 0 1 0 | don't care m5
   1 0 1 1 | don't care 
6  1 1 0 0 | don't care m6
   1 1 0 1 | don't care 
7  1 1 1 0 | don't care m7
   1 1 1 1 | don't care 
9.6 Shifters - Shifters are used to shift all incoming bits left or right, either logically or arithmetically. You may recall that the Intel processors have shift left and right instructions (SHL, SHR, SAR, SAL). Shifters can also rotate input left or right. The diagram on the below left is of a shifter that shifts bits to the right, dropping the lowest bit and replacing the high bit with a 0. The diagram on the right rotates incoming bits to the right, replacing the high with the low order bit.
       
Simple Right Rotate - A unidirectional right shifter capable of rotating input 0, 1, 2, or 3 bits to the right can be constructed as in the following diagram. Note that x is input and y is the rotated output, s1s0 controls the rotating . When s1s0 = 00, no rotate occurs, y3=x3, y2=x2, etc. When s1s0 = 01 each bit is rotated 1 bit to the right, y3=x0, y2=x3, y1=x2, and y0=x1. When s1s0 = 10 each bit is rotated 2 bits to the right, y3=x1, y2=x0, y1=x3, and y0=x2. When s1s0 = 11 each bit is rotated 3 bits to the right, y3=x2, y2=x1, y1=x0, and y0=x3.