CORRESPONDENCE
`
`531
`
`been described by Frank and Zadoff [1] 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 {ad of length N composed of unity modulus
`complex numbers, i.e.,
`
`4aA
`
`、‘，，，
`
`/，‘、
`
`(2)
`
`ak = exp 11Xk,
`
`k = 0， 1 ，… ， N 一1.
`
`The autocorrelation function {x j} is defined as follows:
`
`N-1
`
`Xo = L akak*
`
`巨三云。
`
`Xj = L akat+ j + L akat+j-N,
`
`N-J-1
`
`k三云 o
`
`N-l
`
`k=-N-j
`
`j = 1,2,… , N - 1.
`(3)
`
`It is claimed that for any code length N, the phases IXk can be
`chosen such that for j = 1,2,… , N - 1, Xj vanishes. The single
`maximum of magnitud巳 N occurs at XO.
`Consider first the case that N is even. We claim that if
`
`.Mπk 2
`ak = exp 1 一了'
`
`wher巳 M is an integer relatively prime to N , then
`
`Xj = 0,
`
`j = 1,2,… , N - 1.
`
`From (3)
`
`(4)
`
`(5)
`
`gk,n =
`
`{也-n+lk+m
`\1 + 10 + 12m
`Furthermore, by using
`N
`
`k 手t. n
`k = n.
`
`N
`
`n cos2 qku ~ 1 - u2 L qk2
`
`k= 1
`k= 1
`the Pe expression given by (26) is approximated by
`们 {1 一汇。川
`
`~ erfc (qo/σ) + (2π)-1!2(qO/σ3) exp (q02/2σ 2) L q/
`
`N
`
`k=l
`~ erfc (1 /a) + (2π)-1!2a 巳xp (-IJ2a2) L e/.
`
`N
`
`(37)
`
`Thus, (37) gives the approximate minimum average probability
`ofeηor and (36) gives the approximate solution of (25) explicitly
`in terms of the known Ik.m k = - N ,… ,N , n = -N,… ,N.
`Finally, we observe that the technique used in this correspon(cid:173)
`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)
`com口lUnication system.
`
`ACKNOWLEDGMENT
`The author wishes to thank Dr. L. Milstein and Prof. J.
`Omura for various helpful discussions on this correspondence.
`
`REFERENCES
`[1] R. W. Lucky, J. Salz, and E. J. Weldon, J乱 ， Principles of Data Com(cid:173)
`munication. New York: McGraw-HilI, 1968.
`[2] B. R. Saltzberg, "Intersymbol interference error bounds with appIica(cid:173)
`tion to ideal bandIimited signaIing," lEEE Trans. lnform. Theory, vol.
`IT-14, pp. 563-568, July 1968.
`[3] R. Lugannani, "Intersymbol interference and probability of error in
`digital systems," lEEE Trans. lnform. Theory, vol. IT-15, pp. 682-688,
`Nov.1969.
`[4] M. R. Aaron and D. W. Tufts, "Intersymbol interference and error
`probabiIity," lEEE Trans. lnform. Theory, vol. IT胃口， pp. 26-34,
`Jan. 1966.
`[5] E. Y Ho and Y. S. Yeh, "A new approach for evaluating the error
`probabiIity in the presence of intersyinbol interference arid additive
`Gaussian noise," Be/l Syst. Tech. J. , vol. 49, pp. 2249-2265, Nov. 1970.
`[6] O. Shimbo and M. Celebiler,‘'The probabilfty of error due to inter(cid:173)
`symbol interference and Gaussian noise in digital communication
`systems," lEEE Trans. Commun. Technol. , vol. COM-19, pp. 113-119,
`Apr. 1971.
`[7] A: Erdelyi, Tables of lntegral Transforms. vol. 1. New York: McGraw(cid:173)
`HiII, 1954.
`
`Polyphase Codes With Good Periodic Correlation Properties
`
`DAVID C. CHU
`
`Abstract-This correspondence describes the construction of complex
`codes of the form exp 问 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, CaIif.
`95050.
`
`N 手 :-1
`
`.Mn r.?
`
`"
`
`,,?,
`
`k=口
`
`N
`
`N~l
`k=N-j
`
`.Mπ
`
`JV
`
`句= t -exp i 1~~ [k2 一 (k + j)2] + L exp i 丁
`.W 一 (k + j - N)汀，
`
`j = 1,2,… , N - 1.
`
`Note that
`
`白p i 譬 (k + j - N)2
`
`= exp i 譬 (k + 川 exp - i2nM(k + j) exp iπNM
`
`= exp i 孚 (k +N,
`
`Neven.
`
`The two summations of (5) may be combined.
`Xj = L exp i 弓子 [k 2 -
`
`N-l
`
`k=O
`
`觅..-
`
`1~
`
`(k + NJ
`
`N-l
`
`= L exp i 弓子[ -2kj 一 j2]
`k=O
`
`觅..-
`
`lV
`
`= exp 一 ifXImp-i 半r
`= O.
`
`j =
`
`1 ， 2 ，… ， N 一 1
`
`(6)
`
`The last step comes from the fact that since M and N are
`relatively prime, then exp - i(2πMJN) is a primitive Nth root
`of unity. Therefore, exp 一 i(2nA要ï/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
`
`ZTE/SAMSUNG 1004-0001
`
`APPLE 1004
`
`1
`
`

`

`532
`
`IEEE 四ANSACTIONS ON INFORMATION THEORY, JULY 1972
`
`N-l L r k = 0,
`
`where r is an Nth root of unity and r -:j. 1.
`Consider next the case of N odd. We c1aim that if
`
`k = exp i ~fπk(k + 1) ,
`N
`
`(7)
`
`where 凡1 is relatively prime to N , then
`
`Xj = 0,
`
`j =
`
`1 ，2，… ， N 一1.
`
`REFERENCES
`[1] R. L. Frank and S. A. Zadoff, "Phase shift _pulse codes with good
`periodic correlation properties,"lRE Trans. lnform. Theory (Corresp.),
`~ol. _!T-_8_, pp:}81-.3~?， Oct..1?62.
`[2] R. C. Heiffiiller, "Phase shift codes with gooj _period!c_ .co_r!~la!i on
`properties," lRE Trans. lnform. Theory , vo l.町-7 ， pp. 254-257, Oct.
`1961.
`[3] M. R. Schroeder, "Synthesis of low-peak-factor signals and binary
`sequences with low autocorrelation,"- lEEE Trans. lnform. Theory
`(Còrresp.), vol. IT-16, pp. 85-89, Jan. 1970.
`[4] S. W. Golomb and R. A. Scholtz, "Generalized Barker sequences,"
`lEEE Trans. lnform. Theory, vol. IT-II , pp. 533-537, Oct. 1965.
`
`Substituting (7) into (衍， we have
`'Æ_
`Xj = L exp i 弓子 [k(k + 1) 一 (k + j)(k 十 j + 1)]
`
`k=O
`
`lV
`
`N-j-l
`
`N-l
`
`施，
`
`+ L exp i .'."::' [k(k + 1) 一 (k + j - N)
`
`lV
`
`k=N-j
`(k + j 十 1 - N)].
`With some manipulation, one can show that for odd N ,
`
`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 fi, the error probability per word after decoding.
`
`INTRODUCTION
`Rec巳nt papers [5], [6], use stochastic models to analyze
`decoders. We use here similar methods to upperbound the error
`probability after decoding of an optimal binary burst-error(cid:173)
`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(cid:173)
`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(cid:173)
`matrices B 1:
`
`BB.--Bi
`
`nu'AV-O
`
`-
`
`1It--ti--t」
`
`「EEEE'-BEt-tL
`
`一一
`
`B
`
`wher巳 each BI has (n - k) rows.
`We shall consider systematic codes such that the last (n - k)
`columns of Bo form an identity matrix, and for i -:j. 0 the last
`(n - k) columns of BI 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
`(n - k) are thus 1 and 2 for n odd and 1 for n even.
`Let X be a receiv巳d semi-infinite sequence of the code repre(cid:173)
`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.
`
`exp i 字 [(k + j - N如 j + 1 一 N)]
`
`zw?[(k+j)(k+j+ 川 (9)
`
`and the two summations in (8) can be combined into one:
`
`N 一 1
`酒'一
`Xj = L 叫 iT;? 如(k + 1) 一 (k + j)(k + j + 1)]
`k=O
`lV
`
`N-l
`觅，
`=艺 exp i 土;- [-2jk _ j2 一 j]
`k=O
`1'1
`
`=exp-if孚[j(j + 1)] L I exp - i 丁:.1j I
`
`N 一 1 r
`
`k=O I
`
`句押 Mil k
`
`1'1
`
`I
`
`1'1
`
`j = 1,… , N - 1 and M relatively prime to N.
`= 0,
`Thus a code of any length N may be phase coded by either (4)
`or (7), respectively, d巳pending 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
`饵， or conjugating the entire code obviously wi1l not affect the
`autocorrelation function analogously to the aperiodic case [4].
`In addition, certain linear phase shifts of the form exp i(2πqk/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 {bd where
`
`b-aXD i2πqk
`k 一句""'1-'---;;;
`
`(10)
`
`Substituting bk for ak in (3)
`N-j-l
`
`~__
`
`Xj=Z ad+jexp i 斗~ (k - k 一 j)
`
`k=O
`
`~
`
`··A
`
`-EA
`
`、‘EJ
`
`品
`牛 1
`.2πq
`2.: aka;+j-N exp i 丁?- (k - k 一 j + N)
`k=N-j
`=即一 i 于 (NZGkatJ 立jaιN)
`
`1'1
`
`，，‘‘、
`
`= 0,
`as the quantity inside the parentheses vanishes.
`
`j = 1 ，2，… ， N 一 1
`
`ZTE/SAMSUNG 1004-0002
`
`2
`
`