Signal interpolation and decimation exploiting filter symmetry

Details Signal interpolation and decimation exploiting filter symmetry Signal interpolation and decimation exploiting filter symmetry

1999-04-01

2001-05-01

Ngo, Chuong Dinh (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06226662

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 and 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 in 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 sub-filters of a weight filter is recognized and exploited to reduce the complexity of an interpolator or a decimator and to simpliiy derivation of resulting discrete samples. In particular, a weight filter matrix which includes L=(N−1)M+K weights is divided into two sub-filters, the first having L1=NK weights and the second having L2=(N−1)(M−K). In the case of interpolators, N source samples are applied to the first weight sub-filter to produce K interpolated signals and N−1 source samples are applied to the second weight sub-filter to produce M−K interpolated signals. In the case of decimators, K source samples are applied to the first weight sub-filter to produce N decimated sample components and M−K source samples are applied to the second weight sub-filter to produce N−1 decimated sample components. If the weight filter matrix is centrosymmetric, both sub-filters are also centrosymmetric. Symmetry in the weights of each sub-filter is recognized and exploited.
Within each sub-filter, additive complexity is reduced when 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

Affiliated with

Also associated with

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2470216