Brevet FR3064436A1 — publié le 20180928

Procédé de codage et codeur à code polaire Domaine de l'invention Le domaine de l'invention est celui du codage d'un message numérique d'entrée mettant en oeuvre un code polaire. L'invention se rapporte plus particulièrement aux techniques de codage d'un message numérique source délivrant des codes polaires codant les symboles d'information du message et des symboles dits gelés, destiné(s) à être transmis sur un canal de transmission (par exemple aérien ou filaire de type hertzien, optique ou électrique), ou stocké(s) dans un support matériel. L'invention trouve notamment des applications dans les domaines suivants : - la transmission d'information par télécommunications filaires électriques, comme dans les normes ADSL, ou optiques, sur fibres optiques ou en espace libre ; - la transmission d'information dans les communications radios spatiales et terrestres sans fil (« wireless » en anglais), comme dans les systèmes de télévision numérique TNT, de radio numérique DAB, de téléphonie GSM ou UMTS, de réseau radio WiFi, et aussi dans les futurs systèmes de télécommunications, comme les futures normes pour des applications de télévision, de diffusion radio, de voix, de vidéo et de données (DVB, LTE, 4G, 5G, etc), ou entre véhicules, l'Internet des objets ou machines communicants « IOT : Internet Of Things », - la compression et la décompression de source d'informations par exemple de type vidéo ; - la génération et la détection de séquences dites d'embrouillage (« scrambling » en anglais) dans les systèmes CDMA ; - le stockage d'informations dans des mémoires de masse magnétiques, optiques, mécaniques ou électriques pour constituer des disques durs, ou des mémoires vives d'ordinateurs, ou des clés mémoire à interface de type USB... ; - la correction d'informations lors des calculs dans un circuit intégré d'un microprocesseur ou dans un ordinateur ; - la reconnaissance de formes : images, sons, etc ; - la robotique commandée par une intelligence artificielle à base de réseaux de neurone. Un code correcteur d'erreur est classiquement défini par : - une longueur N, correspondant à la séquence en sortie du codeur (ou mot de code de longueur Nn), - un nombre K de bits ou de données d'information utiles, correspondant aux données en entrée du codeur, encore appelées symboles d'information. Le rendement est alors défini par R= KIN. Art antérieur 3064436 2 Les codes polaires ont été introduits par Arikan 11]. Le code polaire est un code en bloc linéaire avec un code mère de longueur N qui est une puissance de deux : N = 2'. Le code polaire est basé sur une unité de polarisation minimale dont la structure est illustrée par la figure 1. Cette unité a deux branches avec deux entrées et deux sorties. Les deux 5 entrées des deux branches sont polarisées par un noeud qui effectue une addition modulo deux. La sortie du noeud correspond à la première sortie. La seconde sortie est identique à la seconde entrée. Le procédé de codage prend un bloc de K symboles d'information xi i E {1, ..., K} en entrée et complète le bloc avec des bits connus généralement mis à zéro et appelés bits gelés (frozen bits). En considérant que le canal de transmission est de type BEC (Binary Erasure Channel) 10 alors les deux sorties vont emprunter deux chemins différents, un pour la bonne polarisation et un pour la mauvaise polarisation. Dit autrement, en considérant une équiprobabilité d'effacement p = 0,5 avant polarisation entre les deux branches alors après polarisation la sortie bien polarisée va connaître une probabilité d'effacement de seulement pi = 0,25 et la sortie mal polarisée va connaître une plus forte probabilité d'effacement de p2 = 0,75 W. Si on augmente le nombre de 15 branches alors des branches vont être des branches à capacité pleine (full capacity) i.e. à transmission sans erreur alors que d'autres branches vont devenir des branches à capacité nulle (zero capacity) i.e. totalement bruitée. Le procédé de codage à code polaire mappe les bits d'information du bloc d'entrée uniquement sur les branches bien polarisées, jamais sur les branches mal polarisées, et mappe les bits gelés sur les branches mal polarisées. 20 Une matrice génératrice du code polaire est GN et un procédé d'encodage du code polaire consiste à calculer : --- YNI = [x1, ---XN,1 X GN avec GN = 0 1] oi ... L1 avec 0 le produit de Kronecker et N = 2'. 11 ri 01 est la matrice carrée polaire asymétrique de taille deux. L1 1J 25 La matrice génératrice GN est donc le résultat de n - 1 produits de Kronecker de la matrice carrée polaire asymétrique de taille deux. Pour un bloc de longueur N = 22 = 4, la matrice génératrice est : 1 0 0 0 G4 = [11 01 [1 01 [1 1 0 0 11 1 0 1 0 - 1 1 1 1 La structure de treillis associé est représentée à la figure 2. Les entrées sont notées 30 e1, e2, e3, e4 et les sorties sont notées s1, s2, S3, s4. La relation entre une sortie et les entrées est déterminée en remontant la branche depuis la sortie. Ainsi, pour la première sortie en remontant la branche on détermine que : si = e1ee2ee3ee4. 3064436 3 Et de même pour les sorties suivantes, on détermine - s2 = e2EDe4 s3 = e3EDe4 S4 = e4 5 Ce qui correspond bien aux relations obtenues avec la multiplication du vecteur ligne des entrées avec la matrice génératrice G4 : 1 0 0 0 1 0 0 (el, e2, e3, e4) x [11 0 1 0 = (s1, s2, s3, s4) 1 1 1 1 Pour un bloc de longueur N = 23 = 8, la matrice génératrice est : 1 0 0 0 0 0 0 0- 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 G8 = [11 011 0 [11 011 0 [11 01 = 1 1 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 3 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1- 10 La structure de treillis associé est représentée à la figure 3. Les relations entre les sorties et les entrées sont déterminées en remontant la branche depuis chaque sortie. Ainsi : s1 = e1ee2EDe3ee4ee5ee6ee7ee8 s2 = e2EDe4EDe6EDe8 s3 = e3EDe4EDe7EDe8 15 s4 = e4EDe8 ss = e5ee6ee7ee8 s6 = e6EDe8 57 = e7EDe8 s8 = e8 20 Ce qui correspond bien aux relations obtenues avec la multiplication du vecteur ligne des entrées avec la matrice génératrice G8 : 1 0 0 0 0 0 0 0- 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1- (e1, e2, e3, e4, e5, e6, e7, e8) x = (51, S2, S3, S4, S5, S6, S7, S8) Lorsqu'un rendement R est spécifié, la longueur M du bloc codé à transmettre est telle que : M = Ceil(K/R) avec Ceil(Nombre) la fonction qui fournit le plus petit entier supérieur ou 25 égal à la valeur Nombre et K le nombre de bits d'information du bloc à coder. Par exemple, si K = 32 et R = 1/3 alors M = 96 et par conséquent le code polaire mère a pour longueur N = 3064436 4 2 Ceil(log2 M) soit N = 128 pour l'exemple considéré. Par conséquent le code polaire mère de longueur N = 128 doit être poinçonné de 32 bits pour que le bloc de données codées à transmettre ait pour longueur M = 96. Le poinçonnage est une opération délicate qui peut dégrader les performances si elle n'est pas effectuée de manière optimale. En outre, à la réception, le décodeur 5 du code polaire est basé sur une succession d'annulations avec un algorithme de décodage de liste (SCL algorithm) de type série. Un tel procédé de codage risque donc d'être un handicap pour des services qui requièrent une forte fiabilité ou une faible latence telles que les communications dites URLLC (Ultra Reliable Low latency communications).En effet, la latence de décodage est déterminée par la longueur du 10 code polaire mère. Il faut donc que la longueur du code polaire mère soit la plus proche possible de la longueur du bloc codé à transmettre pour diminuer la latence de décodage. Exposé de l'invention L'invention propose un procédé de codage à code polaire à matrice génératrice carrée résultant d'un produit de Kronecker de matrices de base carrés comprenant : 15 - détermination d'une matrice génératrice carrée de taille N telle que N se décompose en au moins une puissance n1 d'un nombre premier impair pl telle que cette matrice génératrice est le résultat d'au moins n1 - 1 produits de Kronecker d'une matrice de base carrée bidiagonales comprenant uniquement des un sur la diagonale et sur une seconde diagonale en- dessous de la diagonale, n1 1. 20 Les données d'entrée à transmettre sont prises par paquets qui sont complétés avec des bits dits gelés généralement pris égaux à zéro pour former des vecteurs ligne ou blocs de longueur N. Un code polaire (polar code) est généré en multipliant un vecteur ligne de longueur N avec la matrice génératrice carrée de taille N. Cette matrice génératrice est construite en effectuant des produits de Kronecker de matrices de base carrées. 25 Selon l'invention, la matrice génératrice carrée est le résultat de n1 - 1 produits de Kronecker d'au moins une matrice de base carrée de taille égale au premier nombre impair pi. Si N = pl alors n1 = 1 ; la matrice génératrice est identique à cette matrice de base carrée de taille pi. Cette matrice de base carrée de taille pi comprend uniquement des un sur deux diagonales, la vraie diagonale et une seconde diagonale en-dessous de la vraie diagonale. Pour chaque autre 30 nombre p2 premier impair intervenant dans la décomposition du nombre N, il est défini une matrice de base carrée de taille p2 construite de manière similaire à la matrice de base carrée de taille pi. La matrice génératrice est alors le résultat de produits de Kronecker des matrices de base carrées de taille égale respectivement aux différents nombres impairs premiers pi, p2, etc. Les matrices de base des codes polaires conventionnels sont toutes identiques à une même 35 matrice carrée polaire asymétrique de taille deux ; le code mère d'un code polaire conventionnel a une longueur N qui est une puissance de deux. 3064436 5 Compte tenu que selon l'invention la taille N de la matrice génératrice peut se décomposer en au moins un nombre premier impair, ce choix de N permet d'obtenir des longueurs de codes polaires intermédiaires entre les longueurs de codes polaires obtenues selon l'art antérieur avec un code mère en puissance de deux uniquement. 5 Ainsi, le procédé proposé permet d'éviter ou tout au moins de réduire le nombre de bits à poinçonner pour certaines valeurs données de rendement et par conséquent de diminuer la latence de décodage pour ces valeurs et de limiter le risque de dégradation des performances suite à un poinçonnage. Un mode avec poinçonnage permet d'affiner la granularité entre les rendements pouvant être obtenus avant poinçonnage. Si N est la longueur du code mère et si M est la longueur 10 après poinçonnage alors la granularité est N-M. Le treillis d'un code polaire est obtenu à partir de la matrice génératrice du code et en utilisant des unités de polarisation. La matrice de base carrée de taille pi selon l'invention correspond à une unité de polarisation de base à pi entrées et pi sorties telle que chaque branche est polarisée par un noeud de 15 type C à deux entrées et une sortie ou de type V a une entrée et une sortie et telle qu'une même branche ne peut pas être polarisée par plusieurs noeuds d'un même type. La polarisation d'une première et d'une seconde branches par un noeud de type C signifie que les deux entrées du noeud sont alimentées respectivement par les deux branches et que la sortie du noeud se fait sur la première branche et qu'elle fournit la somme modulo deux des entrées du noeud. Un noeud de type 20 V ne peut polariser qu'une seule branche ; il n'a qu'une entrée. La polarisation d'une branche par un noeud de type V signifie que la sortie du noeud est identique à l'entrée du noeud. La matrice carrée polaire asymétrique de taille deux selon l'art antérieur comprend un seul zéro. Elle correspond à un treillis à deux entrées et deux sorties tel que la première sortie est la somme modulo deux des deux entrées et la seconde sortie est identique à la seconde entrée. Dit 25 autrement, la première branche est polarisée par un noeud de type C à deux entrées et une sortie et la seconde branche est polarisée par un noeud de type V a une entrée et une sortie. Selon un mode de réalisation particulier de l'invention, N est le produit d'au moins une puissance n de deux et d'au moins la puissance ni du nombre premier impair pi et la matrice génératrice est le résultat d'au moins n produits de Kronecker d'une matrice de base carrée polaire 30 asymétrique de taille deux et des n1 produits de Kronecker de la matrice de base carrée bi- diagonales comprenant uniquement des un sur la diagonale et sur une seconde diagonale en-dessous de la diagonale, n > 1, ni > 1. Ainsi, selon ce mode de réalisation de l'invention, la matrice génératrice carrée est le résultat de n - 1 produits de Kronecker de la matrice carrée polaire asymétrique de taille deux et 35 de ni - 1 produits de Kronecker d'au moins une autre matrice de base carrée de taille égale au premier nombre premier impair pi. La matrice génératrice peut donc être le résultat de produits de Kronecker de la matrice carrée polaire asymétrique de taille deux et d'autres matrices de base 3064436 6 canées de taille égale respectivement à différents nombres impairs premiers pi, p2, etc, chacune étant construite de manière similaire à la matrice de base canée de taille pi. Ce mode permet d'affiner encore la granularité entre les rendements pouvant être obtenus avant poinçonnage. Selon un mode de réalisation particulier de l'invention, pi = 3 et la matrice de base canée 5 bi-diagonales correspondante est la suivante : 0 0 [1 1 0 . 1 0 1 1 Selon un mode de réalisation particulier de l'invention, le code polaire étant de longueur N bits, le procédé comprend en outre : - adaptation du rendement en poinçonnant P bits au code polaire de longueur N pour 10 obtenir un vecteur de données codées de longueur M tel que N = M + P, P > 0, M > 1. L'invention a en outre pour objet un codeur d'un code polaire à matrice génératrice carrée résultant d'un produit de Kronecker de matrices de base canés comprenant : - une mémoire de taille N pour mémoriser des données d'entrée di et des bits dits gelés, 15 - un calculateur pour déterminer la matrice génératrice canée de taille N telle que N se décompose en au moins une puissance ni d'un nombre premier impair pi et telle que cette matrice génératrice est le résultat d'au moins ni - 1 produits de Kronecker d'une matrice de base canée bi-diagonales comprenant uniquement des un sur la diagonale et sur une seconde diagonale en-dessous de la diagonale, ni 1 et pour générer en sortie le code polaire en multipliant les 20 sorties de la mémoire avec la matrice génératrice. Un tel codeur peut bien sûr comporter les différentes caractéristiques relatives au procédé de codage selon l'invention, qui peuvent être combinées ou prises isolément. Ainsi, les caractéristiques et avantages de ce codeur sont les mêmes que ceux du procédé de codage et ne sont donc pas détaillés plus amplement. 25 Selon un mode de réalisation, le codeur selon l'invention comprend en outre : - un dispositif de poinçonnage pour poinçonner P bits au code polaire de longueur N pour obtenir un vecteur de données codées de longueur M tel que N = M + P, P > 0, M > 1. Un codeur selon l'invention peut être implémenté sous la forme d'un circuit intégré numérique ou analogique, ou dans un composant électronique de type microprocesseur. Ainsi, 30 l'algorithme de codage selon l'invention peut être mis en oeuvre de diverses manières, notamment sous forme câblée ou sous forme logicielle. L'invention propose ainsi une nouvelle technique de codage de symboles source pour obtenir simplement des codes avec une variation plus fine du rendement que les codes polaires connus. 35 Dans encore un autre mode de réalisation, l'invention concerne un ou plusieurs 3064436 7 programmes d'ordinateur comportant des instructions pour la mise en oeuvre d'un procédé de codage tels que décrits précédemment, lorsque le ou les programmes sont exécutés par un processeur d'un codeur. De tels programmes peuvent être stockés sur un support d'information. Liste des figures 5 D'autres caractéristiques et avantages de l'invention apparaîtront plus clairement à la lecture de la description suivante de modes de réalisation particuliers, donnés à titre de simples exemples illustratifs et non limitatifs, et des dessins annexés, parmi lesquels : la figure 1, précédemment décrite en relation avec un procédé de codage d'un code polaire selon l'art antérieur, représente l'unité de polarisation de base correspondant à un facteur 10 deux, la figure 2, précédemment décrite, illustre la structure du treillis lorsque N = 4 selon l'art antérieur, la figure 3 précédemment décrite, illustre la structure du treillis lorsque N = 8 selon l'art antérieur, 15 - la figure 4 est une représentation équivalente selon un nouveau formalisme de l'unité de polarisation de base correspondant à un facteur deux, la figure 5 représente l'unité de polarisation de base correspondant à un facteur trois selon l'invention, la figure 6 représente l'unité de polarisation de base correspondant à un facteur cinq selon 20 l'invention, la figure 7 représente le treillis d'un procédé de codage selon l'invention pour N = 6, la figure 8 représente le treillis d'un procédé de codage selon l'invention pour N = 30, la figure 9 est un schéma d'un mode de réalisation d'un codeur selon l'invention. Description de modes de réalisation de l'invention 25 L'organisme de normalisation 3GPP au sein duquel interviennent les travaux pour les futures générations de téléphonie mobile (LTE adv, 5G, etc) requiert des des rendements R de code faibles. Par exemple, il est envisagé des rendements de R = 1/12, 1/6, 1/3 pour les communications URLLC. Les rendements 1/12 et 1/3 ne peuvent pas correspondre à un rapport 30 K/R qui soit une puissance de deux. Le codage à code polaire selon l'art antérieur implique alors inévitablement un poinçonnage ; la contrainte d'une longueur du code mère égale à une puissance de deux n'est pas flexible, certaines combinaisons (K, R) ne peuvent pas être obtenues et nécessitent un poinçonnage. De manière très avantageuse par rapport à l'état de l'art, l'invention permet d'obtenir une 35 granularité qui peut être plus fine en considérant des valeurs de N dont la décomposition en nombres premier comprend au moins une puissance n d'un nombre premier impair pl. Selon 3064436 8 l'invention, la longueur du code polaire mère est de la forme N = 2n X FlpieA pin` avec n et ni des entiers naturels, ni > 1, n > 0, pi un nombre premier impair, A l'ensemble des entiers premiers impairs de la décomposition en nombre premier de N. Pour des raisons de simplicité, l'ensemble A considéré peut être limité à {3, 5} ce qui conduit aux différentes possibilités 5 suivantes : N = 2n X 3n1 X 5n2. Par exemple pour une combinaison donnée (K, R), le procédé de codage peut rechercher parmi toutes les combinaisons de (n, n1, n2 ) i.e. parmi toutes les valeurs de N = 2n 3n1 5n2 celle qui est la plus petite et qui est plus grande que KIR. En reprenant l'exemple de K = 32 et de R = 1/3, le procédé de codage selon l'invention 10 permet ainsi d'obtenir directement un code polaire de longueur N = 96 en choisissant la décomposition : N = 25 x 31. Le procédé selon l'invention permet ainsi d'éviter tout poinçonnage. Le treillis de codage est construit avec des unités de polarisation de base associées respectivement aux nombres premier de la décomposition de N. L'unité de polarisation de base associée au nombre premier deux est identique à celle de l'art antérieur représentée à la figure 1. 15 Selon l'invention, il est défini deux types de noeud de polarisation : un type C et un type V. La polarisation d'une première et d'une seconde branches par un noeud de type C signifie que les deux entrées du noeud sont alimentées respectivement par les deux branches et que la sortie du noeud se fait sur la première branche et qu'elle fournit la somme modulo deux des entrées du noeud. Un noeud de type V ne peut polariser qu'une seule branche ; il n'a qu'une entrée. La 20 polarisation d'une branche par un noeud de type V signifie que la sortie du noeud est identique à l'entrée du noeud. Selon cette convention, l'unité de polarisation de base associée au nombre premier deux est telle que la première branche est polarisée par un noeud de type C à deux entrées et une sortie et la seconde branche est polarisée par un noeud de type V a une entrée et une sortie, cette représentation équivalente est illustrée par la figure 4. 25 Le treillis de codage selon l'invention est construit à partir d'unités de polarisation de base associées chacune à un nombre premier de la décomposition de N en facteurs premier. Chaque unité de polarisation de base est telle que : toutes les branches participent à la polarisation, un noeud de type C et un noeud de type V n'apparaissent qu'au plus une seule fois par 30 branche. Ainsi, selon l'invention l'unité de polarisation de base associée au facteur premier impair trois est illustrée par la figure 5. Les relations entre les sorties et les entrées sont déterminées en remontant la branche depuis chaque sortie. Ainsi : si = eiee2 35 s2 = e2EDe3 s3 = e3 3064436 9 La matrice correspondante est la suivante : 0 0 [1 1 0 . Cette matrice de base carrée 3x3 comporte une diagonale de un et une seconde 1 0 1 1 diagonale de un en-dessous de la diagonale principale (vrai diagonale). Ce qui correspond bien aux relations obtenues avec la multiplication du vecteur ligne des entrées avec cette matrice 5 génératrice : (el, e2, e3) x [1 0 0 = (s1, s2, s3) 1 1 0 0 1 1 Ainsi, selon 1 invention, l'unité de polarisation de base associée au facteur premier impair cinq est illustrée par la figure 6. Les relations entre les sorties et les entrées sont déterminées en remontant la branche depuis chaque sortie. Ainsi : 10 si = e1ee2 s2 = e2EDe3 s3 = e3EDe4 54 = e4EDe5 55 = e6 15 La matrice correspondante est la suivante : 0 0 0 0 1 1 0 0 0 il 1 1 0 0 . Cette matrice de base carrée 5x5 comporte une diagonale de un et une 0 0 0 1 1 0 0 0 0 1 1 seconde diagonale de un en-dessous de la diagonale principale (vrai diagonale). Ce qui correspond bien aux relations obtenues avec la multiplication du vecteur ligne des entrées avec cette matrice génératrice : 1 0 0 0 0 1 1 0 0 0 20 (el, e2, e3, e4, e5) x 0 1 1 0 0 = (si, s2, s3, s4, s5) 0 0 1 1 0 0 0 0 1 1 Le procédé de codage à code polaire selon l'invention qui comprend la détermination de la matrice génératrice carrée de taille N = 2n x pin1 x ... consiste à calculer les produits de Kronecker des matrices de base carrées correspondant aux facteurs de la décomposition en nombres premiers de N. Ces matrices de base carrées sont déterminées selon la convention 25 précédemment définie selon l'invention. Par exemple, pour une longueur du code polaire mère N = 6, la décomposition en facteurs premiers de N donne : N = 3 x 2. La matrice génératrice G6 est déterminée en calculant les produits de Kronecker des matrices de base carrées correspondant aux facteurs premiers pris du plus grand au plus petit : 3064436 [11 01 1 00e 10 0 1 1 0 1 1 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 1 1 0- 0 0 0 0 1- = G6 0 1 [1 0-1 -1 1 0 1 1 0 L1 1] La structure du treillis correspondant est illustrée par la figure 7. Les relations entre les sorties et les entrées sont déterminées en remontant la branche depuis chaque sortie. Ainsi : si = e1ee2ee4ees 5 s2 = e2Epe3EpesEpe6 s3 = e3EDe6 54 = e4ees ss = esee6 s6 = e6 10 Ce qui correspond bien aux relations obtenues avec la multiplication du vecteur ligne des entrées avec la matrice génératrice G6 : 1 0 0 0 0 0- 1 1 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 1 1 0 1 1 0 -0 1 1 0 1 1- Par exemple, pour une longueur du code polaire mère N = 30, la décomposition en facteurs premiers de N donne : N= 5 x 3 x 2. 15 La matrice génératrice G30 est déterminée en calculant les produits de Kronecker des matrices de base carrées correspondant aux facteurs premiers pris du plus grand au plus petit : 1 0 0 0 0 G30 = 0 0 1 1 0 0 1 1 1 1 0 0 ED 1 1 0 ED [ 1 1 1 1 0 0 0 1 0 0 0 0 0 0 1 1 (e1, e2, e3, e4, e5, e6) x = (si, s2, s3, s4, ss, s6) 0] 3064436 11 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 La structure du treillis correspondant est illustrée par la figure 8. Les relations entre les sorties et les entrées sont déterminées en remontant la branche depuis chaque sortie. Ainsi : 5 s1 = e1ee2EDe6EDe7EDe16EDe17EDe21ee22 s2 = e2EDe3EDe7EDe8EBe17EBe18EDe22EDe23 s3 = e3EDe4EDe8EDe9EBe18EBe19EDe23EDe24 s4 = e4EDesee9EBe10EBe19ee20ee24EDe25 55 = esee10ee20EDe25 s6 = e6EDe7ee11ee12eenee22EDe26EDe27 S7 = e7EDe8EBe12EDe13ee22EDe23EDe27EDe28 s8 = e8EDe9EDe13ee14EDe23EDe24EDe28EDe29 59 = e9EDe1oee14EDe1see24EDe25EDe29EDe30 S10 = e10ee15ee25ee30 S11 = e11ee12ee26ee27 S12 = e12 een ee27ee28 S13 = e13ee14ee28ee29 S14 = e14ee15ee29ee30 S15 = e1see30 S16 = e16ee17eenee22 S17 = e17ee18ee22ee23 S18 = e18ee19ee23ee24 10 15 20 3064436 12 Si9 = e19ee20EDe24EDe25 s20 = e20ee25 S21 = ez eez eez6ee27 s22 = e22 ee23EDe27EDe28 5 s23 = e23EDe24EDe28EDe29 s24 = e24 ee2s ee29ee30 _ 25 _ 30 S25 = e elDe s26 = e26 /96'27 S27 = 27 e (De _ _ 28 10 s28 = e28ee29 S29 = e2919e30 S30 = e30 Ce qui correspond bien aux relations obtenues avec la multiplication du vecteur ligne des entrées avec la matrice génératrice G30 : 15 (e1, e2, e3, e4, e5, e6) x G30 = (S1, S2, S3, S4, S5, S6) La figure 9 est un schéma d'un mode de réalisation selon l'invention d'un codeur à code polaire à matrice génératrice carrée résultant d'un produit de Kronecker de matrices de base carrés. Le codeur COD comprend : une mémoire MEM de taille N pour mémoriser des données d'entrée di et des bits dits 20 gelés, un calculateur 1.1.13 pour déterminer une matrice génératrice carrée de taille N (N = 2n x pin1 x ) telle que N se décompose en au moins une puissance n1 d'un nombre premier impair pl et telle que la matrice génératrice est le résultat d'au moins n1 - 1 produits de Kronecker d'une matrice de base carrée bi-diagonales comprenant 25 uniquement des un sur la diagonale et sur une seconde diagonale en-dessous de la diagonale, n1 1 et pour générer en sortie le code polaire cod_m, dit code mère, en multipliant les sorties de la mémoire avec la matrice génératrice, un dispositif PUN de poinçonnage pour poinçonner P bits au code polaire de longueur N pour obtenir un vecteur de données codées cod_p de longueur M tel que N = M + 30 P, P > 0, M > 1. Références : [1] E. Arikan, "Channel polarization: a method for constructing capacity achieving codes for symmetric binary-input memoryless channels", IEEE TIT, 2009 35 REVENDICATIONS1. Procédé de codage à code polaire à matrice génératrice carrée résultant d'un produit de Kronecker de matrices de base carrés comprenant : - détermination d'une matrice génératrice carrée de taille N telle que N se décompose en au moins une puissance n1 d'un nombre premier impair pl telle que la matrice génératrice est le résultat d'au moins n1 - 1 produits de Kronecker d'une matrice de base carrée bi-diagonales comprenant uniquement des un sur la diagonale et sur une seconde diagonale en-dessous de la diagonale, n1 > 1. 2. Procédé de codage selon la revendication 1 selon lequel N est le produit d'au moins une puissance n de deux et d'au moins la puissance n1 du nombre premier impair pl et selon lequel la matrice génératrice est le résultat d' au moins n produits de Kronecker d'une matrice de base carrée polaire asymétrique de taille deux et des n1 produits de Kronecker de la matrice de base carrée bi-diagonales comprenant uniquement des un sur la diagonale et sur une seconde diagonale en-dessous de la diagonale, n > 1, n1 > 1. 3. Procédé de codage selon l'une des revendications 1 et 2 selon lequel pi = 3 et la matrice de base carrée bi-diagonales correspondante est la suivante : [1 0 0 1 1 0. 0 1 1 4. Procédé de codage selon l'une des revendications 1 à 3 selon lequel, le code polaire étant de longueur N bits, le procédé comprend en outre : adaptation du rendement en poinçonnant P bits au code polaire de longueur N pour obtenir un vecteur de données codées de longueur M tel que N = M + P, P 0, M >1. 5. Codeur (COD) d'un code polaire à matrice génératrice carrée résultant d'un produit de Kronecker de matrices de base carrés comprenant : une mémoire (MEM) de taille N pour mémoriser des données d'entrée (di) et des bits dits gelés, un calculateur (e) pour déterminer une matrice génératrice carrée de taille N telle que N se décompose en au moins une puissance n1 d'un nombre premier impair pi et telle que la matrice génératrice est le résultat d' au moins n1 - 1 produits de Kronecker d'une matrice de base carrée bi-diagonales comprenant uniquement des un sur la diagonale et sur une seconde diagonale en-dessous de la diagonale, n1 1 et pour générer en sortie le code polaire (cod_m) en multipliant les sorties de la mémoire avec la matrice génératrice. 6. Codeur (COD) d'un code polaire selon la revendication précédente comprenant en outre : 3064436 14 un dispositif (PUN) de poinçonnage pour poinçonner P bits au code polaire de longueur N pour obtenir un vecteur de données codées (cod_p) de longueur M tel que N = M + P, P > 0, M > 1. 7. Programme d'ordinateur comportant des instructions pour la mise en oeuvre d'un procédé 5 de codage selon l'une quelconque des revendications 1 à 4 lorsque ce programme est exécuté par un codeur à code polaire. 8. Support d'informations comportant des instructions de programme adaptées à la mise en oeuvre d'un procédé de codage selon l'une quelconque des revendications 1 à 4, lorsque ledit programme est chargé et exécuté dans un codeur à code polaire. 10