This paper deals with the synthesis of Petri nets. Partial languages adequately represent the concurrent behaviors of Petri nets. We first propose a construction problem for Petri nets, in which the objective is to synthesize a Petri net to exhibit the desired behavior specified as a partial language. We next discuss the solvability of this problem and last present the cutline of a solution technique.

In this paper, we introduce a parallel algorithm for parsing context-free languages. Our algorithm can handle arbitrary context-free grammars since it is based on Earley's algorithm. Our algorithm can operate on any loosely coupled multiprocessor which can provide a topology of a one-way ring. Our algorithm uses p processors to parse an input string of length n where 1 p n. It is shown that our algorithm requires O(n3/p) time. The algorithm uses a simple job allocation strategy. However, it achieves high load balancing and uses the processors efficiently.

In this paper, we propose a clustering based linear ordering algorithm which consists of global ordering and local ordering. In the global ordering, the algorithm forms clusters from n given vertices and orders the clusters. In the local ordering, the elements in each cluster are linearly ordered. The linear order, thus produced, is used to obtain optimal κ-way partitioning based on scaled cost objective function. When the number of cluster is one, the proposed algorithm is exactly the same as MELO [2]. But the proposed algorithm has more global partitioning information than MELO by clustering. Experiment with 11 benchmark circuits for κ-way (2 κ 10) partitioning shows that the proposed algorithm yields an average of 10.6% improvement over MELO [2] for the κ-way scaled cost partitioning.

It is well known that extracting parallel loops plays a significant role in designing parallelizing compilers. The execution efficiency of a loop is enhanced when the loop can be executed in parallel or partial parallel, like a DOALL or DOACROSS loop. This paper reports on the practical parallelism detector (PPD) that is implemented in PFPC (a portable FORTRAN parallelizing compiler running on OSF/1) at NCTU to concentrate on finding the parallelism available in loops. The PPD can extract the potential DOALL and DOACROSS loops in a program by invoking a combination of the ZIV test and the I test for verifying array subscripts. Furthermore, if DOACROSS loops are available, an optimization of synchronization statement is made. Experimental results show that PPD is more reliable and accurate than previous approaches.

Optical Frequency Division Multiplexing (OFDM) is an attractive multiplexing approach for exploiting optical communication technology. Although considerable progress has been made in this approach, it still suffers from numerous potential impairments, stemming from several phenomena. (i.e., laser unstability, residual temperature variations, linear and nonlinear cross talk.). Conventional serial coding technique is not practical in lightwave systems, as it changes the system's bit rate that is not desirable. In this paper a new Parallel Coded Optical Multicarrier Frequency Division Multiplexing (PCOM-FDM) technique has been investigated. The strategy of multicarriers, together with Parallel Forward Error Control (PFEC) coding, is a potentially novel approach as in this approach we have, 1) Investigated optical multicarrier communication that is effective in combating dispersion and increasing throughput, 2) Proposed PFEC coding which is different from conventional serial coding in respect that it does not change the system bit rate per carrier and prevents the effects of channel wandering. It is highly desirable in lightwave systems and thus holds a vital importance in practical high speed optical communication systems. Theoretical treatment shows that the proposed approach is promising and practical.

This paper treats a new-type power combining system of four oscillators equally coupled to one another through an eight-port hybrid. This system is marked by easy analyzability and adjustability from its symmetrical construction. In addition, a combined power from the four oscillators is distinguishably delivered to an arbitrary port of four output ports, and hence can be switched in four ways. Experimental corroboration is presented also.

Electronic systems are progressively replacing mechanical devices or human operation for identifying people or objects in everyday-life applications. Especially, the contactless identification systems available today have several advantages, but they cannot handle easily several simultaneously present items. This paper describes a solution to this problem, based on blind source separation techniques. The effectiveness of this approach is experimentally demonstrated, especially by using a real-time DSP-based implementation of the proposed system.

An approach to design for testability using register-transfer level (RTL) partial scan selection is described. We define an RTL circuit model which enables efficient description in an electronic system design automation (ESDA) tool and testability analysis which leads to effective partial scan selection for RTL design including data path circuits and control circuits such as state machines. We also introduced a method of partial scan selection at RTL which selects critical registers and state machines based on RTL testability analysis. DFT techniques using gate level testability measures have been studied and concluded that they are not successful in achieving high fault coverage [15]. However, we started this work for the following reasons, 1) In sequential ATPG procedure, more than two memory elements belonging to a functional units such as registers and state machines are often required to be justified at a time. At RTL, state machines and registers are explicitly described and recognized as functional units while gate level memory elements are scattered over the circuit. 2) As discussed in [6], if the circuit is modified so that the test sequence which causes state transition between initial and final states of sequential ATPG can be easily obtained, ATPG results can be also improved. Complex state machines can be identified at RTL. According to the experimental results, our gate level DFT achieves high fault coverage comparable with the previously published most successful DFT methods, and DFT at RTL resulted in higher fault coverage than gate level DFT at much shorter CPU time.

In this paper partial response signalling and trellis coded modulation are considered together to improve bandwidth efficiency and error performance for M-QAM and denoted as Modified/Quadrature Partial Response-Trellis Coded Modulation (M/QPR-TCM) and two new non-catastrophic schemes M/6QPR-TCM and M/9QPR-TCM are introduced for 4QAM. In colored noise with correlation coefficient less than zero, the proposed schemes perform better than in AWGN case. Another interesting result is that when the combined system is used on a Rician fading channel, the bit error probability upper bounds of the proposed systems are better than their counterparts the 4QAM-TCM systems with 2 and 4 states, respectively, for SNR values greater than a threshold, which have the best error performance in the literature.

In this paper, we propose a novel SPICE oriented steady-state analysis of nonlinear circuits based on the circuit partition technique. Namely, a given circuit is partitioned into the linear and nonlinear subnetworks by the application of the substitution theorem. Each subnetwork is solved using SPICE simulator by the different techniques of AC analysis and transient analysis, respectively, whose steady-state reponse is found by an iteration method. The novel points of our algorithm are as follows: Once the linear subnetworks are solved by AC analysis, each subnetwork is replaced by a simple equivalent RL or RC circuit at each frequency component. On the other hand, the reponse of nonlinear subnetworks are solved by transient analysis. If we assume that the sensitivity circuit is approximated at the DC operational point, the variational value will be also calculated from a simple RL ro RC circuit. Thus, our method is very simple and can be also applied to large scale circuits, effciently. To improve the convergency, we introduce a compensation technique which is usefully applied to stiff circuits containing components such as diodes and transistors.

In this paper, we present an analysis of microstrip line with a trapezoidal dielectric ridge in multilayered media. The method employed in this characterization is called partial-boundary element method (p-BEM) which provides an efficient technique to the analysis of the structures with multilayered media. To improve the convergence of the Green's function used in the analysis with the P-BEM, we employ a technique based on a combination of the Fourier series expansion and the method of images. Treatment on convergence for the boundary integrals is also described. After this treatment, it requires typically one tenth or one hundredth of Fourier terms to obtain the same accuracy compared with the original Green's function. Numerical results are presented for two microstrip lines that have a trapezoidal dielectric ridge placed on a one-layered substrate and a two-layered substrate. These numerical results demonstrate the effects on the characteristics of the microstrip line due to the existence of the dielectric ridge as well as the second layer between the ridge and the fundamental substrate.

This paper describes some dynamical properties of higher order neural networks with decreasing energy functions. First, we will show that for any symmetric higher order neural network which permits only one element to transit at each step, there are only periodic sequences with the length 1. Further, it will be shown that for any higher order neural network, with decreasing energy functions, which permits all elements to transit at each step, there does not exist any periodic sequence with the length being over k + 1, where k is the order of the network. Lastly, we will give a characterization for higher order neural networks, with the order 2 and a decreasing energy function each, which permit plural elements to transit at each step and have periodic sequences only with the lengh 1.

The estimation of model parameter is essentially important for an MRF image model to work well. Because the maximum likelihood estimate (MLE), which is statistically optimal, is too difficult to implement, the conventional estimates such as the maximum pseudo-likelihood estimate (MPLE), the coding method estimate (CME), and the least-squares estimate (LSE) are all based on the (conditional) pixel probabilities for simplicity. However, the conventional pixel-based estimators are not very satisfactorily accurate, especially when the interactions of pixels are strong. We therefore propose two window-based estimators to improve the estimation accuracy: the adjoining-conditional-window (ACW) scheme and the separated-conditional-window (SCW) scheme. The replacement of the pixel probabilities by the joint probabilities of window pixels was inspired by the fact that the pixels in an image present information in a joint way and hence the more pixels we deal with the joint probabilities of, the more accurate the estimate should be. The window-based estimators include the pixel-based ones as special cases. We present respectively the relationship between the MLE and each of the two window-based estimates. Through the relationships we provide a unified view that the conventional pixel-based estimates and our window-based estimates all approximate the MLE. The accuracy of all the estimates can be described by two types of superiority: the cross-scheme superiority that an ACW estimate is more accurate than the SCW estimate with the same window size, and the in-scheme superiority that an ACW (or SCW) estimate more accurate than another ACW (or SCW) estimate which uses smaller window size. The experimental results showed the two types of superiority and particularly the significant improvement in estimation accuracy due to using window probabilities instead of pixel probabilities.

This paper describes a waveform relaxationbased coupled lossy transmission line circuit simulator DESIRE3T+. First, the generalized method of characteristics (GMC) is reviewed, which replaces a lossy transmission line with an equivalent disjoint network. Next, the generalized line delay window (GLDW) partitioning technique is proposed, which accelerates the transient analysis of the circuits including transmission lines replaced by GMC model. Finally GMC model and GLDW technique are implemented in hte relaxation-based circuit simulator DESIRE3T+ which can analyze bipolar transistor circuits by using the dynamic decomposition technique, and the performance is estimated.

In this paper we propose a class of byte-error-correcting codes derived from algebraic curves which is a generalization on the Reed-Solomon codes, and present their fast parallel decoding algorithm. Our algorithm can correct up to (m + b -θ)/2b byte-errors for the byte length b, where m + b -θ + 1dG for the Goppa designed distance dG. This decoding algorithm can be parallelized. In this algorithm, for our code over the finite field GF (q), the total complexity for finding byte-error locations is O (bt(t + q - 1)) with time complexity O (t(t + q - 1)) and space complexity O(b), and the total complexity for finding error values is O (bt(b + q - 1)) with time complexity O (b(b + q - 1)) and space complexity O (t), where t(m + b -θ)/2b. Our byte-error-correcting algorithm is superior to the conventional fast decoding algorithm for randomerrors in regard to the number of correcting byte-errors in several cases.

Overheads caused by frequently communicating α-β values among numerous parallel search processes not only degrade greatly the performance of existing parallel α-β search algorithm but also make it impractical to implement these algorithms in parallel hardware. To solve this problem, the proposed architecture reduces the overheads by using specially designed multi-value arbiters to compare and global broadcasting buses to communicate α-β values. In addition, the architecture employs a set of α-β search control units (α-β SCU's) with distributed α-β registers to accelerate the search by searching all subtrees in parallel. Simulation results show that the proposed parallel architecture with 1444 (38 38) (α-β SCU's) searching in parallel can achieve 179 folds of speed-up. To verify the parallel architecture, we implemented a VLSI chip with 3 α-β SCU's. The chip can achieve a search speed of 13,381,345 node-visits per second, which is more than three orders of improvement over that of existing parallel algorithms.

The problem of test generation for VLSI circuits computationally requires prohibitive costs. Parallel processing on a multiprocessor system is one of available methods in order to speedup the process for such time-consuming problems. In this paper, we analyze the performance of parallel test generation for combinational circuits. We present two types of parallel test generation systems in which the communication methods are different; vector broadcasting (VB) and fault broadcasting (FB) systems, and analyze the number of generated test vectors, the costs of test vector generation, fault simulation and communication, and the speedup of these parallel test generation systems, where the two types of communication factors; the communication cut-off factor and the communication period, are applied. We also present experimental results on the VB and FB systems implemented on a network of workstations using ISCAS'85 and ISCAS'89 benchmark circuits. The analytical and experimental results show that the total number of test vectors generated in the VB system is the same as that in the FB system, the speedup of the FB system is larger than that of the VB, and it is effective in reducing the communication cost to switch broadcasted data from vectors to faults.

Most research on the estimation of direction of arrival (DOA) has been performed based on the assumption that the signal sources are point sources. In some real surroundings, signal source localization can more adequately be accomplished with distributed source models. When the signal sources are distributed over an area, we cannot directly use well-known DOA estimation methods, because these methods are established based on the point source assumption. In this paper, we propose a 3-dimensional distributed signal source model, in which a source is represented by two parameters, the center angle and degree of dispersion. Then, we address the estimation of the elevation and azimuth angles of distributed sources based on the parametric distributed source modeling in the 3-dimensional space.

Many numerical simulation problems of natural phenomena are formulated by large tridiagonal and block tridiagonal linear systems. In this paper, an efficient parallel algorithm to solve a tridiagonal linear system is proposed. The algorithm named bi-recurrence algorithm has an inherent parallelism which is suitable for parallel processing. Its time complexity is 8N - 4 for a tridiagonal linear system of order N. The complexity is little more than the Gaussian elimination algorithm. For parallel implementation with two processors, the time complexity is 4N - 1. Based on the bi-recurrence algorithm, a VLSI oriented tridiagonal solver is designed, which has an architecture of 1-D linear systolic array with three processing cells. The systolic tridiagonal solver completes finding the solution of a tridiagonal linear system in 3N + 6 units of time. A highly parallel systolic tridiagonal solver is also presented. The solver is characterized by highly parallel computability which originates in the divide-and-conquer strategy and high cost performance which originates in the systolic architecture. This solver completes finding the solution in 10(N/p) + 6p + 23 time units, where p is the number of partitions of the system.

Recently, the high-speed data transmission techniques that have been developed for communication systems have in turn necessitated the implementation of high-speed error correction circuits. Parallel processing has been found to be an effective method of speeding up operarions, since the maximum achievable clock frequency is generally bounded by the physical constraints of the circuit. This paper presents a parallel encoder and decoder architecture which can be applied to both binary and nonbinary cyclic codes. The architecture allows H symbols to be processed in parallel, where H is an arbitrary integer, although its hardware complexity is not proportional to the number of parallel symbols H. As an example, we investigate hardware complexity for a Reed-Solomon code and a binary BCH code. It is shown that both the hardware complexity and the delay for a parallel circuit is much less than that with the parallel operation of H conventional circuits. Although the only problem with this parallel architecture is that the encoder's critical path length increases with H, the proposed architecture is more efficient than a setup using H conventional circuits for high data rate applications. It is also suggested that a parallel Reed-Solomon encoder and decoder, which can keep up with optical transmission rates, i.e., several giga bits/sec, could be implemented on one LSI chip using current CMOS technology.