Browsing by Author "JaJa, Joseph F."
Now showing 1 - 20 of 21
Results Per Page
Sort Options
Item Efficient Techniques for Range Search Queries on Earth Science Data(2002-02-25) Shi, Qingmin; JaJa, Joseph F.Also UMIACS-TR-2002-19Item Enhancing LZW Coding Using a Variable-Length Binary Encoding(1995) Acharya, Tinku; JaJa, Joseph F.; ISRWe present here a methodology to enhance the LZW coding for text compression using a variable-length binary encoding scheme. The basic principle of this encoding is based on allocating a set of prefix codes to a set of integers growing dynamically. The prefix property enables unique decoding of a string of elements from this set. We presented the experimental results to show the effectiveness of this variable-length binary encoding scheme.Item A High-Level Interactive System for Designing VLSI Signal Processors.(1985) Owens, R.M.; JaJa, Joseph F.; ISRThis paper describes a high-level interactive system that can be used to generate VLSI designs for various operations in signal processing such as filtering, convolution and computing the discrete Fourier transform. The overall process is fully automated and requires that the user specifies only a few parameters such as operation, precision, size and architecture type. The built-in architectures are new digit-on-line bit-serial architectures that are based on recently derived fast algorithms for the above operations. The basic elements are compact and have a very small gate delay. We feel that our system will offer a flexible and easy to use tool that can produce practical designs which are easy to test, efficient and fast.Item A New Approach for Compiling Boolean Functions.(1985) JaJa, Joseph F.; Wu, S.M.; ISRWe propose a new approach for laying out Boolean functions which is based on extracting the symmetries of a given set of functions and applying optimization procedures especially tailored to exploit these symmetries. This paper establishes a rigorous foundation for this approach and shows that it will outperform existing methods for many classes of the functions. The different components of a newly developed system, SYMBL, will be briefly described.Item A New Approach to Realize Partially Symmetric Functions.(1986) JaJa, Joseph F.; Wu, S.M.; ISRIn this paper, we consider the class of partially symmetric functions and outline a method to realize them. Each such function can be expressed as a sum of totally symmetric functions such that a circuit can be designed whose complexity depends on the size of such symmetric cover. We compare the sizes of symmetric and sum-of-product covers and show that the symmetric cover will be substantially smaller for this class of functions. We also establish bounds on the area required to realize these circuits in a reasonable layout model of VLSI. Our results show that these layouts will be considerably smaller than the corresponding PLA's for the partially symmetric functions.Item On Routing Two-Terminal Nets in the Presence of Obstacles.(1987) JaJa, Joseph F.; Wu, S.A.; ISRWe consider the problem of routing k two-terminal nets in the presence of obstacles in two models: the standard two-layer model and the knock-knee model. Determining routability is known to be NP-complete for arbitrary k. Our main results are polynomial time algorithms to determine whether the given nets are routable in either model for any fixed k. We introduce a technique that reduces the general problem into finding edge-disjoint paths in a graph whose size is proportional to the size of the obstacles. Two optimization criteria are considered: the total length of the wires and the number of vias used.Item Optimal Architectures for Multidimensional Transforms.(1988) Chakrabarti, Chaitali; JaJa, Joseph F.; ISRMultidimensional transforms have widespread applications in computer vision, pattern analysis and image processing. The only existing optimal architecture for computing multidimensional DFT on data of size n = Nd requires very large rotator units of area O(n^2) and pipeline-time O(log n). In this paper we propose a family of optimal architectures with areatime trade-offs for computing multidimensional transforms. The large rotator unit is replaced by a combination of a small rotator unit, a transpose unit and a block rotator unit. The combination has an area of O(N^(d+2a)) and a pipeline time of O(N^(d/2-a)log n), for 0 < a < d/2. We apply this scheme to design optimal architectures for two-dimensional DFT, DHT and DCT. The computation is made efficient by mapping each of the one-dimensional transforms involved into two dimensions.Item Optimal Systolic Designs for the Computation of the Discrete Hartley and the Discrete Cosine Transforms.(1988) Chakrabarti, Chaitali; JaJa, Joseph F.; ISRIn this paper, we propose new algorithms for computing the Discrete Hartley and the Discrete Cosine Transform. The algorithms are based on iterative applications of the mod)fied small n algorithms of DFT. The one dimensional transforms are mapped into two dimensions first and then implemented on two dimensional systolic arrays. Pipelined bit serial architectures operating on left to right LSB to MSB binary arithmetic is the basis of the hardware design. Different hardware schemes for implementing these transforms are studied. We show that our schemes achieve a substantial speed-up over existing schemes.Item Optimal Unified Architectures for the Real-Time Computation of Time-Recursive Discrete Sinusoidal Transforms(1992) Liu, K.J. Ray; Chiu, Ching-Te; Kolagotla, Ravi K.; JaJa, Joseph F.; ISRAn optimal unified architecture that can efficiently compute the Discrete Cosine, Sine, Hartley, Fourier, Lapped Orthogonal, and the Complex Lapped transforms for a continuous input data stream is proposed. This structure uses only half as many multipliers as the previous best known scheme [1]. This architecture is regular, modular, and has only local interconnections in both the data and control paths. There is no limitation on the transform size N and only 2N - 2 multipliers are needed for the DCT. The throughput of this scheme is one input sample per clock cycle. We provide a theoretical justification by showing that any discrete transform whose basis functions satisfy the Fundamental Recurrence Formula has a second-order autoregressive structure in its filter realization. We also demonstrate that dual generation transform pairs share the same autoregressive structure. We extend these time-recursive concepts to multi-dimensional transforms. The resulting multi-dimensional structure are fully- pipelined and consist of only d 1-D transform arrays and shift registers, where d is the dimension.Item Optimal Unified Architectures for the Real-Time Computation of Time-Recursive Discrete Sinusoidal Transforms(1993) Liu, K.J. Ray; Chiu, Ching-Te; Kolagotla, Ravi K.; JaJa, Joseph F.; ISRAn optimal unified architecture that can efficiently compute the Discrete Cosine, Sine, Hartley, Fourier, Lapped Orthogonal, and Complex Lapped transforms for a continuous input data stream is proposed. This structure uses only half as many multipliers as the previous best known scheme [1]. The proposed architecture is regular, modular, and has only local interconnections in both data and control paths. There is no limitation on the transform size N and only 2N - 2 multipliers are needed for the DCT. The throughput of this scheme is one input sample per clock cycle. We provide a theoretical justification by showing that any discrete transform whose basis functions satisfy the Fundamental recurrence Formula has a second-order autoregressive structure in its filter realization. We also demonstrate that dual generation transform pairs share the same autoregressive structure. We extend these time-recursive concepts to multi- dimensional transforms. The resulting d-dimensional structures are fully- pipelined and consist of only d 1-D transform arrays and shift registers.Item Parallel Algorithms for Channel Routing in the KnockKnee Model.(1988) Chang, Shin-Chong; JaJa, Joseph F.; ISRWe consider the channel routing problem of a set of two-terminal nets in the knockknee model. The known strategy to handle this problem seems to beinherently sequential. We develop a new approach to route all the nets within d tracks, where d is the density, such that the corresponding layout can be realized with three layers. Both the routing and layer assignment algorithms can be implemented on the CREW-PRAM model in O(log n) time with O(n) processors, where n is the number of nets.Item Parallel Algorithms for Planar Graph Isomorphism and Related Problems.(1986) JaJa, Joseph F.; Kosaraju, S. Rao; ISRWe present new efficient parallel algorithms for planar graph isomorphism and several related problems. Our main parallel model is the SQRT n x SQRT n mesh of processors, where n is the length of the input. Our results include O(SQRT n) time algorithms for finding a good separating cycle and the triconnected components of a planar graph, and for solving the single function coarsest partitioning problem.Item Parallel Algorithms for River Routing.(1987) Chang, Shin-Chong; JaJa, Joseph F.; ISRWe develop fast parallel algorithms for several river routing problems. These algorithms are efficient in the sense that the number of processors used is O(n), where n is the size of the input. Two parallel models of computation are considered: the CREW PRAM model and the two-dimensional mesh of processors model. Our algorithms run in time O(log n) or O(log^2 n) on the first model and in time O(SQRT n) on the second model. Optimal algorithms are developed for several subproblems that are interesting on their own. One such subproblem is to determine the contours of the union of sets of contours within a rectilinear polygon.Item Parallel Algorithms for VLSI Layout.(1989) JaJa, Joseph F.; Krishnamurthy, Sridhar; ISREfficient automatic layout tools are clearly essential for designing complex VLSI systems. Recent efforts have been directed toward developing parallel algorithms to handle the different subproblems involved in the layout phase. Some of these algorithms have been shown to offer significant speed-ups over the sequential ones. In this chapter, basic parallel techniques that have been found to be effective for handling problems arising in the layout phase are reviewed. In particular, parallel algorithms for problems arising in paffitioning, placement and routing are discussed. The algorithms used to handle these problems can be classified into two broad categories: iterative or direct. The iterative techniques such as simulated annealing and the Kernighan-Lin algorithm are very effective for partitioning and placment. The direct methods seem to be dominant in routing. These methods and some new methods are discussed in the general context of parallel processing. Efficient algorithms for the shared-memory model and for distributed-memory multiprocessors such as the hypercube are described. In addition, several special-purpose hardware for placement and routing are also outlined and their merits discussed.Item Parallel Algorithms for Wiring Module Pins to Frame Pads.(1988) Chang, Shin-Chong; JaJa, Joseph F.; ISRWe present fast and efficient parallel algorithms for several problems related to wiring a set of pins on a module to a set of pads lying on the boundary of a chip. The one-layer model is used to perform the wiring. Our basic model of parallel processing is the CREW-PRAM model which is characterized by the presence of an unlimited number processors sharing the main memory. Concurrent reads are allowed while concurrent writes are not. All our algorithms use O(n) processors, where n is the input length. Our algorithms have fast implementations on other parallel models such as the mesh or the hypercube.Item Provably Good Parallel Algorithms for Channel Routing of Multi- terminal Nets.(1988) Krishnamurthy, Sridhar; JaJa, Joseph F.; ISRWe consider the channel routing problem of a set of multi- terminal nets in the knockknee model. We develop a new approach to route all the nets within d + ALPHA tracks, where d is the channel density, and 0 < ALPHA < d, such that the corresponding layout can be realized with three layers. Both the routing and the layer assignment algorithms have linear time sequential implementations. In addition both can be implemented on the CREW- PRAM model in O( n/p + log n) time, with p processors, 1 < p < n and n is the size of the input.Item Systolic Architectures for Finite-State Vector Quantization(1991) Kolagotla, Ravi K.; Yu, S-S.; JaJa, Joseph F.; ISRWe present a new systolic architecture for implementing Finite State Vector Quantization in real-time for both speech and image data. This architecture is modular and has a very simple control flow. Only one processor is needed for speech compression. A linear array of processors is used for image compression; the number of processors needed is independent of the size of the image. We also present a simple architecture for converting line- scanned image data into the format required by this systolic architecture. Image data is processed at a rate of 1 pixel per clock cycle. An implementation at 31.5 MHz can quantize 1024 x 1024 pixel images at 30 frames/sec in real-time. We describe a VLSI implementation of these FSTSVQ processors.Item VLSI Architectures and Implementation of Predictive Tree- Searched Vector Quantizers for Real-Time Video Compression(1992) Yu, S-S.; Kolagotla, Ravi K.; JaJa, Joseph F.; ISRWe describe a pipelined systolic architecture for implementing predictive Tree-Searched Vector Quantization (PTSVQ) for real- time image and speech coding applications. This architecture uses identical processors for both the encoding and decoding processes. the overall design is regular and the control is simple. Input data is processed at a rate of 1 pixel per clock cycle, which allows real-time processing of images at video rates. We implemented these processors using 1.2um CMOS technology. Spice simulations indicate correct operation at 40 MHz. Prototype version of these chips fabricated using 2um CMOS technology work at 20 MHz.Item VLSI Architectures Based on the Small N Algorithms.(1985) JaJa, Joseph F.; Owens, R.M.; ISRDigital convolution and the discrete Fourier transform are basic operations whose computational requirements are of great importance in many applications. In this paper, we propose new types of VLSI architectures which are shown to be quite suitable to handle these operations. These architectures will result in fully pipelined bit-serial arrays which require no control units. Some preliminary implementations indicate a substantial speed-up gain over other existing designs.Item VLSI Implementation of a Tree Searched Vector Quantizer(1990) Kolagotla, Ravi K.; Yu, S.S.; JaJa, Joseph F.; ISRThe VLSI design and implementation of a Tree Searched Vector Quantizer is presented. The number of processors needed is equal to the depth of the tree. All processors are identical and data flow between processors is regular. No global control signals are needed. The processors have been fabricated using MOSIS' 2mm N- well process on a 7.9mm x 9.2mm die. Each processor chip contains 25,000 transistors and has 84 pins. The processors have been thoroughly tested at a clock frequency of 10 MHz. These processors will be used in an adaptive image compression system to compress LANDSAT images.