Indirect test of M-S circuits using multiple specification band guarding

Testing analog and mixed-signal circuits is a costly task due to the required test time targets and high end technical resources. Indirect testing methods partially address these issues providing an efficient solution using easy to measure CUT information that correlates with circuit performances. In this work, a multiple specification band guarding technique is proposed as a method to achieve a test target of misclassified circuits. The acceptance/rejection test regions are encoded using octrees in the measurement space, where the band guarding factors precisely tune the test decision boundary according to the required test yield targets. The generated octree data structure serves to cluster the forthcoming circuits in the production testing phase by solely relying on indirect measurements. The combined use of octree based encoding and multiple specification band guarding makes the testing procedure fast, efficient and highly tunable. The proposed band guarding methodology has been applied to test a band-pass Butterworth filter under parametric variations. Promising simulation results are reported showing remarkable improvements when the multiple specification band guarding criterion is used.     

分散图象压缩的遗传算法

基于分形和PIFS函数的特点，提出一种改进的遗传算法用于分形压缩分块的定义域匹配搜索算法。该方法克服了原来分形图象压缩中分类匹配算法固有的局部最优性和随机搜索的缺点，是一种具导引的全局优化的搜索算法。分析和实验表明，该方法的图象压缩比高，解码质量好，若应用遗传算法的并行性，其编码速度也得到提高。     

用四叉树算法建立自主系统环境模型

对环境建模是自主系统路径规划的基础,针对传统方法中存在的种种缺陷,该文在阐述自主系统中利用激光测距成像雷达的坐标变换法所获取的距离图实时检测障碍物的基础上,利用二值图像的四叉树表示是基于数据区域的一致性判别准则和空间递归分解原理建立起来的一种分层的树形数据结构,将一幅二值图像分为大小相同的四个分区,着重研究了利用模式四叉树建立部分已知或完全未知的环境模型的方法,结果显示其节省了四叉树占用的存储空间,在相同的存储空间情况下,提高了环境分辨率,加快了系统的运行速度,并给出了环境信息的优化策略。     

Image compression for fast wavelet-based subregion retrieval

In an image browsing environment there is need for progressively viewing image subregions at various resolutions. We describe a storage scheme that accomplishes good image compression, while supporting fast image subregion retrieval. We evaluate analytically and experimentally the compression performance of our algorithm. We also provide results on the speed of the algorithm to demonstrate its effectiveness, and present an extension to a client/server environment.     

A comparison of the space requirements of multi-dimensional quadtree-based file structures

A comparison is made of the space requirements of pointer and a number of pointer-less implementations of multidimensional quadtree-based file structures. The database is assumed to be static. In order to make the comparison realistic, considerations such as computer byte sizes are taken into account, and fields are constrained to start on bit and byte boundaries where appropriate. In many practical cases, the pointer quadtree requires less space than the pointer-less quadtree. This effect is more pronounced for octrees and data of higher dimension. Empirical data from a cartographic batabase are used to support the analysis.The support of the National Science Foundation under Grant IRI8802457 is gratefully acknowledged     

Analytic variations on quadtrees

Quadtrees constitute a hierarchical data structure which permits fast access to multidimensional data. This paper presents the analysis of the expected cost of various types of searches in quadtrees — fully specified and partial-match queries. The data model assumes random points with independently drawn coordinate values.The analysis leads to a class of full-history divide-and-conquer recurrences. These recurrences are solved using generating functions, either exactly for dimensiond=2, or asymptotically for higher dimensions. The exact solutions involve hypergeometric functions. The general asymptotic solutions rely on the classification of singularities of linear differential equations with analytic coefficients, and on singularity analysis techniques.These methods are applicable to the asymptotic solution of a wide range of linear recurrences, as may occur in particular in the analysis of multidimensional searching problems.The work of Philippe Flajolet was supported in part by the Basic Research Action of the E.C. under Contract No. 3075 (Project ALCOM). A preliminary version of this paper has been presented in the form of an extended abstract at the Second Annual Symposium on Discrete Algorithms [13].     

Partial match queries in relaxed multidimensional search trees

Partial match queries arise frequently in the context of large databases, where each record contains a distinct multidimensional key, that is, the key of each record is aK-tuple of values. The components of a key are called thecoordinates orattributes of the key. In a partial match query we specify the value ofs attributes, 0<s<K, and leave the remainingK —s attributes unspecified. The goal is to retrieve all the records in the database that match the specified attributes. In this paper we present several results about the average performance and variance of partial matches in relaxedK-dimensional trees (search trees and digital tries). These data structures are variants of the well knownK d-trees andK d-tries. In relaxed trees the sequence of attributes used to guide a query is explicitly stored at the nodes of the tree and randomly generated and, in general, will be different for different search paths. In the standard variants, the sequence of attributes that guides a query examines the attributes in a cyclic fashion, fixed and identical for all search paths. We show that the probabilistic analysis of the relaxed multidimensional trees is very similar to that of standardK d-trees andK d-tries, and also to the analysis of quadtrees. In fact, besides the average cost and variance of partial match in relaxedK d-trees andK d-tries, we also obtain the variance of partial matches in two-dimensional quadtrees. We also compute the average cost of partial matches in other relaxed multidimensional digital tries, namely, relaxedK d-Patricia and relaxedK d-digital search trees. This research was supported by Acciones Integradas Hispano-Austríacas HU1997-0016 (Austrian-Spanish Scientific Exchange Program). The first author was also supported by ESPRIT LTR 20244 (ALCOM IT), CICYT TIC97-1475-CE, DGES PB95-0787 (KOALA), and CIRIT 1997SGR-00366 (SGR). The second author was also supported by the Austrian Research Society (FWF) under Project P12599-MAT. Online publication October 13, 2000.     

Well-separated pair decomposition in linear time?

Given a point set in a fixed dimension, we note that a well-separated pair decomposition can be found in linear time if we assume that the ratio of the farthest pair distance to the closest pair distance is polynomially bounded. Many consequences follow; for example, we can construct spanners or solve the all-nearest-neighbors problem in linear time (under the same assumption), and we compute an approximate Euclidean minimum spanning tree in linear time (without any assumption).     

A geographic information system using quadtrees

We describe the current status of an ongoing research effort to develop a geographic information system based on quadtrees. Quadtree encodings were constructed for area, point and line features for a small area in Northern California. The encoding used was a variant of the linear quadtree. The implementation used a B-tree to organize the list of leaves and allow management of trees too large to fit in core memory. Several database query functions have been implemented, including set operations, region property computations, map editing functions and map subset and windowing functions. A user of the system may access the database via an English-like query language.     

Linear-time border-tracing algorithms for quadtrees

In applications where the quadtree is used as an underlying object representation, a number of basic operations are implemented as a trace along the border of the object's region. A technique is presented that determines a way to shift any given scene (as well as its quadtree), so that the border of all the objects in the scene can be traversed in time proportional to the length of all the borders in the scene (or the number of blocks when the scene is represented as a quadtree). This determination is shown to be performed in time proportional to the length of all the borders in the scene. This allows the direct translation of a number of chain-code algorithms into quadtree algorithms without loss of asymptotic worst-case efficiency. This results in improved worst-case analyses of algorithms that convert chain codes into quadtrees and that perform connected component labeling of images represented as quadtrees.The support of the National Science Foundation under Grant IRI-88-02457 is gratefully acknowledged.