Two operations, the cyclic shifting and the inner product, are defined by the properties of irreducible all one polynomials. An effective algorithm is proposed for computing multiplications over a class of fields GF(2/sup m/) using the two operations. Then, two low-complexity bit-parallel systolic multipliers are presented based on the algorithm. The first multiplier is composed of (m+1)/sup 2/ identical cells, each consisting of one 2-input AND gate, one 2-input XOR gate, and three 1-bit latches. The other multiplier comprises of (m+1)/sup 2/ identical cells and mXOR gates. Each cell consists of one 2-input AND gate, one 2-input XOR gate, and four 1-bit latches. Each multiplier exhibits very low latency and propagation delay and is thus very fast. Moreover, the architectures of the two multipliers can be applied in computing multiplications over the class of fields GF(2/sup m/) in which the elements are represented with the root of an irreducible equally spaced polynomial of degree m.

A vowel-driven Mandarin speech autodialer based on the special characteristics of Mandarin digits is introduced. Additionally, an effective speaker adaptation technique based on the generalized probabilistic descent (GPD) algorithm is derived and integrated into the speech autodialer. Experimental results show that an encouraging performance is obtained.

In this paper, a new iterative winner-take-all (WTA) neural network is developed and analyzed. The proposed WTA neural net with one-layer structure is established under the concept of the statistical mean. For three typical distributions of initial activations, the convergence behaviors of the existing and the proposed WTA neural nets are evaluated by theoretical analyses and Monte Carlo simulations. We found that the suggested WTA neural network on average requires fewer than Log(2)M iterations to complete a WTA process for the three distributed inputs, where M is the number of competitors. Furthermore, the fault tolerances of the iterative WTA nets are analyzed and simulated. From the view points of convergence speed, hardware complexity, and robustness to the errors, the proposed WTA is suitable for various applications.

In this paper, the projection location constraint is exploited to reduce ambiguous correspondences in trinocular systems. The inherent matching problems associated with the spurious features produced by overlapping among targets, the periodic structure of objects and the occlusion features were solved. The projection location constraint can be achieved by the deviation-to-distance transformation and the optimal epipolar constraint. The deviation-to-distance transformation transforms the location deviation of the extracted feature on an image plane to a maximum distance between the potential corresponding features and the epipolar line on another image for restricting the searching area of correspondences. The optimal epipolar constraint is obtained by adjusting the camera model before systems start to work. With the deviation-to-distance transformation and the optimal epipolar constraint, the arbitral area for searching the potential corresponding features can be made reasonably small. This not only saves computational time but also results in fewer ambiguous correspondences. In practice, the importance of the paper is that it proposes a very easy adjustment of camera geometry to simplify the most troublesome matching problem encountered in stereo systems. All the discussions and derivations are based on the geometry of the camera model and the mapping between the locations of the 3D features and their projection locations on the image planes. The non-ambiguity probability of the trinocular system is derived theoretically and verified by experimental results.>

In this paper, a new feasible approach is proposed to determine the 3-D location and orientation as well as the radius of a cylinder pasted with a known-height label. The proposed approach uses a rectangle-shaped standard mark composed of two point-pairs for performing monocular image analysis. A monocular image of a labelled cylinder is first taken. Image processing and numerical analysis techniques are then used to set two point-pairs located on the boundary of the visible part of the cylindrical label. According to 3-D imaging geometry, the location and orientation as well as the radius of the cylinder relative to the camera are uniquely determined by using 3-D vector analysis and simple algebraic computation. Owing to the full linearity of the,derivation, this approach can achieve high speed requirement. In addition, no prerequisite restriction is imposed on the image-grabbing process and there is no need to perform the calibration of the focal length since it can be derived. Experimental results, with mean errors less than 3%, prove the feasibility of the proposed approach.

We present a new technique to synthesize high throughput pipelined data paths for those algorithms containing nested loops. Given an initiation interval constraint, the objective is to synthesize a low cost data path for the problem in register transfer level (RTL). Mapping algorithms for processor array synthesis which do not take initiation interval into account cannot be applied to our case; while traditional pipeline synthesis techniques suffer from complex interconnection and high register cost. Our contributions include proposing (1) an approach which conserves the regularities of nested loops, and (2) an architecture which possesses the advantages of both the highly multiplexed and lowly multiplexed architecture styles. Experiments on several algorithms in the image and DSP applications show this approach is very efficient.

A technique called dynamic search-window adjustment is proposed to improve the performance of three-step searches (TSS) and to prevent the search direction from being easily misdirected by insufficient information. An interlaced-search technique is presented for the purpose of reducing the search positions. A fast search algorithm using both techniques is proposed. It is shown that the average displaced frame difference and search positions of the proposed algorithm are about 1-7% and 24-44% fewer than TSS, respectively.>

A feasible approach is proposed to determine the 3D location and orientation of a cylinder with a label stuck on it at a known height. The proposed approach uses a rectangle-shaped standard mark composed of two point-pairs for performing monocular image analysis. A monocular image of a labelled cylinder is first taken. Image processing and numerical analysis techniques are then used to select two point-pairs located on the boundary of the visible part of the cylindrical label. According to 3D imaging geometry, the location and orientation of the cylinder relative to the camera are uniquely determined by using 3D vector analysis and simple algebraic computation. Owing to the full linearity of the derivation, this approach can perform at high speed.>

A Bayesian neural network; a one-stage dynamic programming algorithm, and a Hopfield time-alignment network are integrated to form a speaker-independent continuous Mandarin digit recognizer. In this system, a Bayesian network trained with a splitting LVQ (learning vector quantisation) and the LVQ2 algorithms gives the a posteriori probability. The one-stage algorithm is then employed for coarse recognition. Finally, the Hopfield time-alignment network is used to eliminate unreasonable candidates. Experimental evaluation of this system, using 53 speakers (28 male, 25 female), each speaking 20 digit strings of varying length (1-7 digits/string) and at varying speaking rate (150-240 digits/min), gave an average recognition accuracy of 94.3%, with 1.4% insertion, 1.1% deletion, and 3.2% substitution errors.>

A speaker-independent isolated word recognizer is proposed. It is obtained by concatenating a Bayesian neural network and a Hopfield time-alignment network. In this system, the Bayesian network outputs the a posteriori probability for each speech frame, and the Hopfield network is then concatenated for time warping. A proposed splitting Learning Vector Quantization (LVQ) algorithm derived from the LBG clustering algorithm and the Kohonen LVQ algorithm is first used to train the Bayesian network. The LVQ2 algorithm is subsequently adopted as a final refinement step. A continuous mixture of Gaussian densities for each frame and multi-templates for each word are employed to characterize each word pattern. Experimental evaluation of this system with four templates/word and five mixtures/frame, using 53 speakers (28 males, 25 females) and isolated words (10 digits and 30 city names) databases, gave average recognition accuracies of 97.3%, for the speaker-trained mode and 95.7% for the speaker-independent mode, respectively. Comparisons with K-means and DTW algorithms show that the integration of the splitting LVQ and LVQ2 algorithms makes this system well suited to speaker-independent isolated word recognition. A cookbook approach for the determination of parameters in the Hopfield time-alignment network is also described.

In this paper we extend the use of the fault analysis method dealing with combinational circuits[1] to synchronous sequential circuits. Using the iterative array model, extended forward propagation and backward implication are performed. based on the observed values at primary outputs, to deduce the actual values of each line to determine its fault status. Any stuck fault can be identified, even in a circuit without any initialization sequence. A fault which is covered is tested unconditionally; thus the results obtained would not be invalidated in the presence of untested or untestable lines. Examples will be given to demonstrate the ability of our method.

In this paper, we address the problem of deriving robust tests for single stuck-open faults in CMOS combinational circuits. We first examine the characteristics of the transition of the two patterns belonging to a two-pattern test. Then, a sufficient and necessary condition for a test to be robust is given. According to the given condition, we propose a new method to derive robust tests. Robustness verification of the derived tests is no longer required when using our approach.

A novel approach to robot guidance in an unfamiliar environment is presented. In previous guiding methods, a preinstalled map or predefined path is required for a robot navigating in its working space. The present method uses an indication post (IP) to provide the information on the destination, the direction, and the distance from the source point to the destination point, assuming that the mobile robot has no information concerning its workplace. To realize the concept, many IPs depicting simple information were designed. The content of IPs can be described by using a finite-state grammar. Image-processing, statistical, and syntactic pattern recognition approaches are integrated to solve the problems of IP finding, robot location determination, IP identification, and understanding. Experiments simulating practical environments were performed. The results verify that the IP candidates can be automatically found and the depicted information can be extracted and understood correctly, so that the mobile robot is able to plan a global optimal path from an arbitrary start point to an arbitrary end point.>

A novel ID-based cryptographic scheme for implementing a public-key cryptosystem and signature is proposed. Instead of generating and publishing a public key for each user, the ID-based scheme permits each user to choose his/her name or network address as his/her public key. This eliminates the needs of a large public field and the exchange of private or public keys. The major advantage of the ID-based cryptosystem based on this scheme over other published ID-based cryptosystems is that the number of users can be extended to t*L users without degrading the system's security even when users conspire, where L is the number of the system's secrets, and t is the number of factors in p-1, where p is a large prime number.>

Two algorithms are proposed to improve the Merkle-Hellman knapsack public-key cryptosystem. an approach to transform a superincreasing sequence to a high-density knapsack sequence is proposed. The algorithm is easy to implement and eliminates the redundancy of many knapsack cryptosystems. A linear shift method is used to improve the security of the knapsack public-key cryptosystem. It is shown that several knapsacks (e.g., the so-called useless knapsack), which cannot be generated by using the Merkle-Hellman scheme, can be generated by the linear shift method. Thus A. Shamir's (1982, 1984) attack to the original knapsack, as well as the low-density attack to the iterated knapsack, cannot be applied to this system successfully. It is interesting to note that the concept of the requirement of being one-to-one in practical enciphering keys is not necessary for this system.>

A new algorithm is presented for the piecewise linear approximation of two-dimensional digitized curves against a square grid. The algorithm utilizes an adaptive reduction procedure in two approximation phases to select the critical points of a digitized curve such that the deviation, from the digitized curve to its final approximated curve, is bounded by a uniform error tolerance. The time complexity of this algorithm is O(m/sup 2/) rather than O(n/sup 2/) on the theoretical plane. In the experiments of fixing the initial and the final processing points, the performance of the algorithm has been compared to those of three prominent other algorithms regarding the required number of critical points and the total execution time of the program. Of the four algorithms compared, the present algorithm consistently has the shortest execution time of the program, and it tends most to require as few critical points as the optimum algorithm that was tested.>

A single-key-lock (SKL) mechanism used for implementing the access matrix of a computer protection system is proposed. The key selection is very flexible. The lock values are generated recursively using the Newton interpolating polynomial. A new user/file can be inserted into the system without recomputing all locks/keys. Since the computational load of the key-lock operation depends on the key positions in the access matrix, a user-hierarchy structure can be constructed for the mechanism. Thus, the smallest key value is assigned to a user who accesses the information resources more frequently than others, in order to reduce the average computation time. An example is included to illustrate this idea.>

A conference key distribution system (CKDS) can provide a common secret communication key to a set of M stations. A CKDS based on Lagrange interpolating polynomial is introduced. It is easy to see that breaking this system is equivalent to break the Diffie-Hellman public-key distribution system. This conference key is selected by the conference chairstation and hidden in the Lagrange interpolating polynomial. Recovering this key by each participating station only requires M-1 multiplications and M-2 additions over a finite field GF(P).>

This paper presents an efficient and reliable method for general semiconductor device parameter extraction. The parameter extraction technique consists of minimizing a nonlinear objective function. A hybrid approach based on strategical combinations of the Gauss method and a novel minimum search scheme is employed. Various of strategies are proposed to make the parameter extraction task more efficient and accurate. According to the proposed technique, a model-independent parameter extraction program was implemented and highly satisfactory results have been obtained. Experimentally, it is found that, if the initial guess deviates from the optimum solution within 70 percent, a unique set of optimum device parameters can be extracted in five to eight iterations. The parameter extraction technique presented in this paper can be readily applied to sensitivity analysis of device and circuit performances and to quantitative evaluation of model accuracy. It is shown that the presented method is a very useful tool for device and integrated circuit design.