IEEE TRANSACTIONS O N COMMUNICATIONS, VOL. COM-20, NO. 2, APRIL 1972
`
`Optimum Frame Synchronization
`
`115
`
`JAMES L. MASSEY, FELLOW, IEEE
`
`Abstract-This paper considers the optimum method for locating
`a sync word periodically imbedded in binary data and received over
`the additive white Gaussian noise channel.
`It is shown that the
`optimum rule is to select the location that maximizes the sum of the
`correlation and a correction term. Simulations
`are reported that
`show approximately a 3-dB improvement at interesting signal-to-
`noise ratios compared to a pure correlation rule. Extensions
`are
`(PSK) sync” case where the
`given to the
`“phase-shift keyed
`detector output has a binary ambiguity and to the case of Gaussian
`data.
`
`decisions. Section
`the receiver can make tentative bit
`I11 gives the necessary modification for
`the “phase-
`shift keyed (PSK) sync” case where the bit values are
`ambiguous until after frame synchronization is
`ob-
`tained. Section
`I V contains the results
`of simulations
`comparing the performance
`of the optimum rule and
`the
`the correlation rule. Section V gives a derivation of
`optimum sync word locating rule
`when the data, rather
`than being random binary digits, are Gaussian random
`variables as might be the case in some pulse-amplitude
`I. INTRODUCTION
`modulation schemes.
`HE MOST widely
`used method for providing
`It should be emphasized
`that our analysis applies
`frame synchronization in a binary signaling scheme
`only to the case
`of a sync word periodically imbedded
`is to insert a
`fixed binary pattern or “sync word”
`into a data stream,
`which is the usual case in space
`periodically into
`the data stream.
`On the assumption
`to the “one-
`telemetry. Specifically, it does not apply
`that symbol synchronization has already
`been obtained,
`shot” synchronization problem where the sync word
`the receiver obtains frame synchronization by locating
`is prefixed
`to the data stream and
`is itself preceded
`the position of
`the sync word in the
`received data
`1-0 pattern. It re-
`either by no signal or by a periodic
`stream.
`mains as an interesting open problem to
`find the opti-
`I n his pioneering work
`[l] on frame synchronization,
`mum synchronization rule for this one-shot case.
`Barker assumed that the sync word would be
`located
`IZ. DERIVATION OF THE OPTIMAL SYNC-WORD
`by passing the received digits through a “pattern recog-
`nizer,” which was simply a device
`to correlate successive
`LOCATING RULE
`of the received sequence with the L-
`L-digit segments
`Let N denote the frame length,
`i.e., each L-digit sync
`digit sync word. The segment giving the nlaximum
`by N-L random binary-data bits. We
`word is followed
`correlation would be
`taken as the
`location of the sync
`to process an N digit span
`assume that the receiver is
`word. Virtually all subsequent work on frame synchroni-
`of the received sequence in order to locate the sync word
`zation has assumed this same correlation
`decision rule,
`If n such spans are actually to be
`contained therein.
`perhaps for simplicity and perhaps in the belief that this
`used, the problem reduces to the above for a frame
`decision rule was optimal.
`I n his encyclopedic coverage
`length of nN digits and a sync word of length nL.
`of synchronization, Stiffer
`recognizes
`12, pp. 499-5021
`. . . , r N - l ) denote the received span to
`Let T = (yo,
`that the data
`surrounding the sync word should
`be
`be processed where
`each rr is the detector output over
`taken into account by an optimal
`decision rule, but in-
`one of the assumed-known bit intervals. The sync word is
`dicates that the analysis becomes intractable and that
`a priori equally likely to begin in any of the N positions
`the resulting true optimal
`decision rule would be
`im-
`of T . We will consider digit ro to follow digit r N - 1 so as to
`practical to implement.
`account for the case when the sync word begins somewhere
`decision rule
`In this paper,
`we derive the optimal
`in the last L-1 digits of T and ali subscripts on received
`for locating the sync word
`on the additive white Gaus-
`N . For example,
`digits will hereafter be taken modulo
`sian noise channel
`and show that the effect of the data
`r N + Z is the digit rz.
`is merely to add a “correction” term to the correlator
`. . . , s[,-,), where each si is either +1
`Let s = (so, sl,
`or -1, be the sync word and let d = ( d L , a,,,, . . * ,
`output so that the optimum rule is nearly as simple to
`implement as the ordinary correlation rule. This deriva-
`denote N-L random data bits where the di are statistically
`tion is given in Section I1 for the standard case where
`independent random variables satisfying P r [di = +1] =
`Pr [di = - 11 = 3. Consider next the concatenation
`sd = (so, sl, . . . , sL-,, d L , . . . ,
`Let T be the cyclic
`shift operator defined by T(sd) = ( d N - 1 , so, . .
`1 S L - 1 ,
`d,, . . . , dN-,J.
`If the sync word actually begins in digit
`rm of T , we can express the received segment as
`T = 4 3 T“(sd) + n
`where each received digit would have value either + z/E
`
`Paper approved by the Communication Theory Committee of
`the IEEE Communications Society
`for publicat,ion without oral
`presentation. This work was supported by the National Aeronau-
`tics and Space Administration under NASA GRANT NGL 15-
`004-026 a t the University of Notre Dame in liaison with the God-
`.dard Space Flight Center. Manuscript
`received August 16, 1971.
`The author is with the Department of Electrical Engineering.
`46556. He is on
`University of Notre Dame, Notre Dame, Ind.
`leave a t the Laboratory for Communication Theory, Royal Tech-
`nical University of Denmark, Lyngby, Denmark.
`
`(1)
`
`Exhibit IV 2016
`IPR2014-01149
`
`

`
`116
`or - fi in the absence
`of noise, and where n =
`(no, nl, . .. , nN-J is the contribution of the additive
`white Gaussian noise
`to the detector outputs. The
`com-
`ponents ni are statistically independent Gaussian random
`N 0 / 2 where N o is
`variables with 0 mean and variance
`the one-sided noise spectral density. Let e = ( p o , p l , . . ,
`p N - J denote the actual value assumed by the random
`vector r. Then the optimum [in the sense,-of maximizing
`the probability
`of correctly locating the sync word]
`decision rule is to choose the estimate of m as the,value p,
`0 5 p < N , which maximizes X, = Pr [m = p I r = e],
`which by the mixed Bayed rule [3, p. 751 for events and
`random variables becomes SI = pr(p I m = p ) Pr [m =
`lower case
`p denotes the
`p ] / p r ( p ) . Here and hereafter,
`density function
`of the subscripted random variable.
`Since Pr [m = p] = 1/N for all p, we may equivalently
`maximize S, = pr(e I m = p ) . Letting 6 = ( 8 L , 6,+,, . . . ,
`where each 6; is either + 1 or - 1, denote a possible
`value of the random data vector d, we have
`p r ( p I d = 6, m = p ) Pr (d = 6).
`S, =
`a l l 6
`Since Pr (d = 6) = 2-‘N-L’ for all 6, we may equivalently
`maximize
`
`(2)
`
`S, =
`
`pr(e I d = 6, m = PI,
`a l l 6
`which upon making use
`
`of (1) becomes
`
`By the Gaussian assumption on n, we have
`
`Substituting this expression into
`(3) and removing all
`factors independent of p, we may equivalently maximize
`
`(4) noting that each ai
`Carrying out the summation in
`] E 2 cosh (2 v‘% pi+,/Nfl).
`takes on only the values
`+1 and -1, we obtain
`
`x, [E
`
`e 2 f i ~ i + p s ~ / N o
`
`IEEE TRANSACTIONS ON COMMUNICATIONS, APRIL 1972
`is a sum over all components of e and hence is independent
`of p, we may subtract this sum from S , without affecting
`the maximization t o give
`
`X, =
`
`L-1
`
`i = O
`
`L-I
`2 d z p i + , ~ / N o - log, cash ( 2 d E ~ i + , , / N o )
`i = O
`
`of p in the
`be maximized by choice
`as the quantity to
`optimum decision rule. Slightly rewriting, we summarize
`as follows.
`Sync W o d : Given
`Optimuan Rule for Locating the
`the received segment p, take the estimate
`of the sync
`word location m to be the value of p , 0 5 p < N , which
`maximizes the statistic
`
`where
`
`f(x) = ( N 0 / 2 d E ) log, cosh ( 2 d Z s/No).
`
`(6)
`
`(5) is
`
`It should be noted that the first summation in
`the ordinary correlation. The second summation repre-
`sents a kind
`of voltage or energy correction required
`to account for the random data surrounding the sync
`word. It should also
`be clear that the optimum sta-
`tistic S is nearly as easy to calculate as the correlation
`above, particularly in the practical case where the de-
`tector outputs are quantized to
`8 or 16 values (3- or
`4-bit quant,ization.)
`In this case, only a small number
`of values of the function f in (6) need be stored for use
`in forming the correction term.
`of
`Additional insight into the nature
`the optimum
`statistic S can be gained by examining its form in the
`limiting cases of very high and very
`low signal-to-noise
`ratios.
`When E / N o >> 1, the argument of the cosh in
`(6) is
`much greater t.han 1 with high probability
`so that we
`(4) elf’[. Using this ap-
`may approximate
`cosh (y) as
`proximation in
`(6), we obtain
`c
`
`c
`
`L-I
`L - 1
`i = O &Pi+,, -
`i = O ( P i + , , l .
`
`s =
`
`i = L
`, = O
`Taking logarithms, we can equivalently maximize
`
`i = O
`
`Noting that
`
`Note that whenever si and pi+s agree in sign, their con-
`tribution to the first summation in
`(7) is exactly can-
`celled by the term
`in the second summation.
`-Ipi+el
`Thus, only negatively correlated terms contribute to the
`statistic S and the optimum
`to
`decision rule reduces
`choosing that location p for the sync word that yields the
`least total negative correlation.
`When B/No << 1, the argument of the cosh in
`(6) is
`much smaller than
`1 with high probability so that we
`may closely approximate log, cosh (y) ley the first term
`(t) y2. Using
`in its Maclaurin series expansion, namely
`
`

`
`MASSEY: OPTIMUM
`FRAME SYNCHRONIZATION
`this approximation in (6), we obtain
`sjpi+, - - c
`4 E L - l
`No
`
`S =
`
`I, - 1
`
`i = O
`
`P L C P 2
`
`i=o
`as the statistic to be maximized by the optimum decision
`rule. From the form. of the second summation in (8), we
`see that the correction term is an energy correction in
`this small signal-to-noise ratio case.
`111. PSK FRAME SYNCHRONIZATION
`[2, p. 3721, when a binary PSI<
`As Stiffler has noted
`signal is demodulated using
`a carrier reference derived
`from the modulated signal, there is
`a binary ambiguity
`in the detector output. With probability +, the detector
`output will be ri = ti + ni where ti is the transmitted
`signal (4% si or 4z d i ) , and with probability
`3 the
`detector output will be ri = -ti - ni. When this am-
`biguity is included in the analysis,
`a derivation very
`11, the details of which will
`similar to that in Section
`be omitted here, leads to the following.
`Optimum Rule for PSK Frame Sync: Given the
`received segment e, take the estimate of the sync-word
`location m to be the value of p, 0 5 p < N , which max-
`imizes the statistic
`
`X = log, cosh (P) -
`
`L-1
`
`i = O
`
`log, cosh
`
`( 2 4 pi+,,/NO) (9)
`
`where
`
`sipi,,.
`
`(10)
`
`L-1
`P = ( 2 d z / N O )
`i = O
`A simple approximate form for this statistic is readily
`obtained. The correlation sum P can be expected to be
`in general so that the
`quite large
`approximation log,
`cosh ( P ) = IPJ - log, 2 will be quite accurate. Using this
`approximation, we obtain as the statistic to be maximized
`
`I
`
`L-1
`
`X’ =
`
`I
`
`c
`
`f(Pi+,)
`
`L-1
`sipi+, -
`i = O
`i = O
`in (6). We note that the usual cor-
`where f ( ) is given
`PSK frame synchronization
`relation rule for
`is just to
`(11). Again
`choose p to maximize the first summation in
`we see the optimal decision rule adds a correction term
`to this usual statistic.
`IV. SIMULATION RESULTS
`The basic question remaining is whether the optimum
`decision rule for frame synchronization provides
`sig-
`nificantly better performance than the ordinarily
`used
`but suboptimum correlation method. A theoretical com-
`parison of performances is ruled out by the complicated
`relationship between probability
`of incorrect synchroni-
`zation and channel signal-to-noise ratio. For this reason,
`a Monte Carlo simulation was performed to obtain suf-
`
`117
`
`(12)
`
`(2j - 1) 1/E/6,
`
`ficient empirical data for a performance comparison for
`channel signal-to-noise ratios E / N o near unity which is
`the range of practical interest in space telemetry.
`T o conform to usual communications practice, the
`detector outputs ri in the simulation were quantized to
`16 levels, and it was verified that 8 levels gave essentially
`the same results. The quantized values used were
`-8 < j 5 8,
`and the quantization boundaries were taken halfway be-
`tween adjacent quantization values. Simulations
`were
`performed using several different sync words and frame
`I shows
`lengths as well as signal-to-noise ratios. Table
`the results of standard frame synchronization by both the
`optimum and the correlation rules for two Barker se-
`quences and one Neuman-Hofman
`[4] sequence as sync
`words and for three different signal-to-noise ratios. The
`same noise and data sequences
`were used with
`all sync
`sequences. Inspection
`of this table reveals a 3-dB ad-
`E/No about
`vantage for the optimum decision rule for
`1 as seen by the fact that the optimum
`decision rule
`performs the same a t E / N o = 1 as does the correlation
`rule a t E/No = 2. (This quite precise gain
`of 3 dB was
`obtained in all the simulations performed that
`cover a
`wide range
`of sync-word lengths and frame lengths.)
`The gain
`becomes less as the channel
`becomes more
`noisy.
`I that the Neuman-
`It should be noted from Table
`Hofman sequence outperforms the Barker sequence
`of
`the same length as a sync word. The Neuman-Hofman
`sequence was designed
`so as to maximize performance
`with a correlation
`decision rule. This simulation also
`shows that it is a good choice for a sync word to be used
`with the optimum decision rule.
`Table I1 shows the results of PSK frame synchroniza-
`tion for the same sequences and signal-to-noise ratios as
`in Table I. The general nature of the results are the same
`with the optimum decision rule at E / N o = 1 showing the
`It
`same 3-dB improvement over the correlation rule.
`should be mentioned that the “optimum” rule
`used in
`I1 was actually the
`the simulations reported in Table
`S of
`rule using
`the approximately optimum statistic
`(12). This decision rule is indiscernible from the true
`optimum decision rule.
`
`V. GAUSSIAN DATA
`
`the
`of completeness, we now consider
`For the sake
`case when the data digits di, rather than being limited to
`values of f l and -1, are instead statistically independ-
`ent zero-mean Gaussian random variables with variance
`unity. Such a situation might describe digitized
`voice
`transmission with pulse-amplitude modulation
`(PAM).
`To derive the optimum sync-word location rule, we note
`that the analysis
`in Section I1 up to (2) is unchanged
`
`

`
`118
`
`
`
`
`
`IEEE TRANSACTIONS ON COMMUNICATIONS,
`
`APRIL 1972
`
`TABLE I
`
`
`PERCENT.4GE OF ERRONEOUSLY SYNCHRONIZED FRAMES I N 100 SYNCHRONIZATION TRIALS USING THE OPTIMUM (OPT) AND THE CORRELATION
`(COR) RULES FOR LOCATING THE SYNC WORD
`
`
`
`Sync Word
`
`E / N o = f
`OPT
`COR
`
`E/No = 1
`OPT
`COR
`
`E/No = 2
`OPT
`COR
`
`L = 13. N = 91 Barker seauence
`s = ( l , l , l , l , l , - 1 , - l , l , l , - l , l , - l , l , )
`L = 13, N = 91 Neuman-Hofman sequence
`s = (-1, -1, -1,
`
`-1, -1,
`
`-1, -1, 1,
`-1, 1, 1,
`L = 7, N = 28 Barker sequence
`s = (1,
`-1,
`
`
`
`1, 1, -1, -1, -1,) 0.21 0.32 0.40 0.45
`
`
`
`
`
`
`
`0.31
`0.28
`
`-1, 1)
`
`0.42
`
`
`0.32 0.07 0.18
`
`0.09
`
`0.19
`
`0 .oo
`0 .oo
`0.09
`
`0.08
`0.07
`0.22
`
`TABLE I1
`
`PERCENTAGE OF ERRONEOUSLY SYNCHRONIZED FRAMES I N 100 TRIALS FOR PSK FRAME sYNCHRONIZ.4TION USING THE OPT -4ND T H E COR
`
`
`RULES FOR LOCATING THE SYNC WORD
`
`
`
`Sync Word
`
`E/No = 4
`OPT
`COR
`
`E / N Q 1
`COR
`OPT
`
`E/NQ = 2
`COR
`OPT
`
`L = 13, N = 91 Barker sequence
`s = ( l , l , l , l , l , - l , - l , l , l , - l , l , - l , l )
`L = 13, N = 91 Neuman-Hofman sequence
`s = ,(-1, -1, -1, -1, -1, -1, 1, 1, -1, -1, 1,
`L = 7, N = 28 Barker sequence
`s = 1, -1, 1, 1, -1,
`-1, -1)
`
`0.47
`
`-1, 1)
`0.49
`
`
`0.63
`
`0.39
`
`0.39
`0.63
`
`0.27
`0.24
`0.46
`
`
`
`
`
`0.14
`0.14
`0.37
`
`0 .oo
`0 .oo
`0.21
`
`0.12
`0.13
`0.40
`
`/
`and (2) becomes replaced by
`
`the statistic
`
`of n are
`Using the assumption that the components
`statistically independent Gaussian random variables with
`mean 0 and variance N 0 / 2 and that the components of d
`are statistically independent Gaussian random variables
`with mean 0 and variance 1, we obtain
`
`Carrying out the indicated integrations and dropping
`factors independent of p, we may equivalently maximize
`
`i = O
`
`c
`
`L - 1
`
`Adding the quantity
`
`i = O
`
`c
`NO + 2E % = L
`&Pi+’ -
`
`1
`
`N - l
`
`which is independent of p, we may equivalently maximize
`
`be maximized
`Once again we see that the statistic to
`by the optimum sync-word location rule consists of the
`ordinary correlation together with a correction term. For
`Gaussian data, the correction term is again
`seen to be a
`true energy correction.
`
`VI. SUMMARY
`This paper has considered the problem of obtaining an
`optimal estimate of the location of the sync word in a
`data frame for binary data in the standard case and
`in the PSK sync case and also for Gaussian data samples.
`I n all cases it was shown that the optimum decision rule
`is to maximize a statistic that is the sum
`of two terms,
`the first being the usual correlation and the second being
`an energy correction that takes into account the fact
`that the sync word is imbedded in data. It was verified
`by simulation that the optimum rule provides about a
`3-dB advantage over the ordinary correlation rule in
`the interesting case of signal-to-noise ratios E/No near
`unity. It was also noted
`that the optimum decision rule
`is only slightly more complicated to implement than the
`correlation rule.
`
`VII. ACKNOWLEDGMENT
`C. Seguin for programming
`The author is grateful to
`the simulations reported in Section IV and to the re-
`viewers of this paper for several helpful comments.
`
`

`
`
`
`
`
`2, APRIL 1972 119
`
`
`IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. COM-20, NO.
`
`REFERENCES
`111 R. H. Barker, “Group synchronization of binary digital sys-
`tems,” in ~Commwnicatiom Theory, W. Jackson, Ed. London.
`Butterworth. 1953. an. 273-287.
`[21 J. J . Stiffler, ’Theory’dj Synchronous Comnmnications. Engle-
`wood Cliffs, N. J.: Prentice-Hall, 1971.
`[31 J. M. Wozencraft and I. M. Jacobs, Principles of Communi-
`cation Engineering. New York: Wiley, i965.
`[41 F. Neuman and L. Hofman,
`“New pulse sequences with de-
`sirable correlation properties,” in Proc. Nat. Telemetry Conj.,
`Washington, D.C., Apr. 1971, pp. 27-282.
`
`S.M. and Ph.D. degrees in electrical engineer-
`ing from the Massachusetts Institute of Tech-
`nology, Cambridge, in 1960 and 1962, re-
`spectively.
`From 1956 to 1959 he served as a Com-
`munications Officer in the U. S. Marine
`Corps. Since 1962 he has been on the Faculty
`of the University of Notre Dame where he is
`now Professor of Electrical Engineering.
`I n
`1966-1967, he was a Visiting Associate Pro-
`at M.I.T.
`fessor of Electrical Engineering
`He is spending 1971-1972 as a Visiting Professor at the Royal
`Technical University of Denmark, Lyngby.
`Dr. Massey is a member of Eta Kappa Nu, Sigma Xi, Tau Beta Pi,
`and the American Society for Engineering Education. He is a past
`chairman of the IEEE Group on Information Theory.
`
`James L. Massey (S’54-M’55-F’71) was born in Wauseon, Ohio,
`on February 11, 1934. He received the B.S.E.E. degree from the
`in 1956, and the
`University of Notre Dame, Notre Dame, Ind.,
`
`Performance of a First-Order Transition Sampling Digital
`Phase-Locked Loop Using Random-Walk Models
`
`Abstract-A new mechanization of a first-order all digital phase-
`locked loop (ADPLL) is discussed and analyzed. The purpose of the
`loop is to provide continuous tracking of the incoming waveform
`corrupted by the presence of white Gaussian noise (WGN). Based on
`a random-walk model, solutions are obtained for the steady-state
`timing-error variance and mean time to slip a cycle. A s a result of the
`mean first-time-to-slip analysis, a difference
`equation and
`its
`solution are obtained that generalize a result of Feller [l]. Using a
`procedure that appears new, an upper bound on
`the timing-error
`bias due to a Doppler shift of the synchronized waveform is also
`derived. An example, for which
`the results presented here are
`applicable, is considered in some detail.
`
`I. INTRODUCTION
`long
`NALOG phase-locked loops
`(PLL) have
`played an important role in modern communica-
`tion systems. Their theory
`of operation is well
`documented in numerous papers throughout the past
`15
`years. The
`increased inhest in digital
`communication
`systems, due primarily to the decreased
`size and cost
`and increased reliability, led to the digital phase-locked
`loop (DPLL). One of the earliest reported DPL,L was
`
`Paper approved for publication by the Communication Theory
`Committee of
`the IEEE Communications Society
`after pre-
`sentation at the 4th Hawaii
`International conference
`on Sys-
`tem Science, January 1971. This paper
`presents the results of
`one phase of research carried out at the Jet Propulsion Labora-
`tory, California
`Institute of Technology, under Contract NAS
`7-100, sponsored by the National
`Aeronautics and Space Ad-
`ministration. Manuscript received July 1, 1971.
`The author
`is with the Jet Propulsion Laboratory, Pasadena,
`Calif. 91103.
`
`constructed by adding a samplc and hold circuit between
`(VCO)
`the filter and the voltage-controlled oscillator
`[2] in an analog
`of integrated
`loop. With the advent
`circuits, more
`refined and more nearly all-digital
`PLL
`emerged [3], [4]. These loops utilize analog integration
`(MI) type phase detector,
`for the midphase in-phase
`with the remaining functions
`of the loop being accom-
`[5] was, ex-
`plished digitally. A loop reported by Gota
`cept, for the use of a digital to analog converter, all digi-
`tal in opemtion; he did not consider noise in the analysis
`of his loop.
`the DPLL
`of
`common function
`To date the most
`has been t’o provide synchronization of a signal.’ How-
`ever, this is not the only application, for example, an all-
`digital phase-locked
`loop (ADPLL) has been built for
`FM demodulation [6]. It was designed
`for potential
`application in large multiple data set. installations, which
`provide low-speed serial data communications, for time-
`shared computers. Additional applications
`of D P L L
`are summarized in a paper by Gupta
`171.
`type
`new simple
`Recently an ADPLL, employing a
`of phase detector has been reported [8] for square-wave
`signal waveforms. The loop was conceived
`to provide
`tracking of the subcarrier signal for a command system.
`Basically, tracking was accomplished by 1) sampling the
`input waveform at the points in time where the signal
`transitions or axis crossing occur, 2) accumulating m of
`these samples, and 3) incrementing the phase of the local
`reference (clock) in such a direction as to bring the value