Ronald Edicson Garzón Bohórquez

Advanced coding and interleaving techniques for next generation communication and broadcasting systems

Keywords: Turbo codes, precoding, ARP interleavers, span properties, correlation graph, EXIT chart, LTE, channel interleaver, time and frequency diversity, mutual information, DVB-T2. v vi Turbocodes, précodage, entrelaceurs ARP, propriétés de dispersion, graphe de corrélation, EXIT chart, LTE, entrelaceur canal, diversité temporelle et vii fréquentielle, information mutuelle, DVB-T2. viii sequence size 6144 . . . . . . . . . . . .

20 Janvier 2015 T he increasing demand for multimedia applications and services, such as TV on demand, live streaming or interactive gaming, calls for the introduction of next generation communication and broadcasting systems. Such systems should provide reliable transmissions ensuring low error rates with a limited impact on spectral resource. To this end, this thesis focuses on the enhancement of the error rate performance of interleaved and coded transmissions.

In the first part, we propose a method to design efficient puncture-constrained interleavers for Turbo Codes (TC). We first introduce a strategy to select suitable puncturing patterns for TCs. Then, we propose a new interleaver constraint related to parity puncturing. Finally, we propose a new graph-based Almost Regular Permutation (ARP) design method. When included via the introduced graphical approach, the proposed parity puncturing constraint allows the number of candidate interleavers with high minimum Hamming distances to be increased and reduces the average time to find such candidates. Significant performance gains compared to the LTE standard are achieved.

The second part of this study deals with precoding techniques for TCs. We start by analyzing a Precoded Turbo Code (PTC) structure from the literature. Then, we derive a modified EXtrinsic Information Transfer (EXIT) chart to select suitable precoding ratios for this structure. Afterwards, we propose a new hybrid precoding structure and we also study the combination of this hybrid structure with the first one. Since the resulting scheme cannot solve the convergence versus error floor tradeoff issue, the hybrid structure is selected for further analysis due to its good asymptotic performance and interleaver design criteria adapted to PTCs are proposed. According to the results, PTCs can find their way in adaptive systems where the target error rate can change according to the transmission conditions.

The last part of the thesis is devoted to the design of efficient channel interleavers. As the first design criterion, we propose to jointly optimize the time and frequency span properties and we give appropriate theoretical tools to represent the span constraints. Second, we show that the best interleaver candidates can then be selected according to the Mutual Information (MI) distribution variance. The DVB-T2 channel interleaver is shown to present shortcomings according to these criteria. Therefore, we propose designing a global channel interleaver for DVB-T2 and we give a set of guidelines for its design. The proposed interleaver improves the error rate performance of the DVB-T2 transmission chain, especially in the presence of regular erasure patterns. Furthermore, a better control of the interleaver design parameters and a lower system latency and complexity are achieved, due to the reduction in the number of channel interleaving components.

T out d'abord, je tiens à remercier le Professeur Catherine DOUILLARD, que j'ai eu le plaisir d'avoir comme directrice de thèse. Je lui suis reconnaissant pour son accueil exceptionnel au sein de son équipe de recherche du Département Electronique de Télécom Bretagne, et aussi pour son encouragement et son soutien tout au long de ces trois années, et notamment pour sa patience et ses conseils lors des nombreuses corrections des différentes publications et versions de ce manuscrit.

Je tenais également à remercier le Docteur Charbel ABDEL NOUR, qui m'a encadré tout au long de mes travaux de thèse, et qui m'a donné l'opportunité de les effectuer dans son équipe de recherche. Les différents échanges que nous avons eu ont été des éléments clés dans le bon acheminement de mes activités de recherche. Son engagement, son soutien et notamment son enthousiasme m'ont beaucoup motivé lors de ces trois années.

Mes remerciements vont aussi à Kévin BURGI, chercheur au Département Electronique, pour son aide dans l'automatisation de certains de mes outils de simulation.

Je voulais aussi remercier les personnes avec lesquelles j'ai eu le plaisir de partager de bons moments à Télécom tout au long de ces trois ans : Daniel, Oscar, Javier, Juan David, Santiago, Sandra Victoria, July Paola, Soraya, Cristina et Dani.

Je remercie également mes parents, Pedro Julio et Temilda, pour tous leurs conseils et encouragements, ainsi que mes frères pour leur soutien aux moments opportuns.

Un remerciement spécial à Petra pour m'avoir accompagné et encouragé pendant cette expérience.

Pour finir, je souhaiterai remercier les jurys de cette thèse pour avoir accepté d'évaluer mes travaux de thèse et pour l'intérêt qu'ils ont porté à mon travail.

iii

List of Figures

S min

Minimum span value associated to an interleaver.

S

Vector of shifts in the ARP interleaver.

T l

Inter-layer shift in the ARP interleaver.

VAR

Variance of the MI distribution over the FEC blocks in the OFDM frame. L e succès commercial des nouveaux périphériques multimédia tels que les tablettes tactiles, les TV connectées ou les smartphones, combiné à la demande croissante de services tels que les jeux interactifs, la TV à la demande ou le streaming, appellent à introduire une nouvelle génération de systèmes de communication et de radiodiffusion. De tels systèmes se devront d'assurer des transmissions fiables tout en ayant un impact limité sur les ressources spectrales, notamment lorsque des faibles taux d'erreurs (typiquement inférieurs à 10 -6 ) sont ciblés. Dans cette optique, les travaux de cette thèse portent sur l'amélioration de la performance en termes de taux d'erreur des transmissions codées et entrelacées. Dans un premier temps, nous étudions deux structures turbocodées dans le contexte de la norme Long Term Evolution (LTE) définie par le consortium 3GPP. La première intègre une optimisation conjointe de la construction du motif de poinçonnage et de l'entrelaceur. La deuxième structure considère le précodage comme un moyen d'améliorer le comportement en convergence et/ou asymptotique du turbocode. Enfin, nous nous intéressons à la conception d'entrelaceurs canal spécifiquement optimisés pour les systèmes de diffusion de dernière génération.

Les turbocodes

Les turbocodes (TCs) [START_REF] Berrou | Near Shannon limit errorcorrecting coding and decoding: Turbo-codes[END_REF] sont parmi les codes correcteur d'erreurs (ou codes FEC) les plus populaires dans les systèmes de transmission actuels, tels que WiMAX [START_REF] Ieee | IEEE standard for local and metropolitan area networks, Part 16: Air interface for fixed and mobile broadband wireless access systems[END_REF] et LTE [START_REF] Etsi | LTE Envolved Universal Terrestrial Radio Access(E-UTRA): Multiplexing and channel coding[END_REF]. Ceci est dû à son pouvoir de correction capable d'approcher la limite de Shannon. Un TC conventionnel est constitué d'une concaténation en parallèle de deux codes élémentaires comme le montre la Figure 1. La trame d'information d est encodée par le premier code élémentaire RSC 1, puis envoyée au deuxième code élémentaire via la fonction d'entrelacement Π. Le rendement de codage mère R est défini par sa structure de base, et les rendements plus élevés sont obtenus par poinçonnage de bits en sortie de l'encodeur. La structure de l'encodeur est donc définie principalement par les paramètres suivants : les codes élémentaires, la terminaison du treillis, la fonction d'entrelacement et le poinçonnage. Dans les travaux de cette thèse nous nous sommes particulièrement intéressés à l'étude de la fonction d'entrelacement et à son optimisation vis-à-vis du motif de poinçonnage.

La fonction d'entrelacement

Un des objectifs de la fonction d'entrelacement des turbocodes consiste à « casser » ou éviter les paquets d'erreurs dans les bits encodés, à savoir un groupe consécutif de bits encodés et erronés par le canal. L'entrelaceur lit les bits de la trame d'information d et les écrit dans un ordre permuté dans la trame entrelacée d . Ainsi, un paquet d'erreurs présent à l'entrée du décodeur du premier code élémentaire est dispersé dans le deuxième. L'entrelaceur est donc un composant essentiel des TCs qui joue un double rôle. Premièrement, il limite la distance minimale de Hamming atteignable par le code [START_REF] Berrou | Near optimum error correcting coding and decoding: turbo-codes[END_REF] et affecte par conséquent sa performance asymptotique.

RÉSUMÉ DE LA THÈSE

xxxi Deuxièmement, due à ses propriétés de dispersion, l'entrelaceur impacte aussi la corrélation affectant l'information extrinsèque échangée par les décodeurs élémentaires lors du processus de décodage itératif [START_REF] Hokfelt | Interleaver design for turbo codes based on the performance of iterative decoding[END_REF].

L'entrelacement canal

Différents codes FEC, tels que les codes LDPC [START_REF] Gallager | Low density parity check codes[END_REF], [START_REF] Mackay | Near Shannon limit performance of low density parity check codes[END_REF] et les TCs, sont à présent capables d'approcher la limite de Shannon, notamment dans des transmissions sur des canaux sans mémoire dans lesquels le bruit est aléatoirement distribué et statistiquement indépendant. En revanche, lorsque ces codes sont utilisés pour des transmissions sur des canaux où le signal est soumis à un bruit de type impulsif ou à des évanouissements profonds, son pouvoir de correction est réduit. Une solution possible à ce problème consiste à distribuer les motifs d'erreurs arrivant en paquets dans des différents mots de code (ou trames FEC). Ainsi, l'entrelacement canal [START_REF] Vangelista | Key technologies for next-generation terrestrial digital television standard DVB-T2[END_REF] a été introduit afin de distribuer uniformément les différents mots de code, en temps et en fréquence, de façon à éviter que les symboles affectés par un bruit impulsif ou par un évanouissement profond finissent dans un même mot de code.

Les entrelaceurs canal peuvent être divisés en deux familles : adaptatifs et non adaptatifs. Dans le premier groupe, la structure de l'entrelaceur est adaptée à une propriété spécifique du canal. Dans le deuxième, la structure d'entrelacement reste invariante pour n'importe quel type de canal et pour un jeu de paramètres donnés. Dans les services de radiodiffusion, différents scenarios de transmission sont présents, l'entrelaceur canal ne pouvant pas être adapté à un seul type de canal. Ainsi, les entrelaceurs adaptatifs ne sont pas adaptés à ce type de service. Dans le contexte de cette thèse nous avons donc choisi d'étudier des voies d'amélioration possibles pour des structures d'entrelacement canal non adaptatives. Un entrelaceur canal représentatif de cette famille est l'entrelaceur inclus dans la dernière norme de transmission de télévision numérique européen DVB-T2. Celui-ci est donc choisi comme référence pour notre étude effectuée sur l'entrelacement canal.

Chapitre 2. Optimisation conjointe du motif de poinçonnage et de la fonction d'entrelacement pour les TCs

Les méthodes classiques de construction des TCs font appel au poinçonnage de bits de parité pour obtenir des rendements de codage élevés [START_REF] Acikel | Punctured turbo-codes for BPSK/QPSK channels[END_REF], [START_REF] Mo | Analysis of puncturing pattern for high rate turbo codes[END_REF]. Néanmoins, il a été montré qu'un poinçonnage de symboles de données approprié permet d'incrémenter la distance minimale de Hamming atteignable par le code [START_REF] Crozier | On the error-rate performance of 4-state turbo codes with puncture-constrained DRP interleavers[END_REF], [START_REF] Gracie | Convergence performance and EXIT analysis of 4state partially-systematic turbo codes[END_REF]. Dans cette première partie de notre étude, nous nous sommes intéressés à la construction de la fonction d'entrelacement interne du TC, ainsi qu'à son optimisation vis-à-vis du motif de poinçonnage.

La méthode d'optimisation que nous proposons est composée de trois phases : tout d'abord, les meilleurs masques de poinçonnage pour les codes élémentaires du xxxii RÉSUMÉ DE LA THÈSE TC sont identifiés, en fonction du spectre de distances du code élémentaire et de l'analyse de l'échange d'information extrinsèque dans le TC. Ensuite, un groupe d'entrelaceurs candidats est généré tout en assurant par construction la validation des différents critères de design, tels que valeur minimale de span et de cycle de corrélation (girth) ainsi que des contraintes liées au poinçonnage. Finalement, le meilleur entrelaceur candidat est déterminé comme celui permettant le meilleur spectre de distance de Hamming au TC.

Détermination du motif de poinçonnage

Soit N la période de poinçonnage, qui correspond également à la longueur du motif de poinçonnage. Afin d'éviter les effets de bord liés au poinçonnage, on supposera que N est un diviseur de la taille du bloc à coder, K. D'autre part, pour limiter l'espace de recherche des entrelaceurs, on ne considère en pratique pour N que les plus petits diviseurs de la taille du bloc. On suppose, en outre, que les motifs de poinçonnages sont identiques pour les deux codes RSC circulaires constituant le TC. La méthode de sélection du motif de poinçonnage proposée est donc composée des trois étapes suivantes :

Détermination du meilleur motif de poinçonnage pour chaque valeur admissible de ratio de symboles d'information poinçonnés (DPR) :

Dans cette étape, pour chaque valeur de N sélectionnée et pour chaque valeur de DPR, on considère tous les motifs de poinçonnage possibles et on détermine pour chacun d'eux le début du spectre des distances du code élémentaire poinçonné. On peut utiliser pour ce faire l'algorithme FAST [START_REF] Cedervall | A fast algorithm for computing distance spectrum of convolutional codes[END_REF], qu'il faut adapter pour le cas des codes poinçonnés. On retient pour chaque valeur de DPR le motif de poinçonnage conduisant à la plus grande distance minimale de Hamming. Dans le cas où plusieurs motifs conduisent à des distances minimales de Hamming identiques, on choisira celui dont la multiplicité (nombre de mots de codes à la distance considérée) est minimale. Cette étape de sélection permet notamment d'éliminer les motifs de poinçonnage catastrophiques.

2. Sélection d'un sous-ensemble de motifs de poinçonnage par analyse de l'échange d'information mutuelle dans un turbo-décodeur utilisant un entrelaceur uniforme : Dans cette étape, on mesure l'information mutuelle échangée entre les décodeurs dans une structure de turbo-décodage pour les motifs de poinçonnages sélectionnés à l'étape précédente. On utilise pour ce faire un entrelaceur uniforme [START_REF] Benedetto | Unveiling turbo codes: some results on parallel concatenated coding schemes[END_REF]. Celui-ci permet d'évaluer les performances moyennes du turbocode, indépendamment du choix de l'entrelaceur. L'échange d'information mutuelle entre les décodeurs élémentaires est d'autant plus grand que le point de jonction des courbes est proche du point de coordonnées [START_REF] Berrou | Near Shannon limit errorcorrecting coding and decoding: Turbo-codes[END_REF][START_REF] Berrou | Near Shannon limit errorcorrecting coding and decoding: Turbo-codes[END_REF]. Dans cette étape, on ne sélectionne que les motifs de poinçonnage

RÉSUMÉ DE LA THÈSE

xxxiii pour lesquels l'information mutuelle échangée est supérieure ou égale au cas où seuls les bits de redondance sont poinçonnés (DPR = 0).

3.

Analyse des courbes de taux d'erreurs en sortie du turbo-décodeur utilisant un entrelaceur uniforme : Le turbo-décodeur à entrelaceur uniforme est simulé pour les motifs de poinçonnage sélectionnés à l'étape précédente. Le motif de poinçonnage retenu est celui offrant le meilleur compromis convergence/error floor en fonction de l'application visée.

Choix des contraintes de connexion de l'entrelaceur liées au poinçonnage des symboles d'information et de redondance

Dans cette thèse nous avons considéré deux règles principales de connexion, la première étant déjà définie dans la littérature et la deuxième étant une de nos contributions principales. Une première règle de connexion nous permet de définir un entrelaceur contraint par le poinçonnage de bits d'information ou DPC. Les symboles d'information étant à la fois utilisés en entrée du code RSC 1 et en entrée du code RSC 2, mais n'étant transmis qu'une fois, un symbole poinçonné pour l'un des codes doit nécessairement être poinçonné pour l'autre code. Par conséquent, la fonction d'entrelacement doit nécessairement transformer une position poinçonnée pour un symbole d'information dans l'ordre naturel en une position poinçonnée pour le symbole d'information entrelacé correspondant. Cette règle est déjà mentionnée dans la littérature, par exemple dans [START_REF] Crozier | On designing turbo-codes with data puncturing[END_REF], [START_REF] Crozier | Rate-compatible turbo codes designed with puncture-constrained DRP interleavers[END_REF]. A titre d'exemple, la Figure 2 illustre l'application de cette règle de connexion de l'entrelaceur sur la période de poinçonnage. La règle de connexion que nous proposons est liée au poinçonnage de bits de parité, celle-ci permet de définir un entrelaceur contrainte par le poinçonnage de xxxiv RÉSUMÉ DE LA THÈSE symboles d'information et de parité (DPPC). Elle est basée sur l'observation que l'information extrinsèque calculée en sortie d'un décodeur relativement à une donnée est plus fiable si cette donnée n'est pas poinçonnée que si elle est poinçonnée et qu'elle est également plus fiable si la redondance correspondante n'est pas poinçonnée que si elle est poinçonnée. Cette règle a pour but de répartir le pouvoir de correction du turbocode sur l'ensemble de la séquence d'information.

Construction de l'entrelaceur contraint par les règles de poinçonnage

La dernière étape consiste à construire un entrelaceur qui tienne compte des règles définies préalablement et qui satisfasse les critères cibles de span et girth minimaux donnés.

Dans le cas particulier de l'entrelaceur quasi régulier ou ARP [START_REF] Berrou | Designing good permutations for turbo codes: towards a single model[END_REF], nous avons mis au point une approche basée sur la construction progressive de la fonction d'entrelacement représentée par un graphe, comme illustré dans la Figure 3. Cette représentation permet d'introduire aisément les règles liées au poinçonnage, de construire progressivement l'entrelaceur et de vérifier à chaque étape les valeurs minimales de span et de girth. Ainsi, la technique de construction proposée permet de réduire considérablement l'espace de recherche des paramètres de la permutation par rapport à une recherche exhaustive ou aléatoire.

RÉSUMÉ DE LA THÈSE xxxv

Evaluation de performance par simulation du taux d'erreur

La Figure 4 montre les performances en termes de taux d'erreur trame des turbocodes avec code élémentaire CRSC [START_REF] Cedervall | A fast algorithm for computing distance spectrum of convolutional codes[END_REF][START_REF] Crozier | On designing turbo-codes with data puncturing[END_REF] 8 utilisant les différentes configurations entrelacements proposées : NDP sans poinçonnage de bits d'information, DPC incluant la contrainte lié au poinçonnage de bits d'information et DPPC incluant les contraintes liées au poinçonnage de bits d'information et de parité. Les simulations sont effectuées sur canal gaussien, avec une modulation BPSK, K = 1504, et un maximum de 16 itérations de décodage BCJR [START_REF] Bahl | Optimal decoding of linear codes for minimizing symbol error rate (corresp.)[END_REF]. Des gains significatifs sont obtenus par rapport au turbocode LTE qui utilise un entrelaceur QPP [START_REF] Sun | Interleavers for turbo codes using permutation polynomials over integer rings[END_REF] et la technique de poinçonnage dite rate matching [START_REF] Cheng | Analysis of circular buffer rate matching for LTE turbo code[END_REF].

Chapitre 3. Etude de techniques de précodage pour les TCs

Afin d'améliorer la performance des TCs, différents types de concaténations de codes entrelacés, dites turbo-like codes [START_REF] Gracie | Turbo and turbo-like codes: Principles and applications in telecommunications[END_REF] ont été étudiés dans les dernières années. Dans [START_REF] Abbasfar | Accumulate repeat accumulate codes[END_REF], la technique de précodage a été appliquée à ce type de codes. Il a été montré que sa performance peut être améliorée en préfixant un accumulateur de rendement unitaire à la structure de l'encodeur. Ceci permet de réduire son seuil de convergence sans modifier son rendement de codage. Cette technique a été appliquée aux TCs dans [START_REF] Tong | Precoded turbo code within 0.1 dB of Shannon limit[END_REF] pour construire un nouveau type de turbo-like codes dits turbocodes précodés (PTCs).

xxxvi

RÉSUMÉ DE LA THÈSE

La structure basique de l'encodeur du PTC considérée dans cette étude est montrée dans la Figure 5. Le précodeur est préfixé et connecté au TC via l'entrelaceur Π 1 . Comme introduit dans [START_REF] Tong | Precoded turbo code within 0.1 dB of Shannon limit[END_REF], seuls ρK bits de la trame d'information d sont encodés par l'accumulateur, ρ étant le taux de précodage. C'est un paramètre qui introduit un nouveau degré de liberté dans l'optimisation du code.

Analyse par EXIT chart modifié

Tout d'abord, nous avons analysé l'impact du taux de précodage sur le seuil de convergence de la structure de référence proposée dans [START_REF] Tong | Precoded turbo code within 0.1 dB of Shannon limit[END_REF] (cf. Figure 5) à l'aide d'un EXIT chart classique [START_REF] Brink | Convergence behavior of iteratively decoded parallel concatenated codes[END_REF], [START_REF] Hagenauer | The EXIT chart -Introduction to extrinsic information transfer in iterative processing[END_REF]. La hiérarchie des performances en convergence prédite par l'EXIT chart n'a pas été confirmée par les résultats de simulation du taux d'erreur binaire du code. Par conséquent, un EXIT chart classique n'est pas approprié à la détermination précise du meilleur taux de précodage en termes de convergence. En effet, nous avons montré que les échantillons d'information extrinsèque dans les PTCs ne peuvent pas être considérés comme générés à partir d'un même processus gaussien, ce qui est le cas des EXIT charts classiques. Afin de résoudre ce problème, nous proposons de mesurer l'échange réel d'information extrinsèque entre les décodeurs élémentaires du TC, tout au long des différentes itérations de décodage du PTC à la valeur de SNR correspondante au seuil de convergence. Dans cet EXIT chart modifié, les meilleurs paramètres du PTC en termes de convergence sont identifiés comme étant ceux qui permettent un point de croisement (IA, IE) aussi proche que possible du point de coordonnées [START_REF] Berrou | Near Shannon limit errorcorrecting coding and decoding: Turbo-codes[END_REF][START_REF] Berrou | Near Shannon limit errorcorrecting coding and decoding: Turbo-codes[END_REF]. Finalement, nous avons analysé différents taux de précodage via l'EXIT chart modifié pour la structure montrée dans la Figure 5, en considérant un entrelacement uniforme [START_REF] Benedetto | Unveiling turbo codes: some results on parallel concatenated coding schemes[END_REF] afin de moyenner l'effet de l'entrelaceur sur la performance du code en termes de taux d'erreur. La hiérarchie dans la performance en convergence prédite par l'EXIT chart modifié a été effectivement confirmée par la performance en termes de taux d'erreur obtenue par simulation.

RÉSUMÉ DE LA THÈSE xxxvii

Structure de précodage hybride

Comme alternative à la structure de précodage de la Figure 5, nous proposons une structure hybride. Dans cette structure, tous les bits d'information sont précodés et un nouveau paramètre φ est introduit, qui définit le taux de précodage sérieparallèle (Figure 6(a)). Ainsi, φK parités et (1 -φ)K symboles d'information de l'accumulateur sont encodés par le TC. L'avantage de cette structure de précodage par rapport à la structure de la Figure 5 repose sur le fait qu'elle permet au décodeur élémentaire de l'accumulateur d'échanger de l'information extrinsèque sur toute la trame encodée par le TC pour toutes les valeurs de φ, comme illustré par la Figure 6(b). Le compromis entre performance en convergence et performance asymptotique du PTC hybride est donc contrôlé par le taux de précodage série-parallèle.

(1-ϕ)K ϕK Précodeur D K K d K (a)
SISO 0 ϕK

Inf. extrinsèque bits d'information

Inf. extrinsèque bits de parité D'autre part, nous avons aussi étudié une structure de précodage combinant la structure montrée dans la Figure 5 et la structure hybride proposée. Nous avons observé que cette structure composite ne permet pas de cumuler le gain en convergence de la structure de référence et le gain asymptotique de la structure hybride. Finalement, le gain asymptotique étant le principal ciblé, nous avons opté pour la structure hybride dans la dernière partie de cette étude. Les systèmes de transmission numériques récents font de plus en plus appel à des fonctions d'entrelacement pour tirer parti du pouvoir de correction du codage canal. Dans le système DVB-T2, la chaîne de transmission contient trois composantes d'entrelacement canal [START_REF] Etsi | Digital Video Broadcasting (DVB): frame structure channel coding and modulation for a second generation digital terrestrial television broadcasting system (DVB-T2)[END_REF] : un entrelaceur cellulaire (CI), un entrelaceur temporel (TI) et un entrelaceur fréquentiel (FI). Nous appellerons par la suite entrelaceur T2 l'entrelaceur canal regroupant ces trois composantes. L'implémentation de chacun de ces entrelaceurs introduit une latence additionnelle dans la chaîne de transmission et requiert une certaine quantité de mémoire. D'autre part, une mauvaise interaction entre les différents entrelaceurs élémentaires peut induire des pertes de performance du système. En effet, chaque composante est dédiée à un type de diversité spécifique, mais leurs interactions potentielles n'ont pas été prises en compte lors du développement du standard [START_REF] Etsi | Digital Video Broadcasting (DVB): frame structure channel coding and modulation for a second generation digital terrestrial television broadcasting system (DVB-T2)[END_REF], [START_REF]Digital Video Broadcasting (DVB): implementation guidelines for a second generation digital terrestrial television broadcasting system (DVB-T2)[END_REF]. Pour faire face à ces problèmes, une nouvelle technique pour concevoir des entrelaceurs canal est introduite dans cette dernière partie de l'étude.

L Ch,0 K (1-ϕ)K (

Exemple de performance du PTC hybride avec entrelaceurs optimisés

RÉSUMÉ DE LA THÈSE xxxix

Critères de conception

Un entrelaceur canal performant doit permettre au récepteur de profiter des diversités temporelle et fréquentielle introduites par le code correcteur d'erreurs et l'OFDM (Orthogonal Frequency Division Multiplexing). Pour ce faire, nous avons identifié comme essentielle lors de la conception de l'entrelaceur l'optimisation de ses propriétés de dispersion (ou span) en temps et fréquence. D'autre part, un deuxième paramètre pertinent d'un point de vue de diversité est la distribution de l'information mutuelle sur les trames FEC.

Propriétés de dispersion

Une implémentation possible de l'entrelaceur canal est montrée en Figure Les spans temporel S t et fréquentiel S f minimaux associés à la cellule d'adresse i sont définis dans [START_REF] Crozier | New high-spread high-distance interleavers for turbo-codes[END_REF], [START_REF] Berrou | Designing good permutations for turbo codes: towards a single model[END_REF] comme :

S t (i) = min j =i |t i -t j | + t Π(i) -t Π(j) S f (i) = min j =i |f i -f j | + f Π(i) -f Π(j)
où t u et f u représentent les indices du symbole OFDM et de la porteuse de la cellule d'adresse u. Deux critères de conception de l'entrelaceur canal s'appuyant sur ces propriétés de span peuvent être définis. Le premier critère consiste à maximiser les valeurs minimales des spans temporel et fréquentiel, afin de casser efficacement les paquets d'erreurs en temps et en fréquence. D'autre part, on cherchera à minimiser le nombre de couples de cellules avec un span faible, autrement dit la multiplicité.

xl

RÉSUMÉ DE LA THÈSE

Distribution de l'information mutuelle

Dans le contexte de conception d'entrelaceurs canal, il est pertinent de visualiser la distribution de l'information mutuelle sur les NFEC trames FEC composant la trame OFDM. Etant donné qu'un entrelaceur canal performant doit assurer une distribution d'erreurs non corrélée dans les trames FEC, l'information mutuelle moyenne devrait être distribuée de façon homogène dans les différentes trames FEC, en assurant ainsi que les paquets d'erreur soient uniformément distribués.

La variance de la distribution de l'information mutuelle donne une mesure de la dispersion de celle-ci par rapport à la valeur moyenne d'information mutuelle sur l'ensemble de trames FEC. Par conséquent, une distribution homogène est caractérisée par une faible valeur de variance. Ainsi, les meilleurs entrelaceurs candidats sont ceux permettant les valeurs les plus faibles de variance de la distribution de l'information mutuelle.

Entrelaceurs canal proposés

Afin de réduire la complexité de la génération des adresses de l'entrelaceur canal, nous avons appliqué les critères d'optimisation décrits précédemment sur des lois de permutation régulières et ARP. Le premier entrelaceur est basé sur une loi de permutation régulière (RI), définie par :

Π(i) = P •i

Etude des performances

Les performances des entrelaceurs proposés ont été évaluées et comparées à celles de l'entrelaceur T2, sur le canal de transmission TU6 (canal en milieu urbain typique à 6 coefficients, Figure 9) définis dans [START_REF]Digital Video Broadcasting (DVB): implementation guidelines for a second generation digital terrestrial television broadcasting system (DVB-T2)[END_REF]. Nous avons de plus considéré un scénario de transmission avec un effacement régulier de 15% des porteuses. Les simulations ont été effectuées avec les paramètres suivants : code LDPC de taille 16 200 bits (taille codée), rendement de codage 2/3, 50 itérations de décodage avec l'algorithme somme-produit [START_REF] Kschischang | Factor graphs and the sumproduct algorithm[END_REF], constellation QPSK, taille FFT de 2k et intervalle de garde 1/4. La fréquence Doppler maximale a été fixée à 166,7 Hz.

La Figure 9 montre que les performances en termes de taux d'erreurs binaires (TEB) des meilleurs entrelaceurs obtenus d'après les différentes familles sont assez proches de l'entrelaceur T2 sur un canal sans effacement. Néanmoins, lorsque la trame OFDM est soumise à un motif d'effacement régulier, les entrelaceurs proposés affichent des gains atteignant 0,5 dB. Les distributions d'information mutuelle respectives sont comparées dans la Figure 10. On remarque que l'information mutuelle dans le cas de l'entrelaceur T2 n'est plus distribuée d'une façon homogène dans les trames FEC, mettant ainsi en évidence sa faiblesse dans des conditions canal sévères. Les entrelaceurs proposés montrent ainsi tout son intérêt dans des conditions de transmissions particulièrement difficiles.

Conclusions et perspectives

xliii ment en convergence du PTC. Ainsi, afin de sélectionner les meilleurs paramètres du PTC en termes de convergence, nous avons proposé une analyse de l'échange réel d'information extrinsèque entre les décodeurs élémentaires du TC, tout au long des différentes itérations de décodage du PTC. Globalement, les PTCs ne pourront probablement pas atteindre les performances des TCs construits par des méthodes optimisées, comme celle proposée dans la deuxième partie de notre étude. Néanmoins, les PTCs conviennent pour les systèmes adaptatifs où le taux d'erreur ciblé peut changer en fonction des conditions de transmission.

La dernière partie de notre étude a été dédiée à la construction de fonctions d'entrelacement canal performantes, notamment pour des applications de radiodiffusion. La méthode de conception proposée est basée sur l'optimisation conjointe des propriétés de span en temps et en fréquence. De plus, nous avons identifié la variance de la distribution de l'information mutuelle sur les trames FEC comme un critère pertinent pour la sélection des meilleurs entrelaceurs canal. Des améliorations de performance de la chaîne DVB-T2 en termes de taux d'erreur binaire sont atteintes avec l'utilisation de l'approche proposée, notamment dans des conditions canal sévères, tels qu'en présence de motifs d'effacement réguliers. En outre, la réduction du nombre de composantes d'entrelacement canal permet une meilleure maîtrise des paramètres de design de l'entrelaceur, ainsi qu'une latence et une complexité réduites.

Plusieurs perspectives d'étude peuvent être considérées à partir des travaux de thèse présentés. Par exemple, de nouvelles contraintes liées au poinçonnage peuvent être envisagées pour les entrelaceurs des turbocodes, notamment pour des codes élémentaires de rendement faible, pour lesquels le degré de liberté dans le poinçonnage de bits systématiques est plus large. Il peut être aussi intéressant d'étudier l'inclusion de poinçonnage de bits systématiques et le design des fonctions d'entrelacement dans des structures de codage plus complexes, comme par exemple les codes M -binaire, non binaire ou les turbocodes irréguliers. D'autre part, le design des fonctions d'entrelacement pour le turbocode précodé, via un algorithme prenant en compte le graphe de corrélation proposé dans le cas tridimensionnel, reste encore à être étudié. Les travaux sur le précodage peuvent être aussi étendus à l'exploration des améliorations en convergence pour des rendements de codage faibles. Finalement, une optimisation des fonctions d'entrelacement canal pour des schémas de transmission incluant des techniques de diversité spatiale, comme dans les systèmes MISO (Multiple Input Single Output) ou MIMO (Multiple Input Multiple Output), reste encore à être considérée. xliv T he basics of information theory were founded in 1948 by the pioneering work of Claude Elwood Shannon, A Mathematical Theory of Communications [START_REF] Shannon | A mathematical theory of communication[END_REF].

In that work, Shannon demonstrated that reliable communication can be achieved by choosing an appropriate Forward Error Correction (FEC) code, provided that the source information rate is less than the channel capacity. Since then, many researchers in information theory and communication fields have worked on designing practical coding systems able to approach the fundamental limits established by Shannon. It was only after more than 40 years of research that such a coding system was discovered. Turbo Codes (TCs), introduced in 1993 by Berrou et al [START_REF] Berrou | Near Shannon limit errorcorrecting coding and decoding: Turbo-codes[END_REF], showed a performance at 0.7 decibels from the Shannon limit. Such results improved by almost 3 decibels the solutions existing at that time. TCs are known as the first implementable capacity-approaching FEC codes. Their introduction opened a way to explore other capacity-approaching codes such as Low-Density Parity-Check (LDPC) codes originally proposed in 1962 by Gallager [START_REF] Gallager | Low density parity check codes[END_REF] and rediscovered in 1996 by Mackay et al. [START_REF] Mackay | Near Shannon limit performance of low density parity check codes[END_REF].

Wireless communication systems have become an important element in the life of modern society. The number of mobile subscribers around the world exceeded six and a half billion by the end of 2013 [START_REF]The World in 2014: ICT Facts and Figures[END_REF]. To deal with the increasing requirements of data rates, mobility, spectral efficiency and quality of service (QoS), different digital communication techniques have been included [START_REF] Molisch | Wireless Communications[END_REF] in the most recent communication systems. Aiming to cope with the requirements in terms of error rate performance, capacity-approaching FEC codes like TCs and LDPC codes have been adopted. Thanks to the near-capacity performance of TCs and their suitability for practical implementation, turbo coding is certainly one of the most popular channel coding schemes in wireless systems, including cutting-edge standards such as Long Term Evolution (LTE) [START_REF] Etsi | LTE Envolved Universal Terrestrial Radio Access(E-UTRA): Multiplexing and channel coding[END_REF], Worldwide Interoperability for Microwave Access (WiMAX) [START_REF] Ieee | IEEE standard for local and metropolitan area networks, Part 16: Air interface for fixed and mobile broadband wireless access systems[END_REF], and 2 nd generation Digital Video Broadcasting -Return Channel via Satellite (DVB-RCS2) [START_REF] Etsi | Digital Video Broadcasting (DVB): second generation DVB interactive satellite system (DVB-RCS2): Part 2: Lower layers for satellite standard[END_REF].

Given the extensive application sector of wireless services, transmission is subject to severe operational conditions: non-line-of-sight, obstacles, multipath fading (echoes), interference. In order to mitigate the effect of such operational conditions on the QoS, spatial, time and frequency diversity techniques are introduced in most INTRODUCTION wireless communication systems. Spatial diversity is usually achieved in cellular networks by using spaced multiples antennas. Time diversity can be obtained by using a Time Interleaver (TI) as in the 2 nd generation Digital Video Broadcasting Terrestrial (DVB-T2) [START_REF] Etsi | Digital Video Broadcasting (DVB): frame structure channel coding and modulation for a second generation digital terrestrial television broadcasting system (DVB-T2)[END_REF]. Frequency diversity can be achieved by using Orthogonal Frequency Division Multiplexing (OFDM) [START_REF] Weinstein | Data transmission by frequency-division multiplexing using the discrete fourier transform[END_REF] modulation together with a Frequency Interleaver (FI) as in DVB-T2, distributed allocation of data as in LTE [START_REF] Molisch | Wireless Communications[END_REF], or subcarrier permutation as in WiMAX [START_REF] Andrews | Fundamentals of WiMAX: understanding broadband wireless networking[END_REF]. In addition, other interleavers are included in wireless communication systems to benefit from diversity. It is the case of the Bit Interleaver (BI) in WiMAX improving frequency diversity, or the BI in DVB-T2. Interleaving functions are also a key component in channel coding techniques, such as TCs. Indeed, Hamming distance spectrum and encountered correlation during the turbo decoding process are strongly related to the TC interleaver. Thus, channel coding and interleaving techniques represent fundamental elements in wireless communication systems.

In recent years, nomadic users got interested in a larger diversity of applications and services, such as TV or multimedia contents on demand [START_REF] Marques | Broadcastingbroadband convergence[END_REF], live streaming, or interactive gaming. These applications call for a reliable QoS. To meet such requirements, low error rates down to 10 -10 for broadcasting applications and down to 10 -6 for live streaming or interactive gaming [START_REF] Guennec | La quatrième génération des systèmes mobiles: Le réseau coeur LTE: ePC[END_REF] are required. Having this end in view, this thesis focuses on the enhancement of the error rate performance of turbo coded transmission schemes. In particular, we study the joint optimization of puncturing patterns and interleavers for punctured TCs. We also consider precoding structures, taking as a reference the one recently presented in [START_REF] Tong | Precoded turbo code within 0.1 dB of Shannon limit[END_REF]. Moreover, in cases where the transmitted signal undergoes impulsive noise and/or selective fading (e.g., broadcasting applications), we focus on the design of efficient channel interleavers to mitigate the effect of such channel impairments on the FEC code performance.

Thesis outline

Chapter 1 gives the basics of channel coding and interleaving techniques necessary for the following chapters. In the first section of this chapter, we present an overview of TCs: the turbo encoder structure as well as the conventional decoding algorithm for TCs are described, the tools commonly used to evaluate their convergence and asymptotic performance are presented and a new turbo-like code known as Precoded Turbo Code (PTC), proposed in [START_REF] Tong | Precoded turbo code within 0.1 dB of Shannon limit[END_REF], is introduced. In the second section, the basics of interleaving techniques for TCs are reviewed: performance and implementation requirements for TC interleavers are given and interleaver design criteria are proposed. Then, the different TC interleaver families available in the literature are presented. In the third and last section, an overview of common channel interleaving techniques is performed.

In Chapter 2, a method to design efficient puncture-constrained interleavers for TCs is proposed. It begins with the selection of puncturing patterns, based on the INTRODUCTION 3 Hamming distance spectrum of the constituent code and on a modified EXIT chart analysis. Then, puncturing constraints on data and/or parity bits are introduced and a graph-based Almost Regular Permutation (ARP) interleaver design method is proposed. Some application examples are studied and significant performance gains compared to the LTE TC are shown. In this chapter, a new correlation graph representation for TCs is also derived.

Chapter 3 is devoted to an exploration of precoding techniques for TCs. It starts with the analysis of the reference precoding structure introduced in [START_REF] Tong | Precoded turbo code within 0.1 dB of Shannon limit[END_REF] and introduces two new variants of Precoded Turbo Codes (PTCs). In this section, we also derive a modified EXIT chart appropriate for the analysis of PTCs. The effect of the precoding pattern structure and of the constituent code of the precoder are then studied for the variant scheme called hybrid PTC. Finally, in addition to the analysis of Chapter 2, relevant design criteria for PTC interleavers are proposed. In the last part of the chapter, a performance example of the proposed precoded structure is shown.

Chapter 4 presents a method to design efficient channel interleavers. First, relevant criteria are identified and appropriate theoretical tools to represent the optimization constraints are provided. Then, the DVB-T2 channel interleaver is studied and the effect of its different components on system error rate performance is analyzed. Afterwards, we propose a set of guidelines to design optimized channel interleavers. As a case study, these guidelines are applied to channel interleavers for DVB-T2. The impacts of the adoption of the proposed structure on the channel interleaver latency and complexity are also studied and the error rate performance of the overall system is evaluated.

Finally, conclusions are drawn and a discussion on perspectives for future research is presented in the last chapter.

Contributions of the thesis

Chapter 2 contains five original contributions. The first contribution is the proposal, in Section 2.2, of a strategy to select suitable puncturing patterns with possible data puncturing.

Then, in Section 2.3.2, we propose an original parity puncturing constraint for the design of TC interleavers that allows the number of candidate interleavers with high minimum Hamming distances to be increased and the average time to find these interleavers to be reduced.

We also introduce in Section 2.4 a new representation of the correlation graph for TCs. It provides a theoretical upper bound on the correlation girth of TCs with additional accuracy when compared to the existing literature.

In Section 2.5.1 we demonstrate that any Dithered Relative Prime (DRP) or Quadratic Permutation Polynomial (QPP) interleaver can be expressed as an ARP interleaver. Consequently, this proves that ARP interleavers can achieve, at least,

INTRODUCTION

the same minimum Hamming distances as their DRP and QPP counterparts. Furthermore, since TCs have found their way to several standards with different interleaving structure in each, unifying the interleaving structure can have an advantage for implementation purposes. In fact, one can design an ARP interleaver that can support all standardized interleaver structures. Thus, the overall complexity can be reduced when several interleaving structures have to be implemented in the same chip.

The last and main contribution in Chapter 2 is the introduction in Section 2.5.2 of a new graph-based method to select ARP interleaver parameters. It allows an easy introduction of puncturing constraints and the validation of other design criteria such as span properties and correlation girth into the interleaver design. The proposed graphical approach suitably limits the search space for the different interleaver parameters. Thus, the generation of ARP interleavers validating the different design criteria is greatly simplified in comparison to previous methods.

Three contributions can be listed in Chapter 3. In Section 3.1.1.1, we propose a suitable optimization tool for the selection of the precoding ratio of PTCs, based on the analysis of the real extrinsic information exchange between the constituent codes of the TC with uniform interleavers.

Then, in Sections 3.1.2 and 3.1.3, two variants of PTC structures are proposed. They bring significant asymptotic improvements compared to the conventional TC scheme with parity-only puncturing, at the expense of a slight loss in convergence performance. The second one proposes a set of parameters that allows a flexible tradeoff between convergence and error floor. This feature can be of interest for communication systems requiring channel coding adaptability.

Finally, in Section 3.3.2, the correlation graph representation was reconsidered for the case of PTCs, considering their three-dimensional (3D) nature.

In Chapter 4, we first propose in Section 4.1.2 an original graphical representation of time and frequency span properties in a bi-dimensional L 1 space, that allows the validation of time and frequency span properties to be simplified.

Then, in Section 4.1.3, we introduce a suitable selection criterion for efficient channel interleavers that avoids running a large number of time-consuming error rate simulations. It involves evaluating the variance of the Mutual Information (MI) distribution in the FEC blocks.

The major contribution of Chapter 4 is the proposal in Section 4.3 of global channel interleaver models, based on regular or almost regular permutations. In state-of-the-art broadcasting systems, such as DVB-T2, a better control of the interleaver design parameters and a lower system latency and complexity are then achieved, thanks to the reduction in the number of channel interleaving components.

We also propose for DVB-T2-like systems an optimized bit interleaver construction which ensures the absence of bad interaction with the channel interleaver.

Chapter 1

Channel coding and interleaving techniques D ifferent channel coding and interleaving techniques have been included in wireless communication systems to cope with the increasing requirements of data rates, mobility, spectral efficiency and quality of service (QoS) [START_REF] Molisch | Wireless Communications[END_REF]. This chapter gives an overview of the channel coding and interleaving techniques studied in the framework of the thesis. It is organized as follows: Section 1.1 presents the basics of Turbo Codes (TCs). The general encoder structure and the MAP decoding algorithms are presented; then the main tools currently used to estimate TC performance in terms of convergence thresholds and asymptotic error rate are given; finally, one of the latest turbo-like coding schemes, named Precoded Turbo Code (PTC) is introduced. Section 1.2 gives the basics on interleaving for TCs: first, the main performance and implementation requirements for a TC interleaver are reviewed; then, the main relevant design criteria are derived; finally, several popular TC interleaving techniques are described. In Section 1.3, common channel interleaving techniques are discussed and Section 1.4 concludes the chapter.

CHAPTER 1. CHANNEL CODING AND INTERLEAVING TECHNIQUES

Channel coding

Parallel convolutional turbo codes introduced by Berrou et al. [START_REF] Berrou | Near Shannon limit errorcorrecting coding and decoding: Turbo-codes[END_REF] are an example of capacity-approaching codes. In addition to their excellent error rate performance, TCs are very flexible in terms of data frame length and code rate. Indeed, in comparison to other capacity-approaching codes, such as LDPC codes, the encoding of different data frame lengths and code rates can be configured in the same TC structure just by modifying some parameters. Therefore, they have been adopted in different applications of wireless communication systems, such as those listed in Table 1.1. This has motivated the choice of the code in our work. It is based, on TCs and one of its latest modifications, PTCs. In the following sections an overview of these codes is given. The performance of this family of codes depends on several parameters, such as generator polynomials and constraint length of the constituent codes, puncturing, interleaver type and decoding algorithm. The encoder structure, the decoding algorithm, as well as the methods to evaluate the TC performance are described below. The TC encoder is constituted of a parallel concatenation of two or more Recursive Systematic Convolutional (RSC) codes. Fig. 1.1 shows a basic representation of the TC encoder structure. The data sequence d is encoded by the first constituent code RSC 1, producing the parity sequence r 1 . Then, d is interleaved and sent to the second constituent code RSC 2 to generate the second parity sequence r 2 . The parity sequences as well as the data sequence are transmitted. Different parameters characterize the TC encoder structure: constituent code, trellis termination, interleaver and puncturing.

Application

Constituent code

RSC codes consist of a linear feedback shift register with memory length v and generator polynomials defining the output branch and the recursion connections. This convolutional code is systematic, since the input data sequence d is available together with the parity sequence at its output. The parity sequence is obtained by adding modulo-2 binary values in the shift register memory according to the feedforward polynomial. Similarly, the recursion branch is defined by the feedback polynomial. Fig. 1.2 shows the RSC constituent code of the LTE TC with feedback and feedforward polynomials, 13 and 15 in octal notation, respectively. This v = 3 convolutional encoder has 2 v = 8 possible state values, and the succession of states of the register depends on the departure state and on the succession of data at the input. The encoding process can be represented in a trellis diagram [START_REF] Glavieux | Convolutional Codes[END_REF], it is a 8 CHAPTER 1. CHANNEL CODING AND INTERLEAVING TECHNIQUES graphical representation of the different transition stages between the register states through time. This representation is useful when decoding convolutional codes, since a path in the trellis is associated to a given coded sequence.

Trellis termination

In order to properly decode a data sequence, the decoder needs to have some information about the initial and final states of the encoding process. Two types of trellis termination techniques are commonly used: inserting tail bits and tail-biting.

The first method involves setting the initial convolutional code state to a known value, and artificially introducing termination or tail bits at the end of the encoding process to make the shift register return to a known final state. The code rate is then slightly reduced by the transmission of tail bits, but considering long data frame lengths, this loss in code rate is usually negligible. The main drawback of this technique is that tail bits are not turbo encoded, thus neighboring data positions are less protected resulting in a loss of performance [START_REF] Boutillon | Iterative decoding of concatenated convolutional codes: Implementation issues[END_REF].

With tail-biting termination, the trellis diagram associated to the RSC code is made circular [START_REF] Weiss | Code construction and decoding of parallel concatenated tail-biting codes[END_REF], leading to a Circular RSC (CRSC) code. This technique requires a two-step encoding process. First, the data sequence is encoded from the zero state, and according to the final state value, a circular state is calculated. Second, the data sequence is encoded from its circular state, which ensures that the final state is also the circular state. Since no termination bits have to be introduced, this trellis termination method avoids any loss in code rate. Furthermore, all data positions are turbo encoded avoiding any edge effects, i.e., the whole sequence is protected in the same way.

Interleaver

One of its objectives is to reduce the effect of burst of errors in encoded bits (i.e., a group of consecutive erroneous encoded bits). It takes and produces data symbols from d in a different order, generating the interleaved sequence. Thereby, a burst of errors affecting the first constituent code (RSC 1) is spread out in the second one (RSC 2). The interleaver is a fundamental component of TCs. Its role is twofold.

CHANNEL CODING

First, it has an important impact on the achievable minimum Hamming distance of the TC. Thus, the TC error rate performance at very low error rates is highly related to the TC interleaver. Second, due to its scattering properties, it also acts on the correlation of exchanged extrinsic information during the iterative decoding process. A more detailed description of different interleaving techniques for TCs is given in Section 1.2.

Puncturing

In most of wireless applications using turbo coding, a mother code rate is defined and higher rates are obtained by puncturing some code bits [START_REF] Acikel | Punctured turbo-codes for BPSK/QPSK channels[END_REF], [START_REF] Mo | Analysis of puncturing pattern for high rate turbo codes[END_REF]. Usually, puncturing is periodic and the positions of the bits which are transmitted or not is given by a puncturing pattern or mask. Sometimes, similarly to the LTE standard, the puncturing pattern is generated by a more complicated mechanism such as the socalled rate matching mechanism [START_REF] Etsi | LTE Envolved Universal Terrestrial Radio Access(E-UTRA): Multiplexing and channel coding[END_REF].

Decoding algorithm for turbo codes

Soft Input Soft Output (SISO) decoding algorithms are required to decode TCs, since the constituent decoders of the turbo decoder have to exchange probabilistic information about the decoded sequence. The Maximum A Posteriori (MAP) algorithm and its modified versions are the most common algorithms used to decode TCs. The MAP algorithm, also known as the BCJR algorithm according to its inventors [START_REF] Bahl | Optimal decoding of linear codes for minimizing symbol error rate (corresp.)[END_REF], was proposed for estimating a posteriori probabilities of the states and state transitions of a Markov source observed in a memoryless noisy channel. Bahl et al. showed that the algorithm is optimal in terms of reducing the bit error rate when used for decoding convolutional codes. Indeed, in contrast to the Viterbi algorithm, which minimizes the probability of choosing an incorrect path through the code trellis, the MAP algorithm examines every path to minimize the probability of choosing an incorrect state transition for each trellis stage during the decoding process. This algorithm provides the estimated bit sequence together with the probability of correctly decoding each bit. Let us briefly present the main steps of its application in the case of a binary RSC code with rate R c = 1 2 . Let d = (d 0 , ..., d K-1 ) be the data sequence transmitted between instants 0 and K -1 using Binary Phase-Shift Keying (BPSK) modulation, over an Additive White Gaussian Noise (AWGN) channel. The received sequence at the output of the channel is: y = (y 0 , ..., y k , ..., y K-1 ), where y k = (y k,s , y k,r ), correspond to the channel observations of the systematic and parity bits received at instant k. The MAP algorithm provides a conditional Log-Likelihood Ratio (LLR) L (d k |y) for each data bit d k as follows: Its magnitude provides a measure of the reliability of the binary decision related to d k . Considering memoryless channel conditions, this LLR can be expressed as [START_REF] Bahl | Optimal decoding of linear codes for minimizing symbol error rate (corresp.)[END_REF]:

L (d k |y) = Ln P(d k = +1|y) P(d k = -1|y) (1.1)
L (d k |y) = Ln (s ,s)⇒d k =+1 {α k-1 (s ) • γ k (s , s) • β k (s)} (s ,s)⇒d k =-1 {α k-1 (s ) • γ k (s , s) • β k (s)} (1.2)
where (s , s)

⇒ d k = ±1 represents the set of possible transitions from state s k-1 = s to state s k = s when d k = ±1, α k-1 (s )
is the joint probability of having state s k-1 = s and the received sequence before k, γ k (s , s) is the branch metric at instant k, which corresponds to the probability of having a trellis transition from s k-1 = s to s k = s given the received symbol y k , and β k (s) is the probability of having s k = s given the received sequence after k.

The forward and backward metrics, α and β are recursively calculated by:

α k (s) = all s γ k (s , s) • α k-1 (s ) (1.3) β k-1 (s ) = all s γ k (s , s) • β k (s) (1.4)
During the decoding process, the MAP algorithm evaluates:

α k (s), ∀s : k = 0 → k = K -1, β k (s), ∀s : k = K → k = 1, and γ k (s , s), for all possible transitions from s k-1 = s to s k = s : k = 0 → k = K -1.
When trellis termination is used, if the initial RSC code state is initialized to s , α 0 (s ) = 1 and α 0 (s) = 0, ∀s = s . Similarly, if the final RSC code state is set to s , β K (s ) = 1 and β K (s) = 0, ∀s = s . In the case of tail-biting termination, α 0 (s) and β K (s) are initialized to 1 2 v , ∀s. Note that the circular property of the trellis is not used when decoding a single convolutional code. It comes into play in the iterative decoding process of TCs. At the end of each iteration, the final alpha values are copied to the initial alpha values for the next iteration and, conversely, the initial beta values are copied to the final beta values for the next iteration.

This algorithm was adapted by Berrou et al. for the iterative decoding of TCs [START_REF] Berrou | Near Shannon limit errorcorrecting coding and decoding: Turbo-codes[END_REF]. Then, the conditional LLR L (d k |y) provided by the MAP algorithm can be expressed as follows:

L(d k |y) = L a (d k ) + L c y k,s + L e (d k ) (1.5)
where L a (d k ) represents the a priori LLR of the k th bit, L Ch = L c y k,s represents the intrinsic information from the channel with L c as the channel reliability, and L e (d k ) represents the extrinsic LLR of d k , which depends on the observation of the parity bit received at instant k. As shown in Fig. 1.3, at each iteration, extrinsic information L e (d k ) from one SISO decoder is sent to the other one to be used as a priori information on d k . This exchanged extrinsic information is expected to improve with decoding iterations. In order to properly decode a data sequence, the constituent SISO decoders need to converge to the same decision for each of the decoded bits at the end of the iterative decoding process.

Π -1 Π Π L e1 (d) L e2 (d) L a1 (d) L a2 (d) L c y r1 L c y r2 L c y s SISO 1 SISO 2
Soft output of the channel

Error rate performance evaluation of turbo codes

The performance of an error correcting code and its decoder is generally evaluated in terms of the residual error rate at the output of the decoder [START_REF] Berrou | Codes and Turbo Codes, ser. IRIS international series[END_REF]. Two parameters are usually measured: the Bit Error Rate (BER), which corresponds to the ratio between the number of residual erroneous bits and the total number of transmitted information bits, and the Frame Error Rate (FER), which corresponds to the ratio between the number of codewords badly decoded and the total number of transmitted codewords.

An example of typical BER curves of coded and uncoded systems is shown in Fig. 1.4. These curves can be obtained by Monte Carlo simulations of the BER at different Signal-to-Noise Ratio (SNR) values E b /N 0 . 5 The BER curve of the coded system can be divided into three regions: low SNR region, waterfall region and error floor region. In the low SNR region, the code provides low correction capabilities, having error rates even higher than the uncoded scheme. The convergence threshold is the minimum SNR value such that the coded scheme performs better than the uncoded scheme. The waterfall region is found for a range of higher SNR values, where a small increase in the SNR yields a large reduction in the error rate. In the error floor region, a change in the slope is observed with respect to the waterfall region, which reduces the improvement of the error rate as E b /N 0 grows. For higher SNR values, the slope of the coded BER curve asymptotically approaches the slope of the uncoded curve and the gap between both curves is given by the asymptotic gain G a .

Convergence analysis of TCs using EXtrinsic Information Transfer (EXIT) chart

The performance of TCs in the waterfall region can be evaluated by Monte Carlo simulation of the BER. However, BER simulations can be time consuming. A method to predict the convergence behavior of the iterative decoding process was introduced by ten Brink [START_REF] Brink | Convergence behavior of iteratively decoded parallel concatenated codes[END_REF]. This method, called EXIT chart analysis, involves looking at the input/output relations of individual constituent SISO decoders to predict the behavior of the iterative decoder. Then, the extrinsic information transfer function of individual constituent decoders is measured and the behavior of the iterative decoder is predicted by analyzing the exchange of extrinsic information between the constituent SISO decoders. This analysis is carried out on the Mutual Information (MI) between the data sequence d and the extrinsic LLRs of the constituent decoders L e . The corresponding MI, IE = I(d; L e ), measures the average quantity of information provided by L e on the data sequence d and is evaluated as [START_REF] Hagenauer | The EXIT chart -Introduction to extrinsic information transfer in iterative processing[END_REF]:

I(d; L e ) = 1 -E log 2 (1 + e -Le ) (1.6)
where E represents the mean function. By applying the ergodicity theorem, the mean can be replaced by the time average and the MI can be measured from a large number K of samples. Then, I(d; L e ) can be evaluated as [START_REF] Hagenauer | The EXIT chart -Introduction to extrinsic information transfer in iterative processing[END_REF]:

I(d; L e ) = 1 - 1 K K i=1 log 2 (1 + e -d i L e,i ). (1.7)
The extrinsic information transfer function T of a constituent SISO decoder is then measured as:

I(d; L e ) = T(I(d; L a )) (1.8)
where IA = I(d; L a ) is the MI between the data sequence d and the a priori LLR at the input of the constituent decoder. The a priori LLR values can be provided by a virtual channel [START_REF] Hagenauer | The EXIT chart -Introduction to extrinsic information transfer in iterative processing[END_REF] as shown in Fig. 1.5. This channel can be modeled as an AWGN channel, considering the extrinsic output LLRs of the other constituent decoder to be independent Gaussian random variables [START_REF] Brink | Convergence behavior of iteratively decoded parallel concatenated codes[END_REF]. Furthermore, Berrou et al. [START_REF] Berrou | Near Shannon limit errorcorrecting coding and decoding: Turbo-codes[END_REF] showed that the extrinsic information approaches Gaussian-like distributions when the decoding process converges. In order to analyze the iterative decoding process, the extrinsic information transfer functions of both constituent decoders are plotted in the same EXIT chart. In the case of symmetric constituent convolutional codes, the SISO decoders have the same extrinsic information transfer function. Thus, only one of them needs to be measured. When the EXIT chart is evaluated at a SNR lower than the convergence threshold of the TC, both curves intersect and the decoding trajectory is blocked, as shown in Fig. 1.6(a). Then, the iterative decoding process does not converge. In contrast, when the SNR is higher or equal to the decoding threshold of the TC, a tunnel is opened between the curves and the iterative decoding process converges, as illustrated in Fig. 1.6(b). Then, the decoding threshold for a TC corresponds to the SNR for which a tunnel starts to open and a decoding trajectory can be observed.

MI measurement d={+1, -1} SISO RSC I(d;L e ) L e L a L c Y Virtual AWGN channel AWGN channel

Distance spectrum estimation methods

The analysis of the TC performance at very low error rates or high SNRs is a complicated task. In fact, reliable BER simulations in the error floor region are very time consuming and require an adequate hardware. In [START_REF] Perez | A distance spectrum interpretation of turbo codes[END_REF] of the code: the higher the d min , the lower the error floor. It was also shown that for high SNRs the error rate performance approaches the union bound truncated to the contribution of the minimum distance. In some cases, the contribution of the first terms of the distance spectrum can be useful to obtain a better approximation as it was shown by Garello et al. [START_REF] Garello | On error floor and free distance of turbo codes[END_REF]. Then, the TC performance in the error floor region can be analytically estimated by the union bounds with the knowledge of the first terms of the TC distance spectrum and their multiplicities. The FER and BER union bounds are expressed as [START_REF] Vucetic | Turbo codes: principles and applications[END_REF]:

FER ≤ 1 2 d≥d min A d erfc dR E b N 0 (1.9) BER ≤ 1 2 d≥d min w d K erfc dR E b N 0 (1.10)
where K is the data sequence size, R is the code rate, d min is the minimum Hamming distance of the code and A d is the number of codewords with weight d (i.e., the multiplicity). The information bit multiplicity w d is the sum of the Hamming weights of the A d input sequences with Hamming weight d. The complementary error function erfc(x) is given by erfc

(x) = 2 √ π ∞
x e -t 2 dt. Different methods to estimate the TC distance spectrum have been studied. In [START_REF] Berrou | Computing the minimum distance of linear codes by the error impulse method[END_REF], Berrou et al. introduced the error impulse method that is based on the analysis of the correction capacity of the decoder. The method involves introducing an error impulse into an all-zero codeword and identifying the maximum impulse amplitude making the decoder converge towards the all-zero sequence. It was shown that, under the maximum likelihood decoding assumption, the maximum amplitude of such an error impulse is equal to d min . However, when the decoding algorithm does not perform maximum likelihood decoding, as in the case of iterative decoding, this method only produces an estimate of d min . Motivated by these results, Garello and Vila proposed the all-zero iterative decoding algorithm [START_REF] Garello | The all-zero iterative decoding algorithm for turbo code minimum distance computation[END_REF] that involves placing a high amplitude error impulse in a specific data index of a modulated all-zero codeword before decoding it. Gaussian noise was added to the all-zero codeword to help the decoder converge towards a low weight codeword concurrent to the all-zero. It allows finding an upper bound on the minimum distance for all codewords having a 1 in the specific data index being tested.

Crozier et al. proposed multiple impulse methods [START_REF] Crozier | Estimating the minimum distance of turbo-codes using double and triple impulse methods[END_REF], [START_REF]Estimating the minimum distance of large-block turbo codes using iterative multiple-impulse methods[END_REF], and [START_REF] Crozier | Estimating the minimum distance of largeblock turbo codes using the event impulse method[END_REF] that follow the same strategy as in [START_REF] Garello | The all-zero iterative decoding algorithm for turbo code minimum distance computation[END_REF]. The difference lies in the number of error impulses introduced in the all-zero codeword. It was reported by Crozier et al. [START_REF]Estimating the minimum distance of large-block turbo codes using iterative multiple-impulse methods[END_REF] that the Double, Triple and Event Impulse Methods (DIM, TIM and EVIM) increase the accuracy of the minimum distance estimation obtained with a single error impulse, at the expense of a higher complexity. Indeed, since the minimum distance of the constituent RSC codes of the TC is related to short data sequences that make the RSC encoder leave and return back to the zero state, the second index in the DIM helps the TC decoder to converge towards such sequences in the first constituent RSC code. In the TIM, the additional impulse is intended to make the TC decoder converge towards such sequences in both constituent RSC codes. Finally, in the EVIM, the error impulses are placed according to input events generating low-weight RSC codewords. Given that the test procedure is similar for the multiple impulse methods, only the single error impulse is described below.

Let c be a codeword sequence:

1. Select a value of SNR between 2 dB and 15 dB.

2. Initialize d min to K.

3. For i = 0 to K -1, where i is the data position being tested:

• Initialize c to the all-zero sequence.

• Send c through an AWGN channel.

• Force P (c i = +1) = 1 to introduce the error impulse.

• Apply iterative decoding to estimate the codeword c i until a valid codeword ĉi is obtained.

• Evaluate its Hamming weight w(ĉ i ).

• If w(ĉ i ) ≤ d min , then d min ← w(ĉ i ) and A d ← 1; else if w(ĉ i ) = d min and ĉi is not stored, then A d ← A d + 1 and store w(ĉ i ).
The suitable SNR value for the evaluation of the algorithm depends on R and K. This value is typically in the error floor region and can be determined through repeated trials.

Precoded turbo codes

In order to improve the error rate performance of TCs, turbo-like codes have been studied in the last years. Such codes can be defined as coding schemes in which the information sequence is encoded by different constituent codes. The data sequence is interleaved between the constituent codes and iterative SISO decoding is performed to improve the decoding of each constituent code [START_REF] Gracie | Turbo and turbo-like codes: Principles and applications in telecommunications[END_REF].

Abbasfar et al. studied the precoding technique applied to turbo-like codes [START_REF] Abbasfar | Accumulate repeat accumulate codes[END_REF]. It was shown that the iterative decoding performance of such codes can be improved by prefixing a rate-1 accumulator to the encoder structure. This allows the decoding threshold of turbo-like codes to be reduced without altering their code rate. This technique was recently applied to TCs by Tong et al. [START_REF] Tong | Precoded turbo code within 0.1 dB of Shannon limit[END_REF] resulting in a new type of turbo-like codes named Precoded Turbo Codes (PTCs). In order to investigate possible TC error rate performance improvements, a research on PTCs is carried out in Chapter 3.

Precoded turbo encoder structure

The basic PTC encoder structure considered in this thesis is shown in Fig. 1.7. The precoder is prefixed and connected to the TC via the interleaving function Π 1 . It is composed of a parallel-to-serial converter block, a rate-1 accumulator and a serialto-parallel converter block. As introduced in [START_REF] Tong | Precoded turbo code within 0.1 dB of Shannon limit[END_REF], only ρK bits of the data frame d are encoded by the accumulator, ρ being the precoding ratio. This parameter introduces a degree of freedom for code optimization.

INTERLEAVING TECHNIQUES FOR TURBO CODES

Decoding algorithm for precoded turbo codes

The structure of the iterative decoding algorithm presented in section 1.1.1.2 was adapted to decode the PTC. The basic PTC decoder structure implemented in this work is shown in Fig. 1.8. The inputs of the constituent SISO decoders of the TC, SISO 1 and SISO 2, are: the channel observations on the parity sequences r 1 and r 2 , the channel observations on the non-precoded data bits, and the a priori LLRs on the ρK accumulator parity bits. The outputs of these decoders, E 1 and E 2 , are extrinsic information on the sequence encoded by the TC. E 1 and E 2 are exchanged between SISO 1 and SISO 2 at each iteration, only the part related to the accumulator parity bis is sent as a priori information A 1,0 and A 2,0 to the SISO decoder of the accumulator (SISO 0). It also receives the channel observations on the accumulator data bits. SISO 0 computes the extrinsic information E 0 that is sent back as a priori information A 0,1 and A 0,2 to SISO 1 and SISO 2, respectively, to reduce the BER in further iterative decoding iterations.

SISO 0 SISO 1 SISO 2 E 2 Π 2 -1 Π 2 Π 1 -1 Π 2 -1 Π 2 Π 1 -1 Π 1 E 0 A 0,1 A 0,2 A 2,1 E 1 A 1,2 A 1,0 E 2 A 2,0 L Ch,2 L Ch,1 L Ch,0

Interleaving techniques for turbo codes

This section gives an overview of different requirements and design criteria for TC interleavers. Common interleaving techniques for TCs are also described.

An interleaver is defined as a device that reads the symbols from an input vector d = (d 0 , d 1 , ..., d K-1 ) and writes them to an output vector

d = (d Π(0) , d Π(1) , ..., d Π(K-1) )
where K represents the data sequence length and Π denotes the interleaving or permutation law. A symbol read out from address Π(i) in d is written to address i in d . When using CRSC codes as constituent codes of the TC, d and d are associated to a circle because CRSC codes apply tail-biting termination with a circular trellis [START_REF] Weiss | Code construction and decoding of parallel concatenated tail-biting codes[END_REF]. A possible representation of such an interleaver is shown in Fig. 1.9.

The interleaver is a key component of turbo coding. Indeed, as introduced by Berrou and Glavieux [START_REF] Berrou | Near optimum error correcting coding and decoding: turbo-codes[END_REF], the minimum Hamming distance d min of the TC is not only defined by its constituent encoders but fixed through the TC interleaver. Furthermore, thanks to its scattering properties, it also acts on the correlation of extrinsic information during the iterative decoding process [START_REF] Hokfelt | Interleaver design for turbo codes based on the performance of iterative decoding[END_REF].

Π(j) Π(i) Π(0) i j d d' 0 . . . 1 Π (1)

Performance requirements for a TC interleaver

As introduced in section 1.1.1.5, TC performance in the error floor region is mainly related to d min . Better performance in this region is obtained with higher values of d min . In order to obtain such values, the interleaver has to avoid feeding the second constituent encoder with the same data sequence patterns that produce low Hamming weight codewords in the first constituent encoder of the TC. Independently of the interleaver choice, data sequences with a single 1 will produce the same codeword weights in both constituent encoders. This motivates the use of RSC codes as constituent codes for the TC, because the output weight due to a weight-1 data sequence is high and even infinite for infinite frame sizes. A Return To Zero (RTZ) sequence is defined as any finite input sequence which makes a RSC code leave the zero state and return back to the same state. Short RTZ sequences have an important impact on the RSC distance spectrum. Indeed, low weight codewords, in the RSC code, correspond to short RTZ sequences.

As far as the TC is concerned, the Hamming weight of codewords resulting from a single RTZ sequence is increased by maximizing the scattering of data through the interleaver. It was shown in [START_REF] Crozier | New high-spread high-distance interleavers for turbo-codes[END_REF] that the increase in scattering of data leads to a better TC performance in the error floor region. In the case of codewords made up of more than one RTZ sequence a disorder must be introduced in the permutation function [START_REF] Berrou | Designing good permutations for turbo codes: towards a single model[END_REF]. In fact, multiple RTZ sequences evenly permuted can compose new RTZ sequences for the second constituent code. Furthermore, the disorder in the permutation makes the parity generation of both constituent encoders as diverse as possible, increasing the weight of such codewords [START_REF] Berrou | Near optimum error correcting coding and decoding: turbo-codes[END_REF]. Then, in terms of TC performance, the interleaver should allow a maximum scattering of data, and a maximum disorder in the interleaved data sequence.

Implementation requirements for a TC interleaver

The principal requirements of a TC interleaver in terms of implementation are: a reduced hardware complexity, which corresponds to the computational complexity of the interleaved addresses and/or the memory needed to store them, and the adaptation to the throughput requirements of the transmission system.

In cutting-edge wireless communication systems, high turbo decoding throughputs are required. This is achieved by using internal parallelization in the turbo decoder. The internal parallelism method, also known as the method of parallel windows [START_REF] Blankenship | High-throughput turbo decoding techniques for 4G[END_REF], involves dividing the trellis of the constituent convolutional codes into W windows of the same length L. Then, in the turbo decoder, W processors working in parallel treat the W windows of the code trellis increasing the decoding throughput by a factor W . Thus, a degree of parallelism of W is achieved.

For parallel processing of W windows of size L, extrinsic values must be stored in W memory banks. The access connections of the processors to the memory banks are defined by the TC interleaving/deinterleaving function. Memory access contentions appear when two or more processors try to access the same memory bank concurrently. These contentions are avoided if the TC interleaver is contention free for a window of size L. Then, in order to allow an efficient parallelization of the turbo decoding the TC interleaver has to be contention free for the desired degree of parallelism.

Interleaver design criteria

According to the performance requirements, some interleaver design criteria can be established. The first one is based on the total spatial distance or span between non-interleaved and interleaved data positions. In fact, the maximization of the span results in the maximization of the scattering of data. The second one is based on the correlation between the extrinsic information in the turbo decoder.

Span properties

The span value associated with a couple of symbols in positions i and j is defined according to [START_REF] Crozier | New high-spread high-distance interleavers for turbo-codes[END_REF], [START_REF] Berrou | Designing good permutations for turbo codes: towards a single model[END_REF] as:

S(i, j) = f (i, j) + f (Π(i), Π(j)) (1.11) where f (u, v) = min[|u -v| , K -|u -v|] (1.12)
Then, the minimum value of span S min associated to the interleaver is evaluated as:

S min = min i,j [S(i, j)] (1.13)

CHAPTER 1. CHANNEL CODING AND INTERLEAVING TECHNIQUES

It was shown in [START_REF] Boutillon | Maximum spread of D-dimensional multiple turbo codes[END_REF] that the maximum achievable value for S min has a theoretical upper bound of √ 2K when using tail-biting termination. The minimum span value affects the TC distance spectrum. In particular, for random-based interleavers, the increase of minimum span was shown to yield larger minimum Hamming distances for the TC [START_REF] Crozier | New high-spread high-distance interleavers for turbo-codes[END_REF]. Therefore, this value needs to be maximized.

Correlation girth

In an iterative decoding process, a high correlation between encoded symbols results in a loss of error rate performance. Actually, if the encoder introduces a high correlation among the encoded symbols, a decoding error can propagate during the different decoding iterations. Different tools have been proposed to design encoders reducing the introduced correlation among the encoded symbols.

Correlation graph analysis is a common tool used to design LDPC codes. In [START_REF] Hu | Progressive edge-growth tanner graphs[END_REF], the authors introduced the Progressive Edge Growth algorithm, which allows the construction of LDPC parity-check matrices with large correlation girths g (i.e., minimum correlation cycle). It was shown that increasing correlation girth values leads to error rate performance improvements. Indeed, the correlation between extrinsic information from different variable nodes is reduced by increasing the correlation girth. Therefore, the influence of correlation cycles in the iterative decoding process is minimized.

In the case of TCs, the decoder output at position i depends on the received sequence at position i and, due to the constituent code, it also depends on positions at the vicinity of i. The decoder output at position i similarly depends on the provided extrinsic information and its correlation properties are defined by the interleaver [START_REF] Hokfelt | Turbo codes: correlated extrinsic information and its impact on iterative decoding performance[END_REF]. Therefore, the interleaver should allow a low correlation between extrinsic information exchanged by constituent decoders and the data sequence [START_REF] Sadjadpour | Interleaver design for short block length turbo codes[END_REF]. As in LDPC code design, a correlation graph can also be established when designing TC interleavers [START_REF] Saouter | Selection procedure of turbocode parameters by combinatorial optimization[END_REF]. This graph is defined by the permutation law and the vertices of d and d as shown in Fig. 1.10. Then, the interleaver should be designed to maximize the correlation girth.

Π(i)

Interleaver types

The interleavers can be classified in two main groups: random-based and algebraic interleavers. In random-based interleavers, the interleaved addresses are randomly obtained. These addresses must then be stored to be used when interleaving/deinterleaving is performed. In algebraic interleavers, the interleaved addresses are obtained by an algebraic expression. Only some parameters defining the corresponding expression have to be stored. Although algebraic interleavers provide a smaller disorder degree in the interleaved addresses than random-based interleavers, their structure is more appropriate for the parallelization of the turbo decoder. Therefore, algebraic interleavers are more suitable to cope with the implementation requirements of a TC interleaver. Within the random-based interleavers family, random and partially random interleavers have been studied. Three of the most popular algebraic interleaver types are: Dithered Relative Prime (DRP) interleavers, Quadratic Permutation Polynomial (QPP) interleavers, and Almost Regular Permutation (ARP) interleavers. A description of these interleavers, as well as a comparison among algebraic interleavers are given in the following sections.

Random permutations

Random interleavers, as introduced by Divsalar and Pollara [START_REF] Divsalar | Turbo codes for deep-space communications[END_REF], are defined by a random permutation of K elements with no repetitions. The data sequence is written into the interleaver memory block and read out in a specific random order. The same interleaver is used for all subsequent data sequences. In [START_REF]Multiple turbo codes[END_REF], an analysis of the effect of random interleavers on low-weight data sequence, which may produce low codeword weights, was carried out. It was shown that the probability to have a low-weight data sequence interleaved to a similar sequence decreases with the data sequence weight. Then, it was concluded that the minimum distance of TCs is more likely to be governed by weight-2 data sequences.

An analysis on the effect of the interleaver on the distance spectrum of TCs in a short data sequence was also performed in [START_REF] Divsalar | Turbo codes for deep-space communications[END_REF]. It was shown that better TC distance spectra were obtained by using random permutations than by using structured permutations like row-column block. In fact, low-weight data sequences such as the one shown in Fig. 1.11 cannot be broken by a row-column block interleaver.

A useful tool for the design of TCs was introduced by Benedetto and Montorsi [START_REF] Benedetto | Unveiling turbo codes: some results on parallel concatenated coding schemes[END_REF]. The so called uniform interleaver is a probabilistic interleaver based on random permutations that generate all possible permutations for a given data sequence size with equal probability. It has been used to calculate error-rate bounds as shown in [START_REF] Benedetto | Unveiling turbo codes: some results on parallel concatenated coding schemes[END_REF]. Furthermore, the uniform interleaver allows the evaluation of the average TC performance for all possible interleavers, providing a TC performance benchmark regardless of the interleaver selection.

Partially random permutations

For random interleavers, there is still a non-negligible probability that low-weight data sequences are interleaved to similar data sequences. This probability can be reduced by a proper design of the interleaver leading to partially random permutations.

In [START_REF] Robertson | Illuminating the structure of code and decoder of parallel concatenated recursive systematic (turbo) codes[END_REF], a method to generate partially random permutations was proposed. First, a random interleaver is generated. Then, for data sequences with a maximum weight of 6, low-weight codewords are listed. Finally, a couple of the interleaved positions are swapped to break such low weight codewords. After swapping, a new verification must be carried out, since the swapping of interleaved positions can generate a new low weight codeword caused by another data sequence. It was shown that this permutation improves the BER curve obtained with a random permutation in the error floor region. The main drawback of this procedure is that it cannot be exhaustively applied to all possible data sequences. Actually, the analysis of codeword weights generated with data sequences of weights higher than 6 is a very complex procedure, considering the high number of sequences to list.

Another partially random permutation called S-random interleaver was introduced by Divsalar and Pollara in [START_REF] Divsalar | Multiple turbo codes for deep-space communications[END_REF]. As in the case of random interleavers, the data sequence is written into the interleaver memory block. Then, each data position is randomly read out from the memory and compared with the S previously selected. If the current selection is equal to any of the S previous selections within a spatial distance of ±S, then the current selection is rejected. This avoids that problematic data sequences of length smaller than S result in similar data sequences after interleaving. The process is repeated until all K data positions are read out from the memory. The searching time for this algorithm increases with S and its convergence is not guaranteed. However, it was observed in [START_REF] Divsalar | Multiple turbo codes for deep-space communications[END_REF] that choosing S < K 2 usually produces a solution in a reasonable time.

An improvement to the S-random interleaver was proposed by Crozier [START_REF] Crozier | New high-spread high-distance interleavers for turbo-codes[END_REF]. The new High-Spread Random (HSR) interleaver is generated following a similar pro-

INTERLEAVING TECHNIQUES FOR TURBO CODES

cedure to the one used for the S-random interleaver. The main difference lies in the criterion of selection of the permuted positions, which is now based on the span between non-interleaved and interleaved data positions. As shown in [START_REF] Crozier | New high-spread high-distance interleavers for turbo-codes[END_REF], HSR interleavers improve the TC performance obtained with random and S-random interleavers.

Regular Interleaver

A Regular Interleaver (RI) is defined as:

Π(i) = (P •i) mod K (1. 14
)
where P is the RI period that must be relatively prime to K, i = 0...K -1 is the address of the data symbol after interleaving and Π(i) is its corresponding address before interleaving. It was shown in [START_REF] Dolinar | Weight distributions for turbo codes using random and nonrandom permutations[END_REF] that the theoretical upper bound of the maximum achievable value for S min ( √ 2K ) can be approached by this interleaver. Furthermore, for data frame sizes that can be factored in the form 2n 2 , the upper bound is exactly achieved by imposing simple conditions on P . On the other hand, this permutation does not allow a good TC performance in the error floor region. Indeed, rectangular RTZ error patterns, which are composed of multiples RTZ sequences, cannot be efficiently avoided due to its regular structure [START_REF] Berrou | Designing good permutations for turbo codes: towards a single model[END_REF] as in the row-column interleaver case shown in Fig. 1.11. However, this interleaver is used as a basis for improved interleavers thanks to its good span properties.

Dithered Relative Prime

DRP interleavers were introduced by Crozier and Guinand [START_REF] Crozier | High-performance low-memory interleaver banks for turbo-codes[END_REF]. The data symbols are read out in a permuted order from the input vector v in and written to the output vector v out . This interleaver is composed of three stages as shown in Fig. 1.12. First, the input vector v in is read out via a dither vector r. This vector provides a local permutation on each F positions of the data sequence. Then, the resulting vector v a is permuted by a RI of period P that includes a constant shift s. Finally, the resulting vector v b is written to the output vector v out through the dither vector w, which provides a local permutation on each G positions of v b . Thus, the dither vectors are intended to break the regular structure of the RI to some extent. Short dither vectors do not destroy the good span properties that can be achieved by a RI but tend to reduce the minimum span value somewhat.

To ensure the bijectivity of the complete interleaver function, the interleaver length K must be multiple of both F and G. Then, prime frame sizes must be avoided. However, this is not a problem because the data sequence lengths commonly used in practice are even. Let us define the three interleaver components by v a

(i) = v in (Π a (i)), v b (i) = v a (Π b (i)), and v out (i) = v b (Π c (i))
. The complete interleaver function can then be written as:

Π(i) = Π a (Π b (Π c (i))) (1. 15
)
where i = 0...K-1 is the write address in the output vector v out and Π(i) is the read address from the input vector v in . Thus, the input vector is interleaved following:

v out (i) = v in (Π(i)) (1.16)
Only r, w, s and P should be stored to implement the interleaver. As reported in [START_REF] Crozier | High-performance low-memory interleaver banks for turbo-codes[END_REF], further reduction on parameters can be performed. Let M be the least common multiple of F and G, for any dithered vectors r and w it can be shown that:

Π((i + M ) mod K) = (Π(i) + M •P ) mod K (1.17)
It follows that the interleaver addresses can be recursively calculated as:

Π(i) = (Π(i -1) +U (i mod M ) )mod K (1.18)
where the M address increments of the vector U are computed as follows:

U (i) = (Π(i) -Π(i -1))mod K, i = 0...M -1 (1.19)
with Π from (1.15). Then, only the M elements of U have to be stored to implement the interleaver according to (1.18). The TC distance spectrum with tail-biting does not depend on the value of Π(0) and the dependence for tail bits termination is weak [START_REF] Crozier | Universal turbo code design for wireless communications[END_REF]. Then, Π(0) can be set to zero to reduce implementation complexity [START_REF] Crozier | Rate-compatible turbo codes designed with puncture-constrained DRP interleavers[END_REF]. As discussed in [START_REF] Crozier | High-performance low-memory interleaver banks for turbo-codes[END_REF], a suitable selection of the dither vectors size is M = F = G. This provides the largest amount of dither with the smaller number of address increments. Furthermore, it is also quite useful when designing good DRP interleavers for TCs with data puncturing [START_REF] Crozier | On designing turbo-codes with data puncturing[END_REF].

INTERLEAVING TECHNIQUES FOR TURBO CODES

25

DRP interleavers allow a parallelism of degree W equal to any multiple of the dither vector length M , provided that W remains a factor of K [START_REF] Crozier | Universal turbo code design for wireless communications[END_REF]. In addition, it was shown that DRP interleavers outperform random and HSR interleavers [START_REF] Crozier | On designing turbo-codes with data puncturing[END_REF] and even QPP interleavers for long frame sizes [START_REF] Crozier | Universal turbo code design for wireless communications[END_REF].

Quadratic Permutation Polynomial

QPP interleavers, proposed by Sun and Takeshita [START_REF] Sun | Interleavers for turbo codes using permutation polynomials over integer rings[END_REF], are based on permutation polynomials over the integer ring Z K . This interleaver was adopted in the LTE standard [START_REF] Etsi | LTE Envolved Universal Terrestrial Radio Access(E-UTRA): Multiplexing and channel coding[END_REF] and is completely defined by the algebraic expression:

Π(i) = (f 1 i + f 2 i 2 )mod K (1. 20
)
where i = 0...K -1 is the address of the data symbol after interleaving and Π(i) is its corresponding address before interleaving. The constant coefficient in the permutation polynomial (i.e., the coefficient for i 0 ) was omitted since it corresponds to a simple cyclic shift of the permutation. Furthermore, with proper termination of the trellis, this has no effect on the TC performance. The necessary and sufficient condition for the polynomial in (1.20) to define a valid permutation can be divided into two cases for even data sequence lengths:

1. 2 n divides K for n > 1: Then, f 1 is relatively prime to K and all prime factors of K are also factors of f 2 .

2. 2 n divides K for n = 1, but not for n > 1: Then, f 1 + f 2 is odd, f 1 is relatively prime to K 2 and all prime factors of K, excluding 2, are also factors of f 2 .

For prime data sequence lengths, there are no valid permutations of the form (1.20) for a non-zero f 2 [START_REF] Takeshita | On maximum contention-free interleavers and permutation polynomials over integer rings[END_REF]. However, this is not a problem for practical implementation frame sizes.

The minimum distance of a subset of low-weight data sequences with weight of the form 2m, m being a small positive integer, is used as a criterion to select the coefficients of the permutation polynomial [START_REF] Sun | Interleavers for turbo codes using permutation polynomials over integer rings[END_REF]. In fact, the minimum distance of the subset is normally close to the real TC minimum distance and can be used as an upper bound. Then, the minimum distance and its multiplicity in this upper bound can be controlled by selecting parameters f 1 and f 2 . It was observed in [START_REF] Sun | Interleavers for turbo codes using permutation polynomials over integer rings[END_REF] that QPP interleavers can avoid weight-2 data sequences resulting in similar data sequences after interleaving. This is a very important property since such sequences dominate the TC performance in the error floor region.

An attractive property of QPP interleavers is that they are maximum contention free [START_REF] Takeshita | On maximum contention-free interleavers and permutation polynomials over integer rings[END_REF]. They allow any parallelism of degree W that divides K. Furthermore, the QPP interleaver function can also be recursively calculated as in the case of DRP interleavers. Then, only additions are needed for its implementation [START_REF] Moision | Coded modulation for the deep-space optical channel: Serially concatenated pulse-position modulation[END_REF]. In terms of implementation, the only drawback of QPP interleavers is that their inverse polynomial is not always of the same degree. Then, to reduce complexity, the selected QPP interleaver should have the lowest degree inverse polynomial. Some conditions on f 2 can be imposed to have a quadratic inverse QPP polynomial [START_REF] Ryu | On quadratic inverses for quadratic permutation polynomials over integer rings[END_REF]. Finally, as shown in [START_REF] Sun | Interleavers for turbo codes using permutation polynomials over integer rings[END_REF], QPP interelavers improve the TC performance obtained with S-random interleavers for short and medium data sequence lengths, and for long frame sizes they provide a performance close to the one obtained with the S-random interleavers.

Almost Regular Permutation

ARP interleavers were proposed by Berrou et al. [START_REF] Berrou | Designing good permutations for turbo codes: towards a single model[END_REF]. Since their introduction they have been adopted in communication standards such as DVB-RCS/RCS2 [START_REF] Etsi | Digital Video Broadcasting (DVB): interaction channel for satellite distribution systems[END_REF], [START_REF] Etsi | Digital Video Broadcasting (DVB): second generation DVB interactive satellite system (DVB-RCS2): Part 2: Lower layers for satellite standard[END_REF] and WiMAX [START_REF] Ieee | IEEE standard for local and metropolitan area networks, Part 16: Air interface for fixed and mobile broadband wireless access systems[END_REF]. This interleaver is based on a RI of period P and a vector of shifts S as follows:

Π(i) = (P •i + S(i mod Q))mod K (1.21)
where i = 0...K -1 is the address of the data symbol after interleaving and Π(i) is its corresponding address before interleaving. The RI component is intended to avoid error patterns made up of single RTZ sequences. In order to break rectangular error patterns [START_REF] Berrou | Designing good permutations for turbo codes: towards a single model[END_REF], some disorder is introduced into the permutation via the vector of shifts S. The choice of this vector must ensure that the good span properties of the RI are preserved with the introduction of S. The number of elements in S is called disorder cycle length or disorder degree and is denoted by Q. This vector is defined as:

S(i mod Q) = A(i mod Q)P + B(i mod Q), (1.22)
where A and B are vectors of length Q and all their elements are multiples of the disorder cycle Q. When using tail-biting termination, S(0) can be set to zero since the properties of the permutation do not change for any rotation. Then, the permutation can be implemented by only storing Q parameters. Given that K has to be a multiple of Q, prime data sequence lengths must be avoided, which is not a problem for practical implementation frame sizes. Furthermore, data sequence lengths multiples of a small integer Q tend to provide more possible parallelism degrees W . In fact, ARP interleavers allow any parallelism of degree W provided that K Q is a multiple of W [START_REF] Nimbalker | ARP and QPP interleavers for LTE turbo coding[END_REF]. A strategy to select the parameters of the permutation was presented in [START_REF] Berrou | Designing good permutations for turbo codes: towards a single model[END_REF]. First, a small disorder degree is selected, typically 4, 8 or 12 according to the frame size. Then, different sets of possible parameters, providing the best span properties, are found. Finally, the best set of parameters is selected according to the estimated minimum Hamming distance of the TC. As stated in [START_REF] Berrou | Designing good permutations for turbo codes: towards a single model[END_REF], this method does not systematically provide the best parameters for the ARP function, but allows to identify possible sets of appropriate parameters.

Another method proposed in [START_REF] Saouter | Selection procedure of turbocode parameters by combinatorial optimization[END_REF] is based on the maximization of the correlation girth. First, the value of P is chosen at random. Then, the candidate shifts for S are randomly set one by one. The correlation girth is then evaluated each time that a new shift value is set and shift values generating a low correlation girth are rejected. Given that the ARP permutation is periodic with period Q, only a small number of data positions are considered to evaluate girths. As shown in [START_REF] Saouter | Selection procedure of turbocode parameters by combinatorial optimization[END_REF], ARP interleavers obtained through this method outperform S-random interleavers.

Comparison of algebraic interleavers

According to the description of DRP, QPP and ARP interleavers, similar interleaving properties can be expected from these interleaver families. Indeed, a good span can be achieved by their RI component. Furthermore, all of them allow the introduction of disorder in the interleaver data sequence. It is obtained by the dither vectors in the DRP case, the quadratic term in the QPP case, and the vector of shifts in the ARP case. On the other hand, only a few parameters need to be stored for their implementation. In addition, they are also well suited for parallel implementation of the turbo decoder. Even if the QPP interleaver is maximum contention free, a similar degree of parallelism can be achieved with all of them because very high parallelism degrees are not suitable for practical implementation. Finally, it is noteworthy that DRP and ARP interleavers are quite suitable to validate design criteria such as span and correlation girth during their parameters selection. This is not possible for interleavers like QPP, since all permutation parameters are needed to define any permuted position. Then, the configuration of QPP parameters cannot be decomposed as in the case of DRP or ARP.

Channel interleaving techniques

In this section the requirements for a channel interleaver are presented, and different published channel interleaver models are discussed.

Forward Error Correction (FEC) codes are now able to approach Shannon capacity [START_REF] Costello | Applications of errorcontrol coding[END_REF], [START_REF] Lin | Error Control Coding, Second Edition[END_REF] especially for transmissions over memoryless channels, in which errors are randomly distributed and statistically independent. In contrast, when FEC codes are used in transmissions over channels in which signal undergoes impulsive noise (i.e., error bursts in a short period of time) and/or selective fading (i.e., interference in a short frequency interval), the error rate performance can be greatly degraded. One possible solution to such a problem involves distributing error patterns arriving in bursts among several FEC frames. Therefore, channel interleaving [START_REF] Vangelista | Key technologies for next-generation terrestrial digital television standard DVB-T2[END_REF] is introduced to uniformly distribute codewords in time and frequency in such a way that the transmitted symbols subject to impulsive noise and selective fading do not end up in the same coded frame.

Channel interleavers have been included in the last generation of broadcast systems such as DVB-SH [START_REF] Etsi | Digital Video Broadcasting (DVB): frame structure, channel coding and modulation for satellite services to handheld devices (SH) below 3 ghz(DVB-SH)[END_REF] and DVB-T2 [START_REF] Etsi | Digital Video Broadcasting (DVB): frame structure channel coding and modulation for a second generation digital terrestrial television broadcasting system (DVB-T2)[END_REF]. Although explicit design criteria were not reported, performance and implementation requirements are listed below.

From the error rate performance point of view, the overall communication system has to benefit from the available time and frequency diversities of the encountered channel. This is achieved by using modulation techniques such as OFDM together with a channel interleaver. In order to maximize the benefit of these diversities in the overall system, the channel interleaver has to maximize the scattering of transmitted symbols in both time and frequency dimensions. It allows the overall system to overcome channel impairments that are common in a broadcast service.

In terms of implementation, a reduced hardware complexity is sought for both, for the computation of the interleaved addresses as well as for the storage of the interleaved symbols. Common channel interleavers have a large length as in the case of DVB-T2 [START_REF] Etsi | Digital Video Broadcasting (DVB): frame structure channel coding and modulation for a second generation digital terrestrial television broadcasting system (DVB-T2)[END_REF]. Thus, the channel interleaver has to be also designed to ensure a reduced latency considering its large length.

Channel interleaver types

Channel interleavers can be divided into two main groups: Adaptive and nonadaptive channel interleavers. In the former group, the interleaver structure is adapted to a given property of the encountered channel. In the second one, the interleaver structure remains the same for any channel and a given set of system parameters. Two examples of adaptive channel interleavers are interleavers with depth or length adapted to Doppler shift and interleavers with interleaving function adapted to the Channel State Information (CSI). Within the second group a representative channel interleaver is the one included in DVB-T2. A description of these interleavers is given below.

Adaptive interleaver based on Doppler shift

A row-column block interleaver structure with variable depth designed for the fading channel was proposed in [START_REF] Li | Adaptive interleaver based on the measurement of Doppler shift in fading channel[END_REF]. The corresponding method for interleaver depth optimization can be described as follows: let N m be the number of transmitted bits during the coherence time of the channel for a given maximum Doppler shift f m . Then, the interleaver length is chosen according to the minimization of a cost function f (d s , δ), where d s is the system delay and δ the relative gain.

This method presents the advantage of dimensioning the latency and required memory with respect to the encountered channel. It results in an error rate performance gain since interleaving depth is adapted to the Doppler shift. However, this technique is not suited for broadcasting applications. In fact, due to the nature of the broadcast service, all receiver situations can be experienced, each with different channel characteristics and Doppler shift values. Therefore, interleaving

CHANNEL INTERLEAVING TECHNIQUES

29

depth should be scaled for the worst-case scenario. In addition, a return channel is required to communicate the maximum Doppler shift back to the transmitter.

Adaptive interleaver based on Channel State Information

In [START_REF] Lei | Performance analysis of adaptive interleaving for OFDM systems[END_REF], the authors adapt the interleaving function with respect to the instantaneous CSI of the OFDM carriers in a multipath Rayleigh fading channel. The design method involves separating the most attenuated channel states as far as possible in the transmitted sequence. First, a suitable deinterleaving pattern is identified according to the estimated CSI. Then, the corresponding interleaving pattern can be obtained.

The deinterleaving pattern is determined as follows. Let N f be the number of carriers in the OFDM symbol. The channel state sequence h of the N f carriers is estimated at the receiver. Then, h is ordered from the least to the most attenuated channel states. Thereafter, the N f received constellation symbols are ordered according to the new indices order in h. Finally, the received sequence is reordered in such a way that the most attenuated symbols are separated as far as possible. This procedure determines the suitable deinterleaving pattern. The same pattern can be obtained at the transmitter with the knowledge of the CSI. Then, the interleaving pattern is identified as the inverse of the deinterleaving pattern.

It was shown that improvement in system performance can be obtained by using this interleaver. Compared to other interleaving structures, time diversity seems to be limited, since the proposed interleaver in [START_REF] Lei | Performance analysis of adaptive interleaving for OFDM systems[END_REF] operates at the OFDM symbol level. Actually, this solution represents a family of adaptive frequency interleavers operating on the carriers of one OFDM symbol. In addition, a return channel is once again required to send the CSI back to the transmitter.

The channel interleaver of DVB-T2

According to [START_REF] Etsi | Digital Video Broadcasting (DVB): frame structure channel coding and modulation for a second generation digital terrestrial television broadcasting system (DVB-T2)[END_REF], [START_REF] Mendicute | DVB-T2: new signal processing algorithms for a challenging digital video broadcasting standard[END_REF], a basic DVB-T2 transmission chain not including the input adaptation stage can be established as shown in Fig. 1.13. The data to be transmitted are first encoded by a Bose-Chaudhuri-Hocquenghem (BCH) code followed by a LDPC code [START_REF] Gallager | Low density parity check codes[END_REF], [START_REF] Mackay | Good error-correcting codes based on very sparse matrices[END_REF]. The BCH code was prefixed to the latter to avoid undetected errors at low BERs. Thus, the concatenation of these two codes constitute the FEC encoder. It offers improved performance compared to the convolutional codes used in DVB-T [START_REF] Etsi | Digital Video Broadcasting (DVB): frame structure channel coding and modulation for digital terrestrial television[END_REF]. LDPC codewords at the output of the encoder are interleaved by the Bit Interleaver (BI) and sent to the mapper block. Then, the codewords are mapped to constellation symbols or cells using Gray mapping. An optional rotated constellation is offered for the 4, 16, 64 and 256-QAM [START_REF] Nour | Rotated QAM constellations to improve BICM performance for DVB-T2[END_REF]. This technique allows a more robust transmission over frequency selective fading channels, since each bit is transmitted in more than one carrier.

The number of cells, N cells , in a codeword or FEC block is defined by the modulation order and the codeword length. Each FEC block has to be interleaved by the Cell Interleaver (CI) before being sent to the OFDM frame builder through the Time Interleaver (TI). The OFDM frame is made up of NFEC FEC blocks. According to the number of carriers, NF , and the first carrier position, F c , the OFDM frame builder assembles the cells coming from the TI into arrays of OFDM symbols. Then, the cells of each OFDM symbol are interleaved by the Frequency Interleaver (FI). In the OFDM modulator block, the values of each cell on the OFDM symbols are taken as coefficients in the frequency domain. Pilots are inserted into the OFDM frame to allow channel estimation in the receiver. Then, the Inverse Fast Fourier Transform (IFFT) is applied to the cells of each OFDM symbol. Finally, a guard interval is inserted between OFDM symbols to avoid inter-symbol interference.

The channel interleaver of DVB-T2 is then composed of CI, TI and FI. Its objective is to ensure an uncorrelated error distribution inside the FEC blocks over time and/or frequency selective propagation channels. A description of the BI and the channel interleaver components is given below.

Bit Interleaver

The BI aims to avoid mapping multiple correlated coded bits on the same constellation symbol [START_REF] Yokokawa | Parity and column twist bit interleaver for DVB-T2 LDPC codes[END_REF]. Correlated coded bits are defined as coded bits connected to the same check node in the LDPC parity-check matrix. In most cases, the BI in the DVB-T2 transmission chain is composed of a parity and a column twist interleaver. As presented in [START_REF] Yokokawa | Parity and column twist bit interleaver for DVB-T2 LDPC codes[END_REF], the parity interleaver permutes the columns of the parity part in the LDPC parity-check matrix. Then, a column-row permutation is implemented, which involves writing the bits column-wise and reading it out from the memory block row-wise. If we consider, as in [START_REF] Yokokawa | Parity and column twist bit interleaver for DVB-T2 LDPC codes[END_REF], a memory block of 4 columns for a 16-QAM constellation and a codeword length of 64,800, the rows of the memory block contains correlated coded bits as shown in Fig. 1.14(a). Since the bits are read out row-wise, a column twist is introduced in the memory block (see Fig.

Cell Interleaver

The CI is a pseudo-random permutation on cells of the FEC block. This interleaver aims to ensure an uncorrelated distribution of interference or channel distortions along the codewords in the receiver. According to [START_REF] Etsi | Digital Video Broadcasting (DVB): frame structure channel coding and modulation for a second generation digital terrestrial television broadcasting system (DVB-T2)[END_REF], its permutation function can be defined as: Π r (q) = (Π 0 (q) + c(r)) mod N cells (1.23) where q = 0...N cells -1 is the address of the cells in the FEC block before interleaving and Π r (q) is its corresponding address after interleaving, where r = 0...NFEC -1 is the FEC block index. In order to achieve a different interleaving pattern for each FEC block, a shift c(r) is included in the permutation. Π 0 (q) represents the basic pseudo-random permutation function, the addresses of which are obtained by a linear feedback shift register [START_REF] Etsi | Digital Video Broadcasting (DVB): frame structure channel coding and modulation for a second generation digital terrestrial television broadcasting system (DVB-T2)[END_REF].

Time Interleaver

The TI is a column-row block interleaver intended to scatter cells from several FEC blocks into one OFDM frame. The cells are written in the memory column-wise and read out row-wise. The number of rows and columns in the interleaver memory, N r and N c , respectively are defined as:

N r = N cells 5 ; N c = 5 • NFEC (1.24)
where the number of FEC blocks, NFEC, in the OFDM frame depends on the TI duration that should be at least 70 ms to ensure some immunity to interference or impulsive noise [START_REF]Digital Video Broadcasting (DVB): implementation guidelines for a second generation digital terrestrial television broadcasting system (DVB-T2)[END_REF]. This interleaver represents the largest memory requirement of the system because all the cells of the FEC blocks contained in the OFDM frame should be stored in the interleaver memory bank.

Frequency Interleaver

The FI is a pseudo-random interleaver operating on the cells of each OFDM symbol. This interleaver aims to mitigate the adverse interaction of the TI structure and regular error patterns (i.e., across frequency) by breaking up the structured nature of the TI. According to [START_REF] Etsi | Digital Video Broadcasting (DVB): frame structure channel coding and modulation for a second generation digital terrestrial television broadcasting system (DVB-T2)[END_REF], the FI reads the cells from an input vector x i = (x i,0 , ..., x i,(NF -1) ), and writes them to an output vector a i = (a i,0 , ..., a i,(NF -1) ), where i is the OFDM symbol index. The relation between the vectors addresses, in the FFT size of 32k, can be expressed as: where H(p), H 0 (p) and H 1 (p) are pseudo-random permutation functions. The addresses of these functions are obtained by a linear feedback shift register [START_REF] Etsi | Digital Video Broadcasting (DVB): frame structure channel coding and modulation for a second generation digital terrestrial television broadcasting system (DVB-T2)[END_REF].

a i,H(p) = x i

Comparison of channel interleavers

Two types of channel interleavers were presented, adaptive and non-adaptive. Improvements in system performance can be obtained with adaptive interleavers, since they modify their structure according to the encountered channel. However, they have a number of disadvantages. First, a return channel is needed to get information about channel conditions. Second, they are not suited for broadcasting applications because different channel conditions can be experienced in the broadcast service and they should be then configured for the worst-case scenario. In the second type of interleavers, the channel interleaver of DVB-T2 was described. This interleaver was included in DVB-T2 to provide robustness in transmissions to fixed, portable and mobile terminals. Thus, it is more suitable for broadcasting applications than adaptive interleavers. This channel interleaver is taken as a reference for the work carried out on channel interleaving in Chapter 4.

Conclusion

This chapter presents the background of the thesis. First, a brief description of TCs and PTCs is given. As presented, TCs have been adopted in several communication standards. This is mainly due to their capacity-approaching performance and their suitability for practical implementation. PTCs have shown to improve convergence performance of TCs without altering their code rate. This part motivates the work carried out on channel coding. Then, to cope with the low error rate requirements of future systems, especially for broadcasting applications, a deeper study regarding these codes is performed in Chapters 2 and 3.

In the second part, interleaving techniques for TCs were analyzed. For implementation purposes, these interleavers should present a reduced complexity as well as efficient parallelization capabilities. The maximization of the span, correlation girth and degree of disorder in the permuted symbols constitute their principal performance requirements. However, the maximization of these parameters does not always lead to the best performance. Consequently, new design criteria are proposed in Chapter 2. Furthermore, it was identified that DRP, QPP and ARP interleavers have similar properties.

In the last part, channel interleaving techniques were discussed. In order to allow the overall system to benefit from the available diversity of the channel, this interleaver has to maximize the scattering of transmitted symbols in both time and frequency. On the other hand, reduced latency and memory area as low as possible are sought for in practical systems. Finally, it was identified that a channel interleaver as the one included in the DVB-T2 standard is more suitable for broadcasting applications than adaptive channel interleavers. Then, this standard was selected as a benchmark in the research on channel interleavers presented in Chapter 4.

Chapter 2

Design of efficient puncture-constrained interleavers for turbo codes T he future generation of wireless communication systems [78] calls for increased data rates and capacity, with a reliable quality of service (QoS) for different receiver scenarios [START_REF]Evolution, convergence and innovation[END_REF] and applications. To meet such requirements, Forward Error Correction (FEC) codes able to guarantee very low error rates, down to 10 -10 , need to be provided. This chapter deals with the design of enhanced Turbo Codes (TC).

As introduced in Chapter 1, the TC interleaver is a key component of TCs. It affects their minimum Hamming distance and therefore their asymptotic performance. The interleaver design criteria presented in Chapter 1 do not always ensure high minimum distances for TCs. Then, to meet the low error rates required in future generation of wireless communication systems, an investigation of new design criteria has to be performed. In this chapter, the joint design of puncturing patterns and interleavers for TCs is investigated in order to guarantee low error floors and good convergence thresholds. As a result, a graph-based method to design TC interleavers is proposed. It includes a new design criterion based on parity puncturing.

The chapter is organized as follows: Section 2.1 gives an overview of the proposed puncture-constrained interleaver design method. In Section 2.2, the puncturing pattern selection proposal is given. Then, in Section 2.3 the state-of-the-art data puncture-constrained interleavers for TCs and proposed parity puncturing constraints are introduced. In Section 2.4, a suitable representation of the correlation graph of TCs is given. Section 2.5 presents the choice of the TC interleaver structure and the proposed interleaver design method. Afterwards, in Section 2.6 application examples are given and compared to the LTE standard. Finally, Section 2.7 concludes the chapter.

CHAPTER 2. EFFICIENT PUNCTURE-CONSTRAINED INTERLEAVER

Overview of the proposed puncture-constrained interleaver design method

In conventional turbo code designs, only parity bits are punctured to obtain high code rates [START_REF] Acikel | Punctured turbo-codes for BPSK/QPSK channels[END_REF], [START_REF] Mo | Analysis of puncturing pattern for high rate turbo codes[END_REF]. Nevertheless, it was later shown that puncturing well-chosen data bits can increase the minimum Hamming distance and improve the convergence threshold of TCs [START_REF] Crozier | On the error-rate performance of 4-state turbo codes with puncture-constrained DRP interleavers[END_REF], [START_REF] Gracie | Convergence performance and EXIT analysis of 4state partially-systematic turbo codes[END_REF]. However, puncturing of data bits must be performed carefully, since the constituent codes of the TC can be affected by a semi-catastrophic or catastrophic puncturing mask or pattern [START_REF] Crozier | On designing turbo-codes with data puncturing[END_REF], [START_REF] Cheng | Analysis of circular buffer rate matching for LTE turbo code[END_REF]. In fact, due to such poor puncturing patterns, the constituent code distance spectrum can contain a minimum distance of one or even zero.

In order to jointly optimize the TC interleaver with puncturing patterns, the proposed method involves three main stages. First, the best puncturing mask for the constituent code of the TC, in terms of constituent code distance spectrum and TC extrinsic information exchange with uniform permutations, is identified. It allows the puncturing mask to be selected independently of the interleaver structure. Second, a group of candidate interleavers validating the different design criteria (e.g., span properties, correlation girth, and proposed puncturing constraints) is generated. Finally, the candidate interleavers with the best TC Hamming distance spectrum are selected. In the following sections, the proposed puncturing pattern selection, puncturing constraints, and interleaver design method are described.

Puncturing mask selection proposal

Periodic puncturing is widely used in practice because it can be easily implemented. In this study, a periodic puncturing pattern with period N is considered. Unless otherwise indicated, CRSC codes with coding rate 1/2 are used as constituent codes of the TC. Then, for each constituent CRSC code, the puncturing mask or pattern is composed of two vectors of length N , corresponding to the puncturing positions in the data and parity sequences. To avoid edge effects when applying the puncturing mask, N is selected as a divisor of the data sequence length K. The puncturing mask configuration is defined according to the target code rate R of the TC and to the puncturing period N . The target code rate R is computed as:

R = N N (1 -DPR) + 2PK (2.1)
where DPR represents the data puncturing rate and PK is the number of unpunctured parity positions per constituent CRSC code in a puncturing period. Considering the same puncturing pattern for both constituent CRSC codes, PK is the same for both CRSC codes. For a given R and N , DPR can take N + 1 different values:

DPR = n N , n = 0, ..., N (2.2)

PUNCTURING MASK SELECTION PROPOSAL

37

However, in practice the values of DPR are restricted to those allowing a CRSC constituent code rate R c smaller than 1, to be able to reconstruct the data sequence from the encoded sequence. From 2.1, the number of unpunctured parity positions per CRSC constituent code is given by:

PK = N 2 1 R + DPR -1 (2.3)
PK is an integer value, since only symmetric puncturing masks (i.e., same puncturing pattern for both constituent CRSC codes) are considered. Different methods found in the literature can be used to design a suitable puncturing mask for convolutional codes. For instance, the "Fast Algorithm for Searching Trees" (FAST) was introduced in [START_REF] Cedervall | A fast algorithm for computing distance spectrum of convolutional codes[END_REF] to evaluate the distance spectrum for unpunctured conventional (non-recursive) convolutional codes. This algorithm can be easily adapted to punctured CRSC codes. It is noteworthy that convolutional codes distance spectrum is independent of K, provided that the codeword size is higher than the largest codeword at the maximum distance considered in the spectrum. The puncturing mask design procedure proposed in this work involves three steps. First, suitable puncturing masks for the CRSC code, in terms of CRSC distance spectrum, are found. Then, a TC extrinsic information exchange analysis is performed to select a restricted subset of masks. A final selection is made by simulating the TC error rate performance with uniform interleaving. These steps are described below:

1. Find the best puncturing pattern for each DPR value: The Hamming distance spectrum of the corresponding punctured CRSC codes is evaluated using the modified FAST algorithm. The best puncturing mask for each DPR value is identified as the one generating the best CRSC Hamming distance spectrum (i.e., highest distance values in the first spectrum terms and minimal number of codewords at these distances).

2. Carry out a mutual information exchange analysis to select a restricted set of puncturing masks: The best puncturing mask for each DPR is introduced and evaluated into the TC structure. Given that, this stage of design is focused on the identification of the optimal puncturing mask independently of the interleaver structure. The TC performance is evaluated for the selected puncturing masks using uniform permutations to average the impact of the interleaver on the error rate performance [START_REF] Benedetto | Unveiling turbo codes: some results on parallel concatenated coding schemes[END_REF] (cf. 1.2.4.1).

As pointed out in [START_REF] Gracie | Convergence performance and EXIT analysis of 4state partially-systematic turbo codes[END_REF], the measured extrinsic information distribution of punctured data bits is different from the one measured on unpunctured data bits. Therefore, conventional EXIT charts are not appropriate to predict the convergence threshold of TCs with punctured data bits because all a priori information samples are generated from the same Gaussian process. Then, an analysis of the real exchange of extrinsic information between the constituent SISO decoders, within actual turbo decoding iterations, is proposed to select the best puncturing mask in terms of TC convergence. The average mutual information between the extrinsic LLRs of each constituent SISO decoder and the data frame is evaluated as presented in Section 1.1.1.4 and illustrated by Fig. 1.5. However, it is computed for each TC decoding iteration and the a priori information L a is taken from the respective constituent SISO decoder, not from a virtual AWGN channel.

Unlike conventional EXIT charts, the crossing point of the curves in the proposed modified EXIT charts is not the point of perfect convergence (IA, IE) = (1, 1). Therefore, the best puncturing mask in terms of convergence performance is selected as the one providing a crossing point closer to (1, 1) than the parity-only punctured version of the code (DPR = 0).

3.

Final selection of the puncturing mask by simulating the TC error rate performance: Afterwards, using the selected puncturing masks, the error rate performance of the TC is analyzed. The puncturing mask providing the best tradeoff between convergence threshold and error floor performance is finally selected.

Puncturing constraints

Designing a non-catastrophic puncturing mask with punctured data bits [START_REF] Crozier | On designing turbo-codes with data puncturing[END_REF] is an easy task for the first (non-interleaved) constituent CRSC code of the TC. For instance, it can be performed by a modified FAST algorithm. However, when designing TC interleavers, these techniques do not guarantee a good correspondence of the puncturing pattern with respect to the second (interleaved) constituent CRSC code.

To deal with this issue, data puncturing constraints must be taken into consideration when designing the interleaver.

As far as we know, no puncturing constraint related to parity puncturing has been included in the design of TC interleavers so far. The analysis carried out in this work allows to identify a useful parity puncturing constraint for the design of TC interleavers. The state-of-the-art data puncturing constraints and the proposed parity puncturing constraint are described in the following sections.

State-of-the-art data puncture-constrained interleavers for TCs

Let us consider a TC interleaver structure as described in Section 1.2. A Data Puncture-Constrained (DPC) interleaver ensures that for a given puncturing pattern the data punctured positions in the data sequence d are interleaved to data punctured positions in the interleaved data sequence d . Two types of DPC interleavers have been proposed in the literature: fully-constrained and partially-constrained interleavers.

In fully-constrained interleavers [START_REF] Gracie | Convergence performance and EXIT analysis of 4state partially-systematic turbo codes[END_REF], [START_REF] Chatzigeorgiou | Punctured binary turbo-codes with optimized performance[END_REF], symbols at position n, n = 0, ..., N -1, within a puncturing pattern with period N in d are interleaved to the same position n within a puncturing pattern in d . This ensures the same puncturing mask in both constituent CRSC codes, avoiding poor puncturing patterns. In partiallyconstrained interleavers, data punctured positions in d are interleaved to data punctured positions in d . This interleaver structure allows two different puncturing masks to be used for the constituent codes, provided that the number of data punctured positions in both masks remains the same. Then, partially-constrained interleavers have a more flexible structure than fully-constrained interleavers. Indeed, a larger number of partially-constrained interleavers can be found validating other design criteria (e.g., span and correlation girth) than fully-constrained. Therefore, TC interleavers proposed in this study are partially-constrained.

Proposed parity puncturing constraint

During the turbo decoding process, extrinsic information from a given constituent decoder is generated based on its received parity sequence and is sent to the other constituent decoder via the interleaver/deinterleaver as a priori information on data. The extrinsic information computed from unpunctured parity positions is expected to be more reliable than the one generated from punctured parity positions. Therefore, an analysis of the connection strategy applied by the interleaver for unpunctured parity positions of a constituent code, and the effect of the information exchange on the remaining code, are of relevance for performance improvement. The proposed connection strategy defines a new puncturing constraint related to parity puncturing. Thus, an interleaver including both data and proposed parity puncturing constraint is named Data and Parity Puncture-Constrained (DPPC) interleaver.

Extrinsic information analysis

In order to illustrate the reliability difference between extrinsic information evaluated from punctured and unpunctured parity positions, a conventional EXIT chart, as introduced in Section 1.1.1.4, was calculated for a parity-only punctured version of a TC with a uniform interleaver. As shown in Fig. 2.1, the EXIT curve obtained from data at unpunctured parity positions has a more opened tunnel than the one obtained from data at punctured parity positions. These results validate the a priori assumption that extrinsic information computed from unpunctured parity positions is more reliable than the one generated from punctured parity positions.

Connection strategy for the unpunctured parity positions

Since extrinsic information corresponds to a priori information on data, a possible strategy for the interleaver construction involves connecting the most reliable ex- trinsic information positions from one constituent decoder to the most error-prone data positions in the other one. Under these conditions, the turbo decoding decision on the most error-prone data positions should be improved. For a given puncturing mask with period N and data puncturing rate DPR, the proposed connection strategy is defined by the following steps:

1. Identify the number of free parities within a puncturing period N : Free parities are defined as unpunctured parities corresponding to unpunctured data symbols.

2. Identify error-prone data positions within a puncturing period N : To this end, additional data puncturing is introduced at the remaining unpunctured data positions, and the resulting CRSC distance spectrum is evaluated.

The number of additional punctured data positions corresponds to the number of free parities. The additional punctured data positions leading to the poorest CRSC distance spectrum are then labeled as the most error-prone. It is noteworthy that additional data puncturing is only introduced to identify error-prone data positions. These additional punctured data positions are removed from the puncturing mask after the corresponding identification.

Apply the connection strategy:

The proposed strategy involves connecting free parities of a CRSC code to the most error-prone data positions of the other one. Thus, in the decoder, the most reliable extrinsic information positions

NEW REPRESENTATION OF THE CORRELATION GRAPH FOR TCS41

from one constituent decoder are sent to the most error-prone data positions in the other one.

The connection strategy can be illustrated through the following example: Let us consider the puncturing mask shown in Fig. 2.2. The unpunctured parity at position j is the only free parity within the puncturing period N because the remaining two parities are at the same position as punctured data symbols. Thus, only one additional punctured data position can be considered in the puncturing mask for the connection strategy analysis. Let p be the most error-prone data position. Therefore, the interleaver has to ensure that extrinsic information from one constituent decoder at position j is sent as a priori information to the other constituent decoder at position p within the puncturing period N .

New representation of the correlation graph for TCs

During the interleaver design process, we faced an issue with the correlation girth of the interleavers: the obtained girths were very far from the values predicted by the Moore bound [START_REF] Biggs | Minimal regular graphs with given girth[END_REF]. Therefore, we questioned the correlation graph representation we used for TCs, taken from [START_REF] Saouter | Selection procedure for binary turbocode permutation parameters[END_REF], [START_REF] Saouter | Selection procedure of turbocode parameters by combinatorial optimization[END_REF] and described in Section 1.2.3.2. We noted that the connections made via the interleaver, between the vertices of d and d , are not counted in the evaluation of the correlation cycle (see Fig. A theoretical upper bound on the girth value g of a regular graph of degree r (i.e., each vertex has exactly r neighbors) is derived, based on the Moore bound [START_REF] Biggs | Minimal regular graphs with given girth[END_REF]. Let x(r, g) be the lowest number of vertices in a r-regular graph with girth g:

               x(r, g) = 1 + r (g-3)/2 i=0 (r -1) i : For odd values of g (2.4)
x(r, g) = 2

(g-2)/2 i=0 (r -1) i : For even values of g (

The Moore bound implies that g can be at most proportional to the logarithm of x(r, g): g ≤ 2 log r-1 (x(r, g))

+ O(1) (2.6)
where O(1) is the error term of the approximation.

In [START_REF] Saouter | Selection procedure for binary turbocode permutation parameters[END_REF], the correlation graph for TCs was said to be strictly cubic (r = 3) with a number of vertices x = 2K, when using CRSC codes as constituent codes of the TC. In the proposed representation, it can be observed that the correlation graph for TCs is a quartic regular graph (r = 4) with a number of vertices x = K (see Fig. 2.3). Therefore, the previously derived theoretical upper bound on the correlation girth of TCs was not accurate. A comparison between the theoretical upper bounds on the correlation girth of TCs obtained from (2.6), for the graph representation in [START_REF] Saouter | Selection procedure for binary turbocode permutation parameters[END_REF] and for the proposed correlation graph, is given in Table 2

Proposed interleaver design method

Different types of TC interleavers were presented in Section 1.2.4. As already mentioned, algebraic interleavers are more suitable for TC implementation purposes than random-based interleavers. Furthermore, an appropriate selection of the parameters of algebraic interleavers allows TC performance improvements in the error floor region. Therefore, the proposed interleaver design method will focus on algebraic interleavers. First, a suitable algebraic interleaver structure is chosen. Then, a new method to select the interleaver parameters is proposed.

Choice of a suitable TC interleaver structure

In order to select the interleaver structure, three of the most popular interleaver families for TCs are analyzed: Dithered Relative Prime (DRP) [START_REF] Crozier | High-performance low-memory interleaver banks for turbo-codes[END_REF], Quadratic Permutation Polynomial (QPP) [START_REF] Sun | Interleavers for turbo codes using permutation polynomials over integer rings[END_REF], and Almost Regular Permutation (ARP) [START_REF] Berrou | Designing good permutations for turbo codes: towards a single model[END_REF]. Until now, no generic permutation model for TCs has been established. However, as discussed in Section 1.2.4.7, DRP, QPP and ARP interleavers have similar interleaving properties. In the following sections, we show that some connections exist among these three families of interleavers and that any DRP or QPP interleaver can be expressed as an ARP interleaver. The results of Sections 2.5.1.1 and 2.5.1.2 are published in the February 2015 issue of IEEE Wireless Communication Letters [START_REF] Garzón Bohórquez | On the equivalence of interleavers for turbo codes[END_REF].

DRP interleavers expressed as ARP interleavers

As introduced in Section 1.2.4.4 the DRP interleaver function is defined as:

Π DRP (i) = Π a (Π b (Π c (i))) (2.7)
where

Π a (i) = F i/F + r(i mod F ) (2.8) Π b (i) = (s + P •i) mod K (2.9) Π c (i) = G i/G + w(i mod G) (2.10)
and x denotes the closest lower integer value with respect to x. Noting that for natural integers n and k, n k/n is equal to k-k mod n, expressions (2.8) and (2.10) can be rewritten as:

Π a (i) = (i -i mod F + r(i mod F )) mod K (2.11) Π c (i) = (i -i mod G + w(i mod G)) mod K (2.12)
Then, the term Π b (Π c (i)) in (2.7) can be expressed as:

Π b (Π c (i)) = (s + P (i -i mod G + w(i mod G))) mod K = (P •i+s+P (w(i mod G)-i mod G)) mod K (2.13)

CHAPTER 2. EFFICIENT PUNCTURE-CONSTRAINED INTERLEAVER

Therefore, a vector with G periodic shifts, S G , can be defined as:

S G (i mod G) = (s + P (w(i mod G) -i mod G)) mod K (2.14)
and (2.13) can be expressed as:

Π b (Π c (i)) = (P •i+ S G (i mod G)) mod K (2.15)
Substituting (2.15) and (2.11) into (2.7) gives the overall expression of the DRP interleaver:

Π DRP (i) = (P •i + S G (i mod G) -(P •i + S G (i mod G)) mod F + r((P •i + S G (i mod G)) mod F )) mod K (2.16)
Let M be the least common multiple of F and G. Then, a vector with M periodic shifts, S M , can be defined as:

S M (i mod M ) = (S G (i mod G) -(P •i + S G (i mod G)) mod F + r((P •i + S G (i mod G)) mod F )) mod K (2.17)
Finally, (2.16) can be expressed in the form:

Π DRP (i) = (P •i + S M (i mod M ))mod K (2.18)
Given that K is a multiple of both M and Q, we can take Q = M and the expression in (2.18) corresponds to the ARP interleaver function in (1.21). Therefore, it is shown that any DRP interleaver can be expressed in the ARP interleaver function form. The obtained equivalent expression of DRP in the form of ARP is given for some examples in Appendix A.

QPP interleavers as special cases of ARP interleavers

As introduced in Section 1.2.4.5, the QPP interleaver function is defined as:

Π QPP (i) = (f 1 i + f 2 i 2 )mod K (2.19)
Provided that (2.19) defines a valid permutation, then K and f 2 can be factorized in their prime factors as:

K = 2 α K,1 ω(K) i=2 p α K,i i (2.20) f 2 = 2 α f,1 ω(K) i=2 p α f,i i ω(f ) i=ω(K)+1 p α f,i i (2.21)
where ω(K) and ω(f ) represent the number of different prime factors of K and f 2 , respectively. α f,1 = 0 for α K,1 = 1 and α f,1 > 1 for α K,1 > 1.

It can be shown that the QPP interleaver is a particular case of the ARP interleaver. Let us first recall the addition property of congruence [START_REF] Apostol | Introduction to Analytic Number theory[END_REF]: if a ≡ b mod n and c ≡ d mod n then ax + cy ≡ bx + dy mod n for all integers x and y.

Therefore, a sufficient condition for the existence of an ARP-equivalent form of a valid QPP interleaver is that the following equations hold:

(P •i)mod K = (f 1 i)mod K (2.22) S(i mod Q)mod K = (f 2 i 2 )mod K (2.23)
(2.22) holds for:

P = f 1 (2.24)
(2.23) holds for the trivial case Q = K. However, it is not a suitable value for implementation purposes, since K shift values have to be stored. It can be shown that a valid value for Q, smaller than the trivial case Q = K, can be found. Given that S is a vector of Q periodic shifts, equation (2.23) is satisfied for:

(f 2 i 2 )mod K = (f 2 (i + Q) 2 )mod K (2.25) (f 2 i 2 )mod K = (f 2 i 2 + 2f 2 Qi + f 2 Q 2 )mod K
Then, it must be verified that:

(2f 2 Qi + f 2 Q 2 )mod K = 0 (2.26)
which holds for:

(2f 2 Qi)mod K = 0 (2.27) (f 2 Q 2 )mod K = 0 (2.28) (2.27) implies that: 2f 2 Q = uK, u ∈ N + (2.29)
which is satisfied for:

Q = (uK)/(2f 2 ) (2.30)
Let us factorize u in its prime factors as:

u = 2 α u,1 ω(K) i=2 p α u,i i ω(f ) i=ω(K)+1 p α u,i i (2.31)
Then, (2.30) with Q as a divisor of K holds for:

           α u,1 ∈ {0, 1} , for α K,1 = 1 (2.32) α f,1 -α K,1 +1 ≤ α u,1 ≤ α f,1 +1, for α K,1 > 1 (2.33) α f,i -α K,i ≤ α u,i ≤ α f,i , i = 2, ..., ω(K) (2.34) α u,i = α f,i , i = ω(K)+1, ..., ω(f ) (2.35)

CHAPTER 2. EFFICIENT PUNCTURE-CONSTRAINED INTERLEAVER

(2.28) implies that:

f 2 Q 2 = mK, m ∈ N + (2.36)
With Q as defined in (2.30), (2.36) evaluates to:

(u/2) 2 (K/f 2 )K = mK (2.37)
According to (2.37), (u/2) 2 (K/f 2 ) ∈ N + , which holds for:

             α u,1 = 1, for α K,1 = 1 (2.38) α f,1 -α K,1 2 +1 ≤ α u,1 , for α K,1 > 1 (2.39) α f,i -α K,i 2 ≤ α u,i , i = 2, ..., ω(K) (2.40)
Finally, we have to find a range for the exponents of the prime factors of u, α u,i , validating the conditions that verify equations (2.30) and (2.37), for which an equivalent ARP function for a valid QPP interleaver is obtained. This range is the following:

For i = 1 and α K,1 = 1: α u,1 = 1 validates both conditions (2.38) and (2.32).

For i = 1 and α K,1 > 1, two cases have to be considered:

   α K,1 < α f,1
: the valid range for α u,1 is given by (2.33)

α K,1 ≥ α f,1 : α f,1 -α K,1 2 +1 ≤ α u,1 ≤ α f,1 +1 (2.41)
For i = 2, ..., ω(K) two cases have to be considered as well:

   α K,i < α f,i : the valid range for α u,i is given by (2.34)

α K,i ≥ α f,i : α f,i -α K,i 2 ≤ α u,i ≤ α f,i (2.42)
For i = ω(K)+1, ..., ω(f ): the exponent values, α u,i , are obtained from (2.35). It is noteworthy that negative lower bounds for α f,i , in (2.41) or (2.42) must be replaced with zero since α f,i ∈ N 0 .

To sum up, an equivalent ARP function for a valid QPP interleaver is obtained by choosing P equal to f 1 with a vector of shifts S of length Q. The possible values for Q are determined by (2.30), for u defined in (2.31). Let Q s be the smallest possible value for Q. It corresponds to the minimum disorder degree for which an equivalent ARP can be found. Other possible values for Q are then multiples of Q s provided that K remains a multiple of Q. Then, the Q periodic shifts of S are obtained from (2.23) for i = 0, ..., Q-1. Note that the shift values of S for multiples of Q s are just periodic repetitions of those obtained for Q s . Therefore, only the shift values for Q s have to be found. Thus, the QPP interleaver is a particular case of the ARP interleaver in which the values of the periodic shifts follow relation (2.23). Some examples of the application of the equivalent expression are given in Appendix A.

Conclusion on the choice of the TC interleaver structure

It was shown that DRP and QPP interleavers can be expressed as ARP interleavers. In addition, QPP interleavers were found to be special cases of ARP interleavers in which the values of the periodic shifts follow the quadratic term of the QPP interleaver function. Thus, the same interleaving properties of DRP or QPP interleavers can be provided by ARP interleavers. Therefore, the ARP interleaver is a sufficient permutation model to design TCs with the achievable asymptotic performance from any of the three interleaver families. Thus, the ARP interleaver structure is chosen for the study carried out in this work.

Graph-based method to select the ARP interleaver parameters

As introduced in Section 1.2.4.6, different methods to select ARP interleaver parameters have been investigated in the past [START_REF] Berrou | Designing good permutations for turbo codes: towards a single model[END_REF], [START_REF] Saouter | Selection procedure of turbocode parameters by combinatorial optimization[END_REF]. Error floors at 10 -5 of FER were reported in [START_REF] Douillard | Turbo codes with rate-m/(m+1) constituent convolutional codes[END_REF] for 8-state double-binary TCs, data frame size of 1504, and code rates of 2/3 and 3/4. Such asymptotic performance is not adapted to the low error rates required in future generation of wireless communication systems. Therefore, a new method to design efficient ARP interleavers, allowing TC error floor performance improvements, should be investigated.

The alternative method proposed in this work is based on a graphical approach. It allows easy integration of puncturing constraints, whilst validating span and correlation girth criteria in the interleaver design. Furthermore, the proposed design method decreases the interleaver parameters selection complexity via a suitable reduction of the search space.

In order to simplify the interleaver parameters selection as well as the validation of the different design criteria, the interleaver structure is divided into different groups of addresses or layers. Then, these layers are progressively placed to complete the interleaver structure. Each time a new layer is placed, the different design criteria are verified. Let us consider the ARP interleaver function defined in (1.21). It can be shown that Π

(i + Q)mod Q = Π(i)mod Q. Proof. First, Π(i + Q) is evaluated as: Π(i + Q) = (P (i + Q) + S((i + Q) mod Q))mod K = (P •i + S(i mod Q) + QP )mod K = (Π(i) + QP )mod K (2.43)
Then noting that K is a multiple of Q, Π(i + Q)mod Q evaluates to:

Π(i + Q)mod Q = ((Π(i) + QP )mod K)mod Q = (Π(i) + QP )mod Q = Π(i)mod Q (2.44)
Therefore, Q groups of permutation addresses are identified in the whole interleaver size K, each one corresponding to a given modulo Q value. Thus, a graphbased method to select the interleaver parameters can be established by dividing the permutation addresses into Q groups or layers with index l = 0, ..., Q -1.

In Fig. 2.4 the interleaver structure is divided into its Q corresponding layers and represented in a circle with the addresses of d and d in its inner and outer parts, respectively. Note that the initial permutation addresses (i.e., non-shifted) are fixed by the RI period P of the ARP function. Afterwards, the final permutation addresses of each layer l are defined by choosing its corresponding shift value S(l). The layer number l to which address i in d belongs is determined as:

1 2Q-1 2Q 3Q Q 3Q K-1 0 1 Q-1 Q 2Q l=0 l=1 l=Q-1 . . . i . . . . . . . . . . . . Q+1 2Q-1 2Q+1 3Q-1 0 Π(i) 3Q-1 K-1 Q-1
l = i mod Q (2.45)
The shift value for each layer l is given by:

S(l) = T l + B l Q (2.46)
where T l = 0, ..., Q -1 and B l = 0, ..., (K/Q) -1 correspond to the inter and intralayer shifts for each layer l, respectively. The inter-layer shift T l defines the position that a given layer takes among the Q different layers as shown in Fig. 2.5, whilst the intra-layer shift B l defines the rotation that a given layer performs without taking the position of another layer as shown in Fig. 2.6. Thus, the value of S(l) can be obtained first by selecting the value of inter-layer shift T l and then selecting the value of intra-layer shift B l . It is noteworthy that the proposed shift selection allows all possible positions for each layer to be considered. In order to simplify the inclusion of puncturing constraints into the interleaver design, Q is set equal to the puncturing period N . Given that the layer order is Q-periodic as shown by (2.44), the validation of puncturing constraints within a puncturing period N is a sufficient condition for their validation in the whole data sequence.

2Q 3Q Q 3Q K-1 0 1 Q-1 Q 2Q . . . . . . . . . . . . Q+1 2Q-1 2Q+1 3Q-1 0 T 0 =0 . . . T 0 =1 T 0 =Q-1 0 0 3Q 3Q Q Q 2Q 2Q 3Q+1
The data puncturing constraint is introduced by selecting the values of T l in such a way that punctured data positions in d are written to punctured data positions in d . Then, to include the parity puncturing constraint, the values of T l are selected to ensure that free parity positions from one CRSC code are interleaved to the most 50 CHAPTER 2. EFFICIENT PUNCTURE-CONSTRAINED INTERLEAVER error-prone data positions of the other one as presented in Section 2.3.2.2.

Considering the above introduced shift selection method, for a given set of design parameters (K, R, S min and g goals, polynomial generators, and puncturing mask), the proposed puncture-constrained interleaver design strategy is defined according to the following steps.

Selection of the best ARP interleaver candidate:

As a last phase of design, the best candidate for TC interleaver is selected from the group of candidates previously generated by comparing their Hamming distance spectrum.

The TC Hamming distance spectrum can be estimated by different methods as mentioned in Section 1.1.1.5. The ARP interleaver candidate generating the best TC Hamming distance spectrum is selected.

The initial selection of a suitable couple of S min and g goals for obtaining good ARP interleaver candidates is not a trivial task. However, an empirical selection strategy involves the following steps: first, evaluate the convergence of Algorithm 1 for a couple of S min and g goals set to their corresponding theoretical upper bounds (cf. Sections 1.2.3.1 and 2.4). Then, if the algorithm does not converge, progressively reduce the S min and g goals until the algorithm converges to a group of ARP candidate interleavers.

Application examples

The previous design guidelines have been applied to design puncture-constrained TC interleavers for the 8-state TCs with CRSC(13, 15) 8 and CRSC(13, 15, 17) 8 constituent codes, respectively. In the first step of design, a suitable puncturing mask is selected following the guidelines presented in Section 2.2. Then, the parity puncturing constraint is identified as proposed in Section 2.3.2.2. Finally, a punctureconstrained ARP interleaver is designed via the method presented in Section 2.5.2.

8-state CRSC(13, 15) 8 TC

The proposed puncturing mask selection and puncture-constrained interleaver design were applied to two code rates, R = 2/3 and R = 4/5, as well as to two data sequence sizes, K = 1504 and K = 6144, available in the LTE standard. Error rate performance was simulated over the AWGN channel with a BPSK modulation and a maximum of sixteen decoding iterations. Only the design for code rate 2/3 and data sequence size 1504 is detailed in this chapter, the description for the other cases is reported in Appendix B.

Puncturing mask selection

Different puncturing periods N can be used according to the data sequence length K = 1504. In order to avoid long exploration time, N is taken from the smallest divisors of K. Then, only puncturing periods of 8 and 16 are considered. A puncturing period N = 8 allows symmetric puncturing masks with data puncturing rates DPR equal to 0/8, 2/8, and 4/8, obtained from (2.2). Table 2.2 lists the distance spectrum of the CRSC constituent code, obtained with the modified FAST algorithm, for the best puncturing mask for each DPR value and R = 2/3. The spectrum for DPR = 6/8 is included to illustrate how a DPR value making the CRSC constituent code rate R c higher than 1 leads to a catastrophic puncturing that generates a nonzero A 0 (see Section 2.2). Thus, catastrophic DPR values can be avoided early in the selection process. In a second phase, the TC convergence behavior with the different puncturing masks is analyzed in the TC structure. Uniform interleavers are used to average the influence of the interleaver on the error rate performance [START_REF] Benedetto | Unveiling turbo codes: some results on parallel concatenated coding schemes[END_REF]. For DPR = 0, the data puncturing constraint is included into the interleaver to avoid poor puncturing patterns in the second constituent code, leading to a DPC uniform interleaver. Fig. 2.7 shows the modified EXIT chart of the TC evaluated at the SNR decoding threshold of the parity-only punctured version of the code (DPR = 0). According to the modified EXIT chart results, the puncturing masks with better convergence than the DPR = 0 mask, due to their (IA, IE) crossing point closer to ( In order to identify the puncturing mask that allows the best tradeoff between TC convergence threshold and error floor, the TC error rate performance curves are simulated (see Fig. 2.8). The puncturing mask with DPR 2/16 performs best in terms of TC convergence threshold as predicted in the modified EXIT chart analysis.

DPR R c A

CHAPTER 2. EFFICIENT PUNCTURE-CONSTRAINED INTERLEAVER

However, this improvement in convergence is achieved at the expense of a loss in TC error floor performance compared to the one obtained with the puncturing mask with DPR 2/8. Therefore, we chose the puncturing mask with DPR = 2/8 as the best tradeoff between TC convergence threshold and error floor performance.

One can observe that using a DPC uniform interleaver yields improved performance compared to a uniform interleaver for DPR = 2/8 and DPR = 2/16 (see Fig. 2.8). DPC interleavers allow a better control of the irregular influence of masks with data puncturing in the decoding process, which leads to better convergence. Once the best puncturing mask in terms of TC convergence threshold and error floor is selected, the parity puncturing constraint is identified.

Parity puncturing constraint

According to the method proposed in Section 2.3.2.2, in the selected mask with DPR = 2/8, only the parity at position 1 is a free parity for N = 8 (see Table 2.2). Therefore, only one additional punctured data position can be considered in the CRSC distance spectrum analysis. Table 2.4 lists the different distance spectra obtained including an additional punctured data symbol from positions 6 to 1 in the puncturing mask. According to these results, an additional punctured data symbol at position 4 generates the worst CRSC distance spectrum. Then, 4 is the most error-prone data position in a puncturing period. Therefore, the DPPC interleaver must ensure that data symbols at positions 1 and 4 in d are interleaved to positions 4 and 1 in d , respectively. ARP S min g P S( 1) S( 2) S( 3) S( 4) S( 5) S( 6) S( 7 In this example, we investigate whether the asymptotic performance of the unpunctured mother code of LTE, CRSC [START_REF] Cedervall | A fast algorithm for computing distance spectrum of convolutional codes[END_REF][START_REF] Crozier | On designing turbo-codes with data puncturing[END_REF] 8 TC of R = 1/3, could also be improved via data puncturing. To allow the inclusion of puncturing, the selected mother code is the CRSC [START_REF] Cedervall | A fast algorithm for computing distance spectrum of convolutional codes[END_REF][START_REF] Crozier | On designing turbo-codes with data puncturing[END_REF][START_REF] Berrou | Designing good permutations for turbo codes: towards a single model[END_REF] 8 TC of R = 1/5 and both data and parity puncturing are used to obtain the code rate 1/3.

A 0 A 1 A 2 A 3 A 4 Data

Puncturing mask selection

In order to avoid long exploration time, only a puncturing period N = 8 was studied for K = 1504. For comparative purposes, the unpunctured CRSC [START_REF] Cedervall | A fast algorithm for computing distance spectrum of convolutional codes[END_REF][START_REF] Crozier | On designing turbo-codes with data puncturing[END_REF] 8 TC of LTE is used for DPR = 0. The two parity outputs of the mother code CRSC [START_REF] Cedervall | A fast algorithm for computing distance spectrum of convolutional codes[END_REF][START_REF] Crozier | On designing turbo-codes with data puncturing[END_REF][START_REF] Berrou | Designing good permutations for turbo codes: towards a single model[END_REF] 8 TC provide a higher degree of freedom for data puncturing than the single parity output of the CRSC(13, 15) 8 TC. Thus, all DPR values generating symmetric puncturing masks can be considered, without leading to catastrophic puncturing masks. Table 2.8 lists the distance spectrum of the CRSC constituent code, obtained with the modified FAST algorithm, for the best puncturing mask for each DPR value and R = 1/3. In a second selection step, the TC convergence behavior with the different puncturing masks is analyzed in the TC structure. Fig. 2.10 shows the modified EXIT chart of the TC, evaluated at the SNR decoding threshold of the CRSC [START_REF] Cedervall | A fast algorithm for computing distance spectrum of convolutional codes[END_REF][START_REF] Crozier | On designing turbo-codes with data puncturing[END_REF] 8 TC (DPR = 0). According to the modified EXIT chart results, a slight improvement in convergence is provided by the mask with DPR = 2/8 and no improvements are achieved with other masks, compared to the mask with DPR = 0. Thus, in this particular case with more than one parity bit per constituent code, rejecting all the puncturing masks with crossing points less close to [START_REF] Berrou | Near Shannon limit errorcorrecting coding and decoding: Turbo-codes[END_REF][START_REF] Berrou | Near Shannon limit errorcorrecting coding and decoding: Turbo-codes[END_REF] than the DPR = 0 case is no longer useful, since only the case DPR = 2/8 would be selected. Therefore, the puncturing masks for all considered DPR values are simulated. Fig. 2.11 shows the TC error rate performance for the considered puncturing masks. As can be observed, there is almost no improvement in convergence threshold compared to the mask with DPR = 0. Therefore, priority was given to the TC error

Parity puncturing constraint

The parity puncturing constraint for the selected puncturing mask with DPR = 6/8 is then identified. Only the parities at positions 0 and 2 are free parities. Furthermore, only the data symbols in these positions are unpunctured. Thus, the parity constraint reduces to interleave data symbols at positions 0 and 2 in d to positions 2 and 0 in d , respectively. A special consideration was taken in this example for non-free parity positions, since there are more non-free than free parity positions in the mask. In fact, two groups of non-free parity positions are identified in the mask with DPR = 6/8 (see Table 2

Puncture-constrained ARP interleaver design

Through the strategy introduced in Section 2.5.2, a S min goal of 80% of the S min theoretical upper bound and a g goal of 8 were selected. Then, the interleaver candidates are generated according to the design method proposed in Section 2.5.2:

1. Selection of the candidate values for P: Since the S min and g goals are the same as those selected in the previous example, the group of candidates for P is also the same as the considered in the previous example from Fig. 2.9.

2. Selection of the Q shift values for each candidate for P: The parameters for the ARP interleaver candidates are determined by Algorithm 1. Three interleaver configurations are considered: NDP for DPR = 0, DPC and DPPC for DPR = 6/8.

3.

Selection of the best ARP interleaver candidate: Table 2.9 lists the best ARP interleavers generated for each design configuration as well as the corresponding S min and g values achieved. Their respective distance spectrum is estimated and given in Table 2.10. Similar conclusions as in the previous example are drawn. Furthermore, a higher d min value is achieved with the proposed DPPC interleaver compared to the DPC interleaver.

ARP S min g P S(0) S( 1) S( 2) S( 3) S( 4) S( 5) S( 6) S( 7

Simulated TC error rate performance

The performance of TCs using different interleaver configurations was simulated over the AWGN channel with a BPSK modulation and a maximum of sixteen decoding iterations, using the MAP algorithm described in Section 1.1.1.2. The estimated distance spectra listed in Tables 2.6 and B.8 for K = 1504 and in Tables B.2 and B.11 for K = 6144 are used to compute the FER and BER union bounds truncated to the third distance spectrum element for performance comparison, as introduced in Section 1.1.1.5. Furthermore, error rate simulation results for the LTE [START_REF] Etsi | LTE Envolved Universal Terrestrial Radio Access(E-UTRA): Multiplexing and channel coding[END_REF] TC are included for comparison in a similar simulation scenario.

Figs. 2.12 and 2.13 show the FER and BER performance of the 8-state CRSC [START_REF] Cedervall | A fast algorithm for computing distance spectrum of convolutional codes[END_REF][START_REF] Crozier | On designing turbo-codes with data puncturing[END_REF] 8 TC for R = 2/3 and R = 4/5, and of the CRSC [START_REF] Cedervall | A fast algorithm for computing distance spectrum of convolutional codes[END_REF][START_REF] Crozier | On designing turbo-codes with data puncturing[END_REF][START_REF] Berrou | Designing good permutations for turbo codes: towards a single model[END_REF] 8 TC for R = 1/3 and K = 1504. The interleaver parameters for the different puncturing constraints are listed in Tables 2.5, B.7, and 2.9. We observe that DPC and DPPC interleavers achieve a good asymptotic performance gain compared to the NDP interleaver, even with a convergence improvement for R = 2/3 and R = 4/5. The gain in the TC error floor region obtained by the DPC interleaver compared to the NDP interleaver is lower for the low code rates than for the higher ones. The proposed DPPC interleaver achieves a higher asymptotic performance gain than the DPC interleaver for all considered code rates. In addition, the proposed DPPC ARP interleaver provides a gain of about 0.5 and 0.7 dB in convergence threshold for R = 2/3 and R = 4/5, respectively and almost 4 decades in error floor in both cases, compared to the puncturing pattern and the interleaver adopted in LTE (see Fig. 2.12). In the R = 1/3 case, a gain of "only" 2 decades in error floor is achieved by the proposed DPPC ARP interleaver, compared to the interleaver adopted in LTE (see Fig. 2.12). In fact, for R = 1/3 no puncturing is included in the LTE system and therefore, no bad interactions between interleaver and puncturing pattern may occur, which is not the case for higher code rates. Figs. 2.14 and 2.15 show the FER and BER performance of the 8-state CRSC(13, 15) 8 TC for K = 6144 and for the interleaver parameters listed in Tables B.1 and B.10 for the different puncturing constraints. A similar behavior as for K = 1504 is found, only the proposed DPPC interleaver achieves the same gain in error floor performance for both code rates compared to the NDP interleaver. Furthermore, the DPPC interleaver provides a gain of about 0.2 and 0.25 dB in convergence threshold for R = 2/3 and R = 4/5, respectively and of about 3 decades in error floor in both cases, compared to the puncturing pattern and the interleaver adopted in LTE (see Fig. 2

.14).

As we can observe in all presented application examples, the best TC error floor performance is provided by the proposed DPPC ARP interleaver as predicted by the evaluated Hamming distance spectra. Furthermore, improvements in TC error floor performance are obtained by introducing data puncturing into the TC structure, which was already identified in the respective puncturing mask selection process. Thus, the TC minimum distance appears to be more related to parity positions than to data positions. It is noteworthy that a considerable asymptotic gain is obtained by the proposed DPPC interleaver compared to the puncturing pattern and interleaver adopted in LTE. Actually, the rate matching process and the QPP interleaver of LTE are not suited to the low error rates required in future generation of wireless communication systems.

CHAPTER 2. EFFICIENT PUNCTURE-CONSTRAINED INTERLEAVER

Conclusion

In this chapter, a new method to design puncture-constrained ARP interleavers for TCs is proposed. It calls for a joint optimization of puncturing patterns and interleaver function. Catastrophic puncturing masks for the constituent codes of the TC are early identified in the selection process by evaluating their respective distance spectrum. A modified EXIT chart analysis is also proposed to identify a suitable puncturing mask for TC convergence performance improvement, with data puncturing.

It was shown that significant improvements in convergence threshold and error floor can be achieved by including puncturing constraints into the interleaver design. In addition to a noticeable increase in the percentage of ARP candidates found generating high minimum Hamming distance values, the proposed parity puncturing constraint reduces the average time to find such interleavers. Finally, the presented method allows an easy introduction of puncturing constraints as well as the validation of other design criteria such as span properties and correlation girth into the interleaver design. The generation of ARP interleavers validating the different design criteria is greatly simplified in comparison to previous methods, since the proposed graphical approach suitably limits the search space for the different interleaver parameters.

CHAPTER 3. PRECODING TECHNIQUES FOR TURBO CODES

Selection of a suitable precoding structure

In this section, different precoding structures are studied for the 8-state CRSC [START_REF] Cedervall | A fast algorithm for computing distance spectrum of convolutional codes[END_REF][START_REF] Crozier | On designing turbo-codes with data puncturing[END_REF] 8 TC, for code rate R = 4/5 and data sequence size K = 1504. The used puncturing pattern corresponds to the parity-only punctured version of the code (DPR = 0) from Table B.5. The different precoding structures and parameters are compared assuming uniform interleaving to average its effect on the error rate performance of the code. First, an optimization of the precoding ratio ρ of the reference precoding structure, shown in Fig. 1.7, is performed. Then, some modified precoding structures are proposed and analyzed. Finally, a conclusion on the choice of the precoding structure is given.

Analysis of the reference precoding structure

For simplicity, only periodic and regular precoding patterns are considered in this analysis. For a precoding ratio ρ, 0 ≤ ρ ≤ 1, the precoding pattern contains 100•ρ % ones and 100(1-ρ) % zeros. Precoding patterns are similar to puncturing masks, except that a 1 represents a precoded data symbol and a 0, a non-precoded data symbol. The precoder and the TC can be seen as the outer and the inner codes of a serially concatenated code, as shown in Fig. 3.1. Therefore, the convergence behavior of the PTC can be analyzed by evaluating the EXIT curves of the corresponding outer and inner codes. Ashikhmin et al. showed in [START_REF] Ashikhmin | Extrinsic information transfer functions: model and erasure channel properties[END_REF] that the design of capacityapproaching serially concatenated codes (among others) reduces to a curve-fitting problem. Thus, in [START_REF] Tong | Precoded turbo code within 0.1 dB of Shannon limit[END_REF], a suitable value for ρ was proposed to be identified as the one allowing the EXIT curve of the outer code to match that of the inner code as much as possible. Fig. 3.2 shows the EXIT chart for different values of ρ over the AWGN channel, evaluated at a SNR value for which the outer curve matches the one of the inner code. Because the precoding ratio only affects the outer code (i.e., precoder) extrinsic information processing, the EXIT curve of the inner code (i.e., TC) is the same for all values of ρ. According to the EXIT chart results, 0.16 is identified as the value of ρ which makes the inner and outer curves fit best. For values of ρ higher than 0.16, the outer curve crosses the inner curve, which prevents the iterative decoding process from converging. Therefore, the PTC convergence SNR is expected to increase as the value of ρ increases to larger values than 0.16.

In order to analyze the actual impact of ρ on the PTC error rate performance, we plotted the error rate curves with uniform interleavers. Fig. 3.3 shows the corresponding curves with values of ρ ranging from 0.06 to 0.3. Sixteen decoding iterations of the decoding algorithm presented in Section 1.1.2.2 were used. As predicted in the EXIT chart analysis, an increase in the convergence threshold of the PTC is observed for values of ρ higher than 0.16. However, in spite of what was expected, the best PTC convergence performance is achieved for ρ = 0.11 not for ρ = 0.16. Even for ρ = 0.06 a better convergence performance than for ρ = 0.16 is obtained, especially in the BER curves.

These observations show that the curve-fitting approach using conventional EXIT charts is not reliable for the considered precoding structure. Then, a three-dimensional (3D) EXIT chart for the PTC is proposed and studied. Because the CRSC constituent codes of the TC are symmetric, only the EXIT curve of the first constituent decoder of the TC, SISO 1, needs to be evaluated. Fig. 3.4 shows the 3D EXIT chart measurement scheme. At each PTC decoding iteration, the postdecoder updates the a priori information L a(0,1) on d 2 (the sequence at input of CRSC 1). The EXIT chart for SISO 1, as introduced in Section 1.1.1.4, is then measured for each PTC decoding iteration. Thus, the PTC decoding trajectory can be plotted from the TC EXIT charts generated for the different PTC decoding iterations. Figs. 3.5 and 3.6 show the 3D EXIT chart evaluated at 2.43 dB, which is a value close to the decoding SNR threshold of the classical TC (see Fig. 3.7). It can be observed that the decoding trajectory for ρ = 0.11 reaches the point (1, 1) whilst for ρ = 0.16 it is blocked. It means that a better PTC convergence performance is obtained for ρ = 0.11, which is in accordance with the obtained error rate performance of Fig. 3.3. However, at 2.38 dB, the decoding trajectory for ρ = 0.06 reaches the point (1, 1), whereas it is not the case for ρ = 0.11, which is not in line with the simulated error rate performance shown in Fig. 3.3.

Consequently, the introduced EXIT chart tools (i.e., EXIT charts for serially concatenated codes and 3D EXIT charts) are not appropriate for the accurate determination of the best precoding ratio in terms of PTC convergence.

Proposed design tool based on extrinsic information exchange

In this section, we propose a modified EXIT chart scheme that is appropriate for the selection of the precoding ratio value. Let us first identify the shortcomings of classical EXIT charts. One important parameter for EXIT charts is the distribution of the extrinsic mutual information (MI) at the input. Traditionally in the case of TCs where one SISO decoder receives a priori information from only one other SISO decoder, a Gaussian assumption is made. In our precoded case, a priori information on some of the bits (precoded ones) is available from the SISO decoder of the accumulator (SISO 0) and from the SISO decoder of CRSC 2 (SISO 2). Therefore, the distribution of the extrinsic mutual information at the input of one component SISO decoder is now different from the TC case. It can be even questioned if it follows a Gaussian distribution at all. In order to verify the validity of our reasoning, we have compared the distribution of the extrinsic information provided at the input of the SISO 1 decoder with the one generated via a Gaussian process, both having the same measured MI value.

Figs. 3.8 (a) and (b) show a comparison of the histograms of extrinsic information measured at the input of the SISO 1 decoder and the one generated from the same Gaussian process, for ρ = 0.06 and for ρ = 0.11, respectively. As observed, the corresponding histograms are different, even for a low value of ρ (0.06), i.e., closer to a conventional TC since only 6 % of the bits are precoded. It proves that the extrinsic information samples at the input of SISO 1 cannot be generated from the same Gaussian process as in classical EXIT chart tools. As a solution, we propose to measure the real exchange of extrinsic information between the constituent SISO decoders of the TC. In this modified PTC EXIT chart, the best PTC parameters in terms of convergence performance are identified as those allowing a crossing point (IA, IE) as close as possible to [START_REF] Berrou | Near Shannon limit errorcorrecting coding and decoding: Turbo-codes[END_REF][START_REF] Berrou | Near Shannon limit errorcorrecting coding and decoding: Turbo-codes[END_REF].

SELECTION OF A SUITABLE PRECODING STRUCTURE

The application of this modified EXIT chart to the most promising precoding ratios of Fig. 3.2 is presented in Fig. 3.9. Corresponding results validate the application of the proposed tool since the convergence threshold hierarchy is in line with simulated error rate curves of Fig. 3.3.

Hybrid precoding structure

In the reference precoding structure, ρK data symbols are encoded by the accumulator. Therefore, the extrinsic information exchange between the SISO decoder of the accumulator and the constituent SISO decoders of the TC is performed only on ρK turbo encoded symbols (see Section 1.1.2.2). As an alternative to this PTC scheme, we propose a hybrid precoding structure, which precodes the whole data sequence and introduces a new parameter φ, 0 ≤ φ ≤ 1, to define the serial-to-parallel precoding ratio (see Fig. 3.10(a)). Thus, φK parities and (1-φ)K data symbols of the accumulator are encoded by the TC. In the precoding mask, a precoder parity and a data position sent to the TC are identified by 1 and 0, respectively. The advantage of this precoding structure over the previous one is that it allows the SISO decoder of the accumulator to exchange extrinsic information on the whole turbo encoded sequence for all values of φ, as represented in Fig. 3.10(b). Note that for φ = 0, the coding structure corresponds to the classical TC, since all the parities of the accumulator are punctured. By increasing the value of φ, the serial concatenation between the accumulator and the TC concerns a higher number of data bits. Therefore, asymptotic performance improvements are expected at the expense of a loss in convergence performance compared to the one of the classical TC. The tradeoff between convergence and asymptotic performance of the hybrid PTC is then controlled by the serial-to-parallel precoding ratio. The modified PTC EXIT chart for different values of φ, evaluated over the AWGN channel, is shown in Fig. 3.11 and the corresponding error rate performance curves, obtained with uniform interleavers are presented in Fig. 3.12. In Fig. 3.11, we can observe that the exchange of extrinsic information becomes less efficient when φ increases and when the SNR is kept constant. This is confirmed by Fig. 3.12. If low SNR region losses greater than 0.3 dB are not acceptable, values of φ higher than or equal to 0.1 should not be used.

CHAPTER 3. PRECODING TECHNIQUES FOR TURBO CODES

According to the hybrid PTC error rate performance presented in Fig. 3.12, a good compromise between convergence and asymptotic performance is obtained for φ equal to 0.04. For higher values of φ (e.g. φ = 0.1), the improvement in error floor performance is not considered large enough to justify the resulting loss in convergence threshold. Note that the error floor gain obtained with the hybrid PTC with φ = 0.04 is of almost one decade and a half, compared to the classic TC.

Composite precoding structure

Trying to benefit from the convergence behavior and the error floor performance of the first and second previously introduced precoding structures, we combined the two of them in a new one and analyzed the resulting performance. The composite precoding structure has then two parameters ρ and φ (see Fig. 3.13), which represent the total and serial-to-parallel precoding ratios as in the original structures. In order to reduce the research complexity of an optimal couple of parameters ρ and φ, two strategies based on the extreme cases are adopted.

In the first strategy, ρ is set to 0.11 and φ to 1. The resulting structure corresponds to the optimal configuration obtained for the original PTC (ρ = 0.11) introduced in Section 3.1.1. Then, φ is decreased and the corresponding modified PTC EXIT charts are plotted (see Fig. 3.14). When the value of φ decreases, the convergence performance of the composite PTC approaches the one of the classical TC. The composite PTC error rate performance, for the couples of ρ and φ considered in this strategy, is shown in Fig. 3.15. The convergence behavior of the code corresponds to the one predicted in the EXIT chart analysis. In addition, no improvement in error floor performance is obtained.

In the second strategy, ρ is set to 1 and φ to 0.04, which corresponds to its optimal value for the hybrid precoding structure proposed in Section 3.1.2. Then, ρ is decreased and the corresponding modified PTC EXIT charts are plotted (see Fig. 3.16). They show that the convergence threshold is expected to decrease when the value of ρ diminishes. The corresponding error rate performance is shown in Fig. 3.17. It is in accordance with the EXIT chart analysis. Convergence improvements are achieved by decreasing the value of ρ at the expense of a loss in error floor performance, compared to the one obtained with the optimal configuration of the hybrid precoding structure (φ = 0.04). Note that any convergence improvement will not enable the considered structure to surpass the case where ρ = 0.11 shown in Fig. 3

Conclusion on the choice of a suitable precoding structure

Three different precoding structures were analyzed. It was shown that convergence improvements are achieved with the reference precoding structure in [START_REF] Tong | Precoded turbo code within 0.1 dB of Shannon limit[END_REF] (see Section 3.1.1) compared to a classical TC. Furthermore, a significant asymptotic gain is attained with the proposed hybrid precoding structure, introduced in Section 3.1.2. The combination of the first two precoding schemes was studied in Section 3.1.3. It was observed that the composite precoding structure shows a performance level that can be considered as a compromise between the original structure with improved convergence threshold and the hybrid precoding structure with improved error floor. It could not solve the convergence versus error floor tradeoff issue. However, it remains of interest for communication systems requiring the adaptation of channel coding to the encountered noise level.

Finally, taking the improvement in the error floor as target, the hybrid precoding structure with φ = 0.04 is selected for the analysis in the following section.

Improving the hybrid precoding structure

In Section 3.1.2, the accumulator parities corresponding to the surviving (unpunctured) positions at the output of the accumulator were assumed to follow a regular pattern (uniform distribution) when sent to the turbo encoder. In this section we study the effect of introducing other patterns when using the hybrid precoding structure of Fig. 3.10. Then, we study the impact of changing the precoder constraint length on the overall performance.

Studying the precoding pattern

As observed in Section 3.1.2, a higher number of accumulator parities sent to the TC improves the asymptotic performance of the hybrid PTC, at the expense of a loss in iterative process convergence. Unpunctured accumulator parities are turbo encoded. Therefore, when decoding the accumulator, extrinsic information is provided by the turbo decoder on these bits. This exchange improves the error correcting capability of the accumulator in trellis stages where parities are unpunctured. Thus, a regular distribution of these parities along the accumulator frame improves the asymptotic performance of the complete coding structure. In fact at high SNR values, the extrinsic information provided by the turbo decoder is quasi-error free. Therefore, it can greatly help in distinguishing between two candidate Return To Zero (RTZ) sequences of the accumulator trellis where these bits differ. This leads to an improved error correction of a large number of different possible erroneous sequences.

On the other hand, for a given value of φ, the extrinsic information at the output of the accumulator is expected to be improved by grouping its trellis stages in which the parity is turbo encoded. Indeed, consecutive trellis stages with unpunctured CHAPTER 3. PRECODING TECHNIQUES FOR TURBO CODES parities benefit from the exchange of extrinsic information with the TC decoder on a large number of successive accumulator parities. Therefore, patterns with long groups of successive unpunctured accumulator parities tend to improve the exchanged MI and lead to better iterative process convergence. However, this comes at the expense of a penalty in the error floor region. Indeed, bit grouping lowers the number of different possible candidate RTZ sequences of the accumulator that can be corrected when the TC decoder provides quasi-error free extrinsic information. In other words, due to bit grouping, larger stages of the accumulator trellis are now continuously punctured with an equivalent error correcting capability of the inner TC alone (see Fig. 3.18(b)). Thus, a good compromise between convergence and asymptotic performance must be found.

Accumulator trellis stage with parity

Accumulator trellis stage with punctured parity (a) (b) A new parameter, CP , is introduced, corresponding to the number of consecutive parities sent to the TC. The groups of such parities are regularly selected according to the precoding mask. Fig. 3.19 shows the modified PTC EXIT chart evaluated over the AWGN channel, for different values of CP and φ = 0.04. We can observe that convergence is improved with CP > 1, compared to the convergence of the original precoding pattern with CP = 1.

0 12 K-1 ... 0 12 K-1 ...
The hybrid PTC error rate performance for the considered values of CP is shown in Fig. 3.20. These curves show that, if very low error rates are sought for, CP = 1 is the best choice, but a non-negligible loss in convergence is observed. Conversely, if obtaining a low convergence threshold is crucial with a low error floor, CP = 2 or CP = 3 could provide a good compromise. For higher values of CP , the asymptotic performance of the hybrid PTC is degraded, for a negligible gain in convergence. This precoding pattern allows then to approach the convergence performance of the classical TC, at the expense of a slight reduction in error floor performance, compared to the original with CP = 1.

IMPROVING THE HYBRID PRECODING STRUCTURE

Analysis of different constituent codes for the precoder

Two main criteria have been considered for the selection of a constituent code intended to replace the accumulator. First, the resulting hybrid PTC should be able to achieve both convergence and asymptotic performance improvements compared to the hybrid PTC scheme using an accumulator. Second, the increase in complexity, especially at the receiver, should not be high. Therefore, the memory length v of the linear feedback shift register of the constituent code of the precoder is limited to 2. The considered candidate constituent codes for the precoder are shown in Fig. 3.21. Tail-biting termination (cf Section 1.1.1.1) was applied to the RSC(7, 4) 8 and RSC(7, 5) 8 codes. On the other hand, the RSC(5, 4) 8 code, as well as the accumulator, cannot be made circular. Then, an exchange of metrics at the end of the forward and backward process is included in the decoding process to deal with this issue. Fig. 3.22 shows the modified EXIT chart evaluated over the AWGN channel, for the different constituent codes of the precoder, CP = 2 and φ = 0.04. According to these results, a loss in convergence performance is introduced when using the considered codes, compared to the accumulator. Moreover, the best error floor performance is expected to be provided by the RSC(7, 5) 8 code, since the RSC(5, 4) 8 , RSC(7, 4) 8 , and RSC(7, 5) 8 codes have a d min of 3, 4, and 5, respectively. Therefore, RSC(7, 5) 8 is the most robust code with respect to the intrinsic puncturing due to the selection of data or parity bits at the output of the precoder in the hybrid precoding structure. The corresponding error rate performance, using the different constituent codes for the precoder, is given in Fig. 3.23 and confirms this analysis.

In order to explore possible convergence improvements for v = 2 codes for the precoder, other values of CP are studied. Fig. 3.24 shows the error rate performance for the best values of CP obtained for RSC [START_REF] Hokfelt | Interleaver design for turbo codes based on the performance of iterative decoding[END_REF][START_REF] Berrou | Near optimum error correcting coding and decoding: turbo-codes[END_REF] 8 and RSC [START_REF] Mackay | Near Shannon limit performance of low density parity check codes[END_REF][START_REF] Hokfelt | Interleaver design for turbo codes based on the performance of iterative decoding[END_REF] 8 in terms of convergence performance. These codes correspond to the best constituent codes in terms of hybrid PTC convergence and error floor performance, respectively from Fig. 3.23. As can be observed, the hybrid PTC error rate performance achieved by the accumulator can be approached by using the RSC(5, 4) 8 and RSC(7, 5) 8 codes for CP = 4 and CP = 5, respectively. In addition, when the convergence thresh-old using the considered codes improves the one provided by the accumulator, the error floor is worsened when compared to the one obtained by the accumulator as constituent code of the precoder. As a conclusion of this analysis, the accumulator is the best constituent code for the precoder, since no better error rate performance can be achieved by considering constituent codes with an increased memory length.

Relevant design criteria for PTC interleavers

In the previous analyses of PTCs, we have only considered uniform interleavers, representative of the average asymptotic performance over all the possible interleavers. In this section, we focus on the design of interleavers for PTC structures.

The hybrid PTC can be seen as a three-dimensional TC, in which the first dimension corresponds to the precoder and the other two dimensions correspond to the constituent codes of the TC. Therefore, the precoder and TC interleavers Π 1 and Π 2 have to be designed considering the three-dimensional nature of the hybrid PTC. Thus, the span criteria presented in Section 1.2.3.1 and the correlation graph representation proposed in Section 2.4 for a classical TC, have to be revisited for the three-dimensional case.

Span properties in the three-dimensional case

As introduced in [START_REF] Gnaedig | Design of three-dimensional multiple slice turbo codes[END_REF], good span properties in Π 1 and Π 2 do not guarantee good span properties in the three dimensions of the code. Let d 1 , d 2 , and d 3 denote the sequences at the input of Π 1 , the interleaved sequence at the output of Π 1 , and the interleaved sequence at the output of Π 2 , respectively. Fig. 3.25(a) shows an example of a couple of interleavers Π 1 and Π 2 providing good span properties, for which the permutation composed of both interleavers, Π 1,2 , has bad span properties. Thus, the span properties of Π 1,2 must also be verified. On the other hand, the validation of good span properties in Π 1,2 is not a sufficient condition to validate it on the considered three dimensions. This is shown by the example in Fig. 3.25(b). Therefore, the minimum span values S min1 , S min2 , and S min1,2 of the three permutations Π 1 , Π 2 , and Π 1,2 , respectively have to be maximized to guarantee good span properties in the three dimensions of the code.

d 2 d 1 d 3 0 K-1 1 2 Π 1 Π 2 ... Π 1,2 (a)

Proposed correlation graph for the three-dimensional case

The sequence at the input of Π 1 , the interleaved sequence at the output of Π 1 , and the interleaved sequence at the output of Π 2 are represented in Fig. 3.26(a). The correlation girths of Π 1 and Π 2 are g 1 and g 2 , respectively and g 1,2 represents the correlation girth of the permutation composed of both interleavers, Π 1,2 . Under this representation, the correlation graph of each interleaver corresponds to a regular graph of degree 4, as proposed in Section 2.4 for the classical TC. However, a unified correlation graph, considering the three-dimensional nature of the code, corresponds to a regular graph of degree 6, as shown in Fig. 3.26(b). Therefore, the lower correlation girth among g 1 , g 2 , and g 1,2 can only be considered as an upper bound on the effective correlation girth g eff of the unified correlation graph in Fig 3.26(b). Indeed, the unified correlation graph of degree 6 has a lower theoretical upper bound on its correlation girth than the independent correlation graphs of Π 1 , Π 2 , and Π 1,2 of degree 4. Thus, in order to reduce the correlation among the exchanged extrinsic information by the precoder and the constituent codes of the TC, g eff has to be maximized.

An example of hybrid PTC with optimized interleavers

Given that the design of an efficient couple of interleavers Π 1 and Π 2 is more complex than the search for a single interleaver in the case of a conventional TC, we had to adopt some simplifications in the selection process of Π 1 and Π 2 . In order to reduce search complexity, the best ARP interleaver for the NDP configuration, R = 4/5, and K = 1504 from Table B.7 is selected as Π 2 . Note that this interleaver was already optimized for the TC. On the other hand, Π 1 is chosen from the group of candidate ARP interleavers generated for the parity-only punctured version of the TC and the same design parameters (see Appendix B). Therefore, S min1 and S min2 as well as g 1 and g 2 are already validated by construction in the TC case.

Because the aim of this section is to provide an example of error rate performance of the proposed hybrid PTC, we propose to simplify the verification of the effective correlation cycle g eff to only the verification of g 1,2 . In the span criterion case, only S min1,2 needs to be evaluated for the different candidates for Π 1 and the selected interleaver for Π 2 . Afterwards, a reduced group of candidates for Π 1 allowing the highest values of S min1,2 and g 1,2 is identified. Finally, the best candidate for Π 1 is selected as the one providing the best Hamming distance spectrum for the hybrid PTC.

Figs. 3.27 and 3.28 show the FER and BER performance of the hybrid PTC using the selected couple of interleavers for Π 1 and Π 2 , whose d min is equal to 11. We observe that the error floor performance of the TC with NDP interleaver configura- tion from Table B.7 is improved by almost one decade and a half with the proposed hybrid PTC. In addition, the proposed hybrid PTC achieves a gain of about 0.38 dB in convergence threshold and almost 4 decades in error floor, compared to the puncturing pattern and the interleaver adopted in LTE (see Fig. 3.27). However, the convergence and asymptotic performance of the TC, including data puncturing and the proposed DPPC interleaver from Table B.7, remain better. In fact, improvements in error rate performance of the hybrid PTC might be possible by designing an efficient couple of interleavers Π 1 and Π 2 , through a specific algorithm verifying the design criteria presented in Section 3.3. The development of such an algorithm is part of the research perspectives on the topic of PTCs.

AN EXAMPLE OF HYBRID PTC WITH OPTIMIZED INTERLEAVERS85

Conclusion

This chapter presents the results of our studies on PTCs. A new precoding structure was introduced. It was shown that asymptotic performance improvements are achieved by the proposed hybrid PTC, compared to a classical TC without data puncturing.

We also showed that extrinsic information samples at the output of the precoder cannot be drawn from the same Gaussian process and therefore, a classical EXIT chart analysis is not suitable to predict the PTC convergence behavior. We proposed an analysis of the real exchange of extrinsic information between the constituent SISO decoders of the TC, within actual PTC decoding iterations, to select the best precoder parameters in terms of PTC convergence.

The effect of the precoding pattern and of the precoder constituent code in error rate performance was then studied. According to the precoding pattern analysis, a mask defining consecutive accumulator trellis stages with turbo encoded parities can improve the convergence performance of the hybrid PTC, at the expense of a loss in asymptotic performance. Thus, a good compromise between convergence and asymptotic performance must be found. We also showed that increasing the memory length of the constituent code of the precoder does not bring much performance gain. Moreover, we adapted the interleaver design criteria derived in Chapter 2 to the case of PTCs.

Usually, for high code rates, the priority is given to the error floor performance, thus the design methods introduced in Chapter 2 still represent the best choice in terms of performance and complexity when compared to the hybrid PTC with Π 1 and Π 2 chosen via the simplified selection strategy presented at the end of this chapter. However, initial results omitted for lack of space, have shown an interest of precoding techniques for low coding rates. They can motivate the extension of this work to this particular context in future works.

Chapter 4

Channel interleavers for terrestrial broadcast: analysis and design A s studied in Chapters 2 and 3, the optimization of puncturing patterns, inter- leaving functions, and coding structures are key factors to improve the error rate performance of FEC codes. However, their performance can be greatly degraded in transmissions where the transmitted signal undergoes impulsive noise and/or selective fading (e.g., broadcasting applications). Channel interleaving is then introduced to allow the overall system to take advantage of the available time and frequency diversities from the encountered channel. Thus, the transmitted symbols subject to impulsive noise and/or selective fading do not end up in the same coded frame and the FEC code is able to reconstruct the data sequence from the encoded one. Therefore, this last chapter presents a research on designing improved channel interleavers.

As presented in Chapter 1, DVB-T2 standard includes a channel interleaver specifically designed for broadcasting applications. Thus, we chose it as a benchmark in the present study. However, some of its weaknesses have been identified. In fact, DVB-T2 advocates the use of three interleavers [START_REF] Etsi | Digital Video Broadcasting (DVB): frame structure channel coding and modulation for a second generation digital terrestrial television broadcasting system (DVB-T2)[END_REF]: a Cell Interleaver (CI), a Time Interleaver (TI), and a Frequency Interleaver (FI). The implementation of each of them introduces additional latency compared to a system with a single channel interleaver. On the other hand, since the implementation of each type of interleaver requires a dedicated memory, the whole interleaving memory can represent a large portion of the silicon area and of the power consumption at the receiver. In addition, from a diversity point of view, a bad interaction between channel interleavers can introduce a degradation of the overall system performance. To deal with these issues, a new technique to design channel interleavers is introduced in this chapter.

The chapter is organized as follows. In Section 4.1, relevant criteria for the interleaver design are identified and appropriate theoretical tools to represent the optimization constraints are provided. Then, Section 4.2 analyzes the impact on performance of CI, FI, and TI interleavers in the DVB-T2 transmission chain. Section 4.3 defines design guidelines to obtain a set of optimized channel interleavers, based on the identified design criteria. In Section 4.4, these guidelines are applied to design channel interleavers for DVB-T2. Their interaction with the BI as well 88 CHAPTER 4. IMPROVING CHANNEL INTERLEAVERS as the impacts of the adoption of the proposed interleaving structures on the channel interleaver latency and complexity are also studied. Finally, Section 4.5 shows simulation results of system performance with proposed interleavers and Section 4.6 concludes the chapter. This work was supported by the French National Research Agency, Project Mobile MultiMedia (M3, ANR-2010-VERS-0010) and is published in the December 2014 issue of IEEE Transactions on Broadcasting [START_REF] Garzón Bohórquez | Channel Interleavers for Terrestrial Broadcast: Analysis and Design[END_REF].

Identification of relevant design criteria for channel interleavers

An efficient channel interleaver has to take advantage of the time and frequency diversities allowed by OFDM multicarriers. Thus, from a diversity point of view, the parameters identified as being the most important are the channel interleaver span properties and the achieved mutual information distribution over FEC blocks.

Span properties

The channel interleaver operates at the OFDM frame level, between the constellation mapper and the OFDM modulator (see Fig. The time and frequency minimum span, S t and S f , associated with the cell with address i can be defined according to [START_REF] Crozier | New high-spread high-distance interleavers for turbo-codes[END_REF], [START_REF] Berrou | Designing good permutations for turbo codes: towards a single model[END_REF] as:

S t (i) = min j =i |t i -t j | + t Π(i) -t Π(j) (4.1) S f (i) = min j =i |f i -f j | + f Π(i) -f Π(j) (4.2)
where t u and f u represent the OFDM symbol and carrier indexes of the cell with address u. To design a channel interleaver with good scattering properties able to efficiently break error bursts, the minimum span values of equations (4.1) and (4.2) have to be maximized. In addition, their respective multiplicity (i.e., number of cells having the same span value) should be minimized. The validation of span properties in bi-dimensional channel interleavers, where the time and frequency components are treated separately, is a straightforward task that can be verified by equations (4.1) and (4.2). This validation may become difficult when one-dimensional interleavers are considered. Indeed, the modification of any of the interleaver parameters jointly affects both span properties. To tackle this problem, a joint representation of both the time and frequency span properties in the L 1 space is proposed. The L p spaces are function spaces defined using a natural generalization of the p-norm for finite dimensional vector spaces [START_REF] Hansen | New types of function spaces[END_REF]. Let x be x = (x 1 , x 2 , x 3 , ..., x q ) a vector in the L p space over the q-dimensional real vector space R q . For a real number p ≥ 1, the p-norm of x is defined by:

x p = (|x 1 | p + |x 2 | p + ... |x q | p ) 1/p (4.3)
Thus, for p = 2 we get the Euclidean norm. For p = 1, in the bi-dimensional real vector space R 2 , (4.3) becomes:

x 1 = |x 1 | + |x 2 | (4.4)
At the OFDM frame level, a valid span region composed of four sub-regions can be defined (see Fig. 4.2). In the worst case, we consider a couple of neighbor cells (i, j) in the input OFDM frame. If the first interleaved cell Π(i) is placed as shown in Fig. 4.2, the second interleaved cell Π(j) must be placed inside one of the valid span sub-regions.

Let us define a vector m = (m 1 , m 2 ) in the L 1 space over R 2 by:

m 1 = i -j (4.5) m 2 = Π(i) -Π(j) (4.6)
The 1-norm of this vector corresponds to the span between i and j. Then according to Fig. 4.2, a couple of cells (i, j) satisfying the minimum time and frequency span constraints, S T min and S F min verifies any of the following conditions:

Sub-region 1 : n 1 (k) ≤ m 1 ≤ n 0 (k) (4.7) OFDM symbols Carriers NT*NF-1 NF-1
Valid span region for Π(j) Sub-region 2 :

1 2 3 4 Π(i) +S Tmin k=t Π( ) i f Π( ) i t Π( ) i -S Tmin k=t Π( ) i k=0 (k) n 3 k=NT-1 (k) n 3 -S Fmin f Π( ) i f Π( ) i +S Fmin (k) n 2 (k) n 0 (k) n 1 (k) n 1 (k) n 2 0 ... 1 (k) n 0
n 3 (k) ≤ m 1 ≤ n 2 (k) (4.8) Sub-region 3 : n 0 (k) ≤ m 1 ≤ n 1 (k) (4.9)
Sub-region 4 :

n 2 (k) ≤ m 1 ≤ n 3 (k) (4.10)
where n 0 , n 1 , n 2 and n 3 represent the boundaries of valid sub-regions in the OFDM frame. Their value depends on the OFDM symbol k considered. Those boundary values can be expressed as:

n 0 (k) = |k•NF -Π(i)| (4.11) n 1 (k) = f Π(i) -S F min + k•NF -Π(i) (4.12) n 2 (k) = f Π(i) + S F min + k•NF -Π(i) (4.13) n 3 (k) = |(1+k)•NF -1 -Π(i)| (4.14)
where k varies from 0 to t Π(i) -S T min for sub-regions 1 and 2 and from t Π(i) +S T min to NT -1 for sub-regions 3 and 4.

Note that the existence of each sub-region depends on the position of Π(i); therefore they exist if the following conditions are met: Sub-region 1 :

t Π(i) -S T min > 0 (4.15) f Π(i) -S F min > 0 (4.

Mutual information distribution

As advocated in [START_REF] Seshadri | Capacity-based parameter optimization of bit-interleaved coded CPM with differential detection[END_REF], [START_REF] Seshadri | The BICM capacity of coherent continuous-phase frequency shift keying[END_REF], capacity-based optimization is a computation-efficient tool to find a good tradeoff between the parameters of a Bit-Interleaved Coded Modulation (BICM) e.g., modulation order M, code rate R. Using capacity as a cost function, energy-efficient parameters can be found, i.e., parameters providing capacity-approaching performance at a minimum of E b /N 0 . Capacity is obtained by evaluating the average MI between the input and the output of the composite channel, consisting of the modulator, the transmission channel, and the soft output of the demodulator (Fig. 4.4). As BICM transforms the composite channel into log 2 M parallel binary-input continuous output channels [START_REF] Caire | Bit-interleaved coded modulation[END_REF], the capacity of the overall system is: The capacity of the ith BICM subchannel C i is the average MI between the input b i ∈ {0, 1} and the corresponding log-likelihood ratio z i at the output of the demodulator:

C = log 2 M i=1 C i (4.19)
C i = I(b i ; z i ) = E [i(b i ; z i )] (4.20)
With the mutual information random variable i(b; z) expressed as in [START_REF] Gallager | Information Theory and Reliable Communication[END_REF], and assuming that b is equally likely to be 1 or 0, i(b; z) evolves to:

i(b; z) = log 2 -max * 0, z (-1) b (4.21)
where, max * (x, y) = log(e x + e y ) as defined in [START_REF] Viterbi | An intuitive justification and a simplified implementation of the MAP decoder for convolutional codes[END_REF]. Then, substituting (4.20) and (4.21) into (4.19) gives the expression for the BICM capacity:

C = log 2 M i=1 log 2 -E max * 0, z i (-1) b i (4.22)
which is measured in nats per channel use. To convert the capacity into bits per channel use, (4.22) must be divided by log 2.

In practice, the effect of the channel interleaver on BICM capacity is very small and, in the context of channel interleaver design, it is more relevant to visualize the MI distribution over the FEC blocks in the OFDM frame. Since an optimal channel interleaver must guarantee an uncorrelated error distribution inside the FEC blocks, the average MI should be homogeneously distributed between FEC blocks, guaranteeing that error bursts are uniformly distributed.

Let L be the FEC block length. The average MI per FEC block can be expressed as:

AMI j = log 2 - L i=1 max * 0, z i (-1) b i /L (4.23)
where the current FEC block number is represented by j, j = 1...NFEC. In addition, the variance of the MI distribution gives a measure of the amount of variation of the FEC block MI to the mean MI:

VAR(AMI) = NFEC j=1 (AMI j -E [AMI]) 2 /NFEC (4.24)
Therefore, a homogeneous distribution of MI is characterized by a low VAR(AMI) value. Thus, the best interleaver candidates are those allowing the lowest values of VAR(AMI). It should be noted that this selection criterion is channel-dependent.

PERFORMANCE ANALYSIS OF DVB-T2 CHANNEL INTERLEAVERS 93

Performance analysis of DVB-T2 channel interleavers

The performance of the set of DVB-T2 interleaver components placed between the constellation mapper and OFDM modulator is analyzed in three steps. First, we observe the impact of each component on the overall system performance. The BER at the output of the LDPC decoder is plotted in different interleaving conditions, starting from no channel interleaving and then introducing the different components, CI, TI and FI. Second, the corresponding MI distributions are analyzed at the SNR decoding threshold. Finally, the time and frequency span histograms of the complete T2 interleaver (i.e., CI, TI and FI) are determined. The simulation parameters are given in Table 4.1. LDPC decoding runs 50 iterations of the sum-product algorithm [START_REF] Kschischang | Factor graphs and the sumproduct algorithm[END_REF]. Both TU6 mobile channel [START_REF]Digital Video Broadcasting (DVB): implementation guidelines for a second generation digital terrestrial television broadcasting system (DVB-T2)[END_REF] with Doppler frequency f d = 166 Hz and P1 Rayleigh channel [START_REF]Digital Video Broadcasting (DVB): implementation guidelines for a second generation digital terrestrial television broadcasting system (DVB-T2)[END_REF] are considered for transmission. The TU6 channel profile reproduces the propagation in a typical urban area including the classical Jakes [START_REF] Jakes | Microwave mobile communications[END_REF] Fig. 4.5 shows simulation results over a TU6 channel. Since the frequency selectivity varies with time, the FI component does not bring much interleaving gain. The best performance is obtained when the complete T2 interleaver or TI only is implemented. This result is confirmed by Fig. 4.6, which shows that, in these cases, a homogeneous MI distribution in the FEC blocks is obtained. In contrast, poor performance is obtained with interleavers that produce a larger dispersion of the MI distribution, i.e., CI, and FI. We can deduce from these observations that the interleaving component that introduces the largest performance gain over the TU6 channel is the TI.

Over time-invariant channels such as the P1 Rayleigh channel, the frequency selectivity does not change with time. Thus, the frequency interleaver is an important interleaving component, as confirmed by Fig. 4.7. The best BER performance over the P1 channel is obtained with the complete T2 interleaver or when the FI only is implemented. These results are also consistent with the MI distribution shown in Fig. 4.8. On the other hand, there seems to be a contradiction between the BER performance obtained with the CI and the corresponding MI distribution, which is very close to the MI distribution obtained without interleaving. Actually, the effect of CI cannot be observed in the MI distribution curves, since CI is applied inside a FEC block and has no impact on the MI distribution per FEC block. Finally, in order to identify potential bad scattering interactions between the different interleaver components, we have plotted the span histograms for the complete T2 interleaver. Fig. 4.9 shows the first 100 values of the histograms, with their multiplicities. In the simulated configuration, the OFDM frame is composed of 357 OFDM symbols transmitted over 1705 carriers. Under these conditions and based on [START_REF] Crozier | New high-spread high-distance interleavers for turbo-codes[END_REF], the theoretical maximum minimum time and frequency span values are √ 2•NT = 26 and √ 2•NF = 58, respectively. According to the histogram results, this instance of T2 interleaver has poor span properties in both the time and frequency domains, since the minimum time and frequency span values are 0 and 1, respectively. These poor span properties are the result of a bad interaction between the different interleaving components due to a non-global optimization. This can lead to system performance degradation in transmissions where the FEC code approaches its limit in error correction capacity. For instance, in the case of channel impairments arriving by bursts and affecting a large number of consecutive OFDM symbols and/or subcarriers, low spans result into the packing of a large number of erroneous or erased bits into a limited number of FEC blocks. These blocks are then likely to be incorrectly decoded, especially for high code rates.

Guidelines for designing improved channel interleavers

The channel interleaving function can be defined as:

i = Π(i) (4.25)
where Π represents the permutation law, and i and i represent the read and write cell addresses in the input and output OFDM frames, respectively. As explained in Section 4.1, Π should be designed in order to, first, maximize the minimum time and frequency span values; second, minimize their respective multiplicity; and third, reduce the MI distribution variance over the FEC blocks.

In order to limit the interleaver complexity, the proposed interleaver families are based on regular and ARP interleavers. Thereby, the first interleaver family is based

DESIGNING IMPROVED CHANNEL INTERLEAVERS

97 on a single regular permutation, the second one on a double regular permutation. In the third one, an ARP is introduced, and the last one is based on a double ARP.

Regular Interleaver

The permutation law for a regular channel interleaver can be defined as:

Π(i) = P •i mod NC (4.26)
where NC is the total number of cells in the OFDM frame and P is the interleaver period. NC and P have to be relatively prime. The Regular Interleaver (RI) period is calculated by: P = P t •NF + P f (4.27)

where P t and P f represent the equivalent interleaver periods in the time and frequency domains. Given that there are NT symbols in an OFDM frame, the best candidate values for P t are the interleaver periods allowing the maximization of the minimum span value for a regular permutation in a vector of length NT . First, all admissible values for P t according to the vector length are identified. Second, the best candidate values regarding the span criterion are selected. In the same way the best candidate values for P f are determined regarding the span criterion in a vector of length NF .

Afterwards, the best candidates for P are chosen among the different values obtained with the selected couples of P t and P f . The candidates for P are validated if the span values of the resulting interleaved cells belong to one of the valid span subregions in the L 1 space defined in Section 4.1.2. Then, a limited number of values are kept for P , corresponding to the highest minimum time and frequency span values with low multiplicities in the complete OFDM frame. Finally, the selected P value is the one providing the best span properties with a low MI distribution variance.

Double Regular Interleaver

A Double Regular Interleaver (2RI) consists of two regular permutations in the time and frequency axes. The write cell address Π(i) can be expressed using its carrier index f Π(i) and its OFDM symbol index t Π(i) as:

Π(i) = NF •t Π(i) + f Π(i) (4.28) where, t Π(i) = P t •t i mod NT (4.29) f Π(i) = P f •f i mod NF (4.30) t i = i/NF (4.31) f i = i mod NF (4 .32)
... As the permutation law is designed independently for the time and frequency components, a modification of the interleaver period on one axis, P t or P f , does not impact the histogram of the other component, unlike the RI family. Consequently, the L 1 space representation is of no help in this case. On the other hand, the time interleaver component as defined in (4.29) has an important drawback: neighboring cells within the same OFDM symbol and belonging to the same FEC block are interleaved to the same OFDM symbol. To deal with this, a periodic shift S T • (f i mod NT ) is introduced into the time component (see Fig. 4

Carriers

Almost Regular Permutation Interleaver

The last considered two interleavers are based on the ARP model. To obtain an ARP channel interleaver, the structure of the RI interleaver is modified by introducing a vector of shifts whose length is equal to the degree of the introduced disorder. First, the best interleaver period P in the RI family is used as the interleaver period of the ARP. Then, the permutation law is obtained by introducing a vector of shifts SG in (4.26) that leads to:

Π(i) = (P •i + SG(i mod Q)) mod NC (4.34)
To ensure the bijectivity of the ARP function, the disorder degree Q must be a divisor of the total number of cells NC. In order to limit the search space for the shifts, Q is selected from the lower divisors of NC. In practice, the Q candidate shifts are randomly set one by one and submitted for validation: a shift vector is valid if the span values of the resulting interleaved cells belong to one of the valid span subregions in the L 1 space defined in Section 4.1.2. Finally, the best candidate shifts are those allowing the best span properties with a low MI distribution variance.

Double Almost Regular Permutation Interleaver

The 2RI structure is modified by replacing each regular interleaver component by an ARP component: a shift vector is introduced in each axis, the vector length being equal to the degree of the introduced disorder. The resulting permutation is called Double Almost Regular Permutation (2ARP). Then, to define the frequency ARP component ARP f , a vector of frequency shifts SF is introduced in (4.30):

f Π(i) = (P f •f i + SF (f i mod Q f )) mod NF (4.35)
To ensure the bijectivity of this function, the frequency disorder degree Q f must be a divisor of the number of carriers, NF . Similarly, on the time axis a vector of time shifts ST is introduced to define the time ARP component, ARP t . Equation (4.33) becomes:

t Π(i) = (P t •t i + S T •(f i mod NT ) + ST ((f i mod NT ) mod Q t )) mod NT (4.36)
To ensure the bijectivity of this function, the time disorder degree Q t must be a divisor of the number of OFDM symbols, NT . It is worth noting that S T is taken as the interleaver period for the ARP t component, since S T represents a time interleaver period for neighboring cells within the same OFDM symbol. Then, the 2ARP permutation law is defined by (4.28) using (4.35) and (4.36) as components.

Due to the introduction of ARP components, the number of interleaver parameters to be set is increased. Consequently, the design procedure is divided into the following steps:

1. Determine the candidate vectors for SF in the ARP f : The P f value obtained for the 2RI is used as interleaver period in this component. In order to limit the search space for the frequency shifts, Q f is selected from the lower divisors of NF . Then, in a vector of length NF the shifts of SF are defined. its interaction with S T , the best couples for such values are determined by taking as candidates the admissible values for P t allowing a minimum span value between 19 and 24 from Fig. 4.11. Finally, the couples of P t and S t corresponding to the lowest MI distribution variances in the TU6 channel are chosen. The four best candidates for P t and S T are given in Table 4.3 for P f = 293, NT =357 and NF =1705.

The best RI period is used as the interleaver period in the ARP permutation law. Given that the total number of cells in the OFDM frame is 608,685, the ARP disorder degree Q can be: 3, 5, 7, 11, 17, or 31. Considering the large depth of this interleaver, Q was set to 5 or 7, avoiding a too long exploration time, whilst maintaining a reasonable disorder degree. Then, the optimal SG vectors are obtained as described The permutation law of the 2ARP interleaver is defined by its two ARP component functions. Due to the number of parameters to define, the complete design procedure is presented in Appendix C. The best candidate vectors for the ARP f component are determined via the frequency span criterion. Then, their performance in terms of MI distribution is evaluated. Table 4 also shows ARP II to be the best ARP-based interleaver, since it reduces the span value multiplicity more than 2ARP I.

Interaction between channel interleaver and BI

Correlated coded bits are defined as coded bits connected to the same check node in the LDPC parity-check matrix. In general, the BI has to map correlated bits to different constellation symbols or cells. To ensure a good interaction between our proposed channel interleavers and the BI, correlated coded bits must be mapped to neighboring cells, but not to the same cell. Afterwards, neighboring cells are spread out by the channel interleaver, ensuring that correlated coded bits are placed neither in neighboring cells, nor in the same cell. Therefore, if deep fading affects a particular constellation symbol, it affects only one of the bits connected to a given check node. Thanks to the contribution of the remaining connections, the affected bit can then be recovered.

In most cases, the BI in the DVB-T2 transmission chain is composed of a parity and a column twist interleaver [START_REF] Yokokawa | Parity and column twist bit interleaver for DVB-T2 LDPC codes[END_REF]. In our case study, the codeword length is 16,200 with a QPSK constellation. For these parameters, only the parity interleaver is included [START_REF]Digital Video Broadcasting (DVB): implementation guidelines for a second generation digital terrestrial television broadcasting system (DVB-T2)[END_REF]. Therefore, correlated coded bits are mapped to different cells far away in the frame, which is not suitable for the channel interleavers we propose. For easy identification of correlated coded bits, the proposed new BI is based on the DVB-T2 parity and column-row interleaver for a codeword length of 16,200 with a 16-QAM constellation. According to [START_REF] Etsi | Digital Video Broadcasting (DVB): frame structure channel coding and modulation for a second generation digital terrestrial television broadcasting system (DVB-T2)[END_REF], the column-row memory block thus has eight columns, as shown in Fig. 4.14. Then, correlated bits are placed in the same row of the memory block. In the new BI the coded bits are no longer read out row-wise from the memory block, but rather following the mapping mask given in Table 4.7. An example of the effect of using this mask on the BER performance is given in Appendix D.

Impact on latency and complexity

The impacts of the adoption of the proposed interleaving structures on the latency and hardware complexity of the channel interleaver are analyzed below.

Impact on latency

In the complete T2 interleaver, the component interleavers operate at different levels: the CI operates on cells inside a FEC block, the TI operates on several FEC blocks and the FI operates on the OFDM subcarriers of each symbol. The CI reads cells from its input vector in normal order and writes them to its output vector in permuted order. Therefore, the TI is supposed to wait until the CI output vector is completed to start reading the cells from it and writing them column-wise to the TI memory block. The FI reads cells from the TI memory block row-wise in permuted order and writes them to its output vector in natural order. Thus, the FI is supposed to wait until the whole TI memory block is completed to start writing the cells to its output vector. Consequently, the three interleaving steps adopted in the standard cannot be performed jointly in one step, since they operate on different sizes. In contrast, our proposed channel interleavers operate on the total interleaving depth size. Therefore, they can be performed directly in one step. Thus, proposed channel interleavers allow a reduction on the overall system latency corresponding to the cumulated CI and FI latencies.

Impact on complexity

Two different levels of complexity have to be considered. First, the memory required to store the data to be interleaved, which is the dominant factor in terms of silicon area. Table 4.8 compares these requirements for the complete T2 interleaver and our proposal. The proposed interleavers only require the TI memory block, saving the CI and the FI memory space. The TI size represents the dominant term for DVB-T2. However, with the FFT size of 32k adopted in the standard, the memory requirements for the FI are no longer negligible. On the other hand, the complexity related to the implementation of the permutation function (i.e., to compute interleaved memory addresses) must be considered. It highly depends on the permutation function. Both the complete T2 and our proposed interleavers require only very simple address computation logic. The CI and FI address computations are based on simple linear feedback shift registers. The DVB-T2 TI is a simple column-row interleaver and only a limited number of parameters have to be stored, depending on the LDPC codeword length and modulation mode. For the proposed interleavers, the address computation complexity is similar to the case of a column-row interleaver, since the same operations are involved. The only difference lies in the number of parameters to store. For each interleaving size, the proposed interleavers need to store the number of parameters listed in Table 4.9. Therefore, all things considered, the proposed channel interleavers are less complex, especially due to reduced memory requirements.

Interleaver Number of blocks to store Complete T2

NFEC +1 FEC blocks and 1 OFDM symbol Proposed interleavers NFEC FEC blocks

ARP Q + 1 2ARP Q t + Q f + 3

Performance evaluation of the proposed channel interleavers

Computer simulations were carried out to evaluate the performance of the proposed channel interleavers, including the new BI structure. We considered transmissions over a TU6 and a P1 channel, with and without regular erasure patterns on the OFDM carriers. These patterns can be caused by man-made noise, e.g., motor vehicle ignition noise [START_REF] Lago-Fernandez | Modelling impulsive interference in DVB-T: Statistical analysis, test waveforms and receiver performance[END_REF]. Indeed, several man-made noise sources generally cause error bursts for broadcast signals. The corresponding model is performed via the introduction of erasure events as proposed in [START_REF] Hazmi | Studies in digital TV signal processing: Impulse noise mitigation, repeater loop interference cancellation, and DVB-T transmission in CATV networks[END_REF]. For comparative purposes, the complete T2 interleaver structure was also simulated. The simulation parameters are listed in show the BER performance of the proposed channel interleavers for LDPC code rate 2/3 over a TU6 and a P1 channel, respectively. In both channel types the performance of the proposed interleavers is very close to the performance of the complete T2 interleaver. Actually, in normal channel conditions, the time and frequency diversities allowed by the FEC code and the OFDM frame are large enough for the complete T2 interleaver to recover from channel impairments. In contrast, when the transmitted signal undergoes a regular erasure pattern of 15%, the performance improvement due to the proposed interleavers can be easily identified. As shown in Figs. [START_REF] Berrou | Near optimum error correcting coding and decoding: turbo-codes[END_REF].15 and 4.16, the performance gain is about 0.5 and 0.8 dB over a TU6 and a P1 channel, respectively compared to the complete T2 interleaver performance. Fig. 4.17 compares the corresponding MI distributions over the TU6 channel with 15% of erasures. One can observe that the MI of the complete T2 interleaver is no longer uniformly distributed, thus bringing out its weakness in such severe channels. When the correction capability is weakened, the impact of this interaction becomes greater.

CHAPTER 4. IMPROVING CHANNEL INTERLEAVERS

According to these results, performance improvements are expected when increasing the code rate or the erasure ratio, provided that the latter does not exceed the redundancy ratio bound. To illustrate these trends, Fig. 4.20 shows the BER performance of the ARP II and the complete T2 interleavers, for LDPC code rate 2/3 over a TU6 channel with different erasure ratios. The ARP II gain increases from 0.5 to almost 1.5 dB, when the erasure ratio increases from 15 to 20%. In order to evaluate the proposed channel interleavers with higher-order modulations, Figs. 4.21 and 4.22 show the BER performance of the ARP II and complete T2 interleavers for 16-QAM modulation and LDPC effective code rate 37/45 over the TU6 and P1 channels. Similarly to the QPSK case, BER performance of both interleavers remains very close for normal channel conditions. When the transmitted signal undergoes a regular erasure pattern of 15%, a performance gain of about 2.5 dB in both channels is observed, although 16-QAM makes constellation symbols more vulnerable to channel impairments than QPSK. Therefore, the proposed interleaver structure is also appropriate for the different constellation orders considered in the DVB-T2 standard.

Conclusion

In this chapter, we have presented a new method to design channel interleavers. It calls for a joint optimization of time and frequency span properties. A graphical representation of the span properties in a bi-dimensional L 1 space can be used to efficiently select the interleaver parameters.

The MI distribution between FEC blocks was identified as a relevant selection criterion for channel interleavers. A suitable target is a homogeneous distribution of the MI in the FEC blocks. Thus, it is possible to select the best channel interleaver candidates according to the MI distribution variance, before running long BER simulations.

Improvements in the BER performance of the DVB-T2 chain can be achieved when using this approach, especially in poor channel conditions, such as in the presence of regular erasure patterns. Furthermore, the reduction in the number of channel interleaving components allows better control of the interleaver design parameters and provides reductions in system latency and complexity.

In transmission systems including a BI, it was shown that a good interaction between the BI and the channel interleaver is achieved by using an appropriate constellation symbol mapping mask.

A further optimization of the interleavers in a Multiple Input Single Output (MISO) transmission still has to be undertaken to consider all DVB-T2 transmission scenarios.

I n this thesis, we studied various techniques to improve the error rate performance of state-of-the-art transmission systems. First, we investigated the enhancement of turbo coded schemes, especially when very low error rates are required. In particular, we have studied the joint optimization of puncturing patterns and interleavers for punctured Turbo Codes (TCs) but we also considered precoded structures. Moreover, for transmission scenarios where the transmitted signal undergoes impulsive noise and/or selective fading (e.g., broadcasting applications), we focused on the design of efficient channel interleavers to mitigate the effect of such channels impairments on the error correction coding performance.

Conclusions

Chapter 1 presents the basic prerequisites related to the channel coding and interleaving techniques studied in the framework of the thesis.

In Chapter 2, we have investigated the optimization of puncturing patterns and interleaving functions for TCs. As a result, a method to design efficient punctureconstrained interleavers was proposed. In order to jointly optimize the TC interleaver with puncturing patterns, the proposed method involves three main stages: first, a suitable puncturing mask for the constituent code of the TC is determined; second, a group of candidate interleavers validating the design criteria is generated; third, the candidate interleaver with the best TC Hamming distance spectrum is selected.

During the puncturing mask selection process, catastrophic masks for the constituent codes of the TC are early identified by evaluating their respective distance spectrum. Then, a restricted subset of puncturing masks providing TCs with good convergence behavior are selected by performing a modified EXIT chart analysis with actual decoding iterations and uniform interleaving. Finally, the puncturing mask providing the best tradeoff between convergence threshold and error floor performance is identified by Monte Carlo simulation of the TC error rate.

In this chapter, conventional design criteria for TC interleavers are considered (e.g., span properties, correlation girth, and data puncturing constraints). However, a new correlation graph representation is proposed: we show that the correlation graph for TCs is a degree-4 regular graph with a number of vertices equal to K, where K is the information sequence length.

In addition, a new interleaver puncturing constraint related to parity puncturing is proposed. By including the proposed parity puncturing constraint into the interleaver design, the most reliable extrinsic information bit positions (i.e., those evaluated from unpunctured parity positions) from one constituent decoder of the TC are sent to the most error-prone data positions in the other one. It allows the TC decoder to take advantage of the reliability difference between extrinsic information evaluated from punctured and unpunctured parity positions.

Subsequently, an analysis of the most popular algebraic interleavers for TCs DRP, QPP, and ARP is carried out to select a suitable interleaver structure for TCs. It is shown that any DRP or QPP interleaver can be expressed as an ARP interleaver. Thus, the same interleaving properties of DRP or QPP interleavers can be provided by ARP interleavers. Therefore, the ARP interleaver is a sufficient permutation model to design TCs with the achievable asymptotic performance from any of the three interleaver families. Consequently, the ARP interleaver structure is chosen for later analyses.

Next, a graph-based method to select the ARP interleaver parameters is proposed, which allows an easy introduction of puncturing constraints as well as other design criteria (e.g., span properties and correlation girth) during the selection of the interleaver parameters. On the other hand, significant improvements in convergence threshold and error floor performance are expected by including puncturing constraints into the interleaver design. When combined with the proposed graphbased approach, these constraints significantly limit the search space for the different interleaver parameters compared to previously known methods and allow good interleavers to be found in record time.

The proposed approach is tested on several examples of TCs using LTE parameters (block size, code rate): significant performance improvements are observed in both the waterfall and the error floor region.

Thereafter, Chapter 3 explores precoding techniques for TCs. First, the reference precoding structure proposed in [START_REF] Tong | Precoded turbo code within 0.1 dB of Shannon limit[END_REF] is analyzed assuming a regular precoding pattern and uniform interleaving. From this analysis, we show that the optimization of precoding ratio ρ cannot be based on classical EXIT charts, as proposed in the reference paper. Conventional 3D EXIT charts also fail to provide an accurate prediction of the best precoding ratios in terms of PTC convergence performance. Therefore, we propose an appropriate optimization tool for the selection of the precoding ratio of Precoded Turbo Codes (PTCs), based on the analysis of the real extrinsic information exchange between the constituent codes of the TC with uniform interleavers.

Afterwards, we propose enhancements to the reference PTC. First, we consider a variant structure, called hybrid precoding structure, which precodes the whole data sequence. A new parameter, φ, is introduced to define the serial-to-parallel precoding ratio. A significant asymptotic gain is achieved with this precoding structure at the expense of a slight loss in convergence performance compared to a classical TC. Then, the combination of the reference and hybrid structures is studied. We observe that the parameters of this new composite structure allows to achieve either the convergence performance of the original structure or the error floor performance of the hybrid structure, but not both for a single couple of parameters ρ and φ. Since this structure cannot solve the convergence versus error floor tradeoff issue, the hybrid structure is selected for further analysis, due to its good performance in the error floor region.

Additionally, the impact of the precoding pattern structure and of the constituent code of the precoder on the error rate performance of the hybrid PTC is analyzed. It is shown that a precoding mask with several consecutive unpunctured parities can improve the convergence of the hybrid PTC. Concerning the precoding constituent code, the accumulator is identified as the best one, both from a performance and complexity point of view.

Finally, relevant interleaver design criteria are proposed, taking into account the 3D nature of PTCs. In particular, we show that the correlation graph in this case becomes a regular graph of degree 6. For illustrative purpose, a set of interleavers is generated for the hybrid PTC, using LTE parameters (block size, code rate). The resulting code shows better performance than the LTE code. However, it is still outperformed by the TC using the puncture-constrained interleaver designed in Chapter 2. As a summary, PTCs will probably not replace well-designed conventional TCs. However, they can find their way in adaptive systems where the target error rate can change according to the transmission conditions. Then, a PTCs encoders and decoders can offer the flexibility needed for adaptability.

Chapter 4 deals with the design of good channel interleavers, especially for broadcasting applications. The joint maximization of time and frequency spans is identified as the main relevant design criteria for such interleavers. A graphical representation of time and frequency span properties in a bi-dimensional L 1 space is proposed to efficiently select the interleaver parameters meeting span constraints. Moreover, it was shown that the best error rate performance is achieved with channel interleavers providing a homogeneous distribution of the Mutual Information (MI) in the FEC blocks. Thus, it is possible to select the best channel interleaver candidates according to the MI distribution variance, before running a large number of timeconsuming error rate simulations.

The DVB-T2 standard is taken as an application example in this chapter. First, we have evaluated the effect of each component of the DVB-T2 channel interleaver on the overall system error rate performance. We have observed that, for mobile channel models, the time interleaver plays the most significant role in the interleaving chain. In contrast, in time-invariant channels, the frequency interleaving component is the most important one. We have also identified that, due to bad interactions between the different components, some particular configurations of the DVB-T2 interleaver do not ensure high span values.

Therefore, we subsequently consider designing a global channel interleaver. Several models, based on regular or almost regular permutations are studied and design guidelines are proposed to meet the span and MI constraints. An application example is derived and compared to the DVB-T2 channel interleaver. We show that improvements in the error rate performance of the DVB-T2 chain can be achieved when using the proposed interleavers, especially in poor channel conditions, such as in the presence of regular erasure patterns. Furthermore, a better control of the interleaver design parameters and a lower system latency and complexity are then achieved, thanks to the reduction in the number of channel interleaving components.

Future works

We have not thoroughly explored all the topics addressed in the thesis, yet. For instance, a deeper exploration related to the work carried out on designing efficient puncture-constrained interleavers for TCs involves exploring new parity puncturing constraints. As shown in the application example for R = 1/3 in Chapter 2, mother codes with low coding rates for TCs allow a higher degree of freedom for data puncturing. Therefore, the number of unpunctured parities becomes larger than the number of unpunctured data symbols. Thus, it is worth exploring new strategies for the connection of the available unpunctured parity positions in that case.

On the other hand, this work can also be extended to communication systems allowing rate compatibility to the different users. In such systems, an incremental redundancy is provided according to the needed Quality of Service (QoS) and to the receiver capabilities. Thus, a joint optimization of the interleaving function and of the puncturing patterns, for the different coding rates allowed in the system, must be crucial in the overall system performance. Moreover, an exploration of the effect of data puncturing and of the design of improved interleaving functions for more complex coding structures, such as M -binary codes, non-binary codes, or irregular turbo codes, can be a relevant topic for future research.

The extension of the work on precoding techniques for TCs to explore convergence improvements for low code rates could be a promising subject, according to the results in [START_REF] Tong | Precoded turbo code within 0.1 dB of Shannon limit[END_REF] for the reference precoding structure. Moreover, the design of the interleavers for the hybrid PTC structure via a specific algorithm, which would use the proposed correlation graph, has still to be studied.

We have proposed efficient channel and BI interleavers for a single input single output system. A further optimization of the interleavers in a Multiple Input Single Output (MISO) transmission still has to be undertaken to consider all DVB-T2 transmission scenarios. In fact, the MISO transmission using Alamouti coding can be used in DVB-T2. In this case, there are time and frequency offsets between antennas. Such offsets can introduce intersymbol interference, which should be considered as an additional parameter for channel interleaver optimization. ARP Q S(0) S( 1) S( 2) S( 3) S( 4) S( 5) S( 6 In another example, the interleaver of length 1696, for which f 2 = 954, is considered. K and f 2 are factorized as: 1696 = 2 5 was associated with the correlation girth g because for the whole group of candidates for P g = 4, except for P = 1 and P = 6143 for which g = 2 in a RI structure. Afterwards, the parameters for the ARP interleaver candidates are determined by Algorithm 1. Three interleaver configurations are considered: NDP for DPR = 0/8, DPC and DPPC for DPR = 2/8. Table B.1 lists the best ARP interleavers generated for each design configuration as well as the corresponding S min and g values achieved.

Their respective distance spectrum is estimated and given in Table B.2. The same conclusions as those observed for the K = 1504 case are made for K = 6144. The use of data puncturing allows to reach larger d min values. In addition, the proposed DPPC ARP interleaver allows to reduce the distance spectrum multiplicities compared to the DPC ARP interleaver. Finally, the statistics on the efficiency of the different configurations in finding large d min values is provided in Table B.3. The conclusions are similar to those made for the K = 1504. Furthermore, it is noted that the increase on the percentage of candidates with large d min values by the proposed DPPC interleaver configuration is higher for K = 6144 compared to the K = 1504 case. ARP S min g P S(1) S( 2) S( 3) S( 4) S( 5) S( 6) S( 7

Parity puncturing constraint

Following the strategy proposed in Section 2.3.2.2, the parity puncturing constraint for the puncturing mask with DPR = 2/16 is identified. In this mask only the parity at position 1 is a free parity for N = 16 (see Table B.5). Table B.6 lists the different distance spectra obtained including an additional punctured data symbol in unpunctured data positions in the mask. According to these results, 10 is the most error-prone data position within a puncturing period. Therefore, the DPPC interleaver must ensure that data symbols at positions 1 and 10 in d are interleaved to positions 10 and 1 in d , respectively.

Puncture-constrained ARP interleaver design

Through the strategy introduced in Section 2.5.2 a S min goal of 70% of the theoretical upper bound and a g goal of 8 were selected. Then, the best candidates for the RI period P of the ARP function have to be identified. Fig. 2.9 shows the possible candidates for P as well as the maximum achievable value of S min , which is 52 for a RI structure. Thus, the best candidates for P are those allowing a S min value of at least 39 from Fig. ... The efficiency of this mask can be easily identified in case of channel impairments, such as erasure events as shown in Figs. D.3 and D.4 over the P1 and TU6 channels, respectively. Indeed, a performance gain around 2 dB is observed for the new BI when compared to the DVB-T2 BI for the best performing interleaver design based on ARP over a P1 channel with 15% of erasures. It increases to around 8 dB for 135 136 APPENDIX D. PROPOSED BI MAPPING MASK PERFORMANCE the case of a TU6 channel with erasures. A small gain (0.35 dB) is even observed over a classical TU6 channel.

1

  Structure basique de l'encodeur d'un turbocode. . . . . . . . . . . . . xxx 2 Exemple d'illustration de la règle de connexion d'un entrelaceur DPC. xxxiii 3 Graphe utilisé pour la construction de l'entrelaceur. Les adresses à l'intérieur du cercle correspondent au placement des données dans l'ordre naturel (non entrelacé) des données et les adresses à l'extérieur du cercle représentent la position des mêmes données après entrelacement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxxiv 4 Courbes de taux d'erreur trame sur canal gaussien du turbocode pour différentes configurations d'entrelacement. LTE : courbes de taux d'erreurs du turbocode LTE. TUB : borne de l'union tronquée. . . . . xxxv 5 Structure basique de l'encodeur d'un turbocode précodé. . . . . . . . xxxvi 6 (a) Structure de précodage hybride. (b) Information extrinsèque échangé par le décodeur élémentaire de l'accumulateur. . . . . . . . . xxxvii 7 Comparaison des courbes de taux d'erreur trame du TC hybride pour φ = 0.04, d'un TC classique (NDP), et du TC LTE sur canal gaussien, modulation BPSK, R = 4/5, K = 1504 et 16 itérations de décodage BCJR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxxviii 8 Représentation de l'entrelaceur canal sur la trame OFDM. . . . . . . xxxix 9 Comparaison de courbes de taux d'erreur binaire des meilleurs entrelaceurs obtenues sur le canal TU6 pour le code LDPC de rendement 2/3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xli 10 Distributions d'information mutuelle sur le canal TU6 avec 15% d'effacement de porteuses, pour le code LDPC de rendement 2/3, NFEC = 75, E s /N 0 = 8 dB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xlii 1.1 Basic TC encoder structure. . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 RSC(13, 15) 8 constituent code of the LTE TC. . . . . . . . . . . . . . 8 1.3 Basic turbo decoder structure. . . . . . . . . . . . . . . . . . . . . . . 11 1.4 Typical BER curves for coded and uncoded systems. . . . . . . . . . 12 1.5 EXIT chart measurement for the constituent SISO decoder. . . . . . 13 xiii xiv LIST OF FIGURES 1.6 Example of TC EXIT charts and decoding trajectories for different SNR values: lower than (a) and higher or equal to (b) the convergence threshold of the TC. . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.7 Basic PTC encoder structure. . . . . . . . . . . . . . . . . . . . . . . 16 1.8 Basic PTC decoder structure. . . . . . . . . . . . . . . . . . . . . . . 17 1.9 A possible representation of the TC interleaver when using CRSC constituent codes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.10 Correlation graph and one example of correlation cycle with g = 4. . 20 1.11 Example of low weight data sequence that cannot be broken by a row-column interleaver. . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.12 DRP interleaver structure. . . . . . . . . . . . . . . . . . . . . . . . . 24 1.13 Basic DVB-T2 transmission chain. . . . . . . . . . . . . . . . . . . . . 29 1.14 Column-row and parity interleaver. (a) Without column twist. (b) With column twist. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.1 Comparison of EXIT charts computed from the complete data frame and from punctured and unpunctured parity positions at the SNR decoding threshold over the AWGN channel. . . . . . . . . . . . . . . 40 2.2 Example of parity puncturing constraint according to the puncturing mask, with 0 = Punctured and 1 = Unpunctured. . . . . . . . . . . . 41 2.3 Example of proposed correlation graph representation for TCs with r = 4 and g = 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.4 Possible representation of the ARP interleaver structure, with S(0), ..., S(Q-1) = 0 and K = 4Q. . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.5 Example of possible inter-layer shifts for layer l = 0, with K = 4Q. . 49 2.6 Example of possible intra-layer shifts for layer l = 0, with T 0 = 0 and K = 4Q. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.7 Extrinsic information exchange between constituent codes of the TC at E b /N 0 = 1.6 dB with 16 TC iterations, K = 1504, and R = 2/3 over the AWGN channel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.8 Error rate performance of the best puncturing masks over the AWGN channel with BPSK modulation for K = 1504 and R = 2/3. . . . . . . 54 2.9 S min for the possible values for P in a RI structure for K = 1504. . . . 55 2.10 Extrinsic information exchange between constituent codes of the TC at E b /N 0 = 0.05 dB with 16 TC iterations, K = 1504, and R = 1/3 over the AWGN channel. . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.11 Error rate performance of the best puncturing masks over the AWGN channel with BPSK modulation for K = 1504 and R = 1/3. . . . . . . 59 2.12 Frame error rate performance comparison between the different ARP interleaver configurations over the AWGN channel for R = 2/3 and R = 4/5, K = 1504, and CRSC constituent codes with generator polynomials (13, 15) 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 LIST OF FIGURES xv 2.13 Bit error rate performance comparison between the different ARP interleaver configurations over the AWGN channel for R = 2/3 and R = 4/5 , K = 1504, and CRSC constituent codes with generator polynomials (13, 15) 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.14 Frame error rate performance comparison between the different ARP interleaver configurations over the AWGN channel for R = 2/3 and R = 4/5, K = 6144, and CRSC constituent codes with generator polynomials (13, 15) 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.15 Bit error rate performance comparison between the different ARP interleaver configurations over the AWGN channel for R = 2/3 and R = 4/5 , K = 6144, and CRSC constituent codes with generator polynomials (13, 15) 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.1 Considered PTC encoder structure. . . . . . . . . . . . . . . . . . . . 3.2 PTC EXIT chart evaluated at E b /N 0 =2 dB for different values of ρ, K = 1504, and R = 4/5 over the AWGN channel. . . . . . . . . . . . . 3.3 PTC error rate performance for different values of ρ over the AWGN channel with BPSK modulation for K = 1504 and R = 4/5. . . . . . . 3.4 3D EXIT chart measurement for SISO 1 decoder in the PTC decoding structure. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 3D EXIT chart and decoding trajectory for the PTC evaluated at E b /N 0 =2.43 dB for ρ = 0.11, K = 1504, and R = 4/5 over the AWGN channel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 3D EXIT chart and decoding trajectory for the PTC evaluated at E b /N 0 =2.43 dB for ρ = 0.16, K = 1504, and R = 4/5 over the AWGN channel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 TC EXIT chart and decoding trajectory evaluated at E b /N 0 =2.43 dB over the AWGN channel. . . . . . . . . . . . . . . . . . . . . . . . . . 3.8 Histograms of extrinsic information E at the input of SISO 1 generated in SISO 0 and SISO 2 without a priori information, for ρ = 0.06 (a) and for ρ = 0.11 (b), evaluated at E b /N 0 = 2 dB over the AWGN channel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.9 Extrinsic information exchange between constituent codes of the TC at E b /N 0 = 2.55 dB with 16 PTC iterations, K = 1504, and R = 4/5 over the AWGN channel. . . . . . . . . . . . . . . . . . . . . . . . . . 3.10 (a) Hybrid precoding structure. (b) Extrinsic information exchanged by the SISO decoder of the accumulator. . . . . . . . . . . . . . . . . 3.11 Extrinsic information exchange between constituent codes of the TC at E b /N 0 = 2.55 dB with 16 iterations of the hybrid PTC decoder for different values of φ, K = 1504, and R = 4/5 over the AWGN channel. 3.12 Hybrid PTC error rate performance for different values of φ over the AWGN channel with BPSK modulation for K = 1504 and R = 4/5. . . 3.13 Composite precoding structure. . . . . . . . . . . . . . . . . . . . . . xvi LIST OF FIGURES 3.14 Extrinsic information exchange between constituent codes of the TC at E b /N 0 = 2.55 dB with 16 iterations of the composite PTC decoder for ρ = 0.11 and different values of φ, K = 1504, and R = 4/5 over the AWGN channel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.15 Composite PTC error rate performance for ρ = 0.11 and different values of φ, over the AWGN channel with BPSK modulation for K = 1504 and R = 4/5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.16 Extrinsic information exchange between constituent codes of the TC at E b /N 0 = 2.55 dB with 16 iterations of the composite PTC decoder for φ = 0.04 and different values of ρ, K = 1504, and R = 4/5 over the AWGN channel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.17 Composite PTC error rate performance for φ = 0.04 and different values of ρ, over the AWGN channel with BPSK modulation for K = 1504 and R = 4/5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.18 Example of accumulator trellis stages for 1 (a) and 2 (b) consecutive parities sent to the TC, selected by a regular precoding pattern. . . . 78 3.19 Extrinsic information exchange between constituent codes of the TC at E b /N 0 = 2.55 dB with 16 iterations of the hybrid PTC decoder for φ = 0.04 and different values of CP , K = 1504, and R = 4/5 over the AWGN channel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 3.20 Hybrid PTC error rate performance for φ = 0.04 and different values of CP , over the AWGN channel with BPSK modulation for K = 1504 and R = 4/5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 3.21 Considered constituent codes for the precoder. . . . . . . . . . . . . . 80 3.22 Extrinsic information exchange between constituent codes of the TC at E b /N 0 = 2.55 dB with 16 iterations of the hybrid PTC decoder for the considered precoder constituent codes, φ = 0.04, CP = 2, K = 1504, and R = 4/5 over the AWGN channel. . . . . . . . . . . . . . . . . . . 81 3.23 Hybrid PTC error rate performance for the considered precoder constituent codes, φ = 0.04 and CP = 2, over the AWGN channel with BPSK modulation for K = 1504 and R = 4/5. . . . . . . . . . . . . . . 82 3.24 Hybrid PTC error rate performance for RSC(5, 4) 8 and RSC(7, 5) 8 as constituent codes for the precoder, different values for CP , and φ = 0.04, over the AWGN channel with BPSK modulation for K = 1504 and R = 4/5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 3.25 Example of Π 1 and Π 2 interleavers having good span properties, which compose a Π 1,2 interleaver showing bad span properties (a). Example of Π 1,2 having good span properties, but composed of a Π 1 interleaver having bad span properties (b). . . . . . . . . . . . . . . . . . . . . . 83 3.26 Example of independent correlation graphs (a) and unified correlation graph (b) for Π 1 , Π2 , and Π 1,2 . . . . . . . . . . . . . . . . . . . . . . . 84 LIST OF FIGURES xvii 3.27 Frame error rate performance comparison between the hybrid PTC, using the accumulator for φ = 0.04 and CP = 2, and the TC for NDP and DPPC interleaver configurations over the AWGN channel for R = 4/5, K = 1504, and CRSC constituent codes with generator polynomials (13, 15) 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.28 Bit error rate performance comparison between the hybrid PTC, using the accumulator for φ = 0.04 and CP = 2, and the TC for NDP and DPPC interleaver configurations over the AWGN channel for R = 4/5, K = 1504, and CRSC constituent codes with generator polynomials (13, 15) 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 A possible representation of the channel interleaver. . . . . . . . . . . 4.2 Valid span sub-regions in the output OFDM frame. . . . . . . . . . . 4.3 First valid span sub-region. . . . . . . . . . . . . . . . . . . . . . . . 4.4 Composite channel in the BICM system. . . . . . . . . . . . . . . . . 4.5 BER system performance with DVB-T2 channel interleaver components over the TU6 channel. . . . . . . . . . . . . . . . . . . . . . . . 4.6 MI Distribution, NFEC = 75, E s /N 0 = 5.2 dB, TU6 channel. . . . . . . 4.7 BER system performance with DVB-T2 channel interleaver components over the P1 channel. . . . . . . . . . . . . . . . . . . . . . . . . 4.8 MI Distribution, NFEC = 75, E s /N 0 = 6.8 dB, P1 channel. . . . . . . . 4.9 Time and frequency span histograms for the complete T2 Interleaver. The Y -axis displays the number of cells having the same time/frequency span value. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.10 Example of periodic shift with 7 OFDM symbols. . . . . . . . . . . . 4.11 Admissible interleaver period values for a regular permutation in a vector of length NT =357. . . . . . . . . . . . . . . . . . . . . . . . . 4.12 Time span histogram for the best proposed interleavers. . . . . . . . 4.13 Frequency span histogram for the best proposed interleavers. . . . . . 4.14 Column-row and parity interleaver . . . . . . . . . . . . . . . . . . . 4.15 BER performance comparison between the best interleavers over the TU6 channel for LDPC code rate 2/3. . . . . . . . . . . . . . . . . . 4.16 BER performance comparison between the best interleavers over the P1 channel for LDPC code rate 2/3. . . . . . . . . . . . . . . . . . . 4.17 MI Distribution, NFEC = 75, E s /N 0 = 8 dB, TU6 channel with 15% of erasures, for LDPC code rate 2/3. . . . . . . . . . . . . . . . . . . 4.18 BER performance comparison between the best interleavers over the TU6 channel for LDPC effective code rate 37/45. . . . . . . . . . . . 4.19 BER performance comparison between the best interleavers over the P1 channel for LDPC effective code rate 37/45. . . . . . . . . . . . . 4.20 BER performance comparison between ARP II and complete T2 interleavers over the TU6 channel for LDPC code rate 2/3 and different erasure percentages. . . . . . . . . . . . . . . . . . . . . . . . . . . . . xviii LIST OF FIGURES 4.21 BER performance comparison between ARP II and complete T2 interleavers over the TU6 channel for LDPC effective code rate 37/45 and 16-QAM modulation. . . . . . . . . . . . . . . . . . . . . . . . . 111 4.22 BER performance comparison between ARP II and complete T2 interleavers over the P1 channel for LDPC effective code rate 37/45 and 16-QAM modulation. . . . . . . . . . . . . . . . . . . . . . . . . 111 A.1 Minimum disorder degree Q s of the equivalent ARP interleavers for the different sizes K of the LTE QPP interleaver. . . . . . . . . . . . 120 B.1 Extrinsic information exchange between constituent codes of the TC at E b /N 0 = 1.6 dB with 16 TC iterations, K = 6144, and R = 2/3 over the AWGN channel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 B.2 Error rate performance of the best puncturing masks over the AWGNchannel with BPSK modulation for K = 6144 and R = 2/3. . . . . . . 122 B.3 S min for the possible values for P in a RI structure for K = 6144. . . . 123 B.4 Extrinsic information exchange between constituent codes of the TC at E b /N 0 = 2.55 dB with 16 TC iterations, K = 1504, and R = 4/5 over the AWGN channel. . . . . . . . . . . . . . . . . . . . . . . . . . 125 B.5 Error rate performance of the best puncturing masks over the AWGN channel with BPSK modulation for K = 1504 and R = 4/5. . . . . . . 126 B.6 Extrinsic information exchange between constituent codes of the TC at E b /N 0 = 2.55 dB with 16 TC iterations, K = 6144, and R = 4/5 over the AWGN channel. . . . . . . . . . . . . . . . . . . . . . . . . . 129 B.7 Error rate performance of the best puncturing masks over the AWGN channel with BPSK modulation for K = 6144 and R = 4/5. . . . . . . 130 D.1 First five rows of the BI memory block. . . . . . . . . . . . . . . . . . 135 D.2 First 20 cells of the FEC block after new BI interleaving. . . . . . . . 135 D.3 BER performance comparison between the DVB-T2 BI ad the proposed new BI over the P1 channel, with and without erasures, for LDPC effective code rate 37/45. . . . . . . . . . . . . . . . . . . . . . 136 D.4 BER performance comparison between the DVB-T2 BI and the proposed new BI over the TU6 channel, with and without erasures, for LDPC effective code rate 37/45. . . . . . . . . . . . . . . . . . . . . . 136List of Tables 1.1 Some known applications of turbo codes. . . . . . . . . . . . . . . . . 2.1 Comparison between the theoretical upper bounds on g for the stateof-the-art and proposed correlation graph representation, K = 1504 and K = 6144. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Best CRSC distance spectrum for each DPR, corresponding codeword multiplicities at distance d, A d , and puncturing masks (0 =Punctured, 1 = Unpunctured). R = 2/3 and N = 8. . . . . . . . . . . . . . . . . . . 2.3 Best CRSC distance spectrum for each DPR, corresponding codeword multiplicities at distance d, A d , and puncturing masks (0 =Punctured, 1 = Unpunctured). R = 2/3, and N = 16. . . . . . . . . . . . . . . . . . 2.4 CRSC distance spectrum of the DPR-2/8 mask when one additional data bit is punctured. A d is the multiplicity of codewords at distance d. Considered parity puncturing mask = 11000001 (0 = Punctured, 1 = Unpunctured). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Best candidates for ARP interleaver with the different puncturing constraints, S(0) = 0, K = 1504 and R = 2/3. . . . . . . . . . . . . . . 2.6 Estimated distance spectrum for the best ARP interleavers in AWGN channel with corresponding multiplicities A d and cumulated input weight at d min = d 0 , w d 0 . K = 1504 and R = 2/3. . . . . . . . . . . . . 2.7 Statistics on the effectiveness of the different ARP configurations for K = 1504 and R = 2/3, in CPU: Intel core i5 3.3 GHz and RAM 8 Go. 2.8 Best CRSC distance spectrum for each DPR, corresponding codeword multiplicities at distance d, A d , and puncturing masks (0 =Punctured, 1 = Unpunctured). R = 1/3 and N = 8. . . . . . . . . . . . . . . . . . . 2.9 Best candidates for ARP interleaver with the different puncturing constraints, K = 1504 and R = 1/3. . . . . . . . . . . . . . . . . . . . 2.10 Estimated distance spectrum for the best ARP interleavers in AWGN channel with corresponding multiplicities A d and cumulated input weight at d min = d 0 , w d 0 . K = 1504 and R = 1/3. . . . . . . . . . . . . 4.1 Simulation Parameters. . . . . . . . . . . . . . . . . . . . . . . . . . . xix xx LIST OF TABLES 4.2 Best P values with NT =357, and NF =1705. . . . . . . . . . . . . . . 4.3 Best P t and S T values with P f =293, NT =357, and NF =1705. . . . . 4.4 Best ARP interleavers with SG(0) =0, P = 40627, NT =357, and NF =1705. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Best SF values with SF (0)=0, P t =193, S T =127, P f =293, NT =357, and NF =1705. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 Best 2ARP interleavers with ST (0)=0, NT =357, and NF =1705. . . . 4.7 New BI mapping mask for bits read out from the memory block and written in the cells. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.8 Memory requirements for the complete T2 and proposed channel interleavers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.9 Number of parameters to store to implement proposed interleavers. . A.1 Parameters of the DRP interleavers. . . . . . . . . . . . . . . . . . . . A.2 Equivalent ARP interleavers to the DRP from Table A.1. . . . . . . . A.3 Possible values for Q in the QPP interleaver with K = 216, f 1 = 11 and f 2 = 36. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.4 Equivalent ARP interleavers with P = f 1 , Q s= 6 and S(0) = 0. . . . A.5 Possible values for Q in the QPP interleaver with K = 1696, f 1 = 55 and f 2 = 954. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.6 Equivalent ARP interleavers with P = f 1 , Q s = 8, S(0) = S(4) = 0. . . . B.1 Best candidates for ARP interleaver with the different puncturing constraints, S(0) = 0, K = 6144 and R = 2/3. . . . . . . . . . . . . . . B.2 Estimated distance spectrum for the best ARP interleavers in AWGN channel with corresponding multiplicities A d and cumulated input weight at d min = d 0 , w d 0 . K = 6144 and R = 2/3. . . . . . . . . . . . . B.3 Statistics on the effectiveness of the different ARP configurations for K = 6144 and R = 2/3, in CPU: Intel core i5 3.3 GHz and RAM 8 Go. B.4 Best CRSC distance spectrum for each DPR, corresponding codeword multiplicities at distance d, A d , and puncturing masks (0 =Punctured, 1 = Unpunctured). R = 4/5, and N = 8. . . . . . . . . . . . . . . . . . B.5 Best CRSC distance spectrum for each DPR, corresponding codeword multiplicities at distance d, A d , and puncturing masks (0 =Punctured, 1 = Unpunctured). R = 4/5, and N = 16. . . . . . . . . . . . . . . . . . B.6 CRSC distance spectrum of the DPR-2/16 mask when one additional data bit is punctured. A d is the multiplicity of codewords at distance d. Considered parity puncturing mask = 1100000000000010 (0 = Punctured, 1 = Unpunctured). . . . . . . . . . . . . . . . . . . . . . . B.7 Best candidates for ARP interleaver with the different puncturing constraints for R = 4/5 and K = 1504. . . . . . . . . . . . . . . . . . . LIST OF TABLES xxi B.8 Estimated distance spectrum for the best ARP interleavers in AWGN channel with corresponding multiplicities A d and cumulated input weight at d min = d 0 , w d 0 . K = 1504 and R = 4/5. . . . . . . . . . . . . B.9 Statistics on the effectiveness of the different ARP configurations for K = 1504 and R = 4/5, in CPU: Intel core i5 3.3 GHz and RAM 8 Go. B.10 Best candidates for ARP interleaver with the different puncturing constraints for R = 4/5 and K = 6144. . . . . . . . . . . . . . . . . . . B.11 Estimated distance spectrum for the best ARP interleavers in AWGN channel with corresponding multiplicities A d and cumulated input weight at d min = d 0 , w d 0 . K = 6144 and R = 4/5. . . . . . . . . . . . . B.12 Statistics on the effectiveness of the different ARP configurations for K = 6144 and R = 4/5, in CPU: Intel core i5 3.

  Cumulated input weight of the A d input sequences with Hamming weight d. Notations xxvii y k,r Channel observation of the parity bit received at instant k. y k,s Channel observation of the systematic bit received at instant k. xxviii Résumé de la thèse

Chapitre 1 .

 1 Techniques de codage canal et d'entrelacementLe premier chapitre présent les prérequis nécessaires sur les techniques de codage canal et d'entrelacement étudiés dans le cadre de cette thèse.

Figure 1 :

 1 Figure 1: Structure basique de l'encodeur d'un turbocode.

Figure 2 :

 2 Figure 2: Exemple d'illustration de la règle de connexion d'un entrelaceur DPC.

Figure 3 :

 3 Figure 3: Graphe utilisé pour la construction de l'entrelaceur. Les adresses à l'intérieur du cercle correspondent au placement des données dans l'ordre naturel (non entrelacé) des données et les adresses à l'extérieur du cercle représentent la position des mêmes données après entrelacement.

Figure 4 :

 4 Figure 4: Courbes de taux d'erreur trame sur canal gaussien du turbocode pour différentes configurations d'entrelacement. LTE : courbes de taux d'erreurs du turbocode LTE. TUB : borne de l'union tronquée.

Figure 5 :

 5 Figure 5: Structure basique de l'encodeur d'un turbocode précodé.

b)Figure 6 :

 6 Figure 6: (a) Structure de précodage hybride. (b) Information extrinsèque échangé par le décodeur élémentaire de l'accumulateur.

  Nous avons adapté les critères de conception d'entrelaceurs aux trois dimensions du PTC hybride. Ensuite, nous avons construit un jeu d'entrelaceurs pour celuici, avec R = 4/5 et K = 1504, basé sur le model ARP. La Figure 7 montre la performance en termes de taux d'erreur trame du PTC hybride sur canal gaussien avec une modulation BPSK. On remarque que la performance d'un TC classique (NDP) utilisant une terminaison circulaire est améliorée de presque deux décades dans le floor pour le PTC hybride. De plus, le PTC hybride proposé atteint un gain xxxviii RÉSUMÉ DE LA THÈSE voisin de 0,38 dB en convergence et de presque 4 décades dans le floor, par rapport au motif de poinçonnage et à l'entrelaceur adoptés dans LTE.

Figure 7 :Chapitre 4 .

 74 Figure 7: Comparaison des courbes de taux d'erreur trame du TC hybride pour φ = 0.04, d'un TC classique (NDP), et du TC LTE sur canal gaussien, modulation BPSK, R = 4/5, K = 1504 et 16 itérations de décodage BCJR.

Figure 8 :

 8 Figure 8: Représentation de l'entrelaceur canal sur la trame OFDM.

Figure 9 :

 9 Figure 9: Comparaison de courbes de taux d'erreur binaire des meilleurs entrelaceurs obtenues sur le canal TU6 pour le code LDPC de rendement 2/3.

Figure 10 :

 10 Figure 10: Distributions d'information mutuelle sur le canal TU6 avec 15% d'effacement de porteuses, pour le code LDPC de rendement 2/3, NFEC = 75, E s /N 0 = 8 dB.

2 Figure 1 . 1 :

 211 Figure 1.1: Basic TC encoder structure.

Figure 1 . 2 :

 12 Figure 1.2: RSC(13, 15) 8 constituent code of the LTE TC.

10 CHAPTER 1 .

 1 CHANNEL CODING AND INTERLEAVING TECHNIQUES where P(d k = ±1|y) are the a posteriori probabilities of data bit d k given the received sequence y. The sign of L (d k |y) gives the value of the data bit d k , 1 or 0.

Figure 1 . 3 :

 13 Figure 1.3: Basic turbo decoder structure.

Figure 1 . 4 :

 14 Figure 1.4: Typical BER curves for coded and uncoded systems.

Figure 1 . 5 :

 15 Figure 1.5: EXIT chart measurement for the constituent SISO decoder.

Figure 1 . 6 :

 16 Figure 1.6: Example of TC EXIT charts and decoding trajectories for different SNR values: lower than (a) and higher or equal to (b) the convergence threshold of the TC.

Figure 1 . 7 :

 17 Figure 1.7: Basic PTC encoder structure.

Figure 1 . 8 :

 18 Figure 1.8: Basic PTC decoder structure.

Figure 1 . 9 :

 19 Figure 1.9: A possible representation of the TC interleaver when using CRSC constituent codes.

Figure 1 . 10 :

 110 Figure 1.10: Correlation graph and one example of correlation cycle with g = 4.

Figure 1 . 11 :

 111 Figure 1.11: Example of low weight data sequence that cannot be broken by a row-column interleaver.

Figure 1 . 12 :

 112 Figure 1.12: DRP interleaver structure.

Figure 1 . 13 :

 113 Figure 1.13: Basic DVB-T2 transmission chain.

Figure 1 . 14 :

 114 Figure 1.14: Column-row and parity interleaver. (a) Without column twist. (b) With column twist.

Figure 2 . 1 :

 21 Figure 2.1: Comparison of EXIT charts computed from the complete data frame and from punctured and unpunctured parity positions at the SNR decoding threshold over the AWGN channel.

Figure 2 . 2 :

 22 Figure 2.2: Example of parity puncturing constraint according to the puncturing mask, with 0 = Punctured and 1 = Unpunctured.

  1.10), since no extrinsic information is provided in such connections. Therefore, a more suitable representation of the correlation graph for TCs is proposed in this section. It includes only existing connections between the vertices in d and d , which correspond to the counted connections in the correlation cycle. An example of this new representation is shown in Fig.2.3. The connections of the vertices in d correspond to the outer circle in red. The inner connections in green represent the connections between the vertices in d for a given interleaver Π. Thus, only the representation of the vertices of d are needed on the graph.

Figure 2 . 3 :

 23 Figure 2.3: Example of proposed correlation graph representation for TCs with r = 4 and g = 4.

Figure 2 . 4 :

 24 Figure 2.4: Possible representation of the ARP interleaver structure, with S(0), ..., S(Q-1) = 0 and K = 4Q.

Figure 2 . 5 :Figure 2 . 6 :

 2526 Figure 2.5: Example of possible inter-layer shifts for layer l = 0, with K = 4Q.

Figure 2 . 7 :

 27 Figure 2.7: Extrinsic information exchange between constituent codes of the TC at E b /N 0 = 1.6 dB with 16 TC iterations, K = 1504, and R = 2/3 over the AWGN channel.

Figure 2 . 8 :

 28 Figure 2.8: Error rate performance of the best puncturing masks over the AWGN channel with BPSK modulation for K = 1504 and R = 2/3.

Figure 2 . 9 :

 29 Figure 2.9: S min for the possible values for P in a RI structure for K = 1504.

Figure 2 . 11 :

 211 Figure 2.11: Error rate performance of the best puncturing masks over the AWGN channel with BPSK modulation for K = 1504 and R = 1/3.

Figure 2 . 12 :Figure 2 . 13 :

 212213 Figure 2.12: Frame error rate performance comparison between the different ARP interleaver configurations over the AWGN channel for R = 2/3 and R = 4/5, K = 1504, and CRSC constituent codes with generator polynomials (13, 15) 8 .

Figure 2 . 14 :

 214 Figure 2.14: Frame error rate performance comparison between the different ARP interleaver configurations over the AWGN channel for R = 2/3 and R = 4/5, K = 6144, and CRSC constituent codes with generator polynomials (13, 15) 8 .

Figure 2 . 15 :

 215 Figure 2.15: Bit error rate performance comparison between the different ARP interleaver configurations over the AWGN channel for R = 2/3 and R = 4/5 , K = 6144, and CRSC constituent codes with generator polynomials (13, 15) 8 .

Figure 3 . 1 :

 31 Figure 3.1: Considered PTC encoder structure.

Figure 3 . 2 :

 32 Figure 3.2: PTC EXIT chart evaluated at E b /N 0 =2 dB for different values of ρ, K = 1504, and R = 4/5 over the AWGN channel.

Figure 3 . 3 :Figure 3 . 4 :

 3334 Figure 3.3: PTC error rate performance for different values of ρ over the AWGN channel with BPSK modulation for K = 1504 and R = 4/5.

Figure 3 . 5 :

 35 Figure 3.5: 3D EXIT chart and decoding trajectory for the PTC evaluated at E b /N 0 =2.43 dB for ρ = 0.11, K = 1504, and R = 4/5 over the AWGN channel.

Figure 3 . 6 :

 36 Figure 3.6: 3D EXIT chart and decoding trajectory for the PTC evaluated at E b /N 0 =2.43 dB for ρ = 0.16, K = 1504, and R = 4/5 over the AWGN channel.

CHAPTER 3 .Figure 3 . 7 :

 337 Figure 3.7: TC EXIT chart and decoding trajectory evaluated at E b /N 0 =2.43 dB over the AWGN channel.

Figure 3 . 8 :

 38 Figure 3.8: Histograms of extrinsic information E at the input of SISO 1 generated in SISO 0 and SISO 2 without a priori information, for ρ = 0.06 (a) and for ρ = 0.11 (b), evaluated at E b /N 0 = 2 dB over the AWGN channel.

CHAPTER 3 .Figure 3 . 9 :Figure 3 . 10 :

 339310 Figure 3.9: Extrinsic information exchange between constituent codes of the TC at E b /N 0 = 2.55 dB with 16 PTC iterations, K = 1504, and R = 4/5 over the AWGN channel.

Figure 3 . 11 :

 311 Figure 3.11: Extrinsic information exchange between constituent codes of the TC at E b /N 0 = 2.55 dB with 16 iterations of the hybrid PTC decoder for different values of φ, K = 1504, and R = 4/5 over the AWGN channel.

Figure 3 . 12 :

 312 Figure 3.12: Hybrid PTC error rate performance for different values of φ over the AWGN channel with BPSK modulation for K = 1504 and R = 4/5.

Figure 3 . 13 :

 313 Figure 3.13: Composite precoding structure.

Figure 3 . 14 :

 314 Figure 3.14: Extrinsic information exchange between constituent codes of the TC at E b /N 0 = 2.55 dB with 16 iterations of the composite PTC decoder for ρ = 0.11 and different values of φ, K = 1504, and R = 4/5 over the AWGN channel.

Figure 3 . 15 :

 315 Figure 3.15: Composite PTC error rate performance for ρ = 0.11 and different values of φ, over the AWGN channel with BPSK modulation for K = 1504 and R = 4/5.

Figure 3 . 16 :

 316 Figure 3.16: Extrinsic information exchange between constituent codes of the TC at E b /N 0 = 2.55 dB with 16 iterations of the composite PTC decoder for φ = 0.04 and different values of ρ, K = 1504, and R = 4/5 over the AWGN channel.

Figure 3 . 17 :

 317 Figure 3.17: Composite PTC error rate performance for φ = 0.04 and different values of ρ, over the AWGN channel with BPSK modulation for K = 1504 and R = 4/5.

Figure 3 . 18 :

 318 Figure 3.18: Example of accumulator trellis stages for 1 (a) and 2 (b) consecutive parities sent to the TC, selected by a regular precoding pattern.

Figure 3 . 19 :

 319 Figure 3.19: Extrinsic information exchange between constituent codes of the TC at E b /N 0 = 2.55 dB with 16 iterations of the hybrid PTC decoder for φ = 0.04 and different values of CP , K = 1504, and R = 4/5 over the AWGN channel.

Figure 3 . 20 :

 320 Figure 3.20: Hybrid PTC error rate performance for φ = 0.04 and different values of CP , over the AWGN channel with BPSK modulation for K = 1504 and R = 4/5.

8 Figure 3 . 21 :

 8321 Figure 3.21: Considered constituent codes for the precoder.

Figure 3 . 22 :

 322 Figure 3.22: Extrinsic information exchange between constituent codes of the TC at E b /N 0 = 2.55 dB with 16 iterations of the hybrid PTC decoder for the considered precoder constituent codes, φ = 0.04, CP = 2, K = 1504, and R = 4/5 over the AWGN channel.

CHAPTER 3 .Figure 3 . 23 :

 3323 Figure 3.23: Hybrid PTC error rate performance for the considered precoder constituent codes, φ = 0.04 and CP = 2, over the AWGN channel with BPSK modulation for K = 1504 and R = 4/5.

Figure 3 . 24 :

 324 Figure 3.24: Hybrid PTC error rate performance for RSC(5, 4) 8 and RSC(7, 5) 8 as constituent codes for the precoder, different values for CP , and φ = 0.04, over the AWGN channel with BPSK modulation for K = 1504 and R = 4/5.

Figure 3 . 25 :

 325 Figure 3.25: Example of Π 1 and Π 2 interleavers having good span properties, which compose a Π 1,2 interleaver showing bad span properties (a). Example of Π 1,2 having good span properties, but composed of a Π 1 interleaver having bad span properties (b).

Figure 3 . 26 :

 326 Figure 3.26: Example of independent correlation graphs (a) and unified correlation graph (b) for Π 1 , Π 2 , and Π 1,2 .

Figure 3 . 27 :

 327 Figure 3.27: Frame error rate performance comparison between the hybrid PTC, using the accumulator for φ = 0.04 and CP = 2, and the TC for NDP and DPPC interleaver configurations over the AWGN channel for R = 4/5, K = 1504, and CRSC constituent codes with generator polynomials (13, 15) 8 .

Figure 3 . 28 :

 328 Figure 3.28: Bit error rate performance comparison between the hybrid PTC, using the accumulator for φ = 0.04 and CP = 2, and the TC for NDP and DPPC interleaver configurations over the AWGN channel for R = 4/5, K = 1504, and CRSC constituent codes with generator polynomials (13, 15) 8 .

  1.13). A possible representation is shown in Fig.4.1, where NF and NT represent the number of carriers and the number of OFDM symbols respectively. The channel interleaver reads the cells from the input OFDM frame address i, i = 0...NT •NF -1, and writes them to the output OFDM frame address Π(i).

Figure 4 . 1 :

 41 Figure 4.1: A possible representation of the channel interleaver.

4. 1 . 2

 12 Joint representation of the time and frequency span properties in the L 1 space

Figure 4 . 2 :

 42 Figure 4.2: Valid span sub-regions in the output OFDM frame.

Figure 4 . 3 :

 43 Figure 4.3: First valid span sub-region.

92 CHAPTER 4 Figure 4 . 4 :

 92444 Figure 4.4: Composite channel in the BICM system.

94 CHAPTER 4

 944

Figure 4 . 5 :

 45 Figure 4.5: BER system performance with DVB-T2 channel interleaver components over the TU6 channel.

Figure 4 . 6 :

 46 Figure 4.6: MI Distribution, NFEC = 75, E s /N 0 = 5.2 dB, TU6 channel.

Figure 4 . 7 :

 47 Figure 4.7: BER system performance with DVB-T2 channel interleaver components over the P1 channel.

Figure 4 . 8 :

 48 Figure 4.8: MI Distribution, NFEC = 75, E s /N 0 = 6.8 dB, P1 channel.

Figure 4 . 9 :

 49 Figure 4.9: Time and frequency span histograms for the complete T2 Interleaver. The Y -axis displays the number of cells having the same time/frequency span value.

Figure 4 . 10 :

 410 Figure 4.10: Example of periodic shift with 7 OFDM symbols.

CHAPTER

5 Figure 4 . 12 :

 5412 Figure 4.12: Time span histogram for the best proposed interleavers.

5 Figure 4 . 13 :

 5413 Figure 4.13: Frequency span histogram for the best proposed interleavers.

Figure 4 . 14 :

 414 Figure 4.14: Column-row and parity interleaver

Figure 4 . 15 :

 415 Figure 4.15: BER performance comparison between the best interleavers over the TU6 channel for LDPC code rate 2/3.

Figs. 4 .CHAPTER 4

 44 Figs.4.18 and 4.19 show the BER performance of the proposed channel interleavers for the LDPC effective code rate 37/45 over a TU6 and a P1 channel, respectively. In normal channel conditions the same conclusions as for the code rate 2/3 can be drawn. Nevertheless, the system performance improvements with the proposed interleavers are increased for transmissions with erasures. As shown in Fig.4.18, over a TU6 channel, the performance gain obtained with the 2ARP I

Figure 4 . 16 :

 416 Figure 4.16: BER performance comparison between the best interleavers over the P1 channel for LDPC code rate 2/3.

Figure 4 . 17 :

 417 Figure 4.17: MI Distribution, NFEC = 75, E s /N 0 = 8 dB, TU6 channel with 15% of erasures, for LDPC code rate 2/3.

Figure 4 . 18 :

 418 Figure 4.18: BER performance comparison between the best interleavers over the TU6 channel for LDPC effective code rate 37/45.

Figure 4 . 19 :

 419 Figure 4.19: BER performance comparison between the best interleavers over the P1 channel for LDPC effective code rate 37/45.

Figure 4 . 20 :

 420 Figure 4.20: BER performance comparison between ARP II and complete T2 interleavers over the TU6 channel for LDPC code rate 2/3 and different erasure percentages.

Figure 4 . 21 :

 421 Figure 4.21: BER performance comparison between ARP II and complete T2 interleavers over the TU6 channel for LDPC effective code rate 37/45 and 16-QAM modulation.

Figure 4 . 22 :

 422 Figure 4.22: BER performance comparison between ARP II and complete T2 interleavers over the P1 channel for LDPC effective code rate 37/45 and 16-QAM modulation.

  118APPENDIX A. EQUIVALENT EXPRESSIONS OF DRP AND QPP AS ARP

Figure B. 1 :

 1 Figure B.1: Extrinsic information exchange between constituent codes of the TC at E b /N 0 = 1.6 dB with 16 TC iterations, K = 6144, and R = 2/3 over the AWGN channel.

Figure B. 2 :

 2 Figure B.2: Error rate performance of the best puncturing masks over the AWGN channel with BPSK modulation for K = 6144 and R = 2/3.

Figure B. 3 :

 3 Figure B.3: S min for the possible values for P in a RI structure for K = 6144.

Figure B. 5 :

 5 Figure B.5: Error rate performance of the best puncturing masks over the AWGN channel with BPSK modulation for K = 1504 and R = 4/5.

Figure B. 7 :

 7 Figure B.7: Error rate performance of the best puncturing masks over the AWGN channel with BPSK modulation for K = 6144 and R = 4/5.

Figure D. 1 :

 1 Figure D.1: First five rows of the BI memory block.

Figure D. 2 :

 2 Figure D.2: First 20 cells of the FEC block after new BI interleaving.

Figure D. 3 :

 3 Figure D.3: BER performance comparison between the DVB-T2 BI ad the proposed new BI over the P1 channel, with and without erasures, for LDPC effective code rate 37/45.

Figure D. 4 :

 4 Figure D.4: BER performance comparison between the DVB-T2 BI and the proposed new BI over the TU6 channel, with and without erasures, for LDPC effective code rate 37/45.

  3 GHz and RAM 8 Go.

	xxiv xxvi	Abbreviations Notations
	HSR L Ch (y k,s ) Channel LLR. High-Spread Random.
	L a (d k )	A priori LLR.
	LDPC Low-Density Parity-Check. L e (d k ) Extrinsic LLR.
	LLR l	Log-Likelihood Ratio. Layer index in the ARP interleaver.
	Abbreviations MAP Maximum A Posteriori. MI Mutual Information. NC Number of cells in the OFDM frame. Notations NFEC Number of FEC blocks in the OFDM frame.
	NF	Number of carriers in an OFDM symbol.
	NDP NT	Non Data-Punctured. Number of OFDM symbols in an OFDM
	2ARP 2RI 3D OFDM Orthogonal Frequency Division Multiplexing. Double Almost Regular Permutation. Double Regular Interleaver. A d frame. Number of codewords with Hamming weight N 0 One-side noise power spectral density. d (i.e., the multiplicity). N Puncturing pattern period. Three-dimensional. ARP P1 Portable indoor/outdoor Rayleigh-fading channel with 20 taps. B l Intra-layer shift in the ARP interleaver. PK Number of unpunctured parity positions per Almost Regular Permutation. AWGN Additive White Gaussian Noise. BCH PTC Precoded Turbo Code. QAM Quadrature Amplitude Modulation. CP constituent code in a puncturing period. Consecutive parities sent from the precoder to Π Turbo code interleaver. the TC. Π 1 Precoder interleaver. Bose-Chaudhuri-Hocquenghem. BER Bit Error Rate. BI Bit Interleaver. QoS Quality of Service. QPP Quadratic Permutation Polynomial. DPR Π 2 Turbo code interleaver in the PTC. Data puncturing rate. d k Data bit transmitted at instant k. P Regular interleaver period.
	BICM BPSK CI RI d min RSC d RTZ d	Bit-Interleaved Coded Modulation. Binary Phase-Shift Keying. Cell Interleaver. Minimum Hamming distance of the code. Regular Interleaver. Data sequence. Recursive Systematic Convolutional. Interleaved sequence at the output of the TC Return To Zero. interleaver.
	CRSC DPC SISO SNR E b	Circular Recursive Systematic Convolutional. Data Puncture-Constrained. Soft Input Soft Output. Signal-to-Noise Ratio. Transmitted energy per information bit.
	DPPC DRP DVB-T2 2 nd generation Digital Video Broadcasting Data and Parity Puncture-Constrained. Dithered Relative Prime. Terrestrial. TC f 1 Coefficient of the linear term of the QPP in-Turbo Code. TI terleaver. Time Interleaver. TU6 f 2 Coefficient of the quadratic term of the QPP Typical Urban channel with 6 taps. interleaver.
	φ	Serial-to-parallel precoding ratio.
	EXIT	EXtrinsic Information Transfer.
	g	Correlation girth.
	FAST	Fast Algorithm for Searching Trees.
	FEC I(d; L e ) Mutual information. Forward Error Correction.
	FER	Frame Error Rate.
	FI K	Frequency Interleaver. Data sequence length.
		xxii xxiii xxv

Q

Disorder degree of the ARP interleaver.

R c

Rate of the constituent code of the TC. R Overall code rate. ρ Precoding ratio.

Turbo code Polynomials Rate Termination 1 Throughput

	CCSDS 2	binary, 16-state	23, 33 25, 37	1/6, 1/4, 1/3, 1/2	tail bits	1.6 Mbps
	LTE	binary, 8-state	13, 15	Up to 0.95	tail bits	100 Mbps
	WiMAX	double-binary, 8-state	15, 13, 11	1/2, 2/3 3/4	tail-biting	65 Mbps
	DVB-RCS2	double-binary, 16-state	23, 35, 27	1/3 to 7/8	tail-biting	148 Mbps
		double-
	DVB-RCT 3	binary,	15, 13	1/2, 3/4	tail-biting	2 Mbps
		8-state
	Inmarsat (BGAN 4 )	binary, 16-state	23, 35	1/2	no	492 kbps
	Eutelsat (Skyplex)	double-8-state binary,	15, 13	4/5, 6/7	tail-biting	36 Mbps

Table 1 .1: Some

 1 known applications of turbo codes.

	1 Trellis termination techniques are described in section 1.1.1.1
	2 Consultative Committee for Space Data Systems.
	3 Digital Video Broadcasting-Return Channel Terrestrial.
	4 Broadband Global Area Network

  .1.

	K	g (Correlation graph representation from [82])	g (Proposed correlation graph representation)
	1504	23	13
	6144	27	15

Table 2 .

 2

1: Comparison between the theoretical upper bounds on g for the state-ofthe-art and proposed correlation graph representation, K = 1504 and K = 6144.

1 .

 1 Selection

of the candidate values for P:

  The set of admissible values for P is the group of integers from 1 to K -1 relatively prime to K. Then, the C candidate values for P ensuring a minimum span value (1.13) greater than or equal to S min goal, considering an RI structure, are selected.

2. Selection of the Q shift values for each candidate for P: The Q layers for each of the C candidates for P are then placed. For each candidate for P , layer l is placed by computing a value for S(l) from (2.46) fulfilling the puncturing constraints. For this value, the minimum span and correlation girth are evaluated. If they are equal to or higher than S min and g goals one can move on to layer l+1. If the span and girth goals are not met, another value for S(l) has to be evaluated. This process is performed until the whole group of Q shift values are determined. A detailed description of the different steps of the shifts selection, for the C candidates for P , is presented in Algorithm 1.

Table 2 .2: Best

 2 = 16 allows symmetric puncturing masks with DPR values equal to 0/16, 2/16, 4/16, 6/16, and 8/16, obtained from (2.2). Table 2.3 lists the best puncturing mask in terms of CRSC constituent code distance spectrum for each DPR value.

			0 A 1 A 2	A 3	A 4	Puncturing mask: Data/Parity
	0/8	0.8	0	0	0	9	48	11111111/10001000
	2/8 0.88 0	0	3	62	566	01111110/11000001
	4/8	1	0	4	38	358	3310	11001100/10011001
	6/8 1.14 1 36 670 12122 219196	01000100/11011100
	According to the results, the best puncturing mask for DPR values equal to 0/16,
	4/16, and 8/16 are the same as those obtained for DPR values equal to 0/8, 2/8,
	and 4/8, respectively.

CRSC distance spectrum for each DPR, corresponding codeword multiplicities at distance d, A d , and puncturing masks (0 = Punctured, 1 = Unpunctured). R = 2/3 and N = 8.

N

Table 2 . 3 :

 23 Best CRSC distance spectrum for each DPR, corresponding codeword multiplicities at distance d, A d , and puncturing masks (0 = Punctured, 1 = Unpunctured). R = 2/3, and N = 16.

	2.6. APPLICATION EXAMPLES

  1,1), correspond to DPR values 2/16 and 2/8.

		0.8	0.85
		0.7	0.80
		0.6	0.75
	IE1, IA2	0.4 0.5	0.70 0.70	0.75	0.80	0.85
		0.3
									DPR:0, Uniform
		0.2							DPR:2/8, DPC uniform
									DPR:4/8, DPC uniform
		0.1							DPR:2/16, DPC uniform
									DPR:6/16, DPC uniform
		0.0
		0.0	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8
							IA1, IE2

Table 2 . 4 :

 24 CRSC distance spectrum of the DPR-2/8 mask when one additional data bit is punctured. A d is the multiplicity of codewords at distance d. Considered parity puncturing mask = 11000001 (0 = Punctured, 1 = Unpunctured).

	puncturing mask

2.6.1.3 Puncture-constrained ARP interleaver design

For K = 1504, S min has a theoretical upper bound of 54 as defined in Section 1.2.3.1. Following the strategy introduced in Section 2.5.2, a S min goal of 80% of the S min theoretical upper bound and a g goal of 8 were selected. Afterwards, the interleaver candidates are generated according to the steps of the design method presented in Section 2.5.2:

1. Selection of the candidate values for P: The possible candidates for P are the group of integers between 1 and 1503 relatively prime to 1504. The maximum achievable value of S min for the possible values for P considering a RI structure is 52, as shown in Fig.

2

.9. Thus, the best candidates for P are those allowing a S min value between 45 and 52 from Fig.

2

.9. No selection criteria for P was associated with the correlation girth g because for the whole group of candidates for P g = 4, except for P = 1 and P = 1503 for which g = 2 in a RI structure.

of the Q shift values for each candidate for P:

  The parameters for the ARP interleaver candidates are determined by Algorithm 1. Three different design configurations have been studied. In the first one, the puncturing mask with Non Data-Punctured (NDP) (DPR = 0/8) is considered and no puncturing constraint is included into the ARP interleaver. In the other two, DPC and DPPC ARP interleavers are considered for the selected puncturing mask with DPR 2/8. In order to evaluate the efficiency of the different configurations in finding large d min values, the same number of ARP candidates is generated by each configuration. The most efficient configuration is the one with the highest number of generated candidates meeting all the design constraints (girth, span and d min ). Table2.5 lists the best ARP interleavers generated for each design configuration as well as the corresponding S min and g values. Their respective distance spectrum is estimated and given in Table2.6. It is observed that the use of data puncturing allows to reach a larger TC minimum Hamming distance. Furthermore, the proposed DPPC ARP interleaver allows a reduced d min multiplicity compared to the DPC ARP interleaver.

	56 CHAPTER 2. EFFICIENT PUNCTURE-CONSTRAINED INTERLEAVER
	2. Selection

3. Selection of the best ARP interleaver candidate:

Table 2 . 5 :

 25 Best candidates for ARP interleaver with the different puncturing constraints, S(0) = 0, K = 1504 and R = 2/3.

	ARP	w d 0 d 0 d 1 d 2 A d 0	A d 1	A d 2
	NDP 5640 15 16 17 1128 4512 7708
	DPC 4324 19 20 21 752 1880 5264
	DPPC 2444 19 20 21 376 2444 3572

Table 2 . 6 :

 26 Estimated distance spectrum for the best ARP interleavers in AWGN channel with corresponding multiplicities A d and cumulated input weight at d min = d 0 , w d 0 . K = 1504 and R = 2/3.Finally, the statistics on the effectiveness of the different configurations in finding large d min values is provided in Table2.7. The proposed DPPC interleaver structure allows not only to increase the percentage of candidate interleavers with large d min values, but also to reduce the average time to find such interleavers.

	2.6. APPLICATION EXAMPLES

Table 2 . 7 :

 27 Statistics on the effectiveness of the different ARP configurations for K = 1504 and R = 2/3, in CPU: Intel core i5 3.3 GHz and RAM 8 Go.

	2.6.2 8-state CRSC(13, 15, 17) 8 TC

Table 2 . 8

 28 58 CHAPTER 2. EFFICIENT PUNCTURE-CONSTRAINED INTERLEAVERfloor performance and the mask with DPR = 6/8 was finally selected.DPR Rc A 4 A 5 A 6 A 7 A 8

			Puncturing mask:
	A 9	A 10	Data Parity 1
			Parity 2

: Best CRSC distance spectrum for each DPR, corresponding codeword multiplicities at distance d, A d , and puncturing masks (0 = Punctured, 1 = Unpunctured). R = 1/3 and N = 8.

Table 2 . 9

 29 ARPwd 0 d 0 d 1 d 2 A d 0 A d 1 A d 2

	NDP 2632 49 50 51 376 564 940
	DPC	752 59 60 61 188 376 376
	DPPC 3196 61 62 63 376 376 564

: Best candidates for ARP interleaver with the different puncturing constraints, K = 1504 and R = 1/3.

Table 2 .10: Estimated

 2 distance spectrum for the best ARP interleavers in AWGN channel with corresponding multiplicities A d and cumulated input weight at d min = d 0 , w d 0 . K = 1504 and R = 1/3.

  All valid span sub-regions can be plotted in a single bi-dimensional L 1 space. For instance, the first sub-region is shown in Fig.4.3.

	4.1. DESIGN CRITERIA FOR CHANNEL INTERLEAVERS	91
	Sub-region 4 :	(4.17) is verified (4.18) is verified
		m 2
			n 1 (0)
			n 1 (1)
			n 1 (t Π(i) -S Tmin )
		. . .	n 0 (t Π(i) -S Tmin )
		n 0 (0)	n 0 (1)	m 1
	Valid span region
				16)
	Sub-region 2 :	(4.15) is verified f Π(i) + S F min < NF -1	(4.17)
	Sub-region 3 :	(4.16) is verified t Π(i) + S T min < NT -1	(4.18)

Table 4 .1: Simulation Parameters.

 4 Doppler spectrum for 6 taps. The P1 channel profile reproduces portable indoor/outdoor reception conditions and does not include any Doppler effect. It has only non-line-of-sight components and uses 20 taps.

	System Parameter	Value
	FEC codeword length	16,200 bits
	Code rate	2/3
	T2 frame length	100 ms
	Constellation	Non-rotated QPSK
	Bandwidth	8 MHz
	FFT size	2k
	Guard interval	1/4
	Channel estimation	Perfect

  .10). Thus,(4.29)

becomes: t Π(i) = (P t •t i + S T •(f i mod NT )) mod NT (4.33)

P t , S T and P f are chosen from the same groups of admissible values for P t and P f considered in the RI family. Since the permutation law is designed component by component, the optimum P f value can be identified via the frequency span criterion. Then, with P f fixed to its optimum value, the best values for P t and S T are determined as those providing the best time span property with a low MI distribution variance. Finally, the 2RI permutation law is defined by (4.28) using (4.30) and (4.33) as components.

  The Q f candidate shifts are randomly set one by one and submitted for validation. The shifts are valid if the minimum span obtained is close to the one obtained with a regular interleaver period of P f . A group of candidate vectors for SF is generated.

		25									Best candidate values for P t
	Minimum span value	5 10 15 20
		0
		0	30	60	90	120	150	180	210	240	270	300	330	360
								Interleaver period
	Figure 4.11: Admissible interleaver period values for a regular permutation in a
	vector of length NT =357.
						RI	P		VAR
						I	40627 2.42 × 10 -7
						II 40373 2.75 × 10 -7
						III 284188 2.28 × 10 -7
						IV 81293 3.48 × 10 -7

Table 4 . 2 :

 42 Best P values with NT =357, and NF =1705.

	2RI P t S T	VAR
	I	193 127 2.00 × 10 -7
	II 163 230 2.13 × 10 -7
	III 200 127 3.02 × 10 -7
	IV 157 230 2.66 × 10 -7

Table 4 . 3 :

 43 Best P t and S T values with P f =293, NT =357, and NF =1705.

Table 4 . 4 :

 44 4. IMPROVING CHANNEL INTERLEAVERS Best ARP interleavers with SG(0) =0, P = 40627, NT =357, and NF =1705.

	ARP	I	II		III	IV
	Q	5	5		5	7
	SG(1)	292436	532541	533907	212779
	SG(2)	605520	156805	422013	579212
	SG(3)	117595	366665	337345	348202
	SG(4)	412029	567614	377385	528456
	SG(5)	-	-		-	303822
	SG(6)	-	-		-	478957
	VAR 3.64×10 -6 1.79×10 -6 3.44×10 -6 2.40×10 -6
	ARP f SF (1) SF (2) SF (3) SF (4)	VAR
	I	0	293	1412	0	1.73 × 10 -7
	II	1704	3	2	1	2.12 × 10 -7
	III	243	1266	1509	1607 2.63 × 10 -7
	IV	98	976	1609	1462 2.65 × 10 -7

Table 4 . 5

 45

: Best SF values with SF (0)=0, P t =193, S T =127, P f =293, NT =357, and NF =1705.

in Section 4.3.3. Finally, the performance of the ARP candidate interleavers is evaluated in terms of MI distribution with an additional erasure pattern of 15% in the TU6 channel. Table

4

.4 lists the best candidates for SG.

Table 4 . 6 :

 46 .5 lists the best vectors for the ARP f component function. Similarly, the best candidate vectors for the ARP t component are identified. Table 4.6 lists the best 2ARP candidate interleavers, which are composed of the best ST vectors shown in the table, and the ARP f I function from Table 4.5.Figs. 4.12 and 4.13 show the first 100 values of the time and frequency span histograms of the best interleavers from the different families. As expected, the interleavers allowing the highest values of minimum time and frequency span are those based on regular permutation (i.e, RI I, and 2RI I). According to the time span histogram, the best ARP-based interleaver is ARP II. This interleaver slightly reduces the span value multiplicity, whilst keeping a high minimum span. In contrast, with 2ARP I the minimum time span value decreases to 12, which is a considerable reduction compared to the theoretical value of 26. Finally, the frequency span histogram Best 2ARP interleavers with ST (0)=0, NT =357, and NF =1705.

	4.4. APPLICATION OF INTERLEAVER DESIGN GUIDELINES	103
	2ARP	I	II	III	IV
	P t	53	197	62	320
	S T	127	23	23	23
	ST (1)	73	213	213	113
	ST (2)	78	63	63	18
	ST (3)	285	114	114	20
	ST (4)	78	327	327	24
	ST (5)	190	20	20	283
	ST (6)	24	306	306	46
	VAR 8.81×10 -7 9.97×10 -7 1.94×10 -6 1.06×10 -6

Table 4 . 7 :

 47 New BI mapping mask for bits read out from the memory block and written in the cells.

	Read Write Read Write Read Write Read Write
	0	0	17	10	20	20	11	30
	8	1	33	11	30	21	27	31
	1	2	6	12	21	22	24	32
	9	3	38	13	31	23	34	33
	2	4	7	14	14	24	25	34
	18	5	39	15	22	25	35	35
	3	6	4	16	15	26	12	36
	19	7	28	17	23	27	36	37
	16	8	5	18	10	28	13	38
	32	9	29	19	26	29	37	39

Table 4 . 8 :

 48 Memory requirements for the complete T2 and proposed channel interleavers.

	Interleaver Number of parameters to store
	RI	1
	2RI	3

Table 4 . 9 :

 49 Number of parameters to store to implement proposed interleavers.

Table 4

 4

	4.5. PERFORMANCE EVALUATION

.1. The erasure ratio of 15% is an average value considered during

Table A . 1 :

 A1 Parameters of the DRP interleavers.

Table A . 2 :

 A2 Equivalent ARP interleavers to the DRP from Table A.1.are factorized as: u = 2 α u,1 3 α u,2 , following(2.31). According to (2.41), the valid range for α u,1 is 1 ≤ α u,1 ≤ 3. Afterwards, the valid range for α u,2 , 0 ≤ α u,2 ≤ 2, is obtained from (2.42). Then, from these ranges the group of valid values for u is calculated. Finally, the possible values for Q are obtained from(2.30). The respective values for Q are listed in Table A.3. A minimum disorder degree of 6 is found. The shift values of S for this interleaver and for those of length 432, 720 and 1008, for which Q s = 6, are listed in TableA.4.

								)
	I	7 220 127	73	99	754 759	47
	II	7 113	47	144	45	48	663 599
	III	6 541	13 5633 539	15 5631	-
	IV	6 127 6055 125 6056 126 6057	-
		u 2 4 6 8 12 18 24 36 72
		Q 6 12 18 24 36 54 72 108 216

Table A . 3 :

 A3 Possible values for Q in the QPP interleaver with K = 216, f 1 = 11 and f 2 = 36.

	K	216 432 720 1008
	f 1	11 47 79	55
	f 2	36 72 120 84
	S(1) 36 72 120 84
	S(2) 144 288 480 336
	S(3) 108 216 360 756
	S(4) 144 288 480 336
	S(5) 36 72 120 84

Table A . 4 :

 A4 Equivalent ARP interleavers with P = f 1 , Q s = 6 and S(0) = 0.

Table B . 1 :

 B1 Best candidates for ARP interleaver with the different puncturing constraints, S(0) = 0, K = 6144 and R = 2/3.

		2.00	2.25	2.50	2.75	3.00	3.25	3.50	3.75	4.00	4.25
											)
	NDP	75 9 83 3340 732 2196 2877 391 481 4095
	DPC	77 8 1045 727 3195 2775 4053 361 4517 1652
	DPPC 78 8 701 2479 1115 5007 2957 3489 4661 1996

Table B . 6 :

 B6 2.9. Afterwards, the parameters for the ARP interleaver candidates are determined by Algorithm 1. Three interleaver configurations are considered: NDP for DPR = 0/16, DPC and DPPC for DPR = 2/16. TableB.7 lists the best ARP interleavers generated for each design configuration as well as the corresponding S min and g values achieved. Their respective distance spectrum is estimated and given in A 0 A 1 A 2 CRSC distance spectrum of the DPR-2/16 mask when one additional data bit is punctured. A d is the multiplicity of codewords at distance d. Considered parity puncturing mask = 1100000000000010 (0 = Punctured, 1 = Unpunctured).

			A 3	A 4	Data puncturing mask
	0	8 6047 2334859 381315178	0111111111111100
	0	2 6123 3272599 750308910	0111111111111001
	0	8 6042 2328199 377642859	0111111111110101
	0	8 6038 2332485 160321914	0111111111101101
	0 16 536 16307	68224	0111111111011101
	0	2 6376 3144441 735019476	0111111110111101
	0 16 489	13457	113075	0111111101111101
	0 16 536	16292	359330	0111111011111101
	0	2 6125 3274279 996842927	0111110111111101
	0	8 6032 2327999 527349550	0111101111111101
	0	8 6047 2331934 606872251	0111011111111101
	0 16 491	13686	376258	0110111111111101
	0	2 6371 3140138 1138244658	0101111111111101
	0	0 3503 2200764 946127360	0011111111111101

Table B .

 B [START_REF] Vangelista | Key technologies for next-generation terrestrial digital television standard DVB-T2[END_REF]. Like in the R = 2/3 case, the use of data puncturing allows to increase the d min values. Furthermore, the proposed DPPC ARP interleaver allows to reduce the distance spectrum multiplicities compared to the DPC ARP interleaver. The statistics on the efficiency of the different configurations in finding large d min values is provided in TableB.9. The proposed DPPC interleaver structure increases the percentage of candidate interleavers with large d min values and reduces the average time to find such interleavers.

		2.00	2.25	2.50	2.75	3.00	3.25	3.50	3.75	4.00	4.25
	ARP S min g P				S
	NDP	39 8 725	(0, 250, 1224, 239, 931, 48, 236, 449, 30, 856, 1487, 1228, 1440, 1372, 293, 93)
	DPC	39 8 267	(0, 1436, 521, 1492, 1048, 1142, 1337, 957, 57, 1125, 740, 189, 56, 650, 852, 158)
	DPPC 39 8 583	(0, 1107, 1412, 1038, 909, 1250, 546, 1366, 958, 1445, 299, 178, 1273, 96, 1212, 1487)

Table B .10:

 B Best candidates for ARP interleaver with the different puncturing constraints for R = 4/5 and K = 6144.

	ARP S min g	P		S
	NDP	80 8 4741	(0, 3987, 2144, 4792, 5501, 3772, 3569, 5513, 1966, 4855, 3369, 3527, 349, 6130, 2295, 807)
	DPC	80 8 3607	(0, 5579, 1681, 1714, 12, 3337, 140, 586, 1353, 3509, 879, 774, 4117, 850, 876, 5393)
	DPPC 80 8 953	(0, 801, 3826, 5118, 210, 1698, 6065, 684, 5076, 2695, 4119, 5250, 775, 3768, 624, 11)
		ARP	w d 0	d 0 d 1 d 2 A d 0	A d 1	A d 2
		NDP	1536 10 11 12 384 3840 25728
		DPC	5376 12 13 14 768 7680 15360
		DPPC 14208 13 14 15 2304 5760 28032

Table B . 11 :

 B11 Estimated distance spectrum for the best ARP interleavers in AWGN channel with corresponding multiplicities A d and cumulated input weight at d min = d 0 , w d 0 . K = 6144 and R = 4/5.

	A0	A1	A2	A3	A4	A5	A6	A7
	B0	B1	B2	B3	B4	B5	B6	B7
	C0	C1	C2	C3	C4	C5	C6	C7
	D0	D1	D2	D3	D4	D5	D6	D7
	E0	E1	E2	E3	E4	E5	E6	E7

Nous avons tout d'abord présenté les prérequis nécessaires sur les techniques de codage canal et d'entrelacement étudiés dans le cadre de cette thèse.Ensuite, nous avons proposé une nouvelle méthode de construction d'entrelaceurs pour les TCs. Celle-ci est basée sur l'optimisation conjointe du motif de poinçonnage et de la fonction d'entrelacement. Nous avons montré que des gains significatifs en convergence et en performance asymptotique peuvent être atteints par l'inclusion des différentes contraintes de poinçonnage dans la construction de l'entrelaceur. En outre, la méthode proposée permet l'introduction des contraintes de poinçonnage, ainsi que la validation d'autres critères de design, comme le span et le girth, lors de la construction de l'entrelaceur. La génération d'entrelaceurs ARP validant les différents critères de construction se trouve considérablement simplifiée en comparaison avec des méthodes précédentes, car l'approche graphique proposée limite considérablement l'espace de recherche pour les différents paramètres de l'entrelaceur.Dans la troisième partie de l'étude nous avons introduit une nouvelle structure de précodage. Il a été montré que des améliorations en termes de performance asymptotique peuvent être obtenues par le PTC hybride proposé, en comparaison avec un TC classique sans poinçonnage de bits de données. D'autre part, nous avons montré que les échantillons d'information extrinsèque à la sortie du précodeur ne peuvent pas être générés à partir d'un même processus gaussien et par conséquent, une analyse par EXIT chart classique n'est plus adaptée à la prédiction du comporte-

E b is the transmitted energy per information bit and N 0 is the one-side noise power spectral density.

Select the best candidate vectors for SF:The group of candidate vectors for SF are analyzed in the complete OFDM frame, using the best time component interleaver obtained in the 2RI design for the time axis. A first

Table B.7: Best candidates for ARP interleaver with the different puncturing constraints for R = 4/5 and K = 1504.

Algorithm 1 Selection of the shift values for the ARP interleaver candidates

1. Initialization : K, puncturing mask, S min and g goals, C candidate values for P , and Q ← N . 2. for j := 0 to C -1 do

3.

CurrentLayer ← 0, Stay ← 1, f lag ← 0. l := CurrentLayer.

8.

Select a value for T l at random from its possible values fulfilling puncturing constraints.

9.

if there are no more possible values for T l then 10. f lag := 2. f lag := 1.

13.

end if 14. case 1:

15.

Select a value for B l at random from its possible values. [START_REF] Crozier | Rate-compatible turbo codes designed with puncture-constrained DRP interleavers[END_REF].

if there are no more possible values for B l then 17. f lag := 2. f lag := 3.

20.

end if 21. case 2:

22.

CurrentLayer := CurrentLayer -1.

23.

if CurrentLayer 0 then 24. Stay := 0. f lag := 0.

27.

end if 28. case 3:

29.

Obtain S(l) by (2.46) and the interleaved addresses from (1.21) with P := P (j), evaluate S min (1.13) and g. 30. if S min and g goals are met then 31. Save the value of S(l).

32.

if CurrentLayer < Q -1 then 33. CurrentLayer := CurrentLayer + 1.

34.

f lag := 0. A valid ARP interleaver candidate is found: Stay := 0.

37.

end if 38. else 39. f lag := 1.

40.

end if 41. end switch 42. end while 43. end for Chapter 3 Exploring precoding techniques for turbo codes A mong the various techniques to improve TC performance, it was shown that the prefixing of a rate-1 accumulator to a turbo encoder allows improving its error correction performance without altering its coding rate [START_REF] Tong | Precoded turbo code within 0.1 dB of Shannon limit[END_REF]. In this chapter, we study the application of this precoding technique to improve the performance of the 8-state TC of the LTE standard [START_REF] Etsi | LTE Envolved Universal Terrestrial Radio Access(E-UTRA): Multiplexing and channel coding[END_REF]. Furthermore, a new precoding structure is proposed allowing asymptotic TC performance improvements.

This chapter is organized as follows: in Section 3.1, the reference Precoded Turbo Code (PTC), introduced in Section 1.1.2, is analyzed. A suitable optimization tool for the selection of the precoding ratio is then proposed, based on the extrinsic information exchange between the constituent codes of the TC. Next, two new precoding structures, hybrid and composite, are introduced and optimized, leading to the final selection of a suitable precoding structure for TCs. Afterwards, Section 3.2 explores possible improvements for the selected precoding structure: the effects of the precoding pattern and of the constituent code of the precoder on the error rate performance are studied. Then, some design criteria for PTC interleavers are identified in Section 3.3. A performance example of the proposed precoding structure is given and compared to LTE performance in Section 3.4. Finally, Section 3.5 concludes the chapter.

CHAPTER 4. IMPROVING CHANNEL INTERLEAVERS

selection is carried out by applying the frequency span criterion. Then, the selected vector is the one providing the lowest MI distribution variance.

Application of interleaver design guidelines and further analysis

An application example is developed for each interleaver family using the parameters listed in Table 4.1. Then, the interaction between the channel interleaver and the BI is studied and an optimized BI is proposed. Finally, a system latency and complexity analysis is performed.

Application of guidelines to design channel interleavers for DVB-T2

We have applied the previous guidelines to design RI, 2RI, ARP and 2ARP interleavers, for the frame parameters of DVB-T2 listed in Table 4.1.

For the RI permutation law, all the admissible values for P t are represented in Fig. 4.11. In practice, only the values of P t allowing the highest minimum span, i.e. 24, are selected as candidates. The candidate values for P f are selected in the same way for NF =1705 carriers. Finally, only the combinations of P t and P f with the best time and frequency span properties and the lowest MI distribution variances in the TU6 channel are chosen. The four best candidates for P are given in Table 4.2 for NT =357 and NF =1705.

Three parameters have to be obtained to define the permutation law of the 2RI: P f , P t and S T . First, the best candidate value for P f is identified as the one providing the maximum value of minimum frequency span with the lowest multiplicity. For the current OFDM configuration, 293 turns out to be the best value for P f . Second, given that the time span properties depend not only on the value of P t but also on

Appendix A

Application examples of the equivalent expressions of DRP and QPP interleavers in the form of the ARP interleaver T he obtained equivalent expressions of DRP and QPP interleavers in the form of the ARP interleaver are applied in some examples.

Equivalent ARP interleavers for the DRP Case

In the first application example, a DRP interleaver of length 784 is considered. A length of 7 is selected for the dither vectors. Two different configurations of these vectors are analyzed and listed in Table A.1. The disorder degree Q of the equivalent ARP interleavers is set to the dither vector size value. The regular permutation period P of each ARP interleaver is the same as the one used in the original DRP version. Then, the 7 shifts of the equivalent ARP interleavers are obtained from (2.17) and listed in Table A.2.

In the second example, a DRP of length 6144 is analyzed. Two different dither vector lengths, 2 and 3, as well as two different configurations are considered and listed in Table A.1. Then, the disorder degree of the equivalent ARP is set to 6 that corresponds to the least common multiple of 2 and 3. The regular permutation period is again selected as the one used in the DRP interleaver and the 6 shifts of the equivalent ARP interleavers are given by (2.17). The corresponding shift values are listed in Table A

Equivalent ARP interleavers for the QPP Case

In this case, two instances of the QPP interleaver defined in the LTE standard [START_REF] Etsi | LTE Envolved Universal Terrestrial Radio Access(E-UTRA): Multiplexing and channel coding[END_REF] are detailed. Let us first take the interleaver of length 216 for which f 2 = 36. The interleaver length and f 2 are factorized in their prime factors as: 216 = 2 3 3 3 and 36 = 2 2 3 2 , respectively. Therefore, the values for u, leading to valid values for Q, spectively. Thus, according to (2.31), the valid values for u are factorized as: u = 2 α u,1 53 α u,2 3 α u,3 . According to (2.41), the valid range for α u,1 is 0 ≤ α u,1 ≤ 2. Then, the valid range for α u,2 , 0 ≤ α u,2 ≤ 1, is obtained from (2.42). Finally, α u,3 = 2 as obtained from (2.35) Given that the CRSC distance spectrum does not depend on K, the puncturing masks obtained for K = 1504 and listed in Tables 2.2 and 2.3 are also considered for K = 6144. Then, the TC convergence behavior with the different puncturing masks is analyzed in the TC structure. The best TC convergence thresholds are achieved with the puncturing masks with DPR values equal to 2/8 and 2/16. The only difference lies in the maximum point achieved in the curves, which is higher in this case due to the increase on data sequence length compared to the modified EXIT charts in Fig. 2.7.

The puncturing mask allowing the best tradeoff between TC convergence threshold and error floor is determined by analyzing the TC error rate performance with the best puncturing masks identified in the previous analysis (see Fig. B.2). According to the obtained TC error rate performance the conclusions remain the same as those made for K = 1504. The best tradeoff between TC convergence threshold and error floor performance is achieved by the puncturing mask with DPR = 2/8. Finally, the parity puncturing constraint for the selected mask DPR = 2/8 is the same as the one obtained for K = 1504 for which the corresponding distance spectra analysis is given in Table 2.4.

Puncture-constrained ARP interleaver design

First, the strategy introduced in Section 2.5.2 led to select a S min goal of 65% of the S min theoretical upper bound and a g goal of 8. Then, the best candidates for the [START_REF] Crozier | Rate-compatible turbo codes designed with puncture-constrained DRP interleavers[END_REF] Afterwards, the TC convergence performance with the different puncturing mask is analyzed. ARP shows the TC error rate performance with the puncturing masks with DPR 2/8 and 2/16. The best tradeoff between TC convergence threshold and error floor performance is obtained with the puncturing mask of DPR = 2/16. Thus, similar conclusions are observed for both data sequence lengths 1504 and 6144. Finally, the parity puncturing constraint for the selected mask DPR = 2/16 is the same as the one obtained for K = 1504 for which the distance spectra analysis is given in Table B

Puncture-constrained ARP interleaver design

The strategy introduced in Section 2.5. T he first step of the proposed new BI involves applying the parity interleaver included in DVB-T2. Then, coded bits are written column-wise in the BI matrix. Thus, correlated coded bits (i.e., belonging to the same LDPC parity-check node) are placed in the same row of the BI memory block, as shown in

List of publications

Journal papers