Sequential serial adders are economically efficient and simple to build. A serial adder consists of a 1-bit full-adder and several shift registers. In serial adders, pairs of bits are added simultaneously during each clock cycle. Two right-shift registers are used to hold the numbers (A and B) to be added, while one left-shift register is used to hold the sum (S). A block diagram of a serial adder is shown in Figure 9.32.
Mealy-type FSM are able to 'react' more quickly than Moore-type FSMs. Briefly describe what characteristic of a Mealy-type FSM makes this the case. Mealy machines 'react' quicker because it has the ability to send the output signal when a certain input condition is met.
Figure 9.32 Block Diagram of a Serial Adder
Figure 9.33 Time Sequence of the Operation of a 4-bit Serial Adder
A finite-state machine adder performs the addition operation on the values stored in the input shift registers and stores the sum in a separate shift register during several clockcycles. During each clock cycle, two input bits ai and bi are shifted from the two input right-shift registers into the 1-bit full-adder, which adds the two bits and evaluates the sum bit si and the carryout bit ci+1. The sum bit si, is shifted out to the left-shift register and the carryout bit ci+1 is stored in the state memory of the serial adder for the next two bits. The time sequence of the operation of a 4-bit serial adder is illustrated in Figure 9.33.
The state memory of a serial adder can only hold a bit for the carryout from a single 2-bit ...
<p>Finite State Machines Lecture 15Salvador Ruiz Correa Centro de Investigaciones en Matemticas04/17/08</p><p>Block Diagram Serial AdderA a Shift register Adder FSM Shift register b s Shift register Sum = A + B</p><p>B Clock</p><p>State Diagram for the Serial Adder FSMReset 00 0 01 1 10 1 ( ab s) 11 0 H 00 1 G: carry-in= 0 H: carry-in= 1 01 0 10 0 11 1</p><p>G</p><p>State Table for the Serial AdderNext state ab =00 G G 01 G H 10 G H 11 H H 00 0 1 Output s 01 1 0 10 1 0 11 0 1</p><p>Present state G H</p><p>State-assigned TablePresent state y 0 1 0 0 Next state ab =00 01 Y 0 1 0 1 1 1 0 1 1 0 10 11 00 Output 01 s 1 0 0 1 10 11</p><p>Figure for the Adder FSMa b Full adder s Y carry-out Clock Reset D Q Q y</p><p>State Diagram for the MooreType Serial Adder FSMReset</p><p>00</p><p>G0 s = 0 00 00</p><p>11</p><p>H0 s = 0</p><p>01 10</p><p>01 10</p><p>11</p><p>11</p><p>01 10</p><p>01 10</p><p>G1 s = 1</p><p>00</p><p>H1 s = 1</p><p>11</p><p>State Table for the Moore-type Serial AdderPresent state G0 G1 H0 H1 Nextstate ab =00 G0 G0 G1 G1 01 G1 G1 H0 H0 10 G1 G1 H0 H0 11 H0 H0 H1 H1 Output s 0 1 0 1</p><p>State Table for the Moore-type Serial AdderPresent state y2 y 1 00 01 10 11 Nextstate ab =00 01 Y2 Y1 00 00 01 01 01 01 10 10 01 01 10 10 10 10 11 11 10 11 Output s 0 1 0 1</p><p>Circuit for the Moore-Type Serial Addera b Sum bit Full adder Carry-out Y1 D Q Q y1 s</p><p>Y2</p><p>D</p><p>Q Q</p><p>y2</p><p>Clock Reset</p><p>State Minimization (1) Two states Si and Sj are said to be equivalent if and only if for every possible input sequence, the same output sequence will be produced regardless of whether Si and Sj is the initial state.</p><p>State Minimization (2) A partition of states consist of one or more blocks where each block comprises a substate of states that ma be equivalent, but the states in a given block are definitely no equivalent to states in other blocks.</p><p>Example State Minimization (1)Present state A B C D E F G Next state w= 0 B D F B F E F w= 1 C F E G C D G Output z 1 1 0 1 0 0 0</p><p>P1 = (ABCDEFG) P2 = (ABD)(CEFG) May be equivalent</p><p>Example State Minimization (2)Present state A B C D E F G Next state w= 0 B D F B F E F w= 1 C F E G C D G Output z 1 1 0 1 0 0 0</p><p>0 and 1- successors of (ABD) 0 .- (BDB) 1.- (CFG)</p><p>P2 = (ABD)(CEFG)</p><p>Example State Minimization (3)Present state A B C D E F G Next state w= 0 B D F B F E F w= 1 C F E G C D G Output z 1 1 0 1 0 0 0</p><p>0 and 1- successors of (CEFG) 0 .- (FFEF) 1.- (ECDG)</p><p>P2 = (ABD)(CEFG)</p><p>Example State Minimization (4)Present state A B C D E F G Next state w= 0 B D F B F E F w= 1 C F E G C D G Output z 1 1 0 1 0 0 0</p><p>P3 = (ABD)(CEG)(F) P4 = (AD)(B)(CEG)(F) P5 = (AD)(B)(CEG)(F)</p><p>P4 = P5 !!!</p><p>Minimized State TablePresent state A B C F Nextstate w= 0 B A F C w= 1 C F C A Output z 1 1 0 0</p><p>Example: Vending Machine The machine accepts 5 and 10 cents coins It takes 15 cents for a piece of candy to be released from the machine If 20 cents is deposited, the machine will not return change, but it will credit the buyer with 5 cents and wait for the buyer to make a second purchase.</p><p>Example: Vending Machine All electronic signals in the vending machine are synchonized to the positive edge of a clock. The clock frequency is 100 (ns) The vending machine coin receptor generates two signals, senseD and senseN,which are asserted when a 10 cent and a 5 cent coin is detected.N-5c D-10c</p><p>Example: Vending Machine Because the coin receptor is a mechanical device, an thus very slow compared to the electronic circuit, inserting a coin causes senseD and senseN, to be set to 1 for a large number of clock cycles The coin rec eptor also generates signals named D and N. The signal D is set for one clock cycle after senseD becomes 1, and N is set to 1 for one clock signal, after senseN becomes 1. If ther is not enough credit to release a candy the vending machine set an output z to 0.</p><p>Signals for Vending MachineClock sense N sense D N D</p><p>(a) Timing diagram</p><p>N sense N Clock D Q Q D Q Q</p><p>(b) Circuit that generates N</p><p>DN Reset DN DN DN D S4 1 N S2 0 D DN S5 1 N S8 1 S6 0 D S9 1 DN DN N S3 0 N D S7 1 S1 0 DN DN</p><p>State Diagram for Vending Machine</p><p>State Table for Vending MachinePresent state S1 S2 S3 S4 S5 S6 S7 S8 S9 Next state DN =00 S1 S2 S3 S1 S3 S6 S1 S1 S3 01 S3 S4 S6 S8 10 S2 S5 S7 S9 11 Output z 0 0 0 1 1 0 1 1 1</p><p>Minimized State Table for Vending MachinePresent state S1 S2 S3 S4 S5 Next state DN =00 S1 S2 S3 S1 S3 01 S3 S4 S2 10 S2 S5 S4 11 Output z 0 0 0 1 1</p><p>DN</p><p>S1 0 N S3 0 N DN S2 0 N D S4 1 D DN S5 1</p><p>DN D DN</p><p>Minimized state diagram for Vending Machine</p>