在数字信号处理领域,傅立叶变换是一种有效分析工具。类似的,在数字逻辑设计领域,谱变换也是一种有效的分析工具。谱变换在逻辑设计上的广泛应用已有40多年的历史。作为一种抽象谐波分析方法,谱变换使数字逻辑设计的研究从逻辑域转化到谱域。因此很多在逻辑域中难以解决或者不能解决的问题在谱域中变得更加简单。 谱变换有两种编码方式,即(1,-1)编码和(0,1)编码。由于谱系数的含义更加明确,因此谱变换的研究主要集中于(1,-1)编码中,而对(0,1)编码却鲜有研究。本文将研究(0,1)编码谱变换。 传统的研究从数字信号处理领域出发,认为逻辑设计中的谱变换矩阵也必须是正交矩阵。我们认为,从信息完整的角度考虑,可以将这个条件放宽到可逆矩阵。在此基础上,我们认为谱系数可以通过构造可逆矩阵来“定制”。 以应用为导向的谱系数的主要缺陷是其计算的复杂性。近年来出现的决策图(Decision Diagram)方法改变了这种情况。通过“共享”部分图,使计算复杂性达到了多项式级。因此,该方法成为近年来算法研究的主流。对于计算整个谱的情况,决策图方法具有不可取代的优越性。但对于只需要计算单个或者部分谱系数的情况,本文根据(0,1)编码的特点,提出了一种针对变换矩阵列向量的算法。该方法具有非常简单的原理。 谱变换在逻辑设计中的应用领域包括逻辑分析、综合、测试等。本文根据(0,1)编码谱系数的性质,系统地研究了这三方面的内容。 本文研究的谱变换方法是Walsh变换、Haar变换、Reed-Muller变换、Arithmetic变换,主要研究Walsh变换。