More efficient algorithms for symbolic network analysis: supernodes and reduced loop analysis

In this paper, two efficient approaches will be discussed that support linear network analysis: supernode analysis (SNA) and reduced loop analysis (RLA). By means of some selected example networks, these methods will be demonstrated and, thus, it will be shown that calculations can be dramatically simplified. In this way, all network situations can be handled. There are obvious advantages to SNA as it combines the MNA and the straightforward manual processing of the network. A very efficient solution strategy is obtained without source shifting and other common, less directed methods being used. SNA/RLA and symbolic algebra fit extremely well together. Thus an algorithm that supports the symbolic calculation of networks by means of supernodes which has been conceptualized and implemented in the analog design expert system EASY will be presented in detail. Above the educational aspect, it should be noted that the computer can now take a systematic approach to MNA and network analysis in general.1. There exist some extreme situations in which these additional equations are needed to express controlling currents.2. Generalized cut-sets are not necessarily minimal cut-sets [2]. This means that the removal of a generalized cut-set may split the network graph into more than only two components.3. Remark: This notation means that the current is in the frequency domain, commonly known as a phasor.4. This intuitive explanation will be confirmed in Section 7.5. These compactions are exactly the same as those applied by the CMNA implemented in ISAAC [7, 8, 11]. In fact, the CMNA is isomorphic to the SNA.6. Not subject of this paper.It's funny how many of the best ideas are just an old idea back-to-front. Douglas Adams     

Spline-based behavioural model for efficient analysis of large front-ends for W-CDMA systems

A new behavioural model suitable for the analysis of RF front-ends for W-CDMA systems is described. The model fully accounts for both linear and nonlinear dispersion effects, so that relatively by a band digitally modulated signals can be accurately dealt with. The linear front-end response is computed by means of the conversion admittance matrix. The relationship between the linear and nonlinear responses is characterised by a voltage and frequency-dependent describing function. The latter is evaluated by a cubic-spline-based two-dimensional interpolation scheme starting from a database generated by harmonic-balance analysis. In this way, front-end simulations that would require months of CPU time even by modern envelope-oriented techniques, can be performed in a matter of seconds without significant loss of accuracy.     

An improved algorithm for symbolic reliability analysis

The authors describe an efficient Boolean algebraic algorithm to compute the probability of a union of nondisjoint sets as applied to symbolic reliability analysis. Coherent networks and fault-trees with statistically-independent components characterized by their minimal pathsets or cutsets are used as examples for generating the nondisjoint sets. The algorithm uses the concept of multiple variable inversion originally proposed by A. Grnarov et al. (1979). The authors illustrate improvements in the use of the multiple variable inversion technique for this problem using two examples. The algorithm is extended to compute the reliability importance of a given component (sensitivity of system reliability to the component reliability). A computer program implementing the modified algorithm is used to solve and obtain measured time complexities for a large set of network and fault tree models     

An improved method for symbolic reliability analysis

This paper describes a method for finding the terminal-pair reliability expression of communication networks. This method incorporates bit manipulation and Boolean operations for generating a sum of disjoint products (SDP) expression in which each term has 1:1 correspondence with respective minimal path (or cut). This method is convenient and efficient. An example of the method is given.     

A hierarchical approach to large circuit symbolic simulation

This paper presents a new approach to symbolic analysis of large circuits. The proposed procedure is grounded on circuit decomposition by node tearing, symbolic analysis at subcircuit level and circuit function generation. Symbolic analysis is based on matrix-determinant method implemented within our original symbolic simulator. The crucial part of this procedure is circuit function generation. Opposed to classic symbolic simulation that gives final result in canonical sum-of-product form, hierarchical approach results in compact nested form. Proposed method is described in details using a simple example. The comparison with two other similar techniques is given using a benchmark example. The overall time reduction in comparison with the circuit function extraction in fully expanded form is 30 times.     

Formula approximation for flat and hierarchical symbolic analysis

This paper addresses the topic of reducing the complexity of formulae resulting from the symbolic analysis of analog integrated circuits, covering both flat and hierarchical symbolic analysis approaches. Previously reported criteria for flat analysis are first briefly reviewed and their limitations illustrated via examples of practical analog circuits. In all of these criteria simplifications are performed by estimating the numerical values of the symbolic terms at a single point of the parameter space, corresponding to the expected typical values for symbols. Consequent quantitative as well as qualitative inaccuracies resulting from this approach are identified. A new simplification strategy for flat symbolic approaches is then presented in which insignificant terms are deleted taking into account expected ranges of variation in the symbol values. Examples are used to show that this new criterion overcomes the drawbacks encountered in previous ones. Finally, an algorithm to simplify hierarchical formulae is presented which includes consideration of the potential ranges of variation in the symbolic parameter values. This algorithm is also applied to practical analog integrated circuits.1. Most of the results in this paper have been obtained with a 4-Mips and 8-Mbyte physical memory SUN3/260 workstation.2. In the rest of the paper the concept offormula complexity denotes the number of symbolic terms contained in a formula. Each addend in (4) is considered as a term to this purpose.3. For instance, simplification of the voltage gain for the folded cascode OTA of figure 1b, with a maximum error margin of 60% ( _M = 0.6), yields a dc gain deviation of 1.6% [9].4. An analog schematic is said to be sized when a numerical value has been assigned to each circuit element and model parameter.5. In practice a sufficiently fine grid should be defined inside that region.6. Here, symbol is generally applied, in the sense that it may either denote a parameter space variable, a product of variables, or a sum of products.7. The models used in this example are intended only as an illustration. Hence, they do not include all the issues required for practical transconductance amplifier applications.     

An efficient large systems analysis method using system dynamic behavior

This paper presents our unified approach to the solution of large system analysis problems. The macromodular behavioral technique combines multiple-logic function macromodeling, functional latency and nested macromodel. We take advantage of the dynamic behavior and the repetitive modular structure of a system to improve the computational efficiency during system analysis. Several Bipolar and MOSFET electronic networks are used to demonstrate the merits of the macromodular behavioral method for large system analysis.Parts of the paper have been presented at the 16th Design Automation Conference (1979) and at the 1980 IEEE International Symposium on Circuits and Systems.     

格基约减算法及其应用

格基约减在许多应用上是一个非常有力的数学工具。本文详细介绍了有关格基约减算 法的概念、定义和著名的LLL算法,并在此基础上通过一个对低阶RSA算法的攻击过程对约减算法 的应用进行了简要介绍。     

MODIFIED DOUBLE-GRAPH DECOMPOSITION ANALYSIS FOR FINDING SYMBOLIC NETWORK FUNCTIONS

The concepts of complementary cofactor pairs, normal double-graphs and feasible torn vertex seta are introduced. By using them a decomposition theorem for first-order cofactor C(Y) is derived. Combining it with the modified double-graph method, a new decomposition analysis-modified double-graph decomposition analysis is presented for finding symbolic network functions. Its advantages are that the resultant symbolic expressions are compact and contain no cancellation terms, and its sign evaluation is very simple.     

Optimized symbolic dynamics approach for the analysis of the respiratory pattern

Traditional time domain techniques of data analysis are often not sufficient to characterize the complex dynamics of respiration. In this paper, the respiratory pattern variability is analyzed using symbolic dynamics. A group of 20 patients on weaning trials from mechanical ventilation are studied at two different pressure support ventilation levels, in order to obtain respiratory volume signals with different variability. Time series of inspiratory time, expiratory time, breathing duration, fractional inspiratory time, tidal volume and mean inspiratory flow are analyzed. Two different symbol alphabets, with three and four symbols, are considered to characterize the respiratory pattern variability. Assessment of the method is made using the 40 respiratory volume signals classified using clinical criteria into two classes: low variability (LV) or high variability (HV). A discriminant analysis using single indexes from symbolic dynamics has been able to classify the respiratory volume signals with an out-of-sample accuracy of 100%.     

An efficient CMOS buffer for driving large capacitive loads

A CMOS class AB high-drive buffer suitable for driving large capacitive and moderate resistive loads is presented. The buffer, designed using 3-/spl mu/m technology, occupies only 100 mils/SUP 2/ of area and dissipates 1.5 mW of DC power from a /spl plusmn/2.5-V supply, yet it is capable of driving a 5000-pF capacitor at over 100-kHz clocking frequency. The buffer achieves good slew rate and fast settling by entering into a high-drive state during slewing and returning to a low-power wide-band state during the settling period. Unconditional stability is attained when C/SUB L//spl ges/100 pF and R/SUB L//spl ges/10 k/spl Omega/. Total harmonic distortion is below 0.5% for over 70% of the full supply range.     

Variation range based simplification for meaningful symbolic analysis of analog integrated circuits

This paper presents a variation range based symbolic simplification technique, where each circuit parameter is represented via a range of variation. We generate a database to handle the variation ranges of the circuit parameters and perform simulated annealing algorithm to achieve the most compact symbolic expressions. In contrast to the existing techniques, the main advantage of the proposed method is that the simplified symbolic expressions have an acceptable generalizability in the whole ranges of variations of the circuit parameters. The maximum allowable simplification error can be controlled by the user based on the required accuracy level that he needs. Simulation results demonstrate that the proposed method outperforms the conventional techniques in terms of expression complexity, accuracy and generalizability of the simplified expressions. The resultant expressions are only as complicated as necessary to give the required accuracy in the results, which help in giving a better insight into the circuit behavior.     

An efficient incremental face annotation for large scale web services

This paper proposes an incremental face annotation framework for sharing and publishing photographs which contain faces under a large scale web platform such as a social network service with millions of users. Unlike the conventional face recognition environment addressed by most existing works, the image databases being accessed by the large pool of users can be huge and frequently updated. A reasonable way to efficiently annotate such huge databases is to accommodate an adaptation of model parameters without the need to retrain the model all over again when new data arrives. In this work, we are particularly interested in the following issues related to increment of data: (i) the huge number of images being added at each instant, (ii) the large number of users joining the web each day, and (iii) the large number of classification systems being added at each period. We propose an efficient recursive estimation method to handle these data increment issues. Our experiments on several databases show that our proposed method achieves an almost constant execution time with comparable accuracy relative to those state-of-the-art incremental versions of principal component analysis, linear discriminant analysis and support vector machine.     

Computers for symbolic processing

A detailed survey on the motivations, design, applications, current status, and limitations of computers designed for symbolic processing is provided. Symbolic processing computations are performed at the word, relation, or meaning levels, and the knowledge used in symbolic applications may be fuzzy, uncertain, indeterminate, and ill represented. Various techniques for knowledge representation and processing are discussed from both the designers' and users' points of view. The design and choice of a suitable language for symbolic processing and the mapping of applications into a software architecture are then considered. The process of refining the application requirements into hardware and software architectures is treated, and state-of-art sequential and parallel computers designed for symbolic processing are discussed     

Memory efficient propagation-based watershed and influence zonealgorithms for large images

Propagation front or grassfire methods are very popular in image processing because of their efficiency and because of their inherent geodesic nature. However, because of their random-access nature, they are inefficient in large images that cannot fit in available random access memory. We explore ways to increase the memory efficiency of two algorithms that use propagation fronts: the skeletonization by influence zones and the watershed transform. Two algorithms are presented for the skeletonization by influence zones. The first computes the skeletonization on surfaces without storing the enclosing volume. The second performs the skeletonization without any region reference, by using only the propagation fronts. The watershed transform algorithm that was developed keeps in memory the propagation fronts and only one greylevel of the image. All three algorithms use much less memory than the ones presented in the literature so far. Several techniques have been developed in this work in order to minimize the effect of these set operations. These include fast search methods, double propagation fronts, directional propagation, and others.     

Algorithm for inversion of large matrices by iteration

A method is described whereby large suitably partitioned matrices can be inverted. The inversion is accomplished with theoretically infinite precision, by a finite iteration procedure involving inversion of submatrices.     

IMe: 4-term formula method for the symbolic analysis of linear circuits

This paper is intended to show a general method (inhibition method) that relies on the superposition principle to analyze linear systems and electric circuits, based on hierarchical sequences of more simple topologies with some inhibited elements and on a simple recollecting logic to calculate the final solution from the previous partial and more elementary solutions. The result of the analysis is represented by and stored into a table (called the inhibition sequence table), which thus consists in a kind of database for the system or electric circuit being analyzed. The method follows a hierarchical structuration that is halfway physical (the hierarchical blocks have a nonabstract meaning) and halfway logical (the relationships among the blocks carry out information richer than the hierarchy itself). Once the table is calculated for a particular system, then a little calculation overhead allows some other interesting features, like the possibility to analyze an old circuit with some new branches added by analyzing the new elements only, or like the calculation of exact sensitivities without using derivatives, or like the calculation of the inverse matrix avoiding the usual matrix inversion procedure. A proof of the Inhibition Theorem is given and also some tutorial circuit examples.     

用Nullor构建理想电压源模型求解符号传递函数的方法

电路网络的符号传递函数分析技术在电路分析与设计中起着重要的作用。本文利用Nullor元件，构建了理想电压源的模型，扩展了节点分析法的应用范围，并且基于Mathematica强大的符号处理能力，设计出一种求解网络符号传递函数的节点分析法。该方法可以求解节点间含有理想电压源的线性时不变（LTI）系统中各种电路参数的符号传递函数。电路分析与设计实例表明，利用本文给出的方法所开发的符号传递函数求解程序，是电路分析和电路设计的有利助手。     

Algorithm for synthesis of efficient S-boxes based on cellular automata

A method for synthesis of efficient schemes of S-boxes based on cellular automata satisfying the main criteria of cryptographic quality has been proposed. The cellular automata rules making it possible to obtain S-boxes satisfying the criterion of maximum avalanche effect were found.     

Computationally efficient algorithms for cyclic spectral analysis

Two computationally efficient algorithms for digital cyclic spectral analysis, the FFT accumulation method (FAM) and the strip spectral correlation algorithm (SSCA), are developed from a series of modifications on a simple time smoothing algorithm. The signal processing, computational, and structural attributes of time smoothing algorithms are presented with emphasis on the FAM and SSCA. As a vehicle for examining the algorithms the problem of estimating the cyclic cross spectrum of two complex-valued sequences is considered. Simplifications of the resulting expressions to special cases of the cross cyclic spectrum of two complex-valued sequences, such as the cyclic spectrum of a single real-valued sequence, are easily found. Computational and structural simplifications arising from the specialization are described