Copyright @ 1973 American Telephone and Telegraph Company
`TnE BELL SYsTEM TECIINICAL JouRNAL
`Vol. 52, No. 10, December, 1973
`Printed in U.S.A.
`
`A Universal Digital Data Scrambler
`
`By DAVID G. LEEPER
`(Manuscript received May 22, 1973)
`Analyses in the literature of digital communications often presuppose
`that the digital source is "white," that is, that it produces stochastically
`independent equiprobable symbols. In this paper we show that it is possible
`to "whiten" to any degree all the first- and second-order statistics of any
`binary source at the cost of an arbitrarily small controllable error rate.
`Specifically, we prove that the self-synchronizing digital data scrambler,
`already shown effective at scrambling strictly periodic data sources, will
`scramble any binary source to an arbitrarily small first- and second-order
`probability density imbalance o if (i) the source is first passed through the
`equivalent of a symmetric memoryless channel with an arbitrarily small
`but nonzero error probability E, and (ii) the scrambler contains M stages
`where
`
`M ;?; 1 + log{ (In 2o) /ln (1 - 2E)].
`Some interpretations and applications of this result are included.
`
`I. INTRODUCTION AND SUMMARY
`
`Digital transmission systems often have impairments which vary
`with the statistics of the digital source. Timing, crosstalk, and equaliza(cid:173)
`tion problems usually involve source statistics in some way. While
`redundant transmission codes may be used to help isolate system
`performance from source statistics, the isolation is not always complete,
`and such codes generate additional problems by increasing the required
`symbol rate or the number of levels per symbol which must be trans(cid:173)
`mitted. In addition, with or without transmission codes, it is always
`easiest to analyze or predict system impairments if we assume that the
`source symbols are stochastically independent and equiprobable. We
`shall refer to such a source as "white" because of the obvious analogy
`to white Gaussian noise. Methods for "whitening" the statistics of
`digital sources without using redundant coding generally come under
`the heading of scrambling.
`
`1851
`
`IV 2003
`IPR2014-01149
`
`

`

`1852
`
`THE BE LL SYSTEM T ECHNICAL JOURNAL, DECEMBER 1973
`
`We describe here a nonredundant scrambling/ descrambling method
`which in principle will satisfactorily whiten the statistics of any binary
`source. The technique is based upon the self-synchronizing digital data
`scrambler. Savage has shown 1 that this device is very effective at
`scrambling strictly periodic digital sources. In this paper it is proven
`that t he same device will scramble any binary digital source to a n
`arbitrarily small first- and second-order probability density imbalance
`o if (i) the source is first passed through t he equivalent of a binary
`symmetric memorylesR channel with an arbitrarily small but nonzero
`error probability E, and (ii) the scrambler contains M stages where
`M ~ 1 + log2 [(In 2o)/ ln (1 - 2e)]. In other words, at the cost of an
`arbitrarily small controllable error rate, one can "whiten" to any degree
`all the first- and second-order statistics of any binary source. This relaxes
`the restriction frequently found in the literature in which the source is
`assumed a priori to produce only independent equiprobable symbols.
`An auxmary result is that the above relation for M is useful when
`designing a standard self-synchronizing scrambler for a given applica(cid:173)
`tion. Heuristically speaking, the relation expresses the "power" of the
`scrambler by linking the "randomnP.ss" of t he input and output to the
`scrambler length, M.
`In Sections II and III of this paper we examine some properties of
`scramblers, maximal length sequencP.s, and mod-2 sums of binary
`random variables. With these discussions as background, we prove the
`main theorem in Section IV. In Section V we derive bounds for the
`autocorrelation of the scrambled sequence. Section VI contains some
`practical considerations involved in applying the theorem of Section
`IV. B eacuse t hey add insight, we give simple direct proofs for the
`lemmas and theorem of Sections III and IV.
`
`II. SCRAMBLERS AND MAXIMAL LENGTH SEQUENCES
`
`Figure 1 shows a five-stage self-synchronizing scrambler and de(cid:173)
`scrambler. 1 As seen, both are linear sequential filters, the scrambler
`ut ilizing feedback paths and the descrambler feedforward paths. Each
`cell represents a unit delay. We restrict our attention to the binary
`case and use the symbols ® and E to denote mod-2 addition. R epre(cid:173)
`senting the data as shown, we have
`bk = ak ® bk- a ® b~c-6
`
`and
`
`Ct = b~c ® b~c-a ® b~c-5 = at,
`which shows that the descrambled sequence is identically equal to the
`
`

`

`A UNIVERSAL DIGITAL DA'l'A SCRAMBLER
`
`1853
`
`bk
`OUTPUT
`
`(a)
`
`••
`
`INPUT
`
`b k
`INPUT
`
`(b)
`Fig. 1-(a) Five-stage scrambler. (b) Five-stage descrambler.
`
`original data sequence. The descrambler is self-synchronizing because
`the effect of a channel error, insertion, or deletion lasts only as long as
`the total delay of the register, five bit-intervals in this example.
`Let us consider the general scrambler of Fig. 2a with the input
`stream disconnected. Under such a condition, the scrambler becomes
`a sequence generator whose output must ultimately become periodic
`because (i) future states of the register are completely determined by
`the present state (the state of the register is the contents of its stages)
`and (ii) only the finite number 2M states are possible, where M equals
`the number of stages. One of these, the all-zeros state, simply leads to
`an all-zeros output. Discounting this state, we see that the longest
`possible period from the generator must be 2M - 1 bits. It is proven in
`the literature2•3 that with the proper choice of feedback taps we can
`generate such a maximal length sequence for any M.
`Registers which generate maximal length sequences make very
`effective scramblers because of their ability to dissociate one scrambler
`output bit from another. This property will enable us to show that two
`arbitrarily chosen output bits tend to be very weakly correlated. We
`state this essential property here in the form of a lemma.
`
`Lemma 1: From Fig. 2a it is evident that each "b" bit is equal to a lengthy
`mod-2 summation of selected "a" bits. Choose two bits, b,. and bn, m > n,
`and define J mn to be the number of "a" bits which enter the summation for
`bm but not the summation f or bn. That is, b,. is dissociated from bn by the
`mod-2 sum of J mn "a" bits.
`Then, if n > 2Af+ t (that is, the scrambler has processed at least 2M+t
`
`

`

`1854
`
`THE BELL SYSTEM TECHNICAL JOURNAL, DECEMBER 1973
`
`••
`
`INPUT
`
`bk
`INPUT
`
`Fig. 2-
`
`(a) Jlf-stage scrambler. (b) M-stage descrambler.
`
`(b)
`
`"a" bits),
`
`m,n
`
`(1)
`
`In other words, after a settling time of 2AIH bits, any chosen pair of
`output bits will differ by the mod-2 sum of at least 2M-
`l input bits.
`Proof: See appendix.
`
`III. MOD-2 SUMS OF BINARY RANDOM VARIABLES
`Throughout this paper we assume that a data sequence may be
`modeled as a sequence of binary random variables defined on a suitable
`probability space. In this section we state as lemmas two essential
`properties of mod-2 sums of binary random variables. Since the
`scrambler output is formed from mod-2 sums of input bits, these
`properties play a key role in determining the scrambler output charac(cid:173)
`teristics. We include the proofs in the text because the equations
`involved will be useful later on.
`
`Lemma 2: Consider two independent binary random variables r1 and r2.
`A third binary random variable r3 = r 1 C±> r 2 • Let
`p ; = P(r; = 1) = I - P(r; = 0),
`
`i = I, 2, 3.
`
`

`

`A UNIVERSAL DIGITAL DATA SCRAMBLER
`
`1855
`
`Then
`
`! I]
`! I, I P1 -
`! I ~ min [I P2 -
`I Pa -
`with equality if and only if P1 or P2 = l, 0, or 1. In other words, ra is
`as close or closer to being equiprobable than either r2 or r1.
`
`Proof: Since r1 and r2 are independent,
`
`(2)
`
`Let
`
`d; = p; -!
`Then by substitution
`
`i = 1, 2, 3.
`
`But since
`
`we have
`
`ld·l < .!
`1 = '2J
`I da l ;;i min [ I dd , I ~ I J
`with equality if and only if I dd or I d2 l = 0 or ! .
`Corollary to Lemma 2: If P1 = t, then Pa = t and ra is independent of r2.
`Proof: Since ra = r1 <±> r2, P(ra = I I r2 = 1) = 1 - P1 = !. But by eq.
`(2), pa = t. Thus, P(ra = 1 lrt = 1) = P(ra = 1) = t, which implies
`ra and r2 are independent.
`
`Lemma 3: Consider now a sequence of independent binary random
`variables {rk, k = 1, 2, ···I with
`P(rk = 1) = 1 - P(rk = 0) = E
`We form the mod-2 sum
`
`for all k.
`
`(3)
`
`and let Pn = P(Rn = 1). Then
`Pn = ![1 -
`(4)
`n ~ 1.
`(1 - 2E)"];
`oo, P" converges to ! for all 0 < E < 1. However,
`Note that, as n -
`we shall be concerned only with finite values for n.
`
`Proof: By applying eq. (2) repeatedly, it is easily shown that the
`sequence p n satisfies
`
`and
`
`n ~ 2,
`
`

`

`1856
`
`THE BELL SYSTEM TECHNICAL JOURNAL, DECEMBER 1973
`
`The solution to this first-order linear difference equation is given by
`eq. (4).
`
`IV. A UNIVERSAL DIGITAL DATA SCRAMBLER
`With the help of the lemmas, we may now derive the main result.
`We model the source as a device which generates a sequence of binary
`random variables I s1c} with completely unknown statistics. Our goal is
`to find a scrambling/ descrambling method such that the scrambled
`sequence { b~c I will have statistics which approach those of the inde(cid:173)
`pendent equiprobable ("white") sequence I w,}. If we attempt to
`scramble I s~c I directly as in Fig. 2, we are faced with a dilemma. The
`scrambler simply provides a one-to-one mapping between its input and
`output. As long as we have no knowledge or control of the statistics of
`I s~c}, the statistics of I b~c I must likewise remain unknown and uncon(cid:173)
`trolled. Hence, the self-synchronizing scrambler alone cannot be
`universal.
`Instead of scrambling directly, we proceed as shown in Fig. 3. The
`source output is first passed through the equivalent of a binary sym(cid:173)
`metric memoryless channel (BSC) with crossover probability E > 0.
`Remarkably, no matter how small E may be, this modification of the
`source sequence is sufficient to guarantee that the first- and second(cid:173)
`order probability densities for I b~c I will approach those of I w~c I to
`within an arbitrarily small difference ~- The only requirement is that
`M, the length of the scrambler, be dependent upon the choice of E and
`~- This is the essence of the theorem which we derive below. (We note
`in passing that the descrambled sequence will now differ from the
`original source sequence by the error rate E, but since E may be chosen
`arbitrarily small, we assume for now that this is of no consequence.)
`To begin, we observe that because of the BSC the scrambler input
`sequence may be written
`
`k = 0, 1, 2, ... '
`
`(5)
`
`where
`
`P(r~c = 0) =E.
`P(r~c = 1) = 1 -
`From Lemma 1 we have seen that the action of theM-stage scrambler
`is to dissociate any chosen pair of bits (bm, bn) by the mod-2 sum of at
`least 2M-I "a" bits. Let us assume that bm and bn are dissociated by
`exactly 2M-t "a" bits and that they are related by
`
`bm = bn <:13 !: az.
`
`2., -I
`
`1-1
`
`(6)
`
`

`

`A UNIVERSAL DIGITAL DATA SCRAMBLER
`
`1857
`
`SOU RCE
`
`, - - - - - - - - -- - --,
`
`'• ! :~, "• -'• e '•
`0~0
`1
`I
`I
`11-EI
`L ___ __ ____ __ _j
`(a)
`
`1-lt---
`
`bk
`__ ....;;__---!, OESCRAMBLER
`
`I M- STAGE
`
`"• - '• e '•
`
`Fig. 3-
`
`(a) Universal scrambler. (b) Descrambler.
`
`(b)
`
`(Here the subscript l is unrelated to the original position of a 1 in the
`scrambler input stream.) In what follows we show that P(bm = 1) ~!
`and that bm and bn are nearly independent. For these purposes the use
`of eq. (6) represents a worst-case analysis. By substitution from eq.
`(5) we may write
`
`(7)
`
`where A and R equal t he first and second bracketed terms, respectively.
`Since the bits comprising R are independent from those comprising A,
`R is independent of A. Furthermore, by Lemma 3,
`
`(8)
`
`Therefore, by Lemma 2, no matter what t he value of P(A = 1),
`o' = I P(bm = 1) -
`t I ~ t[(l - 2E) 2"-'J = o.
`(9)
`It foHows that so long as E > 0 we may force o and o' to be arbitrarily
`small by choosing a large enough M . Specifically, for a given o,
`M ;;;; 1 + log2 [ In (~ .:.o 2E) J ;
`Since o may be made arbitrarily small, the density function p(bm) may
`be made nearly white, and it follows t hat all first-order statistics of the
`scrambled sequence may be made nearly white.
`Our having shown P(bm = 1) ~ t does not by itself show that the
`source has been effectively scrambled. For example, consider a sequence
`
`0 < E < t.
`
`(10)
`
`

`

`1858
`
`THE BELL SYSTEM TECHNICAL JOURNAL, DECEMBER 1973
`
`jx,. } which consists of consecutive blocks of 100 symbols each. All the
`symbols in each block are alike; with probability l they are all ones,
`and with probability ! they are all zeros. Here P(x,. = 1) = l for all n,
`yet the sequence has a very "nonrandom" nature. The implication is
`that to determine the effectiveness of the scrambler, we must also
`evaluate the statistical dependence between scrambler output bits.
`By definition, the variables b"' and b,. are independent if
`
`Accordingly, we define the function
`d(bm, b,.) = p(bm, bn) - p(bm)p(bn)
`= p(bm I b,.)p(b,.) - p(bm)p(b,.)
`
`(11)
`
`and show that the universal scrambler (Fig. 3) bounds the maximum
`value of I d(bm, b,.) 1.
`We do a worst-case analysis by assuming that bm and b,. are related
`by eq. (7). Further, we ignore the "s" bits appearing in eq. (7) because,
`being independent of R, they can only weaken the dependence between
`bm and b,.. Hence, we may compute the maximum value of I d(bm, b,.) I
`by assuming
`
`(12)
`From eqs. (8) and (9) we note P(R = 1) = t - o and for con(cid:173)
`venience we temporarily let P(b,. = 1) = b. Substituting these rela(cid:173)
`tions and eq. (12) into eq. (11), we find that
`I d(bm, b,.) I = 2o[b(1 - b)];
`
`for
`
`Hence, for b = l we obtain the general result
`
`Since o may be forced arbitrarily small if M is given by eq. (10), it
`follows that any pair of output bits may be made nearly independent,
`and we may whiten to any degree all the second-order statistics of the
`source sequence.
`We may also show that the joint (second-order) density p(bm, b,.)
`approaches that for the white sequence. The derivation of eqs. (6) to
`(9) shows that both the density p(b;) and the conditional density
`p(b; I bi) must have values on the interval [ (t - o), ( t + o)] for all
`
`

`

`A UNIVERSAL DIGI'fAL DATA SCRAMBLER
`
`1859
`
`40
`
`20
`
`10
`
`" <(
`>--
`<I: 30
`w
`...J "' ::;;
`
`0 w
`<I:
`::0
`0
`w
`<I:
`<I) w
`
`<I)
`
`<(
`<I:
`u
`
`<I)
`u.
`0
`<I:
`w
`"' ::;;
`::0 z
`
`::;;
`
`Fig. 4--Scrambler stages required as a function of • and ll.
`
`possible values of b,. and bi· Hence,
`
`or
`
`where
`
`I P(b
`m,
`
`,. -
`b )
`
`1 I __ < • + •2 ~ .,
`
`u
`
`u
`
`. - u
`
`4
`
`For the white sequence { Wk l, we know p( Wm, w,.) = i for Wm, w,. = 0, 1.
`Thus the joint density p(bm, b,.) may be whitened to any degree by
`choice of o, e, and M.
`The discussion above constitutes a proof of the following theorem.
`
`Universal Scrambler Theorem: A binary source with unknown output
`statistics is connected to a binary symmetric memoryless channel and an
`M-stage self-synchronizing scrambler as shown in Fig. 3. The channel has
`error probability e where 0 < e < !. The scrambler output is represented
`by a sequence of random variables { b,., n = 0, 1, · · · l and we define
`p(b,.) to be the first-order and p(bm, b,.) the second-order density functions
`for (b,.l . Then for all o > 0; m > n > 2M+l, and bm, b,. = 0, 1,
`
`and
`
`(13)
`
`(14)
`
`

`

`1860
`
`THE BELL SYSTEM TECHNICAL JOURNAL, DECEMBER 1973
`
`provided that
`
`M ~ 1 + log2 [In(~ .:.o 2E) l
`
`(15)
`
`Figure 4 shows the relation between M, E, and o. As seen, M is
`primarily dependent upon E. This may be clarified by rewriting eq.
`(15) for small values of E. We then obtain
`M ~ log2 (1/ E) + log2 [In (1/2o)];
`E « t.
`The primary importance of t his theorem is conceptual. To avoid
`inordinate difficulties, many analyses in the literature of digital trans(cid:173)
`mission must assume a priori that the digital source is white. The
`theorem relaxes this restriction by showing that in concept the first(cid:173)
`and second-order statistics of any source may be made asymptotically
`white. The practical application of this theorem is discussed in
`Section VI.
`
`V. AUTOCORRELATION OF THE SCRAMBLED SEQUENCE
`
`An important second-order statistic of the scrambled sequence is its
`autocorrelation. We define the autocorrelation as the expectation
`
`and for convenience we let the value of bn be + 1 or -1. Clearly,
`R(O) = 1. For k ¢ 0, we compute a bound on I E[bnbn+k] 1. Following
`the argument which led to eq. (12), we have
`I E[bnbn+k] I ~ I E[b .. (b,. Et) R)] I ;
`By definition,
`E[bnbm] = L L ijP(bm = i Ibn = j) P(bn = j).
`i
`
`i
`
`We let bm = b,. Etl R and for convenience
`P(b,. = 1) = b = 1 - P(b,. = -1).
`
`Substituting, the dependency on b vanishes, leaving us with
`E[b,.(bn ® R)] = 2o.
`
`Hence,
`
`for k = 0,
`R(k) = 1
`for k ¢0.
`IR(k) l ~ 2o
`Note that, by forcing o to a small value with proper choice of M and
`E, this autocorrelation approaches that for a "white" digital source
`
`(16)
`
`

`

`A UNIVERSAL DIGITAL DATA SCRAMBLER
`
`1861
`
`RITI
`
`-3T
`
`- 2T
`
`-T
`
`T
`
`2T
`
`JT
`
`(a)
`
`R(TI
`
`1-
`
`--- -,
`I
`I
`I
`
`1
`
`k-TJ
`
`: 1 ____...
`
`I
`I
`L - --..1
`
`UNIT RECTANGULAR PULSES
`
`- JT
`
`-2T
`
`(b)
`
`2T
`
`JT
`
`(a) Autocorrelation for white sequen ce (w1 ). (b) Autocorrelation bound
`Fig. 5-
`for scrambled sequence lb1).
`
`which has R(k) = 0, k ,= 0. This is shown graphically in Fig. 5 which
`shows the autocorrelation of " white" and scrambled sources for unit
`rectangular pulses.
`
`VI. PRACTICAL CONSIDERATIONS
`In practice, the binary symmetric channel required by the theorem
`might be implemented as shown in Fig. 6. The bit rk is a logic "one"
`only when the level from the noise generator exceeds some threshold.
`The threshold is set such that P(rk = 1) = E. The noise source need
`not be white, but values of 11(t) separated by the baud interval should
`
`Fig. 6-0ne possible implementation of the BSC.
`
`

`

`1862
`
`THE BELL SYSTEM TECHNICAL JOURNAL, DECEMBER 1973
`
`be independent. In principle, the combination of this simulated BSC
`and an M-stage self-synchronizing scrambler will form a universal
`scrambler capable of satisfactorily whitening the statistics of any
`binary source. Such a scrambling structure could be used wherever
`randomized bit statistics are essential and a small error rate can be
`tolerated (or perhaps corrected by an error-correcting code).
`There are, of course, good reasons to avoid actual implementation of
`the BSC. First, it may be difficult to generate the rk sequence accu(cid:173)
`rately if E is very small. Second, the deliberate generation of errors, if
`not impractical, is at least unpalatable. Third, and most important,
`many commonly encountered sources do not need it. Self-synchronizing
`scramblers have been used successfully without any prior randomiza(cid:173)
`tion of the source. 4 In this section we consider the operation of the
`scrambler without the BSC and show how a designer may use eq. (15)
`to estimate the required scrambler length for a given application.
`From eqs. (2) and (5) we deduce that the net effect of the binary
`symmetric channel in Fig. 3 is
`
`ak = 0, 1,
`for all k. In other words, because of the BSC there remains a small
`uncertainty as to the value of any "a" bit, even though all the other
`"a" bits might be known. As shown in the theorem, this and the
`dissociation property are sufficient to guarantee effective scrambling.
`Hence, if the designer knew to begin 'v:ith that the source itself had the
`characteristic
`
`(17)
`
`(18)
`
`Bk = 0, 1,
`then no BSC would be necessary, and eq. (15) could be applied directly.
`For example, bit streams encoded from analog waveforms (such as
`frequency-division multiplexed speech) often have such a property, and
`a value for E could be obtained from the coding rule and the amplitude
`distribution of the analog signal.
`For those cases in which a value for E cannot be computed, let us
`assume that the designer has at least some knowledge of the source
`pulse density. He could then proceed by estimating a nominal value for
`E and then decreasing the value to allow some margin. For example, a
`source which produces bit streams known to vary from 10 to 90 percent
`"ones" over short periods (say, several hundred bits) would have a
`nominal E = 0.1. It seems reasonable to allow at least one order of
`magnitude "margin" in the estimate, resulting in E = 0.01. Then from
`Fig. 4 we see that an eight-stage scrambler should be sufficient.
`
`

`

`A UNIVERSAL DIGITAL DATA SCRAMBLER
`
`1863
`
`Of course, estimating E from the source pulse density does not
`guarantee that eq. (18) really holds, but if the source sequence is not
`strictly periodic (the case covered comprehensively by Savage), it is a
`reasonable procedure. The point here is that even when we are un(cid:173)
`willing to commit deliberate errors to guarantee fixed source statistics,
`we may still use eq. (15) to estimate how large a scrambler is required.
`Heuristically speaking, eq. (15) is an expression for the "power" of
`the scrambler, relating the "randomness" of the input and output to
`the number of scrambler stages.
`
`VII. CONCLUSIONS
`We have shown that at the cost of an arbitrarily small error rate it is
`possible to "whiten" to any degree all the first- and second-order
`statistics of any binary digital source. This relaxes the restriction
`frequently found in the literature in which the digital source is assumed
`a priori to produce only independent equiprobable symbols. The key
`equation in our result [ eq. (15)] is useful when designing a standard
`self-synchronizing scrambler for a given application.
`We leave unsolved the problem of whether universal scramblers exist
`for the M-ary source.
`
`VIII. ACKNOWLEDGMENTS
`I wish to thank M. B. Romeiser for editorial suggestions and Miss
`J . M . Michel for assistance in computer programming. I also had the
`benefit of stimulating discussions on the subject of scrambling with
`T. M. Chien and R. J. Deaton.
`
`APPENDIX
`Proof of Lemma 1 •
`For convenience, we assume that in Fig. 2a the scrambler initially
`contains all zeros. Since each scrambler output bit is ultimately a
`mod-2 summation of selected input bits, we may 'vrite
`
`n
`b,. = ~ hkan-k1
`k - 0
`
`(19)
`
`where the binary sequence hk performs the selection. We note that if
`a0 = 1 and a ; = 0 for all i > 0, then lb,.) = lh,.). But under these
`
`• Independently or the author, U. Henriksson has developed• a proof of a similar
`lemma.
`
`

`

`1864
`
`THE BELL SYSTEM TECHNICAL JOURNAL, DECEMBER 1973
`
`conditions, as described in Section II, {b,.j will be a maximal length
`sequence. Hence, { h,. I must itself be a maximal length sequence.
`Now we consider the two output bits b,. and bm. We wish to count
`the number of "a" bits which entered the summation for b.,. but not
`b,.. We have
`
`Since m > n,
`
`(a)
`
`(b)
`
`m - n - 1
`
`m
`!; hkam-k G1 E hkam-k
`k-0
`k-m-n
`
`m.- n- 1
`
`n
`
`E hkam-1: G1 E hm-n+A;an- k
`k - 0
`k-0
`
`(20)
`
`(21)
`
`Examination of the subscript range shows that all the "a" bits
`selected by the first summation in eq. (21) are unique to b .... By com(cid:173)
`paring the second summation with eq. (20a) we see that the additional
`"a" bits which enter b ... but not bn are those for which
`hm- n+k - hm-n+khk = 1.
`
`Hence,
`
`J mn
`
`or
`
`L hk + L [hm-n+k - hm- n+khk],
`
`m-n-1
`
`k - 0
`
`n
`
`k- 0
`
`Jmn
`
`m-n-1
`
`L
`k- o
`
`n
`
`hk + L hm-n+k - L hm- n+khk,
`k- o
`k-o
`
`n
`
`(22)
`
`where addition is now in the usual sense.
`We examine this expression in detail, recalling that the sequence
`{hkl has period p = (2M- 1) and the given condition n > 2M+1.
`Case (1): If m - n = Kp, K = 1, 2, · · · , then
`
`for all values of k. Hence the second and third summations cancel. But
`then the first summation contains K periods of a maximal length
`sequence. Since each period contains exactly 2<M- Jl ones, 8 the first
`summation totals at least 2<M-o.
`Case (2): If m - n ~ Kp, then it is easily shown6 that the sequence
`formed by the term-by-term product hm- n+khk has period p and con-
`
`

`

`A UNIVERSAL DIGITAL DATA SCRAMBLER
`
`1865
`
`tains 2<M-2 > ones per period. The sequence lhm-n+kl contains 2<Af-Jl
`ones per period. Hence the net contribution of the second and third
`summations is 2<M- 2> ones per period. Since n > 2Af+J > 2p, the
`summations cover at least two periods. Thus their net total is at least
`2<M-I).
`Thus for either case,
`
`Jo
`
`ffiln [J mn] =2M-I.
`m,n >2.M+l
`
`REFERENCES
`
`1. Savagel... J. E., "Some Simple Self-Synchronizing Digital Data Scramblers,"
`B.S.T.J., 45, No. 2 (February 1967), pp. 449-487.
`2. Gallager, R. G., Information Theory and Reliable Communication, New York:
`John Wiley and Sons, 1968, pp. 225- 238.
`3. Peterson, W. W., Error Correcting Codes, Cambridge: M.I.T. Press, 1961, pp.
`251-270.
`4. Fracassi, R. D., and Tammaru, T., "Megabit Data Service with the 306A Data
`Set," Bell Laboratories Record, 49, No. 10 (November 1971), pp. 310-315.
`5. Henriksson, U., "On a Scrambling Property of Feedback Shift Registers," IEEE
`Trans. on Commun., 130, No. 5 (October 1972), pp. 998- 1001.
`6. Golomb, S. W., Shift Register Sequences, San Francisco: Holden-Day, 1967, pp.
`23- 59, 88.
`
`