Type of Document Dissertation Author Park, Jae H URN etd-122099-102925 Title Chebyshev Approximation of Discrete polynomials and Splines Degree PhD Department Electrical and Computer Engineering Advisory Committee

Advisor Name Title Ferrari, Leonard A. Committee Chair Abbott, A. Lynn Committee Member Athanas, Peter M. Committee Member Kriz, Ronald D. Committee Member VanLandingham, Hugh F. Committee Member Keywords

- FIR Filter
- Computer Graphics
- Discrete Spline
- Discrete Polynomial
- Chebyshev Approximation
Date of Defense 1999-11-19 Availability unrestricted AbstractThe recent development of the impulse/summation approach for efficient B-spline computation in the discrete domain should increase the use of B-splines in many applications. Because we show here how the impulse/summation approach can also be used for constructing polynomials, the approach with a search table approach for the inverse square root operation allows an efficient shading algorithm for rendering an image in a computer graphics system. The approach reduces the number of multiplies and makes it possible for the entire rendering process to be implemented using an integer processor.In many applications, Chebyshev approximation with polynomials and splines is useful in representing a stream of data or a function. Because the impulse/summation approach is developed for discrete systems, some aspects of traditional continuous approximation are not applicable. For example, the lack of the continuity concept in the discrete domain affects the definition of the local extrema of a function. Thus, the method of finding the extrema must be changed. Both forward differences and backward differences must be checked to find extrema instead of using the first derivative in the continuous domain approximation. Polynomial Chebyshev approximation in the discrete domain, just as in the continuous domain, forms a Chebyshev system. Therefore, the Chebyshev approximation process always produces a unique best approximation. Because of the non-linearity of free knot polynomial spline systems, there may be more than one best solution and the convexity of the solution space cannot be guaranteed. Thus, a Remez Exchange Algorithm may not produce an optimal approximation. However, we show that the discrete polynomial splines approximate a function using a smaller number of parameters (for a similar minimax error) than the discrete polynomials do. Also, the discrete polynomial spline requires much less computation and hardware than the discrete polynomial for curve generation when we use the impulse/summation approach. This is demonstrated using two approximated FIR filter implementations.

Files

Filename Size Approximate Download Time (Hours:Minutes:Seconds)

28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access etd.PDF796.64 Kb 00:03:41 00:01:53 00:01:39 00:00:49 00:00:04

Browse All Available ETDs by
( Author |
Department )

If you have questions or technical problems, please Contact DLA.