學術出版;;Publications

Permanent URI for this communityhdl:11536/1

收集所有交通大學研究人員與學生個人或團體所發表之各項學術著作，涵蓋期刊論文、教師專書、學位論文等項。;;Collections of Publications of NCTU Researchers and Students Like Journal Papers and Thesis.

Browse

🏛️國立陽明交通大學機構典藏

Search Results

Now showing 1 - 10 of 18

An Efficient LDPC Decoder Architecture with a High-Performance Decoding Algorithm
(2010-11-01)
Hung, Jui-Hui
;
Chen, Sau-Gee
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
In this work a high performance LDPC decoder architecture is presented It is a partially parallel architecture for low complexity consideration In order to eliminate the idling time and hardware complexity in conventional partially parallel decoders the decoding process decoder architecture and memory structure are optimized Particularly the parity check matrix is optimally partitioned into four unequal sub matrices that lead to high efficiency in hardware sharing As a result it can handle two different codewords simultaneously with 100% hard ware utilization Furthermore for minimizing the performance loss due to round off errors in fixed point implementations the well known mod died min sum decoding algorithm is enhanced by our recently proposed high performance CMVP decoding algorithm Overall the proposed de coder has high throughput low complexity and good BER performances In the circuit implementation example of the (576 288) parity check matrix for IEEE 802 16e standard the decoder achieves a data rate of 5 5 Gbps assuming 10 decoding iterations and 7 quantization bits with a small area of 653K gates based on UMC 90 nm process technology
Weighted connected domination and Steiner trees in distance-hereditary graphs
(1998-10-05)
Yeh, HG
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
Distance-hereditary graphs are graphs in which every two vertices have the same distance in every connected induced subgraph containing them. This paper studies distance-hereditary graphs from an algorithmic viewpoint. In particular, we present linear-time algorithms for finding a minimum weighted connected dominating set and a minimum vertex-weighted Steiner tree in a distance-hereditary graph. Both problems are NP-complete in general graphs. (C) 1998 Elsevier Science B.V. All rights reserved.
On computing the minimum feedback vertex set of a directed graph by contraction operations
(2000-03-01)
Lin, HM
;
Jou, JY
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
Finding the minimum feedback vertex set (MFVS) in a graph is an important problem for a variety of computer-aided design (CAD) applications and graph reduction plays an important role in solving this intractable problem. This paper is largely concerned with three new and powerful reduction operations. Each of these operations defines a new class of graphs, strictly larger than the class of contractible graphs [Levy and Low (1988)], in which the MFVS can be found in polynomial-time complexity. Based on these operations, an exact algorithm run on branch and bound manner is developed. This exact algorithm uses a good heuristic to find out an initial solution and a good bounding strategy to prune the solution space. To demonstrate the efficiency of our algorithms, we have implemented our algorithms and applied them to solving the partial scan problem in ISCAS'89 benchmarks. The experimental results show that if our three new contraction operations are applied, 27 out of 31 circuits in ISCAS'89 benchmarks can be fully reduced. Otherwise, only 12 out of 31 can be fully reduced. Furthermore, for all ISCAS'89 benchmarks our exact algorithm can fmd the exact cutsets in less than 3 s (CPU time) on SUN-UltraII workstation. Therefore, the new contraction operations and our algorithms are demonstrated to be very effective in the partial scan application.
Linear k-arboricities on trees
(2000-07-15)
Chang, GJ
;
Chen, BL
;
Fu, HL
;
Huang, KC
;
應用數學系
For a fixed positive integer k, the linear k-arboricity la(k)(G) of a graph G is the minimum number l such that the edge set E(G) can be partitioned into G disjoint sets and that each induces a subgraph whose components are paths of lengths at most k. This paper studies linear k-arboricity from an algorithmic point of view. In particular, we present a linear-time algorithm to determine whether a tree T has la(k)(T)less than or equal to m. (C) 2000 Elsevier Science B.V. All rights reserved.
An algorithm to approach invariant curves
(2001-02-01)
Yu, CJ
;
Lee, JE
;
應用數學系
;
Department of Applied Mathematics
We develop an algorithm to identify invariant curves efficiently. In dynamical systems, it helps do continuations of branches of quasi-periodic solutions smoothly in bifurcation diagrams. Several examples are demonstrated to provide the numerical evidence for the versatility of the algorithm. (C) 2001 Elsevier Science B.V. All rights reserved.
The distributed program reliability analysis on ring-type topologies
(2001-06-01)
Lin, MS
;
Chang, MS
;
Chen, DJ
;
Ku, KL
;
資訊科學與工程研究所
Distributed computing system (DCS) has become very popular for its high fault-tolerance, potential for parallel processing, and better reliability performance. One of the important issues in the design of the DCS is the reliability performance. Distributed program reliability (DPR) is addressed to obtain this reliability measure, In this paper, we propose a polynomial-time algorithm for computing the DPR of ring topology and show that solving the DPR problem on a ring of trees topology is NP-hard. (C) 2001 Elsevier Science Ltd. All rights reserved.
Weighted connected k-domination and weighted k-dominating clique in distance-hereditary graphs
(2001-07-28)
Yeh, HG
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
A graph is distance-hereditary if the distance between any two vertices in a connected induced subgraph is the same as in the original graph. This paper presents efficient algorithms for solving the weighted connected k-domination and the weighted k-dominating clique problems in distance-hereditary graphs, (C) 2001 Elsevier Science B.V. All rights reserved.
Neural network forecast model in deep excavation
(2002-01-01)
Jan, JC
;
Hung, SL
;
Chi, SY
;
Chern, JC
;
土木工程學系
Diaphragm wall deflection is an important field measurement in deep excavation. The monitoring data are applied to evaluate the construction performance to avoid a supporting system failure or damages incurred to adjacent structures. Despite the numerous case histories of construction projects and several forecasting methods, no method accurately forecasts the performance of construction due to the complicated geotechnical and construction factors affecting the behavior of the diaphragm wall. This work predicts the diaphragm wall deflection by using the adaptive limited memory-Broyden-Fletcher-Goldfarb-Shanno supervised neural network. Eighteen case histories of deep excavations with four to seven excavation stages are selected for training and verification. In addition, the knowledge representation adopts measured wall deflections of previous excavation stages as inputs to the network. Doing so substantially reduces the importance of soil parameters, which are often extremely fluctuating and difficult to assess. Simulation results indicate that the artificial neural network can reasonably predict the magnitude, as well as the location, of maximum deflection of the diaphragm wall.
A case study on the wafer probing scheduling problem
(2002-01-01)
Pearn, WL
;
Chung, SH
;
Yang, MH
;
工業工程與管理學系
;
Department of Industrial Engineering and Management
The wafer probing scheduling problem (WPSP) is a practical generalization of the classical parallel-machine scheduling problem, which has many real-world applications, particularly, in the integrated circuit (IC) manufacturing industry. In this paper, a case study on the WPSP is presented, which is taken from a wafer probing shop floor in an IC manufacturing factory. For the WPSP case investigated, the jobs are clustered by their product types, which are processed on groups of identical parallel machines and must be completed before the due dates. The job processing time depends on the product type, and the machine setup time is sequentially dependent on the orders of jobs processed. The objective in this case is to seek a probing job schedule with minimum total machine workload. Since the WPSP case investigated involves constraints on job clusters, job-cluster dependent processing time, due dates, machine capacity, and sequentially dependent setup time, it is more difficult to solve than the classical parallel-machine scheduling problem. The WPSP is formulated as an integer programming problem and the problem solved using the powerful CPLEX with effective implementation strategies. An efficient solution procedure to solve the WPSP near-optimally is proposed.
A simple algorithm to find the steps of double-loop networks
(2002-09-15)
Chan, RCF
;
Chen, CY
;
Hong, ZX
;
應用數學系
;
Department of Applied Mathematics
Double-loop networks have been widely studied as architecture for local area networks and it is well-known that the minimum distance diagram of a double-loop network yields an L-shape. Given an N, it is desirable to find a double-loop network DL(N;s(1),s(2)) with its diameter being the minimum among all double-loop networks with N stations. Since the diameter can be easily computed from an L-shape, one method is to start with a desirable L-shape and then asks whether there exist s(1) and s(2) (also called the steps of the double-loop network) to realize it. In this paper, we propose a simple and efficient algorithm to find s(1) and s(2), which is based on the Smith normalization method of Aguilo, Esque and Fiol. (C) 2002 Elsevier Science B.V. All rights reserved.

學術出版;;Publications

Browse

Filters

Settings

Sort By

Results per page

🏛️國立陽明交通大學機構典藏

Search Results