reading

Table of Contents

Cover

Title

Preface

1 Synchronous Finite State Machines

1.1. Introduction
1.2. State diagram
1.3. Design of synchronous finite state machines
1.4. Examples
1.5. Equivalent states and minimization of the number of states
1.6. State encoding
1.7. Transformation of Moore and Mealy state machines
1.8. Splitting finite state machines
1.9. Sequence detector implementation based on a programmable circuit
1.10. Practical considerations
1.11. Exercises
1.12. Solutions

2 Algorithmic State Machines

2.1. Introduction
2.2. Structure of an ASM
2.3. ASM chart
2.4. Applications
2.5. Exercises
2.6. Solutions

3 Asynchronous Finite State Machines

3.1. Introduction
3.2. Overview
3.3. Gated D latch
3.4. Muller C-element
3.5. Self-timed circuit
3.6. Encoding the states of an asynchronous state machine
3.7. Synthesis of asynchronous circuits
3.8. Application examples of asynchronous state machines
3.9. Implementation of asynchronous machines using SR latches or C-elements
3.10. Asynchronous state machine operating in pulse mode
3.11. Asynchronous state machine operating in burst mode
3.12. Exercises
3.13. Solutions

Appendix: Overview of VHDL Language

A.1. Introduction
A.2. Principles of VHDL
A.3. Concurrent instructions
A.4. Components
A.5. Sequential structures
A.6. Testbench

Bibliography

Index

End User License Agreement

List of Tables

1 Synchronous Finite State Machines

Table 1.1. State table of an incompletely specified state machine based on Moore model
Table 1.2. Excitation table of the D flip-flop
Table 1.3. Excitation table of the JK flip-flop
Table 1.4. Excitation table of the T flip-flop
Table 1.5. Excitation table of the SR flip-flop
Table 1.6. Transition table of the SR flip-flop
Table 1.7. Transition table of the D flip-flop
Table 1.8. Transition table of the JK flip-flop
Table 1.9. Transition table of the T flip-flop
Table 1.10. State table (Mealy model)
Table 1.11. Transition table (Mealy model)
Table 1.12. State table (Moore model)
Table 1.13. Transition table (Moore model)
Table 1.14. State table of the Moore state machine
Table 1.15. Transition table with Gray encoding
Table 1.16. Example of two-bit codes
Table 1.17. State table
Table 1.18. Transition table that can be used to derive the logic expressions for the D inputs
Table 1.19. Transition table that can be used to derive the logic expressions for the J and K inputs
Table 1.20. State table
Table 1.21. Transition table
Table 1.22. State table
Table 1.23. Reduced state table
Table 1.24. State table
Table 1.25. Implication table
Table 1.26. Implication table
Table 1.27. Implication table when Y_i ≠ Y_j
Table 1.28. Implication table when Y_i = Y_j
Table 1.29. State table
Table 1.30. Implication table
Table 1.31. Implication table after a marking transition
Table 1.32. Reduced state table of the state machine
Table 1.33. State table
Table 1.34. Implication table
Table 1.35. Implication table based on the state table
Table 1.36. Implication table after the first marking pass
Table 1.37. Implication table after the second marking pass
Table 1.38. Reduced state table of the state machine
Table 1.39. State table
Table 1.40. Implication Table based on the state table
Table 1.41. Implication state after the first marking pass
Table 1.42. Reduced state table of the state machine
Table 1.43. State table
Table 1.44. Determining the equivalent states using the partitioning method (example 1)
Table 1.45. Reduced state table
Table 1.46. State table
Table 1.47. Determining the equivalent states using the partitioning approach (example 2)
Table 1.48. Reduced state table
Table 1.49. State table
Table 1.50. Determining the equivalent states using the partitioning approach (example 3)
Table 1.51. Reduced state table
Table 1.52. State table of an incompletely specified machine
Table 1.53. State table in the case where – is assumed to be 0
Table 1.54. State table when – is assumed to be 1
Table 1.55. Reduced state table when – is assumed to be 1
Table 1.56. Reduced state table
Table 1.57. State table for an incompletely specified machine
Table 1.58. State table when – is assumed to be 0
Table 1.59. State table when – is assumed to be 1
Table 1.60. Reduced state table
Table 1.61. State table for example 1
Table 1.62. Reduced state table for example 1
Table 1.63. State table for example 2
Table 1.64. Reduced state table for example 2
Table 1.65. State table for example 3
Table 1.66. Reduced state table for example 3
Table 1.67. a) Implication table based on the state table; b) implication table after a pass
Table 1.68. Number of state encoding possibilities
Table 1.69. Examples of codes for eight states
Table 1.70. State table of the sequence detector
Table 1.71. Transition table of the sequence detector
Table 1.72. Encoding the states of submachine 1
Table 1.73. Encoding the states of submachine 2
Table 1.74. State table of the sequence detector
Table 1.75. Transition table of the sequence detector
Table 1.76. Transition table
Table 1.77. State table
Table 1.78. State table
Table 1.79. Truth table
Table 1.80. Truth table
Table 1.81. State table (Moore model)
Table 1.82. State table for machine 2
Table 1.83. Table illustrating the operation of the detector
Table 1.84. State table for the finite state machine 1
Table 1.85. State table for the finite state machine 2
Table 1.86. State table for the finite state machine 1
Table 1.87. State table for the finite state machine 1
Table 1.88. State table for the finite state machine 2
Table 1.89. State table for the finite state machine 2
Table 1.90. State table (machine 1)
Table 1.91. State table (machine 2)
Table 1.92. State table (machine 3)
Table 1.93. State table (machine 4)
Table 1.94. Illustration of the operation of the state machine a
Table 1.95. Illustration of the operation of the state machine b
Table 1.96. Transition table of the flip-flop
Table 1.97. Truth table
Table 1.98. Excitation table of the flip-flop
Table 1.99. Truth table
Table 1.100. Truth table
Table 1.101. Function table
Table 1.102. State table (Mealy model)
Table 1.103. State table (Moore model)
Table 1.104. State table (Mealy model)
Table 1.105. State table (Moore model)
Table 1.106. Transition table (Moore model)
Table 1.107. State table
Table 1.108. State table
Table 1.109. Transition table
Table 1.110. State table
Table 1.111. Transition table
Table 1.112. Table that can be used to derive the logic expressions for the flip-flop inputs
Table 1.113. State table
Table 1.114. Transition table
Table 1.115. State table (case a)
Table 1.116. State table (case b)
Table 1.117. Table that can be used to derive the logic expressions for the J and K inputs (case a)
Table 1.118. Table that can be used to derive the logic expressions for the J and K inputs (case b)
Table 1.119. Table that can be used to derive the logic expressions of the flip-flop inputs
Table 1.120. State table of the state machine 1
Table 1.121. State table of the state machine 2
Table 1.122. Implication table according to the state table
Table 1.123. Implication Table after the first marking pass
Table 1.124. Reduced state table for the state machine 1
Table 1.125. Implication table according to the state table
Table 1.126. State Table after one marking pass
Table 1.127. Implication table after two marking pass
Table 1.128. Reduced state table for the state machine 2
Table 1.129. State table of the state machine 1
Table 1.130. State table of the state machine 2
Table 1.131. Determination of equivalent states using the partitioning method (state machine 1)
Table 1.132. Reduced state table (state machine 1)
Table 1.133. Determination of equivalent states using the partitioning method (state machine 2)
Table 1.134. Reduced state table (state machine 2)
Table 1.135. State table of the state machine 1
Table 1.136. Determination of equivalent states using the partitioning method (state machine 1)
Table 1.137. Reduced state table (state machine 1)
Table 1.138. State table of the state machine 2
Table 1.139. Determination of equivalent states using the partitioning method (state machine 2)
Table 1.140. Reduced state table (state machine 2)
Table 1.141. State table (state machine 1)
Table 1.142. State table (state machine 2)
Table 1.143. State table (state machine 3)
Table 1.144. State table (state machine 4)
Table 1.145. Implication Table: a) based on the state table; b) after one marking pass; c) after two marking pass
Table 1.146. Reduced state table (state machine 1)
Table 1.147. Reduced state table (state machine 2)
Table 1.148. Implication table a) based on the state table and b) after one marking pass
Table 1.149. Implication table a) based on the state table, b) after one marking pass and c) after two marking pass
Table 1.150. Reduced state table (state machine 3)
Table 1.151. Reduced state table (state machine 4)
Table 1.152. State table
Table 1.153. Transition table
Table 1.154. Transition table
Table 1.155. Transition table
Table 1.156. State table
Table 1.157. Reduced state table
Table 1.158. Transition table

2 Algorithmic State Machines

Table 2.1. Truth table of a full adder
Table 2.2. State table of the serial adder with encoded states
Table 2.3. State table of the serial adder
Table 2.4. State table of the control unit
Table 2.5. Transition table
Table 2.6. Serial adder/subtracter: summary of the control signals with the corresponding operations and the components involved
Table 2.7. Multiplier: summary of the control signals with the corresponding operations and the components involved
Table 2.8. Divider: summary of the control signals with the corresponding operations and the components involved
Table 2.9. Binary code associated with each type of coin
Table 2.10. State table of the controller
Table 2.11. Transition table
Table 2.12. State table of the state machine
Table 2.13. State table
Table 2.14. State table
Table 2.15. State table
Table 2.16. State table of the signal generator

3 Asynchronous Finite State Machines

Table 3.1. State table of the gated D latch
Table 3.2. Excitation table of the SR latch
Table 3.3. Truth table of the Muller C-element
Table 3.4. Excitation table of the C-element
Table 3.5. Transition table
Table 3.6. Flow table
Table 3.7. Flow table for a state machine using shared-row state assignment
Table 3.8. Flow table of a state machine using multiple-row state assignment
Table 3.9. Flow table
Table 3.10. Flow table
Table 3.11. Transition table
Table 3.12. Flow table
Table 3.13. Initial flow table of the pulse synchronizer
Table 3.14. Reduced flow table of the pulse synchronizer
Table 3.15. Primitive flow table of the modulo 4 counter
Table 3.16. Transition table of the modulo 4 counter
Table 3.17. Comparison of excitation tables for the C-element, SR latch and complementary C-element
Table 3.18. Flow table
Table 3.19. Excitation table of a flip-flop configured to operate in pulse mode
Table 3.20. Flow table of the sequence detector
Table 3.21. Flow table of the controller for a digital lock
Table 3.22. Flow table
Table 3.23. Flow table
Table 3.24. Flow table of an asynchronous state machine
Table 3.25. Flow table
Table 3.26. Flow table
Table 3.27. Flow table
Table 3.28. State assignments
Table 3.29. Primitive flow table of the discriminator
Table 3.30. Reduced flow table of the discriminator
Table 3.31. Transition table
Table 3.32. Extended flow table
Table 3.33. Table showing present states/next states
Table 3.34. Flow table
Table 3.35. Flow table
Table 3.36. Flow table
Table 3.37. Transition table
Table 3.38. Flow table

Appendix: Overview of VHDL Language

Table A.1. State table of the 1011 sequence detector (Mealy model)

List of Figures

1 Synchronous Finite State Machines

Figure 1.1. Finite state machine: Moore model (NS: next state; PS: present state)
Figure 1.2. Finite state machine: Mealy model (NS: next state; PS: present state)
Figure 1.3. Moore state machine: state diagram with present state and next state
Figure 1.4. Mealy state machine: a) state diagram; b) map showing input/next state from state B
Figure 1.5. Section of a state diagram
Figure 1.6. Examples of state diagram sections and maps showing the input/next state from state A
Figure 1.7. State diagram for an incompletely specified state machine based on Moore model
Figure 1.8. State encoding
Figure 1.9. SR flip-flop: a) circuit and symbol; b) state diagram
Figure 1.10. D flip-flop: a) symbol; b) state diagram
Figure 1.11. JK flip-flop: a) symbol; b) state diagram
Figure 1.12. T flip-flop: a) circuit and symbol; b) state diagram
Figure 1.13. D flip-flop with a synchronous reset input and enable signal: a) logic circuit; b) timing diagram
Figure 1.14. State diagram (Mealy model)
Figure 1.15. Mealy state machine: Karnaugh maps for a) A⁺; b) B⁺; c) Y
Figure 1.16. Logic circuit (Mealy model)
Figure 1.17. Mealy state machine: a) ideal timing diagram; b) non-ideal timing diagram
Figure 1.18. State diagram (Moore model)
Figure 1.19. Karnaugh maps (Moore model)
Figure 1.20. Logic circuit (Moore model)
Figure 1.21. Timing diagram (Moore model)
Figure 1.22. Karnaugh maps for the Moore state machine with the states represented according to Gray code
Figure 1.23. State diagram when the overlapping of bits is not taken into account: a) Mealy model; b) Moore model
Figure 1.24. Detector for the sequences 110 and 101: a) Moore model; b) Mealy model
Figure 1.25. Input D₁ D₁ = Q₁ · X + Q₂ · X
Figure 1.26. Input D₂ D₂ = Q₁ · X + · X
Figure 1.27. Logic circuit using D flip-flops
Figure 1.28. Input J₁ J₁ = Q2 · X
Figure 1.29. Input K₁ K₁ =
Figure 1.30. Input J₂ J₂ = X
Figure 1.31. Input K₂ K₂ = + 1
Figure 1.32. Logic circuit using JK flip-flops
Figure 1.33. State diagram of the pulse generator
Figure 1.34. Function A⁺
Figure 1.35. Function B⁺
Figure 1.36. Logic circuit for the pulse generator
Figure 1.37. a) Merger graph. Simplified merger graph: b) compatible states and c) incompatible states
Figure 1.38. Compatibility graph
Figure 1.39. Merger graph: a) compatible states; b) incompatible states
Figure 1.40. a) Merger graph. Simplified merger graph: b) compatible states and c) incompatible states
Figure 1.41. Compatibility graph
Figure 1.42. State diagram (Mealy model)
Figure 1.43. Function A⁺ = · B
Figure 1.44. Function B⁺ = X
Figure 1.45. Function C⁺ = ·
Figure 1.46. Output Y = X · A
Figure 1.47. Logic circuit of the 101 sequence detector (Mealy state machine whose states are represented using the 1-out-of-3 code)
Figure 1.48. Transformation examples of a Moore model to a Mealy model
Figure 1.49. Transformation examples of a Mealy model to a Moore model
Figure 1.50. Splitting rule: case of a single transition
Figure 1.51. Splitting rule: case of several transitions
Figure 1.52. State diagrams: a) initial finite state machine; b) finite state machine obtained after the splitting
Figure 1.53. Implementation of the state machine
Figure 1.54. Implementation using a clock signal synchronization system
Figure 1.55. Timing diagram
Figure 1.56. State diagrams: a) initial finite state machine; b) finite state machines obtained after the splitting
Figure 1.57. Implementation of the state machine
Figure 1.58. State diagram of the sequence detector
Figure 1.59. Function A⁺
Figure 1.60. Function B⁺
Figure 1.61. Function C⁺
Figure 1.62. Output Y
Figure 1.63. Sequence detector implemented by programming a PAL
Figure 1.64. a) Suppression of transient signals by filtering; b) timing diagram
Figure 1.65. Illustration of the timing characteristics of a logic circuit
Figure 1.66. Logic circuit of the 101 sequence detector
Figure 1.67. Finite state machine with a synchronization stage
Figure 1.68. State diagram
Figure 1.69. Logic circuit
Figure 1.70. Logic circuit
Figure 1.71. Finite state machine for the sequential generation of two’s complement
Figure 1.72. Serial comparator
Figure 1.73. Two-bit a) and three-bit b) shift registers
Figure 1.74. Finite state machines
Figure 1.75. State diagram: a) machine 1; b) machine 2
Figure 1.76. Finite state machine (Moore model)
Figure 1.77. Timing diagram
Figure 1.78. Finite state machine (Mealy model)
Figure 1.79. Timing diagram 1
Figure 1.80. Timing diagram 2
Figure 1.81. Moore model: a) machine 1; b) machine 2
Figure 1.82. Mealy model: a) machine 1; b) machine 2
Figure 1.83. Mealy model: a) machine 1; b) machine 2
Figure 1.84. Modulo 6 counter
Figure 1.85. State diagram of the 010 and 1001 sequence detector
Figure 1.86. Logic circuit
Figure 1.87. Timing diagram
Figure 1.88. Logic circuit
Figure 1.89. Timing diagram
Figure 1.90. Bus arbiter
Figure 1.91. Labyrinth
Figure 1.92. State diagram
Figure 1.93. State diagram
Figure 1.94. a) Karnaugh map; b) state diagram
Figure 1.95. Logic circuit
Figure 1.96. Karnaugh maps: a) J; b) K
Figure 1.97. Logic circuit
Figure 1.98. State diagram
Figure 1.99. State diagram
Figure 1.100. State diagram (Mealy model)
Figure 1.101. Karnaugh maps for a) Q⁺ and b) Y; c) logic circuit
Figure 1.102. State table (Moore model)
Figure 1.103. Karnaugh maps: a) A⁺; b) B⁺; c) Y
Figure 1.104. Logic circuit
Figure 1.105. State diagram: a) Mealy model b) Moore model
Figure 1.106. State diagram (Mealy model)
Figure 1.107. Karnaugh maps for a) Q⁺ and b) Y; c) logic circuit
Figure 1.108. State diagram (Moore model)
Figure 1.109. Karnaugh maps: a) A⁺; b) B⁺; c) Y
Figure 1.110. Logic circuit
Figure 1.111. Karnaugh maps: a) X⁺; b) Y ⁺
Figure 1.112. Karnaugh maps: a) O_A>B; b) O_A=B; c) O_A<B
Figure 1.113. Logic circuit of the serial comparator
Figure 1.114. State diagram: a) two-bit register; b) three-bit register
Figure 1.115. Finite State Machine
Figure 1.116. State diagram
Figure 1.117. Timing diagram
Figure 1.118. State table of the counter
Figure 1.119. Function A⁺ A⁺ = D₁ = Ā · B · + Ā · · C
Figure 1.120. Function B⁺ B⁺ = D₂ = A · B · C + Ā · · C + Ā ·
Figure 1.121. Logic circuit of the counter (outputs: A and B)
Figure 1.122. State diagram of the 010 sequence detector
Figure 1.123. Input J₁ J₁ = B · X
Figure 1.124. Input K₁ K₁ = B + X
Figure 1.125. Input J₂ J₂ =
Figure 1.126. Input K₂ K₂ = X. For a color version of this figure, see www.iste.co.uk/ndjountche/electronics3.zip
Figure 1.127. Logic circuit of the 010 sequence detector
Figure 1.128. State diagram
Figure 1.129. Timing diagram 1. For a color version of this figure, see www.iste.co.uk/ndjountche/electronics3.zip
Figure 1.130. Timing diagram 2 (synchronization problem). For a color version of this figure, see www.iste.co.uk/ndjountche/electronics3.zip
Figure 1.131. Input J₁ J₁ = · B
Figure 1.132. Input J₂ J₂ = + A
Figure 1.133. Input K₁ K₁ = X ·
Figure 1.134. Input K₂ K₂ = X + Ā
Figure 1.135. State diagram (case a)
Figure 1.136. State diagram (case b)
Figure 1.137. Input J₁ J₁ = X · B
Figure 1.138. Input K₁ K₁ = 1
Figure 1.139. Input J₂ (a) J₂ =
Figure 1.140. Input K₂ K₂ = X
Figure 1.141. Input J₂ (b) J₂ = · Ā
Figure 1.142. Output Y Y = · A ·
Figure 1.143. Inputs D₁ D₁ = Ā + B · C
Figure 1.144. Input D₂ D₂ = Ā +
Figure 1.145. Input D₃ D₃ = A · B + Ā ·
Figure 1.146. State diagram D₃ = A · B + Ā ·
Figure 1.147. State diagram D₃ = A · B + Ā · C
Figure 1.148. Input J₁ J₁ = 1
Figure 1.149. Input J₂ J₂ = 1
Figure 1.150. Input J₃ J₃ = A
Figure 1.151. Input K₁ K₁ = +
Figure 1.152. Input K₂ K₂ = A
Figure 1.153. Input K₃ K₃ = A ·
Figure 1.154. State diagram (JK flip-flops)
Figure 1.155. a) Merger graph; b) simplified merger graph for compatible states; c) simplified merger graph for incompatible states; d) compatibility graph
Figure 1.156. a) Simplified merger graph for compatible states; b) simplified merger graph for incompatible states; c) compatibility graph
Figure 1.157. a) Simplified merger graph for compatible states; b) simplified merger graph for incompatible states; c) compatibility graph
Figure 1.158. a) Subgraph of the merger graph for compatible states; b) subgraph for merger graph of incompatible states
Figure 1.159. Moore model: a) state machine 1; b) state machine 2
Figure 1.160. Equivalent Mealy model: a) state machine 1; b) state machine 2
Figure 1.161. Mealy model: a) state machine 1; b) state machine 2
Figure 1.162. Moore model: a) state machine 1; b) state machine 2
Figure 1.163. Mealy model: a) state machine 1; b) state machine 2
Figure 1.164. Moore model: a) state machine 1; b) state machine 2
Figure 1.165. State diagram of the modulo 6 counter
Figure 1.166. State diagram of the 010 and 1001 sequence detector
Figure 1.167. State diagram of the modulo 6 counter (after splitting)
Figure 1.168. State diagram of the 010 and 1001 sequence detector (after splitting)
Figure 1.169. Timing diagram
Figure 1.170. Timing diagram
Figure 1.171. State diagram
Figure 1.172. Input T₁ T₁ = Y
Figure 1.173. Input T₂ T₂ = B · + · X
Figure 1.174. Output Z Z = A · B + X · A + X · B
Figure 1.175. Logic circuit
Figure 1.176. State diagram
Figure 1.177. Input D₁ D₁ = X · + X · + X · Q₂
Figure 1.178. Input D₂ D₂ = X · Q₂ + Q₁ · Q₂ + Q₁ ·
Figure 1.179. Output D₃ D₃ = Q₂
Figure 1.180. Logic circuit of the median filter
Figure 1.181. State diagram
Figure 1.182. Input D₁ D₁ = = · R_B + R_B · Q₁
Figure 1.183. Input D₂ D₂ = = R_A + R_B
Figure 1.184. Bus arbiter
Figure 1.185. Operation principle of the robot ant
Figure 1.186. State diagram
Figure 1.187. Input D₁ D₁ = · · Q₂ + · Q₁ + Q₁ ·
Figure 1.188. Input D₂ D₂ = R + L · Q₂ + L ·
Figure 1.189. Output TR TR = Q₂
Figure 1.190. Output TL TL = Q₁ ·
Figure 1.191. Output F F = Q₁ +
Figure 1.192. Logic circuit (robot ant)

2 Algorithmic State Machines

Figure 2.1. Structure of a digital system
Figure 2.2. Symbols representing a) the outputs, b) the decisions and c) the conditional outputs
Figure 2.3. Symbols and corresponding logic circuits
Figure 2.4. Section of an ASM chart and the corresponding logic circuit
Figure 2.5. a) ASM chart for a Mealy machine; b) state diagram
Figure 2.6. a) ASM chart for a Moore machine; b) state diagram
Figure 2.7. a) Incorrect and b) correct representations of a loop in an ASM chart
Figure 2.8. Examples of ASM chart sections
Figure 2.9. Representations of equivalent ASM chart sections
Figure 2.10. Karnaugh map for the next state Q⁺
Figure 2.11. Karnaugh map for the output S
Figure 2.12. Bit-serial adder: a) state diagram; b) logic circuit
Figure 2.13. Datapath and control unit for a serial adder/subtracter
Figure 2.14. ASM chart of the control unit (N = 4)
Figure 2.15. Karnaugh maps: a) J_A; b) K_A; c) J_B; d) K_B = Done; e) LoadR (PrCNT = ); f) Enable; g) ClrD; h) PrD; i) Compl
Figure 2.16. Control circuit
Figure 2.17. Timing diagram of the serial adder/subtracter (/sub = 1)
Figure 2.18. Four-bit multiplier based on addition and shift operations
Figure 2.19. ASM chart of the control unit (N = 4)
Figure 2.20. a) Multiplication of two unsigned binary numbers; b) operation principle of the multiplier
Figure 2.21. A divider based on subtraction and shift operations
Figure 2.22. ASM chart of the control unit (N = 4)
Figure 2.23. a) Division of two unsigned binary numbers; b) operation principle of the divider
Figure 2.24. Automatic vending machine
Figure 2.25. ASM chart for the controller of the automatic vending machine
Figure 2.26. Intersection with traffic lights. for a color version of this figure, www.iste.co.uk/ndjountche/electronics3.zip
Figure 2.27. Traffic light controller
Figure 2.28. Logic circuit of the counter
Figure 2.29. ASM chart of the traffic light controller
Figure 2.30. Input D₁
Figure 2.31. Input D₂
Figure 2.32. Input D₃
Figure 2.33. Output IC
Figure 2.34. Output NR
Figure 2.35. Output NG
Figure 2.36. Output NY
Figure 2.37. Output ER
Figure 2.38. Output EG
Figure 2.39. Output EY
Figure 2.40. Logic circuit for the controller of the traffic lights
Figure 2.41. Two ASM chart versions for a finite state machine
Figure 2.42. ASM chart of a finite state machine
Figure 2.43. ASM charts: machine a); machine b)
Figure 2.44. ASM chart of the programmable signal generator
Figure 2.45. Timing diagram of the programmable signal generator
Figure 2.46. State diagram (Mealy machine) of the controller
Figure 2.47. ASM chart of the finite state machine
Figure 2.48. ASM chart of the finite state machine
Figure 2.49. Karnaugh maps for the determination of a) , b) and c) Z
Figure 2.50. Timing diagram of the programmable signal generator
Figure 2.51. Logic circuit of the ROM-based programmable signal generator
Figure 2.52. Truth table (decoder inputs/ROM outputs)
Figure 2.53. State diagram (Moore model) of the elevator controller

3 Asynchronous Finite State Machines

Figure 3.1. a) Logic circuit for a gated D latch; b) equivalent circuit in fundamental mode
Figure 3.2. Karnaugh maps: a) stable states; b) characteristic equation Q⁺
Figure 3.3. Timing diagram illustrating the effect of propagation delays
Figure 3.4. a) Karnaugh map; b) improved version of the logic circuit for the gated D latch
Figure 3.5. Karnaugh maps: a) S = D · C; b)
Figure 3.6. Implementation of a gated D latch based on an SR latch
Figure 3.7. a) Logic circuit b) symbol and c) timing diagram of the Muller C-element
Figure 3.8. a) Logic circuit and b) symbol of the C-element with a reset input
Figure 3.9. Karnaugh maps: a) S = A · B; b)
Figure 3.10. Implementation of the C-element using an SR latch
Figure 3.11. a) Handshake communication system based on a two-phase protocol; b) timing diagram
Figure 3.12. a) Handshake communication system based on a four-phase protocol; b) timing diagram
Figure 3.13. Implementation of a pipeline datapath based on a two-phase protocol
Figure 3.14. Transition diagram
Figure 3.15. Universal encoding when the minimum number of states does not exceed a) 4, and b) 8
Figure 3.16. a) State diagram; b) Karnaugh map illustrating an oscillatory cycle
Figure 3.17. a) State diagram after transformation; b) Karnaugh map illustrating the elimination of the oscillatory cycle
Figure 3.18. State diagram
Figure 3.19. Karnaugh maps:
Figure 3.20. Logic circuit
Figure 3.21. Karnaugh maps: a) S₁; b) R₁; c) S₀; d) R₀; e) Z
Figure 3.22. Logic circuit
Figure 3.23. a) State diagram; b) Karnaugh map illustrating an essential hazard
Figure 3.24. a) Logic circuit of the state machine; b) timing diagram illustrating the effect of the essential hazard on the state machine operation
Figure 3.25. Logic circuit of the state machine with delay elements
Figure 3.26. Logic circuit of an asynchronous state machine
Figure 3.27. a) State diagram; b) Karnaugh map illustrating the path taken by the state machine due to the d-trio hazard
Figure 3.28. Section of a state diagram
Figure 3.29. a) Symbol and b) timing diagram of a pulse synchronizer
Figure 3.30. Initial state diagram of the pulse synchronizer
Figure 3.31. Karnaugh maps for two different state encodings
Figure 3.32. Karnaugh maps: a) X⁺; b) Y⁺
Figure 3.33. Logic circuit of the pulse synchronizer
Figure 3.34. State diagram of the modulo 4 counter
Figure 3.35. Karnaugh maps: a) ; b) ; c) ; d) Z₁; e) Z₀
Figure 3.36. Logic circuit of the counter
Figure 3.37. a) Symbols of C-element, b) an SR latch and c) a complementary C-element
Figure 3.38. Communication system
Figure 3.39. Karnaugh maps: a) S₀; b) R₀; c) S₁; d) R₁; e) P_X; (f) P_Y
Figure 3.40. Logic circuit of the arbiter based on SR latches
Figure 3.41. Logic circuit of the arbiter based on C-elements
Figure 3.42. Flip-flops activated by a) the falling edge or b) the rising edge of a data signal
Figure 3.43. State diagram of the sequence detector
Figure 3.44. Karnaugh maps: a) TA; b) TB; c) Z
Figure 3.45. Logic circuit of the sequence detector
Figure 3.46. State diagram of the controller for a digital lock
Figure 3.47. Karnaugh maps: (a) T_A; (b) T_B; (c) Z
Figure 3.48. Logic circuit of the controller for a digital lock
Figure 3.49. Rotation-direction discriminator
Figure 3.50. Bus arbiter
Figure 3.51. State diagram
Figure 3.52. State diagram
Figure 3.53. State diagram
Figure 3.54. State diagram
Figure 3.55. State diagram
Figure 3.56. Logic circuit
Figure 3.57. Karnaugh maps: a) A⁺; b) B⁺; c) Z
Figure 3.58. Logic circuit of the discriminator
Figure 3.59. State diagram
Figure 3.60. Function X⁺ X⁺ = · R_B + R_B · X · Y
Figure 3.61. Function Y⁺ Y⁺ = R_A + R_B
Figure 3.62. Bus arbiter
Figure 3.63. Karnaugh maps:
Figure 3.64. Logic circuit
Figure 3.65. Karnaugh maps: a) S₁; b) R₁; c) S₀; d) R₀; e) Q
Figure 3.66. Logic circuit based on SR latches
Figure 3.67. Logic circuit based on C-elements
Figure 3.68. Transition diagram
Figure 3.69. State diagram
Figure 3.70. State diagram
Figure 3.71. Karnaugh maps:
Figure 3.72. Logic circuit
Figure 3.73. Karnaugh maps:
Figure 3.74. a) State diagram; b) logic circuit
Figure 3.75. Karnaugh maps: a) S₁; b) R₁; c) S₀; d) R₀; e) H; f) L
Figure 3.76. Logic circuit
Figure 3.77. Karnaugh maps: a) T_A; b) T_B; c) Z
Figure 3.78. Logic circuit
Figure 3.79. State diagram

First published 2016 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd
27-37 St George’s Road
London SW19 4EU
UK

www.iste.co.uk

John Wiley & Sons, Inc.
111 River Street
Hoboken, NJ 07030
USA

www.wiley.com

The rights of Tertulien Ndjountche to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Control Number: 2016950312

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN 978-1-84821-986-1

Digital Electronics 3

Finite-state Machines