对PLA二级分解技术中输入变量划分的最小切割法的研究

A Study on Min-cut Algorithm of input Variation Partition for PLA Two-stage Decomposition

要把一个给定ＰＬＡ分解成二级串级的ＰＬＡ电路，使该ＰＬＡ电路的总面积较原给定ＰＬＡ的面积为小，这就是所谓ＰＬＡ二级分解技术．在这个技术中首先要解决输入变量的划分问题，本文对以图论为基础的输入变量划分的最小切割法进行分析，并用Ｃ语言对该算法进行程序实现，然后通过实验对算法中的两个关键系数α、β的值作了估计．

The PLA two-stage decomposition technology is to decompose a primitive PLA into two-stage PLA and to minimize the area of primitive PLA. The input variation partition must be solved first in this technique.The paper analyzes the min-cut algorthin of input variation which is based on graphic theory and implements this algorthm using C language and then estimates two key values a and βby experiments.