Browsing by Author "LIU, CM"

Now showing 1 - 11 of 11

A NEW ALGORITHM AND ITS VLSI ARCHITECTURE DESIGN FOR CONNECTED COMPONENT LABELING
(1994)
JEAN, SD
;
LIU, CM
;
CHANG, CC
;
CHEN, Z
;
資訊工程學系
A NEW ARRAY ARCHITECTURE FOR PRIME-LENGTH DISCRETE COSINE TRANSFORM
(1993-01-01)
GUO, JI
;
LIU, CM
;
JEN, CW
;
資訊工程學系
;
電子工程學系及電子研究所
A new approach to derive a systolic algorithm for prime-length discrete cosine transform (DCT) is proposed. It makes use of the input/output (I/O) data permutations and the symmetry property of cosine kernels such that the proposed array possesses outstanding performance in hardware cost of the processing elements (PE's), average computation time, and the I/O cost.
A NOVEL CORDIC-BASED ARRAY ARCHITECTURE FOR THE MULTIDIMENSIONAL DISCRETE HARTLEY TRANSFORM
(1995-05-01)
GUO, JI
;
LIU, CM
;
JEN, CW
;
資訊工程學系
;
電控工程研究所
In this paper, a coordinate rotation digital computer (CORDIC)-based array architecture is presented for computing the multidimensional (M-D) discrete Hartley transform (DHT). Since the kernel of the M-D DHT is inseparable, the M-D DHT problems cannot be computed through the 1-D DHT's directly. Bracewell et al. have presented an algorithm for the M-D DHT through the 1-D DHT's. The existing hardware architectures have been designed using this algorithm. However, the postprocessing required in the algorithm leads to high hardware overhead. This paper presents a new algorithm to compute M-D DHT through a special 1-D transform which is derived through considering both the separable computation and the efficient implementation with CORDIC architectures. This algorithm provides a direct way to compute the M-D DHT separably through 1-D transforms with simpler postprocessing than that in Bracewell's approach. Also, the algorithm exploits the symmetry of the triangular functions to reduce the computational complexity. Using this algorithm, we design an array architecture for the M-D DHT. This architecture features a systolic computing style, PE's with a CORDIC structure, low I/O cost, and the encapsulated new M-D DHT algorithm.
A NOVEL VLSI ARRAY DESIGN FOR THE DISCRETE HARTLEY TRANSFORM USING CYCLIC CONVOLUTION
(1994-01-01)
GUO, JI
;
LIU, CM
;
JEN, CW
;
交大名義發表
;
National Chiao Tung University
A PARALLEL ADAPTIVE ALGORITHM FOR MOVING TARGET DETECTION AND ITS VLSI ARRAY REALIZATION
(1992-11-01)
LIU, CM
;
JEN, CW
;
交大名義發表
;
電控工程研究所
;
National Chiao Tung University
The application of an innovations-based detection algorithm (IBDA) in moving target detector (MTD) radars has been shown to be efficient. In this correspondence, an adaptive algorithm for the IBDA is derived. This algorithm behaves well in numerical properties and computational complexity. Also, it possesses high computing parallelism and data locality which lead to the feasibility of VLSI array realization. A systolic array is designed with the iteration time being (2n + 1) and the number of processing elements being [(n2 + 3n)/2], where n is the length of the adaptive filter.
A SINGLE KALMAN FILTERING ALGORITHM FOR MANEUVERING TARGET TRACKING
(1994)
LIU, CM
;
WU, KG
;
SHEU, JH
;
資訊工程學系
;
Department of Computer Science
ALGORITHMS FOR THE CHINESE POSTMAN PROBLEM ON MIXED NETWORKS
(1995-05-01)
PEARN, WL
;
LIU, CM
;
工業工程與管理學系
;
Department of Industrial Engineering and Management
The Chinese postman problem on mixed networks (MCPP), is a practical generalization of the classical Chinese postman problem (CPP), which has many real-world applications. The MCPP has been shown to be NP-complete. Therefore, it is difficult to solve the problem exactly. For this reason, heuristic solution procedures have been proposed to solve the problem approximately. In this paper, we first review two existing solution procedures proposed by Edmonds and Johnson [Math. Progr. 5, 88-124 (1973)], and Frederickson [J. Assoc. Comput. Mach. 26, 538-554 (1979)], then introduce two new algorithms to solve the MCPP near optimally. The proposed new algorithms are tested and compared with the existing solution procedures. Computational results showed that the two new algorithms significantly outperformed the existing solution procedures.
DESIGN OF ALGORITHM-BASED FAULT-TOLERANT VLSI ARRAY PROCESSOR
(1989-11-01)
LIU, CM
;
JEN, CW
;
交大名義發表
;
電控工程研究所
;
National Chiao Tung University
ON THE DESIGN AUTOMATION OF THE MEMORY-BASED VLSI ARCHITECTURES FOR FIR FILTERS
(1993-08-01)
LEE, HR
;
JEN, CW
;
LIU, CM
;
資訊工程學系
;
電子工程學系及電子研究所
The design automation of the memory-based VLSI architectures for FIR filters is investigated. This paper intends to give a thorough discussion about the design space and schemes for this subject. The discussed topics include the conditions leading to efficient memory replacement, the formulation space of FIR filters, the considerations in architecture design, and the methods to evaluate architectures. With the research results of these topics, we present a parameterized memory-based architecture and the hardware-speed evaluation formulae. This architecture is characterized by three parameters into which various memory-based architectures can be generated by substituting different values. The presented formulae are formulated as functions of the three parameters and implementation technology. Using the evaluation formulae and through the parameterized architecture, an area-minimized architecture can be synthesized under a speed specification. Based on these results, we develop an automatic synthesis tool with an illustrating example.
ON THE DESIGN OF VLSI ARRAYS FOR DISCRETE FOURIER-TRANSFORM
(1992-08-01)
LIU, CM
;
JEN, CW
;
資訊工程學系
;
電子工程學系及電子研究所
;
Department of Computer Science
In this paper the design of VLSI arrays for discrete Fourier transform (DFT) is investigated through three topics: (i) algorithm exploitation, derivation and analysis, (ii) array realisation, and (iii) schemes to calculate arbitrarily long length DFT using a reasonable sized array. Four DFT systolic algorithms are examined and compared in terms of computing parallelism and computational complexity. Among the four algorithms, one is newly proposed. The new one exhibits much higher computing parallelism and lower computational complexity than the other three, but is applicable when the DFT length is prime. Based on the four algorithms, seven systolic arrays and seven two-level pipelined systolic arrays are devised. The outstanding features of these arrays are that the number of I/O channels is independent of the DFT length and the time overhead in manipulating consecutive data bundles are eliminated. Two schemes are presented to calculate long-length DFT using arrays with a reasonable number of processing elements. Performance of different algorithms, arrays and schemes is compared and summarised in six tables to serve as the selection criteria for different applications.
THE EFFICIENT MEMORY-BASED VLSI ARRAY DESIGNS FOR DFT AND DCT
(1992-10-01)
GUO, JI
;
LIU, CM
;
JEN, CW
;
資訊工程學系
;
電子工程學系及電子研究所
In this paper, the efficient memory-based VLSI arrays and the accompanied new design approach for the discrete Fourier transform (DFT) and discrete cosine transform (DCT) are presented. The DFT and DCT are formulated as cyclic convolution forms and mapped into linear arrays which characterize small numbers of I/O channels and low I/O bandwidth. Since the multipliers consume much hardware area, the presented designs utilize small ROM's and adders to implement the multiplications, which is based on good data arrangements exploiting the number properties of the transform kernels. Moreover, the ROM size can be reduced effectively by arranging the data in our designs appropriately. Typically, to perform 1-D N-point DFT and DCT, the arrays need N X 2L words of ROM only. Compared to the conventional distributed arithmetic architectures which should require N X 2N words of ROM, much memory can be saved if N is greater than L, which occurs in most DFT applications. To summarize, the presented arrays outperform others in the architectural topology (local and regular connection), computing speeds, hardware complexity, the number of I/O channels, and I/O bandwidth. They take the advantages of both systolic arrays and the memory-based architectures.