Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Karnaugh maps c++

  1. Apr 25, 2013 #1
    I need to make a karnaugh map for 4 variables(there is no need to involve don't care terms) which gives the output as the simplified function. There's no need to literally display the map itself I only need an algorithm that takes the input as min terms and displays the simplified output. Anyone got an idea on this. I googled about it and found the Quine–McCluskey algorithm but shouldn't that be used with large number of variables. Suggestions would be helpful
  2. jcsd
  3. Apr 26, 2013 #2
    ...and your own ansatz yet is?
  4. Apr 26, 2013 #3
    All I can think of is using ifs to check the minterms (m0 till m15)
    Assuming all min-terms equal to zero
    E.g if(m0==1){

    cout <<"..."

    } else if(m0==1 && m2==1){

    but then in this way the program won't go to the else-if part even if the other min-terms are 1 along with m0? how to correct it?

    Also is it necessary to implement the Quine-McClusky algorithm for the Karnaugh map or is there any other algo as I only need to make it for 4 variables.
  5. Apr 26, 2013 #4
    If you have absolutely no idea how to implement a solution, write the test routines first.

    There are only 2^(16) ~ 64k possible input tables, so the algorithm you develop can be tested completely.

    By designing a test program, you will come to questions which are also crucial for the solution itself:
    - How to store 16 boolean values efficiently? (consider e.g. std::valarray<bool>, std::bitset, std::vector<bool>)
    - How to map their (linear? two-dimensional?) adresses to ABCD keys and vice-versa?

    That will carry you right into the topic.
  6. Apr 28, 2013 #5
    Im a newbie at programming so can you help me out man..I know how to implement loops,arrays..but seeing the Quin Mccluskey algorithm, its very complex..can't I use something much more simple?
  7. Apr 28, 2013 #6
    I've already given you advice about how to get started.
  8. Apr 28, 2013 #7
    Maybe a more clear one?..I didn't quite get what you meant
  9. Apr 28, 2013 #8
    What could be unclear about this
  10. Apr 29, 2013 #9
    #include <iostream>

    using namespace std;

    int main() {

    int m0,m1,m2,m3,m4,m5,m6,m7,m8,m9,m10,m11,m12,m13,m14,m15;
    int arr[16]={m0,m1,m2,m3,m4,m5,m6,m7,m8,m9,m10,m11,m12,m13,m14,m15};

    cout<<"Enter 1 or 0 in m0: "<< endl;
    cout<<"Enter 1 or 0 in m1: "<< endl;
    cout<<"Enter 1 or 0 in m2: "<< endl;
    cout<<"Enter 1 or 0 in m3: "<< endl;
    cout<<"Enter 1 or 0 in m4: "<< endl;
    cout<<"Enter 1 or 0 in m5: "<< endl;
    cout<<"Enter 1 or 0 in m6: "<< endl;
    cout<<"Enter 1 or 0 in m7: "<< endl;
    cout<<"Enter 1 or 0 in m8: "<< endl;
    cout<<"Enter 1 or 0 in m9: "<< endl;
    cout<<"Enter 1 or 0 in m10: "<< endl;
    cout<<"Enter 1 or 0 in m11: "<< endl;
    cout<<"Enter 1 or 0 in m12: "<< endl;
    cout<<"Enter 1 or 0 in m13: "<< endl;
    cout<<"Enter 1 or 0 in m14: "<< endl;
    cout<<"Enter 1 or 0 in m15: "<< endl;

    cout<<" C'D' "<<"C'D "<<"C D" <<" C D'" << endl;
    cout<<"A'B'"<<" "<< m0<<" "<< m1<<" "<< m3<<" "<<m2<<endl;
    cout<<"A'B"<<" "<< m4<<" "<< m5<<" "<< m7<<" "<< m6<<endl;
    cout<<"A B"<<" "<<m12<<" "<< m13<<" "<< m15<<" "<< m14<<endl;
    cout<<"A B'"<<" "<<m8<<" "<< m9<<" "<< m11<<" "<< m10<<endl;


    cout<<endl<<"Simplified Function is F: "<<1 <<endl;

    else if((m0==0)&&(m1==0)&&(m2==1)&&(m3==0)&&(m4==0)&(m5==0)&&(m6==0)&&(m7==0)&&(m8==0)&&(m9==0)&&(m10==0)&&(m11==0)&&(m12==0)&&(m13==0)&&(m14==0)&&(m15==0))

    cout<<"Simplified Function is F: "<<"A'B'C D'" <<endl;

    else if((m0==0)&&(m1==0)&&(m2==1)&&(m3==1)&&(m4==0)&(m5==0)&&(m6==0)&&(m7==0)&&(m8==0)&&(m9==0)&&(m10==0)&&(m11==0)&&(m12==0)&&(m13==0)&&(m14==0)&&(m15==0))

    cout<<"Simplified Function is F: "<<"A'B'C" <<endl;

    else if((m0==0)&&(m1==1)&&(m2==1)&&(m3==1)&&(m4==0)&(m5==0)&&(m6==0)&&(m7==0)&&(m8==0)&&(m9==0)&&(m10==0)&&(m11==0)&&(m12==0)&&(m13==0)&&(m14==0)&&(m15==0))

    cout<<"Simplified Function is F: "<<"A'B'D+A'B'C" <<endl;


    cout<<"Simplified Function is F: "<<"0" <<endl;

    return 0;

    I made something like this but the possible combinations are around 64k is there a way to make a loop which makes it easier to check all the combinations of 1 and 0? also is the technique right to implement K-maps?

    Suppose I want the user to input the 1 and 0s in one line how can I do that? by storing the values in a string array?
  11. Apr 29, 2013 #10
    Does that by any means explain what was unclear to you about my advice regarding writing test routines first?
  12. Apr 30, 2013 #11
    OK, one more tip:

    All possible input tables can simply be generated by counting for 0 to 0xFFFF in a loop.
    That's the input of your to-be-written program.

    The simplified formula must reproduce that table when you apply it on the 16 ABCD tuples.
  13. Apr 30, 2013 #12
    Can you show this through code please just to let me start off?

    Im sorry but like I said Im a beginner at this so Im not really getting what you meant by the test routines and can you atleast tell that my approach is okay for the algorithm?
  14. Apr 30, 2013 #13
    Well, if even counting from 0 to 0xFFFF in a loop exceeds your current skill, then implementing Quine–McCluskey is way beyond your level.

    I somehow get the feeling that you were just hoping for someone doing your homework for you.
    Last edited: Apr 30, 2013
  15. May 1, 2013 #14
    Its not part of an assignment or homework...I'm not particularly asking for the entire code.If you can explain in simple terms what the whole process would be without using the Quine -McCluskey algorithm then I'm sure I'll get that.

    Until now I've learnt the basic loops,switch statement and simple array formation..Keeping that in mind if you can suggest something then that would be really helpful
  16. May 1, 2013 #15


    Staff: Mentor

    The code you showed earlier had no evidence that you know anything about control structures such as loops and switch statements. Your code defined an array, but did nothing with the array after that.

    One way to start is with a particular example. How would you manually (using paper and pencil) produce the simplified function? Once you understand the technique, then you have a better chance of teaching it to the computer, which is essentially what you're doing when you write a program.
  17. May 1, 2013 #16
    I know how to simplify on paper.but how do I tell the computer to make groups of consecutive 1's? or how to decide the size of the group e.g group of 2 or 4 or 8 minterms (1's)?
  18. May 1, 2013 #17
    I had given you three reasonable alternatives for storing multiple boolean values
    but in your "code" (I'm somewhat reluctant to call that wild lot of characters "code")
    you did not even include one of the respective headers.

    So you haven't followed any advice yet, what would providing more advice be good for?

    And again - your programming skills yet are apparently far below the level you need for implementing Quine -McCluskey.
    Better postpone that endeavour and solve some easier assignments first.
  19. May 1, 2013 #18
    You told how to store multiple bool values but did you tell what to do with them NO!. All I'm saying is that If you can explain what algorithm I'm supposed to apply, it would make things easier. I'm not saying I want to follow the Quine McCluskey (I already posted this in the previous post). No need to get angry man
  20. May 1, 2013 #19


    Staff: Mentor

    I'm sure it would, but part of your work is to come up with or do the research to find an algorithm that you can implement.
    I'm inclined to agree with Solkar's advice - to get more experience in programming by tackling simpler problems.
  21. May 3, 2013 #20
    I know but I just need to know how to group the minterms please I really want to do this
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Similar Threads for Karnaugh maps
UV map to view plane