CORRESPONDENCE
`
`531
`
`£7“ = {lk—n + lk-l-m
`
`1 + lo + l2,,,
`
`'
`
`Furthermore, by using
`N
`
`k 9* '1
`
`k = n
`
`N
`
`H cos’ qku _~_1— a2 Z qkz
`k=1
`k=l
`
`the Pe expression given by (26) is approximated by
`
`Pg:
`
`{I — JW (sin qou/u) (1 —~ a2 ‘El qkz)
`- exp (—a2u2/2) du/7:}/2
`ll erfc (qo/0) + (2n)‘“’(qo/03) exp (‘I02/202) :1 qt”
`2 erfc (1/a) + (21r)'“2a exp (— 1/2a2) IE1 e,,2.
`(37)
`
`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.
`
`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.,
`
`ak = exp iack,
`
`k = 0,1,---,N -1.
`
`(1)
`
`The autocorrelation function {xj} is defined as follows:
`zv—1
`
`X0 = 2 akak*
`k=0
`N—j—1
`
`1v—1
`
`x, = Z aka,’:+J + Z a,,a,’,"+,~_N,
`k=0
`k=N-J
`
`(2)
`
`j = 1,2,-~-, N— 1.
`(3)
`
`It is claimed that for any code length N, the phases a,, can be
`chosen such that for j = 1,2,- - -, N — 1, xj vanishes. The single
`maximum of magnitude N occurs at xo.
`Consider first the case that N is even. We claim that if
`
`.Mk2
`a,.=expz
`1’;
`
`,
`
`(4)
`
`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,=o,
`
`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.
`.
`1digital1;}és9tems,” IEEE Trans. Inform. Theory, vol. IT-15, pp. 682-688,
`[4] M. R. Aaron and D. W. Tufts, “Intersymbol interference and error
`an.
`.
`],3rob:i.l;i6li6ty,” 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] O. 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.
`
`Polyphase Codes With Good Periodic Correlation Properties
`DAVID C. CHU
`
`Abstract—This correspondence describes the construction of complex
`codes of the form exp ion, 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.
`
`N—J-1
`x, = kgo
`
`.A4n
`I
`N:1_expiAl—n
`exp :7 [k2 — (k + 1)2] + k=N_J
`N
`
`-[k2 —(k+;'— M2].
`
`;'= 1,2,---,N— 1.
`
`(5)
`
`Note that
`
`Mn
`‘~k+'—N’
`expzN(
`J
`)
`
`ll
`
`exp i% (k + j)’ exp —i27rM(k + j) exp i7zNM
`.M7r
`»—k+'2, Nee.
`exptN(
`1)
`vn
`
`The two summations of (5) may be combined.
`
`N—l
`Al
`x.- = A exp if [k2 — (k +132]
`
`=
`
`"T1
`M1:
`.g4A _2k._ Q
`kgoexpt N[
`1
`1]
`-2N—1
`
`-k
`
`= exp—iM,f,’ H [exp —tL1’f’] ,
`
`;=1,2,---,N—1
`
`= 0.
`
`(6)
`
`The last step comes from the fact that since M and N are
`relatively prime, then exp —i(27rM/N) is a primitive Nth root
`of unity. Therefore, exp — i(27rMj/N) is an Nth root of unity but
`not equal to 1 for the range of j shown in (6). Finally, we employ
`the theorem
`
`1
`
`APPLE 1004
`
`1
`
`APPLE 1004
`
`

`
`532
`
`N—1
`
`where r is an Nth root of unity and r 95 1.
`Consider next the case of N odd. We claim that if
`
`a = exp l.M7rk(k + 1)
`k
`[V
`
`9
`
`(7)
`
`where M is relatively prime to N, then
`
`x,=O,
`
`j=l,2,---,N-l.
`
`Substituting (7) into (3), we have
`
`x, = N’:i:1exp1'¥V7-t[k(k + 1) - (k + j)(k + j +1)]
`
`1v—1
`+ 2 expiM[k(k+1)—(k+j—N)
`k=N-J"
`N
`
`-(k+j+1—N)].
`
`With some manipulation, one can show that for odd N,
`
`expigf-[7E[(k+j-N)(k+j+l—N)]
`
`IEEE TRANSACTIONS ON INFORMATION THEORY, JULY 1972
`
`REFERENCES
`
`[1] R. L. Frank and S. A. Zadoff, “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)g(6>1l)erties,” IRE Trans. Inform. Theory, vol. IT-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
`
`(8)
`
`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 13, the error probability per word after decoding.
`
`INTRODUCTION
`
`= exp i? we + i)(k + 1 +1)1 (9)
`
`and the two summations in (8) can be combined into one:
`
`N——1
`M»
`x, = k:j0 exp pf [k(k + 1) — (k + j)(k +1‘ +1)]
`N-1
`M
`= Z expiil-2jk—j2—i]
`k=0
`N
`
`,M ,
`
`,
`
`"-1
`
`= exp -17; [](] + 1)] kg‘) [exp -1 ”NJ]
`
`.2 M‘ "
`
`= 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 (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
`rxk, 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 1' (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
`
`i27zq
`bk = ak exp T .
`
`(10)
`
`Substituting bk for a,, in (3)
`
`2
`N—j—1
`x, = 2 a,,a,’f+,~exp iflI(k - k —j)
`k=O
`N
`N—1
`
`+
`
`k==N-J
`
`aka,}*+j_Nexpi—2lq(k—k—j+ N)
`N
`
`= exp -1-7fl1( 2 a,,a,’f+,- + Z a,,a,f+J-_N)
`
`-2
`
`- N—j—l
`k=0
`
`N
`
`N—1
`k=N-J'
`
`[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 > 1
`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. l).
`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 1‘ 96 0 the last
`(11 - k) columns of B, are zero. We also restrict our study to
`nonsingular codes, i.e., codes defined by a matrix B whose first
`n 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
`(rt - k) are thus 1 and 2 for n odd and 1 for It 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
`
`=0,
`
`j=1,2,---,N-1
`
`(11)
`
`as the quantity inside the parentheses vanishes.
`
`Manuscript received September 3, 1970; revised December 16, 1971.
`The author is with the MBLE Research Laboratory, Brussels, Belgium.
`
`2