IEEE TRANSACTIONS ON COMMUNICATION

TECHNOLOQY, VOL. C O M - NO. ~~, 1,

FEBRUARY

1968

29

[dl N. Lazo and A. S. Martins, Central office modifications for eight detector and converter combinations with112 ARSs. touch-tone dialing, Bell Lab. Rec., vol. 39, pp. 437441, December I n either arrangement, the equipment quantities can be 1961. R. V. Burns and J. M. Hartz, Touch-calling provides highvaned tomeet individualconditions. speed control signaling, Automat. Elec. Tech. J., vol. 8, pp. 266-273, The average savings in time for a seven-digit call in October 1963. setting up a connection for a subscriber with a TONEDIAL telephone as compared to a rotary dial subscriber is 21/2seconds. This is attributable to the faster keying time, of course, coupled with the controlled outpulsing by the L. Kelly Armstrong was born in Noblesville, Ind., on January 12, converter. Greater time savings are possible by increasing 1920. HeattendedButler Univerthe outpulsing speed where the associated switching system folsity, Indianapolis, Ind., and, is capable of responding to higher speeds. It has also been lowing service in the U.S. Army, noted that these subscribers make less dialing errors than he attended Purdue University, do rotary dial subscribers. These advantages added to the Lafayette, Ind., where he received the B.S.E.E. degree in 1949. greater ease in dialing provide an attractive feature for the He joined Kellogg Switchboard telephone subscriber.

REFERENCES
R. N . Battista, C. G. Morrison, and D. H. Nash, Signaling system and receiver for touch-tone calling, ZEEE Trans. Communication and Electronics, vol. 82, pp. 9-17, March 1963. L21 M. L. Benson, F. L. Crutchfield, and H. F. Hopkins, Application of touch-tone calling in the Bell system, ZEEE Trans. Communication and Electronics, vol. 82, pp. 1-5, March 1963. L3] C. G. Morrison, Central office receiver for touch-tone calling, Bell Lab. Rec., vol. 39, pp. 201-204, June 1961.

and Supply Co., Chicago, Ill., where he designed circuits for manual telephone switchboardsfrom 1949 to 1952. Ele then joined StrombergCarlson Gorp., Rochester, N.Y., and has served as Circuit Designer, Project Engineer, and Engineering Supervisor in the design of dial telephone, automatic toll, and common control systems. He holds three patents on design of telephone equipment.

Adaptive Feedback Communications

REFERENCE :Hayes, J. F. :ADAPTIVE FEEDBACK COMMUNICATIONS, Purdue University, Lafayette, Ind. Recd 7/30/67. Paper 67TP977-COM, approved by the IEEE Communication Theory Committee for publication without oral presentation. IEEE TRANS. ON COMMUNICATION TECHNOLOGY, 16-1, February 1968,pp.29-34. ABSTRACT: A scheme for transmitting binary signals through a Rayleigh fading multipath medium is analyzed. The scheme envisions an adaptive receiver and a feedback channel. The feedback channel conveys information to thetransmitter on the forward channel state learned at the receiver. The transmitter uses this information to modify transmission. Results that show the improvement in performance of the system under the assumptions of perfect receiver learning and noise-free feedback are presented. In this-way, upper bounds on system performance are established.

INTRODUCTION
HE PROBLEM under study is the design of binary signals for transmission through a Rayleighfading multipath medium. The approach to the problem is, in essence, a fusion of two concepts that have appeared in
1 This research was supported by Joint Services under Contract N00014-67-A-226-0004 Mod. AB.

recent communication theoryliterature,adaptivityand feedback. In the system being considered, an adaptive receiver learns the present state of the channel. This information, presumably gleaned from past receptions, is employed in thedetection process. The informationon the channel state is also sent to the transmitter via feedback a channel. The role of this feedback information is to modify the transmitted signal in such a manner that the probability of error is minimized, subject to power constraints on the transmitted signal. The approach in this paper is to evaluate the performance of this adaptivefeedback system underideal conditions. Accordingly, analysis is carried out based on the assumptions that receiver learning is perfect and the feedback channel is delayless and noise free. The results indicate thecircumstances under which the adaptivefeedback technique is most promising. The results alsoshow the forms of transmitted signal and receiver that perform most effectively. This approach is similar to that of previous work that has been concentrated on adaptivity and feedback sepa-

30

IEEE TRANSACTIONS ON COMMUNICATION TECHNOLOGY, FEBRUARY

1968

MESSAGE SOURCE

*I

TRANSMITTER

xr(t,i)
L

FADING MULTIPATH MEDIUM

RECEIVER

MESSAGE SINK

4t),

FORWARD CHANNEL

FEEDBACK C H A N N E L

Fig. 1. Adaptive feedback system.

rately. The effect of receiver adaptivity has been studied by assuming perfect learning of the channel state in oneway systems.[11~[21 The potential of feedback in combating additive noise in the forward channel has been demonstrated by the work of T ~ r i n , [ ~ l Schalkwijk,[51~[61 ~[~l and Iiailath.[51 I n this paper the feedback channel was assumed to be delayless and noise free.
SYSTEM MODEL

state vector (coherent case) or sz (incoherent case). In the sequel we shall find the form of x*(t, si) which, in each case, minimizes the average probability of error subject to a constraint on the average transmitted power. Since the message rate is constant, a constraint on the average transmitted poweris equivalent to a constraint on the average energy per message.

The system under study is depicted in Fig. 1. I n characterizing the random multipath forward channel, the Turin For both the coherent and the incoherent case let us model[] is followed. I f the input to theforward channel is assume that the outputsof the message source are equally probable and that m(t) cos mot, its output is
j=1

AVERAGE TRANSMITTED ENERGY AND PROBABILITY OF ERROR

5 a,m(t

- r j ) cos [wo(t -

7,)

+ e,] + n(t>

(1)

E(&) =

LT
X@,)

x+Z(t, si)&

LT

x - y t , s,)dt,

1, 2.

(a)

where a,, e,, and 7, are the random gain, phase shift, and delay, respectively, in the jth multipath. n ( t ) is additive whiteGaussian noise with single ended power density spectrum N,. Theadditive noiseis independent of the multipath channel components a j , O j , and T ~j , = 1, 2, . . . , n. Each multipath is assumed to be resolvable, i.e., the effective duration of the transmitted signal is less than the differences in the delays of the separate paths. Finally, the multipath channel is assumed to be constant over several successive transmissions. Clearly, if any effective learning is to take place, this condition is necessary. At any instant of time, the state of the multipath is characterized by the vectorsa = (al, . . . , an), 0 = (01, . . . , e,), and 7 = (rl, . . . , rn). These vectors are learned at the receiver. I n this analysis, two levels of receiver learning are examined in turn. In the coherentcase the receiver learns the vectors a, 0, and 7, whereas in the incoherent case the receiver learns the vectors a and 7 . It is convenient to define the state vectors s1 = (al, . . . , a,, el, . . . , On, T ~ , . . . , 7,) for the coherent case and s 2 = (UI, . . . , a,, T ~. , . . , rn) for the incoherent case. In the sequel many of the steps of the analysis are the same for both cases. We denote the coherent case by the subscript i = 1 and the incoherent case by i = 2. The receiver employs these learned vectors sl or s2 to assist in the detection process. The channel state vectors are also fed back to the transmitter.2 Depending on the output of the message source, the transmitted signal is either x+(t, si) cos mot or x-(t, si) cos mot, i = 1, 2. Note that the transmitted signal is a function of the channel
2 As will be seen, it is not necessary to feed back the entirechannel state vector. The sum of the squares of the multipath gains is sufficient.

The cross correlation is denoted by

=ST
0

z+(t, s,)z-(t, Si)&,

1, 2.

(3)

If for agivenchannel

statethetransmitted

signal is

z+(t, si)cos mot, the transmitted energy is

E&)

1 2 E(s,),

1, 2.

(4) over the

The transmitted energypermessageaveraged channel states is

where p(si)is the multidimensional density functionof the channel state. The outputof the forward channel is
n

dt) =

C j=1

a j 4 -

T,,

si)cos

[wdt - TJ

+ e,] + n(t),
i
=

1, 2.

(6)

Since the multipathsin the forward channelare resolvable, we have from ( 2 ) and (6) the received signal energy for a given channel state

The cross correlation between the possible received signals for different messages is
X&,)
= 2 -

X@.) 2

aj2,

1, 2.

.j=l

HAYES:

ADAPTIVE FEEDBACK COMMUNICATIONS

31

Now in the coherent case, the signal component of g ( t ) [see (6) ] is completely known. Thus, thedetection problem is simply that of detecting known signals whose energy and cross correlation are given by (7) and (S), respectively, (i = 1 in this case). The probability of error for a given channel state is easily shown to be
PE(S1) =

We also have the obvious constraint

E(st) ~- - R(s,) 2 0, i

NO

1, 2.

I - e r f d X R ( s l )[I -

X(SJ

(9)

where

A peak power constraint is not considered on the transmitted signal, although the optimization technique can be extended to include this constraint. The derivation of the optimum signal is very similar in both the coherent and the incoherent case. The coherent case is considered first. We form

Averaging over all channel states, the average probability of error is

where f(sl) is the 3-n variate distribution of the channel states. From (10) it is clear that whatever the transmitted energy is, the probability of error willbe minimized if X(sl) = -1 for all sl,i.e., antipodal transmitted signals. From thispoint on it will be assumed that thetransmitted (17) I,(R) = 1 - e r f d Z R pR signals are antipodal in the coherent case. In theincoherent case it is assumed that the transmitted signals are orthogonal, i.e., h(s2)= 0 for all sz.Thus, from for any X 2 0. Differentiating successively with respect (8) the received signals areorthogonal. The probability to R we have of error for this case has been worked out by Pri~e.[*l~[~l For a given channel state, the probability of error is

where p is a Lagrange multiplier. I f R(s1) is such that 1 erfd2XR(sl) pR(sl) is minimized for each channel state sl, then L1is minimized. (Note that X, the sum of the squares of the channel gains, is specified by the channel state.) Thus L1 is minimized by minimizing

P E ( S Z= )
where

1 - exp [ - R ( s J X / ~ ] 2

(11)

d21x(R) -X 2 exp [-2RX] dR2

2 / x

From (19) it is seen that d21x(R)/dR2 2 0, and Ix(R) is a convex function of R. Thus, Ix(R) is minimum for
dIx --(R *) - - exp [-2R*X] dR*
or rearranging terms the implicit equation for R* is

Again the probability of error is computed by averaging over the channel states
I

pE2 = -

J,

exp [ - R ( s J x / ~ I ~ ( s J ~ s ~

(12)

where f(s2) is the 2n variate density function of the channel states. SIGNAL DESIGN In both cases considered, coherent and incoherent reception, we want to find transmitted signals that minimize the averageprobability of error [see (10) or (12)] subject to a constraint on theaverage transmitted energy

R*(X)

X exp [-2R*(X)X]
2 7rp2

Note that (15) is satisfied since

ETt

E(s,)f(s,)ds, 5 M,

i = 1, 2

(13)

where M is some prescribed energy level. It is convenient to work with an equivalent constraint on the signal-to-noise ratio. Thus

The Lagrange multiplier p was chosen such that (14) is satisfied with equality holding. It is not difficult to show that such a p can always be found given any M. We claim that of all transmitted signals whose average energy is equal to M , those specified by (20) minimize PE1.Suppose we have another candidate whose normalized energy is given by M as we have seen

M R1&-: * R(s,)f(s,)ds, I - = M , i = 1, 2.

f Js
6. f

N O

s,

[l - erf 42XR*(sl)

+ pR*(sl)]f(sl)dsl + pR(sl)]f(sl)dsl.

[ l - erf d 2 X R ( s l )

32

IEEE TRANSACTIONS ON COMMUNICATION TECHNOLOGY, FEBRUARY

1968

But R*(sl)and R'(sl) are such that

It is not difficult to prove that R ( X ) as given by (19) has the following properties.
1) R ( X ) is continuous and differentiable. 2 ) R(0) = 0. 3) R ( X ) attains a maximum of [ 2 p d Z exp 4) R ( X ) is unimodal with a maximum at X exp ('/2>. 5 ) For large X , R ( X ) log X / 4 X .

and therefore

(1/2)]-1.

= p

These properties indicate how the optimum signal achieves its economy of operation. The transmitted energy It is easy to see that the optimum signal just comes from the class such that (14) is satisfied withequality. If a is the highest in a middlerange of total channel gain. signal has energy less than M , then the probability of error When the channel gain is low, little energy is wasted in attempting to compensate. As the channel gain increases can be decreased simply by increasing R in (9). beyond X = p d ~ T exp 2 (1/2) the transmitted energy deThe analysis in thecase of incoherent reception proceeds creases as log X / X while the energy received increases as in much the same way. Again the Lagrangian is formed log x. 1 Note that in deriving the optimum transmitted signal, LZ = Js ds2f(s2) { exp [-R(sdXI pR(s2) (21) knowledge of the probability distribution of the channel Clearly, Lz is minimized if exp [ - R ( s z ) X ] pR(s2)is states was not required. It is only inthe computation of p , the Lagrange multiplier, thatthis knowledge is used. minimized for each channelstate. We form Assuming that the channel gains areindependentand J,(R) = exp [ - R X ] pR. Rayleigh distributed with density

[ l - erf d2XRr(sl)]f(sl)dsl.

1.

Differentiating successively with respect to R we have The distribution of

d2Jx(R) = X 2 esp [ - R X ] . dR2

From (23) it is seen that I&) is a convex function of R X . From (22) it is clear that I x ( R ) attainsa global minimum a t

is chi-square with n - 1 degrees of freedom. The density function of the random variableX is
zn--l exp [ - z / k 2 ]
fx(4 =

r(n)k2"

0 Iz <

m.

(27)

The average probability of error is But for X 5 p, R 5 0 and (15) is violated. However, since J x ( R ) is a convex function of R for any channel state within the region R 2 0, I, is minimized by R = 0. Thus we have the solution The average transmitted energy is

I n Fig. 2 P E is plotted as a function of 2k2Rl with n, the number of forward channel multipaths, as a parameter. For comparison purposes P E 1is also plotted as a function of the normalized signal-to-noise ratio 2k2R1,for the case where there is receiver learning of the channel state but EVALUATION OF SOLUTION no feedback. This corresponds to one of the cases examined The solutionto the signal design problem in the case of by Lindsey and Hancock.['l Curves for the no feedback coherent reception given by (19) has several interesting case are computedusing the same numericaltechnique properties. First of all, we note that it is a function onlyof used to compute the curves for the feedback case. It is seen that for the lower values of probability of X , the sums of the squares of the channel gains. For a given channel state, the feedback channel is required to error, the improvement in performance can be significant. For example, for n = 4 the feedback system requires 4 dB supply only one numberto the transmitter rather than the less average power to achieve a probability of error of 3-n numbers that specify the channel state.

As in the former case, p is chosen so that (14) is satisfied with equality. It is not difficult to show that such a value of p can always be found for any given M . Following the same line of reasoning as in the coherent case, one can show that P E 2is minimized by R*(X) given by (25).

HAYES: ADAPTIVE FEEDBACK COMMUNlCATIONS

33

----

FEEDBACK
NO FEEDBACK

n=NUMBERof MULTIPATHS

lo-
J I I I I l I l l l l l l l l l

t
I I I I J I I I I

\
I I I I I I I I I I I I I

16 -14

-12 -10

-8

-6 -4

-2

2 2k

IO

12

14

16

18

20

22

E2,d B

Fig. 2. Coherent case comparison curves.

Fig. 4. Incoherent case comparison curves.

--------

FEEL

-FEEDBACK

----NO

FEEDBACK

n=4

t
10-7

10-7

t t
0

1 1 1 1 1 1 1

\ \
1 1

\
1 1 1 1 , 1 1 1 1 1 1 1 1

-18 -16

-14

-12

-10

-8

-6 -4

-2

IO

12

14

16

18

5 -14 -12 -10

-8

-6

-4

-2

2
2

. 6

IO

12

14

16

18

20

2:

2kK-b d B

2k2R

dB

Fig. 3.

Coherent case cumnlative effect of adaptivity and feedback.

Fig. 5. Incoherent case cumnlative effectof adaptivity andfeedback.

We point out that thisimprovement is due to feedback alone since the comparison is madewithsystems having the same level of receiver learning. In Fig. 3 the cumulative effect of receiver learning andfeedback is illustrated. For the case n = 4, probability of error is plotted as a function of 2k2R for the following three cases: 1) nofeedback, receiver learning of r alone, and orthogonal transmitted signals;3
This curve was taken from Hancock and Lindsev.[1l
-LI

2 ) no feedback, receiver learning of a, 8, and r, and antipodal transmitted signals; 3) feedback, receiver learning of a, 0, and r, and antipodal transmitted signals. Note that if phase information is available at the receiver, no ambiguity will result i f antipodal signals are transmitted. Such is notthe case when the phase is unknown at the receiver. Comparing curves 1 and 2 it is seen that by learning a and 8, an advantage of approximately 6 dB results. Half of this improvement i s d u te o

34

IEEE TRANSACTIONS O N COMMUNICATION TECHNOLOGY, FEBRUARY

1968

differences in thecorrelation coefficient. Comparing curves 3 and 3 it is seen that theimprovement due tofeedback is a t least 4 dB for reasonable values of probability of error. The results for the case of incoherent reception are similar to those of coherent reception. Note thatthe transmitted signal energy is a function onlyof X , the sums of the squares of the channel gains. Averaging over X it is found that the average probability of error is

-[Xn-l exp (-X)]

r(

dX
exp ( - X )

In the course of analysis it was pointed out that the coherent case is simply the familiar problem of coherent detection of known binary signals. If a feedback link is available, it can yield improvement in performance over and above that already discussed, simply by applying the signal design worked out by T ~ r i n . [ ~ l ~ [this ~ ] Iapplican tion, the feedback channel would carry Turins uncertainty feedback signal as well asinformationon the channel state. For the case of uncerta,inty feedback, the deterioration in performance caused by feedback channel noise and delay js known.[lO1,[lll REFERENCES
J. C. Hancock and W. C. Lindsey, Optimum performance of self-adaptive systems operating through a Rayleigh-fading medium, IEEE -Trans. Communication Systems, vol. CS-11, PP. 443453, December 1963. R. Esposito, D. Middleton, and J. A. Mullen, Advantages of amplitude and phase adaptivity in the detection of signals subject to slow Rayleigh fading, IEEE Trans.Information Theory, vol. IT-11, pp. 473481, October 196.5. L3] G. L. Turin, Signal design for sequential det.ection systems with feedback, IEEE Trans. Information Theory, vol. IT-11, pp. 401-408, July 1965. I4], Comparison of sequential and nonsequential detection Information systems with uncertainty feedback, IEEE Trans. Theory, vol. IT-12, pp. 5-8, January 1966. f51 J. P. M. Schalkwijk and T. Kailath, A coding scheme for additive noise channels with feedback-part I : no bandwidth constraint, IEEE Trans.Information Theory, vol. IT-12, pp. 172183, April 1966. f61 J,. P. M. Schalkwijk, Coding scheme for addit.ive noise channels wlth feedback-part 11: band-limited signals, IEEE Trans. Information Theory, vol. IT-12, pp. 183-189, April 1966. [?I G. L. Turin, Communication through noisy randommultipath channels, 1966 I R E Conv. Rec., pt. 4, pp. 154-166. [a] R. Price, Error probabilities for adaptive multichannel reception of binary signals, I R E Trans. Information Theory, vol. IT-8, pp. 305-316, September 1962. Is] , Error probabilities for adaptive multichannel reception of binary signals, Lincoln Labs., M.I.T., Tech. Rept. 258, July 1962. [lo] J. F. Hayes,Studies of sequentialdetectionsystems with uncertainty feedback, Ph.D. dissertation, University of California, Berkeley, Calif., June 1966. [111 , Studies of sequentialdetectionsystemswith uncertainty feedback, IEEE Trans. Information Theory, vol. IT-14, pp. 63-7 1, January 1968.
fll

(30)
andthatthe avera,ge transmitted normalized energy is
R 2 =

exp ( - X ) X n - 2 * L m l o g( X / ~ P ) - dx. r(n)k2n

(31)

I n Fig. 4 P E 2is plotted as a function of 2k2Rz with n, the number of multipaths, as a parameter. For comparison P E 2is also plotted as a function of 2k2R2 for a systemwhose receiver learns a and c but which has no feedback link. Again for reasonably low values of probability of error, feedback provides a significant improvement in performance. For example, for a probabilityof error of 10-4 there is a 4 dB improvement in performance. The cumulative effect of learning in the incoherent case is shown in Fig. 5 where the probability of error is plotted as a function of 2k2R2ratio for the following cases: 1) no feedback, receiver learning of c alone, and orthogonal transmitted signals; 3) no feedback, receiver learning of a and e, and orthogonal signals; 3) feedback, receiver learning of a and e, and orthogonal signals. A comparison of curves 1 and 2 confirms the result of Hancockand Lindsey[] that learning the gain in each multipath does not significantly improve performance. A comparison of curves 2 and 3 shows that if a feedback channel is available, learning of the multipath gains can significantly improve performance.
,

CONCLUSION As we have seen, for low enough probability of error, the adaptivefeedback technique can improveperformance significantly over systems employing the adaptive feature alone. This improvement is predicated on the assumption of noise-free, delayless feedback. Ultimately the validity of this assumption is intimately related to the time constant of the multipath component of the forward channel. It is recalled, that for a given channel state, only the sum of the squares of the channel gains was fed back. I f this number varies slowly compared to the rate of transmitting information, then the capacity of the feedback channel can be far less than that of the forward channel. Further, if the time constant is large compared to the delay in the feedback channel, then the transmittersknowledge of the current channel state is up-to-date.

Jeremiah F. Hayes (S65-N161)was born in New York, N. Y., on July 8, 1934. He received the B.E.E. degree from Manhattan College, New York, N.Y., in 1956. He received theM.S. degree in mathematics from New York University, New York, in, 1961, and the Ph.D. degree in electrical engineering from the University of California; Berkeley, Calif., in 1966. From 1956 to 1960he was a RilemBell ber of the Technical Staff at the Telephone Laboratories, Inc., Murray Hill, N. J . He worked atthe Columpia University Elect.ronics Research Laboratories, New York, N. Y., from 1960 to 1962. Presently he is an Assistant Professor of Engineering a t Purdue University, Lafayette, Ind. During the summer of 1967 he was employed by the Jet Propulsion Laboratory, California Institute of Technology, Pasadena, Calif. Dr. Hayes is a member of Eta Kappa Nu, Sigma Xi, and the America11 Association of University Professors.