C/C++ Karnaugh Map C++ Simplification: 4 Var Output w/o Don't Care Terms

  • Thread starter Thread starter uknowwho
  • Start date Start date
  • Tags Tags
    C++
AI Thread Summary
The discussion centers around creating a Karnaugh map for four variables, specifically seeking an algorithm to simplify Boolean functions without using don't care terms. The Quine–McCluskey algorithm is mentioned but deemed overly complex for the user's current programming skills. Suggestions include using basic programming constructs like loops and conditionals to check minterms, but the user struggles with implementing these effectively, particularly in managing multiple boolean values and generating all possible input combinations.The conversation emphasizes the need for the user to first grasp fundamental programming concepts before tackling more complex algorithms. There is a suggestion to develop test routines to better understand the problem and to explore simpler methods for grouping minterms. The user is encouraged to manually simplify functions on paper to gain insights before attempting to automate the process. Overall, the thread highlights the importance of foundational programming knowledge and iterative learning in problem-solving.
uknowwho
Messages
25
Reaction score
0
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
 
Technology news on Phys.org
...and your own ansatz yet is?
 
Solkar said:
...and your own ansatz yet is?

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){

cout<<"..."
}
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.
 
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.
 
Solkar said:
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.

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?
Thanks
 
I've already given you advice about how to get started.
 
Solkar said:
I've already given you advice about how to get started.

Maybe a more clear one?..I didn't quite get what you meant
 
What could be unclear about this
Solkar said:
If you have absolutely no idea how to implement a solution, write the test routines first.
advice?
 
Solkar said:
What could be unclear about this
advice?
#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;
cin>>m0;
cout<<"Enter 1 or 0 in m1: "<< endl;
cin>>m1;
cout<<"Enter 1 or 0 in m2: "<< endl;
cin>>m2;
cout<<"Enter 1 or 0 in m3: "<< endl;
cin>>m3;
cout<<"Enter 1 or 0 in m4: "<< endl;
cin>>m4;
cout<<"Enter 1 or 0 in m5: "<< endl;
cin>>m5;
cout<<"Enter 1 or 0 in m6: "<< endl;
cin>>m6;
cout<<"Enter 1 or 0 in m7: "<< endl;
cin>>m7;
cout<<"Enter 1 or 0 in m8: "<< endl;
cin>>m8;
cout<<"Enter 1 or 0 in m9: "<< endl;
cin>>m9;
cout<<"Enter 1 or 0 in m10: "<< endl;
cin>>m10;
cout<<"Enter 1 or 0 in m11: "<< endl;
cin>>m11;
cout<<"Enter 1 or 0 in m12: "<< endl;
cin>>m12;
cout<<"Enter 1 or 0 in m13: "<< endl;
cin>>m13;
cout<<"Enter 1 or 0 in m14: "<< endl;
cin>>m14;
cout<<"Enter 1 or 0 in m15: "<< endl;
cin>>m15;



cout<<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;





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

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;


else

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?
 
  • #10
Does that by any means explain what was unclear to you about my advice regarding writing test routines first?
 
  • #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.
 
  • #12
Solkar said:
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.

Can you show this through code please just to let me start off?

Im sorry but like I said I am a beginner at this so I am not really getting what you meant by the test routines and can you atleast tell that my approach is okay for the algorithm?
 
  • #13
uknowwho said:
Can you show this through code please just to let me start off?
Im sorry but like I said I am a beginner at this so I am not really getting what you meant by the test routines and can you atleast tell that my approach is okay for the algorithm?

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:
  • #14
Solkar said:
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.

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 learned the basic loops,switch statement and simple array formation..Keeping that in mind if you can suggest something then that would be really helpful
 
  • #15
uknowwho said:
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 learned the basic loops,switch statement and simple array formation..Keeping that in mind if you can suggest something then that would be really helpful
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.
 
  • #16
Mark44 said:
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.

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)?
 
  • #17
I had given you three reasonable alternatives for storing multiple boolean values
Solkar said:
- How to store 16 boolean values efficiently? (consider e.g. std::valarray<bool>, std::bitset, std::vector<bool>)

but in your "code" (I'm somewhat reluctant to call that wild lot of characters "code")
uknowwho said:
#include <iostream>
using namespace std;
int main() {/* */}
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.
 
  • #18
Solkar said:
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.

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
 
  • #19
uknowwho said:
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 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.
uknowwho said:
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
I'm inclined to agree with Solkar's advice - to get more experience in programming by tackling simpler problems.
 
  • #20
Mark44 said:
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.

I know but I just need to know how to group the minterms please I really want to do this
 
  • #21
uknowwho said:
I know but I just need to know how to group the minterms please I really want to do this
First get an understanding of programming in general, then about C++, and until that postpone any musings about what you "need", let alone "want".

The code you posted is so poor that it would be pointless trying to explain to you how to design or select DTs.
 
Back
Top