CODEWITHSUNDEEP
javascriptboolean-expressionkarnaugh-map
Duy Duy
Duy Duy

Reputation: 621

implement a function to group cells when simplifying Boolean expression using K-map

In order to implement simplification of a 5-variable Boolean expression using Karnaugh map, I write a JavaScript function to group cells (which input is a list of integers specifying minterms):

function groupMinterms(minterms) {
  // Define the size of the 5-variable K-map (32 cells)
  const mapSize = 32;

  // Create an empty array to store groups
  const groups = [];

  // Validate input (check for valid minterms within K-map range)
  for (const minterm of minterms) {
    if (minterm < 0 || minterm >= mapSize) {
      throw new Error(`Invalid minterm: ${minterm}. Must be between 0 and ${mapSize - 1}`);
    }
  }

  // Create a helper function to check if two minterms can be grouped
  function canGroup(m1, m2) {
    const diff = m1 ^ m2; // XOR operation to find the difference between minterms
    return (diff & (diff + 1)) === 0; // Check if only one bit differs (power of 2)
  }

  // Loop through each minterm
  for (let i = 0; i < minterms.length; i++) {
    const minterm1 = minterms[i];
    let foundGroup = false;

    // Check for wrapping around groups
    for (let j = 0; j < groups.length; j++) {
      const firstMinterm = groups[j][0];
      const lastMinterm = groups[j][groups[j].length - 1];

      if ((canGroup(minterm1, firstMinterm) && (minterm1 + 1) % mapSize === firstMinterm) ||
          (canGroup(minterm1, lastMinterm) && (lastMinterm + 1) % mapSize === minterm1)) {
        groups[j].push(minterm1);
        foundGroup = true;
        break;
      }
    }

    // Check existing groups without wrapping
    if (!foundGroup) {
      for (let j = 0; j < groups.length; j++) {
        if (groups[j].some(m => canGroup(m, minterm1))) {
          groups[j].push(minterm1);
          foundGroup = true;
          break;
        }
      }
    }

    // If not added to an existing group, create a new group
    if (!foundGroup) {
      groups.push([minterm1]);
    }
  }

  return groups;
}

// Example usage with the corrected output
const minterms = [1, 2, 5, 7, 11, 19];
const groups = groupMinterms(minterms);

console.log("Minterms:", minterms);
console.log("Groups:", groups);

But when I run the code, which the minterms = [1, 2, 5, 7, 11, 19], I receive the output (groups of cells)

Groups: [ [ 1, 2, 5 ], [ 7 ], [ 11 ], [ 19 ] ]

which is not the same as the result I receive when using online tool, it should be

Groups: [[1, 5], [5, 7], [2], [11], [19]]

What is the thing which is not exact in my code? Thank in advanced

Upvotes: 0

Views: 51

Answers (1)

Axel Kemper
Axel Kemper

Reputation: 11322

Blocks in a K-map (Karnaugh Veitch map) always comprise 2, 4, 8, ... cells, an integer power of two cells. In a first step, two adajcent cells are merged to form a 2-cell block. This corresponds to a minterm with n-1 variables. One variable has vanished due to the merge.

Two 2-cell blocks different in one variable position are merged into one 4-cell block accordingly. And so on ...

Your group logic is flawed as it allows and produces groups with other cell numbers. Example is your group [1, 2, 5]. Cells 1 and 2 cannot be merged as they differ in two positions. Only 1 and 5 differ in just one position.

The solution you found online is correct. You can convince yourself here: enter image description here

Upvotes: 1

Related Questions