C++ 實現 Quine-McCluskey (QM) 算法最小化邏輯函數

QM 算法核心思想

卡諾圖手工優化難以自動化。QM 算法 (表格法) 系統化步驟：

1. 分組：按二進制中 1 的個數分組。
2. 合併：相鄰組間僅 1 位不同的項合併，該位變「-」(消去)，生成主蘊涵項。
3. 迭代：重複合併直到無法再合併，收集所有**主蘊涵項**。
4. 覆蓋表：建立主蘊涵項 × 最小項矩陣。
5. 質蘊涵項：覆蓋唯一最小項的主項 → 必選。
6. 最小覆蓋：從剩餘主項中選最少數量覆蓋所有未覆蓋最小項 (NP-hard，常用啟發式/回溯)。

關鍵數據結構設計

struct Implicant { // 蘊涵項節點
    int bits;      // 0/1 位模式 (int 存儲，支援 ≤32 變量)
    int mask;      // 1 表示該位被消去 ("-")
    bool used = false; // 是否被合併覆蓋
    Implicant* next;
    int countOnes() const { return __builtin_popcount(bits); }
};

核心流程代碼骨架

1. 讀入最小項 → 初始分組鏈表陣列

vector groups(maxVar+1, nullptr);
for (int minterm : minterms) {
    auto* node = new Implicant{minterm, 0, false, nullptr};
    int g = node->countOnes();
    node->next = groups[g];
    groups[g] = node;
}

2. 迭代合併 (Union 函數)

void mergeGroups(vector& groups, vector& primeList) {
    for (int pass = 0; pass < maxVar; ++pass) {
        vector newGroups(maxVar+1, nullptr);
        bool anyMerged = false;
        for (int g = 0; g < maxVar; ++g) {
            for (auto* p = groups[g]; p; p = p->next) {
                for (auto* q = groups[g+1]; q; q = q->next) {
                    int diff = p->bits ^ q->bits;
                    if (__builtin_popcount(diff) == 1) { // 僅 1 位不同
                        int newMask = p->mask | diff;
                        int newBits = p->bits & ~diff; // 消去位歸 0
                        // 去重插入 newGroups[g]
                        if (!exists(newGroups[g], newBits, newMask)) {
                            auto* np = new Implicant{newBits, newMask, false, newGroups[g]};
                            newGroups[g] = np;
                        }
                        p->used = q->used = true;
                        anyMerged = true;
                    }
                }
            }
        }
        // 未被合併的項 → 主蘊涵項
        for (auto& gList : groups)
            for (auto* p = gList; p; p = p->next)
                if (!p->used) primeList.push_back(p);
        if (!anyMerged) break;
        groups = move(newGroups);
    }
}

3. 建立覆蓋矩陣 & 深度優先搜尋最小覆蓋

// matrix[primeIdx][mintermIdx] = 1/0
// 先標記質蘊涵項 (必選)
vector essential = findEssential(matrix);
// DFS 回溯選擇剩餘主項
void dfs(int idx, int selectedCount, vector& curSel, vector& bestSel) {
    if (selectedCount >= bestSel.size()) return; // 剪枝
    if (allCovered(curSel)) { bestSel = curSel; return; }
    if (idx == primeCount) return;
    // 選擇當前項
    curSel.push_back(idx); updateCoverage(idx, +1);
    dfs(idx+1, selectedCount+1, curSel, bestSel);
    // 不選
    updateCoverage(idx, -1); curSel.pop_back();
    dfs(idx+1, selectedCount, curSel, bestSel);
}

工程優化要點

• 去重：合併生成新項時，用 unordered_set<uint64_t> (bits<<32 | mask) O(1) 判重。
• 優先隊列：按 1 的個數分組可用 vector<vector<Implicant*>> 替代鏈表，緩存友好。
• Petrick 方法：最小覆蓋可轉為邏輯乘積和形式求解，比 DFS 更系統化。
• 記憶體管理：統一用 vector<unique_ptr<Implicant>> 托管所有節點，避免洩漏。

總結

QM 算法是邏輯綜合、編譯器優化、數字電路設計的基石。C++ 實現關鍵在於位運算高效表示蘊涵項、分組合併去重、覆蓋矩陣建模與最小覆蓋搜尋。掌握此算法有助於理解現代綜合工具 (如 ABC, Yosys) 內核邏輯。