This thesis deals with the synchronization of digital communication systems. Synchronization (from the Greek syn (together) and chronos (time)) denotes the task of making two systems running at the same time. In communication systems, the synchronization of the transmitter and the receiver requires to accurately estimate a number of parameters such as the carrier frequency and phase offsets, the timing epoch... In the early days of digital communications, synchronizers used to operate in either data-aided (DA) or non-data-aided (NDA) modes. However, with the recent advent of powerful coding techniques, these conventional synchronization modes have been shown to be unable to properly synchronize state-of-the-art receivers. In this context, we investigate in this thesis a new family of synchronizers referred to as code-aided (CA) synchronizers. The idea behind CA synchronization is to take benefit from the structure of the code used to protect the data to improve the estimation quality achieved by the synchronizers. In a first part of the thesis, we address the issue of turbo synchronization, i.e., the iterative synchronization of continuous parameters. In particular, we derive several mathematical frameworks enabling a systematic derivation of turbo synchronizers and a deeper understanding of their behavior. In a second part, we focus on the so-called CA hypothesis testing problem. More particularly, we derive optimal solutions to deal with this problem and propose efficient implementations of the proposed algorithms. Finally, in a last part of this thesis, we derive theoretical lower bounds on the performance of turbo synchronizers.

Efficient multimedia communication over mobile or wireless channels remains a challenging problem. To deal with that problem so far, the industry has followed mostly a divide and conquer approach, by considering separately the source of data (text, image, video, etc.) and the communication channel (electromagnetic waves across the air, a telephone line, a coaxial cable, etc.). The goal is always the same: to transmit (or store) more data reliably per unit of time, of energy, of physical medium, etc. With today's applications, the divide and conquer approach has, in a sense, started to show its limits. Let us consider, for example, the digital transmission of an image. At the transmitter, the first main step is data compression, at the source level. The number of bits that are necessary to represent the image with a given level of quality is reduced, usually by removing details in the image that are invisible (or less visible) to the human eye. The second main step is data protection, at the channel level. The transmission is made ideally resistant to deteriorations caused by the channel, by implementing techniques such as time/frequency/space expansions. In a sense, the two steps are quite antagonistic --- we first compress then expand the original signal --- and have different goals --- compression enables to transfer more data per unit of time/energy/medium while protection enables to transfer data reliably. At the receiver, the "reversed" operations are implemented. This separation in two steps dates back to Shannon's source and channel coding separation theorem in 1948 and has encouraged the division of the research community in two groups, one focusing on data compression, the other on data protection. This separation has also seduced the industry for the design, thereby supported by theory, of layered communication protocols. But this theorem holds only under asymptotic conditions that are rarely satisfied with today's multimedia content and mobile channels. Therefore, it is usually wise in practice to drop this strict separation and to allow at least some cross-layer cooperation between the source and channel layers. This is what lies behind the words joint source-channel techniques. As the name suggests, these techniques are optimized jointly, without a strict separation. Intuitively, since the optimization is less constrained from a mathematical standpoint, the solution can only be better or equivalent. In this thesis, we investigate a promising subset of these techniques, based on the turbo principle and on variable length codes. The potential of this subset has been illustrated for the first time in 2000, with an example that, since then, has been successfully improved in several directions. Unfortunately, most decoding algorithms have been so far developed on an ad hoc basis, without a unified view and often without specifying the approximations made. Besides, most code-related conclusions are based on simulations or on extrinsic information analysis. A theoretical framework on the error correcting properties of variable length codes in turbo systems is lacking. The purpose of this work, in three parts, is to fill in these gaps up to a certain extent. The first part presents the literature in this field and attempts to give a unified overview. The second part proposes a transmission system that generalizes previous systems from the literature, with the simple addition of a repetition code. While most previous systems are designed for bit streams with a high level of residual redundancy, the proposed system has the interesting flexibility to handle easily different levels of redundancy. Its performance is then analyzed for small levels of redundancy, which is a case not tackled extensively in the literature. This analysis leads notably to the discovery of surprising interleaving gains with reversible variable length codes. The third part develops the mathematical framework that was motivated during the second part but skipped on purpose for the sake of clarity. We first clarify several issues that arise with non-uniform bits and the extrinsic information charts, and propose and discuss two methods to compute these charts. Next, several theoretical results are stated on the robustness of variable length codes concatenated with linear error correcting codes. Notably, an approximate average distance spectrum of the concatenated code is rigorously developed. Together with the union bound, this spectrum provides upper bounds on the symbol and frame/packet error rates. These bounds are then analyzed from an interleaving gain standpoint and it is proved that the variable length code improves the interleaving gain if its spectrum is bounded.

No description available.

The upcoming 5G mobile communications system promises to enable use cases requiring ultra-reliable and low latency communications. Researchers therefore require more detailed information about aspects such as channel coding performance at very low block error rates. The simulations needed to obtain such results are very time consuming and this poses achallenge to studying the problem. This thesis investigates the use of hardware acceleration for performing fast simulations of turbo code performance. Special interest is taken in investigating different methods for generating normally distributed noise based on pseudorandom number generator algorithms executed in DSP:s. A comparison is also done regarding how well different simulator program structures utilize the hardware. Results show that even a simple program for utilizing parallel DSP:s can achieve good usage of hardware accelerators and enable fast simulations. It is also shown that for the studied process the bottleneck is the conversion of hard bits to soft bits with addition of normally distributed noise. It is indicated that methods for noise generation which do not adhere to a true normal distribution can further speed up this process and yet yield simulation quality comparable to methods adhering to a true Gaussian distribution. Overall, it is show that the proposed use of hardware acceleration in combination with the DSP software simulator program can in a reasonable time frame generate results for turbo code performance at block error rates as low as 10−9.

L'idée des turbo-codes, construction très performante permettant l'encodage de l'information classique, ne pouvait jusqu'à présent pas être transposé au problème de l'encodage de l'information quantique. En effet, il subsistait des obstacles tout aussi théoriques que relevant de leur implémentation. A la version quantique connue de ces codes, on ne connaissait ni de résultat établissant une distance minimale infinie, propriété qui autorise de corriger un nombre arbitraire d'erreurs, ni de décodage itératif efficace, car les turbo-encodages quantiques, dits catastrophiques, propagent certaines erreurs lors d'un tel décodage et empêchent son bon fonctionnement. Cette thèse a permis de relever ces deux défis, en établissant des conditions théoriques pour qu'un turbo-code quantique ait une distance minimale infinie, et d'autre part, en exhibant une construction permettant au décodage itératif de bien fonctionner. Les simulations montrent alors que la classe de turbo-codes quantiques conçue est efficace pour transmettre de l'information quantique via un canal dépolarisant dont l'intensité de dépolarisation peut aller jusqu'à p = 0,145. Ces codes quantiques, de rendement constant, peuvent aussi bien être utilisés directement pour encoder de l'information quantique binaire, qu'être intégrés comme modules afin d'améliorer le fonctionnement d'autres codes tels que les LDPC quantiques.

Since its introduction in 1993, the turbo coding error-correction technique has generated a tremendous interest due to its near Shannon-limit performance. Two key innovations of turbo codes are parallel concatenated encoding and iterative decoding. In its IMT-2000 initiative, the International Telecommunication Union (ITU) adopted turbo coding as a channel coding standard for Third-Generation (3G) wireless high-speed (up to 2 Mbps) data services (cdma2000 in North America and W-CDMA in Japan and Europe). For battery-powered hand-held wireless terminals, energy consumption is a major concern. In this thesis, a new design for an energy-efficient turbo decoder that is suitable for 3G wireless high-speed data terminals is proposed. The Log-MAP decoding algorithm is selected for implementation of the constituent Soft-Input/Soft-Output (SISO) decoder; the algorithm is approximated by a fixed-point representation that achieves the best performance/complexity tradeoff. To attain energy reduction, a two-stage design approach is adopted. First, a novel dynamic-iterative technique that is appropriate for both good and poor channel conditions is proposed, and then applied to reduce energy consumption of the turbo decoder. Second, a combination of architectural-level techniques is applied to obtain further energy reduction; these techniques also enhance throughput of the turbo decoder and are area-efficient. The turbo decoder design is coded in the VHDL hardware description language, and then synthesized and mapped to a 0. 18<i>&mu;</i>m CMOS technology using the standard-cell approach. The designed turbo decoder has a maximum data rate of 5 Mb/s (at an upper limit of five iterations) and is 3G-compatible. Results show that the adopted two-stage design approach reduces energy consumption of the turbo decoder by about 65%. A prototype for the new turbo codec (encoder/decoder) system is implemented on a Xilinx XC2V6000 FPGA chip; then the FPGA is tested using the CMC Rapid Prototyping Platform (RPP). The test proves correct functionality of the turbo codec implementation, and hence feasibility of the proposed turbo decoder design.

Since its introduction in 1993, the turbo coding error-correction technique has generated a tremendous interest due to its near Shannon-limit performance. Two key innovations of turbo codes are parallel concatenated encoding and iterative decoding. In its IMT-2000 initiative, the International Telecommunication Union (ITU) adopted turbo coding as a channel coding standard for Third-Generation (3G) wireless high-speed (up to 2 Mbps) data services (cdma2000 in North America and W-CDMA in Japan and Europe). For battery-powered hand-held wireless terminals, energy consumption is a major concern. In this thesis, a new design for an energy-efficient turbo decoder that is suitable for 3G wireless high-speed data terminals is proposed. The Log-MAP decoding algorithm is selected for implementation of the constituent Soft-Input/Soft-Output (SISO) decoder; the algorithm is approximated by a fixed-point representation that achieves the best performance/complexity tradeoff. To attain energy reduction, a two-stage design approach is adopted. First, a novel dynamic-iterative technique that is appropriate for both good and poor channel conditions is proposed, and then applied to reduce energy consumption of the turbo decoder. Second, a combination of architectural-level techniques is applied to obtain further energy reduction; these techniques also enhance throughput of the turbo decoder and are area-efficient. The turbo decoder design is coded in the VHDL hardware description language, and then synthesized and mapped to a 0. 18<i>&mu;</i>m CMOS technology using the standard-cell approach. The designed turbo decoder has a maximum data rate of 5 Mb/s (at an upper limit of five iterations) and is 3G-compatible. Results show that the adopted two-stage design approach reduces energy consumption of the turbo decoder by about 65%. A prototype for the new turbo codec (encoder/decoder) system is implemented on a Xilinx XC2V6000 FPGA chip; then the FPGA is tested using the CMC Rapid Prototyping Platform (RPP). The test proves correct functionality of the turbo codec implementation, and hence feasibility of the proposed turbo decoder design.

This dissertation thesis deals with new progressive channel coding methods for data transmission using satellite transponder. The design of the system for SMS transmission, in which novel turbo coding methods are applied, is discussed too. An achievement of the lowest output power and the smallest user aperture is the principal aim of the new method applications. Design of system that would be able to the error free SMS transmission by very low signal to noise ratio is analyzed in this dissertation thesis. The work is focused on energy budget, modification and implementation of new turbo code types and using unique properties, development of new bit error rate estimation methods and methods for determination of final SMS form. The main contribution is the new type of turbo code development that have optimal properties for this usage, development of new bit error rate estimation method and development of method that is able to determine final form of SMS on the basis SMS frame structure and turbo decoding theory when the bit error rate is not zero.

Dans cette thèse, les techniques de coopération ont été étudiées pour un canal multi-accès multi-relais composé d'au moins deux sources qui communiquent avec une seule destination à l'aide d'au moins deux nœuds de relayage en mode semi-duplex. Le multiplexage par répartition dans le temps est supposé. Tout d'abord, l’algorithme d’adaptation de lien est exécuté par l'ordonnanceur centralisé. Durant la première phase de transmission, les sources transmettent chacune à leur tour leur message respectif pendant des intervalles de temps consécutifs. Dans chaque intervalle de temps dans la deuxième phase, la destination planifie un nœud pour transmettre les redondances, mettant en œuvre un protocole coopératif d'Hybrid Automatic Repeat reQuest (HARQ), où les canaux de contrôle limités bidirectionnels sont disponibles depuis les sources et les relais vers la destination. Dans la première partie de la thèse, les stratégies de sélection des nœuds centralisé sont proposées pour la deuxième phase de transmission. Les décisions d’ordonnancement sont prises en fonction de la connaissance des ensembles de sources correctement décodées par chaque noeud et ayant comme objectif de maximiser l’efficacité spectrale moyenne. L'analyse de la probabilité de coupure de l'information ainsi que les simulations Monte-Carlo (MC) sont effectués afin de valider ces stratégies. Dans la seconde partie, un algorithme d’adaptation de lien lent est proposé afin de maximiser l’efficacité spectrale moyenne sous contrainte de vérification d'une qualité de service individuelle cible pour une famille donnée de schémas de modulation et de codage, réposant sur l'information sur la distribution des canaux signalée. Les débits des sources discrets sont déterminés en utilisant l’approche "Genie-Aided" suivie d’un algorithme itératif de correction de débit. Les simulations MC montrent que l’algorithme d’adaptation de lien proposé offre des performances proches de celles de la recherche exhaustive. Dans la troisième partie, les performances de protocole HARQ à redondance incrémentale (IR) avec codage mono et multi-utilisateur, ainsi que l'HARQ de type Chase Combining avec codage mono-utilisateur sont comparées. Les simulations MC montrent que l'IR-HARQ avec codage mono-utilisateur offre le meilleur compromis entre performance et complexité pour le scénario de petit nombre de sources. Un schéma de codage pratique est proposé et validé à l'aide de simulations MC. / In this thesis, cooperation techniques have been studied for Multiple Access Multiple Relay Channel, consisted of at least two sources which communicate with a single destination with the help of at least two half-duplex relaying nodes. Time Division Multiplexing is assumed. First, the link adaptation algorithm is performed at the centralised scheduler. Sources transmit in turns in consecutive time slots during the first transmission phase. In each time slot of the second phase, the destination schedules a node to transmit redundancies, implementing a cooperative Hybrid Automatic Repeat reQuest (HARQ) protocol, where bidirectional limited control channels are available from sources and relays towards the destination. In the first part of the thesis, centralized node selection strategies are proposed for the second phase. The scheduling decisions are made based on the knowledge of the correctly decoded source sets of each node, with the goal to maximize the average spectral efficiency. An information outage analysis is conducted and Monte-Carlo (MC) simulations are performed to evaluate their performance. In the second part, a slow-link adaptation algorithm is proposed which aims at maximizing the average spectral efficiency under individual QoS targets for a given modulation and coding scheme family relying on the reported Channel Distribution Information of all channels. Discrete source rates are first determined using the "Genie-Aided" assumption, which is followed by an iterative rate correction algorithm. The resulting link adaptation algorithm yields performance close to the exhaustive search approach as demonstrated by MC simulations. In the third part, performances of Incremental Redundancy (IR) HARQ with Single and Multi User encoding, as well as the Chase Combining HARQ with Single User encoding are compared. MC simulations demonstrate that IR-HARQ with Single User encoding offers the best trade-off between performance and complexity for a small number of sources in our setting. Practical coding scheme is proposed and validated using MC simulations.

本論文は、多端子通信路に対するマルチユーザ符号化および復号の研究成果をまとめたものである。多重接続加算通信路による情報伝送において、複数ユーザの稼働状態を識別するための誤り訂正可能なシグネチャ符号の構成を論ず,全伝送率の高いシグネチャ符号の一般的な構成法を解明する.双方向中継通信路では、2ユーザターボ符号に対する復号の演算量を低減させる復号法を提案する。加法性白色ガウス雑音環境下では復号性能を劣化することなく、レイリーフェージング環境下では僅かな劣化にとどめながら、復号の演算量を約半分程度に低減することができる. / Coding and decoding for multiuser communication systems are investigated. For MAAC, we propose a coding scheme of (k + 1)-ary error-correcting signature codes. We give binary and non-binary signature codes. They are the best error-correcting signature codes for MAAC, in the sense that they have highest sum rates known. For TWRC, we propose a low-complexity two-user turbo decoding scheme when turbo codes are applied in two users. The approximate decoding algorithm preserves low decoding complexity over the Gaussian TWRC, without much performance degradation. / 博士(工学) / Doctor of Philosophy in Engineering / 同志社大学 / Doshisha University