Nw
`(11] Patent Number:
`5,166,924
`[45] Date of Patent:
`Nov. 24, 1992
`
`[56]
`
`References Cited
`US EATEN? DOCUMENTS
`4,799,214
`1/1989 Kaku ..cccccssscsssssneseneresees 370/32.1
`4,868,874
`9/1989 Takatori et al.
`......:sssessees 370/32.1
`
`United States Patent
`Moose
`
`115
`
`[54] ECHO CANCELLATION IN
`MULTI-FREQUENCY DIFFERENTIALLY
`ENCODED DIGITAL COMMUNICATIONS
`
`[75]
`
`Inventor:
`
`.
`Paul H. Moose, Carmel, Calif.
`
`[73] Assignee: Mercury Digital Communications,
`Inc., Monterey, Calif.
`,
`
`[21] Appl. No.: 566,290
`
`[22] Filed:
`
`Aug. 10, 1990
`
`Primary Examiner—Douglas W. Olms
`Assistant Examiner—Wellington Chin
`Attorney, Agent, or Firm—Davis & Schroeder
`[57]
`ABSTRACT
`A differentially encoded digital signal waveform is
`generated as a discrete time representation of a desired
`analog signal utilizing multi-frequency modulation
`techniques. The computational capability of present
`day, industry-standard microcomputers equipped with
`a floatin
`int array processoror digital signal proces-
`a
`sor chipisutilized to seeisers digitalfrequency encod-
`Reraten US. Appication Data
`
`[63]_Continuation-in-part of Ser. No. 490,769, Mar. 6, 1990, ing and compute both discrete Fourier transforms and
`Pat. No. 5,063,574.
`inverse discrete Fourier transforms to provide a trans-
`mitter and receiver
`system utilizing suitably pro-
`grammed microcomputers coupled by a communica-
`tions channel.
`
`[51] Unt. CUS ccccccsccssesssecseerees HO4L 5/14; HO4M 9/08
`[52] US. CUe oiseisisscssisasesscssssinibssecice 370/32.1; 379/410
`[58] Field of Search................. 370/32.1, 32; 379/410,
`;
`379/411
`
`5 Claims, 11 Drawing Sheets
`
`FDA
`
`77 TRANSMITT
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 1
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 1
`
`

`

`U.S. Patent
`
`Noy. 24, 1992
`
`Sheet 1 of 11
`
`5,166,924
`
`NO.
`
`HARMONIC t
`
`K
`
`HARMONIC k
`
`
`
`o4
`
`ACLOCK: f,
`FIG. 2a
`
`34_,CLOCK: f,
`
`{Y, (k)}
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 2
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 2
`
`

`

`U.S. Patent
`
`Noy. 24, 1992
`
`Sheet 2 of 11
`
`5,166,924
`
`QUADRATURE
`
`IN PHASE
` FIG. 3
`
`PREVIOUS STATE Sg
`
`FIG. 4a
`
`FIG. 4b
`
`PREVIOUS STATE 52
`
`PREVIOUS STATE S3
`
`1
`
`f
`
`59
`
`0
`
`3
`
`S32
`FIG. 4c
`
`2
`
`0
`
`4
`
`{
`
`33
`
`FIG. 4d
`
`r
`
`So
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 3
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 3
`
`

`

`U.S. Patent
`
`Nov. 24, 1992
`
`Sheet 3 of 11
`
`5,166,924
`
`
`
`IMdinovivaSWNOSMAd
`
`
`
`WAIoid“xn¥GYVONVIS
`
`gg|L_AuuSnon
`
`|YALNdNOD
`
`
`
`ONASLax0Vd
`
`WNOIS
`
`|YaNaANODafv/aI}quyanvis
`
`YALNdNOOD
`
`“WNOSY3d
`
`¢9
`
`AMLSNGNI
`
`JONINOASTWNOISALINOSIG|
`
`
`
`|nantviva
`
`19
`
` O/TPTVayii910“xny|co
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 4
`
`GAHOLVN
`
`4al1d
`
`AINOALIWW10d|Ceye
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 4
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Nov. 24, 1992
`
`Sheet 4 of 11
`
`5,166,924
`
`511
`
`513
`
`515
`
`517
`
`
`DIGITAL DATA|ANALOGPACKET
`
`
`
`
`ENCODER TRANSFER|gutIDFT STORAGE
`
`519
`
`tan---- CONTROLLER} ~~ - - --
`
`Deaeeee
`
`FIG. 6
`
`SI
`
`533
`
`535
`
`537
`
`
`ANALOG|DATA DATA DIGITAL
`
`IN
`[ACQUISITION
`STORAGE
`DECODE
`Fur
`
`!|
`
`939
`
`33
`
`a cae
`
`FIG. 7
`
`
`
`FIG. 8
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 5
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 5
`
`

`

`U.S. Patent
`
`Nov. 24, 1992
`
`Sheet 5 of 11
`
`FIG.9
`
`5,166,924
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 6
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 6
`
`

`

`U.S. Patent
`
`Nov. 24, 1992
`
`Sheet 6 of 11
`
`5,166,924
`
`x(n)
`
`z
`
`z
`
`feees i
`
`Sones
`
`79
`
`FIRST STAGE
`APPROXIMATED ECHO
`
`FIG. 10
`
`
`
`x(k) >_SECOND STAGECOMPLEX
`
`MULTIPLY
`APPROXIMATED ECHO
`
`
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 7
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 7
`
`

`

`U.S. Patent
`
`Nov. 24, 1992
`
`Sheet 7 of 11
`
`5,166,924
`
`LOL
`
`00166
`
`L6
`
`G6£6
`
`16
`
`INL
`
`NIVAOG
`
`Lay0Vd
`
`14aNIVNOG
`
`AVY
`
`o3u4
`
`ASVHd®dWV
`
`ONIGOD
`
`Viva
`
`did
`
`Aid
`
`INIGOINA
`
`VLVG
`
`Jd
`
`86
`
`W1ISIG
`
`NIViVG
`
`ALFYOSIG
`
`WNOIS
`
`JONINOIS
`
`LO
`
`clOl
`
`96
`
`¥6
`
`26
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 8
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 8
`
`
`
`

`

`U.S. Patent
`
`Nov. 24, 1992
`
`Sheet 8 of 11
`
`5,166,924
`
`LLL
`
`601
`
`LOl
`
`GO|Ol
`
`WLISIG
`
`WNOIS
`
`AVY
`
`ONIGO030
`
`|dilS
`
`‘dWAL
`
`WLISIG
`
`WNOIS
`
`AVUUY
`
`130NIVAOG
`
`JWI
`
`LayOVd
`
`80l
`
`901
`
`ALIYOSIG
`
`WNOIS
`
`JONANOAS
`
`NI
`
`Olt
`
`tlh
`
`Zbl
`
`INIGOO30
`
`édais
`
`VLG
`
`Wid
`
`Git
`
`WLIOId
`
`inoVLVd
`
`vOl20k
`
`flOU
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 9
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 9
`
`
`
`
`

`

`U.S. Patent
`
`Nov. 24, 1992
`
`Sheet 9 of 11
`
`5,166,924
`
` FIG. 144
`
`aS
`
`git
`
`O19
`
`i
`
`\
`
`\
`
`G
`
`Q
`
`\
`
`/
`
`wf
`
`.
`
`/
`
`O Ja Fei
`
`O
`
`NG
`
`Je
`
`O
`
`Ke
`
`O
`
`tig
`
`119
`
`/
`
`re
`
`oe
`
`/
`
`~
`
`ao A/I\\™e
`Of
`%
`/ oo
`°
`
`b
`
`Q
`
`OXY
`
`-
`
`C
`
`111
`
`191
`
`“sg
`
`%,
`
`\
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 10
`
`Oo@
`
`1)
`
`\
`
`Ni
`
`FIG. 14b
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 10
`
`

`

`U.S. Patent
`
`Noy. 24, 1992
`
`Sheet 10 of 11
`
`5,166,924
`
`= >
`
`.
`
`11
`
`11¢
`
`<>
`~ FIG.15
`YOD
`
`191
`
`199
`
`b19
`
`—SS
`
`.
`
`Ko
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 11
`
`Y
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 11
`
`

`

`U.S. Patent
`
`Nov. 24, 1992
`
`Sheet 11 of 11
`
`5,166,924
`
`
`
`FIG. 16
`
`176
`/
`
`
`
`DMAINIT
`
`FIG. 17
`
`
`
`DIFF
`ENCODE
`
`
`
`18
`
`3
`
`MESSAGE
`
`OUT
`
`
`
`FIG. 18
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 12
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 12
`
`

`

`1
`
`5,166,924
`
`ECHO CANCELLATION IN MULTI-FREQUENCY
`DIFFERENTIALLY ENCODED DIGITAL
`COMMUNICATIONS
`
`CROSS REFERENCE TO RELATED
`APPLICATION
`
`This application is a continuation-in-part of copend-
`ing application Ser. No. 07/490,769 filed on Mar. 6,
`1990, now U.S. Pat. No. 5,063,574.
`
`2
`combination of phase and amplitude modulation known
`as quadrature amplitude modulation (QAM). For exam-
`ple, transmission of data over telephonelines designed
`to carry analog voice frequency signals (WF) is re-
`stricted to a frequency band of about 300 to 3500 Hz.
`Digital modulation of an 1800 Hz carrier frequency
`using QPSK (2 bits per symbol) or 16-QAM(4bits per
`symbol) utilizing a modulator-demodulator device
`(modem) provides data communication at 4800 and
`9600 bits/sec, respectively, when transmitting at a rate
`of 2400 symbols per second. The unprocessed modula-
`tor carrier signal thus provided has a bandwidth sub-
`stantially greater than the available channel bandwidth
`The present invention relates generally to communi-
`so it mustbe filtered to fit in the available band. These
`cations of digital signals over bandlimited, unequalized,
`analog filters must be carefully designed so as not to
`noisy transmission channels at high data rates and, more
`introduce smearing, known as inter-symbolinterference
`particularly to the use of microcomputers such as per-
`sonal computers and the like to accomplish multi-fre-
`(ISI) between adjacent symbol waveforms or the sym-
`bols will be decoded in error. A raised cosine filter
`quency modulation and demodulation for transmission
`of a multitude of frequencies over a single channel.
`function is typically employed. Even then,the filtering
`action of the bandlimited VF channelwill introduce ISI
`In the modern world, computer to computer is
`quickly becoming the fundamental link for message and
`due to non-linearities (group delay) in its phase re-
`data traffic; i.e., information exchange and propagation.
`sponse. These non-linearities are most pronounced at
`In some cases the link is one of many in an extensive
`the band edges so that the symbol waveforms must be
`network; in others, it may be represented by a single
`filtered to the 2400 Hz band from 600 to 3000 Hz before
`point-to-point communications link. The physical me-
`being sent over the channel. The receiving section of
`dium constituting the link for transmitting the data may
`the demodulator contains an adaptivefilter known as an
`be wire or optical fiber. Or, it may be a microwave or
`equalizer in order to remove any residual ISI intro-
`satellite link utilizing radio frequency propagation. (Sat-
`duced by the group delay in the 600 to 3000 Hz band.
`ellites are also being developed for broadcasting digital
`The equalizer must be trained to the particular group
`audio and digital
`television signals.) In all cases, the
`delay characteristics of each switched channel connec-
`actual signal used to carry the data bits must be a prop-
`tion before any data can be transmitted.
`erly modulated analog signal with sufficient energy and
`The degree to which the equalization can reduce the
`of the appropriate frequency to propagate effectively
`ISI on actualcircuits limits the number of symbol wave-
`through the channel. Regardless of the form of the link,
`formsthat can be distinguished from one anotherat the
`the objective is to transmit information at a high rate
`receiver and hencelimits the numberofbits that can be
`with a low rate of errors from the transmitter to the
`encoded into each baud. A baudis a digitally encoded
`receiver.
`symbol waveform.In practice it has been found that the
`Prior art modulation methods for bandpass channels
`combination of ISI and additive noise limit transmission
`utilize amplitude and/or phase modulation to carry
`to either two, or under ideal conditions four, bits per
`signal information on a carrier wave in a channel fre-
`baud when transmitting 2400 bauds per second over
`quency band. When the information sourceis a finite
`2-wire switched telephonecircuits.
`alphabet, numbers, data, etc., or quantized analog
`In order to increase the rate at which data is transmit-
`sources such as digitized audio, television, or facsimile,
`ted, some modems employ multi-frequency modulation
`then only a finite numberofsignal states are required to
`(MFM)techniques. MFM utilizes multiple carrier fre-
`represent, or code the source.
`quencies within the available bandwidth, each fre-
`Digital data is frequently communicated using pulse
`quency independently modulated with digital informa-
`code modulation techniques at baseband,
`i.e.,
`in the
`tion in phase and/or amplitude. The frequencies are
`frequency spectrum from0thatis to some maximum, or
`linearly combined and transmitted as a single digitally
`upper frequency limit. If a bandpass transmission is
`encoded waveform, termed a baud, duringa finite time
`required, i.e., is transmission in a frequency band be-
`interval called the baud interval. U.S. Pat. No. 4,731,816
`tween an upperfrequency and a lowerfrequency,single
`issued to Dirk Hughes-Hartogs on Mar. 15, 1988 and
`side-band (SSB) modulation into and demodulation
`U.S. Pat. No. 4,601,045 issued to Daniel P. Lubarsky on
`from the desired frequency band may be employed. For
`Jul. 15, 1986 disclose examples of modems employing
`example, polar voltage pulses at 48K bits/sec are fil-
`MFM techniques. Hughes-Hartogs teaches minimizing
`tered to attenuate frequencies above 36 KHz and SSB
`modulated onto a 100 KHz carriertofit into the band-
`inter-baud interference by introducing a small guard
`time between successive bauds during which no signal
`pass channel from 60-104 KHz.
`is sent to prevent received baud overlap. Lubarsky
`Frequency modulation techniques are also employed
`teaches concentrating most of the signal in the center of
`for digital data. Typically, these involve sending one of
`the baud interval thus causing the signal to taper off to
`two, frequencyshift keying (FSK), or one of M (M-ary
`zero near the ends of the baud and minimizing interfer-
`FSK),
`frequencies spaced across the available fre-
`ence between baud intervals by eliminating abrupt
`quency band and may be used in applications where
`changes. If the baud interval is of sufficient duration
`bandwidth efficiency is unimportant as they operate at
`compared to the guard timeortapertime, then the loss
`less than one bit per Hz of available bandwidth.
`ofdata rate is relatively insignificant.
`Alternatively, digital
`information may be encoded
`If the baudsare to be long in duration, then manybits,
`onto a basically analog carrier frequency, centered in
`and consequently many frequencies, may be transmitted
`the available frequency band, using phase modulation
`(PSK), differential phase modulation (DPSK), or a
`in each baud. However, in order to preventinter-fre-
`
`BACKGROUNDOF THE INVENTION
`
`10
`
`_ 5
`
`30
`
`35
`
`45
`
`60
`
`65
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 13
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 13
`
`

`

`5,166,924
`
`30
`
`40
`
`4
`3
`tions channels. The present invention functions in pack-
`quencyinterference, the frequencies must not be spaced
`et-switched, circuit-switched, or broadcast enviorn-
`too closely. Ideally, the frequencies are made orthogo-
`ment and operates with either baseband or bandpass
`nal over one baudinterval. This is known as orthogonal
`channels. An MFM digital signal waveform is gener-
`frequency division multiplexing (OFDM). A frequency
`ated as a discrete time,i.e., sampled data, representation
`set will be mutually orthogonal if the frequencies are
`of a desired MFM signal using an industry standard
`separated at multiples of the reciproca] of the baud
`microcomputer, such as a personal computerorthelike,
`interval. For example, a system employing a rate of 10
`equipped with a floating point array processor or a
`bauds per second in the VF band from 300 to 3500 Hz
`digital signal processing (DSP) chip and utilizing a
`could contain 320 frequencies spaced 10 Hz apart. If
`computer software program. For signal transmission,
`each frequency is encoded with 4 bits of information,
`then 1280 bits wil] be encoded into each baud and the
`the discrete time signal samples, which are stored in
`random access computer memory (RAM)as digital
`system will have a throughputrate of 12,800 bits/sec.
`wordsin a time domain array (TDA), are clocked from
`The major disadvantage associated with the MFM
`memory via a suitable input/output (1/O) port of the
`(OFDM)systems described aboveis that although they
`microcomputer at a clock rate whichis a large multiple
`can effectively eliminate inter-baud interference and
`of the baud rate and whichis at least twice the highest
`inter-frequency interference within a baud, they must
`frequency to be sent in the MFM analog signal. The
`be demodulated using fully coherent receivers for each
`digital words are coupled to a digital-to-analog con-
`frequency in order to obtain the high data rates desired.
`verter (DAC)asaserial data stream for conversion to
`Since the multitude of frequencies are subject to differ-
`20
`the desired analog MFMsignal for transmission.
`ent and unknown amplitude and phase changesintro-
`duced by the transmission channel, these channel prop-
`The computer program creates the discrete time sig-
`nal as follows. Digital data to be transmitted are ac-
`erties must be measured during theinitiation phase of
`cepted from a messagefile n bits at a time, differentially
`the communication process and prior to transmission of
`encoded and converted to real and imaginary signal
`data. One example of this technique is disclosed by
`values in accordance with the chosen signal modulation
`Hughes-Hartogs. Such methods are exceedingly com-
`constallation for each of the tones. Each encodedn bit
`plex and computationally intensive easily rivaling the
`work is stored in a position in the lower half of a com-
`cost and complexity of adaptive equalization. Further-
`plex valued frequency domain array (FDA). The com-
`more, such OFDM systems will not be effective for
`plex conjugate of the encoded value is stored in its
`* direct MFMsignalling in bandpass systems such as the
`image position in the upper half of the FDA. Each
`60-104 KHz example described aboveorin a prototype
`position in the array is assigned a position number
`model of a UHFsatellite sound broadcasting system as
`which corresponds to a harmonicof the baud rate of the
`discussed by Alard et al in “A New System of Sound
`system. Only those array positions corresponding to
`Broadcasting to Mobile Receivers", presented at the
`“Centre Commun d'Etude de Telecommunication et
`desired tones in the MFM signal arefilled with modula-
`tion values. All other array position values are set to
`Telediffusion” in France and published by the IEEE in
`zero,
`1988.
`Differential encoding of the carrier frequencies pro-
`vides a practical solution to this problem with an atten-
`dant 3-db loss of signal-to-noise ratio performance
`against additive noise. The conventional method to
`differentially encode information is from baud to baud
`as is customary in conventional DPSK and as done in
`the OFDMsystem disclosed by Alard et al. However,
`this method produces undesirable results when the baud
`interval is long, due to channelinstability such as that
`introduced by fading. Further
`if asynchronous or
`packet transmissions are utilized there may be a signifi-
`cant reduction of data rate when only two or three
`bauds are sent since differential encoding in time re-
`quires utilizing one baud as a reference.
`Frequency differential encoding of multiple carriers
`was utilized in the HF modem disclosed by Gene C.
`Porter in “Error Distribution and Diversity Perfor-
`mance of a Frequency-Differential PSK HF Modem”,
`IEEE TRANS. ON COMMUNICATION TECH-
`NOLOGY, 16-4, August 1968, pages 567-575. While
`frequency differential encoding minimized many of the
`above described problems encountered with OFDM
`systems, the circuitry required for generation and de-
`modulation of the signals was unduly complicated and
`did not reliably maintain the necessary orthogonality
`between the carrier frequencies.
`SUMMARYOF THE INVENTION
`
`In the preferred embodiment, K encoded words are
`placed in adjacent array positions beginning at position
`kj+1 and ending at position k}+K. Reference values
`for differentia] decoding are placed in position k); this
`results in an analog signal strictly bandlimited to the
`band between k;—1 times the baud rate and k}+K+1
`times the baud rate. For example, a baud rate of 10 per
`second, a k) of 3] and a K of 320 results in a modulated
`analog signal strictly bandlimited to the band between
`300 Hz and 3520 Hz. A baud rate of 250 per second,k;
`of 241 and K of 174 results in a modulated analogsignal
`strictly bandlimited to the band between 60,000 Hz and
`104,000 Hz. A baud rate of 30 per second, a k; of 537
`and a K of 128 results in a modulated analog signal
`strictly bandlimited to the band between 16,110 Hz and
`19,980 Hz.
`A real valued TDAis obtained by operating on the
`FDA with an inverse discrete Fourier
`transform
`(IDFT) algorithm. The values in the TDA are guaran-
`teed to be real because of the complex conjugate image
`symmetry established in the FDA. Thetotal number of
`real values in the TDA, designated as k,, is the same as
`the total number of complex values in the FDA. In a
`preferred embodiment, kx is made a power of two and
`the IDFT is executed using a fast Fourier transform
`(FFT) algorithm. The TDAcontains the discrete time
`signal representation of one baud ofdigitally encoded
`data that consists of the superposition of kx/2—1 tones,
`or carrier frequencies, each modulated with a phase and
`amplitude corresponding to the polar representation of
`the complex number that was stored at its harmonic
`number in the FDA as described above. The tones are
`
`60
`
`Thepresent invention provides a method and appara-
`tus utilizing multi-frequency modulation (MFM)tech-
`niques for modulating and demodulating digital infor-
`mation signals for use with bandlimited communica-
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 14
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 14
`
`

`

`5,166,924
`
`5
`harmonics of the baud rate and are mutually orthogonal
`on the baud interval. The TDA values are clocked out
`through the microcomputer I/O port to the DACata
`clock rate of kx times the baud rate.
`In the preferred embodiment where an adjacent sub-
`set of K of the k,/2—1 available tones are modulated
`with information and the others given amplitudes of
`zero, nK bits are transmitted in each baud. In the 10
`baud per second example containing 320 adjacent tones
`between 300 Hz and 3520 Hz, cited above, k, of 1024
`(21°) leads to a clock rate of 10,240 Hz. With n=4 bits
`encoded into each tone, 1280 bits are sent with each
`baud for a data rate of 12,800 bits/sec. In the 250 baud
`per second example containing 174 adjacent tones be-
`tween 60 KHz and 104 KHztones, kx of 1024 leads to a
`clock rate of 256 KHz. With n=2 bits encoded with
`each tone, 348 bits of information are sent with each
`baud for a data rate of 87,000 bits/sec. In the 30 baud
`per second example containing 128 tones in the band of
`16,110 Hz to 19,980 Hz a k, of 2048 leads to a clock rate
`of 61,440 Hz. With n=3 bits per tone, 384 bits of infor-
`mation are transmitted with each baud for a data rate of
`11,520 bits/sec.
`It should be noted from the examples above, anditis
`a significant feature of the present invention, that band-
`pass and baseband signals are generated in an identical
`manner; no further modulation steps are required.
`In the preferred embodiment, a time domain packet
`or array (TDA) is generated for transmission by the
`computer program of the transmitting microcomputer
`consisting of the TDA of a synchronization baud fol-
`lowed by the TDAs ofL data bauds. A packet transmits
`L baudsof K tones each modulated with n bits per baud
`or nLK bits per packet at a data rate of n bits/Hz of
`occupied channel bandwidth. Overhead comprises one
`baud for synchronization and one tonefordifferentially
`encoding the data in frequency.
`Frequency domain differential encoding eliminates
`the need for correcting the channel amplitude and phase
`response,
`i.e., frequency domain equalization as re-
`quired by the prior art, in the following manner. The
`tones are spaced at the baud rate. By using a very low
`baud rate, the tones are very close together and there-
`fore experience substantially the same group delay and
`attenuation when transmitted through the channel. In
`the present invention, phase (and/or amplitude)is dif-
`ferentially encoded from tone-to-tone. Differential de-
`modulation at the receiver cancels out unknown phase
`(and/or attenuation) introduced by the channel. Bulk
`delay through the channel is accounted for at the re-
`ceiver with the synchronization baud using a polarity
`only matchedfilter to establish the timing reference for
`the received baud signal samples.
`One advantageofutilizing a very low baudrate,i.e.,
`long baud intervals, is that the need for a guard time
`between bauds, or for tapering the baud signal ampli-
`tudes at their beginning and end,i.e., “shoring” as dis-
`closed by Lubarsky, is reduced or eliminated. This is
`because only a very small fraction of the baud energyis
`involved in the inter-baud interference. For example,
`over unequalized telephonelines the variation in delay
`for tones from 300 Hz to 3500 is only several millisec-
`onds. For bauds of 100 milliseconds or morein length
`only a small percentage of the baud energyis involved
`in inter-baud interference. This is not significant when
`demodulating QPSK constellations (2 bits encoded per
`tone). Under particularly severe unequalized group
`delay conditions and or when modulation constellations
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`30
`
`35
`
`0
`
`65
`
`6
`with more points are selected, a guard time equal to the
`group delay with zero signal values is inserted between
`bauds in the TDA.
`Demodulation of MFM communication signals is
`accomplished in a manner that is the inverse of their
`generation. The received analog signal is sampled by a
`clock having the same frequencyas the transmit clock.
`Sample values are analog-to-digital (ADC) converted
`and stored in the receive personal computer memoryin
`a receive TDA. Thedata are extracted from the TDP
`one baud at a time. The receive computer program
`executes a ky point discrete Fourier transform (DFT)
`creating a receive FDA. Complex values from the posi-
`tion values in the FDA corresponding to the K+]
`tones in the MFMsignal are differentially decoded
`producing K complex values that are stored in a receive
`digital signal array (DSA). These values are demodu-
`lated in accordance with the detection algorithm of the
`selected modulation constellation to produce the K, n
`bit words of the baud. The entire packet is decoded by
`repeating the process for each of the L bauds.
`One advantage ofdifferential encoding in frequency
`is that the receiver clock frequency need not be phase
`coherent with the transmit clock frequency. Further,
`small frequencyoffset errors, on the order of onepart in
`105, are acceptable with no degradation in performance.
`Thefirst baud in each packetis utilized as a synchroni-
`zation baud to establish baud synchronization. Because
`MFMsignals havethestatistical characteristics of band-
`pass white noise,
`the autocorrelation function of an
`MFMsignal with random input data has a very sharp
`spike for its central peak. Thus, a polarity-only matched
`filter matched to a pre-selected synchronization baud
`which generates a sharp spike at the end of the synchro-
`nization baud may be usedto initiate data transfer from
`the ADCto the receive TDP via the selected receive
`microcomputer computer I/O port. In a preferred em-
`bodiment, data is transferred via the direct memory
`access (DMA) channelsin both the transmit and receive
`microcomputers using the byte transfer mode. For very
`high speed asynchronous operation, block DMAtrans-
`fers are preferred.
`In some data communicationssettings, such as com-
`puter-to-computer links, full duplex transmission is re-
`quired, i.e., information nodes which transmit and re-
`ceive simultaneously. But when operating in the full-
`duplex mode over the same physical communications
`medium using the same channe] bandwidth and time
`slots, a node’s own transmission can interfere with its
`reception from the other node. This is generally known
`as listener echo and is a particular problem in dial-up
`two-wire public switched telephonecircuits. In order to
`combat this problem, high-speed dial-up modems are
`equipped with echo cancellers, devices that removethat
`component of a node’s received signal that is due toits
`own transmission. As much as 75 db of echo suppres-
`sion may be required in order for a system to achieve 8
`bits per Hz of bandwidth efficiency at a signal-to-echo
`ratio of —27 db. The present invention describes a dual-
`Stage, data driven echo cancellation algorithm for
`MFMthatachieves up to 75 db ofrejection of near-end
`echo and upto 35 db ofrejection of far-end echo.
`The present invention provides an MFM transmitter
`and receiver which utilizes the computing power avail-
`able in state-of-the-art industrial standard microcomput-
`ers to encode, modulate, demodulate and decodedigital
`data utilizing discrete Fourier transform (DFT) tech-
`niques. In a data communications system comprising a
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 15
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 15
`
`

`

`7
`transmitting microcomputer and a receive microcom-
`puter linked together via a communications channel, an
`inverse discrete Fourier transform (IDFT)in the trans-
`mit computer and a DFT in the receiver computer are
`executed as Fast Fourier Transforms (FFT)in real time,
`the only requirement being that each microcomputer be
`equipped with readily available floating point array
`processors. Each microcomputeris coupled to the com-
`munications channel via signal converters such as
`readily available ADC and DAC,respectively, chips.
`Thus,
`the present
`invention provides a “universal
`modem” in which the bandwidth and data rate are eas-
`ily controlled by changing parameters in transmit and
`receive software programs.
`Differential encoding of the phase from tone-to-tone
`eliminates the requirement for a phase-locked or coher-
`ent clock reference between the transmit and receive
`terminals and greatly reduces the signal sensitivity to
`phase variations introduced in the physical portions of
`the communications link. Baud synchronization is ob-
`tained at the receiving terminalutilizing a simple polari-
`ty-only correlator circuit operating on a synchroniza-
`tion baud transmitted as the first baud in each data
`packet. The amplitudes of the individual tones in the
`MFMsignal can be controlled at the transmit FDA to
`provide equalization of the frequency-dependentsignal-
`to-noise ratio which may be present in frequency selec-
`tive channels.
`
`BRIEF DESCRIPTION OF THE DRAWING
`
`A fuller understanding of the present invention will
`become apparent from the following detailed descrip-
`tion taken in conjunction with the accompanying draw-
`ing which formsa part ofthe specification and in which:
`FIG. 1 is a diagram illustrating the relationship be-
`tween frequency and time for an MFM signal packet;
`FIGS. 2a and 26 are conceptual block diagramsillus-
`trating the transmitter and receiver sections, respec-
`tively, for an MFM communication system according
`to the principles of the present invention;
`FIG.3 is a diagram illustrating the complex envelope
`for one QPSK tone;
`FIGS. 4a-4d are phase plot diagramsillustrating
`phase encoding for DQPSKencoding;
`FIG. 5 is a functional block diagram of an MFM
`communications system according to the principles of
`the present invention;
`FIG. 6 is a functional block diagram of the transmit-
`ter block shown in the block diagram of FIGS. 2a and
`
`the
`
`FIG. 7 is a functional block diagram of the receiver
`block shown in the system of FIGS.25 and 5;
`FIG. 8 is a functional block diagram of the data ac-
`quisition board shown in FIG.7;
`FIG. 9 is a functional block diagram of a data-driven
`echo cancellation circuit for a full-duplex communica-
`tion system according to the principles of the present
`invention;
`FIG. 10 is a diagram illustrating the first stage echo
`cancellation training algorithm for the echo cancella-
`tion circuit shown in FIG.9;
`FIG. 11 is a diagram illustrating generation of the
`weighting coefficients for the second-stage training
`algorithm for the echo cancellation circuit shown in
`FIG. 9;
`FIG.12 is a flow diagram illustrating multi-frequency
`differential quadrature phase shift keyed modulation in
`accordancewith the principles of the present invention;
`
`20
`
`www
`
`60
`
`5,166,924
`
`8
`FIG. 13 is a flow diagram illustrating demodulation
`and decoding for multi-frequency differential quadra-
`ture phase shift keyed modulation in accordance with
`the principles of the present invention;
`FIG.14a is a diagram illustrating the transition states
`for multi-frequency differential 16-quadrature ampli-
`tude modulation accordingto the principles of the pres-
`ent invention;
`FIG. 146 is a diagram illustrating the decoded phase
`values for the differential encoding strategy shown in
`FIG. 142;
`FIG.15 is a diagram illustrating a decoding decision
`tree for decoding differentially encoded data in accor-
`dance with the encoding strategy shown in FIGS. 14a
`and 14);
`FIG. 16 is a flow chart illustrating a transmit algo-
`rithm for use in the transmit microcomputer shownin
`FIG. 5;
`FIG.17 is a flow chart illustrating another transmit
`algorithm for use in the transmit microcomputer shown
`in FIG. 5; and
`FIG. 18 is a flow chart illustrating a receive algo-
`rithm usedin the receive microcomputer shownin FIG.
`5.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`
`MULTI-FREQUENCY MODULATION
`Referring now to FIG. 1, an analog multi-frequency
`modulation (MFM) transmit signal generated according
`to the principles of the present invention comprises
`“packets” of multiple tones or frequencies which are
`differentially modulated in amplitude and/or phase
`between adjacent frequencies. The tones 13 are present
`simultaneously during a subinterval of the packet 11
`known as a baud 15. The packets 11 can be located
`arbitrarily in the frequency spectrum and in time.
`With further reference to FIG. 1, the following terms
`are defined:
`T: Packet length in seconds
`AT: Baud length in seconds
`K,: Baud length in number of samples
`L: Numberof bauds per packet
`At: Time between samples in seconds
`fx=1/At: Sampling or clock frequency for digital-to-
`analog and analog-to-digital conversion in Hz.
`Af=1/A4T: Frequency spacing (minimum) between
`MFM tones.
`K: Number of MFM tones.
`Since At=AT/k,, the sample frequency f,=k,Af.
`Consequently, there are a maximum of kx/2—1 tones
`spaced at intervals of Af Hz between Af Hz and less
`than f,/2 Hz, the Nyquist frequency, that can carry
`amplitude and phase information during each baud 15.
`Some,or many, ofthe tones may notbe used (or equiva-
`lently have amplitudes of zero) during any or al] bauds
`ofthe packet. For example, to generate bandpass signals
`between frequencies f) and f2, only tones between har-
`monics kj=f)/Af and k2=f2/Af will be allowed non-
`zero amplitudes. Here, the maximum number of tones
`will be K=k2—k;+1 and the signal bandwidth will be
`W=KAf.
`Mathematically the !* baud of the analog transmit
`signal can be described by;
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 16
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 16
`
`

`

`xfu) = ¥ xudu)
`
`where,
`
`xu) = Ap, cos (2rkAfu+ob14),0SuS T.
`
`5,166,924
`
`1
`
`®
`
`(2)
`
`In equations (1) and (2), u is time referenced to the
`beginning of
`the baud 15. Actual
`real
`time
`is
`t=to+1A4T-+u where tg is the time ofi