`
`531
`
`.
`
`k’" =
`
`lk—n + lk+ns
`1+ lo + 12,,
`
`Furthermore, by using
`N
`
`k9’=rz
`k = n
`
`N
`
`k=l
`k=l
`n cos’ qku 21- u2 2 11,,’
`
`the P9 expression given by (26) is approximated by
`no
`N
`
`PE:
`
`{I — I
`
`_ ,0
`
`(sin qou/u) (1 —- u2 2 qkz)
`
`k= 1
`
`The
`been described by Frank and Zadoff [1] and Heimiller
`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 {ak} of length N composed of unity modulus
`complex numbers, i.e.,
`
`ok = exp iack,
`
`k = 0,1,---,N — 1.
`
`(1)
`
`The autocorrelation function {xi} is defined as follows:
`
`-exp (—a2u2/2) du/7:}/2
`erfc (qo/U) + (27l)_1/2010/°'3)eXP(1102/202)kfi1 qr.’
`N
`
`xo
`
`X1
`
`*
`
`N—1
`k=o
`2 aka):
`N—J—1
`
`*
`*
`k=0
`k=N-J‘
`2 akak+j + Z akak-f-J'—Ny
`
`N—1
`
`(37)
`erfc (1/a) + (2rt)‘”2a exp (— 1/2:12) I‘; e,3.
`Thus, (37) gives the approximate minimum average probability
`of error and (36) gives the approximate solution of (25) explicitly
`in terms of the known I,,',,, k = —N,---,N, n = —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 azk 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
`
`ak = exp iMnk2,N
`
`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,
`
`j=1,2,---,N—1.
`
`REFERENCES
`[1] R. W. Lucky, J. Salz, and E. J. Weldon, Jr., Principles of Data Com-
`munication. New York: McGraw-Hill, 1968.
`[2] B. R. Saltzberg, “lntersymbol interference error bounds with applica-
`tion to ideal bandlimited signaling,” IEEE Trans. Inform. Theory, vol.
`IT-14, pp. 563-568, July 1968.
`[3] R. Lugannani, “Intersymbol interference and probability of error in
`ov.
`.
`gggitallgyésgtems,” IEEE Trans. Inform. Theory, vol. 1T-15, pp. 682-688,
`[4] M. R. Aaron and D. W. Tufts, "Intersymbol interference and error
`an.
`.
`proba1.3i6li6ty," IEEE Trans.
`Inform. Theory. vol.
`IT—12, pp. 26-34,
`[5] E. Y Ho and Y. S. Yeh, “A new approach for evaluating the error
`probability in the presence of intersymbol interference and additive
`Gaussian noise," Bell Syst. 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
`systems,” IEEE Trans. Commun. TechnoI., vol. COM-19, pp. 113-119,
`Apr. 1971.
`7] A. Erdelyi, Tables of Integral Transforms, vol. 1. New York: McGraw-
`Hill, 1954.
`
`Note that
`
`M7:
`‘~k+'—N2
`exp:N(
`J
`)
`
`exp 1'? (k + 1)’ exp —i27rM(k + j) exp inNM
`M7:
`'——k+'2, Nee.
`expzN(
`])
`vn
`
`The two summations of (5) may be combined.
`N—l
`
`X1‘:k=o
`
`M7:
`;
`explNl
`
`.2
`( +1)]
`
`Polyphase Codes With Good Periodic Correlation Properties
`DAVID C. CHU
`
`Abstruct—This correspondence describes the construction of complex
`codes of the form exp ia,, whose discrete circular autocorrelations are
`zero for all nonzero lags. There is no restriction on code lengths.
`
`Polyphase codes with a periodic autocorrelation function that
`is zero everywhere except at a single maximum per period have
`
`Manuscript received January 31, 1972.
`The author is with the Hewlett-Packard Company, Santa Clara, Calif.
`95050.
`
`M7:
`""1
`.% _2k._ .2
`I‘; expt N [
`J
`1]
`
`—
`
`_Mnj2 "-1
`1 N k§0[
`
`,27rMj
`exp—z
`N
`
`e
`
`xp
`= 0.
`
`K
`].
`
`;=1,2.~-.N—1
`(6)
`
`The last step comes from the fact that since M and N are
`relatively prime, then exp —i(27zM/N) is a primitive Nth root
`of unity. Therefore, exp — z'(27rMj/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/SAMSUNG/HTC 1020-0001
`
`
`
`N—1
`
`where r is an Nth root of unity and r ¢ 1.
`Consider next the case of N odd. We claim that if
`
`.M7tk(k + 1)
`ak = exp:
`— ——— ——,
`N
`
`where M is relatively prime to N, then
`
`x, = 0,
`
`j=1,2,~--,N—— 1.
`
`Substituting (7) into (3), we have
`N—J—1
`x, = Z expiw [k(k + 1) — (k +j)(k +j+1)]
`k=o
`N
`N—1
`+ 2 expi']—V{n[k(k+1)—(k+j— N)
`k=N—.i
`N
`
`-(k+j+1—N)].
`
`With some manipulation, one can show that for odd N,
`
`expz%’3 [(k+j— N)(k+j+ 1- N)]
`
`=up¥%%w+nm+j+1n<m
`and the two summations in (8) can be combined into one:
`N—l
`xj=E exp i-543 [k(k + 1) — (k + j)(k +1 + 1)]
`k=0
`N
`N—1
`
`2 exp 1/51-21k — 12 — J]
`k=0
`N
`N~1
`exp —iA/J1 lJ'(j + 1)] 2 [exp —i
`N
`k=0
`= 0,
`j = 1,- ~ -, N — 1 and M relatively prime to N.
`
`277:Mj k
`N
`
`Thus a code of any length N may be phase coded by either (4)
`or (7), 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
`ak, or conjugating the entire code obviously will not affect the
`autocorrelation function analogously to the aperiodic case [4].
`In addition, certain linear phase shifts of the form exp i (27rqk/N),
`where q is any integer, when introduced into the code also will
`not affect the correlation. To show this, let the modified sequence
`be {bk} where
`
`bk = ak exp Hi .N
`Substituting bk for ak in (3)
`
`x,
`
`*
`N~j—1
`2”w—k—n
`k =0
`Z akakfiexpz N
`N—1
`k=N-J
`
`2
`aka,’,"+J-_N exp [~Lq(k — k — j + N)
`N
`
`+
`
`.2mU- N—,];—1
`aka,f+,- +
`exp —I~17
`kgdo
`J‘: 1,2,...,N_1
`
`= 0,
`
`1v—1
`k=N-—.I
`
`as
`akak+J'-N
`
`as the quantity inside the parentheses vanishes.
`
`(10)
`
`(11)
`
`IEEE TRANSACTIONS ON INFORMATION THEORY, JULY 1972
`
`REFERENCES
`[I] R. L. Frank and S. A. Zadolf, “Phase shift pulse codes with good
`periodic correlation properties," IRE Trans. Inform. Theory (Corresp.),
`vol. IT-8, pp. 381-382, Oct. 1962.
`_
`.
`_
`[2] R. C. Heimiller, “Phase shift codes with good periodic correlation
`1 61.
`pgoperties,” IRE Trans. Inform. Theory, vol.
`lT—7, pp. 254—257, Oct.
`[3] M. R. Schroeder, “Synthesis of low-peak-factor signals and binary
`sequences with low autocorrelation,” IEEE Trans.
`Inform. Theory
`(Corresp.), vol. IT-16, pp. 85-89, Jan. 1970.
`[4] S. W. Golomb and R. A. Scholtz, “Generalized Barker sequences,"
`IEEE Trans. Inform. Theory, vol. IT-ll, pp. 533-537, Oct. 1965.
`
`A Stochastic Model for Burst-Correcting Convolutional
`Decoders
`
`PHILIPPE PIRET
`
`Abstract——A stochastic model is described for the decoder of an optimal
`burst-correcting convolutional code. From this model, an upper bound is
`obtained for p, 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(n + k)/(n — k) 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-B2 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 (n — k) rows lower
`at each time (Fig. 1).
`The matrix B defining a code can be divided into K sub-
`matrices B,:
`
`where each B, has (n — k) rows.
`We shall consider systematic codes such that the last (n — k)
`columns of B0 form an identity matrix, and for i ;é 0 the last
`(n —- k) columns of B, are zero. We also restrict our study to
`nonsingular codes, i.e., codes defined by a matrix B whose first
`11 rows form a nonsingular matrix. This family includes the
`Berlekamp~Preparata codes as a subclass
`[2],
`[3]. Optimal
`codes can be constructed if (n — k) is a factor of (n + k). We
`suppose that (n — k) and n 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
`(n — k) are thus 1 and 2 for it odd and 1 for n 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, 1970; revised December 16, 1971.
`The author is with the MBLE Research Laboratory, Brussels, Belgium.
`
`ZTE/SAMSUNG/HTC 1020-0002