Browsing by Author "Chen, RJ"

Now showing 1 - 20 of 22

A fast reliability-algorithm for the circular consecutive-weighted-k-out-of-n : F system
(1998-12-01)
Chang, JC
;
Chen, RJ
;
Hwang, FK
;
應用數學系
;
資訊工程學系
An O(Tn) algorithm is presented for the circular consecutive-weighted-k-out-of-n:F system, where T less than or equal to min[n, [(k - w(max))/w(min)] + 1]; w(max), w(min) are the maximum, minimum weights of all components. This algorithm is simpler and more efficient than the Wu & Chen O(min[n,k] . n) algorithm. When all weights are unity, this algorithm is simpler than other O(k . n) published algorithms.
A fast reliability-algorithm for the circular consecutive-weighted-k-out-of-n : F system
(1998-12-01)
Chang, JC
;
Chen, RJ
;
Hwang, FK
;
應用數學系
;
資訊工程學系
An O(Tn) algorithm is presented for the circular consecutive-weighted-k-out-of-n:F system, where T less than or equal to min[n, [(k - w(max))/w(min)] + 1]; w(max), w(min) are the maximum, minimum weights of all components. This algorithm is simpler and more efficient than the Wu & Chen O(min[n,k] . n) algorithm. When all weights are unity, this algorithm is simpler than other O(k . n) published algorithms.
A new random walk model for PCS networks
(2000-07-01)
Akyildiz, IF
;
Lin, YB
;
Lai, WR
;
Chen, RJ
;
資訊工程學系
This paper proposes a new approach to simplify the two-dimensional random walk models capturing the movement of mobile users in Personal Communications Services (PCS) networks. Analytical models are proposed for the new random walks. For a PCS network with hexagonal configuration, our approach reduces the states of the two-dimensional random walk from (3n(2) + 3n - 5) to n(n + 1)/2, where n is the layers of a cluster. For a mesh configuration, our approach reduces the states from (2n(2) - 2n + 1) to (n(2) + 2n + 4)/4 if n is even and to (n(2) + 2n + 5)/4 if n is odd. Simulation experiments are conducted to validate the analytical models. The results indicate that the errors between the analytical and simulation models are within 1%, Three applications (i.e., microcell/macrocell configuration, distance-based location update, and GPRS mobility management for data routing) are used to show how our new model can be used to investigate the performance of PCS networks.
A parallel Poisson generator using parallel prefix
(1996-02-01)
Lu, TC
;
Hou, YS
;
Chen, RJ
;
資訊工程學系
;
Department of Computer Science
In this paper, we use the renewal theory to develop a Poisson random number algorithm without restart. A parallel Poisson random number generator is designed based on this algorithm and prefix computation. This generator iteratively produces m Poisson random numbers with mean mu in average time complexity O([m mu/n]f(n, p)) on EREW PRAM, where f(n,p) is the time for computing an n-element parallel prefix on p processors in each iteration, assuming that parallel uniform random numbers can be generated at the rate of one number per unit time per processor. If n is selected near m mu, it achieves linear speedup when p is small and the average time complexity is O(log(m mu)) when p is O(m mu).
Adaptive asymptotic Bayesian equalization using a signal space partitioning technique
(2004-05-01)
Chen, RJ
;
Wu, WR
;
電信工程研究所
;
Institute of Communications Engineering
The Bayesian solution is known to be optimal for symbol-by-symbol equalizers; however, its computational complexity is usually very high. The signal space partitioning technique has been proposed to reduce complexity. It was shown that the decision boundary of the equalizer consists of a set of hyperplanes. The disadvantage of existing approaches is that the number of hyperplanes cannot be controlled. In addition, a state-search process, that is not efficient for time-varying channels, is required to find these hyperplanes. In this paper, we propose a new algorithm to remedy these problems. We propose an approximate Bayesian criterion that allows the number of hyperplanes to be arbitrarily set. As a consequence, a tradeoff can be made between performance and computational complexity. In many cases, the resulting performance loss is small, whereas the computational complexity reduction can be large. The proposed equalizer consists of a set of parallel linear discriminant functions and a maximum operation. An adaptive method using stochastic gradient descent has been developed to identify the functions. The proposed algorithm is thus inherently applicable to time-varying channels. The computational complexity of this adaptive algorithm is low and suitable for real-world implementation.
Adaptive channel equalization using approximate Bayesian criterion
(2002)
Chen, RJ
;
Wu, WR
;
電信工程研究所
;
Institute of Communications Engineering
The Bayesian solution is known to be optimal for the symbol-by-symbol type of equalizer. However, the computational complexity for the Bayesian equalizer is usually very high. Signal space partitioning technique has been proposed for complexity reduction. It was shown the decision boundary of the equalizer consists of a set of hyperplanes. The disadvantage of the existing approaches is that the number of hyperplane cannot be controlled. Also, to find these hyperplanes, it requires a state searching process which is not efficient for time-varying channels. In this paper, we propose a new algorithm to remedy this problem. We propose an approximate Bayesian criterion such that the number of hyperplanes can be arbitrarily set. As a result, we can trade between performance and computational complexity. In many cases, we can make the performance loss being small while the computational complexity reduction is huge. The resultant equalizer is composed of a set of parallel linear discriminant functions and a maximum operation. An adaptive method using stochastic gradient descent is developed to identify the functions. The proposed algorithm is then inherently applicable to time-varying channels. Also, the computational complexity is low and suitable for real-world implementation.
An efficient algorithm for the reliability of consecutive-k-n networks
(2003-01-01)
Chang, JC
;
Chen, RJ
;
Hwang, FK
;
應用數學系
;
資訊工程學系
A consecutive-k-n network is a generalization of the well-known consecutive-k-out-of-n system, and has many practical applications. This network consists of n + 2 nodes (node 0, the source, nodes 1, 2,..., n, and node n + 1, the target) and directed links from node i to node j (0 less than or equal to i < j less than or equal to n + 1, j - i less than or equal to k). Because all nodes except the source and target, and all links are fallible, the network works if and only if there exists a working path from the source to the target. For the k = 2 case, based on identical node reliabilities and some assumptions on link reliabilities, Chen, Hwang and Li (1993) gave a recursive algorithm for the reliability of the consecutive-2-n network. In this paper we give a closed form equation for the reliability of the general consecutive-k-n network by means of a novel Markov chain method. Based on the equation, we propose an algorithm which is more efficient than other published ones for the reliability of the consecutive-k-n network.
Authenticated public-key distribution over WLAN/cellular dual networks
(2005)
Hwu, JS
;
Chen, RJ
;
Lin, YB
;
資訊工程學系
;
Department of Computer Science
Public-key cryptosystems are characterized by the use of two keys, one held privately and the other available publicly. The main concern in a public-key setting is the authenticity of the public key. This authentication problem is typically resolved by the use of verifiable information called certificate, which is issued by a trusted third party and consists of the user name and his public key. The integrated WLAN/cellular networks enable simultaneous access to both cellular network and wireless LAN. This paper proposes a certificate-free public-key distribution scheme over WLAN/cellular dual networks.
Block-switch networks: A cost-effective class of interconnection network
(1997-05-01)
Chiang, WK
;
Chen, RJ
;
資訊工程學系
;
Department of Computer Science
A new interconnection scheme is proposed for hierarchically constructing massively parallel systems, called the Block-Switch Network (BSN). Presented here is method of connecting together a number of identical basic atoms level by level, a basic atom being an arbitrary connected graph. A BSN is characterized by (G, m), where G represents the basic atom and m denotes the number of levels in hierarchical expansion. A particular choice for G yields a family of hierarchical networks. The topological properties of the BSN for the general case are investigated, and then the results gained from applying BSN to different basic atoms are also discussed. The BSN enables us to construct new families of graphs more feasible and cost-effective. It also deserves mentioning that a shortest-path routing algorithm for the BSN is derived by reducing the routing problem to the K-best perfect matching problem. In particular, we implement fundamental parallel algorithms (descend/ascend) on the BSN(Q(n), m) where Q(n) denotes an n-cube, and demonstrate that the performance on the BSN(Q(n),m) is very close to that of the comparable hypercube.
Block-switch networks: A cost-effective class of interconnection network
(1997-05-01)
Chiang, WK
;
Chen, RJ
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
A new interconnection scheme is proposed for hierarchically constructing massively parallel systems, called the Block-Switch Network (BSN). Presented here is method of connecting together a number of identical basic atoms level by level, a basic atom being an arbitrary connected graph. A BSN is characterized by (G, m), where G represents the basic atom and m denotes the number of levels in hierarchical expansion. A particular choice for G yields a family of hierarchical networks. The topological properties of the BSN for the general case are investigated, and then the results gained from applying BSN to different basic atoms are also discussed. The BSN enables us to construct new families of graphs more feasible and cost-effective. It also deserves mentioning that a shortest-path routing algorithm for the BSN is derived by reducing the routing problem to the K-best perfect matching problem. In particular, we implement fundamental parallel algorithms (descend/ascend) on the BSN(Q(n), m) where Q(n) denotes an n-cube, and demonstrate that the performance on the BSN(Q(n),m) is very close to that of the comparable hypercube.
Distance-preserving mappings from binary vectors to permutations
(2003-04-01)
Chang, JC
;
Chen, RJ
;
Klove, T
;
Tsai, SC
;
資訊工程學系
Mappings of the set of binary vectors of a fixed length to the set of permutations of the same length are useful for the construction of permutation codes. In this correspondence, several explicit constructions of such mappings preserving or increasing the Hamming distance are given. Some applications are given to illustrate the usefulness (if the construction. In particular, a new lower bound on the maximal size of permutation arrays (PAs) is given.
Efficient neural equalization using multiple nonlinear discrimination functions
(2002)
Chen, RJ
;
Wu, WR
;
電信工程研究所
;
Institute of Communications Engineering
Conventional neural equalizers treat equalization as an estimation problem. One drawback is that the number of required hidden nodes is large and this results in the high computational complexity and long training period problems. In this paper, we propose a new approach to alleviate this problem. While treating equalization as a classification problem, we divide the received signal space into 2(N) classes (N > 1) for a binary transmitted symbol and apply the discrimination function approach to perform classification. The discrimination functions, which are nonlinear, is realized using a neural network. We also propose a new discriminative learning criterion for the minimum error classification. Simulations show that our approach can greatly reduce the number of hidden nodes leading to shorter training period and lower computational complexity. We can even obtain satisfactory performance without any hidden layers. This yields a very simple equalization structure and is suitable for real-world implementation.
Embedding cycles in IEH graphs
(1997-10-14)
Chang, HY
;
Chen, RJ
;
資訊工程學系
;
Department of Computer Science
We embed cycles into IEH graphs. First, IEH graphs are proved to be Hamiltonian except when they are of size 2(n) -1 for all n greater than or equal to 2. Next, we show that for an IEH graph of size N, an arbitrary cycle of even length N-e where 3 < N-e < N is found. We also find an arbitrary cycle of odd length N-o where 2 < N-o < N if and only if a node of this graph has at least one forward 2-Inter-Cube (IC) edges. These results help describe the whole cycle structure in IEH graphs. (C) 1997 Elsevier Science B.V.
Embedding cycles in IEH graphs
(1997-10-14)
Chang, HY
;
Chen, RJ
;
資訊工程學系
;
Department of Computer Science
We embed cycles into IEH graphs. First, IEH graphs are proved to be Hamiltonian except when they are of size 2(n) -1 for all n greater than or equal to 2. Next, we show that for an IEH graph of size N, an arbitrary cycle of even length N-e where 3 < N-e < N is found. We also find an arbitrary cycle of odd length N-o where 2 < N-o < N if and only if a node of this graph has at least one forward 2-Inter-Cube (IC) edges. These results help describe the whole cycle structure in IEH graphs. (C) 1997 Elsevier Science B.V.
Graph embedding aspect of IEH graphs
(2001-01-01)
Chang, HY
;
Chen, RJ
;
資訊工程學系
;
Department of Computer Science
In order to overcome the drawback of the hypercube that the number of nodes is limited to a power of two, the incrementally extensible hypercube (IEH) graph is derived for an arbitrary number of nodes [12]. In this paper, we first prove that the incomplete hypercube (IH) is a spanning subgraph of IEH. Next. we present a new method to construct an IEH From an IH. From the aspect of graph embedding, we determine the minimum size of the IEH that contains a complete binary tree. WI: then embed a torus (with a side length as power of two) into an IEH with dilation 1 and expansion 1.
Incrementally extensible folded hypercube graphs
(2000-03-01)
Chang, HY
;
Chen, RJ
;
資訊工程學系
;
Department of Computer Science
In this paper, we propose the incrementally extensible folded hypercube (IEFH) graph as a new class of interconnection networks for an arbitrary number of nodes. We show that this system is optimal fault tolerant and almost regular (i.e., the difference between the maximum and the minimum degree of nodes is at most one). The diameter of this topology is half of that of the incomplete hypercube (IH), the supercube, or the IEH graph. We also devise a simple routing algorithm for the IEFH graph. Finally, we embed cycles and complete binary trees into this graph optimally.
Incrementally extensible folded hypercube graphs
(1998)
Chang, HY
;
Chen, RJ
;
資訊工程學系
;
Department of Computer Science
In this paper,ce propose the incrementally extensible folded hypercube (IEFH) graph as a new class of interconnection networks. for arbitrary number of nodes. We show this system is optimal fault tolerant and almost regular (i.e., the difference between the maximum and the minimum degree of nodes is at most one). The diameter of this topology is half of that of the incomplete hypercube (IH), the supercube, or the IEH graph. also devise a simple routing algorithm for the IEFH graph. Further we embed cycles and complete binary, trees into this graph optimally.
On the arrangement graph
(1998-05-29)
Chiang, WK
;
Chen, RJ
;
資訊工程學系
;
Department of Computer Science
The arrangement graph was proposed as a generalization of the star graph topology. In this paper we investigate the topological properties of the (n, k)-arrangement graph A(n.k). It has been shown that the (n, n - 2)-arrangement graph A(n,n-2) is isomorphic to the n-alternating group graph AG,. In addition, the exact value of average distance of A(n,k) has been derived. (C) 1998 Published by Elsevier Science B.V. All rights reserved.
Performance analysis for dual band PCS networks
(2000-02-01)
Lin, YB
;
Lai, WR
;
Chen, RJ
;
資訊工程學系
;
Department of Computer Science
In a dual band personal communications services (PCS) network, heavy traffic areas are covered by microcells which overlay macrocells. In such a network, microcells and macrocells utilize different frequency bands. We propose an analytic model to study the performance of a dual band PCS architecture. Our model assumes that a PCS subscriber has a general residence time distribution in a microcell and the macrocell residence time distribution is derived from the microcell residence time distribution. An iterative algorithm is used to compute the overflow traffic from a microcell to its overlaid macrocell. Then, the call incompletion probability is computed by a macrocell model based on the overflow traffic. Our study indicates that the variance of the microcell residence time distribution and the number of microcells covered by a macrocell have significant effects on the call incompletion probability.
Pollaezek-Khinchin formula for the M/G/1 queue in discrete time with vacations
(1997-07-01)
Chan, WC
;
Lu, TC
;
Chen, RJ
;
資訊工程學系
;
Department of Computer Science
The continuous-lime M/G/1 queue with vacations has been studied by many researchers. In the paper the authors report on an investigation of the discrete-time M/G/1 queue using Little's formula and conditional expectation. This direct approach can also be adopted to study the continuous-time case.