Karnaugh Maps for Software Engineering

August 19, 2022

After reading Part 1, check out the interactive tool for creating Karnaugh maps.

When you're building software, you may use multiple tools from your toolbox: prototypes, wireframes, design docs, user stories.

I'll suggest one more: the Karnaugh map.

These are typically used in electrical engineering, but can be useful for software too. They're great for reducing a complex problem into smaller parts.

I used to use these every time I would make a UX interaction, to make sure I didn't have any gaps in the experience. Eventually I built up some intuition so I didn't need them as much.

To use a Karnaugh map, you specify a set of boolean variables, fill out the map for every possible combination, and then group together common outputs.

In a scenario where a user is visiting a resource page, your variables might be something like:

• Does the resource exist?
• Is the resource private?
• Is the user logged in?
• Does the user have permission to view this?

Your outputs might be to show the resource, show a 404 page, or redirect the user.

By looking at the pattern of outputs, you can see if you have any potential larger security holes or if you need to rethink your permissions system.

The layout

The layout of a Karnaugh map does two things:

1. Creates a space for every possible combination of the boolean variables.
2. Makes it easy to group together outputs.

If you look at the top row, you'll see 00, 01, 11, 10. This ordering is called Gray Code, which means that only one variable changes between terms. For example, instead of going from 01 to 10, in which both bits would flip, going from 01 to 11 only flips the last bit. This lets us group cells that are next to each other.

For the sake of brevity, I won't go into every way to group a Karnaugh map, or cover how to draw them for each number of variables. This guide covers combining 4-variable maps.

How to use a Karnaugh map

Let's say we're building an art app where you can create digital paintings and then publish your work.

Define your variables

Here are the boolean variables we'll use for deciding what to show a user when they go to a link to a painting.

• Does the painting exist?
• Is the painting private?
• Does the user have permission to view this?
• Is the user logged in?

Draw your map

For 4-variable Karnaugh maps, copy this diagram and change your variables.

Fill in the outputs

You can fill in the outputs in any order you like. Using symbols or colours helps visually express your outputs.

Note that the bottom row has the text N/A. The **10 case doesn't exist because it's not possible to be logged out but have permissions, so we'll just mark these as not applicable.

Combine outputs

Once you have your outputs, you can combine them to simplify your boolean expressions.

Below are a few ways that outputs can be grouped. For 4-variable Karnaugh maps, you can have groups of 1, 2, 4, 8, or 16 outputs. Proximity dictates what cells can be grouped, and they can wrap around, like in the grouping of 1100 and 1110 below.

You'll notice that some grouping include the N/A cells. You can think of these as wildcard cells, meaning they can be included with any other terms. The official terms for these are "Don't care" cells.

You can read more about how grouping works here.

Using Karnaugh maps for detailed discussions

One of the biggest benefits of Karnaugh maps is they're a great visual for communicating complex concepts.

For example, let's look at this map and discuss the unique way that GitHub handles logged-out users for repository pages.

Take a look at cells 1100 and 1101 (the light blue redirect cell and the 404 below it).

For our example art app, we redirect the user to log in for private resources, if they're not logged in. If they are logged in but don't have permissions, we show a 404 page.

GitHub handles these cases slightly differently for their repositories. They'll show a 404 page in both cases.

Why does GitHub show a 404 instead of a redirect? For their use case, it's really important to not leak if a certain repo exists. For example, if I had a repo called marissamarym/twitter-clone, that might leak that I'm working on cloning Twitter.

Because of this privacy constraint, GitHub has to make sure that both 110* cases look the same, whether you're logged out or logged in, and just don't have permissions.

A powerful tool for simplification

Karnaugh maps are pretty powerful, but they shouldn't be the only tool you reach for to solve a problem. And because they can reduce complex problems, they might enable you to create more complexity.

My advice would be to always remember to keep the user experience as simple as possible. Does your app need private resources for the first version? If not, consider cutting that variable.

Just because you can code it doesn't mean you should. And it's very satisfying to cut your Karnaugh map in half.