James L. Massey reviews the book, Algebraic Codes for Data Transmission, written by R. E. Blahut. The book consists of 13 chapters and nearly 500 pages. The second edition of this book is a significant improvement over the first and should find a welcome place on the bookshelves of coding theorists and coding implementers alike.

Two conservation laws for mutual information in terms of directed informations between two synchronized sequences of random variables are derived, the first for the case of no conditioning and the second for the case of causal conditioning on a third synchronized sequence. As a byproduct of the derivation of the first conservation law, the directed information specifying the feedback flowing from the second sequence to the first sequence is identified, which leads to a simple proof that a previously known sufficient condition for equality of mutual and directed information is also a necessary condition

Random variables that take on values in the finite field of q elements are considered. It is shown that joint distributions of such random variables are equivalently described by the individual distributions of their linear combinations. Random vectors X that are equally likely to take on any row of an arbitrary q-ary rectangular array as their value are treated extensively, together with the random vector /spl Delta/X defined as the difference between two independent versions of such a random vector. It is shown that linear combinations of exactly /spl tau/ of the components of X are always biased toward 0. A quantitative measure /spl beta//sub /spl tau//, of this bias is introduced and shown to be given by a sum of Krawtchouk polynomials. The vanishing of /spl beta//sub /spl tau// is shown to be equivalent to the maximal randomness of linear combinations of exactly /spl tau/ of the components of X as well as of /spl Delta/X. When the rows of the original array are the codewords of a q-ary linear code, then the bias /spl beta//sub /spl tau// coincides with the number of codewords of Hamming weight /spl tau/ in the dual code. The results of this article generalize certain well-known results such as the MacWilliams' (1977) identities and Delsarte's (1973) theorem on the significance of the "dual distance" of nonlinear codes.

A user-separating (US) demodulator for a multiple-access system with digital transmission is defined to be a demodulator that, without knowledge of the channel codes of the various users, provides the decoder for each user with a scalar-valued output for each symbol period that permits maximum-likelihood decoding of that user's data. It is shown that such a US demodulator exists in general only for approximations to the true statistics of the modulator-input sequences of the interfering users. It is argued that approximating the interfering modulator-input sequences as independent, white Gaussian processes is the practical compromise between accuracy and simplicity in code-division multiple-access (CDMA) systems. The US demodulator for this approximation is shown to consist of a kind of matrix whitening fitter followed by a kind of matched-filter for the user in question. It is further shown that this US demodulator can often be well approximated as the symbol-by-symbol demodulator that makes the linear minimum mean-squared error estimate of each modulator-input symbol for the user in question. Simulation results are presented to confirm the theory of US demodulation and to illustrate its practical utility.>

It is shown that the sum capacity of the symbol-synchronous code-division multiple-access channel with equal average-input-energy constraints is maximized precisely by those spreading sequence multisets that meet Welch's lower bound on total squared correlation. It is further shown that the symmetric capacity of the channel determined by these same sequence multisets is equal to the sum capacity.>

The covariance of complex random variables and processes, when defined consistently with the corresponding notion for real random variables, is shown to be determined by the usual complex covariance together with a quantity called the pseudo-covariance. A characterization of uncorrelatedness and wide-sense stationarity in terms of covariance and pseudo-covariance is given. Complex random variables and processes with a vanishing pseudo-covariance are called proper. It is shown that properness is preserved under affine transformations and that the complex-multivariate Gaussian density assumes a natural form only for proper random variables. The maximum-entropy theorem is generalized to the complex-multivariate case. The differential entropy of a complex random vector with a fixed correlation matrix is shown to be maximum if and only if the random vector is proper, Gaussian, and zero-mean. The notion of circular stationarity is introduced. For the class of proper complex random processes, a discrete Fourier transform correspondence is derived relating circular stationarity in the time domain to uncorrelatedness in the frequency domain. An application of the theory is presented.>

A general theorem is proved showing how to obtain a constant-weight binary cyclic code from a p-ary linear cyclic code, where p is a prime, by using a representation of GF(p) as cyclic shifts of a binary p-tuple. Based on this theorem, constructions are given for four classes of binary constant-weight codes. The first two classes are shown to achieve the Johnson upper bound on minimum distance asymptotically for long block lengths. The other two classes are shown similarly to meet asymptotically the low-rate Plotkin upper bound on minimum distance. A simple method is given for selecting virtually the maximum number of cyclically distinct codewords with full cyclic order from Reed-Solomon codes and from Berlekamp-Justesen maximum-distance-separable codes. Two correspondingly optimum classes of constant-weight cyclically permutable codes are constructed. It is shown that cyclically permutable codes provide a natural solution to the problem of constructing protocol-sequence sets for the M-active-out-of-T-users collision channel without feedback.>

A parity-check matrix for a q-ary repeated-root cyclic code is derived using the Hasse derivative. Then the minimum distance of a q-ary repeated-root cyclic code is expressed in terms of the minimum distance of a certain simple-root cyclic code. With the help of this result, several binary repeated-root cyclic codes of lengths up to n=62 are shown to contain the largest known number of codewords for their given length and minimum distance. The relative minimum distance d/sub min//n of q-ary repeated-root cyclic codes of rate r>or=R is proven to tend to zero as the largest multiplicity of a root of the generator g(x) increases to infinity. It is further shown that repeated-root cycle codes cannot be asymptotically better than simple-root cyclic codes.>

An appraisal is given of the current status, both technical and nontechnical, of cryptologic research. The principal concepts of both secret-key and public-key cryptography are described. C.E. Shanon's theory of secrecy (1949) and G.J. Simon's theory authenticity (1984) are reviewed for the insight that they give into practical cryptographic systems. Public-key concepts are illustrated through consideration of the Diffie-Hellman public-key-distribution system and the Rivest-Shamir-Adleman public-key cryptosystem. The subtleties of cryptographic protocols are shown through consideration of some such specific protocols.>

The discrete-time Gaussian channel with intersymbol interference (ISI) where the inputs are subject to a per symbol average-energy constraint is considered. The capacity of this channel is derived by means of a hypothetical channel model called the N-circular Gaussian channel (NCGC), whose capacity is readily derived using the theory of the discrete Fourier transform. The results obtained for the NCGC are used further to prove that, in the limit of increasing block length N, the capacity of the discrete-time Gaussian channel (DTGC) with ISI using a per block average-energy input constraint (N-block DTGC) is indeed also the capacity when using the per symbol average-energy constraint.>

It is shown that a Boolean combining function f(x) of n variables is mth-order correlation-immune if and only if its Walsh transform F( omega ) vanishes for all omega with Hamming weight between 1 and m, inclusive. This result is used to extend slightly Siegenthaler's (IEEE Trans. Comput., vol. C-34, pp. 81-85, Jan. 1985) characterization of the algebraic normal form of correlation-immune combining functions.>

Families of zero-error codes for the real binary adder channel with feedback that achieve high rate pairs are introduced. Two families of zero-error block codes are given for the case in which only one of the two senders receives feedback about the channel output. In the first of these families, the uninformed sender transmits at a rate of nearly one bit per symbol and the informed sender transmits slightly less that1/2bit per symbol. The second family is designed for the case in which the informed sender sends at or near one bit per symbol and the uninformed one sends nearly1/2bit per symbol. A family of zero-error codes is introduced, based on the Fibonacci recursion; these codes are readily implemented by means of a simple square-dividing strategy. The Fibonacci codes achieveR_{1}=R_{2}=\log_{2} [(1 + \sqrt{5})/2]in the limit of large block length. Time-sharing between members of these three code families is used to obtain an achievable rate region, or inner bound, to the zero-error capacity region for block coding. For the case in which the feedback is available to both senders, a variant of the Fibonacci difference equation is used to generate zero-error block codes with slightly higher asymptotic rateR_{1}=R_{2}=0.717.

A model is proposed for the situation whereMusers share a common communication resource but, because of unknown time offsets among their clocks, cannot transmit their data packets in a time-sharing mode and, because of the lack of a feedback link, can never determine these time offsets and also can never be sure of the outcomes of their individual packet transmissions. Each user is required to make his packet transmissions at times determined by a protocol signal that is independent of the data to be sent. The capacity and zero-error capacity regions of this channel are determined for both the unsynchronized and slot-synchronized cases; these four regions are shown to coincide. It is further shown that a dense set of rate points on the outer boundary of this region can be achieved in the slot-synchronized case. Specific constructions of protocol sequences for achieving these points are given, and the technique of "decimation decoding" is introduced for identifying the sender of each successfully transmitted packet. Maximum-erasure burst-correcting codes over an alphabet of arbitrary size are constructed and shown to suffice for reconstructing the packets lost in "collisions" when these protocol sequences are used.

{\em Capacity} is defined for a given distribution of offered traffic as the maximum rate with which packets can be sent with finite delay through the network by appropriate routing. It is shown how capacity depends on the traffic characteristics and on the topology of ring communication systems interconnected so as to provide unique loop-free routing. First, the traffic conditions are given under which the capacity of a {\em single ring} attains its maximum and its minimum. For the case of {\em uniform traffic} it is shown that the capacity is equal to twice the minimum capacity. Then it is shown that, for uniform traffic, the capacity relative to a single ring communication system can be increased by as much as33.3or80percent when the stations are split up into two or three separate rings, respectively, interconnected to give unique loop-free routing. Exact formulas are given for the capacity of systems with an arbitrary number of stations split up into an arbitrary number of separate rings interconnected to give unique loop-free routing. Finally, it is shown that connecting {\em local rings} through a star network with a central switching node is particularly useful when stations can be segregated into local groups of stations which often communicate with stations from the same local group but only rarely with stations from the other groups. Exact formulas are given to calculate the capacity of such interconnected ring communication systems.

It is shown that When Pierce's pulse-position modulation scheme with 2Lpositions is used on a self-noise-limited directdetection optical communication channel, there results a 2L-ary erasure channel that is equivalent to the parallel combination ofL"completely correlated" binary erasure channels. The capacity of the full channel is the sum of the capacities of the component channels, but the cutoff rate of the full channel is shown to be much smaller than the sum of the cutoff rates. An interpretation of the cutoff rate is given that suggests a complexity advantage in coding separately on the component channels. It is shown that if short-constraint length convolutional codes with Viterbi decoders are used on the component channels, then the performance and complexity compare favorably with the Reed-Solomon coding system proposed by McEliece for the full channel. The reasons for this unexpectedly fine performance by the convolutional code system are explored in detail, as are various facets of the channel structure.

Two new computationally efficient algorithms are developed for finding the exact burst-correcting limit of a cyclic code. The first algorithm is based on testing the colmn rank of certain submatrices of the parity-check matrix of the code. An auxiliary result is a proof that every cyclic(n,k)codes with a minimum distance of at least three, corrects at least all bursts of length\lfloor (n - 2k + 1)/2 \rflooror less. The second algorithm, which requires somewhat less computation, is based on finding the length of the shortest linear feedback shift-register that generates the subsequences of lengthn - kof the sequence formed by the coefficients of the parity-check polynomialh(x), augmented with\lfloor (n-k)/2 \rfloor -1leading zeros and trailing zeros. Tables of the burst-correcting limit for a large number of binary cyclic codes are included.

It is shown that the fractionpof ones in theMnpositions ofMdistinct binaryn-tuples satisfies the inequality \begin{equation} h(p) \geq (l/n) \log_2 M \end{equation} whereh(p) = - p log_2 p - (1 - p) log_2 (1 - p)is the binary entropy function. This inequality, which simplifies the derivation of the distance property of the Justesen codes, is proved using an elegant information-theoretic argument due to Kriz.

For any nonzero elementcof a general finite fieldGF(q), it is shown that the polynomials(x - c)^i, i = 0,1,2,\cdots, have the "weight-retaining" property that any linear combination of these polynomials with coefficients inGF(q)has Hamming weight at least as great as that of the minimum degree polynomial included. This fundamental property is then used as the key to a variety of code constructions including 1) a simplified derivation of the binary Reed-Muller codes and, for any primepgreater than 2, a new extensive class ofp-ary "Reed-Muller codes," 2) a new class of "repeated-root" cyclic codes that are subcodes of the binary Reed-Muller codes and can be very simply instrumented, 3) a new class of constacyclic codes that are subcodes of thep-ary "Reed-Muller codes," 4) two new classes of binary convolutional codes with large "free distance" derived from known binary cyclic codes, 5) two new classes of long constraint length binary convolutional codes derived from2^r-ary Reed-Solomon codes, and 6) a new class ofq-ary "repeated-root" constacyclic codes with an algebraic decoding algorithm.

This paper considers the optimum method for locating a sync word periodically imbedded in binary data and received over the additive white Gaussian noise channel. It is shown that the optimum rule is to select the location that maximizes the sum of the correlation and a correction term. Simulations are reported that show approximately a 3-dB improvement at interesting signal-to-noise ratios compared to a pure correlation rule. Extensions are given to the "phase-shift keyed (PSK) sync" case where the detector output has a binary ambiguity and to the case of Gaussian data.

It is shown that the metric proposed originally by Fano for sequential decoding is precisely the required statistic for minimum-error-probability decoding of variable-length codes. The analysis shows further that the "natural" choice of bias in the metric is the code rate and gives insight into why the Fano metric has proved to be the best practical choice in sequential decoding. The recently devised Jelinek-Zigangirov "stack algorithm" is shown to be a natural consequence of this interpretation of the Fano metric. Finally, it is shown that the elimination of the bias in the "truncated" portion of the code tree gives a slight reduction in average computation at the sacrifice of increased error probability.

It is shown in this paper that the iterative algorithm introduced by Berlekamp for decoding BCH codes actually provides a general solution to the problem of synthesizing the shortest linear feedback shift register capable of generating a prescribed finite sequence of digits. The shift-register approach leads to a simple proof of the validity of the algorithm as well as providing additional insight into its properties. The equivalence of the decoding problem for BCH codes to a shift-register synthesis problem is demonstrated, and other applications for the algorithm are suggested.

Abstract—This paper states the necessary and sufficient conditions for the existence of a feedforward inverse for a feedforward linear sequential circuit and gives an implicit procedure for constructing such inverses. It then goes on to give the necessary and sufficient conditions for the existence of general inverses with finite delay and gives procedures for constructing a class of such inverses. The discussion considers both the transfer function matrix description and the structural matrix description of the linear sequential circuit, together with the complementary nature of the results obtained from these two viewpoints. Finally, a large part of the work is motivated by results and techniques which have been applied in the study of continuous-time linear dynamical systems and thus serves to point out the advantages which may accrue through simultaneous study of both continuous-time systems and linear sequential circuits.

One of the design problems of digital computers is in code conversion from analog form to its equivalent digital form, and vice versa. In data logging, reduction, and process control applications of digital computers, input data are frequently in analog or shaft position form. Conventionally weighted binary numbers are not used directly for analog readings because at certain positions these may be ambiguously expressed. Gray suggested a code in this application which eliminates the ambiguity of natural binary numbers. The basic rule in Gray code generation is to allow only one bit change between adjacent numbers.1 The Gray code, unfortunately, is difficult to use in computation. Hence, it is customary to perform code conversion before attempting computer arithmetic operations.

For any prime-powerq, it is shown that there existq-ary convolutional codes with the equidistance property that every code word is at the same distance from all code words disagreeing in the information digits to be decoded. These codes are called "uniform codes" and it is shown that they can be encoded in a very simple manner. The block codes most similar to uniform codes are the maximal-length codes which also have the equidistance property. It is shown that the error performance of these classes of codes is nearly identical but that the uniform codes have simpler encoding circuits. This latter fact is of importance in space applications, which is the most likely use for these codes.

A general procedure is formulated for decoding any convolutional code with decoding delayNblocks that corrects all bursts confined toror fewer consecutive blocks followed by a guard space of at leastN-1consecutive error-free blocks. It is shown that all such codes can be converted to a form called "doubly systematic" which simplifies the decoding circuitry. The decoding procedure can then be implemented with a circuit of the same order of complexity as a parity-checking circuit for a block-linear code. A block diagram of a complete decoder is given for an optimal burst-correcting code. It is further shown that error propagation after a decoding mistake is always terminated by the occurrence of a double guard space of error-free blocks.

A new and conceptually simple decoding procedure is developed for all of the cyclic Bose-Chaudhuri-Hocquenghem codes. Iftis the number of errors guaranteed correctable by the Bose-Chaudhuri bound, then any pattern oftor fewer errors can be corrected in a step-by-step manner using this procedure. In the binary case, the method requires only the determination of whether at \times tmatrix is singular. In the general case, the method requires only the determination of whether at \times tmatrix and a(t+1) \times (t+1)matrix are simultaneously singular. Circuits to implement the algorithm are developed and two detailed examples are given. Finally, the step-by-step procedure is compared to other known methods for decoding the Bose-Chaudhuri-Hocquenghem codes.

Two forms of nonlinear-feedback shift-registers are considered. In the Type-I register, the feedback output is added to the shift-register contents at an arbitrary number of stages. In the type-II register, the feedback is input to the first stage only. It is shown that for every Type-I register there is an equivalent Type-II register in the sense that the autonomous state diagrams differ only by a labelling of the states. Moreover, the mapping between equivalent states can always be chosen to be a linear transformation. This theorem is a well-known result in the theory of linear-feedback shift-registers and is thus seen to apply unchanged to the nonlinear case.