K-map Problems And Solutions

[Granville Turley]

I understand how, for example, you can map between SOP (sum-of-product) expressions and a K-map, and why in general you would expect the K-map optimized expression to be simpler, since finding a maximal grouping of 1's corresponds to finding some of the redundancies in a naive SOP expression.

I can vaguely see that the K-map method might not produce optimal solutions, because it seems like the only thing we are actually doing is taking advantage of the distributive and identity (A + A' = 1) properties of the Boolean algebra. But I don't really understand what algebraic operations we are not performing with the K-map, that might allow us to reach a more optimal solution.

I was trying to read: thisbut in that paper, it is just cited that the problem of finding an optimal Boolean expression is in NP, and I think the author is just implicitly saying that K-maps cannot be optimal, since as an algorithm they are not running in NP time.

If you are only using or and and and your input function is shorter than your output function, you are using parenthesis in your input. If that is the case, you will also be able to factor out some variables in the output of the k-map (using boolean algebra), and you'll get an equation that is at least as short.

Generalization: Minimizing a boolean function is like finding the equation for any other series of numbers. There will always be multiple solutions. But which function is the simplest? I might say: "give me a function that returns 1 for 0, 2 for 1, 4 for 2 and 8 for 3". You could say "the function is pow(2,x)". And I could say "wrong! I was thinking of 1

When I say "my function is simpler cause I am simply xor'ing all terms", you could say: "but if I add an extra variable and it doesn't follow your pattern, your function is getting too unwieldy and complex, mine simply still follows the SOP or POS pattern".

If it helps someone, I shall just try to describe the challenges that I faced in terms of optimality when I tried to implement K-map in python. Here is the greedy algorithm I used for a 4-variable boolean function in SOP form:

Using the above steps, I got stuck to the following local minimum first, which was definitely a minimal representation of SOPs but not a minimum representation:f(w,x,y,z) = xy + xz + wxy + wxz. It took 4 minterms to represent f, which is suboptimal. The critical mistake done by the algorithm was that it chose couple of 3-variable minterms wxy and wxz, when a single one (wyz) would suffice, since it was checking the minterms in a certain order and chose the one that had some overlap with the ones not yet covered. Once it chose wxy, it must had to choose another minterm, since a one was still uncovered.

As we know that K-map takes both SOP and POS forms. So, there are two possible solutions for K-map, i.e., minterm and maxterm solution. Let's start and learn about how we can find the minterm and maxterm solution of K-map.

In the next step, we find the boolean expression for each group. By looking at the common variables in cell-labeling, we define the groups in terms of input variables. In the below example, there is a total of two groups, i.e., group 1 and group 2, with two and one number of 'ones'.

In the first group, the ones are present in the row for which the value of A is 0. Thus, they contain the complement of variable A. Remaining two 'ones' are present in adjacent columns. In these columns, only B term in common is the product term corresponding to the group as A'B. Just like group 1, in group 2, the one's are present in a row for which the value of A is 1. So, the corresponding variables of this column are B'C'. The overall product term of this group is AB'C'.

Lastly, we find the boolean expression for the Output. To find the simplified boolean expression in the SOP form, we combine the product-terms of all individual groups. So the simplified expression of the above k-map is as follows:

The education system evolves and transforms towards interactive and immersive learning tools in this digital age. Augmented reality has also evolved as a ubiquitous, robust, and effective technology for providing innovative educational tools. In engineering education, many abstract concepts require technological intervention for conceptual understanding and better instructional content. While learning through the immersive tools, system usability has great importance in terms of effectiveness, efficiency, and satisfaction. Effectiveness refers to users' accuracy and completeness in achieving defined goals; efficiency relates to expended resources about the precision and completeness with which users achieve their objectives; satisfaction deals with a positive attitude towards using the product. If the system fails to provide good usability, it may cause adverse effects such as increasing stress, lacking necessary features, increasing the users' cognitive load, and negatively impacting the student's motivation. In this study, two mobile augmented reality (MAR) applications were developed as an instructional tool to teach the students about Karnaugh maps in the digital electronics course. The first application is a Keypad-based MAR application that uses a keypad matrix for user interaction and the second application is a Marker-based MAR application that uses multiple markers to solve K-Map for producing an optimum solution of the given problem. An experimental study was conducted to determine the student's opinion of the developed MAR applications. The study was designed to determine the system usability of the two MAR applications using the System Usability Score (SUS) and Handheld Augmented Reality Usability Score (HARUS) models. 90 engineering students participated in the study, and they were randomly divided into two different groups: keypad-based group and Marker-based group. The keypad-based group included 47 students who had hands-on experience with a keypad-based MAR application, whereas the marker-based group included 43 students who had hands-on experience with multiple marker-based MAR applications. The experimental outcomes indicated that the keypad-based MAR application has better SUS and HARUS scores than the marker-based MAR application which suggests that the keypad-based MAR application has provided better user interaction.

Learning is an ongoing process for everyone. Traditional teaching approaches depend on the information learned from books and teachers and then applied to solve real-world problems (Dutta et al., 2020). The education system continues to evolve and transform towards a collaborative learning model. Students learn through social networks, collaboration, and immersion in digital spaces to seek, share and create information for self-realization (US Department of Education & Office of Educational Technology, 2017). Universities emphasize incorporating Information and Communication Technology (ICT) tools in the classroom to fulfill learners' demands. Learning through such kinds of environments and tools is known as e-learning (Thamarana, 2016). E-Learning is a form of technology in which learning materials are distributed digitally through the Internet, thereby promoting learning by removing time, distance, and socio-economic barriers (Gohiya, n.d.). HTML pages with embedded images and videos make up most e-learning systems. They are all two-dimensional and lack interactivity (Kumar et al., 2020). Many educators believed that interactivity creates an enjoyable learning environment where students can build interest and use the problem-solving approach towards any real-time problem situation. Ubiquitous learning (u-learning) and mobile learning (m-learning) were used to make the learning more realistic and interactive (Chang et al., 2018). They both use similar tools but may use in different ways. U-learning offers dynamic content and requires a specialized environment, whereas m-learning is flexible to use at any place and offers the scalability feature (Vallejo-Correa et al., 2021). Nowadays, Virtual Reality (VR) and Augmented Reality (AR) are the technologies that provide blended features of u-learning and m-learning. In AR and VR, 3-D dynamic content could be created; students can experience and visualize the 3-D content using smart gadgets such as PDAs, mobile phones, desktops, etc. (Boonbrahm et al., 2016).

The pedagogies mentioned above are innovative in various educational domains such as primary, secondary, K-12, medical, industrial automation, and engineering (Hwang et al., 2016; Prit Kaur et al., 2018). All have their own merits and demerits, but AR has been proved as one of the promising technologies; it provides interactivity, immersion, and instant feedback features. It has also been proved to be a guiding tool for learners to perform different experiments and learn critically about complex real-time problems (Chang & Hwang, 2018). The principal merit of AR is that learners can perform any laboratory-related experiment at any time without spending any money on the costliest hardware equipment.

AR is a technology that overlays virtual objects with real-world objects. It constitutes three main characteristics: the fusion of the physical world and the virtual world, real-time interaction, and 3D registration (Azuma, 1997). Over the last few years, there has been increasing popularity in research interest of AR, as mobile devices such as smartphones and tablets have provided users with much simpler and cheaper access to AR than before. Positive effects of AR technology on student learning, critical thinking, learning motivation, learning experience and collaborative learning, etc. have also been reported in the previous studies (Akayır & Akayır, 2017; De Amicis et al., 2018). By considering all such benefits, an AR-based system has been developed for engineering students to learn and solve the complex problems related to the basic electronics and digital electronics course. Students in electronics engineering frequently design circuits and logic. Digital electronics is a key subject for electronics, electrical, and computer science engineers because it helps learners develop their logic-building abilities. Students were able to construct the logic and solve the K-map on their own while solving design challenges using the Karnaugh map (K-map), but they had difficulty identifying the optimal solution out of redundant pairs. Students require the assistance of teachers to validate the logic design because they lack the necessary skills. The following are the common mistakes that student do while applying K-maps:Wrong selection of redundant pairs, Creating wrong logic expressons based on redundant pairs, Unable to create correct AOI logic diagram. Hence, there is a need for a flexible (inside/outside the class) learning environment where students follow the K-map steps to get the correct logical solution. In this study, an AR-based learning environment was developed to address students' issues with K-map learning. Using an AR-based mobile application, students can learn the K-map method step-by-step and get instant feedback from the system at each stage of designing. Also, AOI logical diagrams for any Boolean expression can be developed by interacting with the application.

c80f0f1006