カルノー図から加法標準形のブール代数を出力するプログラムを作って、全加算器の論理演算を求めてみた

制作の動機

こちらの動画を見て、作ってみようと思い立った。

【初心者向け】カルノー図を徹底解説します。カルノー図 Part1【加法標準形】【論理回路】

動作

全加算器の入出力について

変数	意味	入/出力
A	A + B = S の A	入力
B	A + B = S の B	入力
S	A + B = S の S	出力
Cin	繰り上がってくる桁	入力
Cout	繰り上がる桁	出力

カルノー図

出力が2つあるので、カルノー図も以下の2つが必要。
Cin は C と短縮表記している。

S のカルノー図

       [BC]
       00 01 11 10
[A] 0   0  1  0  1
    1   1  0  1  0

Cout のカルノー図

       [BC]
       00 01 11 10
[A] 0   0  0  1  0
    1   0  1  1  1

プログラムの出力

S = A ^ B ^ C
Cout = BC + AC + AB

記号の意味

記号	意味
!X	NOT
XY	AND
X + Y	OR
X ^ B	XOR

ソースコード

C#。SharpLab に貼ればそのまま動く。
AI をフル活用して制作。

ソースコード全文

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

public static class Program
{
    private readonly record struct Group(
        int Mask,
        int Bits,
        HashSet<int> Covers);

    public static void Main()
    {
        // Full Adder - S
        //
        //       BCin
        //       00 01 11 10
        // A=0    0  1  0  1
        // A=1    1  0  1  0
        //
        int[,] sumMap =
        {
            { 0, 1, 0, 1 },
            { 1, 0, 1, 0 },
        };

        // Full Adder - Cout
        //
        //       BCin
        //       00 01 11 10
        // A=0    0  0  1  0
        // A=1    0  1  1  1
        //
        int[,] carryMap =
        {
            { 0, 0, 1, 0 },
            { 0, 1, 1, 1 },
        };

        Print("S", sumMap);
        Print("Cout", carryMap);
    }

    static void Print(string name, int[,] map)
    {
        var ones = FromKarnaugh(map);
        int variableCount = GetVariableCount(map);

        Console.WriteLine($"{name} = {Simplify(ones, variableCount)}");
    }

    static int GetVariableCount(int[,] map)
    {
        return BitOperations.Log2((uint)map.GetLength(0))
             + BitOperations.Log2((uint)map.GetLength(1));
    }

    static HashSet<int> FromKarnaugh(int[,] map)
    {
        int rowCount = map.GetLength(0);
        int colCount = map.GetLength(1);

        int rowBits = BitOperations.Log2((uint)rowCount);
        int colBits = BitOperations.Log2((uint)colCount);

        return FromKarnaugh(map, rowBits, colBits);
    }

    static HashSet<int> FromKarnaugh(
        int[,] map,
        int rowBits,
        int colBits)
    {
        int rowCount = 1 << rowBits;
        int colCount = 1 << colBits;

        if (map.GetLength(0) != rowCount ||
            map.GetLength(1) != colCount)
        {
            throw new ArgumentException();
        }

        var result = new HashSet<int>();

        for (int row = 0; row < rowCount; row++)
        {
            int rowGray = row ^ (row >> 1);

            for (int col = 0; col < colCount; col++)
            {
                if (map[row, col] == 0)
                    continue;

                int colGray = col ^ (col >> 1);

                int minterm =
                    (rowGray << colBits) |
                    colGray;

                result.Add(minterm);
            }
        }

        return result;
    }

    static string Simplify(HashSet<int> ones, int variableCount)
    {
        if (ones.Count == 0)
            return "0";

        if (ones.Count == (1 << variableCount))
            return "1";

        string? xorExpression =
            TryGetXorExpression(ones, variableCount);

        if (xorExpression != null)
            return xorExpression;

        var groups = FindGroups(ones, variableCount);

        groups = RemoveContainedGroups(groups);

        var best = FindMinimumCover(groups, ones);

        return string.Join(" + ",
            best.Select(g => GroupToExpression(g, variableCount)));
    }

    static string? TryGetXorExpression(
        HashSet<int> ones,
        int variableCount)
    {
        int total = 1 << variableCount;

        bool isXor = true;
        bool isXnor = true;

        for (int i = 0; i < total; i++)
        {
            bool odd =
                (BitOperations.PopCount((uint)i) & 1) != 0;

            bool actual =
                ones.Contains(i);

            if (actual != odd)
                isXor = false;

            if (actual == odd)
                isXnor = false;
        }

        string xorText = string.Join(" ^ ",
            Enumerable.Range(0, variableCount)
                .Select(i => ((char)('A' + i)).ToString()));

        if (isXor)
            return xorText;

        if (isXnor)
            return $"!({xorText})";

        return null;
    }

    static List<Group> FindGroups(
        HashSet<int> ones,
        int variableCount)
    {
        int totalMasks = 1 << variableCount;
        var result = new List<Group>();

        for (int mask = 0; mask < totalMasks; mask++)
        {
            for (int bits = 0; bits < totalMasks; bits++)
            {
                if ((bits & ~mask) != 0)
                    continue;

                var covers = new HashSet<int>();

                for (int minterm = 0; minterm < totalMasks; minterm++)
                {
                    if ((minterm & mask) == bits)
                        covers.Add(minterm);
                }

                bool allOne = true;

                foreach (var cover in covers)
                {
                    if (!ones.Contains(cover))
                    {
                        allOne = false;
                        break;
                    }
                }

                if (allOne)
                    result.Add(new Group(mask, bits, covers));
            }
        }

        return result;
    }

    static List<Group> RemoveContainedGroups(List<Group> groups)
    {
        var alive = Enumerable.Repeat(true, groups.Count).ToArray();

        for (int i = 0; i < groups.Count; i++)
        {
            for (int j = 0; j < groups.Count; j++)
            {
                if (i == j)
                    continue;

                if (groups[i].Covers.Count >= groups[j].Covers.Count)
                    continue;

                if (groups[i].Covers.IsSubsetOf(groups[j].Covers))
                {
                    alive[i] = false;
                    break;
                }
            }
        }

        var result = new List<Group>();

        for (int i = 0; i < groups.Count; i++)
        {
            if (alive[i])
                result.Add(groups[i]);
        }

        return result;
    }

    static List<Group> FindMinimumCover(
        List<Group> groups,
        HashSet<int> ones)
    {
        List<Group>? best = null;

        void DFS(
            int index,
            List<Group> selected,
            HashSet<int> covered)
        {
            if (best != null && selected.Count > best.Count)
                return;

            bool complete = true;

            foreach (var one in ones)
            {
                if (!covered.Contains(one))
                {
                    complete = false;
                    break;
                }
            }

            if (complete)
            {
                if (best == null ||
                    selected.Count < best.Count ||
                    selected.Count == best.Count &&
                    selected.Sum(GetLiteralCount) < best.Sum(GetLiteralCount))
                {
                    best = selected.ToList();
                }

                return;
            }

            if (index >= groups.Count)
                return;

            DFS(index + 1, selected, covered);

            selected.Add(groups[index]);

            var nextCovered = new HashSet<int>(covered);
            nextCovered.UnionWith(groups[index].Covers);

            DFS(index + 1, selected, nextCovered);

            selected.RemoveAt(selected.Count - 1);
        }

        DFS(0, new List<Group>(), new HashSet<int>());

        return best!;
    }

    static int GetLiteralCount(Group group)
    {
        return BitOperations.PopCount((uint)group.Mask);
    }

    static string GroupToExpression(
        Group group,
        int variableCount)
    {
        var terms = new List<string>();

        for (int i = variableCount - 1; i >= 0; i--)
        {
            int bit = 1 << i;

            if ((group.Mask & bit) == 0)
                continue;

            char variable =
                (char)('A' + (variableCount - 1 - i));

            bool isOne =
                (group.Bits & bit) != 0;

            terms.Add(isOne
                ? variable.ToString()
                : $"!{variable}");
        }

        return terms.Count == 0
            ? "1"
            : string.Join("", terms);
    }
}

大体の処理の流れ

YouTube 動画で解説されている通り。
1を含むなるべく大きいサイズの長方形を算出するところがコアロジック。
後は、見た目を整えたり、入力値を解釈したりする、マーシャリング部。

追記：マイクラでも作ってみた

1bit の全加算器。
32個繋げれば、一般的な整数型の加算が出来そう。