Student: Viola Wing Sum Lai, MASc

The PDF file of this thesis

Abstract: We have applied ARQ scheme to slow fading environment and use Turbo Codes as the coding method. If the system can tolerate certain delay, ARQ scheme would help to decrease the probability of bits received in error. The concept of different levels of bits in the signal constellation offering different levels of protection is being discussed in this thesis. We also proposed two ARQ schemes based on this protection concept. In the first proposed method, we proposed to change the constellation during the second transmission to take advantage of different bit protection level. The bit probabilities of both transmissions are combined and send to the Turbo decoding in order to increase the accuracy of decoding.

The results show that changing the constellation and combining the probabilities would outperform traditional retransmission. In the second proposed method, different levels of bits are separated into different frames and are decoded separately. The result shows that the proposed method increases the throughput of the system under low signal-noise-ratio.

Student: Ali Abedi, PhD

The PDF file of this thesis

Abstract: Certain properties of optimal bitwise APP (A Posteriori Probability) decoding of binary linear block codes are studied. The focus is on the Probability Density Function (pdf) of the bit Log-Likelihood-Ratio (LLR). A general channel model with discrete (not necessarily binary) input and discrete or continuous output is considered. It is proved that under a set of mild conditions on the channel, the pdf of the bit LLR of a specific bit position is independent of the transmitted code-word. It is also shown that the pdf of a given bit LLR, when the corresponding bit takes the values of zero and one, are symmetric with respect to each other (reflection of one another with respect to the vertical axis). In the case of channels with binary inputs, a sufficient condition for two bit positions to have the same pdf is presented. An analytical method for approximate performance evaluation of binary linear block codes using an Additive White Gaussian Noise (AWGN) channel model with Binary Phase Shift Keying (BPSK) modulation is proposed. The pdf of the bit LLR is expressed in terms of the Gram-Charlier series expansion. This expansion requires knowledge of the statistical moments of the bit LLR. An analytical method for calculating these moments which is based on some recursive calculations involving certain weight enumerating functions of the code is introduced. It is proved that the approximation can be as accurate as desired, using enough numbers of terms in the Gram-Charlier series expansion.

A new method for the performance evaluation of Turbo-Like Codes is presented. The method is based on estimating the pdf of the bit LLR by using an exponential model. The moment matching method is combined with the maximum entropy principle to estimate the parameters of the new model. A simple method is developed for computing the Probabilities of the Point Estimates (PPE) for the estimated parameters, as well as for the Bit Error Rate (BER). It is demonstrated that this method requires significantly fewer samples than the conventional Monte-Carlo (MC) simulation.

The PDF file of this thesis

Abstract: Turbo coding is a powerful encoding and decoding technique that can provide highly reliable data transmission at extremely low signal-to-noise ratios. According to the computational complexity of the employed decoding algorithms, such as MAP, BCJR and APP, the realization of turbo decoders usually takes a large amount of memory spaces and potentially long decoding delay. Therefore, an efficient memory management strategy becomes one of the key factors toward successfully designing turbo decoders. Either the forward or the backward path metric needs to be stored for the whole frame. In this thesis, reducing memory requirement of turbo decoding algorithms is approached by two methods. The first method tries to find a proper quantization scheme for storing trellis variables in turbo decoding stage. Uniform and non-uniform schemes are the broad classes of quantization schemes studied. The average distortion measure is computed for some of the quantization schemes.

The second method proposes a technique to reduce the storage of the path metrics in MAP algorithm's trellis. The novelty in this technique is to calculate MAP algorithm's forward path metric alpha in backward by utilizing matrix inversion. In this way, most path metrics are calculated as needed with only a small portion of those metrics drawn from memory. This method will reduce the memory requirement by at least 50% without big impact on the system performance while incurring a small penalty in computation complexity.

The PDF file of this thesis

Abstract: The error probability of Maximum-Likelihood (ML) soft-decision decoded binary block codes rarely accepts nice closed forms. In addition, for long codes ML decoding becomes prohibitively complex. Nevertheless, bounds on the performance of ML decoded systems provide insight into the effect of system parameters on the overall system performance as well as a measure of efficiency of the suboptimum decoding methods used in practice. In this dissertation, using the so-called Gallager's first bounding technique (involving a so-called Gallager region) and within the framework of Tangential Sphere Bound (TSB) of Poltyrev, a general bound referred to as the Generalized Tangential Sphere Bound (GTSB) is developed. The Gallager region is chosen to be a general Hyper-Surface of Revolution (HSR) which is optimized to tighten the bound. The search for the optimal Gallager region is a classical problem dating back to Gallager's thesis in the early 1960's. For the random coding case, Gallager provided the optimal solution in a closed form while for the non-random case the problem has been an active area of research in information theory for many years.

GTSB is applied to two problems. First, to the word error probability of BPSK-modulated binary block codes with ML decoding, and second, to the nonuniform signaling of binary block codes with Maximum-A-Posteriori (MAP) decoding. For both, the optimum HSR is obtained and it is noted that in the former case the resulting bound is the TSB of Poltyrev which has been the tightest bound developed for binary block codes to date. This terminates the search for a better Gallager region in the groundwork of the GTSB for the underlying application.
In the development of TSB, union bound which is the simplest inequality from the large class of so-called Bonferroni-type inequalitiesin probability theory is utilized. In this work, first, a new 2nd-order Bonferroni-type inequality is proposed, and then, a new upper bound on the word error probability of sphere codes is developed within the framework of Gallager's First Bounding Technique (GFBT) and the new Bonferroni-type inequality. The resulting bound in its first version is rather complicated as it requires the global geometrical properties of the code.
Subsequently, a second version of the above upper bound, referred to as the Added-Hyper-Plane (AHP) bound, is presented. This bound is very simple as it only requires the spectrum of the code. For some long binary block codes, improvements over the TSB of Poltyrev are reported; making the bound the new tightest bound on the performance of ML-decoded binary block codes.

The PDF file of this thesis

Abstract: In this thesis, the application of Adaptive Modulation and Coding (AMC) for 3rd-Generation (3G) wireless systems is addressed. A new method for selecting the appropriate Modulation and Coding Schemes (MCS) according to the estimated channel condition is proposed.

In this method, a statistical decision making approach is taken to maximize the average throughput while maintaining an acceptable Frame Error Rate (FER). A first-order finite-state Markov model is used to represent the average channel Signal-to-Noise Ratio (SNR) in subsequent frames. The MCS is selected in each state of this Markov model (among the choices proposed in the 3G standards) to maximize the statistical average of the throughput in that state. Using this decision-making approach, a simplified Markov model with fewer parameters is also proposed. This model is suitable in AMC systems where changes in the fading characteristics need to be accounted for in an adaptive fashion. Numerical results are presented showing that both of the proposed models substantially outperform the conventional techniques that use a threshold-based decision making.

The PDF file of this thesis

Abstract: This work presents the application of several important concepts of digital communications, i.e., serial concatenation, turbo principle, temporal and antenna diversity, in a wireless system. It has been shown that employing each of the above concepts gives an improvement in performance of the system.

We expect that by employing all of them in a framework properly, we achieve a system with better performance than a system employing each concept individually. Serial concatenation of a turbo code with a space-time block code is considered and turbo principle (iterative demodulation/decoding) is applied. Simulation results show the gain in performance as we expected.

The PDF file of this thesis

Abstract: A fundamental problem in telecommunications is the reliable transmission of a source over a noisy channel. As an important result of the Shannon's celebrated paper shannon, the problem can be theoretically separated, without loss of optimality, into two parts: source coding and channel coding. However, in practise, due to the strict design constraints, such as the limitations on complexity of the systems involved, the joint design of source and channel coders has found increasing interest.

This thesis deals with the design of efficient reliable communication systems with a particular emphasis on practical issues such as complexity and delay. A low bit-rate low complexity Block-based Trellis Quantization (BTQ) scheme is proposed for the quantization of speech spectrum in speech coding applications. The proposed scheme is based on the modeling of the LSF intraframe dependencies with a trellis structure. The BTQ search and design algorithms are discussed and an efficient algorithm for the index generation is proposed. Extensive comparisons with several other techniques from the literature are provided.

Efficient source decoding schemes are presented, which take advantage of the residual redundancy in the source coder output stream as a bandwidth efficient way to combat the noisy channel degradations. This falls into the category of joint source channel (de)coding. In this part, a family of solutions is proposed for the asymptotically optimum Minimum Mean Squared Error (MMSE) reconstruction of a source over memoryless noisy channels when the residual redundancy is exploited by use of a gamma-order Markov model gamma >= 1 and a delay of delta is allowed in the decoding process. Considering the same problem setup, several other simplified MMSE and maximum a posteriori symbol and sequence decoders are also presented.
The problem of reconstruction of the predicatively quantized signals over a noisy channel is also considered. As well, methods for the reconstruction of speech encoded with the Enhanced Full Rate Codec (EFRC, IS-641) and transmitted over a noisy channel are presented. A methodology to efficiently approximate and store the a priori probabilities characterizing the residual redundancies is introduced. Numerical results are presented which demonstrate the efficiency of the proposed algorithms.

The PDF file of this thesis

Abstract: The fixed-rate entropy-constrained vector quantizer draws its motivation from the large gap in the performance of the optimal entropy-constrained scalar quantizer (ESCQ) and the fixed-rate LMQ for most non-uniform sources and tries to bridge this gap while maintaining a fixed-rate output. Having a fixed-rate output avoids all problems associated with a variable rate output such as error propagation and buffering.

For the task of codebook search in a fixed-rate entropy-constrained quantizer, one can use the dynamic programming approach to achieve an optimum performance. However, for high dimension and rates, the implementation complexity of dynamic programming approach is not affordable by the most practical systems.

In this thesis, we introduce two new low complexity algorithms for the codebook search in a fixed-rate entropy-constrained vector quantizer. It is shown that both schemes are offering the same performance as that of dynamic programming approach while they are reducing the complexity substantially (for most important class of sources). We also propose a decoder for the fixed-rate entropy-constrained vector quantizer to improve its performance in transmission over a noisy channel. In order to add quantization packing gain, we apply the idea of tail-biting to the trellis coded quantization combined with fixed-rate entropy-constrained quantization. The tail-biting trellis significantly reduces the required block length and also mitigates the effect of error propagation.

Abstract: This thesis aims at providing results and insight towards the application of turbo-codes in digital communication systems, mainly in three parts. The first part considers systems of combined turbo-code and modulation. This section follows the pragmatic approach of the first proposed such system. It is shown that by optimizing the labeling method and/or modifying the puncturing pattern, improvements of more than 0.5 dB in signal to noiseratio (SNR) are achieved at no extra cost of energy, complexity, or delay. Conventional turbo-codes with binary signaling divide the bit energy equally among the transmitted turbo-encoder output bits. The second part of this thesis proposes a turbo-code scheme with unequal power allocation to the encoder output bits. It is shown, both theoretically and by simulation, that by optimizing the power allocated to the systematic and parity check bits, improvements of around 0.5 dB can be achieved over the conventional turbo-coding scheme.

The third part of this thesis tackles the question of "the sensitivity of the turbo-code performance towards the choice of the interleaver", which was brought up since the early studies of these codes. This is the first theoretical approach taken towards this subject. The variance of the bound is evaluated. It is proven that the ratio of the standard deviation over the mean of the bound is asymptotically constant (for large interleaver length, N), decreases with N, and increases with SNR. The distribution of the bound is also computationally developed. It is shown that as SNR increases, a very low percentage of the interleavers deviate quite significantly from the average bound but the majority of the random interleavers result in performances very close to the average. The contributions of input words of different weights in the variance of performance bound are also evaluated. Results show that these contributions vary significantly with SNR and N. These observations are important when developing interleaver design algorithms.

The PDF file of this thesis

Abstract: The suitability of general constrained quadratic optimization as a modeling and solution tool for wireless communication is discussed. It is found to be appropriate due to the many quadratic entities present in wireless communication models. It is posited that decisions which affect the minimum mean squared error at the receiver may achieve improved performance if those decisions are energy constrained. That theory is tested by applying a specific type of constrained quadratic optimization problem to the forward link of a cellular DS-CDMA system. Through simulation it is shown that when channel coding is used, energy constrained methods typically outperform unconstrained methods. Furthermore, a new energy-constrained method is presented which significantly outperforms a similar published method in several different environments.

The PDF file of this thesis

Abstract: The modeling of the soft-output decoding of a binary linear block code using a Binary Phase Shift Keying (BPSK) modulation system (with reduced noise power) is the main focus of this work. With this model, it is possible to provide bit error performance approximations to help in the evaluation of the performance of binary linear block codes. As well, the model can be used in the design of communications systems which require knowledge of the characteristics of the channel, such as combined source-channel coding. Assuming an Additive White Gaussian Noise channel model, soft-output Log Likelihood Ratio (LLR) values are modeled to be Gaussian distributed. The bit error performance for a binary linear code over an AWGN channel can then be approximated using the Q-function that is used for BPSK systems. Simulation results are presented which show that the actual bit error performance of the code is very well approximated by the LLR approximation, especially for low signal-to-noise ratios (SNR) .A new measure of the coding gain achievable through the use of a code is introduced by comparing the LLR variance to that of an equivalently scaled BPSK system.

Furthermore, arguments are presented which show that the approximation requires fewer samples than conventional simulation methods to obtain the same confidence in the bit error probability value. This translates into fewer computations and therefore, less time is needed to obtain performance results. Other work was completed that uses a discrete Fourier Transform technique to calculate the weight distribution of a linear code. The weight distribution of a code is defined by the number of codewords which have a certain number of ones in the codewords. For codeword lengths of small to moderate size, this method is faster and provides an easily implement able and methodical approach over other methods. This technique has the added advantage over other techniques of being able to methodically calculate the number of codewords of a particular Hamming weight instead of calculating the entire weight distribution of the code.

The PDF file of this thesis

Abstract: The topic of interference cancellation in a coded Code Division Multiple Access (CDMA) system has been the focus of much recent research. Earlier works have studied methods for jointly decoding all the users resulting in most having an exponential complexity for the corresponding receiver. In this thesis, a number of different iterative decoding methods are proposed for the multi-user interference cancellation in a CDMA system where Turbo Codes are utilized for forward error correction. In the proposed decoding schemes, the individual users are decoded separately with the operation of iterative interference cancellation being mixed with the iterative decoding of Turbo Codes.

These iterative decoders result in only a marginal increase in the overall complexity as compared to a conventional single user receiver utilizing Turbo Codes for forward error correction. Numerical performance results are presented showing that in the cases of practical interest for CDMA applications, the multiple access interference can be essentially removed at a reasonable level of complexity. These iterative decoders achieve a similar to better performance with a reduction in complexity as compared to similar previously known research work.

Abstract: Standard fractal image coding methods seek to find a contractive fractal transform operator T that best scales and copies subregions of a target image I onto smaller subimages. The attractor of this operator is an approximation to the image I and can be generated by iteration of T. For most of the standard fractal-based schemes, the transform coefficients exhibit some degree of linear dependence which can be exploited by using an appropriate vector quantizer such as the LEG algorithm. Additional compression can be achieved by lossless Huffman coding of the quantized coefficients. Although good fidelity is generally achieved at relatively high compression ratios, standard fractal schemes in the spatial domain are not without limitations. Some of the disadvantages of the con- ventional fractal schemes include expensive computational requirement and blockiness artifacts in fractal representation of images. This inspired the introduction of fractal-wavelet transforms which operate on the wavelet domain of images: Wavelet coefficient subtrees are scaled and copied onto lower subtrees. In spite of their numerous advantages, these fractal-wavelet schemes can still be rather restrictive in the sense that they adopt the standard three-subband wavelet tree decomposition. This results in a static representation for each level that varies significantly from one level to the next. However , intermediate approximations may be desired, perhaps for purposes of "bit-budgeting" . We propose and implement an adaptive and unrestricted fractal-wavelet scheme that adopts a dynamic partitioning of the wavelet decomposition tree, resulting in intermediate representation between the various levels. Some of the benefits of such a simple and adaptive fractal-wavelet scheme include: Generating a continuous and relatively smooth rate distortion curve for fractal-wavelet schemes, and encoding images at a pre-defined bit rate or representation tolerance error.

Abstract: A switched lattice-based quantizer for the quantization of speech LSF parameters is presented. LSF difference values are first quantized using a scalar quantizer, as well as a two dimensional vector quantizer, and subsequently adjusted for a lower bit-rate using a lattice. Euclidean distance is used as the distortion measure for the design, while a spectral distortion measure is used for the evaluation of the performance. LSF differences are formed in a closed loop manner for which a first-order prediction filter is used. The parameters for the prediction filter are calculated from a LSF database. Lattice-based double frame and single frame quantization is performed for each frame and the one which results in a lower distortion is chosen. Numerical results are presented showing an excellent performance with very low complexity. The results are compared to the split vector quantizer using common database for test and training showing substantial improvement. Finally, the issue of the robustness to channel errors is investigated.

Abstract: Compression schemes suitable for use in (personal) wireless communication systems are investigated in this thesis. The aim of the thesis is to identify techniques which meet the specific requirements of the personal wireless communication environment.

A lossless data compression algorithm is presented. The algorithm is based on a recent transform technique due to Burrows and Wheeler. It is shown that the algorithm has signifi- cantly improved compression when compared to the V.42bis algorithm which is the industry standard for wireline communication devices. Speech compression is also investigated. In particular, efficient quantization techniques for transmitting speech model parameters ( the Linear Prediction Coefficients) are described. It is shown that quantizing an equivalent set of speech model parameters, Line Spectral Pairs, is more efficient than quantizing the Linear Prediction Coefficients themselves. Various quantization techniques for Line Spectral Pairs are investigated. It is shown that an integer lattice quantization technique, Pyramid Vector Quantization introduced by Fischer, gives a low computational complexity quantizer with competitive performance in terms of the compression ratio (bits used per speech frame) and the distortion introduced by the quantizer . Finally, it is shown that the performance of the Pyramid Vector Quantizer can be improved through the use of the DII lattice to replace the Zll lattice used by Fischer.

The PDF file of this thesis

Abstract: A new method of combined source-channel coding using Turbo-codes is presented. The system presented is designed to transmit a discrete time, continuous amplitude signal over an Additive White Gaussian Noise (AWGN) channel where a Turbo-code is used for error correction purposes. The proposed system takes advantage of the available reliability information (generated by the Turbo decoder) to improve the quality of the reconstructed signal. The design rules for a quantizer and reconstructor to minimize the overall mean square distortion are presented. Numerical results are presented showing up to 1 dB improvement in the end-to-end distortion with respect to a traditional channel optimized quantizer. This improvement is obtained at the price of a small increase in the system complexity.

The PDF file of this thesis

Abstract: This thesis studies a new method of combining Turbo Codes with various modulation techniques to take advantage of inherent tradeoffs between BER performance, code rate, spectral efficiency and decoder complexity. Our new method, which we call Symbol-Based Turbo Codes, parses the parallel data streams of the Turbo Code encoder into n-bit symbols and maps each symbol to a point in a 2n-ary signal set. In the case of Symbol-Based Turbo Codes with BPSK modulation, the BER performance can be improved while at the same time decreasing the decoder complexity as compared with the traditional Turbo Code.

Symbol-Based Turbo Codes are good candidates for spread spectrum communication systems such as CDMA. Specifically, Symbol-Based Turbo Codes with orthogonal modulation are suitable for a non-coherent up-link, or bi-orthogonal modulation for a coherent up-link. Furthermore, Symbol-Based Turbo Codes with either M-ary PSK modulation or BPSK modulation are suitable for a coherent down-link.

Abstract: Recently, C. Berrou, A. Glavieux, and P. Thitimajshima introduced an advanced class of concatenated codes named Turbo-codes. These codes provide outstanding performance and can achieve near-Shannon limit error correcting performance with relatively simple component codes and large pseudo-random interleavers. In this thesis, three concatenated coding methods are designed and evaluated. In the first two schemes, concatenated coding systems which consists of Turbo-codes in serial concatenation with Reed-Muller (RM) codes are introduced. The first system, I called Turbo-Reed-Muller code, uses a Turbo-code as an outer code and a Reed-Muller code as an inner code. These codes provide up to 0.51dB improvement over a Turbo-code at a Bit-Error-Rate (BER) of 10-3 during the 20th iteration. The second system, called Reed-Muller-Turbo code, uses a Turbo-code as an inner code and an Reed-Muller code as an outer code. These codes show a performance improvement over the Turbo-code of up to 1dB at a BER of 10-5. Furthermore, a general method for soft decision decoding of product codes is introduced using the example of a (12,8,3) Hamming code in combination with a single parity check and another (12,8,3) Hamming code. At a BER of 10-5, this scheme performs 3dB better than hard decision decoding and 2.3dB better than soft decision decoding of the (12,8,3) Hamming code.

Abstract: Decoding operation is the major obstacle associated with using a lattice in communication applications. There are two general methods for lattice decoding: i) The integer programming method based on geometry of numbers, and ii) The trellis method. This thesis has contributions to both methods, and provides results which make the comparison between the two methods possible. Regarding method (i), Kannan's algorithm, which is currently known as the fastest method for the decoding of a general lattice, is analyzed. Based on a geometrical interpretation of this algorithm, it is shown that it is a special case of a wider category of algorithms, called recursive cube search (RCS) algorithms. In this category, we improve Kannan's algorithm, and establish tight upper and lower bounds on the decoding complexity of lattices. The lower bounds prove that the RCS decoding complexity of any sequence of lattices with possible application in communications increases at least exponentially with dimension and coding gain.

Regarding method (ii), we discuss and develop a universal approach to the construction and analysis of the trellis diagrams of lattices using their bases. Based on this approach, we derive tight upper bounds on the trellis complexity of lattices, and study the problem of finding minimal trellis diagrams for lattices. The upper bounds both improve and generalize the previously known similar results. Minimal trellis diagrams for many important lattices are also constructed. These trellises, which are novel in many cases, can be employed to efficiently decode the lattices via the Viterbi algorithm. Moreover, we establish tight lower bounds on the trellis complexity of lattices. For many of the obtained trellises, these lower bounds provide a proof for minimality.  Finally, we derive some results in lattice theory with possible application in communications. These include an upper bound on covering radius of a lattice in terms of its successive minima, and an inequality on the coding gain of densest lattice packings in successive dimensions.

The PDF file of this thesis

Abstract: This work considers a combined source-channel coding scheme for image transmission over the uplink of a wireless IS-95 CDMA channel. By adjusting the dimension of the orthogonal signaling scheme, we trade the system error-correction capability for a faster bit rate. The increase in channel error is relieved by employing a set of quantizers which are designed using a joint source-channel optimization algorithm. The bit allocation problem of the quantizer array is solved by using a new approach based on integer programming technique. Without bandwidth expansion, our proposed scheme results in a substantial improvement in the reconstructed image quality, especially for good channel condition.