Search

This paper considers the problem of selecting a subset of nodes in a two-hop wireless network to act as relays in aiding the communication between the source-destination pair. Optimal relay subset selection with the objective of maximizing the overall throughput is a difficult problem that depends on multiple factors, including node locations, queue lengths, and power consumption. A partial decode-and-forward strategy is applied in this paper to improve the tractability of the relay selection problem and the performance of the overall network. Note that the number of relays that are selected ultimately determines the performance of the network. This paper benchmarks this performance by determining the net diversity that is achieved using the relays that are selected and the partial decode-and-forward strategy. This framework is subsequently used to further transform relay selection into a simpler relay placement problem, and two proximity-based approximation algorithms are developed to determine the appropriate set of relays to be selected in the network. Other selection strategies, such as random relay selection and a greedy algorithm that relies on channel state information, are also presented. This paper concludes by showing that the proposed proximity-based relay selection strategies yield near-optimal expected rates for a small number of selected relays. Index Terms--Greedy algorithms, partial decode-and-forward, relays, superposition coding.

A recently proposed space-time block-coding (STBC) signal construction method that combines orthogonal design with sphere packing (SP) (referred to here as STBC-SP) has shown useful performance improvements over Alamouti's conventional orthogonal design. In this paper, we propose a purely symbol-based, low-density parity-check (LDPC)-coded scheme, demonstrating that the performance of STBC-SP systems can further be improved by concatenating SP-aided modulation with nonbinary LDPC and by performing symbol-based turbo detection between the nonbinary LDPC decoder and a rate-1 nonbinary inner precoder. We also investigate the convergence behavior of this symbol-based concatenated scheme with the aid of novel nonbinary extrinsic information transfer (EXIT) charts. Finally, we demonstrate that in the investigated scenarios, it requires 1-2 dB lower power in comparison with the equivalent effective-throughput 0.5-, 0.75-, and 1-bit/symbol systems employing bit-based turbo detection. Index Terms--Nonbinary low-density parity check (LDPC), space-time codes, sphere packing (SP), symbol-based extrinsic information transfer (EXIT) chart, turbo detection.

Distributed space-time coding is a cooperative transmission scheme for wireless relay networks. With this scheme, antennas of the distributive relays work as transmit antennas of the sender and generate a space-time code at the receiver. It achieves the maximum diversity. Although the scheme needs no channel information at relays, it does require full channel information, both the channels from the transmitter to relays and the channels from relays to the receiver, at the receiver. In this paper, we propose a differential transmission scheme, which requires channel information at neither relays nor the receiver, for wireless relay networks. As distributed space-time coding can be seen as the counterpart of space-time coding in the network setting, this scheme is the counterpart of differential space-time coding. Compared to coherent distributed space-time coding, the differential scheme is 3dB worse. In addition, we show that Alamouti, square real orthogonal, and Sp(2) codes can be used differentially in networks with corresponding numbers of relays. We also propose distributed differential space-time codes that work for networks with any number of relays using circulant matrices. Index Terms--Wireless relay networks, cooperative diversity, differential transmission, space-time block coding.

In this paper, we consider the communication problem that involves transmission of correlated sources over broadcast channels. We consider a graph-based framework for this information transmission problem. The system involves a source coding module and a channel coding module. In the source coding module, the sources are efficiently mapped into a nearly semi-regular bipartite graph, and in the channel coding module, the edges of this graph are reliably transmitted over a broadcast channel. We consider nearly semi-regular bipartite graphs as discrete interface between source coding and channel coding in this multiterminal setting. We provide an information-theoretic characterization of 1) the rate of exponential growth (as a function of the number of channel uses) of the size of the bipartite graphs whose edges can be reliably transmitted over a broadcast channel and 2) the rate of exponential growth (as a function of the number of source samples) of the size of the bipartite graphs which can reliably represent a pair of correlated sources to be transmitted over a broadcast channel. Index Terms--Broadcast channels, discrete interface, Gray-Wyner source coding, random graphs.

In 1995, the IEEE approved the 802.12 standard for data transmission at 100-Mbit/s using the Demand Priority Network Access protocol. 100VG-AnyLAN products conforming to this standard offered an upgrade path for Ethernet and Token Ring networks, without requiring new building wiring. A key factor in the approval of the 802.12 standard was the demonstrated error detection properties of its coding scheme. In particular, the coding scheme allows the detection of error bursts affecting encoded data carried on four parallel conductors, using nothing more than the standard IEEE 32-bit cyclic redundancy check applied to the unencoded data. Although these error detection properties were presented for verification as part of the standards process, for many years commercial considerations prevented public disclosure of how the code was actually found. These considerations no longer apply, and, in this paper, we explain in detail the design principles of the code, combining geometrical insight, linear algebra, combinatorial reasoning, and computer search. Index Terms--Cyclic redundancy check, error detection, IEEE 802.12, polynomial, 100VG-AnyLAN.

An overview of the many practical applications of channel coding theory in the past 50 years is presented. The following application areas are included: deep space communication, satellite communication, data transmission, data storage, mobile communication, file transfer, and digital audio/video transmission. Examples, both historical and current, are given that typify the different approaches used in each application area. Although no attempt is made to be comprehensive in our coverage, the examples chosen clearly illustrate the richness, variety, and importance of error-control coding methods in modern digital applications. Index Terms - Block codes, channel coding, convolutional codes, error-control coding.

The key ideas in the theory of broadcast channels are illustrated by discussing some of the progress toward finding the capacity region. The capacity region is still unknown. Index Terms - Binning, broadcast channel, capacity, degraded broadcast channel, feedback capacity, Slepian-Wolf, superposition.

Shannon's determination of the capacity of the linear Gaussian channel has posed a magnificent challenge to succeeding generations of researchers. This paper surveys how this challenge has been met during the past half century. Orthogonal minimum-bandwidth modulation techniques and channel capacity are discussed. Binary coding techniques for low-signal-to-noise ratio (SNR) channels and nonbinary coding techniques for high-SNR channels are reviewed. Recent developments, which now allow capacity to be approached on any linear Gaussian channel, are surveyed. These new capacity-approaching techniques include turbo coding and decoding, multilevel coding, and combined coding/precoding for intersymbol-interference channels. Index Terms - Binary coding, block codes, canonical channel, capacity, coding gain, convolutional codes, lattice codes, multicarrier modulation, nonbinary coding, orthogonal modulation, precoding, shaping gain, single-carrier modulation, trellis codes.

This paper presents a method for evaluating the bit-error probability of a concatenated coding system for BPSK transmission over the AWGN channel. In the concatenated system, a linear binary block code is used as the inner code and is decoded with the soft-decision maximum likelihood decoding, and a maximum distance separable code (or its interleaved code) is used as the outer code and is decoded with a bounded distance decoding. The method is illustrated through a specific example in which the inner code is a binary (64.40. 8) Reed-Muller subcode and the outer code is the NASA standard (255.223.33) Reed-Solomon code over GF([2.sup.8]) interleaved to a depth of 5. This specific concatenated system is being considered for NASA's high-speed satellite communications. The bit-error performance is evaluated by a combination of simulation and analysis. The split weight enumerators for the maximum distance separable codes are derived and used for the analysis.

A coding-decoding strategy for the noiseless T-user q-ary multiple-access channel is presented where no cooperation between the users is needed, neither in the code construction nor in the decoding process. Statistics for the received symbols as a function of q and T are given, and the cutoff rate for the channel is defined and evaluated. Finally, computer simulations are presented to support the results found. Index Terms - Multiuser detection, multiple-access, noiseless channel, cutoff rate, block coding.

New analytical upper bounds are derived for the performance of symbol-by-symbol maximum-likelihood (ML) Abend-Fritchman-type detectors for multi-amplitude/phase-modulated digital sequences transmitted over time-dispersive (generally) time-variant linear channels introducing finite Intersymbol Interference (ISI) and additive white Gaussian noise (AWGN). The proposed bounds are obtained starting from a novel form of the standard Bhattacharyya bound and take explicitly into account the allowed decoding delay. Both deterministic and random multipath slow-fading Rayleigh transmission ISI channels are considered. Simulation results obtained for some test channels of practical interest show the tightness of the derived analytical bounds. Index Terms - Symbol-by-symbol detection, Bhattacharyya-like bound, time-dispersive channels, multipath random channels, Forney's bound, Abend-Fritchman detection algorithm.

Optimal scalar quantizer design for transmission over a finite-state channel is considered. The objective is to minimize the mean-squared error when the channel is in the normal mode of operation, while guaranteeing a minimum fidelity when the channel is in the "bad" state. An optimal quantizer design algorithm for the general case where noisy state information is available both at the receiver and at the transmitter is derived. It is shown that using mixed strategies is necessary in order to achieve the optimal performance. Finally, the case where the observation is noisy is considered and it is shown that the optimal scheme in this case is to apply the algorithm for the "no observation noise" to the mean-squared estimate of the desired random variable from the noisy data. Index Terms - Finite-state channels, quantization, joint source-channel coding, data compression.

We charactrize and investigate the highest achievable exponential growth rate of the expected number of rate-distortion codewords that are within a certain distance from a given source vector. Index Terms - Rate-distortion theory, D-semifaithful codes, memory-less sources, list size exponents.

Let the input to a computation problem be split between two processors connected by a communication link; and let an interactive protocol [Pi] be known by which, on any input, the processors can solve the problem using no more than T transmissions of bits between them, provided the channel is noiseless in each direction. We study the following question: If in fact the channel is noisy, what is the effect upon the number of transmissions needed in order to solve the computation problem reliably? Technologically this concern is motivated by the increasing importance of communication as a resource in computing, and by the tradeoff in communications equipment between bandwidth, reliability, and expense. We treat a model with random channel noise. We describe a deterministic method for simulating noiseless-channel protocols on noisy channels, with only a constant slowdown. This is an analog for general interactive protocols of Shannon's coding theorem, which deals only with data transmission, i.e., one-way protocols. We cannot use Shannon's block coding method because the bits exchanged in the protocol are determined only one at a time, dynamically, in the course of the interaction. Instead, we describe a simulation protocol using a new kind of code, explicit tree codes. Index Terms - Interactive communication, coding theorem, tree code, distributed computing, reliable communication, error correction.

We introduce a new method, called Priority Encoding Transmission, for sending messages over lossy packet-based networks. When a message is to be transmitted, the user specifies a priority value for each part of the message. Based on the priorities, the system encodes the message into packets for transmission and sends them to (possibly multiple) receivers. The priority value of each part of the message determines the fraction of encoding packets sufficient to recover that part. Thus even if some of the encoding packets are lost en-route, each receiver is still able to recover the parts of the message for which a sufficient fraction of the encoding packets are received. For any set of priorities for a message, we define a natural quantity called the girth of the priorities. We develop systems for implementing any given set of priorities such that the total length of the encoding packets is equal to the girth. On the other hand, we give an information-theoretic lower bound that shows that for any set of priorities the total length of the encoding packets must be at least the girth. Thus the system we introduce is optimal in terms of the total encoding length. This work has immediate applications to multimedia and high-speed networks applications, especially in those with bursty sources and multiple receivers with heterogeneous capabilities. Implementations of the system show promise of being practical. Index Terms - Prioritized data, erasure-resilient codes, MDS codes, lossy packet networks, bursty losses, real-time transmission, multimedia applications, video, audio, Reed-Solomon codes, redundancy encoding, information-theoretic lower bounds.

In this paper, we show how coding and constellation shaping may provide significant gains to a discrete multi-tone (DMT) system transmitting over spectrally-shaped channels. First, we present and analyze a concatenated coding scheme consisting of an inner trellis code and outer block code when applied to DMT modulation, and we address some of the implementation issues associated with this scheme. Some laboratory test results for a DMT prototype employing the coding scheme are presented. Next, we propose a method for applying Forney's trellis shaper across the tones in a DMT system to realize significant shaping gain. To illustrate the coding and shaping gains achieved, we use scenarios indicative of the newly introduced asymmetric digital subscriber line service. By combining a powerful coding scheme, shaping, and DMT modulation, we arrive at an implementable transceiver that can provide very high data rates over spectrally-shaped channels.

We consider a direct-sequence spread-spectrum multiple access communication system with convolutional coding and hard decision decoding. We calculate the packet error probability and throughput of this system. Previous bounds on packet error probability have relied on the worst case assumption of phase and chip synchronous interference. We present new bounds on packet error probability and throughput for the case of both slotted and unslotted systems. These new bounding techniques are based on two advances: an improved Chernoff bound on the error event probability of a convolutional code, and the use of moment space techniques. Numerical results indicate that these new bounds on packet error probability improve on previously reported bounds by more than an order of magnitude. We also examine the problem of choosing the optimum code rate which maximizes throughput. We compare the optimum code rate which results from the bounding technique to the optimum code rate derived from an approximation technique. Although the bounding technique and approximation technique yield very different results for throughput, the resulting choice of optimum code rate is similar.

Multiple description source coding concerns situations in which the transmission of the source information is distributed over two data streams at rates [R.sub.1] and [R.sub.2], respectively. When both data streams are received, the decoder uses the combined data at rate [R.sub.1] + [R.sub.2] to reconstruct the source information with average distortion [d.sub.0]. If a communication breakdown prevents one of the data streams from reaching the receiver, the decoder has to base its reconstruction solely on the available data at rate either [R.sub.1] + [R.sub.2]. This results in a higher distortion of either [d.sub.1] or [d.sub.2], respectively. The region R of all achievable quintuples ([R.sub.1], [R.sub.2], [d.sub.0], [d.sub.1], [d.sub.2]) has been determined in the so-called 'no excess rate' sum case defined by imposing the requirement [R.sub.1] + [R.sub.2] = R([d.sub.0]), where R([center dot]) is the rate-distortion function of the source. The case with excess rate sum, characterized by [R.sub.1] + [R.sub.2] > R([d.sub.0]), is challenging. We study in this paper a special case of it in which the requirements [R.sub.t] = R([d.sub.t]), t = 1, 2, are imposed; we refer to this as the 'no excess marginal rate' case. The lower and upper bounds on [d.sub.0] we obtain are separated by only a tiny gap when evaluated for a binary equiprobable source and the Hamming distortion measure. Index Terms - Multiple description; source coding; excess rate; rate-distortion.

In a Diversity Coding System, an information source is encoded by a number of encoders. There are a number of decoders, each of which can access a certain subset of the encoders. In this paper, we study a diversity coding problem in which there are two levels of decoders. The reconstructions of the source by decoders within the same level are identical, and are subject to the same distortion criterion. Our results imply a principle of superposition when the source consists of two independent data streams. Practical codes achieving zero error can easily be constructed for this special case. A class of open problems on this topic is also suggested. Index Terms - Multiterminal source coding, diversity coding, fault tolerance, principle of superposition.

The error correcting capability of the Unequal Error Protecting (UEP) Codes is described in terms of correcting errors in specific digits of a codeword even though other digits may be decoded incorrectly. We investigate the overall distortion when these codes are applied to transmission of analog sources in a communication system. Simulation and analytic results indicate the performance improvement gained by using UEP codes for various sources and source encoding structures.

Nested concatenated coded 8-PSK modulation schemes are proposed to achieve good error performance, large coding gains, and high spectral efficiency with reduced decoding complexity. In the proposed schemes, Reed-Solomon (RS) codes, including the NASA standard (255, 223) RS code, are used as the outer codes and multi-dimensional trellis 8-PSK codes are used as the inner codes. The inner codes are constructed from convolutional codes with good free branch distances and multidimensional 8-PSK coset codes through concatenation. These schemes are analyzed and upper bounds on their error performances are derived. Analytical and simulation results show that these schemes achieve large coding gains over uncoded reference systems for bit-error-rates below [10.sup.-3], with reduced decoding complexity. Keywords - Trellis coded modulation, Concatenation and Multi-stage decoding

The performance of a Reed-Solomon coded binary communication system on a bursty-noise channel is considered. Bursty noise is defined to be background Gaussian noise plus burst noise, where burst noise is defined to be a series of finite-duration Gaussian-noise pulses with fixed duration and Poisson occurrence times. Using the noise model, along with ideal symbol interleaving, decoded bit-error probability hounds are derived for the case where the noise bursts are long with respect to the channel symbol rate. Specific performance results are presented for the (31, 15, 8) Reed-Solomon Joint Tactical Distribution System (JTIDS) code with a Binary Phase Shift Keyed (BPSK) modulation scheme. Simulation results are presented and they compare well with the theoretical results.

Soft-decision maximum-likelihood decoding of convolutional codes using the Viterbi algorithm with a syndrome trellis is proposed. The parity check matrix of a convolutional code is used to construct the trellis. This trellis is minimal. The number of operations for the decoding of one block of a q-ary rate k/n convolutional code is [is similar to] [nq.sup.min(k, n - k)] [q.sup.v], where v is the memory size of the code. When the code rate satisfies k / n > 1/2, the proposed algorithm is simpler than the classical Viterbi algorithm that has complexity [is similar to] [nq.sup.k] [q.sup.v]. Index Terms - Convolutional codes, maximum-likelihood decoding, trellis decoding, complexity estimation.

A general algebraic method for decoding all types of binary cyclic codes is presented. It is shown that such a method can correct t = [(d - 1) / 2] errors, where d is the true minimum distance of the given cyclic code. The key idea behind this decoding technique is a systematic application of the algorithmic procedures of Grobner bases to obtain the error-locator polynomial L(z). The discussion begins from a set of syndrome polynomials F and the ideal I(F) generated by F. It is proved here that the process of transforming F to the normalized reduced Grobner basis of I(F) with respect to the 'purely lexicographical' ordering automatically converges to L(z). Furthermore, it is shown that L(z) can be derived from any normalized Grobner basis of I(F) with respect to any admissible total ordering. To illustrate this new decoding method, examples are given. Index Terms - Coding theory, cyclic codes, decoding, ideal theory, Grobner bases.

Consider the transmission of a finitely interleaved rate 1 / n convolutionally encoded message over a channel with memory having two internal states [[Xi].sub.0] and [[Xi].sub.1], where when in state [[Xi].sub.0], the channel resembles a noiseless binary symmetric channel (BSC), whereas when in state [[Xi].sub.1], the channel is totally blocked and is well approximated by a binary-input single-output channel. Assume that the channel's internal state is drawn at random once every h channel uses, and then remains constant for the following h channel uses. Further assume that the message is short in comparison to h, and that due to delay constraints, the message must be decoded within Nh channel uses, where N need not be large in comparison to the code's constraint length. Such a model is appropriate for describing a convolutionally coded slow frequency hopping system with non-ideal interleaving, in which every frequency is either totally erased or else noiseless. The probability of a message error, the normalized expected number of bits in error, and the bit error rate (BER) are analytically computed for the periodic N x h bit and word interleavers, where a bit refers to a binary code symbol, and a word refers to a n-tuple of consecutive bits. An analytic expression for the BER is also given for pseudo-random word and bit interleavers and for the corresponding limiting cases of infinite interleaving, i.e., N [right arrow] [infinity]. As an example for the use of our methods, we analyze the performance of the GSM system with various interleaving depths and methods. We introduce the notion of 'matched' code and interleaver pairs, and argue that this is a desirable property. Several exhaustive searches are carried out for matched codes and interleavers. Index Terms - Convolutional codes, Viterbi decoding, erasure channel, finite interleaving, periodic interleaving, random interleaving, MDS codes, frequency hopping, GSM.

In the usual ARQ (Automatic-Repeat-Request) communication protocols, when the receiver detects the presence of errors in a received message, it requests the retransmission of another copy of the message, and the process continues until an uncorrupted copy reaches the destination. If the quality of the channel is poor, the number of retransmissions may become very large. In order to improve the efficiency at large channel error rates, some new techniques known as Type-II Hybrid ARQ Schemes have recently been proposed. In these techniques the transmitter does not retransmit the message encoded as in the first transmission: it sends instead additional redundancy that is decoded at the destination along with the previously received information to allow error correction. In this paper a new kind of Type-II Hybrid ARQ transmission scheme is proposed. The copies of the message are encoded in different ways, so that each copy has the same information content, and the knowledge of any subset of the copies allows error correction. This transmission scheme is well suited to broadcast as well as for point to point communications. We have obtained trough computer search a family of optimum and quasi-optimum codes for the proposed transmission scheme. They are described along with new decoding techniques of remarkable simplicity and effectiveness. These codes allow a message to be encoded in up to three different ways, and they are shown to be simple to encode and decode and to perform well over channels affected by error bursts.

This paper presents an adaptive error control technique based on the use of type-I hybrid-ARQ protocols. The communication channel is assumed to be slowly varying and is modeled using a finite state Markov chain. The system counts the number of retransmission requests during an observation interval called a frame and, together with knowledge of the error control strategy in use and a set of thresholds, estimates the state of the channel. The coding strategy which maximizes throughput while maintaining a minimum required level of reliability is chosen for use in the next frame. Examples are provided showing system design and performance using families of Reed-Solomon codes.

Encoding and decoding schemes for concatenated multilevel block codes are presented. By one of these structures, a real coding gain of 5.6-7.4 dB for the bit error range of 10 to the -6 - 10 to the -9 is achieved for transmission through the additive white Gaussian noise channel. Also, a rather large asymptotic coding gain is obtained. The new coding schemes have very low decoding complexity and increased coding gain in comparison with the conventional block and trellis coded modulation structures. A few design rules for concatenated (single and) multilevel block codes with large coding gain are also provided.

By taking a particular look at the generalized Type-II hybrid ARQ scheme on Markov channels, this work investigates the effect of feedback channel errors on the performance of ARQ systems. In the analysis of ARQ methods, it is quite often assumed that the feedback channel is error-free. However, taking into account the feedback channel errors provides a more realistic evaluation of the performance. The main contribution of this work is that it demonstrates that it is indeed possible to derive expressions for certain critical performance parameters, such as the throughput efficiency, the probabilities of packet loss, undetected error, and correct delivery. To provide a means of comparison, the paper provides, in the Appendix, a parallel set of expressions under the usual assumption of an error-free feedback channel. By use of simulations, the ARQ system performance is examined under the two cases - noiseless feedback and noisy feedback. It is found that feedback channel noise can result in the loss of packets, an increase in the number of undetected errors, and the occurrence of unnecessary transmissions. To enhance the performance of the GH-II ARQ scheme, a predictor is used and found to provide remarkable performance improvement - lowering the probability of undetected error, reducing the number of unnecessary transmissions, and increasing the throughput efficiency. The results presented are felt to be important for system design employing ARQ error control methods.

High-rate lattice and trellis quantizers for nonuniform sources are introduced and analyzed. The performance of these quantizers is determined by two separable quantities, the granular gain and the boundary gain, which are determined by the shapes of the granular cells and of the support region, respectively. The granular gain and boundary gain are the duals of shaping and coding gain in data transmission applications. Using this duality, it is shown for Gaussian sources that the ultimate achievable boundary gain with high-rate lattice-bounded lattice codebooks is the same as the ultimate gain that can be obtained from variable-rate entropy coding. It is observed that if lattice codebooks can achieve the ultimate granular gain of 0.255 bit per dimension, then lattice-bounded lattice codebooks can achieve the ultimate granular gain of 0.255 bit per dimension, then lattice-bounded lattice codebooks can approach the rate-distortion limit. Finally, the performance of lattice quantizers is compared to that of optimum vector quantizers.

The identification coding theorems of Ahlswede and Dueck have shown that for any nonzero probabilities of missed and false identification, it is possible to transmit exp(exp(nR))) messages with n uses of a noisy channel, where R is as close as desired to the Shannon capacity of the channel. That capability is achieved by the identification codes explicitly constructed with a three-layer concatenated constant-weight code used in conjunction with a channel transmission code of rate R.

The constraints put on the variable transmission rate and the encodingrate of a compressed video signal by encoder and decoder buffers are studied. Such problems arise in asynchronous transfer mode networks where the channel also plays a role putting restrictions on the bit rates. Conditions which satisfy the constraints and which guarantee the non-overflow or non-underflow of the buffers are derived. A bit rate control system is also presented and applied through simulations to the leaky bucket channel problem.

We propose a new algorithm for carrier frequency estimation in burst-mode phase shift keying (PSK) transmissions. The algorithm is data-aided and dock-aided and has a feedforward structure that is easy to implement in digital form. Its estimation range is large, about [+ or -]20% of the symbol rate and its accuracy is close to the Cramer-Rao bound (CRB) for a signal-to-noise ratio (SNR) as low as 0 dB. Comparisons with earlier methods are discussed.

At every hop in a conventional frequency-hopped spread spectrum multiple-access (FH-SSMA) system, each transmitter sends its data using a single frequency bin. In this paper, a scheme in which several frequency bins are simultaneously used by a transmitter is studied. It is found that such a code diversity scheme can yield a significant reduction in symbol error rate over that of a conventional FH-SSMA system. A priority system can also be implemented by assigning different diversity degrees to the transmitters.

A modified version of the Orwell protocol is presented. While the presented method preserves all the basic features, it introduces the concept of the SURPLUS cell. These surplus cells enhance the performance of the network for class-2 traffic as well as those of the enhancement data in two-layer ceded video by reducing the queuing delays. It is shown that the new method improves delay characteristics of the real-time services under mid-to-high traffic loads.

This paper provides two theorems for decoding all types of cyclic codes. It is shown that from a polynomial ideal point of view, the decoding problems of cyclic codes are closely related to the monic generators of certain polynomial ideals. This conclusion is also generalized to the decoding problems of algebraic geometry codes. Index Terms - Coding theory, cyclic codes, decoding, ideal theory.