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

[uknowwho]

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

 

[Solkar]

...and your own ansatz yet is?

 

[uknowwho]

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

count <<"..."

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

count<<"..."
}
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.

 

[Solkar]

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.

 

[uknowwho]

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

 

[Solkar]

I've already given you advice about how to get started.

 

[uknowwho]

I've already given you advice about how to get started.

Maybe a more clear one?..I didn't quite get what you meant

 

[Solkar]

What could be unclear about this

If you have absolutely no idea how to implement a solution, write the test routines first.

advice?

 

[uknowwho]

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





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



count<<endl;
count<<" C'D' "<<"C'D "<<"C D" <<" C D'" << endl;
count<<"A'B'"<<" "<< m0<<" "<< m1<<" "<< m3<<" "<<m2<<endl;
count<<"A'B"<<" "<< m4<<" "<< m5<<" "<< m7<<" "<< m6<<endl;
count<<"A B"<<" "<<m12<<" "<< m13<<" "<< m15<<" "<< m14<<endl;
count<<"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))

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


count<<"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))

count<<"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))


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


else

count<<"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?

 

[Solkar]

Does that by any means explain what was unclear to you about my advice regarding writing test routines first?

 

[Solkar]

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.

 

[uknowwho]

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?

 

[Solkar]

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.

 

[uknowwho]

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

 

[Mark44]

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.

 

[uknowwho]

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

 

[Solkar]

I had given you three reasonable alternatives for storing multiple boolean values

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

#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.

 

[uknowwho]

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

 

[Mark44]

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.

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.

 

[uknowwho]

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

 

[Solkar]

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.