AU639023B2

AU639023B2 - Block synchronization

Info

Publication number: AU639023B2
Application number: AU63363/90A
Authority: AU
Inventors: Robert Johnson Irvine; Stephen Norman Levine
Original assignee: Motorola Inc
Current assignee: Motorola Solutions Inc
Priority date: 1989-09-25
Filing date: 1990-09-04
Publication date: 1993-07-15
Anticipated expiration: 2010-09-04
Also published as: WO1991005423A1; CA2066195C; AU6336390A; CA2066195A1; BR9007691A

Description

liyb i~ 1 BLOCK SYNCHRONIZATION This invention is concerned with block synchronization in data transmission systems.

More particularly, this invention is concerned with block synchronization using permuted synchronization words.

For a receiver to decode data messages transmitted to it, it must first locate the data in the transmission, known as block synchronization, Thus, long synchronizing sequences usually precede data so that the receiver can reliably correlate on the sequence and synchronize to the data. In radio environments where the signal is subject to fading, as in land-mobile radio, 39

MJP

TO

According to one aspect of the present invention there is provided a method of synchronization comprising: predeterminally arranging synchronization words in a signal containing information of interest, transmitting such signal, receiving that signal having the synchronization words predeterminally arranged therein, detecting at least certain of those synchronization words and their arrangement with respect to one another, and synchronizing to the information of interest with reference to the arrangement of one detected word in relation to each other and their relation to the information of interest.

According to a further aspect of the present invention there is provided a method of synchronization comprising: receiving a signal having information of interest and synchronization words predeterminally arranged in the signal, detecting at least certain of those synchronization words and their arrangement with respect to one another, and synchronizing to the information of interest with reference to the arrangement of one detected word to another and their arrangement in relation to the information of interest.

According to a still further aspect of the present invention there is provided a method of synchronization comprising the steps of: arranging a first, a second, and a third synchronization words in a data transmission; transmitting the data transmission from a e• :transmitter; receiving the data transmission at a receiver; detecting the first and third synchronization words; 35 determining the arrangement of the first to the third synchronization words; and synchronizing the receiver based upon the arrangement.

39 2a

MJP

S ll il i i n l -I -A According to a still further aspect of the present invention there is provided a method of synchronizing a data transmission comprising the steps of: inserting a first synchronization word in the data transmission; inserting a second synchronization word in the data transmission a first predetermined distance from the first synchronization word; inserting a third synchronization word in the data transmission a second predetermined distance, different from the first predetermined distance, from the second synchronization word; transmitting the data transmission from a transmitter; receiving the data transmission at a receiver; detecting one of said first, second, and third synchronization words; detecting another of said first, second, and third synchronization words; determining a distance between the detected synchronization words; and synchronizing to the information of interest using said first detected synchronization word and said determined distance between the detected synchronization words.

According to a still further aspect of the present invention there is provided a method of synchronizing a data transmission comprising the steps of: inserting a first synchronization word having a first bit pattern in the data transmission; inserting a second synchronization word having said first bit pattern in the data transmission a first predetermined distance from the first synchronization word; inserting a third synchronization word having the first bit pattern in the data transmission a second predetermined distance, different from said first predetermined distance, from the second synchronization word; 2b

-A

MJP

transmitting the data transmission from a transmitter; receiving the data transmission at a receiver; detecting one of said first, second, and third synchronization words; detecting another of said first, second, and third synchronization words; determining a distance between the detected synchronization words; and synchronizing to the information of interest using said first detected synchronization word and said determined distance between the detected synchronization words.

A preferred embodiment of the present invention will now be described with reference to the accompanying drawings wherein:- Figure 1 is an illustration of permuted synchronization according to the invention.

Figure 2 is a word permutation tree according to the invention.

Figure 3 is a relative phase permutation tree according to the invention.

39 2c MJP

T

.I WO 91/05423 PCT/US90/04920 1 -FRMUT=E- BLOCK SYNCHRONIZATION RELATED APPLICATIOS This is a continuation-in-part pplication of Serial No. 07/411,959, filed 25 September 1989 by Levine and Irvine, assigned to Motorola, THE FIELD OF INVENTION This invention is concerned with block synchronization in data transmission systems.,' More particularly, this invention is concerned with block synchronization using permuted synchronization words.

BACKGROUND OF THE INVENTION For a receiver to decode data messages transmitted to it, it must first locate the data in the transmission, known as block synchronization. Thus, long synchronizing sequences usually precede data so that the receiver can reliably correlate on the sequence and synchronize to the data, In radio environments where the signal is subject to fading, as in land-mobile radio, I WO 91/05423 PCT/US90/04920 -2the signal may be lost during these long synch sequences and the receiver will have difficulty synchronizing to the data and recovering it.

US Patent No. 4,694,473 to Etoh attempts to solve this problem by preceding the data message by three different synchronization sequences. He locates the data in the transmission by reference to the known distance between the data and that sequence on which the receiver was able to correlate. The disadvantage in this approach is that it requires multiple correlators/correlations, three of them.

This invention takes as its object to ovorcomo these shortcomings and to realize certain advantages presented below.

Rather than using multiple synchronization sequences and multiple correlators/correlations, this invention u'se. various permutations of a single synchronizing word (and its inverse), thereby using only one single correlator/correlation.

OF THE INVENT-N There is provided a mechanism for block synchr ization, It comprises: predeterminally arranging per ations of synchronization words about a poi f interest, transmitting such arrangement, receiving t transmission having permuted synchronizatio ords predeterminally arranged about that point of erest, detecting at least part of certain permutations hose synchronization words, and locating the point of Iferest with reference to the permutation of one d ted word about another and their arrangement about the of intere--t WO 91/05423 PCT/US90/04920 3f-----Rfls 3 N OF THE D-RAW-EW- Additional objects, features and advantages of the i ention will be more clearly understood and the best mod contemplated for practicing it in its preferred mbodiment will be appreciated (by way of unrestricted xample) from the following detailed description, taken to eher with the accompanying drawings in which: Figure 1 is an illustration of pe ruted synchronization according to the invention.

Figure 2 is a word perm tation tree according to the invention.

Figure 3 is a rel ve phase permutation tree according to the invention.

DETAILED DESCRIPTION Figure 1 is an illustration of permuted synchronization acorin4oh e-4 entio n.

Figure 1 illustrates a data message preceded by all eight possible permutations of a synchronization word and its bit-wise inverse two words taken three at a time consecutively, or 23=8. That is,

SS

SSS

SSS etc., resulting in the overlapping composite of: .SSSSSSSS that contains all eight permutations, each permutation being unique and unambiguous. (In fact, it can be 1 -carr^- -PII WO 91/05423 PCT/US90/04920 -4 shown that if the first eight words are cyclically rotated and then the resultant first two words are appended to the rotated eight, then an equally acceptable initialization vector is generated, or more generally, where J is the number of available words to be permuted and N is the number of consecutive word detections, then the first jN words may be cyclically rotated and the resultant most significant N-1 words appended to generate a maximal length initialization vector of jN N This cyclical property can be advantageously utilized to cause receivers having cyclical rotations of this vector to look for the data of interest to begin at a different, and potentially incorrect locations.) The 23 scheme presented above would correspond to a detection criterion that three consecutive words must be detected to establish the one-in-eight unambiguous permutation (and its corresponding characteristic distance from the data of interest). To reliably detect the synchronization word or its inverse, the word should have high auto-correlation characteristics and low cross-correlation characteristics with respect to its inverse, as is well understood by those ordinarily skilled in this field. Thus, on a synch word of say 21 bits, 3 correlation errors or less would correlate to S while errors of 18 or more (in the very same correlator/ correlation) would correlate to the inverse, Accordingly, only one correlator/ correlation is required to detect one synch word and its inverse. Similarly, only two correlators/correlations are required to correlate to four words, X, X. Y, and Y.

Figure 2 is a word permutation tree according to the invention. It illustrates that any given word may be followed by any other available word S or thus, if the first word is 5, it can be followed by either S (moving to the left) WO 91/05423 PCT/US90/04920 or S (moving to the right), which in turn, can be followed by either 5 or S.

If the detection criterion is that the data must be locatable from the detection of any two consecutive words, then no identical pairs of two consecuitive words can exist; otherwise, one would not know which of the two pairs should be used to locate the information. Each X in Figure 2 represents a permutation that should not be allowed to exist if our detection criterion is not to yield ambiguous results.

Accordingly, if pair B were allowed and fading caused node 1 of pair A to have been lost, the pair Ba alone would not permit you to determine whether you were now at node 2 (via node 1) or node 3 (via node Thus, node 3 would be a disallowed permutation and is, therefore, marked X; likewise, pair C in view of pair A. As a result, to comply with this detection criterion, the maximum length initialization vectors where any consecutive pair of words would unambiguously locate the data would be: .SS or its cyclical rotation: SSSa; a complementary tree beginning with S would also exist, having their two inverses, SSSSS and SSSSS.

Let's say that the initialization vector SSSSS is the one of those four selected as the predetermined arrangement to precede the data. Although the synch word, S, is itself a 21bit string, this initialization vector could be more simply represented in memory by a minimum number of bit symbols, S=02, S=12. The decoded initialization vector would then be *d reduced to 001102. If, let's say two consecutive words, 012, were detected, the actual distance from the detected pair to the data is proportional to the intersymbol distance that the detected symbols, 012, must be advanced along the initialization vector symbols 001102, until a match is found.

(The physical implementation would, of course, be through a table and the distance from the beginning of that table to the 91/05423 PCT/US90/04920 -6corresponding index into that table. The same table, with differing beginning pointers, could be used by the transmitter and receiver to simplify both the encoding and decoding, particularly in cyclical rotations for encryption applications.) Thus, using only one correlator/correlation, and two words (one synch pattern and its inverse), the location of data can be unambiguously established from the unique permutation detected from any two consecutive words.

In QAM phase-modulated systems, rather than differentiating synch words by their high positive and negative (inverse) bit correlations, a single synch word, S, could be differentiated by the absolute phase associated with its complex correlation.

Thus, where transmitter and receiver I/Q channels are phasesynchronized, B would be logically equivalent to synch pattern S (ref: zero degrees) rotated by 180 degrees (in n/4 QPSK quadrature modulation, four words X, X, Y, and Y. are easily modeled using one synch pattern, no inverses, but four phases).

Where the transmitter and receiver are not phasesynchronized, the relative phase shift in complex-correlation from word-to-word can be used to difIferentiate the words instead. A phase shift is introduced by inserting, between words, bits whose sole function is to rotate the relative phase of the following word. Figure 3 is a relative phase permutation tree according to the invention. In the same manner and under the same detection criterion as Figure 2, Figure 3 illustrates, moving to the left, S transmitted at zero degrees relative phase shift with respect to the first and, moving to the right, S transmitted at 180 degrees relative phase shift. If, S A0 (no phase change word to word) and S A180 (180 degree phase change word to word), the four maximum length initialization vectors in the relative phase domain are, as illustrated: i -~Lu~---~l~lllll~ WO 91/05423 PCT/US90/04920 -7 A180 A180 AO AO A180 (corresponding to SSSS) A180 AO A0 A180 A180 (corresponding to SSSSS A0 AO A180 A180 AO (corresponding to SSSSS) AO A180 A180 AO AO (corresponding to SU§SS as in the bit-domain of Figure 2).

Thus, there has been provided a mechanism for block synchronization. It comprises: predeterminally arranging permutations of synchronization words about a point of interest, transmitting such arrangement, receiving that transmission having permuted synchronization words predeterminally arranged about that point of interest, detecting at least part of certain permutations of those synchronization words, and locating the point of interest with reference to the permutation of one detected word about another and their arrangement about the point of interest.

The attendant advantages of this invention include a substantial reduction in the number of correlators or correlations required for detection and greater immunity to faded or otherwise lost signals. As a further advantage, it is well understood by those ordinarily skilled in this field how to construct the means for carrying out this methodology.

While the preferred embodiment of the invention has been described and shown, it will be appreciated by those skilled in this field that other variations and modifications of this invention may be implemented. Although the permutation tree gets far more complex, the invention accommodates various detection criterion; for example, initialization vector SiSS satisfies the detection criterion that ANY two (including nonconsecutive) detections unambiguously locate the data, i.e., DDX, DXD, XDD, OR DXXD, where D indicates a detection and X WO 91/05423 PCT/US90/04920 8 indicates a missed detection or "don't care". Similarly, A180 and AO satisfies the detection criteria: DD, DXD, and DXXD.

In the same spirit as that of the foregoing invention, the information between synchronization words could embed information about where the data message begins. A vaiable time delay (a variable number of bits) could be interleaved between successive repetitions of a single synchronization word Thus, in the following initialization vector: S1 S 2 S 3 S 4 S 5 S DATA MESSAGE the numerals between successive synchronization words indicates the number of delay bits between sync words.

Since each two successive synch words has a unique characteristics delay between them, the beginning of the data message can be unambiguously located from the detection of the delay between any two successive synch words. Moreover, since the delay is cumulative (22 bits to the second synch, 23 between the second and third, 45 between the first and third, 47 between the second and fourth, etc.), the data can be unambiguously located from the detection of ANY two synch words. The bits so interleaved, more than functioning as mere place-holders, could be utilized to carry other information; thus, 1+2+3+4+5 or 15 bits of information could be encoded in the delay bits themselves.

Although this technique has been presented utilizing a single sync word having high autocorrelation properties to reduced the number of correlators/correlations, it need not be so limited.

11 WO 91/05423 PCT/US90/04920 -9 These and all other variations and adaptations are expected to fall within the ambit of the appended claims.

i

Claims

2. A method as claimed in claim 1 wherein the step of predeterminally arranging comprises the step of spacing the synchronization words variably in relation to the information of interest.
3. The method of claim 1 wherein the synchronization words are permuted synchronization words.
4. A method of synchronization comprising: receiving a signal having information of interest and synchronization words predeterminally arranged in the signal, detecting at least certain of those synchronization words and their arrangement with respect to one another, and synchronizing to the information of interest with reference to the arrangement of one detected word to another and their arrangement in relation to the 30 information of interest.
5. A method as claimed in claim 4 wherein "i synchronization words are variably spaced in relation to the information of interest.
6. A method of synchronization comprising the steps of: a-ranging a first, a second, and a third synchronization words in a data transmission; transmitting the data transmission from a transmitter; 39 receiving the data transmission at a receiver; MJP 1 11 detecting the first and third synchronization words; determining the arrangement of the first to the third synchronization words; and synchronizing the receiver based upon the arrangement.
7. A method of synchronizing a data transmission comprising the steps of: inserting a first synchronization word in the data transmission; inserting a second synchronization word in the data transmission a first predetermined distance from the first synchronization word; inserting a third synchronization word in the data transmission a second predetermined distance, different from the first predetermined distaw.e, from the second synchronization word; transmitting the data transmission from a transmitter; receiving the data transmission at a receiver; detecting one of said first, second, and third synchronization words; detecting another of said first, second, and third synchronization words; determining a distance between the detected synchronization words; and synchronizing to the information of interest using said first detected synchronization word and said determined distance between the detected synchronization words. 30 8. The method of claim 7 wherein said first, second, and third words each consists of a first bit pattern.
9. A method of synchronizing a data transmission comprising the steps of: inserting a first synchronization word having a first bit pattern in the data transmission; inserting a second synchronization word having said first bit pattern in the data transmission a first predetermined distance from the first synchronization word; 39 i,inserting a third synchronization word having the 4 12 first bit pattern in the data transmission a second predetermined distance, different from said first predetermined distance, from the second synchronization word! transmitting the data transmission from a transmitter; receiving the data transmission at a receiver; detecting one of said first, second, and third synchronization words; detecting another of said first, second, and third synchronization words; determining a distance between the detected synchronization words; and synchronizing to the information of interest using said first detected synchronization word and said determined distance between the detected synchronization words. A method of synchronization substantially as herein described with reference to the accompanying drawings. DATED: 25 November, 1992. PHILLIPS ORMONDE FITZPATRICK Attorneys for: MOTOROLA INC. DC A-'t- 4045u .1 39MJP MJP