Minimization of Excess Bandwidth in Pulse Amplitude Modulated Data Transmission

The invention is concerned with data transmission over bandlimited communications channels.

Transmission channels such as, e.g., telephone connections, microwave systems, and radio links are subject to a variety of frequency dependent intrinsic impairments or extraneous disturbances. For example, in a voiceband telephone channel, impairments such as amplitude attenuation and phase distortion are relatively low at frequencies in the range of approximately 0.4-2.8 kHz but exhibit rapid increase at frequencies below and above this range. Consequently, in order to avoid undue distortion of signals during passage through a telephone channel, transmission of voice or data preferably is limited to frequencies in a suitably restricted range.

While restriction of frequency range is virtually mandated by inherent physical limitations of the typical telephone channel, such restriction may be used to economic advantage in systems which are physically less severely limited. For example, in a microwave or optical communications system, so-called frequency division multiplexing permits the simultaneous operation of several communications channels over one and the same physical facility when non-overlapping portions of the available spectrum are assigned to different communications channels. It is evident that minimization of frequency range assigned to individual channels may lead to an increase in the number of multiplexed channels.

In the case of data communications, there is an additional and paramount concern with transmission rate as limited by bandwidth. From the theoretical work of H. Nyquist it is well known that, in order to transmit numbers at a rate .rho. per second by pulse amplitude modulation, bandwidth of at least .rho./2 Hertz is required. Moreover, use of such minimal bandwidth, conveniently designated Nyquist bandwidth, depends on a number of idealizing assumptions regarding pulse shape and channel properties whose physical implementation is not practical. Pulse shape, in particular, is ideally required to have a perfectly rectangular spectrum of constant nonzero amplutide for frequencies within the frequency band and constant zero amplitude for frequencies outside the band. Such ideal spectrum corresponds to a pulse of the form (sin x)/x which may be approximated but not exactly realized in practice.

Physically realizable pulses which are suitable for pulse amplitude modulation are shown, e.g., in the book by R. W. Lucky et al., "Principles of Data Communications", McGraw-Hill, 1968 on page 51, in the book by William R. Bennett et al., "Data Transmission.revreaction., McGraw-Hill, 1965 on page 56, and in U.S. Pat. No. 2,719,189 (issued on Sept. 27, 1955 to W. R. Bennett et al., "Prevention of Interpulse Interference in Pulse Multiplex Transmission"). Such pulses are characterized by a frequency spectrum which has a frequency interval in which amplitude is a nonzero constant and a so-called roll-off interval of frequencies at which amplitude decreases to zero smoothly and symmetrically with respect to the halfway point. Resulting pulses are known as Nyquist pulses and, at the price of additional bandwidth, are actually superior for purposes of data transmission based on pulse amplitude modulation. An often used Nyquist pulse is the so-called raised cosine pulse shown in the references cited above.

In a conventional pulse amplitude modulated data transmission system, data symbols .alpha..sub.j having 2.sup.L values or levels are represented by pulses whose amplitude at time jT is directly proportional to .alpha..sub.j, T being a fixed time interval between pulses transmitted. For example, if L=1, then, typically, the .alpha..sub.j 's are +1 or -1. Since the resulting signal is a linear combination of time translates of a single pulse, the bandwidth of the signal is equal to the bandwidth of the pulse which, ideally, can be as narrow as 1/(2T). However, due to roll-off as described above, an "excess bandwidth" of at least 10-20 percent is required in practice. In the case of a telephone channel, for example, transmission can be achieved at a rate of 9.6.times.10.sup.3 bits/second using 4-level pulse amplitude modulated signals and corresponding to an ideal bandwidth of 2.4 kHz. However, allowing for 12 percent excess bandwidth, the transmitted signal occupies a frequency range which extends from approximately 0.36 to approximately 3.05 kHz.

While it is possible to transmit data items .alpha..sub.j one at a time, actual transmission systems often use some form of data encoding based on groups of a fixed number .nu. of data items. For example, a simple encoding scheme used in error detection consists in forming the sum (modulo 2) of a block of .nu. binary data items and appending it as an (n+1)-st item to the block. Thus, for each .nu. data items, N=.nu.+1 signals are transmitted and, at the expense of a slight reduction in data rate, information is supplied to the receiver which allows the detection of a transmission error.

Encoding may be used for purposes other than error detection such as, for example, to convert a 2-level signal into a 3-level signal in duobinary systems disclosed on pages 83-88 of the book by Lucky et al. cited above. Also, according to U.S. Pat. No. 3,388,330 (issued June 11, 1968 to E. R. Kretzmer) and as described on pages 88-92 of the book by Lucky et al., encoding may be used to achieve desirable frequency characteristics in so-called partial response systems.

The invention is a method for encoding blocks of multilevel data signals so as to minimize excess bandwidth required to transmit the encoded signal over a transmission channel such as, e.g., a telephone, radio, microwave, or optical communications channel. According to the invention, a block of .nu. data signals is encoded into a larger number N of signals which are obtained as a linear combination of .nu. characteristic sequences known as discrete prolate spheroidal sequences. By judicious choice of N, .nu., and an additional parameter W, excess bandwidth is reduced to less than 10 percent and may be as low as 2-4 percent. As a result of such minimization, fidelity of transmission over bandlimited channels is enhanced and/or the number of frequency-division multiplexed channels is maximized.

FIG. 1 is a diagram of amplitude versus frequency corresponding to the baseband spectrum of a Nyquist pulse used in conventional pulse amplitude modulated data transmission systems.

FIG. 2 schematically shows general features of a transmission system.

FIG. 3 schematically shows general features of a receiving system.

FIG. 4 schematically shows general features of an encoder for use in a transmission system according to the invention.

FIG. 5 schematically shows general features of a decoder for use in a receiving system according to the invention.

It is a purpose of the invention to provide encoding and corresponding decoding techniques for use in pulse amplitude modulated data transmission systems. The encoding technique may be motivated by the desire to minimize excess bandwidth in situations where 10-20 percent excess bandwidth of conventional methods is considered excessive. Conversely, the aim may be to maximize data rate .rho. for prescribed bandwidth F.

FIG. 1 shows the baseband spectrum of a pulse used in pulse amplitude modulated data transmission systems to have a frequency interval from 0 to (1/T)-F.sub.o in which amplitude has a constant value A.sub.o and an adjoining roll-off interval from (1/T)-F.sub.o to F.sub.o in which amplitude decreases to zero smoothly and symmetrically with respect to the midpoint whose frequency and amplitude coordinates are 1/(2T) and A.sub.o /2, respectively. Excess bandwidth as discussed above is represented by the interval from 1/(2T) to F.sub.o.

FIG. 2 shows components as are typically present in a data communications transmission system, namely data source 21, transmitter 22 consisting of encoder 23 and modulator 24, and channel 25. Typically, data produced by data source 21 are multi-level rectangular electrical pulses which, in the simplest case, are binary signals. More generally, data signals may have 2.sup.L distinct levels, L being a small number such as, e.g., 2, 3, or 4. Data may represent letters or real numbers and may have been obtained by sampling an analog signal. Description of the invention is most convenient in terms of baseband signals, in which case the function of modulator 24 is merely to produce baseband limited pulses whose amplitude is proportional to signals produced by encoder 23. It is understood, however, that in practice an additional step of translation to a passband frequency interval is involved.

FIG. 3 shows components as are typically present in a data communications receiving system, namely transmission channel 31, receiver 32 consisting of sampler 33, equalizer 34, decoder 35, and slicer 36, and data sink 37. Equalizer 34 may be, e.g., a tapped delay line or a digitalized transversal filter as disclosed in U.S. Pat. No. 3,315,171 (F. K. Becker).

FIG. 4 shows components of an encoder comprising read-only memory 41, multiplication unit 42, adding units 43 and 43', accumulators 44 and 44', and switches 45 and 46. Signals .alpha..sub.j arrive from a data source, numbering of signals conveniently being taken modulo an integer number .nu. which defines block length. Memory 41 holds a .nu. by N array of entries .phi..sub.j,n, where j runs from 1 to .nu. and n from 1 to N. For any j from 1 to .nu., multiplication unit 42 is capable of simultaneously multiplying all N entries .phi..sub.j,n (n from 1 to N) by a data item .alpha..sub.j. Depending on the position of switch 45 the resulting products are added by adding units 43 or 43' to accumulators 44 or 44', respectively. Upon completion of the .nu.-th additions, accumulators 44 or 44' contain items a.sub.n and a.sub.n ', n from 1 to N, which represent signals encoded according to the invention. Switch 46 is synchronized with switch 45 to allow transmission of the contents of accumulators 44' while additions are made as shown to accumulators 44 and vice-versa. Each time switches 45 and 46 change position, accumulators 44 or 44' about to be connected to multiplication unit 42 are reset to zero. As a result of computations involving .alpha.'s and .phi.'s as described, each sequence (a.sub.n, n from 1 to N), is a linear combination of sequences (.phi..sub.j,n, n from 1 to N), and associated multipliers .alpha..sub.j.

Design of multiplication unit 42 may take advantage of the limited number of levels of signals .alpha..sub.j. E.g., in the case of binary signals .alpha..sub.1 =1 and .alpha..sub.2 =-1, multiplications are dispensable entirely and unit 42 functions merely to associate a sign.

FIG. 5 shows components of a decoder as may be used as a counterpart to the encoder shown in FIG. 4. Signals a.sub.n arrive, e.g., from an equalizer, numbering of signals conveniently being taken modulo N. The decoder comprises read-only memory 51, multiplication unit 52, adding units 53 and 53', accumulators 54 and 54', and switches 55 and 56. Memory 51 holds an N by .nu. array of entries .phi..sub.j,n, where j runs from 1 to .nu. and n from 1 to N. Multiplication unit 52 is capable of simultaneously multiplying, for any n from 1 to N, all .nu. entires .phi..sub.j,n (j from 1 to .nu.) by a data signal a.sub.n. Depending on the position of switch 55, the resulting .nu. products are added by adding units 53 or 53' to accumulators 54 or 54', respectively. Upon completion of the N-th additions, accumulators 54 or 54' contain items .alpha..sub.j or .alpha.'.sub.j, j from 1 to .nu., which represent signals decoded according to the invention. Switch 56 is synchronized with switch 55 to allow transmission of the contents of accumulators 54' while additions are made as shown to accumulators 54 and vice-versa. Each time switches 55 and 56 change position, accumulators 54 or 54' about to be connected to multiplication unit 52 are reset to zero. As a result of computations involving a's and .phi.'s as described, each sequence (.alpha..sub.j, j from 1 to .nu.) is a linear combination of sequences (.phi..sub.j,n, j from 1 to .nu.) and associated multipliers a.sub.n.

It is noted that, while signals denoted a.sub.n in the descriptions of FIGS. 4 and 5 above are ideally the same, signals a.sub.n of FIG. 5 will differ in practice from signals a.sub.n of FIG. 4 due to distortion suffered in the course of transmission. For the sake of simplicity of description, such difference is not reflected in the notation. Similarly, signals .alpha..sub.j obtained upon decoding are different from original data signals .alpha..sub.j and, in particular, have to undergo a so-called slicing operation which results in the recovery of discrete levels. A detailed description of circuitry designed for slicing is given in U.S. Pat. No. 2,537,843 (issued Jan. 9, 1951 to L. A. Meacham, "Pulse Regeneration Apparatus").

Computations described above may be carried out by digital circuitry implementing multiplication units 42 and 52 and adding units 43, 43', 53, and 53'. Alternately, such units may be implemented by analog devices such as e.g., variable gain and operational amplifiers, choice of devices being influenced by practical considerations based, e.g., on data type and physical implementation of read-only memories 41 and 51.

In the following, F denotes the bandwidth as available or desired for the transmission of data signals having 2.sup.L levels. Thus, ideally, bit rate is as high as 2FL. It is an aim of the invention to encode signals so as to allow transmission at a rate .rho. only slightly less than such ideal rate.

According to the invention, entries .phi..sub.j,n in read-only memories 41 and 51 are determined as follows: for any integer number N, N discrete prolate spheroidal sequences (DPSS's for short), each consisting of N numbers, may be defined as a function of a parameter which is a number greater than 0 and less than 1/2. This parameter is denoted by W and is related to time interval T and bandwidth F by the relationship W=FT. Typically, bandwidth F is a given characteristic of a transmission channel and T and W are chosen such that W is less than 1/2. The smaller T, the easier the realization of pulses suitable for pulse amplitude modulation by encoded signals, but the greater also the rate of doing arithmetic required for encoding and decoding. In terms of N and W, a set of DPSS's is defined as a set of orthonormal eigenvectors of the N by N matrix whose (m,n)-entry is .gamma.(m,n)=sin (2.pi.W(n-m))/.pi.(n-m). In the following, this N by N matrix is denoted by K. It can be shown that the N eigenvalues of the matrix K all lie in the interval from 0 to 1 and that their sum equals 2WN. In fact, when N is sufficiently large, approximately 2WN of these eigenvalues are approximately equal to 1 and the remainder are approximately equal to zero. According to the invention, the number .nu. is preferably chosen about equal to the number of eigenvalues which are approximately equal to 1 and the eigenvectors associated with such eigenvalues are chosen as the desired DPSS's in terms of which given data signals are encoded by linear combination as described above.

If, for the sake of convenience, eigenvalues .lambda..sub.j are numbered in decreasing order, .nu. is preferably chosen as large as possible subject to the condition that .lambda..sub.j (j from 1 to .nu.) to close to 1. More specifically, .nu. may be chosen subject to the condition that the value of the expression Q=.SIGMA.(1-.lambda..sub.j)/.nu. be less than a suitably small threshold such as, e.g., 10.sup.-4. The significance of such test lies in that error introduced into a signal due to encoding may generally be bounded in terms of Q and that, as a consequence, Q should preferably be small.

Pulses used for pulse amplitude modulation may be Nyquist pulses or, more generally, any pulses whose baseband spectrum is such that at frequencies less than or equal to F, amplitude is essentially equal to T and at frequencies greater than 1/T-F, amplitude is essentially zero. What is required for frequencies in the roll-off interval from F to 1/T-F is merely that amplitude not exceed a finite bound such as, e.g., T. Thus, in particular, roll-off need be neither smooth nor symmetrical.

The invention, described above in terms of encoding data signals and transmitting the encoded signals by modulating conventional pulses, may be interpreted alternately as a method of transmitting data signals by modulating specially tailored waveforms. In particular, each .alpha..sub.j modulates a waveform g.sub.j and the transmitted signal is an additive superposition of the resulting waveforms.

Whether viewed as produced by encoding followed by amplitude modulation of conventional pulses or by amplitude modulation of specially selected waveforms, the resulting baseband signal may be converted into a passband signal by standard methods such as, e.g., vestigial sideband modulation or quadrature amplitude modulation. The latter, in particular, may be conveniently used to translate two independent baseband signals x(t) and y(t) into a passband signal z(t) having frequencies in the frequency interval from F.sub.1 to F.sub.2 by means of the following procedure: set F=(F.sub.2 -F.sub.1)/2, choose T less than 1/2F, define F.sub.c =(F.sub.1 +F.sub.2)/2, and form z(t)=x(t) cos 2.pi.F.sub.c t+y(t) sin 2.pi.F.sub.c t.

Recovery of original signals x(t) and y(tj) from z(t) may be by so-called homodyne demodulation as described on page 178 of the book by Lucky et al. cited above. Since demodulation requires knowledge of carrier phase and frequency by the receiver, such information is preferably transmitted to the receiver, e.g., by means of a tone.

Instead of encoding data .alpha..sub.j in terms of baseband DPSS's as described above, it is alternately possible to use passband DPSS's which may be defined as follows: Instead of choosing a single parameter W as defined above, two parameters W.sub.1 and W.sub.2 are chosen such that W.sub.1 is less than W.sub.2 and such that W.sub.1 and W.sub.2 lie in the interval from 0 to 1/2. Elements .gamma.(m,n) of a matrix K are defined by .gamma.(m,n)=(2/.pi.k) cos (.pi.(W.sub.2 +W.sub.1)k) sin (.pi.(W.sub.2 -W.sub.1)k), where k=n-m. Passband DPSS's are obtained as eigenvectors of the matrix K as described above.

Use of passband DPSS's allows the direct generation of passband signals which do not require transformation from baseband to passband. Alternatively, encoding in terms of passband DPSS's may be used in combination with an additional transformation in order to reserve a narrow frequency range for the transmission of one or several tones at frequencies near the midpoint of the passband. This may be achieved, e.g., by quadrature amplitude modulation of a signal encoded in terms of passband DPSS's.

While DPSS's are defined as eigenvectors normalized to Euclidean length 1, use of sequences which are normalized differently is also within the scope of the invention. It is evident that encoding data in terms of sequences obtained by multiplying DPSS's by a nonzero scalar c is equivalent to multiplying data signals by c followed by encoding in terms of DPSS's. Correspondingly, decoding by means of sequences obtained by dividing DPSS's by c is also within the scope of the invention.

Encoding and decoding according to the invention may also be compatible with other encoding schemes and, consequently may be used in combination. For example, the new technique may be used in combination with error correction and detection codes based on appending check sums to data blocks.

Numerical computation of the desired eigenvectors and eigenvalues of the matrix K may be carried out by any of a number of standard methods of computational linear algebra such as, e.g., methods associated with the names of Jacobi, Givens, Householder, and Francis and as described, e.g., by J. H. Wilkinson, "The Algebraic Eigenvalue Problem", Clarendon Press, 1965. Programs implementing these algorithms are given by C. Reinsch et al., "Linear Algebra", Springer, 1971 and may also be conveniently available in the form of library subroutines on scientific computing equipment. For the sake of illustration, Table 1 shows 3-digit approximations of eigenvalues .lambda..sub.j computed for the case N=50 and W=1/4. Inspection of Table 1 allows verification that, since 2WN=N/2 in this case, about half of the .lambda..sub.j 's are about equal to 1 and the remainder about equal to zero.

Calculations involving .alpha.'s , .phi.'s, and a's may be conveniently carried out in fixed or floating point arithmetic. It is understood that, in practice, finite precision values .phi..sub.j,n merely approximate the elements of DPSS's, quality of the approximation being dependent on precision used in the computation of .phi.'s as well as on precision used for their representation in read-only memory. Furthermore, accuracy of encoded sequences obtained by encoding in terms of .phi.'s depends on the accuracy of arithmetic used in carrying out computations described above. While 10-bit accuracy may generally be sufficient for encoding and decoding, and while even greater accuracy may be desirable, lesser accuracy is not precluded.

For the computation of elements .phi..sub.j,n of DPSS's for N up to about 100 by means of a numerically stable implementation of one of the algorithms mentioned above, single precision floating point arithmetic may be sufficient as available on scientific data processing equipment.

The following example illustrates the efficacy of the disclosed method for minimizing excess bandwidth.

Transmissions of 2.sup.L -level signals results in a bit rate over the channel of .rho.=(.nu./N)(L/T) and a bandwidth of F=W/T=(.rho./2L) (2WN/.nu.). If W=0.415, N=80, and .nu.=64, then the ratio 2WN/.nu.=1.0375, which implies that bandwidth required in excess of the ideal bandwidth of .rho./2L is a mere 3.75 percent.

If 1/T=6.times.10.sup.3 per second, F=2490 Hz, and L=2, then rho=9.6.times.10.sup.3 bits/second. For the sake of comparison, this bandwidth F may be contrasted with a bandwidth of 2686 Hz required to transmit the same signals at the same rate by prior art direct modulation of Nyquist pulses and allowing for 12 percent excess bandwidth.