Digital Communications Tree Searching Detection

The proliferation of digital communications has spurred interest in achieving higher data rates. In the absence of bandwidth restrictions, this may be easily accomplished without noticeable degradation in detection performance. However, when there is a need to conserve bandwidth so as to maximize the number of available channels such as in telephone and satellite communications, the data rate cannot be easily increased without adversely impinging on the detection performance. For example, each time the data rate is increasing by doubling the number of levels a carrier signal can assume, the signal-to-noise ratio required to support a selected error rate is normally reduced about 6 dB.

A tree searching algorithm was developed by Andrew J. Viterbi which applies a probability technique to convolutional codes to enhance the error detection and correction performance thereof. This technique is discussed in the technical literature including two papers which appeared in the October 1971 IEEE Transactions on Communication Technology entitled "Convolutional Codes and Their Performance in Communication Systems" and "Viterbi Decoding for Satellite and Space Communication" appearing at pages 751 and 835, respectively. Although this technique addresses detection performance, it does so in the context of convolutional codes which are designed to minimize errors and notoriously do not afford bandwidth conservation.

With the foregoing in mind, it is a primary object of the present invention to provide a new and improved means of digital communications through tree searching detection.

It is a further object of the present invention to provide such a new and improved means of digital communications tree searching detection which optimizes bandwidth conservation.

The foregoing objects as well as others and the means by which they are achieved may best be appreciated by referring to the Detailed Description of the Invention which follows hereinafter together with the appended drawings.

In accordance with the objects of the invention, digital data is correlatively encoded into discrete plural states and then transmitted by modulating a carrier whose phase during each baud interval is a function of the data. The data is detected by demodulating the transmitted signal to obtain the baseband signal containing the data and recursively measuring the probability of the baseband signal being in each of the possible states. The probability of being in each state is determined by computing the probability of traversing each possible path into the state, designated the transition metric and adding it to the probability associated with being in the prior state, designated state metric, from which the path originated to arrive at a path metric. The transition metric is determined by taking the dot products of the baseband signal and a reference signal generated therefrom through a differential scheme in which the reference signal in each baud interval corresponds to the estimated or actual baseband signal of the immediately preceding baud interval or an absolute scheme where the reference signal tracks the baseband signal. Each state metric is chosen to be the maximum of its path metrics, designated survivor metric, and is used as the prior state metric for the next baud interval. A data bit stream is generated for each state which consists of the data bit stream generated for the prior state in the previous baud interval corresponding to its survivor metric less the oldest bit thereof and a newest bit whose value is that of the digital bit associted with the survivor metric path as determined from the encoding and modulation employed. It has been shown (see "Convolutional Codes . . . " IEEE Article previously alluded to) that when the number of bits in the data bit stream is about six times the constraint length of the encoder register, the oldest bit for all of the state data bit streams will be the same and indeed equal to the transmitted data bit.

Bandwidth conservation is assured by correlatively encoding the data into three levels which are then employed to frequency modulate a carrier signal having a center frequency f.sub.c and upper and lower frequencies equal to f.sub.c .+-. .DELTA. f where .DELTA.f is equal to one-quarter of the data rate so that during each baud interval the carrier signal shifts 0.degree. , + 90.degree., or -90.degree.. The correlative encoding, which makes the encoder output dependent on the previous data bit, introduces a memory factor into the digital communications which then renders the Viterbi algorithm eminently suited to the tree searching detection herein.

FIG. 1 is a block diagram depicting a typical digital communications system employing the tree searching detection of the invention.

FIG. 2 is a state diagram and associated chart for the correlative encoder employed in the transmitter of the system of FIG. 1.

FIG. 3 is a tree diagram derived from the state diagram of FIG. 2 expository of the tree searching technique.

FIG. 4 is a phasor diagram together with associated charts showing how the dot products of the baseband and reference signals are generated to compute the transition metric of the various paths into each state.

FIG. 5 is a detailed drawing of a differential implementation for computing the dot product wherein the baseband signal during each baud interval is used as the reference signal in the next succeeding baud interval.

FIG. 6 depicts a second differential implementation for generating the dot product entailing decision regions and an estimate of the reference signal to simplify the dot product circuitry.

FIG. 7 is a flow diagram for the algorithm to implement the decision region approach of FIG. 6.

FIG. 8 depicts the simplified dot product circuitry used in the second implementation of FIG. 6.

FIG. 9 is a four-state tree diagram which is applicable to a third dot product implementation employing an absolute reference to also simplify the dot product circuitry.

FIG. 10 is a block diagram for the tree searching detection applicable to the absolute reference implementation of FIG. 9.

Although, as will be appreciated hereinafter, the invention has broad applications, it will be described in connection with a specific encoding and modulation scheme to facilitate its exposition herein. Accordingly, FIG. 1 depicts a digital encoder 10 for encoding the input digital data a.sub.k which may assume a binary logic level one ("1") or zero ("0"). Digital encoder 10 comprises a shift register such as D-type flip-flop 12 which is clocked at the data rate R and which receives the digital input data a.sub.k on its D-input lead via the output a' .sub.k of an exclusive OR gate 14. Correlative encoding is afforded by applying the Q output a' .sub.k-1 of flip-flop 12 as the second input to exclusive OR gate 14 thereby rendering the encoder 10 output a function of the previous received input data. It is this memory feature which renders the tree searching algorithm developed by Viterbi previously alluded to under Background of the Invention eminently suitable for detection purposes. The signals a' .sub.k and a' .sub.k-1, which will be assumed equal to 1 volt for a "1" and zero volts for a "0" only for expediency, are summed in an operational amplifier 16 by application to its positive (+) input via respective resistors 18 and 20. The output of operational amplifier 16, y.sub.k , which is equal to the difference between the sum of a' .sub.k and a' .sub.k-1 and one volt which is applied to the negative (-) input of amplifier 16 is applied to a voltage controlled oscillator (VCO) 22 to control its output frequency (f). The frequency f may assume any one of three different values dependent on the value of y.sub.k which may be 0 or .+-. 1. A voltage of 0 causes the VCO 22 to produce an output frequency f.sub.c while a voltage of 1 volt shifts its frequency in the same direction as the voltage polarity by .DELTA.f, preferably equal to one-quarter of the data rate R. Thus -1 volt reduces f.sub.c by R/4 and +1 volt increases it by R/4, causing a continuous and uniform 90.degree. phase shift in the baseband signal or complex envelope over the transmission time for each data bit or baud interval [.DELTA..theta./baud = 2.pi. .DELTA.fT (T=baud interval) = 2.pi. (1/4T)T = .pi./2 where .DELTA.f = R/4 & R = 1/T]. This is a modified arrangement of a modulation scheme known as minimum shift keying (MSK) which is described in detail in U.S. Pat. No. 2,977,417 entitled "Minimum Shift Data Communication System." That system employs two levels of frequency which requires a baseband signal 90.degree. phase shift in each baud interval and permits transitions between plus and minus phase shifts in consecutive baud intervals, while the subject modulation entails three levels of frequency with the center frequency f.sub.c affording a baseband signal phase shift of 0.degree. and the encoding precludes a transition between plus and minus phase shifts without first passing through one baud interval of 0.degree. phase shift, thus avoiding discontinuities at baud interval transitions which results in the desired bandwidth conservation.

In the encoder state diagram of FIG. 2, the circles labeled S.sub.o and S.sub.1 represent respectively the "0" and "1" states for a'.sub.k-1. During any given baud interval the encoder state a'.sub.k-1 is determined by the encoder state and digital bit value a.sub.k of the immediately preceding baud interval (correlation factor). Using the table accompanying the state diagram, it will be readily seen that if the encoder were in state S.sub.o in baud interval k-1 and the digital bit value for the input data a.sub. k was "0", the encoder would remain in that state during the next baud interval k represented by the arrow returning upon itself for S.sub.o, producing a y.sub.k of -1 and an f of f.sub.c - R/4 at the output of VCO 22. It will be further seen that if the encoder state were S.sub.1 while a "0" were received for a.sub.k, the encoder would likewise remain in the same state, the arrow returning upon itself to the S.sub.1 circle. However, once again referring to the table, y.sub.k would assume a +1 value and the frequency of the VCO 22 would be f.sub.c + R/4. Irrespective of the encoder state, a digital bit value for the input data a.sub.k of "1" produces a change of encoder state during the ensuing baud interval. In this case, y.sub.k assumes a value of zero and the VCO 22 output frequency f a value of f.sub.c. Notice that it is not possible to change between f.sub.c - R/4 and f.sub.c + R/4 without first passing through f.sub.c for at least one baud interval.

As previously mentioned, the tree searching algorithm propounded by Viterbi examines the probability of being in a particular state by looking at the various individual paths which lead into that state. FIG. 3 is a tree diagram for the receiver baseband signal after extracting the carrier through demodulation corresponding to the transmitted baseband signal associated with FIG. 2, and in fact would be the same in the absence of corruption caused by noise. Referring now to FIG. 3, if at time t.sub.k for baud interval K, the baseband signal was in state S.sub.o represented by circle 24 it could have arrived there over the top horizontal path from state S.sub.o, reprepresented by circle 26, in the previous baud interval corresponding to time t.sub.k-1 if a.sub.k were equal to "0" or over the diagonal path from state S.sub.1 in the previous baud interval, represented by circle 28, if a.sub.k were equal to "1". Similarly, if the baseband signal in the K baud interval were in the state S.sub.1, represented by circle 30, then it could have arrived there via the lower horizontal path from prior state S.sub.1 (circle 28) if a.sub.k were equal to a "0" or over the diagonal path from prior state S.sub.o (circle 26) if a.sub.k were "1". In accordance with the Viterbi algorithm, one selects the most likely path into each state S.sub.o (circle 24) and S.sub.1 (circle 30) by examining all the possible paths (tree branches) thereinto and selecting the one thereamong having the maximum probability. For example, looking at S.sub.o (circle 24), the probability of being in that state is equal to the probability of being in the prior state S.sub.o designated as prior state metric or M.sub.k-1 (0) plus the probability of traversing the top horizontal path which originated from that prior state, designated transition metric or T.sub.1 (0). This sum may be referred to as the path metric. The probability of entering state S.sub.o (circle 24) from state S.sub.1 (circle 28) over the diagonal path is equal to the prior state metric M.sub.k-1 (1) associated with the latter plus the transition metric T.sub.2 (0). Whichever one of these two path metrics affords the larger probability generates a survivor decision metric .delta..sub.k-1 (0) for state S.sub.o which identifies the most likely path for entering the state as well as the originating prior state from which it emanated. The corresponding path metric then becomes the updated state metric for S.sub.o for use as its prior state metric in the K + 1 baud interval. A like calculation is made for state S.sub.1 as depicted in FIG. 3. Prior to receiving a transmitted signal, the state metrics for S.sub.o and S.sub.1 would normally be set to zero and then updated during each baud interval by accumulating the successive transition metrics T corresponding to the survivor decision metrics .delta..sub.k-1 whose determination will be explained shortly.

A data bit stream of fixed length A.sub.k is generated for each state S.sub.o and S.sub.1 which consists of the data bit stream generated for the prior state identified by its survivor decision metric .delta..sub.k-1 less the oldest bit thereof and whose newest bit is equal in value to the data bit corresponding to the path associated with .delta..sub.k-1. For example, if state S.sub.o at time t.sub.k was entered over the top horizontal path from state S.sub.o, then the data bit value for a.sub.k would have had to been a "0" whereas if entry were from state S.sub.1 over the diagonal path, a.sub.k would have been equal to a "1". If the former was called out by the survivor decision metric .delta..sub.k-1, the data bit stream for S.sub.o at t.sub.k would be equal to A.sub.k-1 (0) less its oldest bit and having a "0" for its newest bit. If the diagonal path from state S.sub.1 corresponded to the survivor decision metric .delta..sub.k-1 (0) then the data bit stream for S.sub.o at t.sub.k would be equal to A.sub.k-1 (1) less its oldest bit with a "1" being inserted as its newest bit. The same calculation would be made for generating a data bit stream for state S.sub.1. As shown by Viterbi, when the generated data bit stream has a number of bits equal to about six times that of the stages in the encoding register, the oldest bit for the various state data bit streams converges to the same value and indeed is equal to the actual transmitted data bit. In the instant case, the data bit stream would have a minimum length of six bits corresponding to the single stage shift register 12.

Before describing how the transition metric T is calculated herein, reference back to FIG. 1 will demonstrate how the tree searching detection is applied to the digital communication systems under consideration. After the digital data a.sub.k is encoded and used to modulate the output of the VCO 22 by controlling the baseband phase shift in each baud interval, it is transmitted to a distant point over a channel symbolically represented by line 32. Upon reception, the transmitted signal is demodulated through a demodulating circuit 34 to provide the baseband signal engendering the digital data a.sub.k preferably in the form of the complex in-phase and quadrature components I.sub.k and Q.sub.k of the phasor Z.sub.k representing the signal in the complex plane. This is done by mixing the transmitted signal with an injection signal Cos (.omega..sub.c t + .theta.) derived from the output of a sinusoidal generator 36 where .omega..sub.c = 2.pi.f.sub.c and .theta. can be any arbitrary phase angle. It will be appreciated by those skilled in the art that the direct mixing of the transmitted signal with the output of generator 36 in multiplier 38 produces the in-phase component I.sub.k after passage through lowpass filter 40 in analog form. By passing the signal through an analog/digital converter (ADC) 42 whose output is sampled at the end of each baud interval, the sample signal being derived from a suitable clock (not shown), I.sub.k is transformed to a digital value. The component Q.sub.k is obtained by mixing the output of generator 36 after passage through a 90.degree. phase shifter 44 with the transmitted signal in multiplier 46 and likewise passing its output through lowpass filter 48 and analog-to-digital converter 50. Ideally I.sub.k and Q.sub.k, constituting a baseband signal (complex envelope) which engenders the input digital data a.sub.k, will be equal to zero or plus or minus some fixed value in the absence of channel noise. Noise in the channel 32 of course corrupts the transmitted signal so that the baud interval phase shift will not always be 0.degree. or .+-.90.degree.; the magnitude and signs of I.sub.k and Q.sub.k, however, may be used as a measure of the probability that the signal associated with the closest ideal noise free value thereto (ascertainable from the encoding and modulation scheme) was transmitted as effectuated through the Viterbi algorithm.

The tree searching detection is performed by a tree searching detector 52 which comprises two transition metric blocks, 54 and 56, for receiving the baseband signal (preferably in the form of I.sub.k and Q.sub.k components) and developing the transition metrics T respectively for states S.sub.o and S.sub.1. The transition metrics T.sub.1 (0) and T.sub.2 (0) for state S.sub.o are appropriately added to the prior state metrics M.sub.k-1 (0) and M.sub.k-1 (1) which are respectively stored in blocks 58 and 60 via adders 62 and 64, respectively. The outputs of adders 62 and 64, representing the path metrics for the two paths into the state S.sub.o, are compared in comparator 66 which determines the maximum one thereof and provides an indication in the form of the survivor decision metric .delta..sub.k-1 (0). The maximum path metric is fed back to block 58 where it is stored to serve as the prior state metric in the next baud interval. A comparator 68 affords the same functions as the foregoing in connection with the outputs of two more adders, 70 and 72, whose outputs represent the path metrics over the two paths into state S.sub.1.

Associated with state S.sub.o and S.sub.1 are two data bit stream blocks, 74 and 76, respectively, which store their respective prior state data bit streams A.sub.k-1 (0) and A.sub.k-1 (1), respectively. The states S.sub.o and S.sub.1 also have associated therewith routing blocks 78 and 80, respectively, each of which receives the data bit stream outputs from both blocks 74 and 76 and routes the appropriate one to its associated data bit stream block in response to the survivor decision metric .delta..sub.k-1 applied thereto. For example, if .delta..sub.k-1 (0) corresponds to prior state S.sub.o, then block 78 routes the output A.sub.k-1 (0) of block 74 back thereinto less its oldest bit. If .delta..sub.k-1 (0) corresponds to prior state S.sub.1, then the output A.sub.k-1 (1) of block 76 would be routed through block 78 into block 74. In addition to routing the appropriate data bit stream, A.sub.k-1, blocks 78 and 80 also provide the appropriate digital value for insertion into the newest bit position of the data bit stream in accordance with the particular path corresponding to the survivor decision metric .delta..sub.k-1.

The transition metric T is obtained by comparing the baseband signal Z.sub.k preferably through its I.sub.k and Q.sub.k components, with a reference signal which is derived therefrom and whose relative closeness to the reference signal is a measure that the signal represented by the reference was in fact transmitted. This measure of closeness is gauged by making a dot product analysis of the baseband and reference signals (the product of their magnitude multiplied by the Cosine of the angle therebetween). Three different ways will be presented by generating a reference signal against which to compare the baseband signal. The first is designated a differential method wherein the baseband signal in each baud period is stored and used as a reference signal in the immediately succeeding baud interval. As shown in FIG. 4, the reference signal designated Z.sub.k-1 forms an angle .theta. with respect to the horizontal I (the I and Q axes being the complex components for the output of generator 6) which is a result of the arbitrary phase angle for the output of generator 36 which would be common to all samples and thus of no effect in the detection process. Referring to the table immeditely below the phasor diagram, it will be appreciated that if there is no differential phase shift between consecutive baud intervals, the baseband signal Z.sub.k will coincide with the reference signal Z.sub.k-1 affording a normalized dot product (Z.sub.k .multidot.Z.sub.k-1) of 1 corresponding to the carrier frequency f.sub.c. However, if the transmitted frequency is other than the carrier signal frequency f.sub.c, then a 90.degree. phase shift will have occurred and the dot product of Z.sub.k and Z.sub.k-1 will be equal to 0 since the COS of .pi./2 is 0. To ascertain whether the 90.degree. phase shift is + or -, Z.sub.k is compared with Z.sub.k-1 shifted +90.degree. which is equivalent to multiplying Z.sub.k-1 by the operator j. If the 90.degree. phase shift was positive, then the dot product of Z.sub.k and jZ.sub.k- 1 will be 1 since they would coincide, while a negative 90.degree. phase shift affords a dot product of -1 since they would be separated by 180.degree. . If there were in fact no phase shift, then the dot product of Z.sub.k and jZ.sub.k-1 would be 0. These two dot product computations are thus sufficient to characterize Z.sub.k vis-a-vis the reference signal Z.sub.k-1.

Referring back to FIG. 3, the transition metric T.sub.1 (0) for state S.sub.o is maximum when the dot product of Z.sub.k and jZ.sub.k-1 is -1 (y.sub.k = - 1). Similarly, the transition metric T.sub.2 (0) is maximum when the dot product of Z.sub.k and Z.sub.k-1 is 1 (y.sub.k = 0). The transition metrics T.sub.1 (1) and T.sub.2 (1) for state S.sub.1 are maximum when the dot products of Z.sub.k and Z.sub.k-1 and Z.sub.k and jZ.sub.k-1 are respectively maximum both equal to 1. The foregoing is tabulated in the bottom Table of FIG. 4.

The logic circuitry for implementing the differential reference signal method of FIG. 4 is shown in FIG. 5. It may be recalled from vector methematics that:

The foregoing scalar products are obtained after first obtaining I.sub.k-1 and Q.sub.k-1 by passing I.sub.k and Q.sub.k through delay circuits 82 and 84, respectively, whose outputs are delayed from their inputs by one baud interval. Under the control of a multiply signal which is derived from a suitable synchronized timing source (not shown), multipliers 86, 88, 90 and 92 provide at their outputs, respectively, I.sub.k I.sub.k-1, Q.sub.k I.sub.k-1, I.sub.k Q.sub.k-1, and Q.sub.k Q.sub.k-1 in response to the appropriate signals applied to their inputs. Under the control of a combine signal also derived from the synchronized timing source, adder 94 sums the outputs of multipliers 86 and 92 to provide at its output the dot product of Z.sub.k and Z.sub.k-1 while a subtractor 96 subtracts the output of multiplier 90 from the output of multiplier 88 to provide the dot product of Z.sub.k and jZ.sub.k-1 at its output.

In response to a load signal from the synchronized timing source, the outputs of adder 94 and subtractor 96 are parallel loaded into adders 98 and 100, respectively, via respective gates 102 and 104. Simultaneous therewith, the output of a register 106 which stores the digital value for the prior state metric M.sub.k-1 (1) is applied as a second input to adders 98 and 100 via respective gates 108 and 110. The output of adder 98 is thus seen to be the path metric m.sub.k-1 (1) + T.sub.2 (0) representing the probability of entering state S.sub.o (circle 24) over the diagonal path from the prior state S.sub.1 (circle 28) of FIG. 3, while the output of adder 100 is the path metric M.sub.k-1 (1) + T.sub.1 (1) for entering the state S.sub.1 (circle 30) from the prior state S.sub.1 (circle 28).

In response to the aforementioned load signal, the outputs of adder 94 and subtractor 96 are also respectively entered into an adder 112 and subtractor 114 via respective gates 116 and 118. At this time the output of a register 120 which is the digital equivalent for the prior state metric M.sub.k-1 (0) is parallel loaded as a second input to adder 112 and subtractor 114 via respective gates 122 and 124. The output of adder 112 is the path metric M.sub.k-1 (0) + T.sub.2 (1) for entering state S.sub.1 (circle 30) from prior state S.sub.o (circle 24) while the output of subtractor 114 is the path metric M.sub.k-1 (0) + T.sub.1 (0) for entering the state S.sub.o (circle 24) from prior state S.sub.o (circle 26).

The path metrics for state S.sub.o are compared in a subtractor 126 whose output is high when the survivor decision metric .delta..sub.k-1 (0) corresponds to prior state S.sub.1 and low when its corresponds to prior state S.sub.o. In response to a compare signal derived from the synchronized timing source, the output of subtractor 126 is passed through an AND gate 128 to enable a gate 130 when high or a gate 132 via inverter 134 when low. The input of register 120 is interconnected with the outputs of adder 98 and subtractor 114 by gates 130 and 132, respectively, which permits it to store the updated state metric M.sub.k-1 (0) when the survivor decision metric corresponds to prior state S.sub.1 (gate 130 enabled) or S.sub.o (gate 132 enabled).

In a similar vein, the outputs of adders 100 and 112 are applied to a subtractor 136 whose output is high when the survivor decision metric for state S.sub.1 corresponds to prior state S.sub.1 and low when it corresponds to state S.sub.o. The output of subtractor 136 is applied through an AND 138 in response to the aforementioned compare signal to directly enable a gate 140 when high and a gate 142 via inverter 144 when low. The outputs of both gates are connected to the input of register 106 while the input of gate 140 is connected to the output of adder 100 and the input of gate 142 is connected to the output of adder 112. Consequently, the metric M.sub.k-1 (1) stored in register 106 is updated from the output of adder 100 when the survivor decision metric .delta..sub.k-1 (1) for state S.sub.1 corresponds to prior state S.sub.1 and from the output of adder 112 when it corresponds to state S.sub.o.

The data bit streams for states S.sub.o and S.sub.1 are generated, respectively, in registers 146 and 148 which in accordance with the Viterbi algorithm should have a number of stages equal to about six times the constraint length of the encoder register (6 bits vis-a-vis the 1 bit shift register 12 of the subject encoder). After the commencement of each baud period, the data bit streams in the registers 146 and 148 are shifted once to the right in response to a shift right signal thus ejecting from the register the oldest bit thereof which is considered to be a valid data bit and presumably would be appropriately processed. At the end of the baud interval, the data bit stream A.sub.k-1 less the oldest bit which was ejected is loaded back into the same register if the associated state and prior state corresponding to its survivor decision metric are the same or the other register if they are not. For example, the input of register 146 for all the bits but the most recent one (leftmost) is connected to the counterpart output of register 146 via gate 150 and the counterpart output of register 148 via gate 152. Gate 152 is enabled by a high-level signal at the output of AND gate 128 to pass the data bit stream A.sub.k-1 (1) less its oldest bit into register 146 to update A.sub.k-1 (0) when the survivor decision metric .delta..sub.k-1 (0) for state S.sub.o corresponds to prior state S.sub.1. If the output of AND gate 128 is low indicating that the prior state was not S.sub.1 but S.sub.0, then gate 150 is enabled to return the data bit stream A.sub.k-1 (0) less its oldest bit to register 146 by virtue of inverter 154. Gates 156 and 158 interconnecting the input of register 148 with the outputs of register 146 and 148, respectively, together with inverter 160 will be seen to afford a like operation with respect to register 148.

After shifting the data bit streams in registers 146 and 148 to the right, the newest or leftmost bit thereof is generated by applying thereto the digital value for the data bit corresponding to the survivor decision metric path. In the case of register 146 and state S.sub.o, the digital value is taken from the output of AND gate 128 directly which will be high corresponding to a "1" for a.sub.k when the survivor decision metric .delta..sub.k-1 (0) corresponds to the prior state S.sub.1 and low when it does not. In the case of register 148 and state S.sub.1, the output of AND gate 138 is first inverted via inverter 162 before being applied to the leftmost stage thereof since the output of AND gate 138 is always opposite to the data bit value corresponding to the survivor decision metric .delta..sub.k-1 (1) for S.sub.1.

A second way for providing the reference signal Z.sub.k-1 is depicted in FIG. 6 wherein the complex plane is organized into four 90.degree. decision regions D.sub.1 -D.sub.4 and the reference signal Z.sub.k-1, obtained through a phase lock loop circuit which controls the phase of the injection signal generator 36 (to be explained shortly) is estimated to lie within one of the regions along the horizontal I or vertical Q axes (generator 36 output) so that the value of its I.sub.k-1 and Q.sub.k-1 components as shown by the table of FIG. 6 is always plus or minus 1 or 0. This being so, the dot products for measuring the transition metrics assume the values shown in the table by substituting the I.sub.k-1 and Q.sub.k-1 values into the equations previously used. This affords a simply way to compute the dot products without the need for the commercially costly digital multipliers 86-92 of the differential approach shown in FIG. 5. The dot product results can be defined with two control logic signals, namely, D.sub.SEL to specify when .vertline.Z.multidot.Z.sub.k-1 .vertline. and .vertline.jZ.Z.sub.k-1 .vertline. are respectively I.sub.k and Q.sub.k (D.sub. SEL =" 1") or Q.sub.k and I.sub.k (D.sub.SEL =" 0"), D.sub.SGN to specify when Z.sub.k .multidot.Z.sub.k-1 is positive (D.sub.SGN ="0") or negative (D.sub.SGN ="1") and a third signal D.sub.SEL .+-. D.sub.SGN derived from the two foregoing ones to specify when Z.sub.k .multidot.jZ.sub.k-1 is positive (D.sub.SEL D.sub.SGN = " 1" ).

The control logic signals D.sub.SEL and D.sub.SGN may easily be generated through implementation of the algorithm depicted in the flow chart of FIG. 7 wherein a phase lock loop (PLL) control signal of +1 tends to shift the phase of the injection signal of the output of generator 36 clockwise and a -1 tends to shift it counterclockwise. At the beginning of each computation, it is assumed that a -1 is required for shifting the signal phase counterclockwise. If the I.sub.k component of the baseband signal Z.sub.k in the complex plane is greater than 0 represented by branch point 162, then Z.sub.k must lie in regions D.sub.1, D.sub.2, or D.sub.4 so that the algorithm then moves to branch 164. If I.sub.k does not exceed 0, then Z.sub.k must lie in regions D.sub.2 -D.sub.4 which moves the algorithm to branch 166. At branch 164, if the absolute value of I.sub.k exceeds the absolute value of Q.sub.k, then Z.sub.k perforce must lie in region D.sub.1 which moves the algorithm to block 168 to generate the control signals D.sub.SEL equal to "1" and D.sub.SGN equal to "0". If the absolute value of I.sub.k exceeds that for Q.sub.k at branch 166, then Z.sub.k perforce must lie in decision region D.sub.3 whereby the algorithm moves the block 170 to generate control signals D.sub.SEL and D.sub.SGN both having a value "1". If the absolute value of I.sub.k is less than the value of Q.sub.k at either branch 164 or 166, the algorithm then moves to branch 172 where a determination is made as to whether or not Q.sub.k exceeds 0. If it does, then Z.sub.k must lie in region D.sub.2 whereby the algorithm moves to block 174 to generate control signals D.sub.SEL and D.sub.SGN both having a value of "0". If Q.sub.k is less than 0, Q.sub.k must lie in decision region D.sub.4 whereby the algorithm moves to block 176 to generate control signals D.sub.SEL and D.sub.SGN having values of "0" and "1", respectively.

If Z.sub.k has been determined to lie in decision region D.sub.1 and Q.sub.k exceeds 0, represented by branch 178, the phase of Z.sub.k is ahead of Z.sub.k-1, requiring that the phase lock loop circuit retard the injection tracking signal at the output of generator 36 which gave rise to the components I.sub.k and Q.sub.k in the first place, so as to bring it into coincidence with Z.sub.k-1. This is accomplished by generating a +1 (to produce a clockwise shift in phase for Z.sub.k) for application by the phase lock loop circuit via block 180 from branch 178. If in decision region D.sub.1, Q.sub.k is less than 0, Z.sub.k lags Z.sub.k-1 and a minus one is automatically inserted by the phase lock loop circuit to advance the carrier tracking signal. Thus, the carrier tracking signal when determined to be in decision region D.sub.1 is automatically properly corrected for phase during each baud interval. The same correction is afforded for determination of Z.sub.k in regions D.sub.2, D.sub.3, and D.sub.4 by virtue of branches 182-186 and blocks 188-192, respectively.

A simple logic circuit responsive to the control signals D.sub.SEL and D.sub.SGN for performing the foregoing dot product computations is shown in FIG. 8 wherein I.sub.k is applied to the first input and second input of select gates 194 and 196, respectively. Q.sub.k is applied to the second input and first input of select gates 194 and 196, respectively. Each select gate has a control input C, connected to receive the control signal D.sub.SEL generated in the control logic block 198 representing the algorithm flow chart of FIG. 7. As shown by the accompanying left table of FIG. 1, a "1" for D.sub.SEL passes to the output of select gates 194 and 196 the signals appearing at their 1 inputs, whereas a "0" passes the signals appearing on their 2 inputs. The output of select gate 194 is connected to an inverter 200 while the output of select gate 196 is connected to an inverter 202. The inverter 200 is controlled directly by the control signal D.sub.SGN generated in control logic block 198 in accordance with the right table of FIG. 8. Accordingly, whenever D.sub.SGN assumes a "1" inverter 200 inverts the signal appearing at its input whereas when D.sub.SGN assumes a "0", inverter 200 does not so invert. Referring to table of FIG. 6, it will be readily seen that the output of inverter 200 is in fact the dot product Z.sub.k .multidot.Z.sub.k-1. Inverter 202 is controlled from the output of an exclusive NOR gate 204 whose inputs are D.sub.SEL and D.sub.SGN. When these signals are the same, the output of exclusive NOR gate 204 is high to cause an inversion by inverter 202 and when they are not, the low level output of NOR gate 204 inhibits inversion by inverter 202. It will be readily seen that the output of inverter 202 is the dot product of Z.sub.k and jZ.sub.k-1.

The plus or minus one signal produced by control logic block 198 for correcting the phase of the injection signal is applied to the injection signal generator 36 preferably through a digital accumulator (not shown). the PLL circuit path follows the I.sub.k and Q.sub.k outputs of the demodulator 34 through the control logic 198 and back to the generator 36 which could be merely a VCO.

A third method for obtaining the dot product to perform the transition metric is based on using an absolute reference signal generated from a phase lock loop circuit like the foregoing wherein the injection signal at the output of generator 36 once again tracks the baseband signal. As shown by the tree diagram in FIG. 9, this reference signal can assume any one of four absolute states 0.degree., 90.degree., 180.degree., or 270.degree. at the end of each baud interval. Because of the encoding employed, given a particular state at t.sub.k-1, the carrier signal can move into only one of three of the four states at t.sub.k engendering a phase shift of 0.degree. or .+-.90.degree.. If the reference signal is in state S.sub.0.degree., then the transition metric T(0.degree.) will be maximum when the baseband signal Z.sub.k is equal to I.sub.k for all paths thereinto. Likewise, if the reference signal is at 90.degree. the transition metric T(90.degree.) will be maximum when Z.sub.k is equal to Q.sub.k for all paths thereinto. Extending this to the transition metrics T(180.degree.) and T(270.degree.), these will be maximum when Z.sub.k is equal to -I.sub.k and -Q.sub.k, respectively. These values are inserted in the path metrics for the various paths into the four possible states of the absolute reference signal to determine the state metrics and survivor decision metrics as delineated in FIG. 9. The associated values for the data bit a.sub.k which were obtained from FIG. 3 are shown in the table below the tree diagram wherein the middle column corresponds to the prior state designated by the survivor decision metric .delta..sub.k-1.

FIG. 10, like that of FIG. 1, is a block diagram for implementing the tree searching detection by effecting the computations of the various metrics used for generating the various data bits streams for the four states associated with the absolute reference signal approach of FIG. 9. Thus, four comparators, 206-212, are required for the four respective states S.sub.0.degree. -S.sub.270.degree. along with four data registers, 214-220 and their respective routing blocks 222-228. Four registers, 230-236, are likewise provided for each of the four states S.sub.0.degree. - S.sub.270.degree. for storing the individual prior state metrics M.sub.k-1. The path metrics for state S.sub.o are computed by adding I.sub.k to the appropriate outputs of registers 230-236 in adders 238 as shown in FIG. 10 in accordance with the equations delineated in FIG. 9. Similarly, adders 240 combine Q.sub.k with the appropriate register 230-236 outputs to provide the path metrics for comparison in comparator 208 for state S.sub.90.degree.. The path metrics for states S.sub.180.degree. and S.sub.270.degree. are computed through subtractors 242 and 244, respectively. The outputs of the data bit stream registers 214-220 are appropriately routed to their possible destinations (there being three for each register) as is evident from FIG. 9.

Numerous modifications to the foregoing disclosure are possible without departing from the scope and spirit of the invention engendered thereby. For example, although a digital implementation has been described, it is quite conceivable, although perhaps not practical to employ an analog implementation. Also, although a correlatively encoded digital signal was converted to a three-level frequency signal for transmission purposes to conserve bandwidth, other encoding and modulation schemes are unquestionably feasible as well as other numerical level frequencies. Thus, the invention is not to be limited to the scope of the foregoing disclosure, but rather by the claims which will now be set forth.