Digital Circuits – Useful Resources ”; Previous Next The following resources contain additional information on Digital Circuits. Please use them to get more in-depth knowledge on this. Useful Links on Digital Circuits Digital Circuits Wiki − Wikipedia Reference for Digital Circuits. Useful Books on Digital Circuits To enlist your site on this page, please drop an email to [email protected] Print Page Previous Next Advertisements ”;
Programmable Logic Devices ”; Previous Next Programmable Logic Devices (PLDs) are the integrated circuits. They contain an array of AND gates & another array of OR gates. There are three kinds of PLDs based on the type of array(s), which has programmable feature. Programmable Read Only Memory Programmable Array Logic Programmable Logic Array The process of entering the information into these devices is known as programming. Basically, users can program these devices or ICs electrically in order to implement the Boolean functions based on the requirement. Here, the term programming refers to hardware programming but not software programming. Programmable Read Only Memory (PROM) Read Only Memory (ROM) is a memory device, which stores the binary information permanently. That means, we can’t change that stored information by any means later. If the ROM has programmable feature, then it is called as Programmable ROM (PROM). The user has the flexibility to program the binary information electrically once by using PROM programmer. PROM is a programmable logic device that has fixed AND array & Programmable OR array. The block diagram of PROM is shown in the following figure. Here, the inputs of AND gates are not of programmable type. So, we have to generate 2n product terms by using 2n AND gates having n inputs each. We can implement these product terms by using nx2n decoder. So, this decoder generates ‘n’ min terms. Here, the inputs of OR gates are programmable. That means, we can program any number of required product terms, since all the outputs of AND gates are applied as inputs to each OR gate. Therefore, the outputs of PROM will be in the form of sum of min terms. Example Let us implement the following Boolean functions using PROM. $$A(X,Y,Z)=sum mleft ( 5,6,7 right )$$ $$B(X,Y,Z)=sum mleft ( 3,5,6,7 right )$$ The given two functions are in sum of min terms form and each function is having three variables X, Y & Z. So, we require a 3 to 8 decoder and two programmable OR gates for producing these two functions. The corresponding PROM is shown in the following figure. Here, 3 to 8 decoder generates eight min terms. The two programmable OR gates have the access of all these min terms. But, only the required min terms are programmed in order to produce the respective Boolean functions by each OR gate. The symbol ‘X’ is used for programmable connections. Programmable Array Logic (PAL) PAL is a programmable logic device that has Programmable AND array & fixed OR array. The advantage of PAL is that we can generate only the required product terms of Boolean function instead of generating all the min terms by using programmable AND gates. The block diagram of PAL is shown in the following figure. Here, the inputs of AND gates are programmable. That means each AND gate has both normal and complemented inputs of variables. So, based on the requirement, we can program any of those inputs. So, we can generate only the required product terms by using these AND gates. Here, the inputs of OR gates are not of programmable type. So, the number of inputs to each OR gate will be of fixed type. Hence, apply those required product terms to each OR gate as inputs. Therefore, the outputs of PAL will be in the form of sum of products form. Example Let us implement the following Boolean functions using PAL. $$A=XY+X{Z}”$$ $$A=X{Y}”+Y{Z}”$$ The given two functions are in sum of products form. There are two product terms present in each Boolean function. So, we require four programmable AND gates & two fixed OR gates for producing those two functions. The corresponding PAL is shown in the following figure. The programmable AND gates have the access of both normal and complemented inputs of variables. In the above figure, the inputs X, ${X}”$, Y, ${Y}”$, Z & ${Z}”$, are available at the inputs of each AND gate. So, program only the required literals in order to generate one product term by each AND gate. The symbol ‘X’ is used for programmable connections. Here, the inputs of OR gates are of fixed type. So, the necessary product terms are connected to inputs of each OR gate. So that the OR gates produce the respective Boolean functions. The symbol ‘.’ is used for fixed connections. Programmable Logic Array (PLA) PLA is a programmable logic device that has both Programmable AND array & Programmable OR array. Hence, it is the most flexible PLD. The block diagram of PLA is shown in the following figure. Here, the inputs of AND gates are programmable. That means each AND gate has both normal and complemented inputs of variables. So, based on the requirement, we can program any of those inputs. So, we can generate only the required product terms by using these AND gates. Here, the inputs of OR gates are also programmable. So, we can program any number of required product terms, since all the outputs of AND gates are applied as inputs to each OR gate. Therefore, the outputs of PAL will be in the form of sum of products form. Example Let us implement the following Boolean functions using PLA. $$A=XY+X{Z}”$$ $$B=X{Y}”+YZ+X{Z}”$$ The given two functions are in sum of products form. The number of product terms present in the given Boolean functions A & B are two and three respectively. One product term, ${Z}”X$ is common in each function. So, we require four programmable AND gates & two programmable OR gates for producing those two functions. The corresponding PLA is shown in the following figure. The programmable AND gates have the access of both normal and complemented inputs of variables. In the above figure, the inputs X, ${X}”$, Y, ${Y}”$, Z & ${Z}”$, are available at the inputs of each AND gate. So, program only the required literals in order to generate one product term by each AND gate. All these product terms are available at the inputs of each programmable OR
Digital Circuits – Shift Registers ”; Previous Next We know that one flip-flop can store one-bit of information. In order to store multiple bits of information, we require multiple flip-flops. The group of flip-flops, which are used to hold (store) the binary data is known as register. If the register is capable of shifting bits either towards right hand side or towards left hand side is known as shift register. An ‘N’ bit shift register contains ‘N’ flip-flops. Following are the four types of shift registers based on applying inputs and accessing of outputs. Serial In − Serial Out shift register Serial In − Parallel Out shift register Parallel In − Serial Out shift register Parallel In − Parallel Out shift register Serial In − Serial Out (SISO) Shift Register The shift register, which allows serial input and produces serial output is known as Serial In – Serial Out (SISO) shift register. The block diagram of 3-bit SISO shift register is shown in the following figure. This block diagram consists of three D flip-flops, which are cascaded. That means, output of one D flip-flop is connected as the input of next D flip-flop. All these flip-flops are synchronous with each other since, the same clock signal is applied to each one. In this shift register, we can send the bits serially from the input of left most D flip-flop. Hence, this input is also called as serial input. For every positive edge triggering of clock signal, the data shifts from one stage to the next. So, we can receive the bits serially from the output of right most D flip-flop. Hence, this output is also called as serial output. Example Let us see the working of 3-bit SISO shift register by sending the binary information “011” from LSB to MSB serially at the input. Assume, initial status of the D flip-flops from leftmost to rightmost is $Q_{2}Q_{1}Q_{0}=000$. We can understand the working of 3-bit SISO shift register from the following table. No of positive edge of Clock Serial Input Q2 Q1 Q0 0 – 0 0 0 1 1(LSB) 1 0 0 2 1 1 1 0 3 0(MSB) 0 1 1(LSB) 4 – – 0 1 5 – – – 0(MSB) The initial status of the D flip-flops in the absence of clock signal is $Q_{2}Q_{1}Q_{0}=000$. Here, the serial output is coming from $Q_{0}$. So, the LSB (1) is received at 3rd positive edge of clock and the MSB (0) is received at 5th positive edge of clock. Therefore, the 3-bit SISO shift register requires five clock pulses in order to produce the valid output. Similarly, the N-bit SISO shift register requires 2N-1 clock pulses in order to shift ‘N’ bit information. Serial In – Parallel Out (SIPO) Shift Register The shift register, which allows serial input and produces parallel output is known as Serial In – Parallel Out (SIPO) shift register. The block diagram of 3-bit SIPO shift register is shown in the following figure. This circuit consists of three D flip-flops, which are cascaded. That means, output of one D flip-flop is connected as the input of next D flip-flop. All these flip-flops are synchronous with each other since, the same clock signal is applied to each one. In this shift register, we can send the bits serially from the input of left most D flip-flop. Hence, this input is also called as serial input. For every positive edge triggering of clock signal, the data shifts from one stage to the next. In this case, we can access the outputs of each D flip-flop in parallel. So, we will get parallel outputs from this shift register. Example Let us see the working of 3-bit SIPO shift register by sending the binary information “011” from LSB to MSB serially at the input. Assume, initial status of the D flip-flops from leftmost to rightmost is $Q_{2}Q_{1}Q_{0}=000$. Here, $Q_{2}$ & $Q_{0}$ are MSB & LSB respectively. We can understand the working of 3-bit SIPO shift register from the following table. No of positive edge of Clock Serial Input Q2(MSB) Q1 Q0(LSB) 0 – 0 0 0 1 1(LSB) 1 0 0 2 1 1 1 0 3 0(MSB) 0 1 1 The initial status of the D flip-flops in the absence of clock signal is $Q_{2}Q_{1}Q_{0}=000$. The binary information “011” is obtained in parallel at the outputs of D flip-flops for third positive edge of clock. So, the 3-bit SIPO shift register requires three clock pulses in order to produce the valid output. Similarly, the N-bit SIPO shift register requires N clock pulses in order to shift ‘N’ bit information. Parallel In − Serial Out (PISO) Shift Register The shift register, which allows parallel input and produces serial output is known as Parallel In − Serial Out (PISO) shift register. The block diagram of 3-bit PISO shift register is shown in the following figure. This circuit consists of three D flip-flops, which are cascaded. That means, output of one D flip-flop is connected as the input of next D flip-flop. All these flip-flops are synchronous with each other since, the same clock signal is applied to each one. In this shift register, we can apply the parallel inputs to each D flip-flop by making Preset Enable to 1. For every positive edge triggering of clock signal, the data shifts from one stage to the next. So, we will get the serial output from the right most D flip-flop. Example Let us see the working of 3-bit PISO shift register by applying the binary information “011” in parallel through preset inputs. Since the preset inputs are applied before positive edge of Clock, the initial status of the D flip-flops from leftmost to rightmost will be $Q_{2}Q_{1}Q_{0}=011$. We can understand the working of 3-bit PISO shift register from the following table. No of positive edge of Clock Q2 Q1 Q0 0 0 1 1(LSB) 1 – 0 1 2 – – 0(LSB) Here, the serial output is coming
Quine-McCluskey Tabular Method ”; Previous Next In previous chapter, we discussed K-map method, which is a convenient method for minimizing Boolean functions up to 5 variables. But, it is difficult to simplify the Boolean functions having more than 5 variables by using this method. Quine-McClukey tabular method is a tabular method based on the concept of prime implicants. We know that prime implicant is a product (or sum) term, which can’t be further reduced by combining with any other product (or sum) terms of the given Boolean function. This tabular method is useful to get the prime implicants by repeatedly using the following Boolean identity. xy + xy’ = x(y + y’) = x.1 = x Procedure of Quine-McCluskey Tabular Method Follow these steps for simplifying Boolean functions using Quine-McClukey tabular method. Step 1 − Arrange the given min terms in an ascending order and make the groups based on the number of ones present in their binary representations. So, there will be at most ‘n+1’ groups if there are ‘n’ Boolean variables in a Boolean function or ‘n’ bits in the binary equivalent of min terms. Step 2 − Compare the min terms present in successive groups. If there is a change in only one-bit position, then take the pair of those two min terms. Place this symbol ‘_’ in the differed bit position and keep the remaining bits as it is. Step 3 − Repeat step2 with newly formed terms till we get all prime implicants. Step 4 − Formulate the prime implicant table. It consists of set of rows and columns. Prime implicants can be placed in row wise and min terms can be placed in column wise. Place ‘1’ in the cells corresponding to the min terms that are covered in each prime implicant. Step 5 − Find the essential prime implicants by observing each column. If the min term is covered only by one prime implicant, then it is essential prime implicant. Those essential prime implicants will be part of the simplified Boolean function. Step 6 − Reduce the prime implicant table by removing the row of each essential prime implicant and the columns corresponding to the min terms that are covered in that essential prime implicant. Repeat step 5 for Reduced prime implicant table. Stop this process when all min terms of given Boolean function are over. Example Let us simplify the following Boolean function, $fleft ( W,X,Y,Z right )=sum mleft ( 2,6,8,9,10,11,14,15 right )$ using Quine-McClukey tabular method. The given Boolean function is in sum of min terms form. It is having 4 variables W, X, Y & Z. The given min terms are 2, 6, 8, 9, 10, 11, 14 and 15. The ascending order of these min terms based on the number of ones present in their binary equivalent is 2, 8, 6, 9, 10, 11, 14 and 15. The following table shows these min terms and their equivalent binary representations. Group Name Min terms W X Y Z GA1 2 0 0 1 0 8 1 0 0 0 GA2 6 0 1 1 0 9 1 0 0 1 10 1 0 1 0 GA3 11 1 0 1 1 14 1 1 1 0 GA4 15 1 1 1 1 The given min terms are arranged into 4 groups based on the number of ones present in their binary equivalents. The following table shows the possible merging of min terms from adjacent groups. Group Name Min terms W X Y Z GB1 2,6 0 – 1 0 2,10 – 0 1 0 8,9 1 0 0 – 8,10 1 0 – 0 GB2 6,14 – 1 1 0 9,11 1 0 – 1 10,11 1 0 1 – 10,14 1 – 1 0 GB3 11,15 1 – 1 1 14,15 1 1 1 – The min terms, which are differed in only one-bit position from adjacent groups are merged. That differed bit is represented with this symbol, ‘-‘. In this case, there are three groups and each group contains combinations of two min terms. The following table shows the possible merging of min term pairs from adjacent groups. Group Name Min terms W X Y Z GB1 2,6,10,14 – – 1 0 2,10,6,14 – – 1 0 8,9,10,11 1 0 – – 8,10,9,11 1 0 – – GB2 10,11,14,15 1 – 1 – 10,14,11,15 1 – 1 – The successive groups of min term pairs, which are differed in only one-bit position are merged. That differed bit is represented with this symbol, ‘-‘. In this case, there are two groups and each group contains combinations of four min terms. Here, these combinations of 4 min terms are available in two rows. So, we can remove the repeated rows. The reduced table after removing the redundant rows is shown below. Group Name Min terms W X Y Z GC1 2,6,10,14 – – 1 0 8,9,10,11 1 0 – – GC2 10,11,14,15 1 – 1 – Further merging of the combinations of min terms from adjacent groups is not possible, since they are differed in more than one-bit position. There are three rows in the above table. So, each row will give one prime implicant. Therefore, the prime implicants are YZ’, WX’ & WY. The prime implicant table is shown below. Min terms / Prime Implicants 2 6 8 9 10 11 14 15 YZ’ 1 1 1 1 WX’ 1 1 1 1 WY 1 1 1 1 The prime implicants are placed in row wise and min terms are placed in column wise. 1s are placed in the common cells of prime implicant rows and the corresponding min term columns. The min terms 2 and 6 are covered only by one prime implicant YZ’. So, it is an essential prime implicant. This will be part of simplified Boolean function. Now, remove this prime implicant row and the corresponding min term columns. The reduced prime implicant table is shown below. Min terms / Prime Implicants
Digital Arithmetic Circuits ”; Previous Next In this chapter, let us discuss about the basic arithmetic circuits like Binary adder and Binary subtractor. These circuits can be operated with binary values 0 and 1. Binary Adder The most basic arithmetic operation is addition. The circuit, which performs the addition of two binary numbers is known as Binary adder. First, let us implement an adder, which performs the addition of two bits. Half Adder Half adder is a combinational circuit, which performs the addition of two binary numbers A and B are of single bit. It produces two outputs sum, S & carry, C. The Truth table of Half adder is shown below. Inputs Outputs A B C S 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 When we do the addition of two bits, the resultant sum can have the values ranging from 0 to 2 in decimal. We can represent the decimal digits 0 and 1 with single bit in binary. But, we can’t represent decimal digit 2 with single bit in binary. So, we require two bits for representing it in binary. Let, sum, S is the Least significant bit and carry, C is the Most significant bit of the resultant sum. For first three combinations of inputs, carry, C is zero and the value of S will be either zero or one based on the number of ones present at the inputs. But, for last combination of inputs, carry, C is one and sum, S is zero, since the resultant sum is two. From Truth table, we can directly write the Boolean functions for each output as $$S=A oplus B$$ $C=AB$ We can implement the above functions with 2-input Ex-OR gate & 2-input AND gate. The circuit diagram of Half adder is shown in the following figure. In the above circuit, a two input Ex-OR gate & two input AND gate produces sum, S & carry, C respectively. Therefore, Half-adder performs the addition of two bits. Full Adder Full adder is a combinational circuit, which performs the addition of three bits A, B and Cin. Where, A & B are the two parallel significant bits and Cin is the carry bit, which is generated from previous stage. This Full adder also produces two outputs sum, S & carry, Cout, which are similar to Half adder. The Truth table of Full adder is shown below. Inputs Outputs A B Cin Cout 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 When we do the addition of three bits, the resultant sum can have the values ranging from 0 to 3 in decimal. We can represent the decimal digits 0 and 1 with single bit in binary. But, we can’t represent the decimal digits 2 and 3 with single bit in binary. So, we require two bits for representing those two decimal digits in binary. Let, sum, S is the Least significant bit and carry, Cout is the Most significant bit of resultant sum. It is easy to fill the values of outputs for all combinations of inputs in the truth table. Just count the number of ones present at the inputs and write the equivalent binary number at outputs. If Cin is equal to zero, then Full adder truth table is same as that of Half adder truth table. We will get the following Boolean functions for each output after simplification. $$S=A oplus B oplus C_{in}$$ $c_{out} = AB + left ( A oplus B right )c_{in}$ The sum, S is equal to one, when odd number of ones present at the inputs. We know that Ex-OR gate produces an output, which is an odd function. So, we can use either two 2input Ex-OR gates or one 3-input Ex-OR gate in order to produce sum, S. We can implement carry, Cout using two 2-input AND gates & one OR gate. The circuit diagram of Full adder is shown in the following figure. This adder is called as Full adder because for implementing one Full adder, we require two Half adders and one OR gate. If Cin is zero, then Full adder becomes Half adder. We can verify it easily from the above circuit diagram or from the Boolean functions of outputs of Full adder. 4-bit Binary Adder The 4-bit binary adder performs the addition of two 4-bit numbers. Let the 4-bit binary numbers, $A=A_{3}A_{2}A_{1}A_{0}$ and $B= B_{3}B_{2}B_{1}B_{0}$. We can implement 4-bit binary adder in one of the two following ways. Use one Half adder for doing the addition of two Least significant bits and three Full adders for doing the addition of three higher significant bits. Use four Full adders for uniformity. Since, initial carry Cin is zero, the Full adder which is used for adding the least significant bits becomes Half adder. For the time being, we considered second approach. The block diagram of 4-bit binary adder is shown in the following figure. Here, the 4 Full adders are cascaded. Each Full adder is getting the respective bits of two parallel inputs A & B. The carry output of one Full adder will be the carry input of subsequent higher order Full adder. This 4-bit binary adder produces the resultant sum having at most 5 bits. So, carry out of last stage Full adder will be the MSB. In this way, we can implement any higher order binary adder just by cascading the required number of Full adders. This binary adder is also called as ripple carry (binary) adder because the carry propagates (ripples) from one stage to the next stage. Binary Subtractor The circuit, which performs the subtraction of two binary numbers is known as Binary subtractor. We can implement Binary subtractor in following two methods. Cascade Full subtractors 2’s complement method
Digital Circuits – K-Map Method ”; Previous Next In previous chapters, we have simplified the Boolean functions using Boolean postulates and theorems. It is a time consuming process and we have to re-write the simplified expressions after each step. To overcome this difficulty, Karnaugh introduced a method for simplification of Boolean functions in an easy way. This method is known as Karnaugh map method or K-map method. It is a graphical method, which consists of 2n cells for ‘n’ variables. The adjacent cells are differed only in single bit position. K-Maps for 2 to 5 Variables K-Map method is most suitable for minimizing Boolean functions of 2 variables to 5 variables. Now, let us discuss about the K-Maps for 2 to 5 variables one by one. 2 Variable K-Map The number of cells in 2 variable K-map is four, since the number of variables is two. The following figure shows 2 variable K-Map. There is only one possibility of grouping 4 adjacent min terms. The possible combinations of grouping 2 adjacent min terms are {(m0, m1), (m2, m3), (m0, m2) and (m1, m3)}. 3 Variable K-Map The number of cells in 3 variable K-map is eight, since the number of variables is three. The following figure shows 3 variable K-Map. There is only one possibility of grouping 8 adjacent min terms. The possible combinations of grouping 4 adjacent min terms are {(m0, m1, m3, m2), (m4, m5, m7, m6), (m0, m1, m4, m5), (m1, m3, m5, m7), (m3, m2, m7, m6) and (m2, m0, m6, m4)}. The possible combinations of grouping 2 adjacent min terms are {(m0, m1), (m1, m3), (m3, m2), (m2, m0), (m4, m5), (m5, m7), (m7, m6), (m6, m4), (m0, m4), (m1, m5), (m3, m7) and (m2, m6)}. If x=0, then 3 variable K-map becomes 2 variable K-map. 4 Variable K-Map The number of cells in 4 variable K-map is sixteen, since the number of variables is four. The following figure shows 4 variable K-Map. There is only one possibility of grouping 16 adjacent min terms. Let R1, R2, R3 and R4 represents the min terms of first row, second row, third row and fourth row respectively. Similarly, C1, C2, C3 and C4 represents the min terms of first column, second column, third column and fourth column respectively. The possible combinations of grouping 8 adjacent min terms are {(R1, R2), (R2, R3), (R3, R4), (R4, R1), (C1, C2), (C2, C3), (C3, C4), (C4, C1)}. If w=0, then 4 variable K-map becomes 3 variable K-map. 5 Variable K-Map The number of cells in 5 variable K-map is thirty-two, since the number of variables is 5. The following figure shows 5 variable K-Map. There is only one possibility of grouping 32 adjacent min terms. There are two possibilities of grouping 16 adjacent min terms. i.e., grouping of min terms from m0 to m15 and m16 to m31. If v=0, then 5 variable K-map becomes 4 variable K-map. In the above all K-maps, we used exclusively the min terms notation. Similarly, you can use exclusively the Max terms notation. Minimization of Boolean Functions using K-Maps If we consider the combination of inputs for which the Boolean function is ‘1’, then we will get the Boolean function, which is in standard sum of products form after simplifying the K-map. Similarly, if we consider the combination of inputs for which the Boolean function is ‘0’, then we will get the Boolean function, which is in standard product of sums form after simplifying the K-map. Follow these rules for simplifying K-maps in order to get standard sum of products form. Select the respective K-map based on the number of variables present in the Boolean function. If the Boolean function is given as sum of min terms form, then place the ones at respective min term cells in the K-map. If the Boolean function is given as sum of products form, then place the ones in all possible cells of K-map for which the given product terms are valid. Check for the possibilities of grouping maximum number of adjacent ones. It should be powers of two. Start from highest power of two and upto least power of two. Highest power is equal to the number of variables considered in K-map and least power is zero. Each grouping will give either a literal or one product term. It is known as prime implicant. The prime implicant is said to be essential prime implicant, if atleast single ‘1’ is not covered with any other groupings but only that grouping covers. Note down all the prime implicants and essential prime implicants. The simplified Boolean function contains all essential prime implicants and only the required prime implicants. Note 1 − If outputs are not defined for some combination of inputs, then those output values will be represented with don’t care symbol ‘x’. That means, we can consider them as either ‘0’ or ‘1’. Note 2 − If don’t care terms also present, then place don’t cares ‘x’ in the respective cells of K-map. Consider only the don’t cares ‘x’ that are helpful for grouping maximum number of adjacent ones. In those cases, treat the don’t care value as ‘1’. Example Let us simplify the following Boolean function, f(W, X, Y, Z)= WX’Y’ + WY + W’YZ’ using K-map. The given Boolean function is in sum of products form. It is having 4 variables W, X, Y & Z. So, we require 4 variable K-map. The 4 variable K-map with ones corresponding to the given product terms is shown in the following figure. Here, 1s are placed in the following cells of K-map. The cells, which are common to the intersection of Row 4 and columns 1 & 2 are corresponding to the product term, WX’Y’. The cells, which are common to the intersection of Rows 3 & 4 and columns 3 & 4 are corresponding to the product term, WY. The cells, which are common to the intersection of Rows 1 & 2 and
Digital Circuits – De-Multiplexers ”; Previous Next De-Multiplexer is a combinational circuit that performs the reverse operation of Multiplexer. It has single input, ‘n’ selection lines and maximum of 2n outputs. The input will be connected to one of these outputs based on the values of selection lines. Since there are ‘n’ selection lines, there will be 2n possible combinations of zeros and ones. So, each combination can select only one output. De-Multiplexer is also called as De-Mux. 1×4 De-Multiplexer 1×4 De-Multiplexer has one input I, two selection lines, s1 & s0 and four outputs Y3, Y2, Y1 &Y0. The block diagram of 1×4 De-Multiplexer is shown in the following figure. The single input ‘I’ will be connected to one of the four outputs, Y3 to Y0 based on the values of selection lines s1 & s0. The Truth table of 1×4 De-Multiplexer is shown below. Selection Inputs Outputs S1 S0 Y3 Y2 Y1 Y0 0 0 0 0 0 I 0 1 0 0 I 0 1 0 0 I 0 0 1 1 I 0 0 0 From the above Truth table, we can directly write the Boolean functions for each output as $$Y_{3}=s_{1}s_{0}I$$ $$Y_{2}=s_{1}{s_{0}}”I$$ $$Y_{1}={s_{1}}”s_{0}I$$ $$Y_{0}={s_1}”{s_{0}}”I$$ We can implement these Boolean functions using Inverters & 3-input AND gates. The circuit diagram of 1×4 De-Multiplexer is shown in the following figure. We can easily understand the operation of the above circuit. Similarly, you can implement 1×8 De-Multiplexer and 1×16 De-Multiplexer by following the same procedure. Implementation of Higher-order De-Multiplexers Now, let us implement the following two higher-order De-Multiplexers using lower-order De-Multiplexers. 1×8 De-Multiplexer 1×16 De-Multiplexer 1×8 De-Multiplexer In this section, let us implement 1×8 De-Multiplexer using 1×4 De-Multiplexers and 1×2 De-Multiplexer. We know that 1×4 De-Multiplexer has single input, two selection lines and four outputs. Whereas, 1×8 De-Multiplexer has single input, three selection lines and eight outputs. So, we require two 1×4 De-Multiplexers in second stage in order to get the final eight outputs. Since, the number of inputs in second stage is two, we require 1×2 DeMultiplexer in first stage so that the outputs of first stage will be the inputs of second stage. Input of this 1×2 De-Multiplexer will be the overall input of 1×8 De-Multiplexer. Let the 1×8 De-Multiplexer has one input I, three selection lines s2, s1 & s0 and outputs Y7 to Y0. The Truth table of 1×8 De-Multiplexer is shown below. Selection Inputs Outputs s2 s1 s0 Y7 Y6 Y5 Y4 Y3 Y2 Y1 Y0 0 0 0 0 0 0 0 0 0 0 I 0 0 1 0 0 0 0 0 0 I 0 0 1 0 0 0 0 0 0 I 0 0 0 1 1 0 0 0 0 I 0 0 0 1 0 0 0 0 0 I 0 0 0 0 1 0 1 0 0 I 0 0 0 0 0 1 1 0 0 I 0 0 0 0 0 0 1 1 1 I 0 0 0 0 0 0 0 We can implement 1×8 De-Multiplexer using lower order Multiplexers easily by considering the above Truth table. The block diagram of 1×8 De-Multiplexer is shown in the following figure. The common selection lines, s1 & s0 are applied to both 1×4 De-Multiplexers. The outputs of upper 1×4 De-Multiplexer are Y7 to Y4 and the outputs of lower 1×4 De-Multiplexer are Y3 to Y0. The other selection line, s2 is applied to 1×2 De-Multiplexer. If s2 is zero, then one of the four outputs of lower 1×4 De-Multiplexer will be equal to input, I based on the values of selection lines s1 & s0. Similarly, if s2 is one, then one of the four outputs of upper 1×4 DeMultiplexer will be equal to input, I based on the values of selection lines s1 & s0. 1×16 De-Multiplexer In this section, let us implement 1×16 De-Multiplexer using 1×8 De-Multiplexers and 1×2 De-Multiplexer. We know that 1×8 De-Multiplexer has single input, three selection lines and eight outputs. Whereas, 1×16 De-Multiplexer has single input, four selection lines and sixteen outputs. So, we require two 1×8 De-Multiplexers in second stage in order to get the final sixteen outputs. Since, the number of inputs in second stage is two, we require 1×2 DeMultiplexer in first stage so that the outputs of first stage will be the inputs of second stage. Input of this 1×2 De-Multiplexer will be the overall input of 1×16 De-Multiplexer. Let the 1×16 De-Multiplexer has one input I, four selection lines s3, s2, s1 & s0 and outputs Y15 to Y0. The block diagram of 1×16 De-Multiplexer using lower order Multiplexers is shown in the following figure. The common selection lines s2, s1 & s0 are applied to both 1×8 De-Multiplexers. The outputs of upper 1×8 De-Multiplexer are Y15 to Y8 and the outputs of lower 1×8 DeMultiplexer are Y7 to Y0. The other selection line, s3 is applied to 1×2 De-Multiplexer. If s3 is zero, then one of the eight outputs of lower 1×8 De-Multiplexer will be equal to input, I based on the values of selection lines s2, s1 & s0. Similarly, if s3 is one, then one of the 8 outputs of upper 1×8 De-Multiplexer will be equal to input, I based on the values of selection lines s2, s1 & s0. Print Page Previous Next Advertisements ”;
Digital Circuits – Canonical & Standard Forms ”; Previous Next We will get four Boolean product terms by combining two variables x and y with logical AND operation. These Boolean product terms are called as min terms or standard product terms. The min terms are x’y’, x’y, xy’ and xy. Similarly, we will get four Boolean sum terms by combining two variables x and y with logical OR operation. These Boolean sum terms are called as Max terms or standard sum terms. The Max terms are x + y, x + y’, x’ + y and x’ + y’. The following table shows the representation of min terms and MAX terms for 2 variables. x y Min terms Max terms 0 0 m0=x’y’ M0=x + y 0 1 m1=x’y M1=x + y’ 1 0 m2=xy’ M2=x’ + y 1 1 m3=xy M3=x’ + y’ If the binary variable is ‘0’, then it is represented as complement of variable in min term and as the variable itself in Max term. Similarly, if the binary variable is ‘1’, then it is represented as complement of variable in Max term and as the variable itself in min term. From the above table, we can easily notice that min terms and Max terms are complement of each other. If there are ‘n’ Boolean variables, then there will be 2n min terms and 2n Max terms. Canonical SoP and PoS forms A truth table consists of a set of inputs and output(s). If there are ‘n’ input variables, then there will be 2n possible combinations with zeros and ones. So the value of each output variable depends on the combination of input variables. So, each output variable will have ‘1’ for some combination of input variables and ‘0’ for some other combination of input variables. Therefore, we can express each output variable in following two ways. Canonical SoP form Canonical PoS form Canonical SoP form Canonical SoP form means Canonical Sum of Products form. In this form, each product term contains all literals. So, these product terms are nothing but the min terms. Hence, canonical SoP form is also called as sum of min terms form. First, identify the min terms for which, the output variable is one and then do the logical OR of those min terms in order to get the Boolean expression (function) corresponding to that output variable. This Boolean function will be in the form of sum of min terms. Follow the same procedure for other output variables also, if there is more than one output variable. Example Consider the following truth table. Inputs Output p q r f 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 Here, the output (f) is ‘1’ for four combinations of inputs. The corresponding min terms are p’qr, pq’r, pqr’, pqr. By doing logical OR of these four min terms, we will get the Boolean function of output (f). Therefore, the Boolean function of output is, f = p’qr + pq’r + pqr’ + pqr. This is the canonical SoP form of output, f. We can also represent this function in following two notations. $$f = m_{3}+m_{5}+m_{6}+m_{7}$$ $$f = sum mleft ( 3,5,6,7 right )$$ In one equation, we represented the function as sum of respective min terms. In other equation, we used the symbol for summation of those min terms. Canonical PoS form Canonical PoS form means Canonical Product of Sums form. In this form, each sum term contains all literals. So, these sum terms are nothing but the Max terms. Hence, canonical PoS form is also called as product of Max terms form. First, identify the Max terms for which, the output variable is zero and then do the logical AND of those Max terms in order to get the Boolean expression (function) corresponding to that output variable. This Boolean function will be in the form of product of Max terms. Follow the same procedure for other output variables also, if there is more than one output variable. Example Consider the same truth table of previous example. Here, the output (f) is ‘0’ for four combinations of inputs. The corresponding Max terms are p + q + r, p + q + r’, p + q’ + r, p’ + q + r. By doing logical AND of these four Max terms, we will get the Boolean function of output (f). Therefore, the Boolean function of output is, f = (p + q + r).(p + q + r’).(p + q’ + r).(p’ + q + r). This is the canonical PoS form of output, f. We can also represent this function in following two notations. $$f=M_{0}.M_{1}.M_{2}.M_{4}$$ $$f=prod Mleft ( 0,1,2,4 right )$$ In one equation, we represented the function as product of respective Max terms. In other equation, we used the symbol for multiplication of those Max terms. The Boolean function, f = (p + q + r).(p + q + r’).(p + q’ + r).(p’ + q + r) is the dual of the Boolean function, f = p’qr + pq’r + pqr’ + pqr. Therefore, both canonical SoP and canonical PoS forms are Dual to each other. Functionally, these two forms are same. Based on the requirement, we can use one of these two forms. Standard SoP and PoS forms We discussed two canonical forms of representing the Boolean output(s). Similarly, there are two standard forms of representing the Boolean output(s). These are the simplified version of canonical forms. Standard SoP form Standard PoS form We will discuss about Logic gates in later chapters. The main advantage of standard forms is that the number of inputs applied to logic gates can be minimized. Sometimes, there will be reduction in the total number of logic gates required. Standard SoP form Standard SoP form means Standard Sum of Products form. In this form, each
Binary Numbers Representation ”; Previous Next We can make the binary numbers into the following two groups − Unsigned numbers and Signed numbers. Unsigned Numbers Unsigned numbers contain only magnitude of the number. They don’t have any sign. That means all unsigned binary numbers are positive. As in decimal number system, the placing of positive sign in front of the number is optional for representing positive numbers. Therefore, all positive numbers including zero can be treated as unsigned numbers if positive sign is not assigned in front of the number. Signed Numbers Signed numbers contain both sign and magnitude of the number. Generally, the sign is placed in front of number. So, we have to consider the positive sign for positive numbers and negative sign for negative numbers. Therefore, all numbers can be treated as signed numbers if the corresponding sign is assigned in front of the number. If sign bit is zero, which indicates the binary number is positive. Similarly, if sign bit is one, which indicates the binary number is negative. Representation of Un-Signed Binary Numbers The bits present in the un-signed binary number holds the magnitude of a number. That means, if the un-signed binary number contains ‘N’ bits, then all N bits represent the magnitude of the number, since it doesn’t have any sign bit. Example Consider the decimal number 108. The binary equivalent of this number is 1101100. This is the representation of unsigned binary number. (108)10 = (1101100)2 It is having 7 bits. These 7 bits represent the magnitude of the number 108. Representation of Signed Binary Numbers The Most Significant Bit (MSB) of signed binary numbers is used to indicate the sign of the numbers. Hence, it is also called as sign bit. The positive sign is represented by placing ‘0’ in the sign bit. Similarly, the negative sign is represented by placing ‘1’ in the sign bit. If the signed binary number contains ‘N’ bits, then (N-1) bits only represent the magnitude of the number since one bit (MSB) is reserved for representing sign of the number. There are three types of representations for signed binary numbers Sign-Magnitude form 1’s complement form 2’s complement form Representation of a positive number in all these 3 forms is same. But, only the representation of negative number will differ in each form. Example Consider the positive decimal number +108. The binary equivalent of magnitude of this number is 1101100. These 7 bits represent the magnitude of the number 108. Since it is positive number, consider the sign bit as zero, which is placed on left most side of magnitude. (+108)10 = (01101100)2 Therefore, the signed binary representation of positive decimal number +108 is 𝟎𝟏𝟏𝟎𝟏𝟏𝟎𝟎. So, the same representation is valid in sign-magnitude form, 1’s complement form and 2’s complement form for positive decimal number +108. Sign-Magnitude form In sign-magnitude form, the MSB is used for representing sign of the number and the remaining bits represent the magnitude of the number. So, just include sign bit at the left most side of unsigned binary number. This representation is similar to the signed decimal numbers representation. Example Consider the negative decimal number -108. The magnitude of this number is 108. We know the unsigned binary representation of 108 is 1101100. It is having 7 bits. All these bits represent the magnitude. Since the given number is negative, consider the sign bit as one, which is placed on left most side of magnitude. (−108)10 = (11101100)2 Therefore, the sign-magnitude representation of -108 is 11101100. 1’s complement form The 1’s complement of a number is obtained by complementing all the bits of signed binary number. So, 1’s complement of positive number gives a negative number. Similarly, 1’s complement of negative number gives a positive number. That means, if you perform two times 1’s complement of a binary number including sign bit, then you will get the original signed binary number. Example Consider the negative decimal number -108. The magnitude of this number is 108. We know the signed binary representation of 108 is 01101100. It is having 8 bits. The MSB of this number is zero, which indicates positive number. Complement of zero is one and vice-versa. So, replace zeros by ones and ones by zeros in order to get the negative number. (−108)10 = (10010011)2 Therefore, the 1’s complement of (108)10 is (10010011)2. 2’s complement form The 2’s complement of a binary number is obtained by adding one to the 1’s complement of signed binary number. So, 2’s complement of positive number gives a negative number. Similarly, 2’s complement of negative number gives a positive number. That means, if you perform two times 2’s complement of a binary number including sign bit, then you will get the original signed binary number. Example Consider the negative decimal number -108. We know the 1’s complement of (108)10 is (10010011)2 2’s compliment of (108)10 = 1’s compliment of (108)10 + 1. = 10010011 + 1 = 10010100 Therefore, the 2’s complement of (108)10 is (10010100)2. Print Page Previous Next Advertisements ”;
Digital Circuits – Signed Binary Arithmetic ”; Previous Next In this chapter, let us discuss about the basic arithmetic operations, which can be performed on any two signed binary numbers using 2’s complement method. The basic arithmetic operations are addition and subtraction. Addition of two Signed Binary Numbers Consider the two signed binary numbers A & B, which are represented in 2’s complement form. We can perform the addition of these two numbers, which is similar to the addition of two unsigned binary numbers. But, if the resultant sum contains carry out from sign bit, then discard (ignore) it in order to get the correct value. If resultant sum is positive, you can find the magnitude of it directly. But, if the resultant sum is negative, then take 2’s complement of it in order to get the magnitude. Example 1 Let us perform the addition of two decimal numbers +7 and +4 using 2’s complement method. The 2’s complement representations of +7 and +4 with 5 bits each are shown below. (+7)10 = (00111)2 (+4)10 = (00100)2 The addition of these two numbers is (+7)10 +(+4)10 = (00111)2+(00100)2 ⇒(+7)10 +(+4)10 = (01011)2. The resultant sum contains 5 bits. So, there is no carry out from sign bit. The sign bit ‘0’ indicates that the resultant sum is positive. So, the magnitude of sum is 11 in decimal number system. Therefore, addition of two positive numbers will give another positive number. Example 2 Let us perform the addition of two decimal numbers -7 and -4 using 2’s complement method. The 2’s complement representation of -7 and -4 with 5 bits each are shown below. (−7)10 = (11001)2 (−4)10 = (11100)2 The addition of these two numbers is (−7)10 + (−4)10 = (11001)2 + (11100)2 ⇒(−7)10 + (−4)10 = (110101)2. The resultant sum contains 6 bits. In this case, carry is obtained from sign bit. So, we can remove it Resultant sum after removing carry is (−7)10 + (−4)10 = (10101)2. The sign bit ‘1’ indicates that the resultant sum is negative. So, by taking 2’s complement of it we will get the magnitude of resultant sum as 11 in decimal number system. Therefore, addition of two negative numbers will give another negative number. Subtraction of two Signed Binary Numbers Consider the two signed binary numbers A & B, which are represented in 2’s complement form. We know that 2’s complement of positive number gives a negative number. So, whenever we have to subtract a number B from number A, then take 2’s complement of B and add it to A. So, mathematically we can write it as A – B = A + (2”s complement of B) Similarly, if we have to subtract the number A from number B, then take 2’s complement of A and add it to B. So, mathematically we can write it as B – A = B + (2”s complement of A) So, the subtraction of two signed binary numbers is similar to the addition of two signed binary numbers. But, we have to take 2’s complement of the number, which is supposed to be subtracted. This is the advantage of 2’s complement technique. Follow, the same rules of addition of two signed binary numbers. Example 3 Let us perform the subtraction of two decimal numbers +7 and +4 using 2’s complement method. The subtraction of these two numbers is (+7)10 − (+4)10 = (+7)10 + (−4)10. The 2’s complement representation of +7 and -4 with 5 bits each are shown below. (+7)10 = (00111)2 (+4)10 = (11100)2 ⇒(+7)10 + (+4)10 = (00111)2 + (11100)2 = (00011)2 Here, the carry obtained from sign bit. So, we can remove it. The resultant sum after removing carry is (+7)10 + (+4)10 = (00011)2 The sign bit ‘0’ indicates that the resultant sum is positive. So, the magnitude of it is 3 in decimal number system. Therefore, subtraction of two decimal numbers +7 and +4 is +3. Example 4 Let us perform the subtraction of two decimal numbers +4 and +7 using 2’s complement method. The subtraction of these two numbers is (+4)10 − (+7)10 = (+4)10 + (−7)10. The 2’s complement representation of +4 and -7 with 5 bits each are shown below. (+4)10 = (00100)2 (-7)10 = (11001)2 ⇒(+4)10 + (-7)10 = (00100)2 + (11001)2 = (11101)2 Here, carry is not obtained from sign bit. The sign bit ‘1’ indicates that the resultant sum is negative. So, by taking 2’s complement of it we will get the magnitude of resultant sum as 3 in decimal number system. Therefore, subtraction of two decimal numbers +4 and +7 is -3. Print Page Previous Next Advertisements ”;