TLDR: I built an online tool in 2013 at AUC that gets ~1000 visits a month from students all over the world and is mentioned in a couple of reputable universities material including Columbia University.
7 years ago, while I was pursuing my bachelor’s of Computer Engineering at The American University in Cairo, I had a course called Digital Design, which in retrospect I think was supposed to be called Digital Electronics but who am I to name courses!! The course had nothing to do with design in the common known sense; it was mainly about the design of electronic logic gates to build processors and basic computer systems.
Part of the course was studying the Quine McCluskey algorithm and learning how it works, then the semester project was building a calculator to solve for it in C++.
Luckily after finishing the assignment I checked the domain name quinemccluskey.com and to my surprise, it was available 😯😯
I immediately bought the domain name and started converting my C++ program to a website using my limited knowledge of PHP at the time. I also used one of the earliest versions of Bootstrap for styling. Please don’t judge the UI, it was 2013 😅
Adoption
After publishing the website, I connected it to Google Analytics then I posted the link on several social media websites and added it to the Quine Mccluskey Wikipedia page.
Since this algorithm is a standard topic taught in most CS and Electronics undergraduate programs around the world, it had a relatively wide demand across students all over the world.
Looking at Google Analytics data we can see that over the past 6 years, almost 50k users visited the website.
Also there’s a 28 day average of 943 “Active Users”:
Did you notice any patterns in the visitors timeline?
That’s because students usually use the tool during the assignment period or the Midterms season, which is usually in November or March depending on the semester.
Where do those visitors come from?
Geographically we can see that the heavy load is coming from the US and India.
It’s also worth noting that doing a simple search in the sources datatable we can find visitors coming from these universities internal systems:
- Texas State University (USA)
- MSA (Egypt)
- Auburn University (USA)
- National Ilan University (Taiwan)
- Hunan Normal University (China)
- Ming Chuan University (Taiwan)
- Columbia University (USA)
What is Quine Mccluskey?
In the world of digital logic design, everything is a logical function that can be boiled down to one of the basic arithmetic operations: addition, subtraction, multiplication or division.
Even the most complex processes like image/video processing or machine learning algorithms are converted at the very low level to these simple arithmetic operations so it can run through the physical gates and flip-flops inside the processor/GPU card.
Earlier in computing history, engineers used to design and build such processors manually by finding out how to map a real problem to a series of boolean functions that outputs the correct result when electricity runs through the processing board.
Theoretically a boolean function is an equation that can be represented in multiple ways; however, there should be one optimal way to implement it. Here comes the process of Logic Optimization. One of the most straightforward ways to optimiza boolean functions is the Quine–McCluskey algorithm, which serves the same purpose as the K-maps method but for more variables.
Quine-McCluskey is a tabular and tedious method based on the concept of prime implicants. A prime implicant is a product or sum term, which can’t be further reduced by combining with any other terms of the given Boolean function.
Basically you have to do the following 6 steps to simplify a Boolean Function using Quine–McCluskey.
I omitted explaining the “don’t care” notion for simplicity but you can read about it in depth here.
Step 1: List down all of the minterms in ascending order in binary representation, then group them by the number of 1s in each. This should create a maximum of n+1 groups for n minterms.
Step 2: Compare the minterms in each group with the group after it. If there is a change in only one bit position, replace that one bit with ‘_’.
Step 3: Repeat Step 2 with the First Comparison results to come up with the prime implicants.
Step 4: Create the prime implicants coverage table. Prime implicants are be placed in rows and min terms are placed in columns. Then cross out (X) the cells which correspond to a min term that is covered with a prime implicant.
Step 5: Now we need to get the Essential Prime Implicants. An Essential Prime Implicant is a minterm that is covered by only one prime implicant. These essential prime implicants are the pre-final form the simplified Boolean function.
Step 6: Reduce by removing the row of each essential prime implicant and the columns corresponding to the min terms that are covered in that essential prime implicant.
Repeat Step 5 for prime implicants till all min terms of given Boolean function are completed.
