At present, optimal coding for a noiseless digital channel with digits of unequal cost requires solving a large linear programming problem. Much simpler procedures give codes, resembling Shannon's (1948) and Huffman's, that are found close to optimal in tests with typical sources and channels.>

A noiseless ideal low-pass filter, followed by a limiter, is normally used as a binary data channel by sampling the output once per Nyquist interval. Detectors that sample more often encounter intersymbol interference, but can be used in ways that increase the information rate. A signaling system that achieves an information rate of 1.072 b/Nyquist interval by allowing the detector to sample at times a half Nyquist interval apart is presented. This rate increase is small, but it shows that, in principle, oversampling does permit faster rates. Another signaling system that more closely resembles a digital data system is also presented; it has rate 1.050. By allowing a more irregular pattern of sampling times, the rate is increased to 1.090 (or 1.062 for the 'digital' system).>

A job is to be run on a machine subject to random failures. Failures are not self-evident. They must be detected by explicit tests, or checks. Checks detect failures to avoid wasting time working with a defective machine. After each successful check one has the option of saving the work just completed. Then, when failures occur, only the work done since the last save must be repeated. Effective use of checks and saves requires a compromise, since these procedures are themselves time-consuming. Scheduling saves alone, when failures are evident as soon as they occur, is often called checkpointing. The novelty of the model studied here stems from not assuming that failures are self-evident. This compounds the usual checkpointing problem by requiring schedules of failure checks as well as saves. This paper gives schedules of checks and saves that minimize the expected total time required to complete a given job. The most general failure mechanism considered is a renewal process. The Poisson process receives special emphasis, as it leads to the simplest results. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Abstract Finding short paths through mazes of rectangles has applications in VLSI wire‐routing and robotics. This paper introduces and analyzes heuristic algorithms for finding short paths, under the assumption that the algorithms have no information about rectangles not already encountered along a path. Tight worst‐case bounds are derived for the ratio of the length of these algorithms' paths to the lengths of shortest paths. A model of random mazes is defined for testing the typical or average‐case behavior of algorithms. Although specially designed mazes can force the heuristic algorithms to give long paths, simulations and analysis show that the better heuristics usually give paths nearly as short as possible.

Data compression has been suggested as a nonparametric way of discriminating between message sources. Compressions obtained from a Lempel-Ziv algorithm for relatively short messages, such as those encountered in practice, are examined. The intuitive notion of message complexity has less connection with compression than one might expect from known asymptotic results about infinite messages. Nevertheless, discrimination by compression remains an interesting possibility.>

Abstract Stations 1, 2, …,n are interconnected; bij channels join stations i and j. Channels may be grouped together in cables to reruce cost. A Routing problem requires a channel layout (or network of cables) that has minimum cost. The cost of a cable is taken to be independent of its length but a function f(k) of the cable size k. That kind of cost is unusual in practice, but might be appropriate if the “cable” is actually a satellite link. Requiring f(k) to be concave gives a discount for large cables. That imposes a number of special properties on the minimizing network. An extra assumption bij = b, a constant for all i, j, produces a solvable problem. Depending on the shape of f(k), the solution network is either a complete graph or a particular kind of tree.

An overloaded service system may reject customers if it has no queue to store them. In practice, rejected customers return later to make retrials and may not leave permanently (balk) until several retrials fail. A single-server system with Poisson arrivals is examined in which rejected customers balk or make retrials according to a simple probabilistic model. Customer service times are independent random variables, all with the same given distribution function b(t). The stationary probability distribution for the number of customers waiting to make retrials satisfies a complicated functional equation. The solution is elusive in general but can be obtained for special b(t) (exponential distribution) or special values of model parameters. When the solution cannot be found, bounds on the fraction of customers served can be obtained.>

In a flexible manufacturing system stations are arranged along a common conveyor that brings items for processing to the stations and also carries away the processed items. At each station specialized robots automatically load and unload items on and off the conveyor. We examine here a single station in such a system. A new kind of queueing problem arises, with input-output dependencies that result because the same conveyor transports items both to and from the station. The paper analyzes two models of a station. Model 1 has one robot that cannot return a processed item to the conveyor while unloading a new item for processing. Model 2 has two robots to allow simultaneous loading and unloading of the conveyor. A principal goal of the analysis is the proper choice of the distance separating the two points at which items leave and rejoin the conveyor.

A server moves at a constant rate around a closed tour, stopping to perform services wherever requests are encountered. Requests appear according to a Poisson process at locations independently and uniformly distributed over the tour, and the service times are all taken to be one unit. Discrete versions of this model have applications ranging from machine repair to computer/communication polling systems. The distributions of the number served in a cycle and the number of waiting requests and their waiting times are calculated, and defections are studied. Because our continuous model is simpler than the discrete models, more easily interpreted formulas and some results that have yet to be obtained for discrete models are acquired.

Information theory obtains efficient codes by encoding messages in large blocks. The code design requires block probabilities that are often hard to measure accurately. This paper studies the effect of inaccuracies in the block probabilities and gives coding procedures that anticipate some of the worst errors. For an efficient code, the mean numberdof digits per letter must be kept small. In some cases the expected value ofdcan be related to the size of the sample on which probability estimates are based. To underestimate badly the probability of a common letter or block is usually a serious error. To ensure against this possibility, some coding procedures are given that avoid extremely long codewords. These codes provide a worthwhile insurance but are still very efficient if the probability estimates happen to be correct.

In an asynchronous multiplex system a single band of radio frequencies carries many simultaneous conversations, each of which uses a distinguishable train of pulses as a "carrier." To design a good list of allowed pulse trains one is led to a peculiar kind of error-correcting code problem. The encoding sought uses binaryN-tuples (code words) in which most of the digits are zero. In addition the Hamming distances from any given code word to all cyclic permutations of all other code words must exceed a prescribed minimum value. The code words found herein may be generated simply using a shift register.

When messages are transmitted as blocks of binary digits, means of locating the beginnings of blocks are provided to keep the receiver in synchronism with the transmitter. Ordinarily, one uses a special synchronizing symbol (which is really a third kind of digit, neither 0 nor 1) for this purpose. The Morse code letter space and the teletype start and stop pulses are examples. If a special synchronizing digit is not available, its function may be served by a short sequence of binary digitsPwhich is placed as a prefix to each block. The other digits must then be constrained to keep the sequencePfrom appearing within a block. If blocks ofNdigits (including the prefixP) are used, the prefix should be chosen to make large the numberG(N)of different blocks which satisfy the constraints. Lengthening the prefix decreases the number of "message digits" which remain in the block but also relaxes the constraints. Thus, for eachN, there corresponds some optimum length of prefix. For each prefixP, a generating function, a recurrence formula, and an asymptotic formula for largeNare found forG(N). Tables ofG(N)are given for all prefixes of four digits or fewer. Among all prefixesPof a given lengthA, the one for whichG(N)has the most rapid growth isP = 11 \cdots 1. However, for this choice ofP, the table of values ofG(N)starts with small values;11 \cdots 1does not become the bestA-digit prefix untilNis very large. At these values ofN, the(A + 1) -digit prefix11 \cdots 10is still better. The tables suggest that, for anyN, a best prefix can always be found in the form11 \cdots 10, for suitableA. TakingP = 11 \cdots 10andA = [\log_2 (N \log_2 e)]it is shown thatG(N)is roughly0.35N^{-1} X2^N. This result is near optimal since no choice ofPcan makeG(N)exceedN^{-1}2^N.