Formal verification is playing a significant role in IC design.However,the common models for verification either have their complexity problems or have applicable limitations.In order to overcome the deficiencies,a no...Formal verification is playing a significant role in IC design.However,the common models for verification either have their complexity problems or have applicable limitations.In order to overcome the deficiencies,a novel model-WGL(Weighted Generalized List)is proposed,which is based on the general-list decomposition of polynomials,with three different weights and manipulation rules introduced to effect node sharing and the canonicity.Timing parameters and operations on them are also considered.Examples show the word-level WGL is the only model to linearly represent the common word-level functions and the bit-level WGL is especially suitable for arithmetic intensive circuits.The model is proved to be a uniform and efficient model for both bit-level and word-level functions.Then based on the WGL model,a backward-construction verification approach is proposed,which reduces time and space complexity for multipliers to polynomial complexity(time complexity is less than O(n3.6)and space complexity is less than O(n1.5))without hierarchical partitioning.Both the model and the verification method show their theoretical and applicable significance in IC design.展开更多
基金Sponsored by the National Natural Science Foundation of China(Grant No.69973014and60273081)the Natural Science Foundation of Heilongjiang Province(Grant No.F0209)HEU Foundation(Grant No.HEUF04088).
文摘Formal verification is playing a significant role in IC design.However,the common models for verification either have their complexity problems or have applicable limitations.In order to overcome the deficiencies,a novel model-WGL(Weighted Generalized List)is proposed,which is based on the general-list decomposition of polynomials,with three different weights and manipulation rules introduced to effect node sharing and the canonicity.Timing parameters and operations on them are also considered.Examples show the word-level WGL is the only model to linearly represent the common word-level functions and the bit-level WGL is especially suitable for arithmetic intensive circuits.The model is proved to be a uniform and efficient model for both bit-level and word-level functions.Then based on the WGL model,a backward-construction verification approach is proposed,which reduces time and space complexity for multipliers to polynomial complexity(time complexity is less than O(n3.6)and space complexity is less than O(n1.5))without hierarchical partitioning.Both the model and the verification method show their theoretical and applicable significance in IC design.
