The availability of feedback in communication channels can significantly increase the reliability of transmission while decreasing the encoding and decoding complexity. Most of the applications like cellular telephony, satellite communications and internet involve two-way transmission. Hence, it is important to devise coding schemes which utilize the advantages of feedback. Most of the results in code designs, which make use of feedback, concentrate on noiseless and instantaneous feedback. But in real-time systems, the feedback is usually noisy, and is available at the transmitter after some delay. Hence, it is important that we characterize the gains obtained in this case over that of one-way channels. We consider binary erasure channels to keep the problem tractable. For the erasure channels with noisy feedback, we have designed and analyzed a concatenated coding scheme, which achieves lower probability of error than any forward error correcting code of the same rate. Hence, it is shown that even noisy feedback can be useful in increasing the reliability of the channel. We have designed and analyzed a coding scheme using Low Density Parity Check (LDPC) codes along with selective retransmission strategy, which utilizes the limited (but noiseless), delayed feedback to achieve low frame error rates even with small blocklengths, at rates close to capacity. Furthermore, our scheme provides a way to trade off feedback bandwidth for reliability. The complexity of this scheme is lower than that of a forward error correcting code (FEC) of same blocklength and comparable performance. We have shown that our scheme performs better than the Automatic Repeat Request (ARQ) protocol which makes use of 1 bit feedback to signal retransmissions. For fair comparisons, we have also incorporated the rate loss due to the bits which are fed back in addition to the retransmitted bits. Thus, we have shown that for two-way communications with complexity and delay constraints, it is better to utilize the availability of feedback than to use just FEC.

Doctor of Philosophy / Department of Electrical and Computer Engineering / Don M. Gruenbacher / Future technologies such as cognitive radio require flexible and reliable hardware architectures that can be easily configured and adapted to varying coding parameters. The objective of this work is to develop a flexible hardware encoder and decoder for low-density parity-check (LDPC) codes. The design methodologies used for the implementation of a LDPC encoder and decoder are flexible in terms of parity-check matrix, code rate and code length. All these designs are implemented on a programmable chip and tested. Encoder implementations of LDPC codes are optimized for area due to their high complexity. Such designs usually have relatively low data rate. Two new encoder designs are developed that achieve much higher data rates of up to 844 Mbps while requiring more area for implementation. Using structured LDPC codes decreases the encoding complexity and provides design flexibility. The architecture for an encoder is presented that adheres to the structured LDPC codes defined in the IEEE 802.16e standard. A single encoder design is also developed that accommodates different code lengths and code rates and does not require re-synthesis of the design in order to change the encoding parameters. The flexible encoder design for structured LDPC codes is also implemented on a custom chip. The maximum coded data rate of the structured encoder is up to 844 Mbps and for a given code rate its value is independent of the code length. An LDPC decoder is designed and its design methodology is generic. It is applicable to both structured and any randomly generated LDPC codes. The coded data rate of the decoder increases with the increase in the code length. The number of decoding iterations used for the decoding process plays an important role in determining the decoder performance and latency. This design validates the estimated codeword after every iteration and stops the decoding process when the correct codeword is estimated which saves power consumption. For a given parity-check matrix and signal-to-noise ratio, a procedure to find an optimum value of the maximum number of decoding iterations is presented that considers the affects of power, delay, and error performance.

4 ABSTRACT Tremendous amount of research has been conducted in modern coding theory in the past few years and much of the work has been done in developing new coding techniques. Low density parity check (LDPC) codes are class of linear block error correcting codes which provide capacity performance on a large collection of data transmission and storage channels while Root LDPC codes in this thesis work are admitting implementable decoders with manageable complexity. Furthermore, work has been conducted to develop graphical methods to represent LDPC codes. This thesis implement one of the LDPC kind “Root LDPC code” using iterative method and calculate its threshold level for binary and non-binary Root LDPC code. This threshold value can serve as a starting point for further study on this topic. We use C++ as tool to simulate the code structure and parameters. The results show that non-binary Root LDPC code provides higher threshold value as compare to binary Root LDPC code. / postal address: Björnkullaringen 26, LGH 1029 14151 Huddinge Stockholm Sweden. Mobile: +46-720 490 967

ITC/USA 2008 Conference Proceedings / The Forty-Fourth Annual International Telemetering Conference and Technical Exhibition / October 27-30, 2008 / Town and Country Resort & Convention Center, San Diego, California / This paper considers the joint selection of the source code rate and channel code rate in an image telemetry system. Specifically considered is the JPEG2000 image coder and an LDPC code family. The goal is to determine the optimum apportioning of bits between the source and channel codes for a given channel signal-to-noise ratio and total bit rate, R(total). Optimality is in the sense of maximum peak image SNR and the tradeoff is between the JPEG2000 bit rate R(source) and the LDPC code rate R(channel). For comparison, results are included for the industry standard rate-1/2, memory-6 convolutional code.

This thesis investigates optimization of advanced telecommunication algorithms from power and performance perspectives. The algorithms chosen are MIMO and LDPC. MIMO is implemented in custom ASIC for power optimization and LDPC is implemented on dynamically reconfigurable fabric for both power and performance optimization. Both MIMO and LDPC are considered computational bottlenecks of current and future wireless standards such as IEEE 802.11n for Wi-Fi and IEEE 802.16 for WiMax applications. Optimization of these algorithms is carried out separately. The thesis is organized implicitly in two parts. The first part presents selection and analysis of the VBLAST receiver used in MIMO wireless system from custom ASIC perspective and identifies those processing elements that consume larger area as well as power due to complex signal processing. The thesis models a scalable VBLAST architecture based on MMSE nulling criteria assuming block rayleigh flat fading channel. After identifying the major area and power consuming blocks, it proposes low power and area efficient VLSI architectures for the three building blocks of VBLAST namely Pseudo Inverse, Sorting and NULLing & Cancellation modules assuming a 4x4 MIMO system. The thesis applies dynamic power management, algebraic transformation (strength reduction), resource sharing, clock gating, algorithmic modification, operation substitution, redundant arithmetic and bus encoding as the low power techniques applied at different levels of design abstraction ranging from system to architecture, to reduce power consumption. It also presents novel architectures not only for the constituent blocks but also for the whole receiver. It builds the low power VBLAST receiver for single carrier and provides its area, power and performance figures. It then investigates into the practicality and feasibility of VBLAST into an OFDM environment. It provides estimated data with respect to silicon real estate and throughput from which conclusion can easily be drawn about the feasibility of VBLAST in a multi carrier environment. The second part of the thesis presents novel architectures for the real time adaptive LDPC encoder and decoder as specified in IEEE 802.16E standard for WiMax application. It also presents optimizations of encoder as well as decoder on RICA (Reconfigurable Instruction Cell Architecture). It has searched an optimized way of storing the H matrices that reduces the memory by 20 times. It uses Loop unrolling to distribute the instructions spatially depending upon the available resources to execute them concurrently to as much as possible. The parallel memory banks and distributed registers inside RICA allow good reduction in memory access time. This together with hardware pipelining provides substantial potential for optimizing algorithms from power and performance perspectives. The thesis also suggests ways of improvements inside RICA architecture.

A high throughput scalable decoder architecture, a tiling approach to reduce the complexity of the scalable architecture, and two low power decoding schemes have been proposed in this research. The proposed scalable design is generated from a serial architecture by scaling the combinational logic; memory partitioning and constructing a novel H matrix to make parallelization possible. The scalable architecture achieves a high throughput for higher values of the parallelization factor M. The switch logic used to route the bit nodes to the appropriate checks is an important constituent of the scalable architecture and its complexity is high with higher M. The proposed tiling approach is applied to the scalable architecture to simplify the switch logic and reduce gate complexity. The tiling approach generates patterns that are used to construct the H matrix by repeating a fixed number of those generated patterns. The advantages of the proposed approach are two-fold. First, the information stored about the H matrix is reduced by onethird. Second, the switch logic of the scalable architecture is simplified. The H matrix information is also embedded in the switch and no external memory is needed to store the H matrix. Scalable architecture and tiling approach are proposed at the architectural level of the LDPC decoder. We propose two low power decoding schemes that take advantage of the distribution of errors in the received packets. Both schemes use a hard iteration after a fixed number of soft iterations. The dynamic scheme performs X soft iterations, then a parity checker cHT that computes the number of parity checks in error. Based on cHT value, the decoder decides on performing either soft iterations or a hard iteration. The advantage of the hard iteration is so significant that the second low power scheme performs a fixed number of iterations followed by a hard iteration. To compensate the bit error rate performance, the number of soft iterations in this case is higher than that of those performed before cHT in the first scheme.

Tα σύγχρονα τηλεπικοινωνιακά συστήματα έχουν υιοθετήσει κώδικες διόρθωσης λαθών με στόχο να αυξήσουν της αξιοπιστία των συστημάτων κατά τη μετάδοση πληροφορίας. Οι LDPC (Low-Density-Parity-Check codes) κώδικες είναι μία κατηγορία κωδίκων που πρόσφατα άρχισαν να απασχολούν την επιστημονική κοινότητα κι αυτό γιατί διαθέτουν εξαιρετικές επιδόσεις. Οι κώδικες αυτοί είναι γραμμικοί block κώδικες με απόδοση πολύ κοντά στο όριο του Shannon. Επιπλέον, ο εύκολος παραλληλισμός της διαδικασίας αποκωδικοποίησής τους, τους καθιστά κατάλληλους για υλοποίηση σε υλικό. Στην παρούσα διπλωματική μελετήθηκαν αρχικά τα ιδιαίτερα χαρακτηριστικά και οι παράμετροι των κωδίκων αυτών. Ο στόχος ήταν να σχεδιαστεί ένας αποκωδικοποιητής που να υποστηρίζει τα χαρακτηριστικά των LDPC κωδίκων που έχουν υιοθετηθεί από το DVB-S2. Με αυτό το στόχο υλοποιήθηκε στο System Generator(εργαλείο του Xilinx) ένας ημιπαράλληλος αποκωδικοποιητής. Η ημιπαράλληλη αρχιτεκτονική επιτρέπει καταλαμβάνοντας μικρή περιοχή του υλικού να δημιουργηθεί ένας αποκωδικοποιητής που να είναι εφικτό να χρησιμοποιείται από οποιοδήποτε κώδικα με χρήση των ίδιων λειτουργικών μονάδων και διαφορετικών μονάδων ελέγχου. Στην αποκωδικοποίηση χρησιμοποιήθηκε ο Min-Sum αλγόριθμος καθώς αυτός προσφέρει χαμηλή πολυπλοκότητα χωρίς να θυσιάζει αρκετά σε επίπεδο απόδοσης. Η σωστή λειτουργία ολόκληρου του σχεδιασμού επιβεβαιώθηκε με εξομοιώσεις στη Matlab. / Modern telecommunication systems have adopted error correction codes in order tor improve the reliability during information transmission. LDPC (Low-Density-Parity-Check codes) are a special group of codes with extremely good performance. These codes are linear block codes with performance near to the theoretical Shannon limit. Furthermore, the fact that the procedure of the decoding is easily parallelism makes them suitable for implementation on hardware. At the beginning of this thesis, the special characteristics and the parameters of these codes were stated. The main aim was to design a decoder that can be used for the DVB-S2 system. So, it was designed at System Generator a semi parallel decoder. The implementation of this architecture allows every code (block size, code rate) to be decoded, using the same functional units and different control units. Moreover this implementation requires small area but it is not possible to succeed high throughput. For the decoding process, Min-Sum Algorithm has been used, as it is the less complex algorithm for hardware implementations.The design has been successfully verified with simulations using Matlab.

This dissertation presents four technical contributions in the theory and practice of low-density parity-check (LDPC) codes and orthogonal frequency division multiplexing (OFDM) systems withtransmission non-linearity and with interference due to high mobility.We first explore the universality of LDPC codes for the binary erasure channel (BEC), the AWGN channel, and the flat Rayleigh fading channel. Using excess mutual information as a performance measure, we demonstrate that an LDPC code designed on a singlechannel can be universally good across the three channels. Thus, a channel for which LDPC code design is simple may be used as a surrogate for channels that are more challenging.Due to fast channel variations, OFDM systems suffer from inter-carrier interference (ICI) in frequency-selective fast fading channels. We propose a novel iterative receiver design that achieves near-optimal performance while maintaining a complexity that grows only linearly with the number of OFDM carriers. Weprove that the matched filter bound for such a channel is also the maximum-likelihood sequence detection (MLSD) bound.Because of the presence of high peaks at OFDM modulator output, amplitude clipping due to amplifier saturation causes performance degradation. We show that existing analyses underestimate the capacity of OFDM systems with clipping, and we analyze thecapacity of clipped OFDM systems with AWGN and frequency-selective Rayleigh fading. We prove that for frequency-selective Rayleigh fading channels, under certain conditions, there exists an SNR threshold, above which the capacity of a clipped system is higherthan that of an unclipped system. We provide upper and lower bounds on the channel capacity and closed-form approximations of discrete-input capacities with and without clipping.We also derive tight MLSD lower bounds and propose near-optimal receivers for OFDM systems with clipping. We show that over frequency-selective Rayleigh fading channels, under certain conditions, a clipped system with MLSD can achieve better performance than an unclipped system. We show that the MLSD boundscan be achieved or closely approached by the proposed low complexity receivers in various channel types.

This dissertation provides a comprehensive analysis of the coding-spreading tradeoff problem in finite-sized synchronous DS-CDMA systems. In contrast to the large system which has a large number of users, the finite-sized system refers to a system with a small number of users. Much work has been performed in the past on the analysis of the spectral efficiency of synchronous DS-CDMA systems and the associated coding-spreading tradeoff problem. However, most of the analysis is based on the large-system assumptions. In this dissertation, we focused on finite-sized systems with the help of numerical methods and Monte-Carlo simulations.Binary-input achievable information rates for finite-sized synchronous DS-CDMA systems with different detection/decoding schemes on AWGN channel are numerically calculated for various coding/spreading apportionments. We use these results to determine the existence and value of an optimal code rate for a number of different multiuser receivers, where optimality is in the sense of minimizing the SNR required for reliable multiuser communication. Our results are consistent with the well-known fact that all coding (no spreading) is optimal for the maximum a posteriori receiver.Simulations of the LDPC-coded synchronous DS-CDMA systems with iterative multiuser detection/decoding and MMSE multiuser detection/single-user decoding are also presented to show that the binary-input capacities can be closely approached with practical schemes. The coding-spreading tradeoff is examined using these LDPC code simulation results, where agreement with the information-theoretic results is demonstrated.We extend our work to the DS-CDMA systems on two idealized Rayleigh flat-fading channels: the chip-level flat-fading (CLFF) and the (code) symbol-level flat-fading (SLFF). These models represent ideal fast fading and slow fading channels, respectively. Both information-theoretic results and LDPC code simulation results are presented to show the effects of channel fading on system performance and the coding-spreading tradeoff. It is shown that fast fading can be beneficial to system performance under the condition of perfect channel state information at receiver, but slow fading is very harmful. Slow fading also increases the importance of coding greatly, compared to the AWGN and fast fading.Finally, we present some comparisons with large-system results on AWGN and CLFF channels, which show both consistencies and discrepancies.

No description available.