一種有效簡化單極性雷穆勒展開式的方法

Abstract

雷穆勒形式是一種函數僅使用及閘和排斥或閘來制作的電路形態。這種形態的電路擁 有容易測試的優點，而且當輸入變數只以固定極性或稱為單極性的形式顯現，則只需 要固定之數目及式樣的測試樣本，既可偵測出電路中所有的固結故障，且這測試樣本 的產生與電路的函數無關。雷穆勒形式的電路雖有容易測試的優點，然而它比傳統的 設計方式（例如積項之和的形式）耗費較多的硬體。因此，有許多簡化雷穆勒形式之 電路的方法相繼被提出。可是這些方法大都採用窮舉方式以求得最佳解，以致於應用 上有些缺點，例如，浪費時間、不適用於大輸入變數的函數。為了解決窮舉方式的缺 點以擴展雷穆勒展開式的適用性，吾人提出一種有效且快速地簡化固定極性雷穆勒展 開式的方法。這個方法可直接操作於以串列形式顯現的函數，而不須預先轉換函數的 形式。最主要的是，這個方法能有效處理：（１）大輸入入變數的函數（２）單一或 多重輸出的函數（３）函數的項中含有未定的輸入變數。至於這方法的作法，則可分 為三大步驟。假設輸入函數是積項之和的形式。步驟（１）：分離項目，以使得函數 的或閘運算能被轉變成排斥或閘運算。步驟（２）：串列轉換，根據輸入變數的權數 以決定輸入變數的極性，然後根據此一決定的極性，將函數轉換成固定極性雷穆勒展 開式的電路。步驟（３）：極性轉換，藉由變換輸入變數的極性，嘗試改良步驟二的 結果。經由實驗結果的驗證，這個方法能有效地處理前述三類函數。此外，為了觀察 實驗結果之優劣，窮舉方式亦被執行以作為比較之用。結果，這方法所須的時間比窮 舉方式縮短甚多，而且大部分的例子都能簡化成最佳結果。