Schalkwijk and Kailath (1966) developed a class of block codes for Gaussian channels with ideal feedback for which the probability of decoding error decreases as a second-order exponent in block length for rates below capacity. This well-known but surprising result is explained and simply derived here in terms of a result by Elias (1956) concerning the minimum mean-square distortion achievable in transmitting a single Gaussian random variable over multiple uses of the same Gaussian channel. A simple modification of the Schalkwijk-Kailath scheme is then shown to have an error probability that decreases with an exponentialorderwhich is linearly increasing with block length. In the infinite bandwidth limit, this scheme produces zero error probability using bounded expected energy at all rates below capacity. A lower bound on error probability for the finite bandwidth case is then derived in which the error probability decreases with an exponential order which is linearly increasing in block length at the same rate as the upper bound.

Variable-length block-coding schemes are investigated for discrete memoryless channels with ideal feedback under cost constraints. Upper and lower bounds are found for the minimum achievable probability of decoding error Pe,min as a function of constraints R, P, and tau on the transmission rate, average cost, and average block length, respectively. For given R and P, the lower and upper bounds to the exponent -( ln Pe,min)/tau are asymptotically equal as tau rarr infin. The resulting reliability function,limtaurarrinfin(-In Pe,min)/tau as a function of R and V, is concave in the pair (R,P) and generalizes the linear reliability function of Burnashev to include cost constraints. The results are generalized to a class of discrete-time memoryless channels with arbitrary alphabets, including additive Gaussian noise channels with amplitude and power constraints.

A wireless network with fading and a single source-destination pair is considered. The information reaches the destination via multiple hops through a sequence of layers of single-antenna relays. At high signal-to-noise ratio (SNR), the simple amplify-and-forward strategy is shown to be optimal in terms of degrees of freedom, because it achieves the degrees of freedom equal to a point-to-point multiple-input multiple-output (MIMO) system. Hence, the lack of coordination in relay nodes does not reduce the achievable degrees of freedom. The performance of this amplify-and-forward strategy degrades with increasing network size. This phenomenon is analyzed by finding the tradeoffs between network size, rate, and diversity. A lower bound on the diversity-multiplexing tradeoff for concatenation of multiple random Gaussian matrices is obtained. Also, it is shown that achievable network size in the outage formulation (short codes) is a lot smaller than the ergodic formulation (long codes).

Variable-length block-coding schemes are investigated for discrete memoryless channels (DMC) with perfect feedback under cost constraints. Upper and lower bounds are found for the minimum achievable probability of decoding error Pepsi,minas a function of transmission rate R, cost constraint P, and expected block length taumacr. For given P and R, the lower and upper bounds to the exponent -(InPepsi,min)/taumacr are asymptotically equal as taumacr rarrinfin. The reliability function, limtaurarrinfin(-ln Pepsi,min)/taumacr, as a function of P and R, is concave in the pair (P, R) and generalizes the linear reliability function of Burnashev (M.V. Burnashev, 1976) to include cost constraints

We develop an on-line wavelength assignment (WA) algorithm for a wavelength-routed WDM tree network. The algorithm dynamically supports all k-port traffic matrices among N end nodes, where k denotes an integer vector [k/sub 1/...,k/sub N/] and end node i,1/spl les/i/spl les/N, can transmit at most k/sub i/ wavelengths and receive at most k/sub i/ wavelengths. Our algorithm is rearrangeably nonblocking, uses the minimum number of wavelengths, and requires at most d/sup */-1 lightpath rearrangements per new session request, where d/sup */ is the degree of the most heavily used node. We observe that the number of lightpath rearrangements per new session request does not increase as the amount of traffic k scales up by an integer factor. In addition, wavelength converters cannot reduce the number of wavelengths required to support k-port traffic in a tree network. We show how to implement our WA algorithm using a hybrid wavelength-routed/broadcast tree with only one switching node connecting several passive broadcast subtrees. Finally, using roughly twice the minimum number of wavelengths for a rearrangeably nonblocking WA algorithm, we can modify the WA algorithm to be strict-sense nonblocking.

We study the provision of deterministic rate guarantees over single crossbar switches. Birkhoff decomposition yields a general approach for this problem, but the required complexity can be very high and the quality of service can be unsatisfactory for practical traffic sources. We develop a method called rate quantization which works with any resource speedup greater than 1 to convert the set of desired rates into a certain discrete set in such a way that the complexity and the quality of service guarantees can be greatly improved over a Birkhoff switch. Moreover, quantization enables us to develop a Slepian-Duguid-like algorithm that enables the switch to both adapt to dynamically varying traffic and simplify switch scheduling significantly.

We develop on-line routing and wavelength assignment (RWA) algorithms for WDM bidirectional ring and torus networks with N nodes. The algorithms dynamically support all k-allowable traffic matrices, where k denotes an arbitrary integer vector [k/sub 1/, k /sub 2/, ..., k/sub N/], and node i, 1/spl les/i/spl les/N, can transmit at most k/sub i/ wavelengths and receive at most k/sub i/ wavelengths. Both algorithms support the changing traffic in a rearrangeably nonblocking fashion. Our first algorithm, for a bidirectional ring, uses /spl lceil/(/spl Sigma//sub i=1//sup N/k/sub i/)/3/spl rceil/ wavelengths in each ring direction and requires at most three lightpath rearrangements per new session request regardless of the number of nodes N and the amount of traffic k. When all the k/sub i/s are equal to k, the algorithm uses /spl lceil/kN/3/spl rceil/ wavelengths, which is known to be the minimum for any off-line rearrangeably nonblocking algorithm. Our second algorithm, for a torus topology, is designed for the special case with all the k/sub i/s equal to k. For a square torus network with N nodes, the algorithm uses /spl lceil/k/spl radic/N/2/spl rceil/ wavelengths in each fiber, which is shown to be at most two times a lower bound obtained by assuming full wavelength conversion at all nodes. In addition, the algorithm requires at most /spl radic/N-1 lightpath rearrangements per new session request regardless of the amount of traffic k.

Queueing systems which map Poisson input processes to Poisson output processes have been well-studied in classical queueing theory. This paper considers two discrete-time queues whose analogs in continuous-time possess the Poisson-in-Poisson-out property. It is shown that when packets arriving according to an arbitrary ergodic stationary arrival process are passed through these queueing systems, the corresponding departure process has an entropy rate no less (some times strictly more) than the entropy rate of the arrival process. Some useful by-products are discrete-time versions of: (i) a proof of the celebrated Burke's (1956) theorem, (ii) a proof of the uniqueness, amongst renewal inputs, of the Poisson process as a fixed point for exponential server queues proposed by Anantharam (1993), and (iii) connections with the timing capacity of queues described by Anantharam and Verdu (1996).

We consider a user communicating over a fading channel with perfect channel state information. Data are assumed to arrive from some higher layer application and are stored in a buffer until transmitted. We study adapting the user's transmission rate and power based on the channel state information as well as the buffer occupancy; the objectives are to regulate both the long-term average transmission power and the average buffer delay incurred by the traffic. Two models for this situation are discussed; one corresponding to fixed-length/variable-rate codewords and one corresponding to variable-length codewords. The tradeoff between the average delay and the average transmission power required for reliable communication is analyzed. A dynamic programming formulation is given to find all Pareto optimal power/delay operating points. We then quantify the behavior of this tradeoff in the regime of asymptotically large delay. In this regime, we characterize simple buffer control policies which exhibit optimal characteristics. Connections to the delay-limited capacity and the expected capacity of fading channels are also discussed.

We show that very large bandwidths on fading multipath channels cannot be effectively utilized by spread-spectrum systems that (in a particular sense) spread the available power uniformly over both time and frequency. The approach is to express the input process as an expansion in an orthonormal set of functions each localized in time and frequency. The fourth moment of each coefficient in this expansion is then uniformly constrained. We show that such a constraint forces the mutual information to 0 inversely with increasing bandwidth. Simply constraining the second moment of these coefficients does not achieve this effect. The results suggest strongly that conventional direct-sequence code-division multiple-access (CDMA) systems do not scale well to extremely large bandwidths. To illustrate how the interplay between channel estimation and symbol detection affects capacity, we present results for a specific channel and CDMA signaling scheme.

Claude E. Shannon (1948) invented information theory and provided the concepts, insights, and mathematical formulations that now form the basis for modern communication technology. In a surprisingly large number of ways, he enabled the information age. A major part of this influence comes from his two-part monumental 1948 paper, "A Mathematical Theory of Communication." We attempt here to provide some clues as to how a single person could have such a major impact. We first describe Shannon's life and then study his publications in the communication area. We next consider his research style in the context of these publications. Finally, we consider the process under which the impact of his work evolved from the creation of a beautiful and challenging theory to the establishment of the central principles guiding digital communication technology. We end with some reflections on the research environment that stimulates such work both then and now.

We present a new algorithm for automatic protection switching (APS) which creates node (edge) redundant trees on any node (edge)-redundant network. These trees are desirable for performing multicasting with APS. Our algorithm is based on constructing trees with appropriate associated directions. The algorithm gives great flexibility in the choice of trees.

Tunstall codes are variable-to-fixed length codes that maximize the expected number of source letters per dictionary string for discrete, memoryless sources. We analyze a generalization of Tunstall coding to sources with memory and demonstrate that as the dictionary size increases, the number of code letters per source symbol comes arbitrarily close to the minimum among all variable-to-fixed length codes of the same size. We also find the asymptotic relationship between the dictionary size and the average length of a dictionary entry.

The purpose of this paper is to understand the relationship between utilization, fairness and access delay in high speed slotted bus networks. We illustrate this relationship by means of a protocol called FUFA (fully utilized and fair). We define full utilization, and fairness precisely, and show that both are achieved together in the FUFA protocol. In addition, the protocol provides bounded access delay that is linear in the round trip propagation delay, and at most a constant away from its minimum possible value for any bus protocol that is both fully utilized and fair. The main idea is that each station takes account of the idle slots propagated previously to interpret the information from downstream (i.e., estimated aggregate number of data segments in the queue downstream and estimated number of active downstream stations). This allows the active downstream stations to be served in a round robin fashion according to the updated information.

We describe some of the results of the Advanced Research Projects Agency (ARPA) sponsored Consortium on Wideband All-Optical Networks in developing architectures, technology components, and applications for the realization of scaleable, wideband, and transparent optical wavelength-division multiplexing (WDM) networks. Our architecture addresses all-optical transport over the wide, metropolitan, and local areas. It utilizes wavelength partitioning, routing, and active multiwavelength cross-connect switches to achieve a network that is scaleable in the number of users, data rates, and geographic span. The network supports two services which can be point-to-multipoint or multipoint-to-multipoint simplex or duplex connections. The A service is a transparent physically circuit-switched service and the B-service is a scheduled time-slotted circuit which is transparent within its time slots. We have developed a 20-channel local and metropolitan area WDM testbed deployed in the Boston area, now undergoing characterization and experimental applications.

We develop and analyze a multiaccess communication model over the additive Gaussian noise channel. The framework is information-theoretic; nonetheless it also incorporates some queueing-theoretic aspects of the problem.>

We study the problem of statistical multiplexing of cell streams that have correlations at multiple time-scales. Each stream is modeled by a singularly perturbed Markov-modulated process with some state transitions occurring much less frequently than others. One motivation of this model comes from variable-rate compressed video, where the fast time-scale dynamics may correspond to correlations between adjacent frames, while the slow time-scale dynamics may correspond to correlations which in the same scene of a video sequence. We develop a set of large deviations results to estimate the buffer overflow probabilities in various asymptotic regimes in the buffer size, rare transition probabilities, and the number of streams. Using these results, we characterize the multiplexing gain in both the channel capacity and the buffering requirements and highlight the impact of the slow time-scale of the streams.>

All-optical networks are networks for which all data paths remain optical from input to output. With rapid development of optical technology, such networks are a viable choice for the high speed wide area networks of the future. Wavelength division multiple access (WDMA) currently provides the most mature technology for all-optical networks. The authors discuss a class of WDMA networks that are homogeneous in the sense that each node contains both an input/output port and a switch. They focus on the permutation routing problem and first, present a lower bound on the number of wavelengths required for permutation routing as a function of the size and degree of the network. They use particular topologies, including the multistage perfect shuffle, the Debruijn, and the hypercube, to find achievable upper bounds on the number of required wavelengths.>

The authors analyze the expected delay for infinite precision arithmetic codes, and suggest a practical implementation that closely approximates the idealized infinite precision model.>

Worst-case bounds on delay and backlog are derived for leaky bucket constrained sessions in arbitrary topology networks of generalized processor sharing (GPS) servers. The inherent flexibility of the service discipline is exploited to analyze broad classes of networks. When only a subset of the sessions are leaky bucket constrained, we give succinct per-session bounds that are independent of the behavior of the other sessions and also of the network topology. However, these bounds are only shown to hold for each session that is guaranteed a backlog clearing rate that exceeds the token arrival rate of its leaky bucket. A much broader class of networks, called consistent relative session treatment (CRST) networks is analyzed for the case in which all of the sessions are leaky bucket constrained. First, an algorithm is presented that characterizes the internal traffic in terms of average rate and burstiness, and it is shown that all CRST networks are stable. Next, a method is presented that yields bounds on session delay and backlog given this internal traffic characterization. The links of a route are treated collectively, yielding tighter bounds than those that result from adding the worst-case delays (backlogs) at each of the links in the route. The bounds on delay and backlog for each session are efficiently computed from a universal service curve, and it is shown that these bounds are achieved by "staggered" greedy regimes when an independent sessions relaxation holds. Propagation delay is also incorporated into the model. Finally, the analysis of arbitrary topology GPS networks is related to Packet GPS networks (PGPS). The PGPS scheme was first proposed by Demers, Shenker and Keshav (1991) under the name of weighted fair queueing. For small packet sizes, the behavior of the two schemes is seen to be virtually identical, and the effectiveness of PGPS in guaranteeing worst-case session delay is demonstrated under certain assignments.>

Presents a logical approach to designing an effective and efficient error detection scheme for ATM. The authors specifically look at providing error protection for the class C service of ATM, which is a connection oriented, variable bit rate service, with no required timing between source and destination. The resulting scheme is similar to the scheme proposed by the CCITT in AAL 5. The authors propose to add a 34 bit CRC to each frame. Their proposal also includes a modification of the mechanism for preventing misdirected cells that is used at the ATM layer.>

Worst-case bounds on delay and backlog are derived for leaky bucket constrained sessions in arbitrary topology networks of generalized processor sharing servers. When only a subset of the sessions are leaky bucket constrained succinct per-session bounds that are independent of the behavior of the other sessions and also of the network topology are given. However, these bounds are only shown to hold for each session that is guaranteed a backlog clearing rate that exceeds the token arrival rate of its leaky bucket. When all of the sessions are leaky bucket constrained, a much larger class of networks called consistent relative session treatment networks is analyzed. The session i route is treated as a whole, yielding tighter bounds than those that result from adding the worst-case delays (backlogs) at each of the servers in the route. The bounds on delay and backlog for each session are computed and shown to be achieved by staggered regimes when an independent sessions relaxation holds. Propagation delay is also incorporated into the model.>

The problem of allocating network resources to the users of an integrated services network is investigated in the context of rate-based flow control. The network is assumed to be a virtual circuit, connection-based packet network. It is shown that the use of generalized processor sharing (GPS), when combined with leaky bucket admission control, allows the network to make a wide range of worst-case performance guarantees on throughput and delay. The scheme is flexible in that different users may be given widely different performance guarantees and is efficient in that each of the servers is work conserving. The authors present a practical packet-by-packet service discipline, PGPS that closely approximates GPS. This allows them to relate results for GPS to the packet-by-packet scheme in a precise manner. The performance of a single-server GPS system is analyzed exactly from the standpoint of worst-case packet delay and burstiness when the sources are constrained by leaky buckets. The worst-case session backlogs are also determined.>

The authors analyze the expected delay for infinite precision arithmetic codes and suggest a practical implementation that concentrates on the issue of delay.>

The problem of allocating network resources to the users of an integrated services network is investigated in the context of rate based flow control. The authors propose the use of a packet service discipline at the nodes of the network that is based on a multiplex scheme called generalized processor sharing (GPS). This service discipline is combined with leaky bucket rate admission control to provide flexible, efficient and fair use of the links. A single server GPS system is analyzed exactly, and tight bounds on worst case packet delay, output burstiness and backlog are derived for each session, when the sources are constrained by leaky buckets. The analysis yields a simple resource assignment scheme that allows the server to make worst case delay and rate guarantees to every session in the system. Extensions of this work to arbitrary topology networks are also discussed.>

An algorithm is presented that allows each node in a computer network to maintain a correct view of the network topology despite link and node failures. Reliability is achieved without transmitting any information other than the operational status of links. Messages are only sent in response to topological changes: periodic retransmission is not required.>

A broadcast network of N+1 nodes is considered in which each binary digit transmitted by each node is received by every other node via a binary symmetric channel of given transition probability. The errors on these channels are independent over transmitters, receivers and time. Each node has a binary state, and the problem is to construct a distributed algorithm to find the parity of the set of states with some given reliability. It is shown that this can be done with O(ln(lnN)) bits of communication from each node. Communicating all the node states to one node can be accomplished with only marginally more communication.>

A new distributed algorithm is presented for constructing breadth first search (BFS) trees. A BFS tree is a tree of shortest paths from a given root node to all other nodes of a network under the assumption of unit edge weights; such trees provide useful building blocks for a number of routing and control functions in communication networks. The order of communication complexity for the new algorithm isO(V^{1.6} + E)whereVis the number of nodes and E the number of edges. For dense networks withE \geq V^{1.6}this order of complexity is optimum.

This paper develops a new distributed BFS algorithm for an asynchronous communication network. This paper presents two new BFS algorithms with improved communication complexity. The first algorithm has complexity O((E+V1.5)·logV) in communication and O(V1.5·logV) in time. The second algorithm uses the technique of the first recursively and achieves O(E·2 √logVloglogV) in communication and O(V·2√logVloglogV) in time.

The information theoretic approach and the collision resolution approach to multiaccess channels are reviewed in terms of the underlying communication problems that both are modeling. Some perspective on the strengths and weakness of these approaches is given, and the need of a more combined approach focused on coding and decoding techniques is argued.

This paper attempts to present a comprehensive tutorial survey of the development of efficient modulation techniques for bandlimited channels, such as telephone channels. After a history of advances in commercial high-speed modems and a discussion of theoretical limits, it reviews efforts to optimize two-dimensional signal constellations and presents further elaborations of uncoded modulation. Its principal emphasis, however, is on coded modulation techniques, in which there is an explosion of current interest, both for research and for practical application. Both block-coded and trellis-coded modulation are covered, in a common framework. A few new techniques are presented.

We propose a class of algorithms for finding an optimal quasi-static routing in a communication network. The algorithms are based on Gallager's method [1] and provide methods for iteratively updating the routing table entries of each node in a manner that guarantees convergence to a minimum delay routing. Their main feature is that they utilize second derivatives of the objective function and may be viewed as approximations to a constrained version of Newton's method. The use of second derivatives results in improved speed of convergence and automatic stepsize scaling with respect to level of traffic input. These advantages are of crucial importance for the practical implementation of the algorithm using distributed computation in an environment where input traffic statistics gradually change.

A distributed algorithm is presented that constructs the minimum-weight spanning tree in a connected undirected graph with distinct edge weights.A processor exists at each node of the graph, knowing initially only the weights of the adjacent edges.The processors obey the same algorithm and exchange messages with neighbors until the tree is constructed.The total number of messages required for a graph of N nodes and E edges is at most 5N log2N + 2E, and a message contains at most one edge weight plus log28N bits.The algorithm can be initiated spontaneously at any node or at any subset of nodes.

Two familiar techniques for encoding message lengths are considered. One technique breaks messages into packets, with each but the last message packet having the same length. The message length is encoded by specifying the last packet and its length. The other technique uses a special bit sequence called a flag to terminate the message and slightly re-encodes the message to prevent the flag from appearing within the message. For a geometric message length distribution and for properly chosen parameters, it is shown that the packet strategy is optimal in the Huffman coding sense and that the flag strategy is very close to optimal. Moreover, for a given expected message length the expected codeword lengths are quite insensitive to the message length distribution.

In honor of the twenty-fifth anniversary of Huffman coding, four new results about Huffman codes are presented. The first result shows that a binary prefix condition code is a Huffman code iff the intermediate and terminal nodes in the code tree can be listed by nonincreasing probability so that each node in the list is adjacent to its sibling. The second result upper bounds the redundancy (expected length minus entropy) of a binary Huffman code byP_{1}+ \log_{2}[2(\log_{2}e)/e]=P_{1}+0.086, whereP_{1}is the probability of the most likely source letter. The third result shows that one can always leave a codeword of length two unused and still have a redundancy of at most one. The fourth result is a simple algorithm for adapting a Huffman code to slowly varying esthnates of the source probabilities. In essence, one maintains a running count of uses of each node in the code tree and lists the nodes in order of these counts. Whenever the occurrence of a message increases a node count above the count of the next node in the list, the nodes, with their attached subtrees, are interchanged.

An algorithm is defined for establishing routing tables in the individual nodes of a data network. The routing table at a nodeispecifies, for each other nodej, what fraction of the traffic destined for nodejshould leave nodeion each of the links emanating from nodei. The algorithm is applied independently at each node and successively updates the routing table at that node based on information communicated between adjacent nodes about the marginal delay to each destination. For stationary input traffic statistics, the average delay per message through the network converges, with successive updates of the routing tables, to the minimum average delay over all routing assignments. The algorithm has the additional property that the traffic to each destination is guaranteed to be loop free at each iteration of the algorithm. In addition, a new global convergence theorem for noncontinuous iteration algorithms is developed.

We consider basic limitations on the amount of protocol information that must be transmitted in a data communication network to keep track of source and receiver addresses and of the starting and stopping of messages. Assuming Poisson message arrivals between each communicating source-receiver pair, we find a lower bound on the required protocol information per message. This lower bound is the sum of two terms, one for the message length information, which depends only on the distribution of message lengths, and the other for the message start information, which depends only on the product of the source-receiver pair arrival rate and the expected delay for transmitting the message. Two strategies are developed which, in the limit of large numbers of sources and receivers, almost meet the lower bound on protocol information.

LetP(i)= (1 - \theta)\theta^ibe a probability assignment on the set of nonnegative integers where\thetais an arbitrary real number,0 < \theta < 1. We show that an optimal binary source code for this probability assignment is constructed as follows. Letlbe the integer satisfying\theta^l + \theta^{l+1} \leq 1 < \theta^l + \theta^{l-1}and represent each nonnegative integeriasi = lj + rwhenj = \lfloor i/l \rfloor, the integer part ofi/l, andr = [i] mod l. Encodejby a unary code (i.e.,jzeros followed by a single one), and encoderby a Huffman code, using codewords of length\lfloor \log_2 l \rfloor, forr < 2^{\lfloor \log l+1 \rfloor} - l, and length\lfloor \log_2 l \rfloor + 1otherwise. An optimal code for the nonnegative integers is the concatenation of those two codes.

A simple algorithm is developed for mapping the outputs of a source into the set of code sequences generated by a tree code. The algorithm is analyzed for a special case in which the source produces discrete independent equiprobable letters, and the distortion measure satisfies a symmetry condition. LettingRbe the code rate andD^{\ast}be the minimum average distortion for that rate as given by Shannon's rate-distortion theorem, we show that the algorithm is capable of achieving average distortion as close toD^{\ast}as desired. Furthermore an upper bound is developed on the average amount of computation for the algorithm. Asymptotically as the average distortion approaches the theoretical limitD^{\ast}, the bound on average computation has the form\exp [a/ \sqrt{ - D^{\ast} }]for some constanta.

The random coding bound of information theory provides a well-known upper bound to the probability of decoding error for the best code of a given rate and block length. The bound is constructed by upper-bounding the average error probability over an ensemble of codes. The bound is known to give the correct exponential dependence of error probability on block length for transmission rates above the critical rate, but it gives an incorrect exponential dependence at rates below a second lower critical rate. Here we derive an asymptotic expression for the average error probability over the ensemble of codes used in the random coding bound. The result shows that the weakness of the random coding bound at rates below the second critical rate is due not to upperbounding the ensemble average, but rather to the fact that the best codes are much better than the average at low rates.

An upper bound is calculated for the probability that a mean-zero Gaussian random process remains above a specified signal throughout a prescribed interval of time.

Upper bounds are derived on the probability of error that can be achieved by using block codes on general time-discrete memoryless channels. Both amplitude-discrete and amplitude-continuous channels are treated, both with and without input constraints. The major advantages of the present approach are the simplicity of the derivations and the relative simplicity of the results; on the other hand, the exponential behavior of the bounds with block length is the best known for all transmission rates between0and capacity. The results are applied to a number of special channels, including the binary symmetric channel and the additive Gaussian noise channel.

A low-density parity-check code is a code specified by a parity-check matrix with the following properties: each column contains a small fixed numberj \geq 3of l's and each row contains a small fixed numberk > jof l's. The typical minimum distance of these codes increases linearly with block length for a fixed rate and fixedj. When used with maximum likelihood decoding on a sufficiently quiet binary-input symmetric channel, the typical probability of decoding error decreases exponentially with block length for a fixed rate and fixedj. A simple but nonoptimum decoding scheme operating directly from the channel a posteriori probabilities is described. Both the equipment complexity and the data-handling capacity in bits per second of this decoder increase approximately linearly with block length. Forj > 3and a sufficiently low rate, the probability of error using this decoder on a binary symmetric channel is shown to decrease at least exponentially with a root of the block length. Some experimental results show that the actual probability of decoding error is much smaller than this theoretical bound.