Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-02-23
2004-04-06
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S319000
Reexamination Certificate
active
06718354
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to signal processing in a computer system and, in particular, to a particularly efficient mechanism for interpolating and decimating discrete samples of an analog signal.
BACKGROUND OF THE INVENTION
Signal interpolation and signal decimation are forms of signal processing which require substantial resource in terms of computer resources and/or circuitry. Signal interpolation and decimation involve discrete samples of an analog signal generally taken at a specific frequency. Signal interpolation produces synthesized discrete signals of the analog signal at a greater frequency. For example, discrete samples of an analog audio signal taken at a frequency of 20 MHz can be interpolated by a 1-to-2 signal interpolator to produce synthesized discrete samples of the analog audio signal at 40 MHz. Signal decimation produces synthesized discrete signals of the analog signal at a lesser frequency.
Signal interpolators and decimators are used to process discrete samples of various types of analog signals to produce discrete samples of the analog signal at various frequencies. For example, signal interpolators and decimators can process discrete samples of an analog seismic signal recorded using a vibration source and one or more geophones in a conventional manner. Alternatively, signal interpolators and decimators can process discrete samples of an analog light signal, i.e., pixels of a color graphical image, recorded by a video camera. Furthermore, signal interpolators and decimators can process discrete samples of an analog audio recording. The discrete samples are typically taken from a source analog signal using an analog-to-digital converter, which converts a particular value of the analog signal at a particular time to a digital number which can be stored in the memory of a computer.
Signal interpolation acid decimation typically requires significant amounts of processing resources due in part to the complexity of filters used in interpolation and decimation and due in part to the substantial number of discrete samples processed. A filter is generally a number of weights which are applied to each of a number of discrete samples. The weights are generally referred to as a filter since the weights are applied to various collections of discrete samples. For example, a filter which has twenty-four weights is generally applied, first, to the first through twenty-fourth discrete samples; second, to the second through twenty-fifth discrete samples; third, to the third through twenty-sixth samples; and so on. In the case of a signal interpolator which has twenty-four weights, twenty-four multiplication operations and twenty-three addition operations are required to produce a synthesized discrete sample. Similarly, in the case of a signal decimator which has twenty-four weights, twenty-four multiplication operations and twenty-three addition operations are required to process an original discrete sample of the analog signal.
Signals which are interpolated or decimated typically include substantial numbers of discrete samples. For example, seismic data can involve scores of lines of seismic data, each line representing a path along the surface of the earth and each line including a thousand seismic traces or more. A seismic trace can tin turn include thousands of discrete samples of an analog seismic signal measured at a specific point on the surface of the earth. Therefore, a seismic signal can easily include scores of millions of discrete samples. In another example, it is common today for graphical images to have one-thousand or more columns and one-thousand or more rows of picture elements, i.e., pixels, each of which is a discrete sample of a video signal. Such a video signal can be recorded using a video camera, an optical scanner, or can be generated by a computer to represent physical objects defined in part through physical manipulation of computer input devices by a user. Thus, it is common for a graphical image to include a million or more discrete samples of a video image. In addition, motion video signals can include thousands of frames, each of which can include a million or more discrete samples Accordingly, interpolation or decimation of such seismic or video signals involves processing of millions of signals. Efficiency in a signal interpolator or decimator is therefore highly desirable to reduce the amount of time and resources required to process such signals.
In addition, it is frequently desirable to interpolate or decimate signals very rapidly. For example, a compact disc player typically reads discrete samples of an analog audio signal at a rate of more than 40 million discrete samples per second. To enhance the sound quality of an analog audio signal reproduced from the discrete samples, additional discrete samples are interpolated from the discrete samples retrieved from the compact disc. Such an interpolator must generally process the discrete samples at a rate which is at least the rate at which the discrete samples are retrieved, i.e., at least 40 million discrete samples per second.
Because of the significant processing resources required for such signal interpolation and decimation, a need persists in the industry for ever increasing efficiency in signal interpolators and decimators.
SUMMARY OF THE INVENTION
In accordance with the present invention, symmetry in a filter is used to reduce the complexity of an interpolator or a decimator and to simplify derivation of resulting discrete samples. In particular, an inverse relationship between weights applied to two samples is recognized and exploited. An inverse relationship is recognized when (i) a first weight is associated with a first of the samples and a second weight is associated with a second of the samples in the derivation of a first resulting sample, and (ii) a weight which is equivalent to the first weight is associated with the second sample and a weight which is equivalent to the second weight is associated with the first sample in a derivation of a second resulting sample. The inverse relationship is exploited by forming two composite weights of the first and second weights and weighting composite sample signals with the composite weights. A first of the composite weights has a value which is one-half of the sum of the values of the first and second weights. A second of the composite weights has a value which is one-half of the difference of the values of the first and second weights. The composite weights can be used repeatedly for each subsequent interpolation or decimation and are therefore calculated only once for processing many samples according to the same filter. The two composite samples have values which are, respectively, (i) the sum of the values of the first and second samples and (ii) the difference of the values of the first and second samples. Since only two composite weights are involved, two multipliers are required rather than four in which the first and second samples are weighted by the first and second weights, respectively, and by the second and first weights, respectively. The number of required adders is also reduced significantly as described more completely below.
Further in accordance with the present invention, symmetry in weights applied to a single sample is recognized and exploited. For example, if two or more equivalent weights of a filter are applied to the same sample, one of the equivalent weights is applied to the sample once and the resulting weighted signal is used repeatedly rather than weighting the sample by each of the equivalent weights.
Further in accordance with the present invention, symmetry of weights applied to samples in producing a single resulting sample is recognized and exploited. For example, if equivalent weights are applied to two samples and the weighted samples are combined in producing a resulting sample, one of the equivalent weights is applied to the sum of the two samples. As a result, only one of the equivalent weights is applied to reduce the multiplicative complexity of the interpola
Kivlin B. Noäl
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Ngo Chuong Dinh
LandOfFree
Signal interpolation and decimation exploiting filter symmetry does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Signal interpolation and decimation exploiting filter symmetry, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Signal interpolation and decimation exploiting filter symmetry will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3235661