Presents a combinatorial analysis to derive a closed-form expression for the number of transmission errors that occur in a block transmitted through a Gilbert channel. This expression simplifies the computations needed to investigate the tradeoffs among the decoding error probability, degree of interleaving, and the error-correction ability of a code. The authors illustrate how a designer may apply the method to determine different combinations of the degree of interleaving and error correction ability to achieve a specified decoding error rate.>

The use of direct motion vision for determining the depth of a scene is investigated. To permit direct comparison of analytical and experimental results, only translational motion and planar patches of constant depth are considered. The analysis shows that the accuracy with which depth can be determined increases with the sum of the squares of the temporal derivatives over the patch; this quantity is referred to as the apparent size of the patch. After determining the relationship between relative depth error and apparent size analytically, a number of experiments with camera-generated image sequences were performed. In nearly all of these experiments, the agreement between the analytically determined and measured values of the relative depth error is very good.>

A closed curve in the plane can be described in several ways. We show that a simple representation in terms of radius of curvature versus normal direction has certain advantages. In particular, convolutional filtering of the extended circular image leads to a closed curve. Similar filtering operations applied to some other representations of the curve do not guarantee that the result corresponds to a closed curve. In one case, where a closed curve is produced, it is smaller than the original. A description of a curve can be based on a sequence of smoothed versions of the curve. This is one reason why smoothing of closed curves is of interest.

A new procedure for handling retransmissions in a selective-repeat ARQ system is proposed. This procedure can operate with a receive buffer of minimal size; in addition it places little computational load on the transmit and receive processors. The procedure is simple enough that its throughput can be calculated exactly. Analysis of this strategy shows that: 1)it yields higher throughput than earlier ARQ techniques; 2) for modest receive buffer size, its throughput differs little from channel capacity; 3) as buffer size increases, throughput approaches channel capacity. The final section of the paper considers the performance of ARQ systems on channels in which errors occur in bursts. It indicates that on reasonably good channels, error burstiness has little effect on throughput.

Coding schemes for the binary memorylessT-user adder channel are investigated in this paper. First upper and lower bounds on the capacity sum, which are asymptotically tight with increasingT, are derived for the noiseless case. Second, a class ofT-user uniquely decodable codes with rates, asymptotically inT, equal to the maximal achievable values is constructed. A decoding algorithm for these codes is also presented. Next, a class of error-correcting codes for the noisyT-user adder channel is constructed. It is shown that these codes can he used to construct multilevel codes suitable for use on the additive white Gaussian noise channel.

Justesen has shown that concatenating a class of binary codes with a Reed-Solomon (RS) code produces asymptotically good codes. For low rates, the value of the ratio of minimum distance to code length(d/n)for such codes is substantially lower than that known to be achievable by the Zyablov bound. In this paper, we present a small class of binary codes with some useful properties. This class is then used in Justesen's construction to produce codes that have relatively large values ofd/nfor low rates.

By using the more general class of BCH codes, rather than RS codes as originally proposed, the results of Justesen [1] are improved for code rates below 0.07. The value ofd/nfor the new codes approaches the Varsharmov-Gilbert hound (0.5) as the rate approaches zero.

This paper presents an algebraic technique for decoding binary block codes in situations where the demodulator quantizes the received signal space intoQ > 2regions. The method, referred to as weighted erasure decoding (WED), is applicable in principle to any block code for which a binary decoding procedure is known.

Cyclic product codes are useful for two reasons. First, they impart a great deal of algebraic structure to a subclass of the class of cyclic codes. Second, because they can be formulated in terms of much shorter (component) codes, their decoding may be considerably simpler than many other types of codes. In this paper both of the properties of cyclic product codes are developed. It is shown that the product of two majority-logic decodable cyclic codes is also majority-logic decodable provided that one of the component codes is one-step decodable. More precisely, if the row-component code can realize minimum distanced_1(i.e., correct[(d_1 -- 1)/2]errors) with a one-step majority-logic decoder and if the column-component code can realize minimum distanced_2with anL-step decoder, then the product code can realize distanced_1 d_2with anL-step decoder. It is also shown that the algebraic structure of cyclic product codes can be applied to establish the exact minimum distance of certain subclasses of BCH codes.

In this paper a class of nonprimitive cyclic codes quite similar in structure to the original Reed-Muller codes is presented. These codes, referred to herein as nonprimitive Reed-Muller codes, are shown to possess many of the properties of the primitive codes. Specifically, two major results are presented. First the code length, number of information symbols, and minimum distance are shown to be related by means of a parameter known as the order of the code. These relationships show that for given values of code length and rate the codes have relatively large minimum distances. It is also shown that the codes are subcodes of the BCH codes of the same length and guaranteed minimum distance; thus in general the codes are not as powerful as the BCH codes. However, for most interesting values of code length and rate the difference between the two types of codes is slight. The second result is the observation that the codes can be decoded with a variation of the original algorithm proposed by Reed for the Reed-Muller codes. In other words, they areL-step orthogonalizable. Because of their large minimum distances and the simplicity of their decoders, nonprimitive Reed-Muller codes seem attractive for use in error-control systems requiring multiple random-error correction.

A new class of linear block codes, called self-orthogonal quasi-cyclic codes, is defined. It is shown that the problem of designing these codes is equivalent to the problem of designing disjoint difference sets. As a result, several classes of optimal and near-optimal codes can be constructed analytically and other codes can be found by a computer-aided search procedure. A list of codes is given for practical values of minimum distance and efficiency. Two easily implemented decoding algorithms are described, and a Monte Carlo evaluation of the performance of several codes on the binary symmetric channel is presented. This evaluation shows that, when decoded with the better of the two algorithms, these codes perform nearly as well as the Bose-Chaudhuri-Hocquenghem (BCH) codes with the same minimum distance and efficiency in the cases examined. Although these codes must be long relative to the BCH codes, the low cost and lack of complexity of the equipment required to correct large numbers of errors should make them competitive for practical systems.

A new class of cyclic codes, cyclic product codes, is characterized. These codes enjoy the implementation advantages of cyclic codes and, in addition, possess the important structural properties of product (iterated) codes. The main results are as follows: \begin{enumerate} \item Conditions are given which ensure that the product of two, and, hence, arbitrarily many, cyclic codes is itself a cyclic code. \item Cyclic product codes are shown to be capable of unambiguous correction of both bursts and random errors. \item The generator polynomial of the cyclic product code is derived and shown to be a simple function of the generator polynomials of the subcodes. \end{enumerate} These results have the following various applications: a) the codes effect a compromise between random and burst-error-correcting codes and, therefore, appear to be well-suited to error correction on channels in which both types of errors occur, b) many codes in a particular subclass of the class of cyclic product codes are efficient burst-error correctors and are more easily implemented than the equivalent codes formed by interleaving short codes, c) the previously mentioned results 1) and 3) can be applied to some cyclic codes to show that they are product codes as well; then known results on the minimum distance of product codes can be applied. This improves on the Bose-Chaudhuri-Hocquenghem lower bound in many cases.