United States Patent
`
`[19]
`
`|||||||l|||||I||||||l|lllll||l||||||||l||||||||illllllllillllllllllllllllll
`U5005166924A
`[11] Patent Number:
`
`5,166,924
`
`Moose
`
`[451 Date of Patent:
`
`Nov. 24, 1992
`
`[54] ECHO CANCELLATION IN
`MULTI-FREQUENCY DIPFERENTIALLY
`ENCODED DIGITAL COMMUNICATIONS
`
`[75]
`
`Inventor:
`
`Paul H. Moose. Carmel. Calif.
`
`[73] Assignee: Mercury Digital Communications,
`Inc., Monterey. Calif.
`
`‘
`
`[2]] App]. No.: 566,290
`
`[22] Filed:
`
`M13 10 1990
`
`'
`.
`Rented U.S. Application Data
`Continuation-impart 0f Ser. ”0- ”3559- M311 6- 1990-
`Pa“ “0‘ 5-053'574'
`
`[631
`
`Im. C1.5 ......................... H041. 5/14; How 9/08
`[51]
`[52] U5. C1. .................................... 310/32.1; 379/410
`[53] Field of Search
`370/311. 32; 379/410,
`'
`379/41]
`
`[56]
`
`References Cited
`
`U'S' PATENT DOCUMENTS
`4.199.214
`1/1939 Kaku .................................. 370/31]
`4.863.874 9/ 1989 Takatori eta}.
`................... 37032.]
`
`Primary Examiner—Douglas W. Olms
`Assistant Examiner—Wellington Chin
`Attorney. Agent, or Firm—Davis 8: Schroeder
`
`ABSTRACT
`[5?]
`A differentially encoded digital signal waveform is
`generated as a discrete time representation of: desired
`analog signal utilizing mold-frequency modulation
`techniques. The computational capability of present
`day. industry-standard microcomputers equipped with
`a floatin
`int array rocessor or (ii
`'tal signal proces-
`sor chipgispiitilized to liiier‘l'orm digitalgi'requency encod-
`ing and compute both discrete Fourier transforms and
`inverse discrete Fourier transforms to provide a trans-
`mitter and receiver
`system utilizing suitably pro-
`grammed microcomputers coupled by a communica-
`tions channel.
`
`5 Claims, 11 Drawing Sheets
`
`
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 1
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 1
`
`

`

`US. Patent
`
`Nov.24, 1992
`
`Sheet 1 of 11
`
`5,166,924
`
`SYMBOL 1k
`
`
`
`
`
`
`
`
`
`
`--m-
`
`i‘1
`
`K
`
`HARMONIC k
`
`HARMONIC
`N0.
`
`
`
`24
`
`CLOCK: 1x
`
`FIG. 20
`
`34
`
`CLOCK: 1x
`
`
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 2
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 2
`
`

`

`US. Patent
`
`Nov.24,1992
`
`Sheet 2 of 11
`
`5,166,924
`
`QUADRATURE
`
`IN PHASE
`
`
`PREVIOUS STATE So
`
`FIG. 3
`
`FIG. 40
`
`FIG. 4b
`
`PREVIOUS STATE 52
`
`i
`
`S
`
`S3
`
`2
`
`FIG. 4c
`
`1
`
`f
`
`52
`
`o
`
`PREVIOUS STATE 53
`
`i
`
`2
`
`3
`
`T
`
`1
`
`52
`
`FIG. 4d
`
`53
`
`0
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 3
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 3
`
`

`

`US Patent
`
`eh
`
`3
`
`%
`
`2P,mlllllllllllnfli_n@328m38%;
`s_2._VAlllllllllllllllllll|_
`
`:29ESEa}r5.58:._oa:
`9.,m.o:6iiiiiim_|lII1llllllllllJi,_858%222m55%_22%_025$qu_@3385::
`
`5&8Es:28me88:...@5928u355.52332%
`
`a_aaa_
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 4
`
`E582.
`
`omgzfim
`
`\H_5n::3o:55.xi_No
`
`1— _ _
`
`2 §W E g E E
`
`.Qa
`
`l_. _
`
`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
`
`5‘7
`
`DIGITAL
`[N
`
`PACKET
`STORAOE
`ENCODER
`|
`I
`|
`|
`I
`|
`:
`:
`i
`1
`. —————— CONTROLLER ------ 4 ----------
`
`IDFT
`
`519
`
`L_._-————
`
`‘_-."'
`
`0m ANALOG
`TRANSFER
`OUT
`
`FIG. 6
`
`531
`
`333
`
`535
`
`537
`
`DIGITAL
`OUT
`
`53
`
`DECODE
`
`I|I
`
`:
`
`lI
`
`||II E
`
`INAILOG
`m
`
`DATA
`ACQUISIIION
`
`OATA
`STORAGE
`
`539
`
`—————— CONTROLLER ____--._________-.
`
`FIG. 7
`
`f F
`
`IG. 8
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 5
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 5
`
`

`

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

`

`US. Patent
`
`Nov. 24, 1992
`
`Sheet 6 of 11
`
`5,166,924
`
`A”)
`
`z
`
`2
`
`S
`
`2
`
`h(0)
`
`h(1)
`
`h(2)
`
`-
`
`-
`
`'
`
`h(n-1)
`
`5. . . .
`
`FIRST STAGE
`APPROXIHATED ECHO
`
`9
`
`FIG. 10
`
`
`
`,
`
`SECOND STAGE
`APPROXIMATE!) ECHO
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 7
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 7
`
`

`

`US. Patent
`
`Nov. 24, 1992
`
`Sheet 7 of 11
`
`5,166,924
`
`m2:
`
`z<zoo
`
`meo<a
`
`mpmmomo
`
`4<zom
`
`HQZwDOMm
`
`bao
`
`96:
`
`mm
`
`+m
`
`mm
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 8
`
`mm
`
`Pop
`
`oo—
`
`mm
`
`mm
`
`mm
`
`mm
`
`Fm
`
`Fmo_
`
`cum;
`
`zEzoo
`
`><mm<
`
`mm<zmamz<
`
`ozaoo
`
`<H<o
`
`MJE
`
`mks
`
`ozsoozm
`
`4<hfi=o
`
`z_<p<o
`
`<H<o
`
`m;:
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 8
`
`
`
`

`

`US. Patent
`
`Nov. 24, 1992
`
`Sheet 8 of 11
`
`5,166,924
`
`
`
`mo__mo_
`
`___mo_~o_
`
`mo—
`
`.
`
`44:0:H
`288;353
`
`gawk
`
`o_#
`
`4¢zom
`
`>¢mm¢
`
`_gmpm44205
`
`><xm4
`
`to
`
`m2
`
`Emmoma
`
`.Esz
`
`52595
`
`2_
`
`“2....
`
`22:8
`
`ESE
`
`ozaooma
`
`“mam
`
`¢H<o
`
`“an
`
`n*
`
`44:05
`
`#30(Rio
`
`2.o_.._
`
`n:m:N:
`
`3:
`
`No—
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 9
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 9
`
`
`
`
`

`

`US. Patent
`
`Nov. 24, 1992
`
`Sheet 9 of 11
`
`5,166,924
`
` FIG. 14a
`
`”1‘
`
`\
`
`in
`
`M
`
`j,“
`
`/
`
`¢1¢
`
`11¢
`
`\
`
`.
`
`.
`
`/
`
`\
`
`. .
`
`-
`\ o
`\
`
`o
`I /
`/
`
`/
`
`. .
`
`O
`
`.
`
`\ /
`
`O
`
`/ \
`
`-
`
`'
`
`/
`
`//
`
`.
`
`/
`
`/
`
`-
`
`'
`
`\
`. \
`-
`
`" -
`
`\
`
`'
`
`\
`
`Ni
`
`1W
`
`FIG. 14b
`
`/
`
`r=fil
`
`“1
`
`1951
`
`\
`
`}=_i
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 10
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 10
`
`

`

`US. Patent
`
`Nov. 24, 1992
`
`Sheet 10 of 11
`
`5,166,924
`
`Z
`
`)_
`
`>—
`
`z
`
`z
`
`>_
`
`E.
`
`«s.
`
`as:
`
`15.
`
`E
`
`|—'—""-—I—
`
`._r-
`15:.
`
`[.0
`'—
`.
`
`(.9
`E
`
`z
`
`>—
`
`2
`
`>-
`
`z
`
`E
`
`>—
`
`z
`
`3"
`
`.
`
`a15:.
`
`as.
`f.
`as»
`
`15L
`15L
`a
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 11
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 11
`
`

`

`US. Patent
`
`Nov. 24, 1992
`
`Sheet 11 of 11
`
`5,166,924
`
`DHAINIT
`
`COMPLEX
`FFT
`
`171
`
`FIG. 16
`
`SELECT
`BAUD
`
`175
`
`1'18
`/
`
`MESSAGE FILE
`
` 3
`
`MESSAGE
`
`OUT
`
`FIG. 17
`
`DECODE
`
`DlFF
`
`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
`DII-‘FERENI‘IALLY ENCODED DIGITAL
`COMMUNICATIONS
`
`CROSS REFERENCE TO RELATED
`APPLICATION
`
`This application is a continuation-impart of copend-
`ing application Ser. No. (ll/490,769 filed on Mar. 6,
`1990, now U. 8. Pat. No. 5,063,574.
`
`10
`
`BACKGROUND OF THE INVENTION
`
`2
`combination of phase and amplitude modulation known
`as quadrature amplitude modulation (QAM). For exam-
`ple, transmission of data over telephone lines designed
`to carry analog voice frequency signals (VF) is re-
`stricted to a frequency band of about 300 to 3500 Hz.
`Digital modulation of an 18(1) Hz carrier frequency
`using QPSK (2 bits per symbol} or lo-QAM (4 bits per
`symbol} utilizing a modulator-demodulator device
`(modem) provides data communication at 4800 and
`96m 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
`so it must be filtered to fit in the available hand. These
`analog filters must be carefully designed so as not to
`introduce smearing. known as inter-symbol interference
`(181) between adjacent symbol waveforms or the sym-
`bols will be decoded in error. A raised cosine filter
`
`15
`
`The present invention relates generally to communi-
`cations of digital signals over bandlimited. unequalized,
`noisy transmission channels at high data rates and, more
`particularly to the use of microcomputers such as per-
`sonal computers and the like to accomplish multi-fre-
`quency modulation and demodulation for transmission
`of a multitude of frequencies over a single channel.
`In the modern world, computer to computer is
`quickly becoming the fundamental link for message and
`data traffic; i.e., information exchange and propagation
`In some cases the link is one of many in an extensive
`network; in others, it may be represented by a single
`point-to-point communications link. The physical me-
`dium constituting the link for transmitting the data may
`be wire or Optical fiber. Or, it may be a microwave or
`satellite link utilizing radio frequency propagation. (Sat-
`ellites are also being deveIOped for broadcasting digital
`audio and digital
`television signals.) In all cases, the
`actual signal used to carry the data bits must be a prop-
`erly modulated analog signal with sufficient energy and
`of the appmpriate frequency to propagate effectively
`through the channel. Regardless of the form of the link,
`the objective is to transmit information at a high rate
`with a low rate of errors from the transmitter to the
`receiver.
`Prior art modulation methods for bandpass channels
`utilize amplitude and/or phase modulation to carry
`signal information on a carrier wave in a channel fre-
`quency band. When the information source is a finite
`alphabet, numbers, data, etc., or quantized analog
`sources such as digitized audio, television. or facsimile,
`then only a finite number of signal states are required to
`represent, or code the source.
`Digital data is frequently communicated using pulse
`code modulation techniques at baseband,
`i.e.,
`in the
`frequency spectrum from 0 that is to some maximum, or
`upper frequency limit. If a bandpass transmission is
`required, i.e., is transmission in a frequency band be—
`tween an upper frequency and a lower frequency, single
`side-band (SSE) modulation into and demodulation
`from the desired frequency band may be employed. For
`example, polar voltage pulses at 48K bits/sec are fil-
`tered to attenuate frequencies above 36 RH: and SSH
`modulated onto a 100 KHz carrier to fit into the band-
`
`pass channel from 60—104 Kl-lz.
`Frequency modulation techniques are also employed
`for digital data. Typically, these involve sending one of
`two, frequency shift keying (FSK), or one of M (M-ary
`FSK),
`frequencies spaced across the available fre-
`quency band and may be used in applications where
`bandwidth efficiency is unimportant as they operate at
`less than one bit per Hz of available bandwidth.
`Alternatively, digital
`information may be encoded
`onto a basically analog carrier frequency, centered in
`the available frequency band, using phase modulation
`(PSK), differential phase modulation (DPSK), or a
`
`20
`
`function is typically employed. Even then, the filtering
`action of the bandlimited VF channel will introduce 151
`
`25
`
`35
`
`45
`
`55
`
`60
`
`65
`
`due to non-linearities (group delay) in its phase re-
`sponse. These non-linearities are most pronounced at
`the band edges so that the symbol waveforms must be
`filtered to the 2400 Hz band from 600 to 3000 Hz before
`
`being sent over the channel. The receiving section of
`the demodulator contains an adaptive filter known as an
`equalizer in order to remove any residual 15] intro-
`duced by the group delay in the 600 to 3030 Hz band.
`The equalizer must be trained to the particular group
`delay characteristics of each switched channel connec-
`tion before any data can be transmitted.
`The degree to which the equalization can reduce the
`181 on actual circuits limits the number of symbol wave-
`forms that can be distinguished from one another at the
`receiver and hence limits the number of bits that can be
`encoded into each band. A baud is a digitally encoded
`symbol waveform. In practice it has been found that the
`combination of [SI and additive noise limit transmission
`to either two, or under ideal conditions four, bits per
`baud when transmitting 24-00 bands per second over
`2-wire Switched telephone circuits.
`In order to increase the rate at which data is transmit-
`ted, some modems employ multi—frequency modulation
`(MFM) techniques. MFM utilizes multiple carrier fre-
`quencies within the available bandwidth, each fre-
`quency independently modulated with digital informa-
`tion in phase and/or amplitude. The frequencies are
`linearly combined and transmitted as a single digitally
`encoded waveform, termed a hand. during a finite time
`interval called the baud interval. US. Pat. No. 4,131,816
`issued to Dirk Hughes-Hartogs on Mar. 15, 1988 and
`[.75. Pat. No. 4,601,045 issued to Daniel P. Lubarsky on
`Jul. 15, 1986 disclose examples of modems employing
`MFM techniques. Hughes-Hanogs teaches minimizing
`inter-baud interference by introducing a small guard
`time between successive bands during which no signal
`is sent to prevent received baud overlap. Lubarsky
`teaches concentrating most of the signal in the center of
`the baud interval thus causing the signal to taper off to
`zero near the ends of the baud and minimizing interfer-
`ence between baud intervals by eliminating abrupt
`changes. If the baud interval is of sufficient duration
`compared to the guard time or taper time, then the loss
`of data rate is relatively insignificant.
`If the bands are to be long in duration, then many bits.
`and consequently many frequencies, may be transmitted
`in each baud. However, in order to prevent inter-fre-
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 13
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 13
`
`

`

`3
`quency interference. the frequencies must not be spaced
`too closely. Ideally, the frequencies are made orthogo-
`nal over one band interval. This is known as orthogonal
`frequency division multiplexing (OFDM). A frequency
`set will be mutually orthogonal if the frequencies are
`separated at multiples of the reciprocal of the baud
`interval. For example. a system employing a rate of IO
`bauds per second in the VF band from 300 to 3500 Hz
`could contain 320 frequencies spaced 10 Hz apart. If
`each frequency is encoded with 4 bits of information.
`then 1280 hits will be encoded into each band and the
`system will have a throughput rate of 12,800 bits/sec.
`The major disadvantage associated with the MFM
`(OFDM} systems described above is that although they
`can effectively eliminate inter-baud interference and
`inter-frequency interference within a baud, they must
`be demodulated using fully coherent receivers for each
`frequency in order to obtain the high data rates desired.
`Since the multitude of frequencies are subject to differ-
`ent and unknown amplitude and phase changes intro-
`duced by the transmission channel, these channel prop-
`erties must be measured during the initiation phase of
`the communication process and prior to transmission of
`data. One example of this technique is disclosed by
`Hughes-Hanogs. Such methods are exceedingly com-
`plex and computationally intensive easily rivaling the
`cost and complexity of adaptive equalization. Further-
`more. such OFDM systems will not be effective for
`' direct MFM signalling in bandpass systems such as the
`60—]04 KHz example described above or in a prototype
`model of a UHF satellite sound broadcasting system as
`discussed by Alard et al in “A New System of Sound
`Broadcasting to Mobile Receivers", presented at the
`“Centre Commun d‘Etude de Telecommunication et
`
`Telediffusion“ in France and published by the 115515 in
`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 OFDM system disclosed by Alard et 3]. However,
`this method produces undesirable results when the baud
`interval is long. due to channel instability 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
`bands 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 modern disclosed by Gene C.
`Porter in “Error Distribution and Diversity Perfor-
`mance of a Frequency-Differential PSK l-IF Modem".
`IEEE TRANS. 0N COMMUNICATION TECH-
`NOLOGY, 16-4. August 1968, pages 567-575. While
`frequency differential encoding minimized many of the
`above described problems encountered with OFDM
`sy5tems, 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.
`SUMMARY OF THE INVENTION
`
`The present invention pmvides 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-
`
`10
`
`15
`
`20
`
`25
`
`35
`
`45
`
`55
`
`65
`
`5,166,924
`
`4
`tions channels. The present invention ftmctions in pack-
`et-switched, circuit-switched, or broadcast enviorn-
`ment and operates with either baseband or bandpass
`channels. An MFM digital signal waveform is gener-
`ated as a discrete time, i.e.. sampled data. representation
`of a desired MFM signal using an industry standard
`microcomputer, such as a personal computer or the like.
`equipped with a floating point array processor or a
`digital signal processing (DSP) chip and utilizing a
`computer software program. For signal transmission,
`the discrete time signal samples which are stored in
`random access computer memory (RAM) as digital
`words in a time domain array (TDA), are clocked from
`memory via a suitable input/output (I/O) port of the
`microcomputer at a clock rate which is a large multiple
`of the baud rate and which is at least twice the highest
`frequency to be sent in the MFM analog signal. The
`digital words are coupled to a digital-to-analog con-
`verter (DAC) as a serial data stream for conversion to
`the desired analog MFM signal for tranSmission.
`The computer program creates the discrete time sig-
`nal as follows. Digital data to be transmitted are ac-
`cepted from a message file 11 bits at a time, differentially
`encoded and converted to real and imaginary signal
`values in accordance with the chosen signal modulation
`constallation for each of the tones. Each encoded :1 bit
`work is stored in a position in the lower half of a com-
`plex valued frequency domain array (FDA). The cum-
`plex conjugate of the encoded value is stored in its
`image position in the upper half of the FDA. Each
`position in the array is assigned a position number
`which corresponds to a harmonic of the baud rate of the
`system. Only those array positions corresponding to
`desired tones in the MFM signal are filled with modula-
`tion values. All other array position values are set to
`zero.
`
`In the preferred embodiment. K encoded words are
`placed in adjacent array positions beginning at position
`k1+l and ending at position It] +K. Reference values
`for differential decoding are placed in position it]; this
`results in an analog signal strictly bandlimited to the
`hand between kl—l times the baud rate and k1+K+l
`times the baud rate. For example. a baud rate of 10 per
`second. a In of 3] and a K of 320 results in a modulated
`analog signal strictly bandlimited to the hand between
`300 Hz and 3520 Hz. A baud rate of 250 per second, k]
`of 241 and K of 174 results in a modulated analog signal
`strictly bandlimited to the hand between 60.000 Hz and
`104,000 Hz. A baud rate of 30 per second. a k] of 53'!
`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 “FDA is obtained by operating on the
`FDA with III
`inverse discrete Fourier
`transform
`(IDFI') algorithm. The values in the TDA are guaran-
`teed to be real because of the complex conjugate image
`symmetry established in the FDA. The total number of
`real values in the TDA. designated as k3, is the same as
`the total number of complex values in the FDA. In a
`preferred embodiment. It; is made a power of two and
`the IDFT is executed using a fast Fourier transform
`(FFT) algorithm. The "FDA contains the discrete time
`signal representation of one band of digitally encoded
`data that consists of the superposition of kx/Z-l 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
`
`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 DAC at a
`clock rate of ItJr times the baud rate.
`in the preferred embodiment where an adjacent sub-
`set of K of the k,/2—l available tones are modulated
`with information and the others given amplitudes of
`zero. nK bits are transmitted in each band. In the 10
`baud per second example containing 320 adjacent tones
`between 300 Hz and 3520 Hz, cited above, it; of 1024
`(210) leads to a clock rate of 10,240 Hz. With n=4 bits
`encoded into each tone. 1280 bits are sent with each
`band for a data rate of 12,800 bits/sec. In the 250 band
`per second example containing 174 adjacent tones be-
`tween 60 RH: and 104 I012 tones, ItJr of 1024 leads to a
`clock rate of 256 KHz. With n=2 bits encoded with
`each tone. 343 bits of information are sent with each
`band for a data rate of 87,000 bits/sec. In the 30 baud
`per second example containing 123 tones in the band of
`16,110 Hz to 19,980 Hz a kxof2048 leads to a clock rate
`of 61,440 Hz. With it: 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, and it is
`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 microeomputer
`consisting of the TDA of a synchronization baud fol-
`lowed by the TDAs of L data bauds. A packet transmits
`1.. bands of 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 tone for differentially
`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. 8qu
`delay through the channel is accounted for at the re-
`ceiver with the synchronization baud using a polarity
`only matched filter to establish the tinting reference for
`the received baud signal samples.
`One advantage of utilizing a very low baud rate. i.e.,
`loag baud intervals, is that the need for a guard time
`between bands, 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 energy is
`involved in the inter—baud interference. For example,
`over unequalized telephone lines the variation in delay
`for tones from 300 Hz to 3500 is only several millisec-
`onds. For bands of 100 milliseconds or more in length
`only a small percentage of the baud energy is 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
`
`10
`
`IS
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`6
`with more points are selected, a guard time equal to the
`group delay with zero signal values is inserted between
`bands 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 frequency as the transmit clock.
`Sample values are analog-to-digital (ADC) converted
`and stored in the receive personal computer memory in
`a receive TDA. The data are extracted from the TD?
`one band at a time. The receive computer program
`executes a 1:, point discrete Fourier transform (DPT)
`creating a receive FDA. Complex values from the posi-
`tion values in the FDA corresponding to the K+l
`tones in the MFM signal 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, :1
`bit words of the band. The entire packet is decoded by
`repeating the process for each of the L bauds.
`One advantage of differential encoding in frequency
`is that the receiver clock frequency need not be phase
`coherent with the transmit clock frequency. Further,
`small frequency offset errors, on the order of one part in
`105, are acceptable with no degradation in performance.
`The first baud in each packet is utilized as a synchroni-
`zation baud to establish baud synchronization. Because
`MFM signals have the statistical characteristics ofband-
`pass white noise.
`the autocorrelation function of an
`MFM signal with random input data has a very sharp
`spilte for its central peak. Thus, a polarity-only matched
`filter matched to a preselected synchronization band
`which generates a sharp spike at the end of the synchro-
`nization band may be used to initiate data transfer from
`the ADC to 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) channels in both the transmit and receive
`microcomputers using the byte transfer mode. For very
`high speed asynchronous operation. block DMA trans-
`fers are preferred.
`In some data communications settings, 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 channel 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 telephone circuits. In order to
`combat this problem, high-speed dial-up modems are
`equipped with echo cancellers. devices that remOve that
`component of a node‘s received signal that is due to its
`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
`MFM that achieves up to 75 db of rejection of near-end
`echo and up to 35 db of rejection 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 decode digital
`data utilizing discrete Fourier transform (DPT) 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 DPT 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 microeomputer is 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 terminal utilizing 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
`MFM signal can be controlled at the transmit FDA to
`provide equalization of the frequency-dependent signal-
`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 forms a part of the specification and in which:
`FIG. 1 is a diagram illustrating the relationship be-
`tween frequency and time for an MFM signal packet;
`FIGS. 2e and lb are conceptual black diagrams illus-
`trating the transmitter and receiver sections. respec-
`tively. for an MFM cummunication system according
`to the principles of the present invention;
`FIG. 3 is a diagram illustrating the complex envelope
`for one QPSK tone;
`FIGS. 40—40" are phase plot diagrams illustrating
`phase encoding for DQPSK encoding;
`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. In and
`5:
`
`the
`
`FIG. 7 is a functional block diagram of the receiver
`block shown in the system of FIGS. 26 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
`accordance with the principles of the present invention;
`
`10
`
`15
`
`20
`
`25
`
`35
`
`45
`
`50
`
`55
`
`65
`
`5,166,924
`
`8
`FIG. 13 is a flow diagram illustrating demodulation
`and decoding for mold-frequency differential quadra-
`ture phase shift keyed modulation in accordance with
`the principles of the present invention;
`FIG. 14:: is a diagram illustrating the transition states
`for multi-frequency differential
`Iii-quadrature ampli-
`tude modulation according to the principles of the pres-
`ent invention;
`FIG. 14b is a diagram illustrating the decoded phase
`values for the differential encoding strategy shown in
`FIG. 140:
`
`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 14b:
`FIG. 16 is a flow chart illustrating a transmit algo-
`rithm for use in the transmit microcomputer shown in
`FIG. 5;
`FIG. 1'! 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 used in the receive microcomputer shown in FIG.
`5.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`
`MIJLTI-FREQUENCY MODULATION
`
`Referring now to FIG. 1. an analog mold-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
`IQ: Baud length in number of samples
`L: Number of bauds per packet
`At: Time between samples in seconds
`fx= l/At: Sampling or clock frequency for digital—to-
`analog and analog-to-digital conversion in Hz.
`Af= VAT: Frequency spacing (minimum) between
`MFM tones.
`K: Number of MFM tones.
`
`Since At=AT/ltx. the sample frequency fx=ltthi
`Consequently, there are a maximum of m—l tones
`spaced at intervals of Af Hz between Af Hz and less
`than fxn Hz. the Nyquist frequency. that can carry
`amplitude and phase information during each band 15.
`Some. or many, of the tones may not be used (or equiva-
`lently have amplitudes of zero) during any or all bands
`of the packet. For example, to generate bandpass signals
`between frequencies f; and I}. only tones between har-
`monics k1=f1/Af and k2=lenfwill be allowed non-
`zero ampli