Automating the modeling and optimization of the performance ofsignal transforms

Fast implementations of discrete signal transforms, such as the discrete Fourier transform (DFT), the Walsh-Hadamard transform (WHT), and the discrete trigonometric transforms (DTTs), can be viewed as factorizations of their corresponding transformation matrices. A given signal transform can have many different factorizations, with each factorization represented by a unique but mathematically equivalent formula. When implemented in code, these formulas can have significantly different running times on the same processor, sometimes differing by an order of magnitude. Further, the optimal implementations on various processors are often different. Given this complexity, a crucial problem is automating the modeling and optimization of the performance of signal transform implementations. To enable computer modeling of signal processing performance, we have developed and analyzed more than 15 feature sets to describe formulas representing specific transforms. Using some of these features and a limited set of training data, we have successfully trained neural networks to learn to accurately predict performance of formulas with error rates less than 5%. In the direction of optimization, we have developed a new stochastic evolutionary algorithm known as STEER that finds fast implementations of a variety of signal transforms. STEER is able to optimize completely new transforms specified by a user. We present results that show that STEER can find discrete cosine transform formulas that are 10-20% faster than what a dynamic programming search finds     

广义可能性计算树逻辑的模型检测问题

本文首先分别给出了"约束可达","总是可达"这两个公式在广义可能性计算树逻辑（GPoCTL）中的另外两种等价形式;其次讨论了基于广义可能性测度的计算树逻辑的模型检测问题,将GPoCTL的模型检测问题规约为经典的CTL模型检测问题,利用截集的方法,给出了计算GPoCTL的模型检测问题的算法及其复杂度,并通过实例分析说明了这种算法的可行性;最后,研究了具有公平性假设的GPoCTL模型检测问题的计算复杂度,得到了与上面相似的结论.     

基于扩展层次自动机的UML状态图完备性和一致性检验

UML状态图是UML中重要的建模元素之一,用以描述软件系统的离散行为。完备性和一致性是UML状态图模型最重要的性质之一,是进一步验证模型行为正确性的前提。给出了状态图模型完备性和一致性的定义,研究了对完备性和一致性进行检验的方法。该方法首先把状态图模型变换成扩展层次自动机(EHA),然后对EHA进行分析。EHA中间格式消除了状态图的复杂性,简化了冲突迁移的优先级判别,便于设计简捷有效的算法对完备性和一致性进行检验。该方法的主要优点是利用了EHA的特性,给出了组合状态上迁移的传播算法,解决了完备性和一致性分析的难点。     

Properties and relations for fast linearly independent arithmetic transforms

New fast linearly independent arithmetic (LIA) transforms are introduced here which can be used to represent any functions of binary variables. The transforms are grouped into classes where consistent formulas relating forward and inverse transform matrices are obtained. All the presented transforms have the same computational cost, which is lower than the computational cost of the well-known fixed polarity arithmetic transforms. General classifications and fast forward and inverse transform definitions for all the fast LIA transforms are given. Various properties and mutual relations that exist for the different transforms and their corresponding spectra are also shown. The presented relations and properties reduce the computational cost of finding the best LIA polynomial expansion based on the new transforms.     

Linear boundary extensions for finite length signals and paraunitary two-channel filterbanks

In this paper, we introduce a novel and general matrix formulation of artificial linear boundary extension methods for removing border effects inherent to any paraunitary two-channel size-limited filterbank. This new characterization of the transformation operator allows us to prove that perfect reconstruction (PR) of finite signals can be ensured under some conditions without using extra subband coefficients; in other words, we characterize the signal extension methods that lead to nonexpansive transforms. The necessary and sufficient condition we find allows us to show that some traditional extension techniques that are being used in an expansive way, such as the polynomial extension, lead in fact to nonexpansive invertible transforms; moreover, we can also prove that in contradiction to previous literature, not every transformation matrix associated with a linear extension is invertible even if using prototype filters of the same length. Apart from these invertibility criteria, we propose the first algorithm for the design of all linear extensions and their associated biorthogonal boundary filters that lead to nonexpansive and invertible transforms. Analogously, we provide the first method for the design of all linear extensions that yield orthogonal transforms: We construct an infinite number of orthogonal extensions, apart from the commonly used periodic extension, and their associated orthogonal boundary filters. The final contribution of the paper is a new algorithm for the design of smooth orthogonal extensions, which keep the orthogonality property and overcome the main drawback of periodization, that is, the introduction of subband coefficients of great amplitude near the boundaries in the transform domain.     

Diffraction tomographic algorithm for the detection ofthree-dimensional objects buried in a lossy half-space

A diffraction tomographic (DT) algorithm has been proposed for detecting three-dimensional (3-D) dielectric objects buried in a lossy ground, using electric dipoles or magnetic dipoles as transmitter and receiver, where the air-earth interface has been taken into account and the background is lossy. To derive closed-form reconstruction formulas, an approximate generalized Fourier transform is introduced. Using this algorithm, the locations, shapes, and dielectric properties of buried objects can be well reconstructed under the low-contrast condition, and the objects can be well detected even when the contrast is high. Due to the use of fast Fourier transforms to implement the problem, the proposed algorithm is fast and quite tolerant to the error of measurement data, making it possible to solve realistic problems. Reconstruction examples are given to show the validity of the algorithm     

Sur Ľemploi de la transformation de Fourier pour Ľénumération de poids des codes linéaires en bloc

The problem of computing the weight distribution of a linear block code is addressed in this paper through the use of the Fourier transforms of indicator functions of parts of a set. After deriving the necessary mathematical formalism, we show that it enables to simply prove again certain known formulas (concerning for instance the Krawtchouk polynomials) and besides to derive two results we believe to be new. First, a recursion formula on polynomials enables direct computation of the weight enumerator of the code in terms of its parity-check matrix. Second, since this formula leads in any case to cumbersome calculations, we derive analytical formulas concerning average weight estimates, together with an estimate of their precision.     

科技项目申请书关键词提取方法

关键词提取在文本相似度计算得到应用。传统的关键词提取方法忽略文本中的未登录词以及缺乏对词语语义的理解。针对科技项目申请书,研究提出一种基于未登录词识别与语义的关键词提取方法。应用Lucene和统计相融合的方法进行分词,并识别未登录词作为申请书关键词的一部分;依据社会网络理论构建词语语义相似度网络,并计算词语关联度提取申请书其他关键词。实验结果表明,与传统的关键词提取方法相比,新方法能提取更准确的关键词,有更好的科技项目相似性检查效果。     

A family of lapped regular transforms with integer coefficients

Invertible transforms with integer coefficients are highly desirable because of their fast, efficient, VLSI-suitable implementations and their lossless coding capability. In this paper, a large class of lapped regular transforms with integer coefficients (ILT) is presented. Regularity constraints are also taken into account to provide smoother reconstructed signals. In other words, this ILT family can be considered to be an M-band biorthogonal wavelet with integer coefficients. The ILT also possesses a fast and efficient lattice that structurally enforces both linear-phase and exact reconstruction properties. Preliminary image coding experiments show that the ILT yields comparable objective and subjective performance to those of popular state-of-the-art transforms with floating-point coefficients     

基于微分算子的Eno-haar小波变换及其应用

该文首先引入微分算子并结合Haar小波的特点,提出了一种遗传性算法,用于2D信号奇异性检测。其次,将该算法与Eno-haar(Essentially non-oscillatory-haar)小波相结合,得到了一种基于微分算子的Eno-haar小波变换算法,并通过仿真实验说明了其在图像压缩中的可行性和有效性。