Class Notes (836,680)
Canada (509,870)
CMPT 150 (6)

week 7.pdf

7 Pages
Unlock Document

Computing Science
CMPT 150
Anthony Dixon

A.H.Dixon CMPT 150: Week 7 (Oct 16 - 18) 47 24 SEQUENTIAL CIRCUITS Digital systems are divided into two major groups: 1. Combinational Systems are those that have no \feedback loops" in their schemat- ics. That is, there is no pathway from the output of a component at level n in the schematic that is connected to an input of another component at level m, where m < n. All of the examples up to this point share this property and therefore they are all examples of combinational systems. As described previously, to formally de▯ne a combinational system, a behavioral description must identify two sets and a function, speci▯cally: ▯ The input set, I: This consists of all possible binary sequences that can be delivered to the digital system. Thus if there are 3 inputs to the entity de▯nition, there are 2 possible input sequences. ▯ The output set, O: This consists of all \valid" output sequences that can be output from the system. Each valid output sequence corresponds to an encoding n of some meaningful result. With n output ports there are up to 2 possible output binary sequences, although not all of them may be meaningful. ▯ The output function, f : I ! O: This function de▯nes what output sequence will be generated by the digital system for each input binary sequence. 2. Sequential Systems are those that possess one or more feedback loops. Because of the propagation delay introduced by components along any path, feedback loops enable circuits to be designed that possess memory. The formal speci▯cation of sequential systems includes the speci▯cation of the input and output sets and an output function. However an additional set, S, called the state set must also be de▯ned. Each \state" represents a distinct binary sequence that can be stored in memory. Digital systems can be designed to provide memory for storing any number of bits. in a digital system possessing n bits of memory, there n are 2 possible binary sequences of length n that can be stored in that digital system. Digital systems are often referred to as \being in a particular state." This simply means that the memory of the digital system is currently set to a particular value, that value being a binary sequence of length n, where n is the number of bits of memory within the system. The state set therefore represents all valid binary sequences that can be stored in the digital system. Each meaningful binary sequence that can be stored de▯nes one state of the system. The output from a sequential system will depend not only on the input but also on the value stored in memory. Therefore the output function is a function of two arguments: the state and the input. That is f : S ▯ I ! O. An additional function, g, called the state-transition function must also be iden- ti▯ed to provide a complete behavioral description. The purpose of this function is to describe how the contents of memory is changed by the digital system. Since any new value stored in memory (called the \next state") will depend on both the current state and the input, g is also a function of two arguments; that is, g : S ▯ I ! S. Therefore when providing a functional speci▯cation of a sequential system, information about the e▯ect of memory on the outputs must be addressed, along with whether any A.H.Dixon CMPT 150: Week 7 (Oct 16 - 18) 48 change in memory occurs. It is this additional information that is captured by the state set and state transition function. In practice, sequential digital systems, like combinational systems, can be formally speci▯ed by an entity de▯nition and a functional speci▯cation. The functional speci▯cation, however, must now identify the possible states of the system and provide both the output function and the state transition function. In many cases these functions will be the same, since the output from sequential systems is often just the contents of memory, and this is already identi▯ed by the state-transition function. A common way to express the functional speci▯cation of a small sequential system (one with few inputs and few storage bits) is with a characteristic table. This table de▯nes the state-transition function for the system, that is, the value that is placed in memory when given the previous value in memory and a particular input sequence. In this table, the symbol Qi (or Q(i), oi Q ) is often used to denote the current value of bit i of the set of bits that de▯ne the memory of the system. When there is only one bit of storage, no \subscript" is required. Since this bit is subject to change, we denote the \new" value (or \next" value) of bit i by the symbol Qi+. Example 1: Design a memory circuit with two inputs: S, and R. Depending on the inputs, either a 0 or a 1 is stored in menory, as follows: 1. If S = 0 and R = 1 then 0 is stored in memory 2. If S = 1 and R = 0 then 1 is stored in memory 3. if S = 0 and R = 0 the value of memory remains unchanged. Formal Speci▯cation: 1. Input, State, and Output sets: I = f00, 01, 10g, S = f0, 1g, O = f0, 1g Q S R Q+ 0 0 0 0 0 0 1 0 0 1 0 1 2. State Transition Function:0 1 1 X 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 X NOTE: This tabular representation of the state transition function is called a char- acteristic table. 3. For many sequential systems, the output function simply delivers the value stored in memory, as is the case in this example. Therefore, the output function is: A.H.Dixon CMPT 150: Week 7 (Oct 16 - 18) 49 Q S R z 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 X 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 X Example 2: Design a circuit that counts from 0 to 3 and then repeats as long as a control input, up is equal to 1. Formal Speci▯cation: 1. Input, State, and Output sets: i = f0;1g, S = f00;01;10;11g, O = f00;01;10;11g. In this case, memory is required to remember the current value in the sequence being output. Since there are four possible values, each value must be able to stored in memory and this requires binary sequences of length 2 to be stored. 2. Sate Transition Function: Q1 Q0 up Q1+ Q0+ 0 0 0 0 0 0 0 1 0 1 0 1 0 ) 1 0 1 1 1 0 1 0 0 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 0 0 3. As in the previous example, the output is simply the value stored in memory: Q1 Q0 up z1 z0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 0 0 Formal speci▯cations are more often given as an entity de▯nition and a functional speci▯- cation, just as was the case with combinational circuits described previously. Example: The SR latch is a sequential system whose behavioral description is giv
More Less

Related notes for CMPT 150

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.