Search

The paper presents techniques for analyzing the expected download time in distributed storage systems that employ systematic availability codes. These codes provide access to hot data through the systematic server containing the object and multiple recovery groups. When a request for an object is received, it can be replicated (forked) to the systematic server and all recovery groups. We first consider the low-traffic regime and present the close-form expression for the download time. By comparison across systems with availability, maximum distance separable (MDS), and replication codes, we demonstrate that availability codes can reduce download time in some settings but are not always optimal. In the high-traffic regime, the system consists of multiple inter-dependent Fork-Join queues, making exact analysis intractable. Accordingly, we present upper and lower bounds on the download time, and an M/G/1 queue approximation for several cases of interest. Via extensive numerical simulations, we evaluate our bounds and demonstrate that the M/G/1 queue approximation has a high degree of accuracy., Comment: Accepted for a publication in IEEE Transactions on Communications

In this paper, we provide an analysis of the performance of concatenation of polar codes with outer cyclic redundancy check (CRC) codes, separated by an interleaver, in the short and moderate block length regimes. The analysis addresses maximum likelihood decoding as a proxy to the code performance under successive cancellation list decoding. The analysis is carried out by introducing the concatenated polar code (CPC) ensembles, whose distance properties can be analyzed (for sufficiently short block lengths) by means of the uniform interleaver approach. At moderate block lengths, we resort to the Monte Carlo simulations. Results show that if the inner polar code possesses a low minimum distance and the outer CRC code has a sufficiently large amount of redundancy, then the choice of the outer code generator polynomial and the interleaver may yield to a large variability in the performance of the resulting CPC.

This paper focuses on the design and evaluation of pragmatic schemes for delay-sensitive communication. Specifically, this contribution studies the operation of data links that employ incremental redundancy as a means to shield information bits from the degradation associated with unreliable channels. While this inquiry puts forth a general methodology, exposition centers around erasure channels because they are well suited for analysis. Nevertheless, the goal is to identify both structural properties and design guidelines that are broadly applicable. Conceptually, this paper leverages a methodology, termed sequential differential optimization, aimed at identifying near-optimal block sizes for hybrid ARQ. This technique is applied to erasure channels and it is extended to scenarios where throughput is maximized subject to a constraint on the feedback rate. The analysis shows that the impact of the coding strategy adopted and the propensity of the channel to erase symbols naturally decouple when maximizing throughput. Ultimately, block size selection is informed by approximate distributions on the probability of decoding success at every stage of the incremental transmission process. This novel perspective, which rigorously bridges hybrid automatic repeat request and coding, offers a computationally efficient framework to select code rates and blocklengths for incremental redundancy. These findings are supported through numerical results.

This paper presents a general approach for optimizing the number of symbols in increments (packets of incremental redundancy) in a feedback communication system with a limited number of increments. This approach is based on a tight normal approximation on the rate for successful decoding. Applying this approach to a variety of feedback systems using nonbinary (NB) low-density parity-check (LDPC) codes shows that greater than 90% of capacity can be achieved with average blocklengths fewer than 500 transmitted bits. One result is that the performance with ten increments closely approaches the performance with an infinite number of increments. The paper focuses on binary-input additive-white Gaussian noise (BI-AWGN) channels but also demonstrates that the normal approximation works well on examples of fading channels as well as high-SNR AWGN channels that require larger QAM constellations. This paper explores both variable-length feedback codes with termination (VLFT) and the more practical variable length feedback (VLF) codes without termination that require no assumption of noiseless transmitter confirmation. For VLF, we consider both a two-phase scheme and CRC-based scheme.

A generalization of unequal error protection (UEP) rateless codes and distributed rateless codes for distributed relay networks is proposed. We consider a two-hop relaying network where a single source transmits UEP rateless coded data to a destination via multiple relays. At the relays, the UEP rateless coded symbols are re-encoded by distributed rateless codes (DRC) to minimize the redundancy at the second hop. Previously introduced UEP rateless codes (URC) have supported a limited number of importance classes, mostly two classes, and targeted importance levels suited to a specific application. In this paper, however, we formulate an optimization problem to provide optimal URC in terms of the symbol error rate (SER) given any specific number and strengths of importance levels. Next, another optimization is proposed to obtain DRC with the minimum SER at a given overhead, which utilizes information of common symbols among the relays. The optimization methods are based on the AND-OR tree analysis and sequential quadratic programming. In addition, we evaluate the minimum achievable end-to-end symbol error rates over the wireless relay networks.

This paper elaborates on the suboptimal greedy algorithm for target channel sequence selection as presented by Wang et al. in the paper, “Optimal Target Channel Sequence Design for Multiple Spectrum Handoffs in Cognitive Radio Networks,” IEEE Transactions on Communications , vol. 60, no. 9, pp. 2444–2455, September 2012. They claimed that the greedy algorithm requires comparing six target channel sequences. We prove that only five target channel sequences comparisons are sufficient. Hence, we present a modified algorithm and test it with a set of numerical results. It appears that the new algorithm reduces the processing time compared to the original one especially for a network with a large number of candidate channels.

Coherent detection is commonly facilitated by means of pilot-aided channel estimation. While this approach offers a high estimation accuracy, the spectral and power efficiencies are reduced due to the pilot overhead. In the case that redundancy due to channel coding is not used for the purpose of channel estimation, the maximum pilot spacing for which a time-varying channel can be reconstructed without distortion is given by the Nyquist-Shannon sampling theorem. In this paper, it is shown that if channel coding is taken into account for channel estimation in an iterative fashion, the maximum spacing can be significantly extended, which results in an increased spectral efficiency. Towards this goal, a so-called coded sampling bound is derived. This semi-analytical bound is compared with the Nyquist-Shannon sampling theorem. The presented results indicate that the maximum pilot spacing can be arbitrarily large given a suitable channel code and code rate.

This paper examines throughput performance, and its optimization, for lossless and truncated automatic repeat request (ARQ) schemes in Gaussian block fading channels. Specifically, ARQ, repetition redundancy, and in part also incremental redundancy-hybrid ARQ, are considered with various diversity schemes. We propose a parameterization-based method that allows (semi-)closed-form expressions, linking optimized throughput, optimal rate, and mean SNR, to be derived for any ARQ and repetition redundancy-HARQ method even when a non-parameterized closed-form does not exist. We derive numerous throughput and optimal throughput expressions for various ARQ schemes and diversity scenarios, potentially useful for benchmarking purposes or as design guidelines Refereed/Peer-reviewed

In this paper, we propose a novel scheme for the design of grouping of radio-frequency identification (RFID) tags, based on the Chinese remainder theorem (CRT). Grouping allows verifying the integrity of a collection of objects without the requirement for accessing external systems, and can be extended to identify missing objects. Motivated by the redundancy property of the Chinese remainder representation, we propose grouping of RFID tags via the CRT. The proposed scheme not only provides designated decoding guarantees, but also offers flexibility in constructing group generation matrices. We also characterize the key objects needed to study decoding guarantees of grouping and its extended counterpart, called rank-deficient and dead-end sets, respectively, which enable theoretical analyses of error rates. The two key objects are related to the minimum and stopping distances of a linear code, respectively. As such, the characterization offers direct connection with coding theory that helps in the understanding of the verification/identification problems being studied. Theoretical and simulation results are presented, demonstrating that the proposed scheme is an efficient approach to the design of grouping of RFID tags.

In this paper, we focus on capacity-delay tradeoffs for multicast traffic pattern. Under the assumption that n nodes move in a unit square according to an i.i.d. mobility model, with each serving as a source that sends identical packets to k destinations, we propose four schemes of which the achievable capacity λ and delay D are analyzed: (1) 2-hop noncooperative non-redundancy scheme, (2) 2-hop noncooperative redundancy scheme, (3) 2-hop cooperative non-redundancy scheme, (4) 2-hop cooperative redundancy scheme. Compared with non-cooperative scheme with capacity delay tradeoff λ = O( E[D]/nk log k) first developed in [5], cooperation among destination nodes achieves optimal capacity delay tradeoff λ = O(E[D]/n log k) in cell partitioned network. With intelligent cooperation, each destination acts equivalently as relay and helps other destinations get more opportunities of receiving packets with capacity sacrificed to a addition, our redundancy schemes also allow delay under Θ(√n) log k factor compared with unicast in [3] under the same delay. In achievable, which is the minimum delay under the schemes of [3],[5].

For a block-fading channel, this paper optimizes the allocation of redundancy between packet-level erasure coding (which provides additional packets to compensate for packet loss) and physical layer channel coding (which lowers the probability of packet loss). After some manipulation, standard optimization techniques determine the trade-off between the amount of packet-level erasure coding and physical-layer channel coding that minimizes the transmit power required to provide reliable communication. Our results indicate that the optimal combination of packet-level erasure coding and physical-layer coding provides a significant benefit over pure physical-layer coding when no form of channel diversity is present within a packet transmission. However, the benefit of including packet-level erasure coding diminishes as more diversity becomes available within a packet transmission. Even with no diversity within a packet transmission, this paper shows that as the total redundancy becomes large the optimal redundancy for packet-level erasure coding reaches a limit while the optimal redundancy for physical-layer coding continues to increase. Hence providing limitless redundancy at the packet-level with rateless codes such as fountain codes is not the best use of limitless redundancy for block-fading channels.

Channel-optimized quantizer index assignment and maximum a posteriori (MAP) decoding have been extensively studied for error-resilient communications. An interesting and largely untreated problem is how to optimize the index assignment with respect to joint source-channel MAP decoding. In this paper we formulate the above problem as one of quadratic assignment, and discuss its solutions from very general to some special cases. For highly correlated Gaussian Markov sources and Hamming distortion, we can construct the optimal index assignment analytically. For general cases, simulated annealing algorithm is adopted to search for the optimal index assignment. Experimental results are presented to demonstrate the performance improvement of the index assignments optimized for MAP decoding over those designed for hard-decision decoding (e.g. Gray code). The reduction of symbol error rate and mean squared error can be as large as 40% and 50% respectively for highly correlated Gaussian Markov sources.

Utilization of redundancy left in a channel coded sequence can improve channel decoding performance. Stronger improvement can usually be achieved with nonsystematic encoding. However, nonsystematic codes recently proposed for this problem are not robust to the statistical parameters governing a sequence and thus should not be used without prior knowledge of these parameters. In this work, decoders of nonsystematic quick-look-in turbo codes are adapted to extract and exploit redundancy left in coded data to improve channel decoding performance. Methods, based on universal compression and denoising, for extracting the governing statistical parameters for various source models are integrated into the channel decoder by also taking advantage of the code structure. Simulation results demonstrate significant performance gains over standard systematic codes that can be achieved with the new methods for a wide range of statistical models and governing parameters. In many cases, performance almost as good as that with perfect knowledge of the governing parameters is achievable.

All binary polynomials of degree up to 10 which are suitable to be used as generator polynomials of CRC codes are classified and all the necessary data for the evaluation of the error control performance of the CRC codes generated by the classified polynomials is calculated. A procedure, based on the computed data, for choosing the best CRC code is suggested.

The prefix-free code construction problem is to take a message containing n unique symbols and produce a set of n codewords which can be used to create a reversible encoding of the message. The minimum-redundancy code construction problem adds the requirement that the code produced must minimise the cost of transmission (or storage) of the message. Adding another constraint, the minimum-redundancy length-restricted code construction problem is to create a minimum-redundancy code in which no codeword has a length greater than L bits. The solution to the minimum-redundancy code construction problem is due to Huffman (1952). The package-merge strategy of Larmore and Hirschberg (1990) is a two-stage mechanism for creating minimum-redundancy length-restricted codes. Their implementation, here called ORIGINAL-PM, requires O(nL) time and space. ORIGINAL-PM follows the underlying strategy closely and the following is a description of both the principle and that first implementation. Different implementation methods are discussed.

In this paper, we present a novel packetized bit-level decoding algorithm for variable-length encoded Markov sources, which calculates reliability information for the decoded bits in the form of a posteriori probabilities (APPs). An interesting feature of the proposed approach is that symbol-based source statistics in the form of the transition probabilities of the Markov source are exploited as a priori information on a bit-level trellis. This method is especially well-suited for long input blocks, since in contrast to other symbol-based APP decoding approaches, the number of trellis states does not depend on the packet length. When additionally the variable-length encoded source data is protected by channel codes, an iterative source-channel decoding scheme can be obtained in the same way as for serially concatenated codes. Furthermore, based on an analysis of the iterative decoder via extrinsic information transfer charts, it can be shown that by using reversible variable-length codes with a free distance of two, in combination with rate-1 channel codes and residual source redundancy, a reliable transmission is possible even for highly corrupted channels. This justifies a new source-channel encoding technique where explicit redundancy for error protection is only added in the source encoder.

It is well known that turbo codes provide highly unequal error protection within a transmitted frame. Previous attempts to exploit this fact focused mainly on adding additional redundancy to provide extra protection for the error-prone bit positions. Here, instead, we use the error-detection capability of the cyclic redundancy check (CRC), which is almost always employed in practical systems. Once a frame is declared uncorrectable by the CRC, a process termed the error-prone bit processing procedure is activated in an attempt to correct the probable error patterns which are a priori identified as being error-prone.

We first provide an analysis of available redundancy remaining in compressed video data. This residual redundancy has two origins: the variable-length code (VLC) syntax and the source constraints. We compute the two in terms of equivalent redundancy bits. Then, a VLC decoding algorithm able to exploit both VLC syntax and source constraints for improving the decoding performance is outlined. Finally, it is shown that by taking this redundancy into account, video decoding over additive white Gaussian noise channels is substantially improved.

This paper considers properties of the extrinsic information transfer (EXIT) functions of turbo equalized intersymbol interference channels and finite-impulse response precoders. An analytic expression is derived for the maximum value of the EXIT function of the equalizer. Using this parameter, a design strategy is proposed for allocating redundancy between the equalizer and the decoder. The key quantities are pilot-symbol rate and code puncturing, for fixed overall data and symbol rates.

We study the throughput of hybrid automatic retransmission request (H-ARQ) schemes based on incremental redundancy (IR) over a block-fading channel. We provide an information-theoretic analysis assuming binary random coding and typical-set decoding. Then, we study the performance of low-density parity-check (LDPC) code ensembles with iterative belief-propagation decoding, and show that, under the hypothesis of infinite-length codes, LDPCs yield almost optimal performance. Unfortunately, standard finite-length LDPC ensembles incur a considerable performance loss with respect to their infinite-length counterpart, because of their poor frame-error rate (FER) performance. In order to recover part of this loss, we propose two simple yet effective methods: using a modified LDPC ensemble designed to improve the FER; and using an outer selective-repeat protocol acting on smaller packets of information bits. Surprisingly, these apparently very different methods yield almost the same performance gain and recover a considerable fraction of the optimal throughput, thus making practical finite-length LDPC codes very attractive for data wireless communications based on IR H-ARQ schemes.

The paper considers discrete multitone (DMT) modulation for multiuser communications when multiple users are supported by the same system, a zero-padding redundancy is employed at the transmitter output, and linear redundancy removal is used at the channel output. These users may have differing quality of service (QoS) requirements, as quantified by bit rate and symbol-error rate specifications, and are each assigned an equal number of subchannels. Our goal is to minimize the transmitted power, given the QoS specifications and subject to the knowledge of the channel and the second-order statistics of the colored interference at the receiver input. In particular, we find an optimum bit-loading scheme that distributes the bit rate transmitted across the various subchannels belonging to each user, and, subject to this bit allocation, we determine the precise subchannels assigned to each user, the optimum transceiver characterized by the input/output block transforms, and the redundancy removal operation. A major conclusion is that even though the optimum bit-rate allocation differs from the single-user case, the optimum transceiver does not. Further, it is determined entirely by the channel and interference conditions, and is unaffected by the QoS requirements.

For data communications in time-varying channels such as wireless channels, the dynamic channel fluctuations often cause high frame-error rates. When the link layer detects that a frame is in error, conventionally, the frame is dropped and retransmission of the frame is requested. Based on the fact that the erroneous frames still contain useful information, several schemes have been proposed, such as packet combining and incremental redundancy, which retain and utilize the erroneous frames to improve retransmission performance. In this paper, we address two questions: 1) how much information is still useful in the erroneous frame; and 2) how to design a retransmission scheme to make efficient use of such information. We model this scenario (retransmission with an erroneous frame available at the receiver) as communication with side information at the receiver, and for a class of time-varying channels, the compound block interference channels, we derive with information-theoretic arguments the minimum information rate sufficient for retransmission to recover the erroneous frame. Motivated by the theoretical results, we propose an embedded channel coding/modulation structure together with a rate-adaptive retransmission scheme. Performance results indicate significant improvements over existing retransmission schemes in both additive white Gaussian noise and quasi-static Rayleigh fading channels.

Real world source coding algorithms usually leave a certain amount of redundancy within the coded bit stream. Shannon (1948) already mentioned that this redundancy can be exploited at the receiver side to achieve a higher robustness against channel errors. We show how joint source-channel decoding can be performed in a way that is applicable to any mobile communication system standard. Considerable gains in terms of bit error rate or signal-to-noise ratio (SNR) are possible dependent on the amount of redundancy. However, an even better performance can be achieved by changing also the transmitter sided source and channel encoders. We propose an encoding concept employing low-dimensional quantization. Keeping the gross bit rate as well as the clean channel quality the same, it decreases the complexity of the source encoder and the decoder significantly. Finally, we give an application of our methods to spectral coefficient coding in speech transmission over a Rayleigh fading channel resulting in channel SNR gains of about 2 dB as compared to state-of-the-art (de-)coding and bad frame handling methods.

Block cyclic redundancy check (CRC) codes represent a popular and powerful class of error detection techniques used almost exclusively in modern data communication systems. Though efficient, CRCs can detect errors only after an entire block of data has been received and processed. In this work, we exploit the "continuous" nature of error detection that results from using arithmetic codes for error detection, which provides a novel tradeoff between the amount of added redundancy and the amount of time needed to detect an error once it occurs. We demonstrate how this continuous error detection framework improves the overall performance of communication systems, and show how considerable performance gains can be attained. We focus on several important scenarios: 1) automatic repeat request (ARQ) based transmission; 2) forward error correction (FEC frameworks based on (serially) concatenated coding systems involving an inner error-correction code and an outer error-detection code; and 3) reduced state sequence estimation (RSSE) for channels with memory. We demonstrate that the proposed CED framework improves the throughput of ARQ systems by up to 15% and reduces the computational/storage complexity of FEC and RSSE by a factor of two in the comparisons that we make against state-of-the-art systems.

In previous work on source coding over noisy channels it was recognized that when the source has memory, there is typically "residual redundancy" between the discrete symbols produced by the encoder, which can be capitalized upon by the decoder to improve the overall quantizer performance. Sayood and Borkenhagen (1991) and Phamdo and Farvardin (see IEEE Trans. Inform. Theory, vol.40, p.186-93, 1994) proposed "detectors" at the decoder which optimize suitable criteria in order to estimate the sequence of transmitted symbols. Phamdo and Farvardin also proposed an instantaneous approximate minimum mean-squared error (IAMMSE) decoder. These methods provide a performance advantage over conventional systems, but the maximum a posteriori (MAP) structure is suboptimal, while the IAMMSE decoder makes limited use of the redundancy. Alternatively, combining aspects of both approaches, we propose a sequence-based approximate MMSE (SAMMSE) decoder. For a Markovian sequence of encoder-produced symbols and a discrete memoryless channel, we approximate the expected distortion at the decoder under the constraint of fixed decoder complexity. For this simplified cost, the optimal decoder computes expected values based on a discrete hidden Markov model, using the wellknown forward/backward (F/B) algorithm. Performance gains for this scheme are demonstrated over previous techniques in quantizing Gauss-Markov sources over a range of noisy channel conditions. Moreover, a constrained delay version is also suggested.

This letter describes a technique for finding cyclic redundancy check polynomials for systems for transmission over symmetric channels which encode information in multiple voltage levels, so that the resulting redundancy check gives good error protection and is efficient to implement. The codes which we construct have a Hamming distance of 3 or 4. We discuss a way to reduce burst error in parallel transmissions and some tricks for efficient implementation of the shift register for these polynomials. We illustrate our techniques by discussing a particular example where the number of levels is 9, but they are applicable in general.

This paper proposes a fast block-matching algorithm that uses three fast matching error measures, besides the conventional mean absolute error (MAE) or mean square error (MSE). An incoming reference block in the current frame is compared to candidate blocks within the search window using multiple matching criteria. These three fast matching error measures are established from the integral projections, taking their advantages of good representation for block features and simple complexity in measuring matching errors. Most of the candidate blocks can be rejected by calculating only one or more of the three fast matching error measures. The time-consuming computations of MSE or MAE are performed on only a few candidate blocks that first pass all the three fast matching criteria. Simulation results show a reduction of over 86% in computations is achieved after integrating the fast three matching criteria into the full-search algorithm, while ensuring the optimal accuracy.

Minimum redundancy coding (also known as Huffman coding) is one of the enduring techniques of data compression. Many efforts have been made to improve the efficiency of minimum redundancy coding, the majority based on the use of improved representations for explicit Huffman trees. In this paper, we examine how minimum redundancy coding can be implemented efficiently by divorcing coding from a code tree, with emphasis on the situation when n is large, perhaps on the order of 10/sup 6/. We review techniques for devising minimum redundancy codes, and consider in detail how encoding and decoding should be accomplished. In particular, we describe a modified decoding method that allows improved decoding speed, requiring just a few machine operations per output symbol (rather than for each decoded bit), and uses just a few hundred bytes of memory above and beyond the space required to store an enumeration of the source alphabet.

We investigate lossless compression schemes for video sequences. A simple adaptive prediction scheme is presented that exploits temporal correlations or spectral correlations in addition to spatial correlations. It is seen that even with motion compensation, schemes that utilize only temporal correlations do not perform significantly better than schemes that utilize only spectral correlations. Hence, we look at hybrid schemes that make use of both spectral and temporal correlations. The hybrid schemes give significant improvement in performance over other techniques. Besides prediction schemes, we also look at some simple error modeling techniques that take into account prediction errors made in spectrally and/or temporally adjacent pixels in order to efficiently encode the prediction residual. Implementation results on standard test sequences indicate that significant improvements can be obtained by the proposed techniques.

Presents an architecture for the efficient encoding of Reed-Solomon codes, with or without interleaving. This architecture utilizes a clock whose rate is r times the symbol rate, where r is the redundancy of the code. The finite field operations are performed in a sequential manner, requiring only one finite field multiplier and one finite field adder. All memory elements (except one symbol register) are consolidated into a discrete-time delay line, which can be easily implemented with a random access memory. This approach alleviates the clock skew problem and leads to significant hardware savings over the usual parallel approach, when the redundancy and/or interleaving depth are large. The architecture can be easily reconfigured for changes in the generator polynomial of the code, the amount of redundancy, and the interleaving depth. >

A hardware device for efficiently evaluating the probability of undetected error for a class of CRC error detection codes with a large number of parity check digits is described. The generator polynomial for the codes in this class are of the form g(x)=(1+x)p(x) where p(x) is a primitive irreducible polynomial. The degree of g(x), R, is the number of parity check digits. Using this hardware, a search was conducted for codes in this class (for 8/spl les/R/spl les/39) which are "proper" for shortened block lengths. A table of codes satisfying this condition is included. >

The generalized type-II hybrid automatic repeat request (ARQ) scheme on Markov channels is examined in order to study the effect of feedback channel errors on the performance of ARQ systems. It is shown that it is 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, a parallel set of expressions is provided under the usual assumption of an error-free feedback channel. By use of simulations, the ARQ system performance is examined under 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 lower the probability of undetected error, reduce the number of unnecessary transmissions, and increase the throughput efficiency. >

The performance of nonlinear cancellation schemes is limited by the accuracy of tentative decisions. This correspondence analyzes the performance of combined trellis coded modulation and nonlinear cancellation. A scheme is proposed to make use of the redundancy of the code. It is shown that performance close to optimum can be achieved with this scheme. >

A technique for providing error protection without the additional overhead required for channel coding is presented. The authors start from the premise that, during source coder design, for the sake of simplicity or due to imperfect knowledge, assumptions have to be made about the source which are often incorrect. This results in residual redundancy at the output of the source coder. The residual redundancy can then be used to provide error protection in much the same way as the insertion of redundancy in convolutional coding provides error protection. The authors develop an approach for utilizing this redundancy. To show the validity of this approach, the authors apply it to image coding using differential pulse code modulation (DPCM), and obtain substantial performance gains, both in terms of objective and subjective measures. >

The authors investigate the efficacy of using two different cyclic redundancy check (CRC) codes in tandem to increase error-burst detecting capability. For a set of pairs of CRCs which are used in standards, it is found that the guaranteed detectable burst length is less than the sum of the individual guaranteed detectable burst lengths, but not much less. Thus strengthened CRC codes can readily be obtained using existing devices. >

Optimal binary cyclic redundancy-check codes with 16 parity bits (CRC-16 codes) are presented and compared to those in existing standards for minimum-distance, undetected-error probability on binary symmetric channels (BSCs) and properness. The codes in several cases are seen to be superior at block lengths of practical interest when they are used on low-noise BSCs. The optimum minimum distance obtainable by some CRC-16 codes is determined for all block lengths. For several typical low-noise BSCs the minimum undetected error probability achievable with some CRC-16 codes is given for all block lengths. >

An image coding method for low bit rates is proposed. It is based on alternate use of the discrete cosine transform (DCT) and the discrete sine transform (DST) on image blocks. This procedure achieves the removal of redundancies in the correlation between neighboring blocks as well as the preservation of continuity across the block boundaries. An outline of the mathematical justification of the method, assuming a certain first-order Gauss-Markov model, is given. The resulting coding method is then adapted to nonstationary real images by locally adapting the model parameters and improving the block classification technique. Simulation results are shown and compared with the performance of related previous methods, namely adaptive DCT and fast Karhunen-Loeve transform (FKLT). >

Arithmetic coding for data compression has gained widespread acceptance as the right method for optimum compression when used with a suitable source model. A technique to implement error detection as part of the arithmetic coding process is described. Heuristic arguments are given to show that a small amount of extra redundancy can be very effective in detecting errors very quickly, and practical tests confirm this prediction.

The contents of error-protected frames can be intentionally altered as the frames traverse through a digital network. The check bits must be recomputed to conform with the altered text. A method is described for updating the check bits of a cyclic redundancy check (CRC) code, based on knowledge of the altered bits and their position in the frame. Unlike previous methods, its complexity is independent of the frame size. >

A new method for reducing the peak-to average power ratio (PAPR) in orthogonal frequency-division multiplexing is proposed. The new method, called erasure pattern selection (EPS), is based on the use of frame expansion for adding redundancy to the data. Part of the redundancy is removed by examining several patterns for erasing subcarriers, and selecting the pattern that produces the lowest PAPR for transmission. The residual redundancy in the data is exploited at the receiver to aid both the reconstruction of the erased data and correction of errors. The implementation is aided with the incorporation of a projection-onto-convex-sets (POCS) method in EPS, in order to select and assign the best values to the unused subcarriers and further reduce the PAPR. Complexity analysis and simulation results show that the POCS-based EPS method outperforms existing probabilistic methods, while requiring lower overall complexity.

This paper presents the results of a study in data compression of adaptive delta modulated video signals. The Song mode ADM is first investigated at a sampling rate of 16 Mbits/s and shown not to produce enough redundancy to warrant entropy encoding. We then present a modified adaptive delta modulator algorithm that operates at a sampling rate of 16 Mbits/s and does produce sufficient redundancy to yield a 40-50 percent data compression by using a simple code on 4 bit data blocks. Other techniques such as field interpolation and direct substitution are shown to increase the possible data compression further without noticeable degradation in the two input images used in this investigation. The effects of channel errors in the transmission of packet video over a computer network are considered. A leaky integrator is used to reduce the effects of channel errors in the data bits. We show that the effects of channel errors can be reduced by field interpolating those packets that can be shown to contain errors.

A codec for videoconferencing purposes [8]-[12], [31] is proposed based on the one-at-a-time search (OTS) motion compensation algorithm [1], [30], [31]. The coder is implemented in an interframe hybrid mode using the C -matrix transform (CMT) [13]-[15]. The motion estimation algorithm employed is simple and reduces temporal redundancy, while the CMT reduces spatial redundancy in the transmitted prediction errors. The operation of the codec is presented. Simulation results based on three different scenes with varying levels of motion are presented. The coder operates in a feedback mode.

An improved low-frequency spectral suppression (LOFS) code is introduced and analyzed as a method to suppress low-frequency energy in a digital baseband signal with significantly lower redundancy than required methods. Alternatively, the LOFS code will suppress more energy near DC with a given redundancy when compared to current coding methods, allowing insertion of a pilot tone which leads to a simple unambiguous carrier recovery subsystem that can track system-induced noise. The LOFS code reduces redundancy by adding control bits in word format for multilevel signals, that is, control bits for multiple frames are inserted in one symbol duration. Use of this LOFS code could reduce the redundancy of currently used digital transmission systems from 4% to 1%. Analysis of computer simulations shows that a premodulation high-pass filter, while significantly degrading the uncoded PAM signal, causes little degradation of the coded data and keeps data to pilot interference to a minimum. Experimental hardware results are included to verify simulation results. >

A method is presented to automatically inspect the block boundaries of a reconstructed two-dimensional transform coded image, to locate blocks which are most likely to contain errors, to approximate the size and type of error in the block, and to eliminate this estimated error from the picture. This method uses redundancy in the source data to provide channel error correction. No additional channel error protection bits or changes to the transmitter are required. It can be used when channel errors are unexpected prior to reception.

In this paper we develop a simple encoder/decoder pair which utilizes the natural redundancy of a source for error detection. It does so with no loss in rate of transmission and with only minimal hardware cost.

This paper presents a class of digital transformations which generate n -level sequences having an autocorrelation function which remains nonzero throughout its domain in order to insure a narrow spectrum. In addition, any transformation of the class attains maximum redundancy and can be implemented by a simple one-bit memory stochastic machine. Most importantly, the autocorrelation function is obtained analytically which permits establishing for any odd value of n the set of level values which achieve optimum bandwidth compression.

Many redundancy removal algorithms employ some sort of run length code. Blocks of timing words are coded with synchronization words inserted between blocks. The probability of incorrectly reconstructing a sample because of a channel error in the timing data is a monotonically nondecreasing function of time since the last synchronization word. In this paper we compute the "probability that the accumulated magnitude of timing errors equal zero" as a function of time since the last synchronization word for a zero-order predictor (ZOP). The result is valid for any data source that can be modeled by a first-order Markov chain and any digital channel that can be modeled by a channel transition matrix. An example is presented.

A comparison and a valuation of different redundancy reducing coding techniques for the digital transmission of facsimile documents on telephone lines is presented. Especially taken into account are those codes which have been submitted to the International Telegraph and Telephone Consultative Committee (CCITT) for standardization of digital group 3 facsimile machines. The reduction factor and the sensitivity of channel errors of these one- and two- dimensional codes have been investigated by computer simulations using the CCITT test documents and burst error patterns of real telephone lines. For a resolution of 1728 picture elements per line and 3.85 lines per mm one-dimensional run length coding proves to be the most economical solution. Using a higher vertical resolution of 7.7 lines per mm the effects of transmission errors are less visible in the received document and two-dimensional codes become more efficient. To achieve a transmission time of 1 min or less for a size A4 document a transmission bit rate of 4800 bits/s is required. For the higher vertical resolution a transmission time of 1 min cannot be guaranteed for all types of documents with this bit rate even if two-dimensional coding is used.

Methods are presented for enhancing one-dimensional variable-length differential pulse-code modulation (VLDPCM) images corrupted by transmission errors, are presented. The proposed methods take advantage of the VLDPCM code's high sensitivity to errors. Two methods are described. The first involves no increase of transmitted bit rate and consists of processing the corrupted image. The second method involves the transmission of additional information to enable an almost exact reconstruction of the original image. The amount of added redundancy can be reduced at the cost of performing more computations. In a simulation, the authors used less than 7% redundancy. Both methods achieve significant improvements which are demonstrated by the simulation results. The simulation results include original, corrupted, and enhanced images as well as the signal-to-noise ratio (SNR) versus bit-error rate (BER) curve. For BER 10/sup -3/, the SNR (signal-to-noise ratio) gains for the first and second methods are greater than 17 and 44 dB, respectively. >

The two-dimensional predictive redundancy of a television picture element is calculated as a function of the preceding point correlation for both interlaced and noninterlaced scanning. The resulting curves level off rapidly when the number of previous points taken into account is increased. This seems to indicate that while appreciable improvement would accrue if preceding point redundancy were used, there would be little more to earn by including the redundancies due to more distant points, especially in view of the necessarily increased complexity of circuitry. An analysis of three-dimensional redundancy would probably result in similar conclusions.