[發明專利]基于粒計算的時序邏輯電路狀態化簡方法

有效

• 申請號: 201711355995.3
• 申請日: 2017-12-16
• 公開（公告）號: CN108170911B
• 公開（公告）日: 2020-06-02
• 發明（設計）人: 陳澤華;李偉;柴晶;趙哲峰;尚奧;劉帆
• 申請（專利權）人: 太原理工大學
• 主分類號: G06F30/3312
• 分類號: G06F30/3312;G06F30/337
• 代理公司: 太原晉科知識產權代理事務所(特殊普通合伙) 14110
• 代理人: 任林芳

本發明公開了一種基于粒計算的時序邏輯電路狀態化簡方法，該方法定義了描述狀態轉移情況的次態矩陣，并通過對相容類的標記不斷更新次態標記矩陣，從而求得最大相容類集合，這樣避免了大規模稀疏矩陣的產生；在求解最大相容類的過程中，直接對狀態轉移表中的全體初始狀態進行劃分，通過迭代即可得到最終結果，避免了其它算法中對初始狀態兩兩求相容對和不相容對的過程，減少時間開支；利用核相容類作為啟發式信息構建初始狀態樹，可以較快求得所有可能的最小覆蓋；通過構建最小狀態樹可以對所有最小覆蓋的閉合性進行驗證并能得到狀態最少的化簡結果，保證了算法結果的最優性。

技術領域

本發明涉及電路化簡領域，尤其涉及一種基于粒計算的時序邏輯電路狀態化簡方法。

背景技術

時序邏輯電路的優良設計主要取決于根據問題建立的狀態轉移表(圖)的精確性和簡潔性。精確性指的是嚴格按照具體問題，將輸入、輸出和電路的狀態變化轉移情況用圖表的方式表達；簡潔性指的是盡量消去表中冗余的狀態，因為狀態數目越少，記憶電路越簡單，系統可靠性越高。

狀態化簡就是消除原始狀態轉移圖中的冗余狀態，得到最小化狀態轉移表的過程。根據輸出和次態是否有不確定值，可將時序電路分為完全確定時序電路和非完全確定時序電路。完全確定時序電路指的是狀態轉移表中的輸出和次態都是確定的情況，此種類型電路狀態化簡算法目前比較成熟；非完全確定時序電路指的是狀態轉移表中輸出和次態有不確定的情況，輸出不確定指的是0或1均有可能，次態不確定指的是給定某個輸入時下一個狀態不確定，即轉移到任意狀態都有可能。

化簡非完全確定時序電路時，不確定的輸出和次態可被多次使用，同一個狀態可能出現在不同相容類中，因此非完全確定時序電路的化簡要相對復雜些。常用方法有隱含表法、劃分法，以及一些啟發式算法等。張賢達利用化簡之后的最大相容類隱含圖，運用阱點的遞歸選擇及回路分解，得到最小閉覆蓋，該方法為求取最小閉覆蓋的圖解法，在求取最大相容類的過程中，本質上用到的仍然是傳統的隱含表法，需要從狀態轉移表中找到所有相容狀態對、不相容狀態對和隱含相容狀態對，在分解回路求最小閉覆蓋過程中，往往不能一次成功，需要經過多次實驗，導致算法復雜度很大；同時有人提出了一種不完全確定時序機的快速算法，該算法先確定一個覆蓋了全部狀態而包含相容類數不多的“候選集”，通過不斷修改這個“候選集”，使最小閉覆蓋的成員逐漸引入該“候選集”，從而得到所求結果。但該算法不能保證得到的結果一定是最小閉覆蓋，而往往是一個接近最小閉覆蓋的準最小閉覆蓋，造成結果的準確性不夠，另外，該算法不夠形式化，不便于編程實現；Higuchi,H.和Matsunaga,Y.提出了一種改進的迭代算法，其中使用二元決策圖避免組合爆炸問題；Goren,S.等提出了一種啟發式的狀態化簡算法，該算法基于分支定界搜索技術和識別技術，提高了約簡效率，通過先找到狀態轉移表的上界和下界，然后采用搜索算法，逐步構建出符合要求的結果，但在定界和搜索過程中，需要遞增地構建輸入/輸出序列，且不斷引入額外狀態進行識別，使原狀態表規模增大，增加了存儲開銷。

發明內容

本發明的目的在于避免現有技術的不足之處而提供一種基于粒計算的時序邏輯電路狀態化簡方法。