Method and Apparatus for Recognizing in a Receiver the Start of a Telegram Signal Consisting of a Bit Impulse Sequence

Use of a (2,1)-convolutional code for bit synchronization is known from the article "Branch Synchronization Schemes for Convolutional Codes" Wai-Hung Ng, proc. IEE Volume 123, No. 6, June 1976, pgs. 481-484.

One of the principal objects of the invention is to devise a simple bit synchronization which does not require any convolutional code, or which can be utilized in combination with such a convolutional code for synchronization of a bit sequence.

This object ist attained in a method and an apparatus for recognizing the start of a noise-corrupted received telegram signal and wherein the telegram signal consists of an information-containing sequence of bits by transmitting a preliminary sequence of bits ahead of the telegram signal, thereafter transmitting an intermediate sequence of bits following the preliminary sequence, but still ahead of the telegram signal, wherein the preliminary and the intermediate sequences are correlated with different parts of the preliminary and of the intermediate sequence in a prearranged manner, and detecting the pre-arranged manner so as to positively signal termination of the intermediate sequence. Recognition of the start of the telegram signal is thus ensured.

Other objects of the invention will in part be obvious, and will in part appear hereinafter.

For a fuller understanding of the nature and objects of the invention, reference should be had to the following detailed description, taken in connection with the accompanying drawings in which:

FIG. 1 is a block diagram of a synchronizing circuit for an uncoded sequence of bits;

FIG. 2 is a block diagram of a synchronizing circuit for a coded sequence of bits;

FIG. 3 is a block diagram of correlator; and

FIG. 4 is a diagram of a processing means

Identical reference numerals in each Fig. denote similar parts.

Both the circuit according to FIG. 1 as well as the circuit according to FIG. 2 consists of a synchronization circuit 1 and a receiver portion 2, each forming part of a common receiver.

In both cases the receiver portion 2 has a single input, a signal output and a "ready" output, and the synchronization circuit 1 has a signal input connected to the signal output of the receiver portion 2, a release input connected to the ready output of the receiver portion 2, and a telegram signal output, which in the case of FIG. 1, is single pole, but in the case of FIG. 2 is a k-bit data bus; in the simplest case k=1, so that the synchronization circuit 1 according to FIG. 2 then has a single pole telegram signal output also.

The synchronization circuit 1 according to both Figs. includes inter alia:

a single changeover switch (FIG. 1) or k changeover switches 3 (FIG. 2) each consisting of an inverter 4, a first AND gate 5, and a second AND gate 6, each of these AND gates having two inputs;

a first shift register 7 and a first correlator 8 associated with the first shift register;

a third AND gate 9, which has three inputs in the case of FIG. 1, and two inputs in the case of FIG. 2; and

a clock generator 10.

The synchronizing circuit 1, according to FIG. 1 additionally includes a second shift register 11 and a second correlator 12 associated with the second shift register 11, while the circuit according to FIG. 2 additionally includes a series-to-parallel converter 13, a decoder 14, a frequency divider 15, a third correlator 16, a fourth AND gate 17 having two inputs, a reset input 18, a D-flip flop 19, and a fifth AND gate 20 having two inputs.

The two shift registers 7 and 11 are digital shift registers and have each a single clock input, a single series input as well as a single series output, and a single x-bit parallel output. Each correlator 8 and 12 has a first and a second parallel input of x-bits, as well as a single pole output. The x-bit parallel output of one of the shift registers 7 or 11 is connected through an x-bit data bus connection to the first x-bit input of the associated correlator 8 or 12. A first digital x-bit reference word "A" appears on the second x-bit input of the first correlator 8, and, if available, a second digital x-bit reference word "B" appears on the second x-bit input of the correlator 12.

Each of the correlators 8 and 12 consists of "x" non-exclusive OR gates 21 (see FIG. 3), each having two inputs, which control in each correlator 8 or 12 a common processing means 22. If the number of binary values "1" at the output of the "x" non-exclusive OR gates of one of the correlators 8 or 12 exceeds a predetermined limit value q<x, then there appears at the single output of the associated processing means, which is also the output of the corresponding correlator 8 or 12, a binary value "1".

Each processing means 22 includes, for example (see FIG. 4), a AND-OR gate, which in turn consists of ##EQU1## of not yet mentioned AND gates 23, which each have q inputs and control a common OR gate 24, whose output forms the output of the processing means. Each combination of "x" outputs of the non-exclusive OR gates 21 of each correlator 8 or 12 of the q.sup.th class is associated with one of the AND gates 23 of the AND-OR gate, wherein q of these outputs are respectively connected to the q inputs of one of these AND gates 23, without a certain combination of these outputs being ever repeated.

In FIG. 1 the following additional single-pole connections exist:

a release input of the synchronizing circuit 1 is connected to the first input of the third AND gate 9;

the output of the first correlator 8 is connected to the second input of the third AND gate 9;

the output of the second correlator 12 is connected with the third input of the third AND gate 9;

the single output of the clock generator 10 is connected to the two clock inputs of the first and the second shift register 7 and 11 connected to one another;

the output of the third AND gate 9 is connected directly to the first input of the second AND gate 6 and is connected through the inverter 4 with the first input of the first AND gate 5;

the signal input of the synchronizing circuit 1 is connected to the second input of the first and second AND gates 5 and 6, which in turn are connected to one another;

the output of the first AND gate 5 is connected with the series input of the second shift register 11 and its series output is connected with the series input of the first shift register 7, its series output not being utilized however; and

the output of the second AND gate 6 is connected with the telegram output of the synchronization circuit 1.

In FIG. 2 the following additional connections exist:

the signal input of the synchronizing circuit 1 is connected to the series input of the first shift register 7, and its series output is connected to the single series input of the series-to-parallel converter 13;

the release input of the synchronizing circuit 1 is connected to the first input of the third AND gate 9;

the output of the first correlator 8 is connected with the second input of the third AND gate 9, and its output with the single clock input of the D-flip flop 19;

the Q output of the D-flip flop 19 is connected to the single enable inputs of the series-to-parallel converter 13 and of the decoder 14 connected to one another, as well as with the first input of the fifth AND gate 20;

the single output of the clock generator 10 is connected to the second input of the fifth AND gate 20 and with the clock input of the first shift register 7;

the output of the fifth AND gate 20 is connected with the single input of the frequency divider 15;

the single D-input of the D-flip flop 19 has at its input a binary value "1";

the n data outputs of the series-to-parallel converter 13 are connected to the "n" data inputs of the decoder 14, and its "k" data outputs with the respective single data inputs of the "k" changeover switches 3, wherein each data input of a switch 3 is in turn connected to the first inputs of the first and second AND gates 5 and 6, which first inputs are connected to one another.

the single output of the frequency divider 15 is connected to the single clock inputs of the series-to-parallel converter 13 and of the decoder 14, which, in turn, are connected to one another.

the output of the k AND gates 5 are connected to a first "k"-bit input of the third correlator 16, and its output is connected to a first input of the fourth AND gate 17, its second input receiving a reset signal 18;

the output of the fourth AND gate 17 is connected directly to the respective input of the "k" second AND gates 6, and through a respective of the "k" inverters 4 with the second input of the corresponding "k" AND gates 5; and

the outputs of the k second AND gates 6 are connected to the k-bit parallel telegram outputs of the synchronizing circuit 1.

The following relations apply: for the first shift register 7, for the first digital reference word A, and for the first correlator 8, x=h, and for the second shift register 11, the second reference word B and the second correlator 12, x=k, wherein h and k are integers.

At a second k-bit input of the third correlator 16, which has a structure similar to the structure of correlators 8 and 12, there appears a third digital k-bit reference word C.

The receiver portion 2, the clock generator 10, and the frequency divider 15 are known electronic circuits; the decoder 14 is preferably a known Viterbi decoder implemented by means of a microcomputer. These circuits are not subject of a claim, and are therefore not further described in detail. For all remaining circuits, digital components of the TTL series 74 . . . of e.g. Texas Instruments, Dallas, Tex., may be utilized.

Before the operation of the circuits, according to the present invention is described, there follows for easy reference a listing of the symbols employed hereinafter:

x: number of exclusive NOR gates 21, and number of parallel output cells of a shift register 7 or 11

q: limit value of the number of binary values "1" at the outputs of the exclusive NOR gates 21

m: number of bits of a preliminary sequence

k: number of bits of an uncoded intermediate sequence

h: number of bits in the first digital reference word A and the number of cells in the first shift register 7

n: number of bits of a period of a coded preliminary sequence and number of bits of the coded intermediate sequence

A received signal at the input of the receiver portion 2 is conditioned in a known and therefore not further described manner, for example by filtering, demodulation, level regulating and the like, and appears as a bit impulse sequence at the signal input of the synchronizing circuit 1. As soon as the received parameters, for example level values, have been conditioned so as to result in an acceptable quality in the receiver portion 2, then there appears at the ready output of the receiver portion 2 a binary value "1" and releases the third AND gate 9 for the remaining input signals. The aforedescribed bit sequence consists, in sequence, of the aforesaid preliminary sequence V, of an intermediate sequence Z and of a telegram signal T. The telegram signal T is the information-containing signal.

The preliminary sequence V consists, for example of m alternating binary values "1" and "0". The intermediate sequence Z and the telegram signal T are either uncoded or are coded by means of a (n,k) convolutional code, and are then denoted as Z' and T'.

The uncoded intermediate sequence Z consists of k-bits and is chosen in the uncoded version so that the following correlations are as small as possible:

correlation between the intermediate sequence Z with the last k-bits of the preliminary sequence Z;

correlation of the first two j-bits of the intermediate sequence Z with the last two j-bits of the preliminary sequence V; and

correlation of the first two j-bits of the intermediate sequence Z with the last two j-bits of the intermediate sequence Z in the case of even k, or correlation of the first (2j-1) bits of the intermediate sequence V with the last (2j-1) bits of the intermediate sequence Z in the case of k being odd.

It should be noted that j=1,2 . . . , (k/2-1) in the case of k being even, and j=1,2 . . . , (k-1/2) in the case of k being odd.

m=14 (preliminary sequence)

k=8 (intermediate sequence)

preliminary sequence V: 10101010101010 (14 bits)

intermediate sequence Z: 01011100 (8 bits)

preliminary sequence V: 01010101010101 (14 bits)

intermediate sequence Z: 10101100 (8 bits)

In the coded version the k successive bits form the uncoded intermediate sequence Z, which is converted by means of a (n,k) convolutional code into the coded intermediate sequence Z' which is to be transmitted.

Normally there appears at the output of the third AND gate 9 the binary value "0", so that all second AND gates 6 are inhibited, and simultaneously all first AND gates 5 are released through the respective inverter or inverters 4.

Both shift registers 7 and 11 are connected in series and form together a single (h+k) bit shift register. Into this shift register there are transmitted through the released first AND gate 5, in sequence, in the drawing from right to left, the preliminary sequence V and the intermediate sequence Z by means of the clock impulses supplied by the clock generator 10. Based on the assumption that, for example m>(h+k), the (h+k) storage cells of the two shift registers 7 and 10 are occupied with the last (h+k) bits of the preliminary sequence V, as soon as there appears on the input of the second shift register 11 the first bit of the intermediate sequence Z. This period of time is denoted as t=0.

The further operation will now be illustrated in more detail by means of an example wherein h=5 and by means of the Table I shown overleaf.

The following relationships apply: m=14, (h+k)=13 wherein m>(h+k).

The transmitted bit sequence is:

The first reference word A equals the last h bits of the preliminary sequence V, namely in the example chosen is equal to the 5 last bits "01010" of the fourteen bits of the preliminary sequence V.

The second reference word B is equal to the preliminary sequence Z, namely equal to "01011100".

Each new clock impulse of the clock generator 10 shifts the contents of SR.sub.t of the (h+k) bit shift register shown in FIG. 1 and Table 1 by one location from right to left, while simultaneously the bit appearing on the series input of the second shift register 11 is shifted to the first right-most storage cell of that shift register 11.

In Table 1:

The lines SR.sub.t denotes the contents of the (h+k) bit shift register at the period t;

The row X denotes the contents of the first shift register 7; and

The row Y denotes the contents of the second shift register 11.

As has already been mentioned, at the time t=0 the contents SR.sub.0 of the (h+k) bit shift register is equal to the last (h+k)=13 bits of the preliminary sequence V, namely "0101010101010", and the first bit of the intermediate sequence Z "01011100", namely "0" appears at the input of the second shift register 11. The value t is the continuous count of the clock impulses of the clock generator 10 since the time t=0.

For example, after three such clock impulses the time t=3 has been reached, and the contents of the (h+k) bit shift register is equal to SR.sub.3, namely equal to "1010101010010".

A line in the form of a stair step shown in Table 1 separates the preliminary sequence V from the intermediate sequence Z. In the last t storage cells of the (h+k) bit shift register there are stored always the first t bits of the intermediate sequence Z based on the afore-noted assumption, as read from left to right.

The last line of Table 1 contains the reference words, namely in column X the first reference word A, namely "01010" and in column Y the second reference word, namely "01011100" are shown.

In Table 1 both bits of SR.sub.t which are correlated with the associated bit of the corresponding first or second respective reference word A or B, namely which are identical with this bit, are underlined; their number is a correlation value shown in the last two columns of Table 1. From the penultimate column, namely the column shown under X in Table 1, it can be seen that during the reception of non-corrupted bits during odd values of t, the correlation for X is minimal and equal to 0, and during even values of t is maximal and equal h=5. If individual or several bits are falsified due to interference, then it is true that these correlation values of X are decreased; at a high probability these values will not, however, reach the average value of (h/2)=2.5. The first correlator 8 generates on its output, and therefore on the associated input of the third AND gate 9 only then a binary value "1", if the correlation value of X exceeds a limit value q.sub.1 .gtoreq. (h/2). Depending of the length of the preliminary sequence V the correlator 8 has several possibilities to recognize the reference word A. It is therefore advisable to select the limit value q.sub.1 for relatively long preliminary sequences greater than h/2, so as to obtain better protection from an erroneous actuation of the AND gate 9. Thus only the contents SR.sub.t received and stored in the (h+k) bit shift register having an even value of t are significant for the start-synchronization. All values of SR.sub.t with an odd value of t have no significance and in what follows can be neglected, as they never enable the third AND gate 9 through its second input. Thus, recognition of the start of the telegram signal is blocked when q.sub.1 <h/2.

As can be ascertained from the last column of Table 1, in the case of even values of t, the correlation values of Y are equal to 2,2,2,3 and t=8. All these correlation values are very low, with the exception of the last value k=8. If a high limit value q.sub.2 <k is chosen for the second correlator 12, for example an approximately intermediate value of 6 between the highest values 3 and k=8, then the second correlator 12 enables the third AND gate 9 postcoupled thereto through its third input definitely only at the time t=k=8. This is, however, the very time at which the intermediate sequence Z is terminated and where the next bit signals the commencement of the telegram signal T. This release is correctly accomplished as long as any bit errors caused by interference do not exceed the correlation values of X or Y in terms of the associated limit value q.sub.1 or q.sub.2, respectively, in one or the other direction.

If at the ready output of the receiving portion 2 there appears a logical value "1", then at the time t=k=8 the third AND gate 9 is definitely enabled so that the logic value "1" switches over the switch 3 at its output, by this time inhibiting the first AND gate 5 and simultaneously enabling the second AND gate 6. The telegram signal T following the intermediate sequence therefore reaches through the second AND gate 6 the output of the synchronizing circuit 1. The third AND gate 9 therefore is the last link in the chain of the detecting and recognizing means including the intermediate sequence, the shift register 11, the correlator 12 and the second reference word B, which positively signal termination of the intermediate sequence. The first bit appearing at this telegram signal output is recognized by a (non-illustrated) portion of the receiver postcoupled to the synchronizing circuit 1 as a first bit of the telegram signal t and accepted as such, so that the commencement of the processing, and therefore the commencement of synchronization of this telegram signal T is accomplished at the correct moment in time in spite of possible bit corruptions.

The preliminary sequence V, the coded intermediate sequence Z', and the coded telegram signal T' are sequentially shifted in FIG. 2 from right to left into the first and single shift register 7. The preliminary sequence V is an n-bit periodic sequence which has been coded with the aid of a (n,k) convolutional code from an uncoded k-bit periodic sequence. The first of these coded combinations need not absolutely be complete on their left sides. The correlation of one period of the preliminary sequence V with two consecutive periods shifted by t bits of that preliminary sequence must be as small as possible, namely 0<t<n. The h-bit reference word A is composed of the last h-bits of the preliminary sequence V.

n=2,

n-bit combination="10",

preliminary sequence V=0101010101010 wherein m=13,

reference word A=01010, wherein h=5.

After the first shift register 7 has been filled, with the h-bits of the preliminary sequence V, and after the initial incomplete part of the n-bit combination has left the first shift register 7, the contents of this first shift register 7 agrees the first time with the first reference word A, based on the assumption that the received and stored bits of the preliminary sequence V have not been falsified by any interferences. If, however, errors have occurred in the sequence, the first correlator 8, whose limit value q.sub.1 is again.gtoreq.(h/2) generates at this moment in time, nevertheless, at its output a binary value "1" for the same reasons which have already been explained when describing the operation of the uncoded version of the invention. This is repeated each "n" bit times up to the moment when a binary value "1" appears both on the ready output of the receiver portion 2 as well as on the output of the first correlator 8. Depending on the length of the preliminary sequence V the correlator 8 has several possibilities to recognize the reference word A. Here it is also advisable to select the limit value q.sub.1 for relatively long preliminary sequences larger than h/2, so as to obtain better protection from any erroneous actuation of the AND gate 9. At the output of the third AND gate 9 there appears then the binary value "1", whose positive-going edge flips over the D-flip flop 19 post-coupled thereto, so that its Q-output releases on one hand the series-to-parallel converter 13 and the decoder 14 through its enable inputs as well as the frequency divider 15 through the fifth AND gate 20. By means of this signal at the "enable" input of the decoder 14, the decoder 14 is brought into the state in which it would remain, if at its data inputs there would always appear the "n" bit combination of an intermediate sequence period. For all (n,1) codes this state corresponds to the 11 . . . 1 state, as it has been generated by an input sequence of only "1's". If the Viterbi decoding algorithm described in the "The Theory of Information and Coding" R. J. McEliece, Addison-Wesley Publishing Comp. 1977, Page 211, is used, then initialization is achieved by associating with the state 11 . . . 1 a high initial metric so as to set the metric of the other states equal to 0. From this time of release the frequency divider 15 divides the frequency of the clock impulses of the clock generator 10 by "n" and subsequently feeds the series-to-parallel converter 13 and the decoder 14 with this frequency-divided clock signal.

The n-bits of the n-bit combination following thereto at this moment of release are distributed through the series-to-parallel converter 13 to its "n" data outputs, and therefore to all "n" data inputs of the decoder 14, so that at its "n" data inputs there appear successively in time the individual n-bit combinations in parallel, and are decoded by the decoder 14 sequentially into a decoded k-bit word.

As long as the n-bit combinations of the preliminary sequence V appear on the data inputs of the decoder 14, the data at the k data outputs remain equal from one decoding step to another and in the case of the (2,1) convolutional code there would appear successive binary values "1". If at the reset input 18 of the gate 17 a binary value "1" appears, and if the third digital reference word C consists of the uncoded intermediate sequence, and if the limit value of the third correlator 16 q.sub.3 =k, then during the preliminary sequence V the AND gate 17 is inhibited. Thus the AND gates 5 are released through the inverter 4 and simultaneously the AND gates 6 are blocked. The coded intermediate sequence Z is always selected so that it has a Hamming distance to an n-bit period of the preliminary sequence V as large as possible.

In the case of the (2,1) convolutional code, the uncoded intermediate sequence is, for example, equal to "0" the coded sequence equal to "01" or "10", wherein q.sub.3 =1.

If, following the preliminary sequence V the n-bit combination of the intermediate sequence Z is decoded, then there appears on the data output of the decoder 14, and consequently on the first k-input of the third correlator 16 the uncoded k-bit intermediate sequence which is equal to the third digital reference word C. Thus there appears at the output of the third correlator 16 the binary value "1", the AND gate 17 is enabled, and the next k-output bits of the decoder 14 reach through the k switches 3 the telegram output of the synchronizing circuit 1.

If a (2,1) convolutional code is used, then the decoded intermediate sequence of the length one is equal to "0". Thus the correlator 16 is reduced to an inverter, the third reference word C is redundant, the dividing ratio of the frequency divider 15 becomes 2, and is therefore reduced to a single flip flop, the k-bit telegram output of the synchronizing circuit 1 consists then only, as in the uncoded version, of a single series output, and only a single switch 3 is required.

In this case the single n-bit combination of the coded intermediate sequence Z is equal, for example to the one complement "01" of the n-bit combination "10" of the preliminary sequence V, so that the transmitted and correct (non-falsified) coded bit impulse sequence with m=13 and m=2 appears as follows: V,Z,T'=0101010101010,01,T'.

The decoded bit impulse sequence is then at k=1:111111,0,T, wherein T' represents the coded telegram T. T' consists of a multiplicity of double bit combinations, where each of the double bits (n=2) is the (2,1) convolutional code word of the single bit (k=1) of the uncoded telegram T.

We wish it to be understood that we do not desire to be limited to the exact details of construction shown and described, for obvious modifications will occur to a person skilled in the art.