Introduction to digital systems ercegovac solutions pdf free download

The switching expressions for the network can be obtained by inspection of the state diagram: Exercise 8. A Moore model implementation would require an extra ip- op. The 2-out-of-5 code represents decimal digits as shown in the following table: Exercise 9.

The code table is shown next. The relation between BCD code and the Excess-3 code is: x 0 1 2 3 4 5 6 7 8 9 10 11 12 z Ex-3 - - - 0 1 2 3 4 5 6 7 8 9 y BCD 0 1 2 3 4 5 6 7 8 9 - - where x is the radix-2 representation of the input vector and z and y are the indices of the outputs of the decoders with value 1. From the table we see that for x between 3 and 9, the output of the Excess-3 decoder can be relabeled to give some of the outputs of the BCD decoder.

Since for x between 0 and 2, no output of the Excess-3 decoder has value 1, it is necessary to decode these values separately. The corresponding network is shown in Figure 9. The implementation of these functions using a 4-input decoder and OR gates is shown in Figure 9. The even parity is produced by output EP and the odd parity by output OP. The circuit is shown in Figure 9. In the gure only some of the AND gates are shown, with the corresponding output numbers. Part b using coincident decoding we need ve 4-input decoders to receive the 20 inputs.

We would need AND gates. Exercise 9. The output vector will depend on the code to be generated. Two 4-bit encoders or a large 7-bit encoder should be used, and since there is only a small set of 7-segment codes, many of the encoder inputs would not be used, or would require OR gates to combine two or more decoder outputs. One uses a decoder and OR gates, and the other uses a decoder and encoder.

The function table of the system follows: BCD 2-out-of-5 b3b2 b1b0 c4c3 c2c1c0 Two implementations of this code converter, one using a decoder and OR gates, and another using a decoder and encoder are shown in Figure 9. The outputs of the decoder are labeled according to the Gray code and connected to the corresponding inputs of the encoder.

In one implementation, a left 7-shifter is used to move the highest-priority input xc to the highest input of the priority encoder w7. The amount of shift is therefore 7 c to the left this is obtained by complementing each bit of the binary representation of c.

Consequently, to obtain the correct result, the output of the encoder y has to be decremented by 7 c mod 8. To avoid the complementation of c, we can use a right shift of c instead of the left shift. This would put xc in w0 instead of w7. Therefore, the connections between the output of the shifter and the input of the priority encoder have to be as shown in the Figure 9.

In the rst level there are eight encoders, each of them encoding part of the input vector x. Also, only the corresponding A has value 1. Since each 4-input multiplexer has two select inputs, the tree has four levels. That means, each multiplexer has k selection lines and 2k inputs. Figure 9. A description of an 8-bit shifter is easily obtained from there. The block diagram of the circuit is shown in Figure 9. Each output is generated by an 8-input multiplexer as shown in Figure 9.

Replacing these values on Equation 9. So, only renaming the inputs we are able to obtain a left shifter from a right shitfter. It can shift right or left direction input d and the distance of shifting can vary from 0 to p.

The implementation of a bit 3-shifter using four 8-bit 3-shifters is presented in Figure 9. The circuit on the top is a bit 3-shifter that shifts to the left only. The circuit on the bottom of the gure is a bi-directional bit 3-shifter. The input of the circuit was named i31 to i0, and the output z31 to z0. Solutions Manual - Introduction to Digital Design - November 15, Design of Part a bit right 3-shifter using 4-bit right shifter modules.

The network is shown in Figure 9. This circuit is useful to allow the sharing of the single line between Mux and Demux among all pairs of input,output : x0; y0 , x1 ; y It's used in communication lines to divide the full capacity of the communication line among the many transmitters and receivers. Each pair can communicate without interference of the other pairs.

The reduced sequential system has only 4 states. The design steps are not shown. The binary decoder connected to the state register generates the signals Si , which is 1 when the sequential system is at state i.

The system outputs correspond to the state signals, that means, each output is active in one particular state. For this reason we used the output names as state names to make the state diagram more meaningful.

In each present state we identify which input of the binary encoder is 1. This input determines the next state. For example, the origin of arcs going into state S1 check are obtained by considering the input of the Binary Encoder labeled 1, which is S0 for input GO, S2 always, no condition , and S3 always. The state diagram shows the operation of a controller which starts to operate with a GO signal. The path connects the input xi or yi or ci and output zi. The propagation delay of this path is obtained as: Exercise This path has a worst case delay: TpHL ci!

The propagation delay of this path is obtained as: TpHL xi! The path connects the input xi or yi and output zi. So, two cases must be considered. The propagation delay of this path is obtained as: TpLH xi! It also has less propagation delay for the carry than case a.

The input load factors for the FA are: Input load factor Input load xi 2. The output consists of a carry out and a digit coded in BCD also. Exercise Let a and b be the decimal digits to be added. The addition is described by: Exercise This process is straighforward. However, the obtained high-level description indicates that the system can be implemented with two 3-bit adders to add up x, y , and 2 in modulo 8.

The value An equivalent network with fewer modules is shown in Figure We assume that NOT gates are used to obtain the complement of the input variables, so 5 NOT gates are also used in the network. Internally, all NAND gates in the intermediate level are connected to only one input of the next level, all loads are 1. The loads of the input signals and their complements generated by the NOT gates are: Signal Load a1 11 a01 6 11 b1 b01 6 11 a0 a00 6 11 b0 b00 6 c 11 c0 6 Solutions Manual - Introduction to Digital Design - November 15, Exercise The section that generates propagate and generate signals doesn't need gates with more than 2 inputs.

The same for the last layer of XOR gates that generates the nal sum. The highest fan-in is required by the gates inside the CLG module. We decompose these gates into three gates. The implementation of the 6-bit CLA is shown in Figure From the Figure we count 66 gates distributed in 6 levels. This implementation of a bit adder needs 16 adder modules CLA The delay is: Exercise Note that this design is an extension of the design showed in Figure This scheme is presented in Figure Another way is to manipulated the vector of digits.

The most signi cant bit of wR is the carry out bit of the n bit addition performed with xR and yR. Note that case 2 produces a result vector 1; 1; : : :; 1 , which is correct since this is another representation of 0 in the one's complement system.

In that case the carry chain is broken by this combination. No active loop. In that case, there is an active loop. To have a stable result all carries have to be reset to zero before the operation starts. Figure Output: z represented by zs ; zm. The magnitude subtractor is used to compare the operands, performing the operation a b. The comparison result is obtained from the borrow output.

This single complementation can be done by bit-invert and carry-in forced to 1 in the adder, as shown in Figure A carry-ripple adder was implemented. By the use of a multiplexer, the output of the adder, or the NAND gate is selected as circuit output. First, from the network, we obtain the switching expressions.

Then, using the encoding given there, we obtain the high-level description. These carries have three values: Equal, Greater, and Smaller. The comparator output is obtained from the carry-out of the last cell. The equality among inputs is implied when both G and S conditions are zeros. The LOAD input is used to shift left, while the serial data and other next state bits are entered through the parallel inputs of the shift register Ii.

The network for this exercise is shown in Figure When subtraction is requested, a carry in of 1 in the rst clock cycle is applied to the Full-Adder, together with the complementation of all bits of b. When the 16th bit of the number is being computed, the signal last bit is 1. The pattern recognizer for the sequences and is presented in Figx input CK 3-bit Shift Register z Figure There is a delay of 4 cycles between the input digits and the output digit.

The result of the operation is 85 in decimal. Consider a group of four bits corresponding to one decimal digit of x and y.

These bits are applied at the input of the adder from least signi cant to most signi cant at clock cycles when K0, K1 , K2, and K3 are active. Since the result should be in BCD radix it is necessary to correct it whenever it is larger than 9.

Consequently, it is necessary to detect whether the addition of 2 decimal digits is greater than 9 and then subtract 10 form the result. Since the binary representation of 6 is , it's necessary to add 1 in two consecutive cycles. The least signi cant bit of the rst addition reaches the second adder when K0 is active, if the addition of 6 is necessary, the input of the second adder must have a 1 during the cycles when K1 or K2 are active.

Note that when the least signi cant bits of another pair of BCD digits come into the rst adder, the least signi cant bit of the addition of the previous pair is at the input of the second serial adder. The analysis nishes when we consider the carry bits of the BCD addition. When the sum value of the digits of x and y is a value greater than 15, the carry bit is stored in the rst adder, to be used with the next BCD digits. When the value is in the range 10 to 15, the correction step addition of 6 executed in the second adder generates a carry which is stored in the second adder for the next sum value which is the contents of the shifter.

The timing diagram is shown in Figure In each transition we use a pair of bits representing the inputs x and y , respectively. The system output corresponds to the system's present state.

A one-hot state encoding is used. After the clear signal the counter is in state 0 and the NOR gate connected to its output forces a 1 input into the half-adder HA. The other input of the HA is connected to the complemented serial output of the shift register.

The bits are shifted out least-signi cant bit rst and stored back into the same register. The carry bit of each bit addition is delayed and inserted back into the HA, as done in serial addition. The output is stored back into the registers with the same organization. Two HAs with extra logic are used to increment X 0. Since 2 bits per clock cycle are processed, a modulo counter is enough.

This design is shown in Figure L is used as selection control signal for the multiplexer. The multiplexer selects the proper output of the shifter that corresponds to the system output for a given value of L.

A modulo-m divider is implemented by a counter that loads the value 16 m every time TC is 1. In two's complement system, the computation of 16 m results in m.

The value of m is obtained from m by bit complementation Compl module and addition of 1. Another option is to use 15 m as a loading value and load the counter with this value when it reaches the state Such operation corresponds to the one's complement of m and it is obtained by simple bit complementation no incrementer. The network computes the next state adding one to the present state value when the value is less than 9, or adding 7 to the present state when it reaches 9 forcing the counter to go back to state 0.

However, since there is a typo, we give the solution as stated. The network that implements the counter is shown in Figure Black boxes were used to represent the gate networks that implement I3 ; I2; I1; and I0. The network is shown in Figure The two counters should be con gured as shown in Figure The timing diagram for both cases is shown in Figure Care must be taken with the input values for Ij when in S6.

The circuit is presented in Figure The LOAD input has the same circuit as the one used for implementation 2. These gate networks are obtained from the following table and Kmaps. Since the counter is module, it is necessary to detect when the counter state is 9 and load a 0. Similarly, the count-down feature is used for s t 1 mod 8. Others are part of a cycle that represents a counter behavior.

This type of counter is called twisted tail counter. The additional NAND gate when compared to the design shown in the textbook is used for self-starting feature. The loaded value is always 2. We can see from the Figure that the main loop consists of the sequence: 0,8,12,14,15,7,3,1, Thus, the counter is self starting. It is a twisted-tail counter. For simplicity we represent the state code using decimal numbers. To modify this modulo counter to a modulo counter, state Solutions Manual - Introduction to Digital Design - November 15, 22 is detected, which is represented by the code 1; 6 , and the state 0, coded as 0; 0 is loaded, as shown in Figure A total of 19 states are needed.

The cascade implementation of this counter is shown in Figure Observe that state 29 is detected and generates a load signal. The value loaded corresponds to state 11 The same load signal TC is the output of the frequency divider.

The parallel implementation makes use of a modulo-4 and a modulo-7 counter to obtain a modulo counter. When state 26 2; 5 is reached, both counters are loaded with the initial state 0. The circuit output corresponds to the load signal TC. The implementation is shown in Figure The counter on top counter 1 is a modulo counter counts from 0 to 14 and provides a loading value for the bottom counter counter 2.

Every time counter 2 loads the value on its parallel inputs Ii , counter 1 goes to its next state. Counter 1 counts the number of TCs from counter 2 when counter 2 reaches However, counter 1 must be initialized with value 1 when the clear signal is issued. That happens because counter 2 will start counting from zero after the clear signal no load is needed , and after 15 cycles its TC output becomes a 1, and the value to be loaded must be 1.

The implementation has fewer ip ops, more gates and more connections than the implementation in Figure Twelve ip ops are needed, instead of the six ip- ops used in Figure However, no gates are required and besides the clock line, all interconnections can be made very short.

The TC condition is generated when the present state is , and that is the only state when we have a 0 preceding a 1 at the rightmost ip op. The right counter is a modulo-5 counter. When the state of the modulo-5 counter is and the state of the other counter is , the output z becomes 1. Such a state diagram is adequately implemented using a modulo counter and a input multiplexer.

In order to generate the required outputs, another counter is used to count the number of times the buttons were pressed. This counter generates a signal END when the keys were pressed 12 times.

A network for this task is shown in Figure Only a reset signal R will remove the counters from these states, if the wrong sequence is inserted. Twelve address lines receive the input bits from a, b, and c 2 f0; 1; ; 15g.

The block diagram of the component is shown in Figure Four bits are used by each Excess-3 digit a or b represented by a and b , and one bit is used for carry input c.

Each word needs to have 5 bits: four bits for the output digit in Excess-3 s and one bit for carry output c. Part b - using ROM modules and a multiplexer. Solutions Manual - Introduction to Digital Design - November 15, 1 ROM c d e 2 1 0 0 1 2 3 4 5 6 7 1 E ROM c d e 2 1 0 a 1 b 0 0 1 2 3 4 5 6 7 1 E c d e 2 1 0 0 1 2 3 4 5 6 7 1 E ROM ROM c d e 2 1 0 0 1 2 3 4 5 6 7 E 4x4-input MUX f0 f1 f2 f3 Figure The design is shown in Figure Thus, a complete switching function table should be implemented, with 64 entries.

The minterms used to generate z1 are shown in the following table: a2a1a0 b2b1b0 product terms to generate z1 a2 a1a0 b2b1b0 a2 a1a0 b2b1b0 a2 a1a0 b2b1b0 a2 a1a0 b2b1b0 a2 a1a0 b2b1b0 a2 a1a0 b2b1b0 a2 a1a0 b2b1b0 a2 a1a0 b2b1b0 For PLAs what matters is the number of product terms. It is not possible to reduce the number of product terms shown in the table since both a and b change one bit from one row to another. The number of product terms is already minimal.

Thus, the PLA would need to have 16 products, 6 inputs, and 2 outputs. No need for the adder. The ROM module receives the Present State of the counter stored in the 4-bit register as address bits. Each word contains the value of the next state.

For states, a minimum of 9 bits are required to represent each state. The ROM needs to have as many address lines as the number of state bits plus the number of inputs, which corresponds to a total of 12 bits. Since this is a Moore machine the total number of ROM bits is reduced by using separate ROMs to generate the next state and to generate the outputs.

Of course, the implementation can use only one ROM, resulting the same as for the Mealy case. This time the output values are stored with the next state bits. The multiplier is used to select the correct input among the possible system inputs, depending on the present state of the system.

Since this is a Moore machine, another ROM is used to generate the outputs. A 9-bit register is used to store the state values.

A block diagram of the system is shown in Figure ROM outputs Figure The ROM stores both the next state bits and the output values. If we apply this idea to the system in part d , then the output should be generated by a separate ROM with 11 addressing lines and 2-bit words. The network of muxes to select the inputs would be used, and a 9-bit register would store the state bits. A multiplexer can be used to select the desired input, and the diagram can be modi ed to have only one input, let's call it x.

The network that implements the state diagram is given in Figure Part b : The system diagram is shown in Figure The third input is inserted directly as an address signal to the ROM.

Thus 9 bits are required per ROM word. We consider the design of an autonomous counter. The block diagram for the circuit is shown in Figure It is easier to consider the following tabular description that uses ranges of values. ROM addresses or word contents are represented by a pair x; y , with x; y 2 f0; 1; 2; g. As an example, the range speci ed as 1; 10 1; 15 represents the ordered sequence of values: 1; 10 ; 1; 11 ; 1; 12 ; 1; 13 ; 1; 14 ; and 1; Address Contents 0,0 - 0,9 0,1 - 0,9 , 1,0 0,10 - 0,15 d.

A content of D. A Terminal Count signal is generated when the next state is 0; 0. If more inputs and products are available in the component, functions z1 and z00 could also be implemented in the same PLA.

A total of 21 products were listed in the expressions above, however, it is possible to reduce this number of products to One possible solution is to combine m2 9 and m2 25 on the generation of z20 and obtain the single product term y22 y20x22 x21x Since a CLB can implement a 2-input multiplexer, and the 8-to-1 multiplexer can be designed with a tree of 7 2-input multiplexers, the total number of CLBs required for this case is 7.

For this implementation, a 4-input multiplexer is required for each register bit. The ip- ops to store the register state are available in the CLBs used to implement the multiplexers. When we add the inputs CNT, LD, and parallel input, to the variable Y in order to generate the actual value that is loaded as each state bit , we get a function of 4 inputs, that requires 1 CLB for each state bit.

Thus the total number of CLBs is 6. The required ip ops are available on the CLBs used for combinational logic. A Carry Ripple adder will require 8 Full Adders. These bits are summed in a 5-bit adder, which, based on the result given in the previous item, will require 5 CLBs. Thus, the total number of CLBs required to implement the multiplier is 9. The reader may also try to reduce this number by creating a optmized mapping of the the product generation and addition funtions for the least signi cant bits.

Each iteration that results from a True test at f4 has a duration of 2T , which is also the execution time of the last two tasks to nish the computation f7 and f8. The execution time of the sequential solution shown in Figure Each iteration takes 3T and the last sequence of tasks takes 5T. The scaled value used as input for the algorithm. So, the algorithm input should be 2x. The output generated by the algorithm z must be corrected by multiplying it by the same scaling factor 2k used to prescale the input x.

The execution time for this computation is 3T. The generalization of the factorial computation is based on a recurrent structure as shown in Figure This structure shows that 2m numbers may be simultaneously multiplied pairwise to generate m products. The tree generated by this structure will have 2i inputs after i levels.

To compute n! Thus, dlog2 n 1 e levels are required. An example of the computation of 11! In this case 4 levels are required in the tree. The execution time for n! We can see from the graph that the loop is executed n 1 times. All n integers are stored in a vector V. The vector is scanned from position 0 to position n 1. In this process, the maximal value is obtained. The computation graph is shown in Figure Using similar organization of Figure Based on these assumptions and the networks presented in Figure This signal will force the counter to load a zero value.

The state diagram for the control part is shown in Figure The signals A, B , and C represent the output of each register. The general architecture of the multiplier is shown in Figure The left multiplexer is used to select among the 4 multiples of X , that means: 0, X , 2X , and 3X.

To enable the generation of the 3X value using the same adder used during the algorithms iterations, some gates were inserted in the path of the selection signals of this multiplexer to force the X value as an output. Another multiplexer was placed at the other input of the adder to receive the 2X value.

After the value 3X is generated, the iterations will be executed. Only the sum output of the FAs presents the addition result in this case. The delay of the recon gurable adder has one multiplexer delay longer than the simple CS adder. A new control signal CRA ctr was included in the controller interface. This signal is 1 when we want the carry bit to propagate on the adder.

Two other states were also included: convert and store. In the convert state, there is no shift in the Y register, and no load on the Z register. Once the controller waited enough for the carry to propagate, it moves to state store, where the ldZ control signal is activated to store the non-redundant addition result into the Z register.

The Z register for a CS representation of the partial product is composed of two sub-registers: PS sum vector and C carry vector. The non-redundant result will be available on the PS register only. Y Shift Reg. We call these registers: RF Registers. Similarly for the B outputs. The binary decoders are used to generate the control signals for writing and reading the register le.

This pointer stays static when no access is requested. The system interface is shown in Figure This is the behavioral description of a -- circular shift register. Each word has 8 bits. A block diagram of the circuit is shown in Figure Each SAM module is designed as described in Exercise All SAM modules receive the same address, read, clock, and data input signals.

Depending on Ar , one of the modules are selected by the signal selm. When a module is selected, a write or read cycle may be performed. When writing, only the selected module will search the correct address position and perform the storage of the data input.

The time to access a position from the direct-access memory will depend on the time to access the SAM. A state diagram for the control subsystem is shown in Figure For convenience, we replace the s input by start. The implementation of the control circuit using a counter, multiplexer, a decoder, and gates is shown in Figure Check out the top books of the year on our page Best Books of Grillo marked it as to-read Sep 15, Gia Huy rated it really liked it Apr 26, Karan S is currently reading it Dec 18, Jessy George marked it as to-read Jun 26, To ask other readers questions about Introduction to Digital Systemsplease sign up.

Introduction to Digital Systems: Goodreads helps you keep track of books you want to read. Want to Read Currently Reading Read. Want to Read saving…. A companion Web site provides additional information. Be the first to ask a question about Introduction to Digital Systems.

Diego Tribek marked it as to-read Nov 27, Hardcoverpages. This website uses cookies to improve your experience while you navigate through the website. Out of these cookies, the cookies that are categorized as necessary are stored on your browser as they are as essential for the working of basic functionalities of the website.

We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may have an effect on your browsing experience.

Necessary cookies are absolutely essential for the website to function properly. This category only includes cookies that ensures basic functionalities and security features of the website. These cookies do not store any personal information.

Skip to content.