Browsing by Author "Guo, JY"

Now showing 1 - 6 of 6

An almost-linear time and linear space algorithm for the longest common subsequence problem
(2005-05-16)
Guo, JY
;
Hwang, FK
;
應用數學系
;
Department of Applied Mathematics
There are two general approaches to the longest common subsequence problem. The dynamic programming approach takes quadratic time but linear space, while the nondynamic-programming approach takes less time but more space. We propose a new implementation of the latter approach which seems to get the best for both time and space for the DNA application. (c) 2005 Elsevier B.V. All rights reserved.
On improving dynamic range of wideband multistage Sigma Delta modulator using nonlinear oscillation
(2005)
Chang, TH
;
Dung, LR
;
Guo, JY
;
電控工程研究所
;
Institute of Electrical and Control Engineering
This paper presents an improved architecture of the multistage (MASH) multibit sigma-delta modulators (Sigma Delta Ms). The architecture can be immune to circuit nonidealities over a large portion of input range when oversampling ratio (OSR) is low, and hence the dynamic range (DR) can be improved. Our approach is based on two resonator topologies, high-Q cascade-of-resonator-with-feedforward (HQCRFF) and low-Q cascade-of-integrator-with-feedforward (LQCIFF). The key to improving DR is to use HQCRFF-based single-bit structure in the first stage and have the first stage oscillated. When the first stage oscillates, the coarse quantization noise vanishes and hence circuit nonidealities, such as finite op-amp gain and capacitor mismatching, do not cause leakage quantization noise problem. In addition, because of the in-band zeros introduced by the resonators, the proposed architecture enhances the suppression of the in-band quantization noise for wideband applications. As the results of simulation, the proposed MASH architecture can inherently have wide DR without using additional calibration techniques.
On reducing leakage quantization noise of multistage Sigma Delta modulator using nonlinear oscillation
(2005)
Chang, TH
;
Dung, LR
;
Guo, JY
;
電控工程研究所
;
Institute of Electrical and Control Engineering
This paper presents an improved architecture of the multistage (MASH) multibit sigma-delta modulators (Sigma Delta Ms). The architecture can be immune to circuit nonidealities over a large portion of input range when oversampling ratio (OSR) is low, and hence the dynamic range (DR) can be improved. Our approach is based on two resonator topologies, high-Q cascade-of-resonator-with-feedforward (HQCRFF) and low-Q cascade-of-integrator-with-feedforward (LQCIFF). The key to improving DR is to use HQCRFF-based single-bit structure in the first stage and have the first stage oscillated. When the first stage oscillates, the coarse quantization noise vanishes and hence circuit nonidealities, such as finite op-amp gain and capacitor mismatching, do not cause leakage quantization noise problem. In addition, because of the in-band zeros introduced by the resonators, the proposed architecture enhances the suppression of the in-band quantization noise for wideband applications. As the results of simulation, the proposed MASH architecture can inherently have wide DR without using additional calibration techniques.
One-dimensional optimal bounded-shape partitions for Schur convex sum objective functions
(2006-05-01)
Chang, FH
;
Chen, HB
;
Guo, JY
;
Hwang, FK
;
Rothblum, UG
Consider the problem of partitioning n nonnegative numbers into p parts, where part i can be assigned n(i) numbers with n(i) lying in a given range. The goal is to maximize a Schur convex function F whose ith argument is the sum of numbers assigned to part i. The shape of a partition is the vector consisting of the sizes of its parts, further, a shape (without referring to a particular partition) is a vector of nonnegative integers (n(1),..., n(p)) which sum to n. A partition is called size-consecutive if there is a ranking of the parts which is consistent with their sizes, and all elements in a higher-ranked part exceed all elements in the lower-ranked part. We demonstrate that one can restrict attention to size-consecutive partitions with shapes that are nonmajorized, we study these shapes, bound their numbers and develop algorithms to enumerate them. Our study extends the analysis of a previous paper by Hwang and Rothblum which discussed the above problem assuming the existence of a majorizing shape.
Wide-sense nonblocking for multi-log(d) N networks under various routing strategies
(2006-03-07)
Chang, FH
;
Guo, JY
;
Hwang, FK
;
應用數學系
;
Department of Applied Mathematics
Chang et al. showed that the number of middle switches required for WSNB under strategies: save the unused, packing, minimum index, cyclic dynamic, and cyclic static, for the 3-stage Clos network C(n, m, r) with r >= 3 is the same as required for SNB. In this paper, we prove the same conclusion for the multi-log(d) N network. We also extend our results, except for the minimum index strategy, to a general class of networks including the 3-stage Clos network and the multi-log(d) N network as special cases. (c) 2005 Elsevier B.V. All rights reserved.
Wide-sense nonblocking for symmetric or asymmetric 3-stage Clos networks under various routing strategies
(2004-04-10)
Chang, FH
;
Guo, JY
;
Hwang, FK
;
Lin, CK
;
應用數學系
Benes established the notion of wide-sense nonblocking by constructing an example on the symmetric 3-stage Clos network under packing which requires less hardware compared to strict nonblocking. This has remained the only example of a wide-sense non-blocking 3-stage Clos network which is not strictly nonblocking. In this paper, we study packing as well as several other routing strategies which have been studied in the literature and proved that no other example exists for the symmetric 3-stage Clos network. We then extend the study to asymmetric 3-stage Clos network for the first time. In particular, we extend Benes example to asymmetric 3-stage Clos network and show that these are the only two possible examples for the strategies under study. (C) 2003 Elsevier B.V. All rights reserved.