Quine McCluskey

Table of contents

  1. Introduction
  2. Further reading
  3. References

Introduction

Karnaugh Maps for functions with a large number of literals are difficult to minimise. Usually, a K-map is manageable up to 5 or 6 input literals. MEV can help for functions with a couple more variables. If we look at computer data buses, the information is 8, 16, 32, 64 bits wide or more. Additionally, to do a joint optimisation of functions with multiple output variables, the K-maps for all the combinations of the output variables must be analysed. Also, the visual minimisation using K-maps cannot be programmed to be performed by a computer program.

The Quine-McCluskey method is a tabular recursive algorithm, which can be programmed in software. It has no limitations regarding the number of input or output literals. However, it will take longer and more recursions to process functions with more variables (the complexity grows exponentially).

Further reading

Details of the Quine McCluskey Algorithm can be found in the following references:

  • Chapter 4 “Complements in Combinational Network Design” in [1]
  • Section “Tabular method of minimization” in [2]
  • Section 4.4 “The tabulation procedure for the determination of prime implicants” in [3]
  • Section 6.10 “Quine–McCluskey Minimization” in [4]
  • Wikipedia:Quine–McCluskey algorithm

References

  • [1]G. Donzellini, L. Oneto, D. Ponta, and D. Anguita, Introduction to Digital Systems Design. Springer International Publishing, 2018 [Online]. Available at: https://books.google.cl/books?id=va1qDwAAQBAJ
  • [2]J. Stonham, Digital Logic Techniques. CRC Press, 2017 [Online]. Available at: https://books.google.cl/books?id=a-5HDwAAQBAJ
  • [3]Z. Kohavi and N. K. Jha, Switching and Finite Automata Theory. Cambridge University Press, 2010 [Online]. Available at: https://books.google.cl/books?id=jZIxam8Rb9AC
  • [4]M. Ferdjallah, Introduction to Digital Systems: Modeling, Synthesis, and Simulation Using VHDL. Wiley, 2011 [Online]. Available at: https://books.google.cl/books?id=kJRoR8AAu1AC