1
`
`RS1037
`Rohde & Schwarz Gmbh & Co., KG vs. Tektronix, Inc.
`IPR2018-00643
`
`

`

`US. Patent
`
`Oct. 30, 2001
`
`Sheet 1 0f 6
`
`US 6,310,566 B1
`
`1o
`INTERPOLATION
`051w RK
`
`20
`DELAY
`/ NETWORK
`
`BOOTSTRAP i
`40
`
`FILTER
`;
`
`
`27
`
`OPTIONAL
`COMPENSATION
`
`
`
`
`
`
`SAMPLE RATE
`CONVERTER
`INPUT
`
`
`
`-------------
`
`-————————______________________<—---—.-....____
`
`DIGITAL
`
`FILTER
`
`CONV.
`
`POSITION
`INDEX MSB
`
`
`
`POSITION
`INDEX
`
`FIG. 1
`
`2
`
`

`

`US. Patent
`
`Oct. 30, 2001
`
`SheetZ 0f6
`
`US 6,310,566 B1
`
`IEazofim3u......................0_$5:3.5$253:5528.._
`
`to:n
`
`to;Hmm29:“
`
`
`
`
`
`
`5E5
`
`15$on10Ex#35
`
`_mzomi
`
`fez“
`
`70:"mmEOmfi
`
`3
`
`

`

`US. Patent
`
`Oct. 30, 2001
`
`Sheet 3 0f 6
`
`US 6,310,566 B1
`
`mmm
`
`3:.
`
`h=m_=o
`
`5:8as
`
`mp<mmd¢5<w
`
`gupmm>zoo
`
`Ham;
`
`4
`
`

`

`US. Patent
`
`Oct. 30, 2001
`
`Sheet 4 0f 6
`
`US 6,310,566 B1
`
`mom E53E8m8m
`
`8v.Acan
`
`
`
`wt».53%
`
`
`
`5&8EEm>zoo
`
`vmmmom0%mmmmmmEmNwmowmmumKmEm
`
`IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII'IIIIIIIIIIIIIIIIIII
`
` E
`
`
`
`.....33.9sz
`
`xmoz""382958
`n.so:uHmm:
`
`.._____.——-___.._-——-___________.4
`
`5
`
`
`

`

`US. Patent
`
`Oct. 30, 2001
`
`Sheet 5 0f 6
`
`US 6,310,566 B1
`
`420
`
`425
`
`430
`
`
`
`
`/ WWW 48
`
`
`
`63
`
`1 24
`
`5
`
`399
`
`495
`
`
`
`583
`
`624
`
`700
`
`735
`
`-28
`
`-39
`
`48
`
`-55
`
`m 3
`
`1/32
`
`_25/32 -63
`
`_23/32
`
`
`
`
`
`
`
`
`IIIIIIIIIII|I|I|§
` 768
`
`mmmmmm
`
`
`
`mmmmw
`
`
`mmmmm
`W/Wmmm
`
`
`
`
`V/mmmmmm
`WWWWWW
`
`WWWWWW
`
`WWWWWW
`
`WWWWWW
`
`WMWWWWW
`WMWWW
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`735
`
`700
`
`663
`
`624
`
`583
`
`540
`
`495
`
`448
`
`399
`
`348
`
`295
`
`240
`
`183
`
`124
`
`63
`
`6
`
`

`

`US. Patent
`
`Oct. 30, 2001
`
`Sheet 6 0f 6
`
`US 6,310,566 B1
`
`INTERPOLNHON
`NEWNORK
`
`510
`
`
`
`605
`
`610
`
`615
`
`COMENER
`
`UNEAR
`TRANSFORM
`
`FACTOR
`
`7
`
`

`

`US 6,310,566 B1
`
`1
`DIGITAL DATA SAMPLE RATE
`CONVERSION SYSTEM WITH DELAYED
`INTERPOLATION
`
`This is a non-provisional application of provisional
`application Ser. No. 60/121,198 by D. McNeely, filed Feb.
`24, 1999.
`
`FIELD OF THE INVENTION
`
`This invention is related to the sample rate conversion of
`digital data for data processing applications including Video
`and audio among others.
`BACKGROUND OF THE INVENTION
`
`There are a variety of applications requiring conversion of
`digital data samples occurring at a first data rate to digital
`data samples occurring at a different second data rate. In
`these applications, data sampled at one rate is interpolated to
`provide estimates of data at a different rate or sampling
`phase. Sample rate conversion applications include,
`for
`example, conversion between different Video standards such
`as between High Definition TV (HDTV) data and CCIR601
`standard data and conversion between different Video dis-
`
`play formats such as between interlace and progressive
`display formats. Other applications include, for example,
`multi-media composite image formation and display e.g. for
`Picture-in-Picture (PIP) presentation, and data processing
`for digital data storage such as for CDROM or DVD
`applications and digital demodulation involving digital
`sample rate conversion for establishing frequency, phase or
`symbol
`timing synchronization. The widespread use of
`sample rate conversion in cost sensitive applications means
`that there is a need to optimize configurations for both
`sample rate converters and their interpolator and digital filter
`sub-components.
`Known, classical interpolator configurations have been
`thought to be optimal in terms of maximizing performance
`and minimizing the hardware complexity involved, i.e., the
`numbers of adders, multipliers, registers etc. that are used.
`However, the sample rate converter, interpolator and digital
`filter systems and the methods of their derivation presented
`herein provide improvements over the known filter designs
`in both performance and reduced complexity.
`SUMMARY OF THE INVENTION
`
`A sample rate conversion system converts data of a first
`sample rate to data of a different second sample rate. The
`system uses an interpolator, operating at the first sample rate
`and includes a first
`interpolation network and a delay
`network. The first interpolation network interpolates the first
`sample rate data to provide upsampled interpolated data
`samples according to a first sample spacing. The delay
`network interpolates the upsampled interpolated data to
`provide delayed upsampled interpolated data samples,
`according to a second sample spacing of higher resolution
`than the first sample spacing, and preceding and succeeding
`an original sample position. The system also includes a
`digital filter operating at the second sample rate for filtering
`the higher resolution data samples to provide the second
`sample rate data.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`In the drawing:
`FIG. 1 shows an enhanced performance sample rate
`converter for converting the horizontal line sample rate of
`luminance and chrominance data samples in a Video display
`format conversion application, according to the principles of
`the invention.
`
`2
`FIG. 1A shows an enhanced performance digital filter for
`use as digital filter 40 in the sample rate converter configu-
`ration of FIG. 1, according to the principles of the invention.
`FIG. 2 shows a filter configuration suitable for providing
`the H1(z) and H0(z) outputs of the first interpolation network
`stage bootstrap filter of unit 10 of FIG. 1, according to the
`invention.
`
`FIG. 3 shows a reduced complexity digital filter for use as
`digital filter 40 in the sample rate converter configuration of
`FIG. 1, according to the principles of the invention.
`FIG. 4 shows a table indicating coefficient values and the
`effective filter delay in conjunction with the corresponding
`position index signal for the reduced complexity digital filter
`of unit 40 of FIG. 3.
`
`FIG. 5 shows an arrangement exemplifying extension of
`the interpolation network (unit 10) and delay network (unit
`20) of FIG. 1 to provide enhanced interpolator performance,
`according to the principles of the invention.
`FIG. 6 shows the principal elements of a structural
`factoring process used to derive improved digital filter
`functions, according to the principles of the invention.
`
`DETAILED DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 shows an enhanced performance sample rate
`converter for converting the horizontal line sample rate of
`luminance and chrominance data samples in a Video display
`format conversion application. Although the disclosed con-
`verter is described in the context of a system for processing
`Video signals for display format conversion purposes e.g. to
`upsample a standard definition format of 720x1280 pixel
`resolution to a high definition format of 1080x1920 pixel
`resolution (or Vice versa), it is exemplary only. The con-
`verter and digital filter configurations and inventive prin-
`ciples disclosed may be used for any filtering or sample rate
`converter application including either upsampling or down-
`sampling conversions.
`In overview, the sample rate converter system of FIG. 1
`comprises compensation pre-filter 17, interpolation network
`10, delay network 20 and digital filter 40. Pre-filter 17 is
`optional and used to optimize performance in terms of noise
`rejection outside of the desired passband and gain within the
`desired passband in the high performance system of FIG. 1.
`In contrast, in a reduced complexity sample rate converter
`system (described later in connection with FIG. 3), pre-filter
`17 is omitted.
`
`A sample rate converter converts data at an input sample
`rate to data at a different output sample rate and possesses a
`number of mutually dependent properties. These include, for
`example, gain and phase response characteristics, phase
`delay, group delay, and clock delay. In order to achieve a
`desired sample rate converter performance and to tailor
`converter operation for a particular application, it is neces-
`sary to select an acceptable compromise between these
`properties, both for the converter as a whole and for inter-
`mediate processing stages within the converter. In deriving
`a sample rate converter configuration, individual selected
`properties may be established as either invariant properties
`or as properties to be optimized.
`Important objectives in sample rate converter design are:
`1) maximizing performance including minimizing alias (i.e.
`interference) components in the Pass Band, and 2) minimiz-
`ing complexity (e.g. measured in the number of adders
`required for an implementation). Normally performance and
`complexity are inversely related in sample rate converter
`design. However, by Viewing a sample rate converter system
`as being equivalent to a multi-stage interpolator comprising
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`
`

`

`US 6,310,566 B1
`
`3
`a sequence of cascaded interpolators, an advantageous
`sample rate converter configuration is derived offering
`reduced complexity and improved performance over previ-
`ously deemed optimal arrangements. In such a multi-stage
`interpolator, a first “coarse” interpolator stage converts a
`spatial sampling grid of an input signal to a higher resolution
`spatial sampling grid (a “coarse” up-sample grid) Asecond
`“finer” resolution interpolator stage converts the coarse
`up-sample grid to a spatial sampling grid of desired resolu-
`tion. A conventional implementation of this concept would
`require three clock domains representing the input sample
`rate, an intermediate re-sampled rate and the desired output
`re-sampled rate. The sample rate converter system disclosed
`herein and exemplified in FIG. 1 provides data at the desired
`output sample rate whilst advantageously:
`1. processing data at a reduced number of data rates,
`specifically at two data rates (the input sample rate and the
`desired output sample rate), and
`2. maximizing the proportion of circuitry operating at the
`input sample rate (input sample rate is less than the output
`sample rate for an upsample application and greater than
`the output sample rate for a down-sample application).
`These important benefits are achieved by employing advan-
`tageous sample rate converter architectures that merge and
`integrate the coarse and fine interpolator stages of the
`multi-stage interpolator. Such an advantageous architecture
`is exemplified by the compensation pre-filter 17, interpola-
`tion network 10, delay network 20 and digital filter 40 of
`FIG. 1. In such an improved converter architecture a second
`“finer” resolution interpolator stage is chosen to have a
`reduced number of intermediate delay stages (taps) with a
`larger number of sets of digital filter weighting coefficients
`than is typical for an equivalent conventional converter
`architecture. Note, each digital filter weighting coefficient is
`associated with an intermediate delay stage. The “coarse”
`first stage interpolator is chosen to have a larger number of
`intermediate delay stages (taps) with a lower number of sets
`of digital filter weighting coefficients than is typical for an
`equivalent conventional converter architecture.
`An improved converter architecture using an integrated
`multi-stage interpolator according to invention principles
`includes:
`
`1. A second stage interpolator (exemplified by digital filter
`40 of FIG. 1) of finer resolution than a first stage inter-
`polator (units 10 and 20 of FIG. 1) that is configured to
`isolate its tapped delay line which comprises multiple
`intermediate delay stages.
`2. A generalized tapped delay line (exemplified by interpo-
`lation network 10 in conjunction with delay network 20 of
`FIG. 1) replacing the isolated tapped delay line of the
`second stage interpolator. This generalized tapped delay
`line is clocked at the input sample rate and consists of
`intermediate delay stages (taps) with a larger number of
`sets of digital filter weighting coefficients than is typical
`for an equivalent conventional converter architecture. The
`generalized tapped delay line includes:
`a) a first interpolation network (unit 10 of FIG. 1 com-
`prising a temporal bootstrap filter), for interpolating
`data at a first sample rate to provide upsampled inter-
`polated data samples according to a first sample spac-
`ing and having one input and n outputs,
`b) multiple tapped delay lines (units 22, 24 an d 26 of
`delay network 20 of FIG. 1) comprising a delay net-
`work providing delayed upsampled interpolated data
`samples according to a second sample spacing of
`higher resolution than the first sample spacing. Sets of
`delayed upsampled interpolated data samples encom-
`
`4
`
`pass (i.e. precede and succeed) a corresponding original
`sample position, and
`c) a multiplexer network (units 27, 29, 31 and 33 of delay
`network 20 of FIG. 1) providing multiple
`
`’1
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`spaced delay line outputs (taps) comprising higher resolu-
`tion second sample spacing data surrounding the desired
`output sample time, where T is the period between samples
`of the input sampled rate and n, in the converter architecture
`of FIG. 1, is 2.
`In considering the operation of the sample rate converter
`of FIG. 1 in detail, a pre-filtered compensated input signal is
`provided by unit 17 to units 13 and 15 of interpolation
`network 10. The signal provided by unit 17 is filtered with
`a transfer function selected to optimize overall passband
`performance of the FIG. 1 converter in terms of providing
`noise rejection outside of the passband and to provide an
`optimized (i.e. ideally flat) gain response within the pass-
`band. Units 13 and 15 of network 10 process the data from
`unit 17 and provide upsampled data to delay network 20.
`Specifically, units 13 and 15 interpolate the input data from
`unit 17 with transfer functions H0(z) and H1(z) respectively
`and provide interpolated data outputs to delay network 20.
`Unit 13 (H0(z)) in the embodiment of FIG. 1, merely passes
`the original pre-filtered data from unit 17 to delay network
`20 i.e. H0(z) in the embodiment of FIG. 1 is a delay function.
`Unit 15 (H1(z)) in the embodiment of FIG. 1 interpolates the
`sampled data from unit 17 to provide intervening data
`samples intermediate between the input samples from unit
`17. Therefore, the two outputs provided by units 13 and 15
`together comprise data representative of the pre-filtered
`input data upsampled by a factor of two. In other embodi-
`ments units 13 and 15 provide interpolated data, that is
`upsampled or downsampled by the desired sampling factor,
`to delay network 20 which may employ transfer functions
`that are either the same, or different, as desired.
`The data from unit 13 of interpolation network 10 is
`provided to multiplexer 33 via both delays 24 and 26 and to
`multiplexer 27 via delay 24 and also to multiplexers 29 and
`31. The data from unit 15 of intcrpolation network 10 is
`provided to multiplexers 31 and 33 via delay 22 and to
`multiplexers 27 and 29. In this configuration, units 22, 24
`and 26 of network 20 comprise multiple tapped delay lines
`providing outputs of delayed upsampled interpolated data
`samples of higher resolution than the sample spacing of the
`input data from unit 17. Multiplexers 27, 29, 31 and 33
`multiplex the inputs received from units 10, 22, 24 and 26
`to provide a selected set (selected from between two avail-
`able sets) of upsampled delayed samples to digital filter 40.
`Multiplexers 27, 29, 31 and 33 multiplex between the two
`sets of upsampled delayed inputs from units 10, 22, 24 and
`26 in response to a position representative selection signal
`identifying the upsampled delayed output sample set spa-
`tially encompassing (i.e. straddling) the corresponding posi-
`tion of the converter output sample whose value is currently
`being determined by the converter of FIG. 1. Specifically,
`this selection signal identifies and selects the set of four
`upsampled delayed output samples comprising the two
`upsampled delayed output samples located either side of the
`corresponding output sample being determined by the FIG.
`1 converter system. In the configuration of FIG. 1,
`the
`selection signal input to multiplexers 27, 29, 31 and 33
`comprises the MSB (most significant bit) of a position index
`signal used by filter 40 to spatially interpolate between two
`input samples being processed.
`
`9
`
`

`

`US 6,310,566 B1
`
`5
`The set of four upsampled delayed output samples pro-
`vided by network 20 to digital filter 40 consist of multiple
`
`’1
`
`spaced delay line outputs (taps) comprising higher resolu-
`tion second sample spacing data surrounding the output
`sample time desired (where T is the period between samples
`of the input sample data from unit 17 and n is 2 in the
`architecture of FIG. 1).
`Other architectures with other values of n may be derived
`by replacing an isolated tapped delay line with the advan-
`tageous generalized delay line arrangement in accordance
`with the invention principles. For example, in the arrange-
`ment of FIG. 5 (discussed later), the generalized delay line
`of FIG. 1 is extrapolated to provide n=3. Further, the use of
`the generalized delay line configuration of FIG. 1 facilitates
`the processing of the input sample data at a single data rate.
`Specifically, the configuration of FIG. 1 enables filter 17,
`interpolation network 10 and delay network 20 to process
`input data at the input sample rate. The use of the general-
`ized delay line maximizes the proportion of converter sys-
`tem circuitry operating at the input sample rate and allows
`a concomitant reduction in the quantity of converter cir-
`cuitry that is required to implement the sample rate conver-
`sion function (in comparison to a conventional approach).
`Further, the use of the generalized delay line arrangement
`advantageously enables the processing of data in the con-
`verter of FIG. 1 at two data rates, specifically at the input
`sample rate and at the desired output sample rate.
`The sets of four upsampled delayed output samples pro-
`vided by network 20 to the second stage fine resolution
`interpolator of digital filter 40 are interpolated by filter 40 to
`provide sample data at the desired output sample rate. In
`providing the output sample data at
`the desired output
`sample rate, unit 40 processes the upsampled delayed output
`sample sets from unit 20 together with a spatial position
`index signal used by filter 40 to spatially interpolate between
`two input samples being processed.
`FIG. 1A shows the structure of an exemplary enhanced
`performance digital filter for use as digital filter 40 in the
`sample rate converter configuration of FIG. 1. Filter 40
`(FIG. 1A) advantageously implements a fine resolution
`second stage interpolation function with reduced circuitry
`(i.e. a reduced number of adders). The interpolation function
`performed by filter 40 is derived using an advantageous
`method of mathematically structuring and factoring the
`desired filter function into a minimized logic implementa-
`tion. This advantageous filter function derivation method is
`arrived at from the consideration that a sample rate converter
`system may be viewed as comprising a pre-filter, a sample
`rate converter and a post-filter in a cascade that possesses
`inter-related characteristics. These characteristics include,
`for example, gain and phase response characteristics, phase
`delay, group delay, and clock delay for the converter as a
`whole and for intermediate processing stages within the
`converter.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`The method of mathematically structuring and factoring
`the desired filter function into a mathematical function
`
`60
`
`yielding a minimized logic implementation derives, in part,
`from the realization that advantage may be taken of relaxing
`certain filter characteristics to achieve simplification in
`implementing the filter function. However, such mathemati-
`cal structuring is constrained by the desired performance
`requirements of the filter and the consequent need to main-
`tain particular characteristics invariant during the factoring
`
`6
`process. In the video processing application for which the
`FIG. 1A converter is intended, filter 40 is desired to mini-
`mize alias components in the Passband (ideally to less than
`50 dB) whilst also maintaining low complexity (measured in
`number of adders required for the filter 40 implementation).
`Normally performance and complexity are inverse relation-
`ships in filter design (an interpolator can be viewed as a
`programmable filter). However, both objectives may be met
`by structurally factoring a mathematical interpolation func-
`tion as disclosed herein to yield an optimally minimized
`circuit implementation of a desired filter function that is
`tightly tied to the mathematical structure of the desired filter
`function.
`
`FIG. 6 shows the principal elements of a structural
`factoring process used to derive improved digital filter
`functions. The structural factoring process comprises struc-
`turing a mathematical expression representing a filter func-
`tion into a form that maps into a linear sequence of opera-
`tions that are readily implementable in logic (i.e. adders,
`multipliers and latches). The factoring process of FIG. 6
`comprises determining delay (e.g. achieved using a shift
`register), linear transformation and factor combination pro-
`cesses (steps 605, 610 and 615 respectively). The structural
`factoring steps 605, 610 and 615 are described as follows.
`1. The shift register process 605 comprises representing an
`interpolator’s output in column vector form,
`
`Sk={z’k,k=0 .
`
`.
`
`. M}=transpose([1,z’1, 2’2, .
`
`.
`
`.
`
`, [A4]),
`
`where the interpolator’s output at any one time is a function
`of M+1 contiguous input samples.
`2. The linear transform process 610 comprises representing
`series and parallel connections of a multi-input multi-
`output filter network as both a single matrix, Lik(where i
`is row index (superscript), k is column index (subscript)),
`and products and sums of matrices. It is through decom-
`posing the single matrix Lik into a matrix expression that
`an optimally minimized filter hardware implementation
`(in terms of latches, adders and multipliers) is achieved.
`3. The factor combiner process of step 615 derives the filter
`40 (FIG. 1A) output by calculating a weighted sum of the
`N outputs (“factors”) of the linear transform process of
`step 610. For the converter of FIG. 1A the factor combiner
`is constrained to employ a single parameter u representing
`interpolate spatial position by the row vector,
`
`Ut={u’i,i=0 .
`
`.
`
`. M}=[1,u, uz, .
`
`.
`
`.
`
`, #4)]
`
`Given the conditions that, u=0 corresponds to a delay of
`half way between two input samples, u is within (—0.5,0.5),
`and M is odd, then matrix Lik has the following properties;
`odd rows are coefficient symmetric and even rows are
`coefficient anti-symmetric. An Lik matrix for a four tap filter
`(M=3) comprising filter 40 of FIG. 1A that provides a
`minimum alias solution for 0 to 0.6 of the Nyquist folding
`frequency, is closely approximated with the integer matrix:
`
`6
`53
`53
`6
`59 —59 —23
`23
`31 —31 —31
`31
`
`65
`
`D _
`k‘
`
`16 —43
`
`43 —16
`123
`
`'
`
`10
`
`10
`
`

`

`7
`
`8
`
`US 6,310,566 B1
`
`The number of adders (# Lik) required to implement each
`constant are
`
`2 2 l
`l
`2 2 2 2
`l
`l
`l
`l
`O
`l
`l
`O
`
`#L; =
`
`, Plus 12 adders for accumulation
`
`A direct implementation of this filter would take 32 adders
`but taking advantage of individual row symmetries could
`reduce this to 21 adders. However, by applying the structural
`factoring method and decomposing the single matrix Lik into
`a matrix expression, further minimization in filter hardware
`is achieved. Such structural factoring takes advantage of the
`existence of a factor comprising a sparse matrix in matrix Lik
`that results from matrix row symmetries. A sparse matrix is
`a matrix containing multiple zero value elements. While the
`constants that fill this sparse matrix are dependant upon a
`particular matrix L,
`it
`is the row coefficient symmetry
`imposed upon Lik that ensures that a sparse matrix factor
`with at least half of its entries of zero value exists. Many
`solutions with this form exist for a specific Lik. One of
`minimal implementation complexity is constructed as fol-
`lows. The filter 40 matrix Lik is structurally factored to
`provide:
`
`0
`6
`0
`64
`23
`0123 0
`0
`0 310
`
`01 1
`
`0
`
`Li— 0
`k‘
`
`0 016_01—10
`123
`1—1—11
`1—3
`3 —1
`
`#Li =(O+0+2+2)+2m+(0+1+1+0)+8m=16 adder
`
`(Where # Lik is the number adders required for
`implementation).
`Therefore, structural factoring yields a 50% reduction in the
`number of adders required for this factored implementation
`in comparison to the direct implementation (i.e. 16 adders
`are required vs. 32 adders). Filter 40 of FIG. 1A implements
`this structurally factored solution which represents the func-
`tion:
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`rate (the desired output sampling rate). It is implemented
`with three multipliers (units 43, 46 and 49) and 16 adders
`(units 51—81) and 39 latches as depicted in FIG. 1A. This
`filter function provides improved performance in terms of
`reducing passband alias components (critical for video pro-
`cessing type applications) in comparison with a conven-
`tional function. The improved performance is achieved with
`reduced circuit hardware cost and complexity. The structural
`factoring method is also applicable for optimizing and
`minimizing of other digital filter functions for sample rate
`converter and other uses.
`
`The structurally factored filter function of unit 40 (and
`other filter functions) may be further simplified by taking
`advantage of other row properties. This may be done in the
`function of filter 40, for example, by making use of an
`additional matrix factor and by decomposing matrix Lik into
`the following.
`
`64060
`0123023
`00310
`
`LZ=00016_
`
`123
`
`0110
`
`[1 _1]®1 0 —1
`1—21
`
`010]
`
`
`
`#Lf‘=(0+0+2+2)+2m+(O+O+O+O)+5m=11Adders
`
`(Where # Lik is the number adders required for
`implementation).
`Therefore, further structural factoring yields a 66% reduc-
`tion in the number of adders required for this factored
`implementation in comparison to the direct implementation
`(i.e. 11 adders are required vs. 32 adders).
`FIG. 2 shows a filter configuration suitable for providing
`the H1(z) and H0(z) outputs of the first interpolation network
`stage (bootstrap filter) of units 13 and 15 within unit 10 of
`FIG. 1. As previously mentioned, function H0(z) is merely
`a pass-through identity function (H0(z)=z) whereby input
`pre-filtered data (from unit 17 of FIG. 1) is buffered in unit
`200 of FIG. 2 before being provided to delay network 20
`(FIG. 1). The FIG. 2 interpolator function H1(z) interpolates
`the input sampled data after buffering by unit 200 to provide
`
`H(DC)=1,
`
`H4tap(z)=[l M #2 1431'
`
`0
`
`0
`
`0
`
`1
`3
`2
`a
`0
`01 0
`1
`1
`0
`23
`0
`1 —1
`m 0
`1
`31
`1 —1 —1
`'
`0 — 0
`128
`1 —3
`3 —1
`
`0
`
`0
`
`0
`
`13
`
`ASSEMBLY FUNCTIONS
`
`BASIS FIRs
`
`p e [—5, .5]
`
`(11470.5, 0.5]
`
`intervening data samples intermediate between the input
`samples from unit 17. The H1(z)
`interpolator function,
`Filter 40 advantageously implements this minimized 65 comprising adders (units 204, 206 and 214—232), scalers
`structurally factored function to provide the FIG. 1A sample
`(units 202, 208, 210, 212, 234 and 236) and output stage
`rate converter output whilst processing data at a single data
`250. The H1(z)
`function is shown as
`follows.
`
`11
`
`11
`
`

`

`US 6,310,566 B1
`
`9
`
`2 — 551 +1152 — 2453 + 8054 +
`8055 — 2456 + 1157 — 558 + 25"
`128
`
`H1(z) =
`
`The resultant outputs of the H0(z) and H1(z) functions,
`provided by the FIG. 2 arrangement, comprise interpolated
`data samples upsampled by a factor of two in comparison
`with the input data.
`FIG. 3 is an example of an advantageous reduced com-
`plexity filter (in comparison to the high performance filter of
`unit 40 of FIG. 1A) that may alternatively be used in the
`sample rate converter configuration of unit 40 of FIG. 1. The
`filter of FIG. 3 employs nine adders (units 312, 314, 318,
`334, 340, 349, 374, 380 and 392) and two multipliers (units
`326 and 352) plus a plurality of D-type register delay stages
`and scaling and other stages. (Note, units 320, 342 and 386
`are not counted as adders for circuit purposes as they merely
`add a digital one value and may be implemented without
`additional adder elements). The filter of FIG. 3 is used for
`interpolation and may be used to perform a wide range of
`sample rate conversions. The filter of FIG. 3 does this by
`calculating the closest interpolate value to each value at a
`required output spatial position using a X 32 spatial upsam-
`pling output grid. The filter of FIG. 3 implements the
`following interpolation function.
`
`0
`
`O
`
`3
`
`O
`
`H4zap(z) = [1 M #2]-
`
`|—1
`
`4 —2 —1 I
`
`1Z71
`
`HDCl
`1—1 —11
`ft“ <
`)—
`Z73
`
`The structural factoring method may be applied to this
`function to decompose the single matrix Lik into a matrix
`product expression and obtain further minimization in filter
`hardware. Such structural factoring takes advantage of the
`existence of a factor comprising a sparse matrix in matrix Lik
`that results from matrix row symmetries. Applying the
`structural factoring method to take advantage of row sym-
`metries and sparse matrix factor, the following function is
`derived.
`
`H4,ap<z)=[1p M]-
`
`
`
`10 0
`
`1 41-
`
`0
`
`0
`
`l
`
`0 010
`01 0
`
`]®[10 Ali
`
`1—1
`
`L
`
`O0
`1
`
`_
`3
`
`,H(DC)=1
`
`0
`
`-
`
`0
`l
`,1Z
`7
`
`2
`
`1 adder + 2 adder + 2 adder = 5 adder Linear Transform
`
`This advantageous configuration of the FIG. 3 filter function
`may be implemented with three less adders than the non-
`structurally factored version. This represents a significant
`saving in the required circuit hardware.
`FIG. 4 shows a table indicating coefficient values and
`effective filter delay in conjunction with the corresponding
`position index signal for the reduced complexity digital filter
`of unit 40 of FIG. 3. FIG. 4 lists the coefficient values,
`effective filter delay values and position index values for
`
`10
`each of the 32 spatial sample positions used by the FIG. 3
`interpolation filter in its x32 spatial upsampling output grid.
`The position index data 420 (in the first column of FIG. 4)
`is used by filter 40 to spatially interpolate between two input
`samples being processed. The position index signal 420
`controls the phase of filter 40 on a pixel by pixel basis. It
`does this through multipliers 326 and 352 (via delays
`302—308 of FIG. 3) and by selecting between two sets of
`delayed upsampled interpolated data samples encompassing
`a corresponding original sample position via the multiplex-
`ers of unit 20 (FIG. 3).
`The delay data 425 in the second column of FIG. 4 shows
`the actual effective delay through filter 40. The delay values
`range from 48/32 (FIG. 4 column 425 item 0) to 17/32 (FIG.
`4 column 425 item 31).
`Individual delay values are
`expressed as a fraction of the input sample period and
`consequently range from 1.5 to approximately 0.5 input
`samples in duration. The delay data 425 shows the actual
`effective delay through filter 40 corresponding to each of the
`two sets of delayed upsampled interpolated data samples
`being processed. Selection between the two sets of delayed
`upsampled interpolated data samples being processed and
`the corresponding filter 40 delay is determined by position
`index signal 420. The processing of the first set of delayed
`upsampled interpolated data samples from the multiplexers
`of unit 20 (FIG. 3) involves data items 425—445 presented in
`the first 16 shaded spatial interpolation positions (position
`index 420-items 0—15) of FIG. 4. The processing of the
`second set of delayed upsampled interpolated data samples
`from the unit 20 multiplexers (FIG. 3) involves data items
`425—445 presented in the second 16 non-shaded spatial
`interpolation position (position index 420-items 16—31) of
`FIG. 4.
`The next four columns 430—445 of FIG. 4 show the
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`effective weighting coefficients of the four taps of the
`converter of FIG. 3. The first two of these columns 430 and
`
`435 (1 for no delay, and z'O's for a one half clock delay)
`actually show the values of the gain produced by coefficients
`C0 and C1 of the FIG. 3 interpolation filter. The last two
`columns 440 and 445 (z'l—a one clock delay, and z'l's—a
`one and one half clock delay) show the gains for the last
`coefficient C2 and C3 stages. Note that these are effective
`coefficients and cannot be individually localized in the
`hardware.
`
`FIG. 5 shows an arrangement exemplifying extension of
`the interpolation network (unit 10) and delay network (unit
`20) of FIG. 1 to provide enhanced interpolator performance.
`Specifically, FIG. 5 shows how the generalized delay net-
`work of units 10 and 20 of FIG. 1 may be replaced by
`corresponding interpolation network 510 and delay network
`520 to provide higher resolution interpolation. FIG. 5 also
`shows how virtually any tapped delay line (e.g. delay line
`505) used in any digital filter or sample rate converter
`system, for example, may be replaced by the advantageous
`generalized delay line exemplified by units 10 and 20 of
`FIG. 1 and units 510 and 520 of FIG. 5. Such replacement
`yields improvements including (a) increasing the proportion
`of sample rate converter circuitry operating at the input
`sample rate, and (b) enabling a consequent reduction in the
`number of data rates required by sample rate converter
`system. In the system of FIG. 1, for example, dat