CORRBPONDENCE
`
`531
`
`.
`“"‘v"
`Furthermore, by using
`
`( Ik—a+ 13+.»
`1 + 1., + 1,",
`
`kin
`k=n
`
`2 N
`2
`N
`k=l
`k=I
`]_—[cosq,.u21—u2q,,"'
`
`the PE expression given by (26) is approximated by
`
`P, 2
`
`{I — -F)
`
`_.,,
`
`(sin quads) (1 — #2 E qt”)
`
`lrzl
`
`been described by Frank and Zadoll [l] and Heimiller [2]. The
`lengths of such codes are restricted to perfect squares. It will be
`shown that codes with the same correlation properties can be
`constructed for any code length. The method is borrowed from
`the work of Schroeder [3] in connection with synthesis of low
`peak-factor signals.
`Consider a. code {a,,} of length N composed of unity modulus
`complex numbers. i.e.,
`
`at = exp risk,
`
`k = 0,1,---,N -1.
`
`(1)
`
`The autocorrelation function {xJ} is defined as follows:
`
`-exp (—a2a‘f2) do/rt},i2
`are (me) + (2a)-“=<q..ra“) exp (rio‘.’2a2) Q: 91:2
`N
`
`‘
`
`nr—1
`0
`xu - *3 aka,,
`N—J—l
`
`J\'—1
`
`xi
`
`k=D
`2 akaffl; +
`
`k
`
`=~—r
`
`3
`akak+j—N:
`
`c
`J = . 9"
`
`-,N— 1.
`
`(3)
`
`(37)
`erfc (ua) + (2n)‘”2a exp (-112.53) 1;‘ 9,3.
`Thus, (37) gives the approximate minimum average probability
`of error and (36) gives the approximate solution of (25) explicitly
`i.n terms of the known t',._,,, k = -—N,---,N,
`r: = —N,---,N.
`Finally, we observe that the technique used in this correspon-
`dence for the analysis of intersymbol interference in a binary
`low-pass pulse-communication system is also readily applicable
`to a binary or a quadriphase bandpass phase-shift-keyed (PSK)
`communication system.
`
`It is claimed that for any code length N, the phases at can be
`chosen such that for j = 1,2,- - -, N — 1, x, vanishes. The single
`maximum of magnitude N occurs at xo.
`Consider first the case that N is even. We claim that if
`
`a — exp 1' Mm;
`It
`N s
`
`where M is an integer relatively prime to N, then
`
`ACKNOWLEDGMENT
`The author wishes to thank Dr. L. Milstein and Prof. J.
`Omura for various helpful discussions on this correspondence.
`
`From (3)
`
`x,=0,
`
`j: l,2,~--,N— 1.
`
`REFERENCES
`[1] R. W. Lucky, J. Salz, and E. J. Weldon, Jr., Principles of Dara Com-
`mum'catr'an— New York: McGra.w-Hill, I968.
`[2] B. R. Saltzbcrg, “lntersymbol interference error bounds with applica-
`tion to ideal bendlimited signaling." IEEE Trans. Inform. Theory. vol.
`lT—14. pp. 563-568. July 1963.
`[3] R. Lugannani, "lntersymbol interference and probability of error in
`digital systems," IEEE Trans. Inform. Theory. vol. IT-15, pp. 682-688,
`Nov. 1969.
`[4] M. R. Aaron and D. W. Tufts, "Intersymbol interference and error
`an.
`.
`roba]l;i‘l2:y," IEEE Trans.
`Inform. Theory, vol.
`IT-I2, pp. 26—34.
`[5] E. Y Ho and Y. 5. Yeh, "A new approach for evaluating the error
`probability in the presence of intersymbol interference and additive
`Gaussian noise." Bel‘! Sysr. Tech. J., vol. 49, pp. 2249-2265, Nov. 1970.
`[6] 0. Shimbo and M. Celebiler. “The probability of error due to inter-
`symbol
`interference and Gaussian noise in digital communication
`s stems," IEEE Trans. Cammrm. TechnaL, vol. COM-I9, pp. ll3-119,
`pr. 1971.
`I
`fi._l]lErd§‘l?ri, Tables ofIntegral Transforms, vol. 1. New York; McGraw-
`
`[7]
`
`M
`N—l
`l'\|'—J—1
`Ag: 2 expi&[k‘ — (!c+j)2]+ E exp1'——E
`K=0
`:¢=N~J
`N
`N
`
`-[:8 — (k +j— NP],
`
`1': 1,2,---,N— 1.
`
`(5)
`
`Note that
`
`exp1'%‘(k +_,r' ~ N)’
`
`exp i% (k + D2 exp —i21tM(k + 1') exp EIINM
`Mn
`exp £17 (I: + 1')’,
`
`N even.
`
`The two summations of (5) may be combined.
`N-1
`x, = 2 exp r@ [:52 — (k + n2]
`ts=o
`N
`
`Polyphase Codes With Good Periodic Correlation Propertiw
`DAVID C. CHU
`
`"*1
`
`Mn
`.T _2k._ .1
`exp! N l
`J
`J]
`
`Ab.-:rmc!—'l‘l|is correspondence describes the construction of complex
`coda cl’ the form exp for. whose discrete circular nutocorrelatinns are
`zero for all nonzero lags. There is no restriction on code lengths.
`
`=exp—j
`
`Mnjz Nilk=o
`N
`
`_2::M;‘ "
`exp—r—T ,
`N
`
`j=l,2,---,N—l
`
`:0.
`
`Polyphase codes with a periodic autocorrelation function that
`is zero everywhere except at a single maximum per period have
`
`Manuscript received January 3]. 1932.
`The author is with the Hewlett-Packard Company, Santa Clara, Calif.
`95050.
`
`The last step comes from the fact that since M and N are
`relatively prime, then exp —t'(2nM}'N) is a primitive Nth root
`of unity. Therefore, exp —r'(21rMj/N) is an Nth root of unity but
`not equal to 1 for the range ofj shown in (6). Finally, we employ
`the theorem
`
`ZTE Corporation and ZTE (USA) Inc.
`Exhibit 1004-0001
`
`BlackBerry Exhibit 1007, pg. 1
`
`

`
`N—l
`
`kg% rk = 0,
`where r is an Nth root of unity and r aé 1.
`Consider next the case of N odd. We claim that if
`
`H 2 exp iiiinktic +1)
`I!
`N
`
`r
`
`where M is relatively prime to N, then
`
`j 21,2,---,N— 1.
`x, : 0,
`Substituting (7) into (3), we have
`N—.l'—l
`
`EXDf%[k(k+ l)—(k+j)(k+_i'+ 1)]
`“J: Ek=O
`H-1
`+ 2 cxp:E’t[ku.».+1)—(k+;'— N)
`ic=N—J'
`N
`
`-(k+,i'+1—N)].
`
`With some manipulation, one can show that for odd N,
`
`expi£;§[(k+j—N)(k+j+i—N)]
`
`= exp 9;" [Ur + ark + 1 +13]
`and the two summations in (8) can be combined into one:
`N—1
`. Mir
`exp 1
`
`[ktk +1)—(k + ;')(k +;'+1}]
`
`351:2k=O
`
`(9)
`
`A4
`N—l
`2 exp fl [-2176 F I2 - 1']
`k=o
`N
`N—l
`
`exp W-3% [f(__;' + I)]k;o [exp —i. 22r.ll/13]"N
`
`: 0,
`
`j : l,- - -, N — 1 and Mrelatively prime to N.
`
`Thus a code of any length N may be phase coded by either (4)
`or (T), respectively, depending on whether N is even or odd, and
`the resulting code will have the desired correlation properties.
`Trivial variations such as cyclic shifts, addition of a constant to
`at,“ or conjugating the entire code obviously will not aliect the
`autocorrelation function analogously to the aperiodic case [4].
`In addition, certain linear phase shifts of the form exp i'(2nql:,'N),
`where q is any integer, when introduced into the code also will
`not alfect the correlation. To show this, let the modified sequence
`be {bk} where
`
`i'2irq
`bk 2 an exp —— .
`N
`
`Substituting (7,, for L1,, in (3)
`
`IEEE TRANSACTIONS ON INFORMATION THEORY, JULY 1972
`
`REFERENCES
`
`[I] R. L. Frank and S. A. Za_dofi', “Phase shifl pulse codes with good
`periodic correlation properties," IRE Trans. Inform. Theory (Corresp.),
`vol. lT—B, pp. 381-382, Oct. I962.
`_
`_
`_
`[2] R. C. Heimillcr, "Phase shift codes with good periodic correlation
`figgrliertles." IRE Trans. hifarin. Theory. vol. IT-7, pp. 254-257, Oct.
`[3] M. R. Schroeder. “Synthesis o!'_low-peak-factor signals and binary
`sequences with low autocorrelation," IEEE Trans.
`inform. Theory
`tCorresp.), vol.
`lT—l6, pp. 85-89. Jan. 1970.
`[4] S. W. Golomb and R. A. Scholtz. "Generalized Barker sequences."
`IEEE Trans. Inform. Theory. Vol. IT-ll. P13. 533-537, Oct. 1965.
`
`A Stochastic Model for Burst-Correcting Convolutional
`Decoders
`
`PHILIPPE PIRET
`
`Ab.i-mm—A stochastic model is described for the decoder of an optimal
`burst-correcting comrolutional code. From tltis model, an upper bound is
`obtained for 13, the error probability per word after decoding.
`
`INTRODUCTION
`
`[6], use stochastic models to analyze
`[5],
`Recent papers
`decoders. We use here similar methods to upperbound the error
`probability after decoding of an optimal binary burst-error-
`correcting convolutional code.
`A burst of r consecutive words followed by a guard space G
`of r-(ii + k)f(.-2 e 12) correct words [1] is always correctable by
`an optimal type-B2 code. Optimal codes for this bound are well
`known [2], [3] and the practical construction of a type-B2 code
`for arbitrary r requires only the construction of a type-B; code
`with r = 1. This last code is called basic, and codes with r > I
`are Obtained by interlacing.
`A basic code can be defined as the set of all binary Semi-
`infinite sequences orthogonal
`to the matrix A constructed by
`indefinitely displacing the binary matrix B by (it — k) rows lower
`at each time (Fig. I).
`The matrix B defining a code can be divided into X sub-
`matrices 3,:
`
`3 =
`
`Bu
`Bl‘
`BK—1
`
`where each B, has (11 — k) rows.
`We shall consider systematic codes such that the last (rt — k)
`columns of B0 form an identity matrix, and for 1'
`;-E 0 the last
`(it —- k) colurrins of B; are zero. We also restrict our study to
`nonsingular codes, i.e., codes defined by a matrix B whose first
`iri rows form a nonsingular matrix. This family includes the
`Berle]-:amp—Preparala codes as a subclass
`[2],
`Optimal
`codes can be constructed if (it
`-— k) is a factor of (rt + k). We
`suppose that (H — k) and ii are relatively prime. Otherwise a
`shorter code exists, with the same rate and correcting capability
`and no larger guard space G [7]. The only possible values of
`(H — k) are thus 1 and 2 for it odd and l for M‘ even.
`Let x be a received semi-infinite sequence of the code repre-
`sented as a column vector; then Ax is the syndrome sequence.
`Each word of x can be decoded by looking at N elements of
`Ax [4], where N, the number of rows" of the matrix B, is given
`
`Manuscript received September 3, I970; revised December 16, 1971.
`The author is with the MBLE Research Laboratory, Brussels, Belgium.
`
`ZTE Corporation and ZTE (USA) Inc.
`Exhibit 1004-0002
`
`(10)
`
`(11)
`
`3
`‘Txflii+.r—N
`
`J
`
`N—}—1
`x_,— k:
`
`U N
`
`2
`akafuexpi ;q(k—k—j)
`-1
`2
`aRaf+_._”expii¥(k—k—j+ N)
`N-J
`N
`-—J—1
`iv
`1
`2 akal:+.l+ _g7
`=0
`I:
`j=l,2,---,N—l
`
`+
`
`=0,
`
`as the quantity inside the parentheses vanishes.
`
`BlackBerry Exhibit 1007, pg. 2