We find good rate 2/3 and 3/4 convolutional codes for use with iterative decoding (turbo equalization) of coded intersymbol interference with AWGN. The method is based on the input-output bit error rate characteristic of the convolutional BCJR decoder module. An analysis leads to an equivalent minimum distance under the required intrinsic subtraction, which depends on free distance and an input-output LLR correlation parameter.

This paper presents a study of analog and digital versions of a low complexity channel decoder to investigate the overall performance of both circuits in 65nm CMOS for moderate bit rate applications. Both decoding circuits realize the corresponding decoding algorithm for the convolutional codes generated by the well known 4-state (7,5)8encoder. The two digital and analog implementations are then analyzed for power consumption, offered coding gain, required silicon area and energy efficiency. The simulations show that the analog circuit outperforms its digital version by a factor of 10X at nominal supply voltage for the same throughputs. Furthermore, the analog implementation is 4.6 times smaller in area than its counterpart.

In this paper, we survey faster-than-Nyquist (FTN) signaling, an extension of ordinary linear modulation in which the usual data bearing pulses are simply sent faster, and consequently are no longer orthogonal. Far from a disadvantage, this innovation can transmit up to twice the bits as ordinary modulation at the same bit energy, spectrum, and error rate. The method is directly applicable to orthogonal frequency division multiplex (OFDM) and quadrature amplitude modulation (QAM) signaling. Performance results for a number of practical systems are presented. FTN signaling raises a number of basic issues in communication theory and practice. The Shannon capacity of the signals is considerably higher.

We give a procedure to find good convolutional codes for use with iterative decoding (turbo equalization) of the coded AWGN intersymbol interference (ISI) channel. The method is based on the input-output bit error rate characteristic of the convolutional BCJR module in the iterative decoder, in combination with the code minimum distance. Both are essential to find best codes. Best feedforward and recursive systematic codes are listed for memories 2-4, and some individual good codes at memory 5. Codes are tested over a root raised-cosine faster than Nyquist channel with severe ISI. Turbo BER performance reaches 0.8-1.6 dB from capacity with a 4-16 state codes. Feedforward codes perform better than recursive systematic.

We propose new M-algorithm BCJR (M-BCJR) algorithms for low-complexity turbo equalization and apply them to severe intersymbol interference (ISI) introduced by faster than Nyquist signaling. These reduced-search detectors are evaluated in simple detection over the ISI channel and in iterative decoding of coded FTN transmissions. In the second case, accurate log likelihood ratios are essential and we introduce a 3-recursion M-BCJR that provides this. Focusing signal energy by a minimum phase conversion before the M-BCJR is also essential; we propose an improvement to this older idea. The new M-BCJRs are compared to reduced-trellis VA and BCJR benchmarks. The FTN signals carry 4-8 bits/Hz-s in a fixed spectrum, with severe ISI models as long as 32 taps. The combination of coded FTN and the reduced-complexity BCJR is an attractive narrowband coding method.

We perform a minimum distance analysis of a class of two-dimensional intersymbol interference (ISI) channels applicable to multitrack magnetic recording and orthogonal frequency division multiplex transmission systems. Exact minimum distance for a wide class of ISI responses is derived. The fundamental analytical technique is to transform the channel into an equivalent minimum phase channel. The results improve upon the prior work of Soljanin and Georghiades.

A complete architecture with transistor level simulation is presented for a low power analog convolutional decoder in 65 nm CMOS. The decoder core operates in the weak inversion (sub-Vτ) and realizes the BCJR decoding algorithm corresponding to the 4-state tail-biting trellis of a (7,5) convolutional code. The complete decoder also incorporates serial I/O digital interfaces and current mode differential DACs. The simulated bit error rate is presented to illustrate the coding gain compared to an uncoded system. Our results show that a low power, high throughput convolutional decoder up to 1.25 Mb/s can be implemented using analog circuitry with a total power consumption of 84 μW. For low rate applications the decoder consumes only 47 μW at a throughput of 250 kb/s.

M-BCJR algorithms are proposed and tested over an AWGN channel with moderate to intense intersymbol interference (ISI). Two M-BCJR applications are evaluated, simple detection over the ISI channel and turbo equalization. The signaling is binary faster than Nyquist linear modulation. The ISI models tested correspond to transmission of increasingly many bits/Hz-s with a fixed signal spectra; the paper studies the range 2-8 bits/Hz-s, which implies ISI models as long as 32 taps. As a simple detector, the M-BCJR achieves the ML error rate with small computation, where the Viterbi algorithm is completely impractical. In turbo equalization, the M-BCJR needs somewhat more computation and a more careful design because it must produce accurate likelihoods.

This paper presents the complexity analysis of a transmitter architecture for a faster-than-Nyquist (FTN) system. Complexity issues in terms of computations and memory requirements to achieve an FTN system are dealt with. An OFDM based multi-carrier system is considered as it is one of the most widely used in upcoming wireless standards. Retaining the modules within the OFDM transmitter helps in exploiting the already optimized and hardware efficient structures, the IFFT being one. From an implementation perspective the introduction of FTN introduces negligible overhead for the transmitter.

A critical component in detection under intersymbol interference (ISI) and in turbo equalization is the BCJR algorithm. We combine three approaches to reducing its computation. First, energy seen by the receiver is focused by a phase-maximizing all pass filter; an improvement on this older idea is proposed. Then the state used by the BCJR is broken into an offset state and a main state. Finally, some reduced-state BCJR procedures are evaluated. These receivers are tested by ISI detection and turbo equalization over strongly bandlimited channels.

We extend Mazo's concept of faster-than-Nyquist (FTN) signaling to pulse trains that modulate a bank of subcarriers, a method called two dimensional FTN signaling. The signal processing is similar to orthogonal frequency division multiplex(OFDM) transmission but the subchannels are not orthogonal. Despite nonorthogonal pulses and subcarriers, the method achieves the isolated-pulse error performance; it does so in as little as half the bandwidth of ordinary OFDM. Euclidean distance properties are investigated for schemes based on several basic pulses. The best have Gaussian shape. An efficient distance calculation is given. Concatenations of ordinary codes and FTN are introduced. The combination achieves the outer code gain in as little as half the bandwidth. Receivers must work in two dimensions, and several iterative designs are proposed for FTN with outer convolutional coding.

This paper deals with capacity computations of faster-than-Nyquist (FTN) signaling. It shows that the capacity of FTN is higher than the orthogonal pulse linear modulation capacity for all pulse shapes except the sinc. FTN signals can in fact achieve the ultimate capacity for the signal power spectral density (PSD). The paper lower- and upper-bounds the FTN capacity under the constraint of finite input alphabet. It is often higher than the capacity for comparable orthogonal pulse systems; sometimes it is superior to all forms of orthogonal signaling with the same PSD.

Faster-than-Nyquist (FTN) signaling is a trellis coding method that maintains the error rate while reducing signal bandwidth. The combined effect is to move closer to capacity. We study some basic receiver issues: How to model the signaling efficiently in discrete time, how much the Viterbi receiver can be truncated, and how to combine the method with an outer code. The methods are modeling for minimum phase, minimum distance calculation and receiver tests. Concatenated FTN in a turbo equalization scenario proves to be a strong coding method.

In this paper we perform a minimum distance analysis of a class of two dimensional intersymbol interference channels. In particular, some important cases of multitrack multihead magnetic recording systems fall into the studied class. Previously, Soljanin and Georghiades have studied the same problem as we do. The results derived in this paper are more conclusive and they improve upon theirs. The fundamental proof technique that we will use is to transform the channel into an equivalent minimum phase channel.

We consider the effect of symbol rate on the constrained capacity of linear modulation with a fixed spectral density. We show that constrained capacity grows with the symbol rate for some modulation pulses but shrinks with others. Sufficient conditions on the pulse are derived for the constrained capacity to be monotonically increasing with faster symbol rate. Most standard pulses fulfill these.

Faster than Nyquist (FTN) signaling is an important method of narrowband coding. The concept is extended here to non binary signal constellations; these are much more bandwidth efficient than binary ones. A powerful method of finding the minimum distance for binary and non binary FTN is presented. Preceding FTN transmissions with short linear filters proves to be an effective way to gain distance. A Shannon limit to bit error rate is derived that applies for FTN. Tests of an M-algorithm receiver are performed and compared to this limit.

In this paper we investigate partial response signaling (PRS) systems that are intended to operate close to capacity. We show that finding PRS systems with maximal capacity is a rather easy optimization task. We give an alternate way of defining bandwidth for PRS systems based on capacity considerations; this differs considerably from the traditional method based on transmission power. Practical PRS schemes are derived, based on these ideas. Their bit error rate is significantly better than earlier, distance-optimizing schemes.

We minimize the frequency and time occupancy of multicarrier binary linear modulation based on two-dimensional faster than Nyquist (FTN) signaling. FTN analysis provides the asymptotic time-frequency consumption per bit and prolate spheroidal wave analysis minimizes the side lobe occupancy. For both problems, an excellent choice is a Gaussian pulse, with some adjustment of the side lobes.

Rate-distortion trellis source codes are developed for quantizing memoryless independent and identically distributed (i.i.d.) sources. The codes are generated by simple linear congruential recursions. The method generates codes at a variety of rates including fractional ones; reproducer sets can be large, a crucial advantage with certain sources. Axioms for good code construction are developed that are based on recursion properties and certain trellis symmetries. These axioms are justified by the outcome of random searches for good codes. It is found that the trellis code design breaks into two problems: the trellis labels should have certain properties regardless of the source distribution; and the reproducer values depend on the source. Encoders are simulated for a number of continuous amplitude sources. For the same computational complexity, the new codes, in most cases, perform better than the best codes in the literature, including trellis-coded quantization and fake process approaches.

The Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm is an important channel decoding method. We extend it to trellis rate-distortion data compression. Beginning from source coding principles, the derivation of the algorithm avoids channel coding or soft output ideas. The encoder does not use entropy coding; equiprobable reproducer letters are emphasized since these maximize entropy. The BCJR method is demonstrated by tests of a tail-biting variant. It performs much better than the ordinary Viterbi algorithm for short and medium blocks. However, the improvement stems from tail biting; the role of the BCJR is to achieve tail biting in a relatively simple way. Some issues that arise with tail biting are explored. It is shown that there is an optimal trellis state size for each block length.

We consider the lossy image compression problem and propose a model-residual approach. Polynomial basis images encode the model image and powerful new trellis codes quantize the residual part. A simple bit allocation scheme determines the residual bit rates and a variety of rates are attainable without entropy coding. The trellis structure is also used to form a joint source and channel coding scheme for the residual components. Results are shown for the 0.4-1.6 bits per pixel region. Comparisons are made to several state-of-the-art techniques and show that the proposed scheme is very competitive.

In this paper we consider the information rates of faster than Nyquist (FTN) signaling schemes. We consider binary, quaternary and octal schemes that use root raised cosine pulses. Lower and upper bounds to the information rates are given. The main result is that the lower bounds are often above the information rates for standard Nyquist signaling schemes. This implies that FTN must be superior to Nyquist signaling in some cases. Test results for one coding scheme are given; these show that high throughput communication based on FTN is indeed practical.

We motivate and discuss the logarithmic bit-significance ratio (S-value) which is a universal measure to quantify the significance of each bit in a digital communication system. Calculation rules for the S-values are given which, for instance, allow for the computation of the significances of parity bits when the significances of the data bits are given. The introduction of the S-value allows for the processing of soft-information, e.g., in encoding and modulation and can, hence, be interpreted as the transmitter-based counterpart of the well-established log-likelihood ratio (L-value) at the receiving end

We investigate the performance of concatenated coding schemes based on faster than Nyquist (FTN) signaling over the AWGN channel. We test both serial and parallel concatenations. In serial concatenation the FTN signaling is considered as the inner encoder and the outer code is a rate b/c convolutional code. In parallel schemes we use two parallel Gaussian channels and transmit FTN pulse trains in both; here a precoding device turns out to be crucial. The convergence behaviour is analysed using EXIT charts. The overall spectral density of the schemes varies but is roughly 1-2 bit/s/Hz. The results, in terms of needed Eb/N0for reliable communication versus spectral density, are very good

In earlier work we have extended Mazo's concept of faster-than-Nyquist signaling to pulse trains that modulate adjacent subcarriers, a method we called two dimensional Mazo signaling. The signal processing is similar to orthogonal frequency division multiplex (OFDM) transmission. Despite pulses that are faster than the Nyquist limit and subcarriers that significantly overlap, the transmission achieves the isolated pulse error performance. In this paper we review the method and test a receiver based on successive interference cancellation. It virtually achieves the matched filter bound.

Summary form only given. In this paper, we examine the effect of block size on the performance of trellis based quantization. In particular, the Viterbi and tailbiting BCJR algorithms are compared. It is shown that for short blocks of data, the T-BCJR algorithm achieves a superior performance over the Viterbi algorithm (VA). One approach is to use the maximum a posteriori probability (MAP) heuristic and the T-BCJR algorithm. If the MAP-encoder does not produce a tailbiting state sequence, the path is modified for a number of stages at the beginning and end of the block such that it tailbites. The enclosed figure shows MSE as a function of block size and sample position, respectively, for a rate R=1 bit per sample, 32-state trellis quantizer and an IID Gaussian source. The effects of start-up are clearly visible. For the T-BCJR algorithm, the distortion is evenly distributed across the whole block. The performance decrease for short blocks stems from the increase in the number of tailbiting violations for short blocks and the suboptimal modification to ensure tailbiting. The results presented here hold for a large class of trellis constructions, such as TCQ.

We present two methods for variable-rate trellis quantization. Both methods utilize trellis codes based on linear congruential (LC) recursions. LC code trellises have good pseudo-random properties and are easily adapted to serve reconstruction alphabets of different sizes. The first method finds an entropy-constrained code only by optimizing over a scale factor. The scale factor modifies an initial reproducer alphabet in order to skew the associated set of codeword lengths. Using a Lagrangian formulation and the maximum a posteriori (MAP) heuristic, we also develop an entropy-constrained trellis quantizer suitable for short blocks of data. Here the tailbiting BCJR algorithm is used to find the MAP path in the trellis. Simulation results for the Gaussian and Laplacian distributions show that the proposed method is competitive with the best in the literature.

The decision depth L/sub d/ for finite and infinite partial response signaling (PRS) schemes is investigated. New measures are proposed that take into account error event multiplicity. We conclude that small to moderate decoder decision depths achieve performance near MLSE even for near catastrophic codes. Under some constraints, the decision depth should be an increasing function of the signal to noise ratio.

The BCJR algorithm is an important method of channel decoding. We extend it here to rate-distortion encoding. The arguments begin from source coding principles and make no use of channel coding or soft output ideas. An important role is played by codeword ensembles with equiprobable reproducer letters. The BCJR method is demonstrated by tests of a tailbiting BCJR with the Gaussian source. The outcome improves Viterbi algorithm performance at short and medium blocklengths

Partial response signaling (PRS) codes with maximal minimum Euclidean distance have previously been found by linear programming. These perform very well in the narrowband-high energy region, but they were not optimized for minimal bit error rate (BER), so they are only optimal in the limit of infinite signal to noise ratio. Here we search for codes that perform better for more practical signal to noise ratios. The BER objective function is no longer linear, but it is still convex

Faster than Nyquist (FTN) signaling is extended. We send FTN pulse trains that overlap in both time and frequency; this is called two dimensional Mazo signaling. The minimum time and frequency separation that achieves dmin2= 2 for root raised cosine pulses is found. Two dimensional signaling is more bandwidth efficient than one dimensional. A simple decoder is tested and it verifies the distance results

A flexible channel decoding platform should be able to operate in varying communication scenarios, and different code rates have to be supported. Therefore, we present a framework that allows efficient processing of rate-flexible trellises. Using a fundamental computational unit for trellis-based decoding, formal principles are obtained to emulate more complex trellises. In a design example, such a computational block supports both rate 1/c convolutional codes and set partition codes with subset selectors of rate 2/3. Synthesis results show the hardware requirements for two different architectural approaches

This paper presents new methods trellis source coding at rates above and below one. The new schemes have in common a code design based on branch correlation, a large reproducer alphabet, and an encoder based on either the Viterbi algorithm or a tailbiting MAP technique. The methods are easily adapted to various bit rates, but here only the results for R = 2 and R = 1/2 bits per source sample are presented. Results, demonstrated for the memoryless Gaussian source, show similar or better performances than previous methods with similar coding complexity.

Two new kinds of fractional-rate trellis source codes based on linear congruential recursions are evaluated. Properties of good codes are given. Square error distortion is similar to or better than competing schemes.

Optimal finite partial response signals based on 2 and 4 PAM were found by Said and Anderson. The encoder is a simple discrete-time filter, whose combination of bandwidth and Euclidian distance is optimized. Here we extend the idea to the case when the modulated symbols are first encoded by a convolutional encoder. Good narrowband codes are the result.

New trellis constructions for compression of short data sequences are presented. Traditional low rate trellis source coding suffer from having a too small reproduction alphabet. Governed by alphabet-constrained rate-distortion theory a simple method was proposed for a source coding rate of 1 bit per sample that allows 2/sup m/ reconstruction values for a trellis with 2/sup m/ states. The proposed method is based on the maximum a posteriori probability criterion distortion measure and it employs tailbiting. Tailbiting makes the method suitable also for short data sequences. Simulation results are compared to TCQ-like methods.

Summary form only given. BCJR based source coding of image residuals is investigated. From a trellis representation of the residual, a joint source-channel coding system is formed. Then the BCJR algorithm is applied to find the MAP encoding. MAP and minimized squared error encoding are compared. The novelty of this work is the use of the BCJR algorithm and the MAP criterion in the source coding procedure. The source encoding system described preserves more features than an MSE based encoder. Also, blocking artifacts are reduced. Comparisons may be found in the full paper version (see http://www.it.lth.se/tomas/eriksson/spl I.bar/novak/spl I.bar/anderson/spl I.bar/dcc02.ps, 2001).

We propose a Viterbi-type decoder for tailbiting trellis codes that works by traversing the tailbiting circle somewhat more than once. The traversal is the least possible for any bounded distance Viterbi decoder. Procedures are given that compute this minimum. Unlike previous decoders of the type, the new scheme does not suffer limit cycles or from pseudocodewords. The bit-error rate is compared to that of Bahl-Cocke-Jelinek-Raviv and maximum-likelihood decoding.

Earlier work has derived the storage complexity of the bounded distance decoder (BDD) for binary channel convolutional codes. We extend this work to the Gaussian noise channel and to partial-response codes. We show that the storage requirement /spl sim/(2/sup 1-R/ - 1)/sup -t/ paths for rate-R convolutional codes over the binary channel becomes /spl sim/2/sup 2Rt/ over the Gaussian channel, where the decoder must correct t errors. Thus, convolutional coding over the Gaussian channel is not only 3 dB more energy efficient, but its decoding is simpler as well. Next, we estimate the path storage for partial-response codes, i.e., real-number convolutional codes, over the Gaussian channel. The growth rate depends primarily on the bandwidth of the code. A new optimization procedure is devised to measure the maximum storage requirement in Gaussian noise for these two code types. An analysis based on difference equations predicts the asymptotic storage growth for partial response codes.

Tailbiting codes encoded by feedback convolutional encoders are studied. A condition for when tailbiting will work is given and it is described how the encoder starting state can be obtained for feedback encoders in both controller and observer canonical forms. Finally, results from a search for systematic feedback encoders that encode tailbiting codes with good decoding bit error probabilities are presented.

The BCJR algorithm consists of two linear recursions whose joint transient response define the algorithm's response to errors. The transient behavior is described and some implications are discussed for sliding block decoder storage, recovery from incorrect starts, and good code design.

We give a method of finding convolutional codes with minimum bit-error rate (BER) that combines ideas of importance sampling, Monte Carlo integration, and maximum a posteriori probability decoding. The method is applied to rate 1/2 tailbiting convolutional coding, both feedforward and feedback systematic. Tables of BER-minimizing encoders are given for memories 2-5 and tailbiting size 5-40, over a range of good and bad binary symmetric and additive white Gaussian noise channels. The best generators for these cases are in general all different and are not necessarily the generators that optimize distance. The best generators for bad channels are always systematic. The best when the channel quality is known are usually feedforward, but when it is unknown, they are feedback systematic. The best generators in good channels are predicted by a union bound technique.

Optimum demodulation of intersymbol interference may be performed using maximum-likelihood sequence estimation receivers. Standard performance analysis of these receivers assume that the receiver has perfect knowledge of the channel. We assume instead a mismatched receiver that uses an imperfect estimate of the channel to decode the information sequence. A free-distance expression for a mismatched ML receiver is derived and applied to the case of linear-coded modulation. A truncated union bound approximation accurately predicts the error probability.

The results of an extensive search for short and moderate length polynomial convolutional encoders for time-invariant tail-biting representations of block codes at rates R=1/4, 1/3, 1/2, and 2/3 are reported. The tail-biting representations found are typically as good as the best known block codes.

We extend the MAP decoding algorithm of Bahl et al. (1974) to the case of tail-biting trellis codes. An algorithm is given that is based on finding an eigenvector, and another that avoids this. Several examples are given. The algorithm has application to turbo decoding and source-controlled channel decoding.

A turbo-type scheme that uses parallel concatenation and soft-output iterative detection is proposed for transmission over linear intersymbol interference channels. When the receiver has perfect knowledge of the channel, the scheme offers only marginal improvement in performance over optimum linear coded modulation with Viterbi or reduced search detection. However, the improvement is significantly higher when the detector is mismatched, i.e., if it uses an imperfect channel estimate. The delay is low since the block sizes are small, and the performance improvement is achieved with few iterations. The technique may be applied as a retransmission strategy in order to save power for systems that suffer from losses due to ISI and channel mismatch.

We apply two reduced-computation variants of the BCJR algorithm to the decoding of serial and parallel concatenated convolutional codes. One computes its recursions at only M states per trellis stage; one computes only at states with values above a threshold. The threshold scheme is much more efficient, and it greatly reduces the computation of the BCJR algorithm. By computing only when the channel demands it, the threshold scheme reduces the turbo decoder computation to one-four nodes per trellis stage after the second iteration.

Consider nonbacktracking convolutional decoders that keep a fixed number of trellis survivors. It is shown that the error performance of these depends on the early part of the distance profile and on the number of survivors kept, and not on the free distance or the details of the code generators. Particularly, the encoder may be feedforward systematic without loss. Furthermore, this kind of encoder solves the correct path loss problem in reduced-search decoders. Other kinds do not. Therefore, with almost any other decoding method than the Viterbi algorithm, systematic feed-forward encoders should be used. The conclusions in this correspondence run counter to much accepted wisdom about convolutional codes.

We study the design of optimal signals for bandwidth-efficient linear coded modulation. Previous results show that for linear channels with intersymbol interference (ISI), reduced-search decoding algorithms have near-maximum-likelihood error performance, but with much smaller complexity than the Viterbi decoder. Consequently, the controlled ISI introduced by a lowpass filter can be practically used for bandwidth reduction. Such spectrum shaping filters comprise an explicit coded modulation, for which we seek the optimal design. We simultaneously constrain the bandwidth and maximize the minimum Euclidean distance between signals. We show that under quite general assumptions the problem can be formulated as a linear program, and solved with well-known efficient optimization techniques. Numerical results are presented, and the performance of the optimal signals, measured by their combined bandwidth and noise immunity, is analyzed. The new codes are comparable to set-partition (TCM) trellis codes. Tests of an M-algorithm decoder confirm this and show that the performance occurs at small detection complexity.

Controlled intersymbol interference may be used to design bandwidth efficient coded modulation schemes. The performance of the optimum receiver depends only on the free distance of the code and is independent of its phase. Large reductions in receiver complexity are obtained by using reduced search detection techniques like the M-algorithm (MA). However, we show that MA detector performance depends critically on phase, and is characterized by the partial energy of the encoder or channel. The minimum phase encoder needs by far the least detector searching. We propose modifications to the receiver, so that the reduced search can operate on all nonminimum phase channels at this same low complexity.

This paper provides a new closed form expression for calculating the probability that an MPSK signal will lie in a particular decision region when received over N independent and identically distributed Rayleigh fading channels corrupted by additive white Gaussian noise. This expression is applied to provide a unified method to derive the exact symbol error rate and bit error rate for MPSK signals considering N channel diversity reception. The N channel diversity reception techniques considered are maximal ratio combining (MRC) and selection combining. MRC with identical channels and dissimilar channels is considered. The results for MRC can be extended to provide an approximation for the error rates of MPSK under equal gain combining.>

Analyzes the sensitivity of equalizers to white gaussian noise mismatch, which exists whenever the noise power observed during training differs from that observed during detection. A closed-form solution for the mean-square error is obtained for linear and decision feedback equalizers as a function of the channel spectrum and degree of noise mismatch. The results show that increasing equalizer complexity may actually degrade performance in the presence of channel mismatch.>

We evaluate the down-link (base-to-mobile) capacity of a frequency-hopped TDMA system using a theoretical development of outage probability. Expressions for outage probability are provided considering voice activity, antenna diversity and Reed-Solomon coding. The system capacity is evaluated with and without power control. Down-link capacity is compared with up-link capacity. The effect of increasing system bandwidth on capacity is analyzed. Finally, the issue of calculating capacity under the assumption of connecting mobiles to the closest base station instead of the strongest base station is examined.>

Reduced-state sequence detection (RSSD) reduces the state trellis of a channel code by forming the states into classes. States within a class are such that paths into the states lie further than a distance parameter d from each other. An RSSD decoder retains only one survivor per class at each trellis level. The authors apply RSSD to ordinary binary convolutional codes. They first give a class-forming algorithm that finds the greatest reduction. It turns out that no commonly tabulated good code benefits from RSSD. However, RSSD is an effective way to repair weaker codes, such as quick look-in and RCPC codes. Finally, the authors show that RSSD cannot be more efficient than the M-algorithm.>

Continuous phase modulation (CPM) signals may be precoded by a convolutional code followed by a mapping rule. Better codes may, however, be obtained by a more general code formed by a finite state machine. We provide improved codes for one such finite state machine. A new description of codes and design rules are presented. Better results are demonstrated for the partial response CPM schemes and previous optimum results are matched for the full response case. Tests of an M-algorithm decoder achieve near maximum-likelihood performance with only a fraction of the complexity of the Viterbi algorithm.>

An analysis of sequential decoding is presented that is based on the requirement that a set probability error P/sub e/ be achieved. The error criterion implies a bounded tree or trellis search region: the shape of this is calculated for the case of a binary symmetric channel with crossover probability P and random tree codes of rate R. Since the search region is finite at all combinations of p and R below capacity, there is no cutoff rate phenomenon for any P/sub e/>0. The decoder delay (search depth), the path storage size, and the number of algorithm steps for several tree search methods are calculated. These include searches without backtracking and backtracking searches that are depth- and metric-first. The search depth of the non-backtracking decoders satisfies the Gallager reliability exponent for block codes. In average paths searched, the backtracking decoders are much more efficient, but all types require the same peak storage allocation. Comparisons are made to well-known algorithms.>

The problem of decoding data in the presence of infinite-duration intersymbol interference that is caused by severe channel filtering is considered. Filtered continuous phase modulations (CPM) are the particular object of study. A state-variable approach is used for defining the decoder tree. Maximum likelihood sequence estimation requires exhaustive tree searching, which is restricted by using the (M, L) algorithm since this approach does not require that the channel intersymbol interference be finite. After briefly describing the (M, L) algorithm, the authors motivate the problem of equalization of infinite-impulse-response channels by considering the performance of a discrete-time single-pole channel filtering a binary input sequence. The state variable description of a linear system is used to analyze the filtered modulation. The state of the filtered modulation for a given input modulation is used to define the tree structure of the filtered signal upon which the (M, L) algorithm operates. The minimum signal space distance results for several filtered CPM schemes are then summarized. Extensive simulation results are presented, and comparisons to the optimal performance are made.>

The least storage and node computation required by a breadth-first tree or trellis decoder that corrects t errors over the binary symmetric channels is calculated. Breadth-first decoders work with code paths of the same length, without backtracking. The Viterbi algorithm is an exhaustive trellis decoder of this type; other schemes look at a subset of the tree or trellis paths. For random tree codes, theorems about the asymptotic number of paths required and their depth are proved. For concrete convolutional codes, the worst case storage for t error sequences is measured. In both cases the optimal decoder storage has the same simple dependence on t. The M algorithm and algorithms proposed by G.J. Foschini (ibid., vol.IT-23, p.605-9, Sept. 1977) and by S.J. Simmons (PhD. diss., Queens Univ., Kingston, Ont., Canada) are optimal, or nearly so; they are all far more efficient than the Viterbi algorithm.>

The decision depth function of a convolutional code L/sub D/(w) is the first trellis depth at which all unmerged incorrect subset paths exceed weight w. The authors tabulate this function for most codes in common use. L/sub D/(w) specifies the path memory length of a decoder. It follows a clear asymptotic growth rule.>

The minimum distance and hence the asymptotic error probability of trellis modulation codes that have been subjected to severe channel filtering are evaluated. A general algorithm is proposed for this purpose and applied to one class of coded modulations. Using a frequency-domain interpretation of the Euclidean distance, it is shown that under extreme channel band limitations, the error event that causes the minimum distance is characterized by a spectral null at DC. Numerical results show that for filtered continuous-phase-modulation codes, decreasing the modulation index or smoothing the frequency pulse does not improve the error performance. For some of these modulations, channel filtering can actually improve the minimum distance. Bandpass and low-pass filtering are contrasted. The numerical results are explained by power spectrum considerations.>

This paper documents the laboratory and theoretical performance of a pilot-aided digital radio system. The technique considered transmits a midband pilot tone to improve the receiver data detection performance in a multipath fading channel and is referred to as the tone calibrated technique (TCT). We report on the performance of a 860 MHz prototype system carrying 2.4 kbit/s data under Rician fading conditions. Both experimental and analytical results show that the error floor experienced with nonpilot-aided transmission methods is effectively removed by the TCT scheme, resulting in significant performance gains at high signal-to-noise ratio (SNR) values. The paper also examines the TCT system performance under typical operating conditions and presents a new analysis of the TCT theoretical error probability.

The cost of a number of sequential coding search algorithms is analyzed in a systematic manner. These algorithms search code trees, and find use in data compression, error correction, and maximum likelihood sequence estimation. The cost function is made up of the size of and number of accesses to storage. It is found that algorithms that utilize sorting are much more expensive to use than those that do not; metric-first searching regimes are less efficient than breadth-first or depth-first regimes. Cost functions are evaluated using experimental data obtained from data compression and error correction studies.

Code tree search algorithms find wide applicability in source encoding, channel decoding, pattern recognition, and maximum likelihood sequence estimation. These algorithms search code trees and may be classified as depth-first, breadth-first, and metric-first depending on the search criterion employed. We define here a criterion for metric-first algorithms to be optimal. We show that implementations of metric-first searches proposed heretofore are not optimal, and we propose and analyze two algorithms which are. Experimental data obtained by encoding a voiced speech sound point to superiority of the proposed implementation over earlier versions.

Recent results have established that DPCM is quite inefficient when encoding tightly correlated autoregressive sources at low rates. This work presents a slightly more complex code generator based on interpolation for rate 1 encoding of such sources and evaluates its performance via simulation for Gaussian and Laplacian distributed general stationary autoregressive sources. Improvements in the range of 3 dB over the LMS predictive quantizer for speech-like correlated sources at rate 1 have been realized with no tree searching. Another 1 dB is gained with a moderate tree searching. The code generator is less sensitive to the quantizer step size and a locally mismatched source than DPCM, two desirable features for encod, ing quasi-stationary sources.

The performance of differential pulse-code modulation and random codes is evaluated experimentally for a range of autoregressive sources, including Gaussian and Laplacian sources of orders1, 2, and3encoded at rates1, 2, and7. Correlations are typical of those encountered in speech and images. Results show that the gain from a fixed moderate degree of code searching increases as the rate decreases, and increases consistently with1 /D_{o}, whereD_{o}is the Berger-Gray critical distortion. Laplacian and Gaussian sources behave similarly. Random codes perform better than DPCM codes for lightly correlated Laplacian sources but are otherwise worse.

Constant envelope phase varying sinusoids of the form\sqrt{2E/T} \cos(\omega_{c}t + \phi(t))are studied, in which the phase function\phi(t)follows some coded pattern in response to data. Power and bandwidth performance are studied for such patterns. The patterns depend on a phase shaping function, a modulation index (h), and a sequence ofM-ary underlying changes in phase which are chosen at random. A cutoff rate-like parameter R0is computed, which guarantees existence of codes at all ratesR < R_{0}bits/T-interval whose error performance varies as exp[-N(R_{0} - R)], whereNis the code word length inT-intervals. Plots of R0are given as a function of interval energyE, the shaping functionhandM. Extensive spectral calculations give the spectra of these phased sinusoids, and their performance is plotted in the power-bandwidth plane. The results give strong evidence that phase codes can approximate any power-bandwidth combination consistent with Shannon's Gaussian channel capacity, and that linear channels are not required for narrow-band transmission.

Multi-hphase coded signals are constant-envelope sinusoids whose phase varies in a piecewise linear manner driven by cyclically chosen slopes. The transmission of these over a Gaussian noise channel with Viterbi decoder is simulated. Decoded error events are of two types normal and long, but in either case only a few bit errors are caused; events are empirically independent, they do not propagate, and their frequency is that predicted by signal space theory. Power gain compared to MSK modulation varies from1.5dB at bit error rate0.05to4dB at0.0001.

The performance and complexity of tree encoding of images in the presence of channel errors is considered. We demonstrate that a variation of the(M, L)algorithm yields performance close to the rate-distortion bound in the absence of channel errors for synthetic images modeled as two-dimensional autoregressive random fields. Trade-offs in optimizing the choice of tree search parameters are described, and experimental results on real-world images are presented. Simple tree search procedures are shown to provide signal-to-noise improvements in excess of 5 dB over conventional two-dimensional DPCM at the important rate of one bit/pixel; the effect is clear and striking to the eye. Channel error effects are treated by computer simulation and demonstrate signal-to-noise ratio improvement as high as 8 dB using tree encoding. Finally, a combined source-channel coding approach is described that exploits the significant trade-offs between source quantization accuracy and vulnerability to channel errors.

A metric-first tree coding algorithm, similar to the stack algorithm, is used to encode voiced speech. From experimental evidence, it is shown how to optimize the algorithm's performance with respect to the algorithm's storage, execution time, and number of tree branches searched per symbol released as output. For each of these, the optimal parameterizing of the algorithm differs markedly. Similarities are pointed out between our results for speech and earlier theoretical results for the binary i.i.d, source with Hamming distortion measure. Comparisons to theMalgorithm are made.

A new class of codes in signal space is presented, and their error and spectral properties are investigated. A constant-amplitude continuous-phase signal carries a coded sequence of linear-phase changes; the possible signal phases form a cylindrical trellis in phase and time. Simple codes using 4-16 phases, together with a Viterbi algorithm decoder, allow transmitter power savings of 2-4 dB over binary phase-shift keying in a narrower bandwidth. A method is given to compute the free distance, and the error rates of all the useful codes are given. A software-instrumented decoder is tested on a simulated Gaussian channel to determine multiple error patterns. The error parameterR_{o}is computed for a somewhat more general class of codes and is shown to increase rapidly when mere phases are employed. Finally, power spectral density curves are presented for several codes, which show that this type of coding does not increase the transmitted signal bandwidth.

Recent work has shown the usefulness of sequential or "tree" encoding of speech. We report on construction of a TTL hardware multi-path sequential encoder which uses the so-calledMalgorithm search procedure. The device attains a signal-to-noise ratio of about 20 dB at 16 kbits/s. Hardware peculiar to this type of encoder is discussed, including architecture of the search algorithm sorter, the squared error calculator, and the code generator.

Speeds of computation divergence as distortion tends to the rate-distortion limit are determined for three recent sequential source coding algorithms. The speeds follow from analysis and simulation; they remain unchanged for several sources and rates. The stack algorithm is most efficient in terms of nodes extended per encoder output digit.

Recently developed methods of tree source coding with a fidelity criterion are applied to speech coding. We first demonstrate that tree codes are inherent in A-D speech convertors of the waveform following type and point to ordinary and adaptive delta modulation and differential pulse code modulation (DPCM) as examples. Insights of coding theory improve these trees at low rates; we offer two new code classes, one obtained by smoothing the DPCM tree and one using the rate-distortion theory of autoregressive sources. Using these codes, we study the performance of a simple synchronous tree searching algorithm called theM-algorithm that maintains a small fixed number of paths in contention. 1 and 2 bit/sample code trees, used to encode actual speech at 8, 10, and 16 kbits/s, yield improved dynamic range and channel error resistance, and 4-8 dB improvement in mean-square error (mse) over ordinary single-path searched DPCM. These improvements in excess of analytical estimates suggest that tree coding methods perform better with real-life sources than previously thought.

A new scheme for encoding source information with respect to a fidelity criterion by tree codes is analyzed. Taking its design from earlier stack sequential decoders for channels, the algorithm keeps a stack of code tree paths of variable lengths ordered by a metric. It repeatedly extends the topmost path and reorders, until the topmost rises above a given metricA. The analysis uses difference equations, both linear and nonlinear; a commonly occurring nonlinear equation is solved asymptotically for the first time. The distribution of the worst metric to appear at the stack top is found to fall off faster than exponentially below a specifiable metric, whenever the encoder performance lies above the rate-distortion limit. Next, development of the top path is found to follow asymptotically a certain trajectory in the length-metric plane; this leads to a tight bound on path length released at termination. Finally, difference equations are written to bound the nodes searched. The work concludes with numerical calculations and simulations for the binary lid source with Hamming distortion measure. Comparison is made to other algorithms.

Since the birth of rate-distortion theory with the landmark paper of Shannon, research has centered on the extension of his theory to new situations and on the calculation of rate-distortion functions. Comparatively little has been done toward developing efficient algorithms for encoding information sources at rates near Shannon's rate-distortion limit. This paper reports one such algorithm, the 2-cycle algorithm, used with randomly chosen tree codes. In analyzing the 2-cycle algorithm, we present the first theoretical analysis of a realizable algorithm for tree coding of sources with a fidelity criterion. The algorithm may prove to be the first practical method of coding whose design actually derives from rate-distortion theory. Analysis proceeds by bounding methods related to difference equations and branching processes. Upper bounds on average distortion and encoding work are obtained and the latter are shown bounded as long as the coding rate exceeds Shannon's rate-distortion function. Of particular interest is the stack-searched branching process bound of Section IV. The two cycles of the algorithm are described fully in terms of expectations and probabilities, and recursions are listed to compute these quantities. Concluding the paper is numerical analysis, by theory and by simulation, with respect to the binary i.i.d, source and Hamming distortion measure. These numerical results are sufficient to optimize the algorithm over its free parameters.

We study here the use of tree codes to encode time-discrete memoryless sources with respect to a fidelity criterion. An easily instrumented scheme is proposed for use with binary sources and the Hamming distortion metric. Results of simulation with random and convolutional codes are given.