Interpolation in Digital
Modems—Part I: Fundamentals
Floyd M. Gardner,
Abstract— Timing adjustment in a digital modem mast be
performed by interpolation if sampling te not syachroneed to
the data symbols. Tis paper describes the fundamental equation
{or interpolation, proposes a method for control, and outlines the
signal processing characteristics appropriate to an lnterpolater
‘The material combines a review of previously known topics
presentation of new results, and a tutorial exposition of the
subject.
‘eat performance and implementa:
1 Inrropucrion
HIMING in a data receiver must be synchronized to
the symbols of the incoming data signal, In analog-
Implemented modems, synchronization typically is performed
by a feedback loop that adjusts the phase of a local clock, or
by a feedforward arrangement that regenerates a timing wave
from the incoming signal. The loca clock or the timing wave
is used to sample (or strobe) the filtered output of the modem,
‘once per symbol interval, Message data are recovered from
the strobes. Timing of the strobes is adjusted for optimum
‘detection of the symbols
Implementation of the modem by digital techniques (atopic
of intense present activity) introduces sampling ofthe signal
In some citcumstances, the sampling can be synchronized
to the symbol rate of the incoming signal; sce Fig. 1(a)
and (b), Timing in a synchronously sampled modem can be
‘recovered in much the same ways that are familiar from analog
practice
In other circumstances, the sampling cannot be synchronized
‘o the incoming signal. Examples include 1 digital processing
of unsynchronized frequency-multiplexed signals, or 2) noa-
synchronized digital capture and subsequent postprocessing of
«signal, For one reason or another, the simpling clock must
‘emain independent ofthe symbol timing, See Fig. (c) for a
rnonsynchronized-sampling configuration.
How is receiver timing to be adjusted, by digital methods,
hen iis not possible to alter the sampling lock? One answer
is t interpolate among the nonsyachronized samples in such
‘manner as to produce the correct strobe values at the modem
Paget approved by the Ete for Syactisizton an Optical Detection
ofthe TERE Communication Socty Manes reed ese
Toon, eevses May" 2, 191. This work mas. uppre. ener Contac
SUBAEINIIDG by he Eatopean Space Agsny, Nob, The Nhe
‘This pper was presented othe Second rational Wokshp 9 Dig
Slee Pocaning Techiges Applied to Space Comnetion (DSP),
Polcrico a Trin, Tur ay Sep 2235 1090
“he ahr i wih Onder Resch Company, Fla Allo CA 9804
TEE Log Nomber 208082
ae
=a i =} wee FE
ee
ss } aE
outpot—the Same strobe values that would occur if the original
sampling had been synchronized tothe symbols.
Interpolation isa timing-adjustment operation on the signal,
not on a local clock of timing wave. In this respect, it
is radically different from timing adjustment in the better-
known analog modems, Of al the operations in a digitally
implemented modem, interpolation is perhaps the one with
the least resemblance to established analog methods,
Several issues arise as follows.
—What mathematical model of intepolation can be de-
visee?
—How is interpolation to be contrlled?
—What characterises are desirable in an interpolator for
modems?
—Hoow is the interpolator to be implemented?
—What performance can be obtained? How large is the
‘computing burden?
—What conceptual model is appropriate for interpolation?
“These are the matters treated inthis paper and its companion
[1]. The first three issues are addressed here in Part I, and the
last three in Part Il [1]. Attention is concentrated on high
speed methous, defined by a hardware-imposed constraint that
‘no clock frequency can greatly exceed the signal sample rate.
27-on629380500 © 1959 EEE1, Backorounn
Interpolation as a Digital Signal Processing (DSP) opera-
tion has been covered extensively in the literature; excellent
‘examples and further references may be found in [2] ad [3].
By contrast, the role of interpolation in timing adjustment has
nad comparatively meager attention [2, eh 6}, [4 [8]. Infact,
these later references do not speak of “interpolation”, but of
“digital phase shifting” [2 eh 6} and [4], or of “sampling-rate
conversion” [2, ch. 2] and [5].
11 willbe Seen presently thatthe process of timing adjust-
‘meat includes substantially more than interpolation alone and
that “rate conversion” is a more accurate label. Nonetheless,
‘we will apply the term “interpolation” to denote all of the
processes that are involved in adjustment of timing.
‘The term “interpolation” 10 describe the entire timing-
adjustment process appears to have been published frst by
4 group at the Technical University of Aachen (6), [J]. The
term is also used by Bingham [8, p. 167]
In light of the extensive DSP literature on interpolation,
and of the large number of digitally implemented modems
‘that have been bul for voice-fequency telephone
how isi that the literature on digital
sparse?
‘Authors inthe established DSP literature almost invariably
restrict themselves 10 sampling-rate conversion by a rational
factor, which can be modeled a8 a cascade of interpolation
and decimation, each by integer ratios. Thus, the output is
‘synchronized to the inp.
‘But the inherent problem of fully digital timing adjustment
is that the signal sampling isnot synchronized to the symbol
timing; the two rates are incommensurate and the sample times
never coincide exactly with desired strobe times, Recognition
of incommensurability is vital to understanding the timing-
adjustment problem,
Limitations of the DSP literature aside, why didn’t the
timing. adjustment problem arise more clearly in the design
‘of digitally implemented telephone-line modems? The answer
is that it indeed did arise, and was solved by the adaptive
equalizers that play so large a role in those modems. Besides
correcting for transmission dispersion, an equalizer almost
incidentally also corrects the timing, For that reason, timing
adjustment itself does not appear as a widely recognized,
distinc problem in the context of telephone-ine modems.
Digital implementation is now coming to higher speed com-
‘munications links which do not requite adaptive equalization
The need for digital timing adjustment must be faced by itself,
without embedding it inside an equalizer.
timing adjustment is $0
ML, Moose.
A. Timing Loop
Consider the feedback timing recovery of Fig. 2. (Feedfor
‘ward interpolation is aso feasible, but not considered here.) A
‘ime-continuous, PAM signal x(¢) is received. Symbol pulses
in (2) are uniformly spaced at intervals. For simplicity, 2()
is assumed to be a real, bascband signal, but those restrictions
can be removed without difficulty
Assume r(2) to be bandlimited so that it can be sampled
at a rate 1/T, without aliasing. If x(t) is not adequately
bandlimited, aliasing will insoduee distorion that causes
® performance penalty. Interpolation is not an appropriate
technique to be applied to wide-band signals
Samples z(mT,) = 2(m) are taken at uniform intervals
1,. The ratio T/T, is assumed to be irrational, as indeed will
bee true in all practical situations where the symbol timing
i derived ftom 8 source that is independent of the sampling
clock. These signal samples are applied to the interpolator,
Which computes interpolants, designated y(KT;) = y(k) at
intervals T,. We assume that T; = T/K where Kis a small,
integer.
The data filter employs the interpolants to compute the
strobes that are used for data and timing recovery
Inthe sequel, the interval T; between interpola is treated
1s constant, for simplicity of explanation. A practical modem
‘must be able 1 adjust the interval so that the strobes can be
brought into synchronism withthe data symbols ofthe signal;
thus, the interpolation interval cannot be constant
Al elements within the feedback loop contribute 10 the
synchronization process. Timing error is measured by the tm
ing ertor detector and filtered in the loop filter, whose output
Grives the controller. The interpolator obtains instructions for
its computations ftom the controller
‘This paper concentrates on the interpolator and controller
Alone, with litle oF no consideration of the data filter, the
timing ertor detector, or the loop filter. One example of digital
timing-ertor detectors may be found in [9], which also has
references to other examples. An illustrative loop design and
simulation may be found in Part It [1
‘The datafile is shown within the feedback loop, after the
integpolator. That placement is not essential the data Mter
could be outside ofthe loop, prior to the interpolate. A data
filter inside the feedback loop introduces delay, with adverse
influence on loop stability
Past placement may be advantageous when the data filter
is more complicated than the interpolator—a likely situs
tion—and when a relatively high sampling rate is employed for
imterpolation. With postplacement, the data fiter can decimate
its output to the required strobe rate Gust ane or two samples
per symbol) and thereby save on computing burden, If the data
filter is placed before the interpolator, then the sample rate
‘out ofthe dita filter must be maintained high enough to avoid
aliasing. On the other hand, simulation result [1] indicate that
‘quite modest sampling rates provide excellent results, even
Fig. 2. lene of gia timing sveie = Ee are
ee
ort,
with very simple interpolator. Thus, post placement may not
‘often be necessary.
2B. Interpolator Equations
‘To derive a model forthe interpolator, we recapitulate the
fundamental development of Crochiere and Rabine (2, ch. 2].
‘The same basis underlies the adaptive rate convertor in [5].
Refer to Fig. 3, which shows tious, hybrid ana:
loghtigial method ‘of rte conversion. Conve the samples
tora sequence of weighted analog impulses, which are applied
to time-contnuous, analog, iterpolaig fier with impulse
‘response h(t). The time-continuous output of the is
wt) = So a(mjhy(t m4).
O)
‘Observe that y(t)¥(t). There i no attempt, and no need to
recover the original waveform, contrary to mest conventional
interpolation. Since a modem is required to perform filtering
of signals there is no reason why some ofthe fitering cannot
be included in the interpolator.
"Now resample y(t) at time instants t = AT; where 7; is
synchronized with the signal symbols. In general, T/T, is
itrtional; the sampling snd symbol rates are incommensurate
‘The new samples—the interpolants—are represented by
WKD) =D x(n P,)hi(kT — mT).
@
Although the model includes a fictitious DAC and a fictitious
analog filter, the interpolants in (2) can be computed entirely
digitally from knowledge of: 1) the input sequence {(m)}.
2) the impulse response y(t) ofthe interpolating filter, and 3)
the time instants m7, and KT, ofthe input and output samples.
These digitally computed interpolants have identically the
same valves as ifthe analog operation had been performed
‘A more useful format is obtained by rearranging the index>
ing in (2). Recognizing that m isa signal index, define filer
index
i im(e./7,) ~ m °
‘where int[z] means largest integer not exceeding 2. Also,
define a basepoint index
mq = iA,
o
and a fractional interval
ae = KT [Ts — me o
Fig. § Sale time relies
where 0-< jog < 1. Timing relations are ilutated in Fig. 4
Punction arguments in (2) become m = me ~ i and
(AT, ~ mT.) = (0+ sa), and the interpolant is computed
at time £7; = (me + se). Equation (2) can be rewritten as
uk)
ul(oma + 4)
Yall pT + 47}
©
Equation (6) is the foundation of digital interpolation in
modems.
If the interpolating filter has finite impulse response (FIR),
then Jy and Zz are fixed, finite numbers and the digital filter
actually used for computing the interpolants has J = 2—f,+1
most DSP accounts of interpolation assume
,/T, is rational. No such assumption will
bbe made here; real-world symbol rates are almost never
synchronous with independent, fixed-rate sampling, clocks.
‘Assuming a commensurate ratio tends to obscure broader
issues of control and implementation,
‘When Tis incommensurate with T,, the fractional inter
sx will be ieational and will change for each interpolant. If
‘determined to infinite precision, x takes on an infinite number
‘of values, which never repeat exactly. This behavior is contrary
to that observed if T, is assumed very nearly equal to T;—it
sampling is nearly synchronized. Then ix changes only very
slowly; if x i quantized, it might remain constant over many
inerpolations f 7, were commensurate with T, but not equal,
then ju would cyclicly repeat a finite set of values, when the
timing Toop is in equilibrium.
IV. Controt.
Fig. 5 presents the timing loop of Fig. 2 with expanded detail
forthe controller. The interpolator performs the computations
‘of (6). The controller provides the interpolator with infor-
mation needed to perform the computations. Other essential
elements in the loop will not be treated here.
‘An interpolant is computed from (6) using J adjacent
samples z(rm) of the signal and J samples of the impulse
response /r(0) of the interpolating filter The correct set of
signal samples is identified by the basepoint index my and
the correct set of filter samples is identified by the fractional
interval jx. Thus, the contoller of Fig. $ is responsible for
‘determining my and je, and making that information available
to the interpolator.
‘Once me and jg have been identified by the controler, then
‘other elements load the selected signal and impulse-responsesamples into the interpolation filter structure for computations.
‘These loading operations are regarded as part of the filler
implementation; Some options are examined in Part IL [1]
‘The necessary contol can be provided by a number:
Controlled oscillator (NCO). Assume thatthe signal samples
are uniformly clocked through a shift register at rate L/T, and
that the NCO is clocked ata rate synchronized to 1/7.
Provided that the interpolator is never called upon to per=
form upsampling, then the NCO clock period can be Ty. If
upsampling is ever required, then a higher NCO clack rate is
needed. Further discussion will concentrate on NCO clocking.
at rate 1/T, (dowssampling only); modifications needed t0
accommodate upsampling are readily devised once the basic
principles are established
‘The NCO is operated so that its average petiod is 7
Recycling of the NCO register indicates that a new interpolant
is to be computed, using the signal samples currently residing
in the interpolatoe's shift register. Thus, basepoint index is
identified by flagging the correct set of signal samples, rather
than explicitly computing 1s,
A. Euraction of i
Fractional interval jx canbe calelated from the contents of,
the NCO's register upon recycling, as will now be explained.
Designate the NCO register contents computed at the mth
clock ick a8 1(m), and the NCO contol word as Won). Then
the NCO difference equation is
om) = fon = 1) — Won ylmod-t.
(A decrementing NCO is employed because it affords &
‘minor simplification in computation of jy as compared to an
incrementing, NCO.)
Control word W(on) [a positive fraction} is adjusted by the
timing-tecovery loop so that output of the data filter i strobed
st near-optimal timing. Under loop equilibrium conditions,
Wm) will be nearly constant. Contents of the NCO register
(also a positive fraction) will be decremented by an amount
W(m) each T. seconds and the register will undertow each
L/W) clock ticks, on average. Thus, the NCO period is
T; = T,/W(mn) and so
wim) = 2
)
Fig. NCO relations
‘That is to say, Wm) is the synchronizer’s estimate of the
average frequency of interpolation 1/T;, expressed relative
‘o the sampling frequency 1/T,. The control word is an
estimate because itis produced from filtering of multiple, noisy
measurements of timing error.
To see how jx cam be extracted from the NCO, refer to Fig.
6, which is a plot of (Rettious) time-continuous (2) versus
continuous time. Inthe figure, m4 T, isthe time ofthe samp
clock pulse immediately preceding the kth interpolation time
ET, = (14 + 1u)Ts- NCO register contents decrease through
zet0 at ¢ = KT, and the 2er0 crossing (underlow) becomes
Known at the next clock tick at time (my + 1)T.. Register
contents (7g) and (ay +1) are available tthe clock ticks,
From similar triangles in Fig. 6, ican be seen that
mE, mT
ifm) ~ T= ame +)
Which can be solved for sas
rms) nine)
"= Tim-+DFam) ~ Womy
‘An estimate for jx can be obtained hy performing the ind
cated division ofthe two numbers (mx) and WY (ong) that are
both available from the NCO. [Equation (9) isan estimate of
the exact yx because its constituents TV (m4) and n(mme) are
both estimates of the true frequency and phase.)
To avoid division, recognize that 1/W(m) ~ T,/T,; nom-
inal value of this ratio is designated G. Although the exact
‘T/T, is unknown and irrational, the nominal value &o, ex-
pressed to finite precision, can often be an excellent approxi
‘mation to the tue value. Therefore, the fractional interval can
be approximated by
4 = fantom) a0)
Represent the deviation in y from the true ratio of periods
as DE. This deviation causes a uniformly distributed error with
standard deviation A€/(E>VT2) in the ealeuated value ofIf the deviation off i too large, then a first order correction
be = Gonna) [2 — GoW (me ~ 1) ay
reduces the standard deviation in yy to A€?/(EGV72), again
without requiring a division.
‘Timing errors arising from multiplying by the nominal &
using (10) instead of dividing by the exact W'(m) using (@)
‘cannot accumulate; the feedback loop removes any constant
error or trend.
2. Inerpolaion Jver
Although the kth interpolation is computed fra time kT;
(+ un) Te the interpotant is actually delivered coincident
with a clock ick no earirthan (mg + 1)T,. Therefor, the
‘output exhibits «timing jiter with peak-to-peak fluctuations
of T,, even ifthe sampling clock and receved symbol rate
ame etirelyjiter fre.
“Timing iter may be inconsequential i the received
ane consumed atthe receiver location. timing clock is
provided by underfows ofthe NCO. Underlow maths give an
indication of comet data clocking o any downstream devices
because they have the same jiter asthe dat
‘Bur often the data must be retransmitted over a synchronous
link to a remote consumer. The undefiow marks usally
cannot be revansmited along. with the dala Unless jiter is
removed before retransmission, the jiter wil be transmitted
om the data stream,
‘Aver [10] has pointed out that a nea terse clock can
be retrieved from the NCO and used to reclck the data before
retransmission. His scheme employs the contents 7(m) of
the NCO register in a direct digital frequency synthesizer.
[AL each NCO lock tick, the register conten afe used 10
aurea able of snes to produce a sample sin 2r7(m).
‘These sine samples ate applied to D/A convertor and then
filtered to yield an analog, low ite sinewave with frequency
1/T, = K/T, trom which a symbol-ate clock ean be derived.
Alternative Control Methods
‘An NCO is not the only possible control structure. An
alternative, suggested by M. Moeneclaey, is described in
“Appendix A.
\V. FILTER PROPERTIES
‘What properties are desirable in the interpolating filter's
impulse response h(t) or equivalently, via Fourier transfor
ration, in its transfer function Hy()? Take heed that the
properties sought are those ofthe fictitious analog fle, despite
the fact that all physical operations are performed digitally
A. Duration of Impulse Response
In general, new filter coefficients [samples of h(t)] must
be reloaded or recomputed for each interpolation. The fiac-
tional interval py—which specifies the fltercoefficient sample
values—never repeats if, and 7, are incommensurate
If the filter has finite impulse response (FIR), then I filter
coefficients and J signal samples must be delivered tothe filter
structure for each interpolation,
If an infinite impulse response (IIR) filter were employed,
a recursive structure would be required so thatthe computing
effort could be finite, Let the filler have p poles and = zeros
‘Then for each interpolation it would be necessaty to load the
following information to be able 10 compute the interpolant:
p+ 2+ 1 filer coetficients, as specified by sx.
241 signal samples.