Radio Data System (RDS) : analyse du canal numérique transmis par les stations radio FM commerciales, introduction aux codes correcteurs d’erreur – Partie 1/2

RDS – Radio Data System – est le mode numérique de communication exploité par les stations FM de la bande commerciale 88–108 MHz pour indiquer à l’utilisateur des informations telles que le nom de la station reçue, du texte libre tel que les informations en cours de diffusion ou un titre de musique, ainsi que l’heure ou la nature du programme diffusé. Nous nous proposons, à partir du signal analogique reçu par un récepteur de télévision numérique terrestre (DVB-T) exploité comme récepteur radiofréquence généraliste, d’analyser les diverses étapes de démodulation et de décodage, pour finalement conclure sur une exploration des méthodes de détection et de correction d’erreurs.

La bande commerciale FM, comprise entre 88 et 108 MHz, est divisée pour allouer une bande de 200 kHz à chaque station (Fig. 1, à gauche). Chaque station redivise chaque tranche du spectre radiofréquence qui lui est allouée en trois sous-segments : le son, avec d’abord la somme des signaux destinés à l’oreille droite et l’oreille gauche, puis si la transmission est en stéréo, la différence entre oreille droite et oreille gauche (afin qu’un récepteur mono puisse recevoir une station stéréo), et finalement un signal numérique – RDS (Radio Data System, Fig. 1 à droite) – comportant des informations telles que le nom de la station (Fig. 2), ou du texte libre tel que le titre d’une émission ou d’un morceau de musique. Un récepteur est informé qu’une émission est en stéréo par la présence d’un pilote – un signal périodique continu – à 19 kHz. La sous-porteuse de la transmission numérique se fait à 57 kHz générée comme trois fois le pilote si l’émetteur est stéréo, hypothèse que nous ne ferons pas au cours de nos traitements dans lesquels nous nous efforcerons de reproduire une copie locale de la sous-porteuse à 57 kHz. La bande passante du signal numérique est de l’ordre de 5 kHz.

Fig. 1 : En haut : la bande de fréquence qui nous intéresse – RDS – se trouve à 57 kHz de la porteuse de chaque station FM : elle est donc accessible par transposition de fréquence, pour ramener le signal numérique en bande de base (autour de la fréquence nulle), après la démodulation FM de la station écoutée. En bas : les divers signaux émis par une station de la bande commerciale FM sont visibles sur le mode waterfall après le démodulateur WBFM. Nous avons changé la fréquence en milieu d’acquisition entre une station stéréo et une station mono, qui toutes deux émettent un signal d’identification RDS.

 

Fig. 2 : Réception de diverses stations FM commerciales, avec affichage du nom de la station tel que transmis par RDS. Noter que Le Mouv’ est parfois perçu comme stéréo, parfois comme mono, sans que cela empêche d’afficher son identifiant.


Un lecteur simplement désireux de lire le contenu des informations numériques ainsi transmises pourra se contenter d’utiliser un composant intégré qui se charge de tout le travail, par exemple chez ST le TDA7330 [1] ou TDA7478 (single chip RDS decoder), voire le récepteur FM intégré RDS5807 de RDA MicroElectronics [2] qui exploite dans la même veine un TEA5764 pour synchroniser un réseau de capteurs, bien que toutes ces références semblent obsolètes et inaccessibles chez les principaux fournisseurs. Ce faisant, nous n’aurons rien appris du mode d’encodage, de la nature des informations transmises, mais surtout de la méthode utilisée pour retrouver des bits corrompus lors de la transmission. Tous ces concepts seront appréhendés lors du décodage logiciel des trames, avec analyse étape par étape de la séquence suivie pour passer d’un signal radiofréquence modulé en fréquence (FM commerciale) à des phrases intelligibles. Comme d’habitude, cette compréhension permettra de mieux appréhender des utilisations malicieuses du protocole ou de le détourner de son usage initial [1][3][4]. Tous les prototypages s’aideront de l’outil d’implémentation de traitement du signal GNURadio [5] pour acquérir le signal, suivi d’une mise en œuvre des algorithmes de décodage sous GNU/Octave [6] en s’efforçant de revenir aux bases, et sans passer par des bibliothèques de haut niveau telles que la communication toolbox [7] qui nous cacheraient la compréhension détaillée du flux de traitement.

Le décodage d’un flux de communication numérique sur porteuse radiofréquence nécessite toujours de résoudre les problèmes de synchronisation d’oscillateurs distants, à savoir l’oscillateur radiofréquence qui génère la porteuse sur laquelle l’information est transmise, et le débit de communication. Le récepteur transpose le signal radiofréquence en bande de base par le mélange avec un oscillateur local LO (Fig. 3). La phase qui encode l’information sur la porteuse ne sera exploitable que si une copie de l’oscillateur de l’émetteur – RF – est générée en local : LO est asservi sur RF selon des mécanismes qui seront décrits plus bas (section 2). Une fois que des bits seront obtenus en sortie de la démodulation, l’information numérique est échantillonnée périodiquement pour extraire l’état de chaque bit et former des trames. Ici encore, le rythme du décodage n’a aucune raison d’être synchronisé avec le rythme de génération des données : même si la valeur nominale du débit de communication est connue, un écart entre l’oscillateur qui génère les données numériques sur l’émetteur et celui qui cadence l’échantillonnage sur le récepteur finira au bout d’un moment par induire une désynchronisation. Ici encore, un asservissement sera nécessaire, qui sera décrit en section 7.

Fig. 3 : Problème de synchronisation des oscillateurs distants qui portent le signal et cadencent le débit de donnée. Le décodage ne sera fonctionnel que si les deux oscillateurs du récepteur – LO et échantillonnage de l’état de l’information numérique – sont asservis sur leurs homologues du côté de l’émetteur.


Dans la séquence d’acquisition par GNURadio proposée en figure 4 qui vise à démoduler un signal dans la bande FM, en extraire la sous-porteuse comportant les informations numériques, et stocker le résultat dans un fichier binaire pour post-traitement, deux caractéristiques déterminent la qualité de la démodulation et la puissance de calcul nécessaire : les fréquences de coupure pour isoler la bande qui nous intéresse par filtrages successifs, et les décimations (ne prendre qu’un point sur N pour une décimation d’un facteur N) pour réduire le débit de données. Un récepteur de télévision numérique terrestre (DVB-T) basé sur le convertisseur analogique-numérique RTL2832U travaille nécessairement avec une fréquence d’échantillonnage comprise entre 1,5 et 2,4 MHz, soit bien plus que l’encombrement spectral d’une bande FM. Notre première tâche consiste donc à décimer ce flux de données pour n’avoir qu’environ 200 kéchantillons/s, respectant ainsi l’encombrement spectral d’une unique station FM. Cependant, la décimation ne peut se faire sans avoir atténué le signal des autres stations se trouvant à plus de 100 kHz de la bande qui nous intéresse, sinon leurs signaux se ramèneront dans la bande de base par repliement spectral [8] lors de la décimation. Par conséquent, nous commençons par un filtre passe-bas qui isole la station d’intérêt, puis décimons suffisamment pour réduire le flux à un débit de l’ordre de 200 kéchantillons/s. L’autre intérêt de la décimation est de permettre des transitions des filtres en aval plus nettes avec un même nombre de coefficients : en effet, la bande de transition d’un filtre est de l’ordre de la fréquence d’échantillonnage divisée par le nombre de coefficients. Ainsi, il est très lourd de calculer un filtre présentant une bande étroite à taux d’échantillonnage élevé, tandis que le même résultat s’obtient à ressource de calcul réduite en décimant judicieusement auparavant. Les 200 kéchantillons/s que nous venons d’obtenir portent toutes l’information qui encode la station FM commerciale qui nous intéresse : le bloc WBFM démodule le signal et fournit un flux de données qui peut lui aussi être décimé si seule la composante audiofréquence nous intéressait. Cependant, nous désirons décoder le signal RDS qui se trouve autour d’une sous-porteuse à 57 kHz, donc nous ne pouvons pas encore décimer, mais devons attendre de transposer la sous-porteuse de 57 kHz vers la bande de base par un Xlating FIR Filter [9] pour une fois de plus décimer, les 200 kéchantillons/seconde étant bien trop rapides pour les quelques kHz occupés par le signal numérique. Ainsi, le filtre FIR (filtre à réponse impulsionnelle finie) est conçu pour isoler le signal numérique sur une bande de quelques kHz et rejeter les autres composantes spectrales avant la décimation qui fournit un débit de données raisonnable pour décoder le signal numérique. Attention : la fréquence d’échantillonnage qui définit le FIR doit être la fréquence d’échantillonnage en entrée du Xlating FIR Filter, donc tenir compte de la décimation du premier filtre passe-bas et éventuellement du démodulateur FM. Dans notre cas, ce filtre (variable taps qui sera appelée dans le champ du même nom dans le Xlating FIR Filter) est défini par l’expression Python : filter.firdes.low_pass_2(1, samp_rate/8, 2000, 500, 60) pour dire que le filtre passe-bas a décimé d’un facteur 8, pas de décimation sur la démodulation WBFM, 2 kHz de fréquence de coupure et une transition sur 500 Hz. À l’issue de ce traitement, nous avons isolé la bande du signal RDS que nous désirons décoder.

Fig. 4 : En haut : séquence de traitements d’un signal acquis dans la bande FM commerciale. Le mode waterfall (en bas à droite) montre clairement le pilote à 19 kHz et le RDS autour de 57 kHz. En bas : en l’absence de synchronisation sur la porteuse (bleu), la phase qui encode le signal comporte encore une dérive linéaire de pente égale à l’écart entre la fréquence nominale de 57 kHz et la fréquence de l’oscillateur local numérique. L’application de la boucle de Costas (vert) élimine cet écart de fréquence : la phase représente des bits exploitables (en bas à droite en bleu).


RDS est actuellement accessible pour les utilisateurs de GNURadio au travers du module gr_rds, initié par Dimitrios Symeonidis [11] et maintenu à ce jour par Bastian Bloessl [12]. Reprendre un code existant peut fournir de l’inspiration, voire valider le bon fonctionnement de l’installation matérielle de réception, mais n’amène rien à la compréhension de la mise en œuvre des diverses étapes de démodulation et de décodage, que nous tenterons d’appréhender ici. Les divers contributeurs à gr_rds ne semblent pas avoir cru bon de détailler le fonctionnement de leur code dans une documentation ou publication associée, rendant la lecture du code source quelque peu fastidieuse, surtout pour les novices que nous sommes à ce stade de l’analyse du protocole. En effet, nous verrons que plusieurs couches OSI devront être parcourues avant d’obtenir un message intelligible, et cette séparation claire dans la documentation technique n’en reste pas moins confuse au premier abord par le report en annexe de la couche 2 tandis que le texte principal aborde les couches 1 et 3. Par ailleurs, tous les codes consultés sur le Web s’inspirent d’une implémentation des codes correcteurs d’erreur sous forme de registre à décalage, une solution naturelle pour l’électronicien, mais peu intuitive pour le traiteur de signaux qui exprime plus naturellement un problème sous forme matricielle. Nous proposerons donc une implémentation qui nous semble originale de la synchronisation de trames et de la correction d’erreurs que nous n’avons pas trouvée dans les documentations consultées au cours de cette étude, mais dont la concision semble favoriser la compréhension de concepts un peu complexes à appréhender au niveau de la porte logique.

Le mode de modulation est décrit de façon quelque peu confuse dans les documents techniques décrivant la norme RDS [13], en expliquant qu’une modulation d’amplitude sans porteuse [14] est générée par deux signaux en opposition de phase [13, section 1.4]. L’alternative, de considérer l’information comme portée par une modulation en phase de ±90°, change complètement notre stratégie de démodulation (voir annexe A). Alors qu’une modulation d’amplitude ne nécessite qu’une estimation grossière de la porteuse et un redressement/filtrage dans une bande suffisamment large pour inclure tout écart entre fréquence de l’émetteur et fréquence de l’oscillateur local du récepteur, une modulation de phase nécessite une stratégie pour reconstruire une copie locale de l’oscillateur de l’émetteur avant modulation, qui sera l’objet de la première partie de ce document.

Ayant obtenu des signaux – phase du signal – représentatifs d’une séquence de bits, nous nous efforcerons de regrouper ces bits en trame (Fig. 5). Étant donné que les bits sont transmis continuellement, nous devrons trouver une stratégie pour identifier un début de trame dans ce flux continu de bits. Finalement, ayant synchronisé notre récepteur sur le flux de bits, nous en interprèterons le contenu et verrons que des résultats cohérents sont obtenus. Nous constatons sur la figure 4 – qui consiste en un flux de traitement dans GNURadio pour démoduler une bande FM, en extraire l’information à 57 kHz de la porteuse et en extraire phase et amplitude – que la phase ne présente pas une structure visuellement associée à une séquence de bits. Le spectre de la phase nous indique que la piste de la modulation de phase à deux états séparés de 180° (BPSK – Binary Phase Shift Keying [15][16]) est la bonne : le spectre est étalé autour de 1200 Hz par la modulation de phase, mais la raie fine à 2375 Hz confirme que tout processus non-linéaire qui a produit le carré du signal introduit un signal spectralement pur, comme on peut s’y attendre avec le BPSK.

Fig. 5 : Séquence de décodage des trames : le passage du milieu au bas est conforme au Tab. 2 de [13] avec une conversion respectant le codage de Manchester différentiel.

1. Transposition et reproduction de la porteuse

Nous avions déjà vu en étudiant les signaux GPS [15] que le mode de modulation BPSK, caractérisé par deux états de la phase 0 et 180° pour représenter deux états des bits 0 et 1 par exemple, s’exploite en produisant une copie locale de l’oscillateur de l’émetteur sans modulation. Pour ce faire, nous avions considéré diverses approches incluant une extraction de phase à partir des données complexes I et Q issues du démodulateur en exploitant une fonction insensible aux rotations de phase de 180° (atan de GNU/Octave qui ne tient pas compte du quadrant dans lequel se trouvent I et Q individuellement, mais ne s’intéresse qu’à Q/I, contrairement à atan2 qui exploite chaque composante séparément et restitue la phase en tenant compte des rotations de 180°). Une alternative avait été de passer le signal reçu au carré (le multiplier par lui-même) afin de retirer la modulation de phase, puisque le passage au carré d’un signal harmonique génère le double de son argument, et 2 x 180° = 360 = 0 [360] (Fig. 6 en bas à droite). Le résultat, de fréquence double de la fréquence de la sous-porteuse, produit une copie locale de la source émise avant modulation par passage dans un compteur qui divise par deux sa fréquence. Cette dernière méthode est implémentée dans le bloc de traitement dit de la boucle de Costas [15], qui fournit d’une part le signal corrigé de l’erreur entre l’oscillateur émetteur et l’oscillateur local du récepteur, et d’autre part une estimation de cette erreur.

Notre stratégie de traitement consiste donc à :

  1. transposer le signal à 57 kHz de la sortie du démodulateur FM pour amener l’information numérique en bande de base, par exemple avec Xlating FIR Filter de GNURadio, en exploitant un oscillateur local libre. Alors que nous devons habituellement expérimenter avec la fréquence de transposition de ce bloc avant de nous rappeler s’il faut indiquer + ou – la fréquence pour amener le signal en bande de base (autour de la fréquence nulle), le problème ne se pose exceptionnellement pas dans ce cas où la sortie du démodulateur FM est un signal réel, donc dont le module de la transformée de Fourier est pair. L’information qui nous intéresse est autour de +57 kHz, mais aussi autour de -57 kHz : les deux solutions sont acceptables et fournissent le même résultat ;
  2. extraire la phase du signal résultant, phase qui présente deux composantes : l’information encodée dans la phase à ±90°, et la dérive linéaire due à l’écart de fréquences des oscillateurs de l’émetteur et du récepteur Δf ;
  3. fournir ce signal à une boucle de Costas qui estime Δf et la compense.

La modulation se fait à 1187,5 bits/s, et nous verrons plus loin qu’il s’agit d’un mode d’encodage différentiel qui nécessite donc au moins 1187,5 x 2 = 2375 Hz, déterminant donc la largeur du filtre du Xlating FIR Filter ainsi que son facteur de décimation. Nous viserons d’avoir au moins 5 points par période, soit au moins 11875 échantillons/s.

Fig. 6 : À gauche : réception FM, suivi de l’extraction de la sous-bande RDS. En l’absence de synchronisation sur la porteuse, la phase varie trop vite pour ressembler à un signal numérique.

 

2. Du signal en bande de base aux bits

Nous supposons maintenant avoir un flux représentatif d’un signal numérique. Nous voulons extraire de la phase une séquence de bits. Dans un premier temps, nous apprenons [13, section 1.6] que le signal est encodé de façon différentielle (s’apparentant aussi à un codage Manchester différentiel [16]), confirmé par notre observation que la phase varie deux fois plus vite que le taux attendu de 1187,5 Hz. Nous allons donc seuiller la phase après en avoir retranché la valeur moyenne – en considérant qu’une phase inférieure à 0 est une valeur nulle sinon la valeur du bit est 1 (bit slicer dans GNURadio), et une fois la valeur saturée obtenue, nous appliquons la condition que deux phases adjacentes de phase de même valeur se traduisent par un bit à 0 et si une transition est observée, le bit résultant est égal à 1. Les deux subtilités ici tiennent d’une part à se tromper de front lors de la recherche du demi-bit permettant de commencer l’analyse – dans ce cas toutes les paires adjacentes présentent une transition (cas du codage Manchester) – et d’autre part de recaler le débit de communication si le rythme des données n’est pas calé sur notre horloge locale. Nous recherchons donc la première transition (debut), puis avançons dans la séquence de données en recherchant au quart de la période après la transition et aux trois quarts (second état). En fonction de l’égalité ou l’inégalité de ces deux états (s1 et s2), nous déduisons so le bit de sortie, comme OU exclusif de ces deux bits, ce qui correspond aussi à une somme modulo 2, expression plus naturelle pour GNU/Octave il nous semble.

La chaîne de traitement GNURadio fournit un signal synchronisé sur la porteuse radiofréquence, mais ne traite pas le problème de la synchronisation du débit de données numérique (intervalle de temps entre deux bits). Dans l’exemple ci-dessus, une approche naïve consiste à observer si la transition d’un bit à l’autre se produit une période avant ou après le moment attendu, et si c’est le cas de décaler un peu le compteur qui s’incrémente le long de la trame (variable l). Une façon plus rigoureuse, mais plus complexe, est discutée en annexe B, en exploitant les blocs de traitement adéquats de GNURadio que sont le MPSK Decoder ou Clock Recovery MM, tels que présentés dans http://gnuradio.4.n7.nabble.com/Clock-Recovery-MM-documentation-td55117.html. Bien que cette méthode de synchronisation du flux numérique n’ait pas été exploitée au cours de la rédaction de cet article, induisant les études sur la capacité de correction des bits corrompus lors du décodage des trames par le code correcteur d’erreur qui vont suivre, sa mise en œuvre tardive rend le décodage extrêmement efficace tel qu’illustré en fin d’annexe B.

3. Des bits aux messages : synchronisation

Nous observons une séquence continue de bits. Cependant, une trame commence et finit à certaines frontières que nous devons déterminer : nous avions vu par exemple que dans ACARS [17] chaque phrase commence par un préambule qui permet par ailleurs de synchroniser le récepteur avec le débit de données de l’émetteur. Dans le cas de RDS, le mode de recherche du début est décrit dans la norme [13, annexe C] : placer ce sujet aussi loin dans la documentation rend sa lecture quelque peu complexe puisqu’elle encourage à se lancer dans le décodage des trames [13, section 2] avant de s’être assuré de l’intégrité des trames. Nous apprenons entre ces deux sections que toute trame RDS est formée de 16 bits de données suivies d’un code correcteur d’erreur de 10 bits (pour une alternative, voir l’annexe C). L’information de base est donc un bloc de 26 bits, et 4 blocs successifs de types différents – nommés A, B, C, D – se suivent pour former une trame. Le mode de synchronisation [18, chapitre 12] consiste donc à :

  1. prendre 26 bits adjacents dans la séquence acquise ;
  2. calculer le code correcteur d’erreur (voir ci-dessous) pour ces 26 bits en supposant qu’il s’agit d’un bloc A ;
  3. si les 10 derniers bits de la séquence considérée correspondent au code correcteur d’erreur, il est envisageable que nous ayons trouvé la synchronisation, que nous validons en calculant le code correcteur du bloc suivant (B, 26 bits suivants) puis D (26 bits séparés de 78 bits de l’indice courant d’analyse). Si ces trois conditions sont vérifiées, nous avons très probablement trouvé un cas de synchronisation et donc le premier bit de la trame. Le bloc C a été sauté, car deux cas peuvent se présenter – C et C’ selon la nature du message – avec des syndromes différents, multipliant les cas à traiter ;
  4. si le calcul du code correcteur sur les 16 premiers bits ne donne pas la séquence des 10 derniers bits, il n’y a pas synchronisation : nous avançons d’un bit dans la séquence et nous recommençons la procédure.

Cette séquence doit finir par converger vers une condition où tous les 10 bits de fin de chaque bloc correspondent au code correcteur d’erreur des 16 bits qui précèdent. Si ce n’est pas le cas, le décodage des bits (étape précédente) a échoué, et il faut reconsidérer la conversion des données brutes de phase vers les données numérisées. Ce succès du décodage est la source de la synchronisation en temps proposée par [2]. Une fois le début du bloc identifié, le contenu de chaque bloc dépend de la nature du message : alors que le bloc A contient toujours un identifiant de la station (code PI, annexe C), le contenu des autres blocs change pour chaque type d’information transmise, tel que documenté dans [13, section 3].

Un point clé de cette discussion tient au calcul du code correcteur d’erreur. Toutes les implémentations que nous avons trouvées exploitent un registre à décalage avec rétroaction (Linear Feedback Shift Register – LFSR), une représentation naturelle pour un FPGA ou un microcontrôleur programmé en assembleur [19], mais peu approprié à GNU/Octave qui exprime les problèmes sous forme matricielle (voir note). Afin de ne pas risquer d’être qualifié de plagiat – tous les codes libres consultés sur Internet et implémentés pour calculer le code correcteur sont du même acabit que https://github.com/bastibl/gr-rds/blob/master/lib/decoder_impl.cc#L69-L80 (Fig. 7) – nous proposons de calculer le code correcteur par son expression matricielle telle que proposée dans [13, section B.2.1] : une matrice H de 26 x 10 fournit la relation entre les données et chacun des bits du code correcteur d’erreurs.

Fig. 7 : Implémentation sous forme de registre à décalage du code correcteur d’erreur. Nous proposons l’alternative de précalculer les états possibles du code correcteur d’erreur pour l’implémenter sous forme d’opération matricielle, plus naturelle sous GNU/Octave. Chaque symbole « ⊕ » se comprend au sens binaire, comme un OU exclusif. Ce schéma est issu de [13, p.62].


Le passage de l’expression polynomiale du code correcteur d’erreur à l’expression matricielle ne saute pas forcément aux yeux au premier abord. Le principe de l’algèbre linéaire (expression matricielle) tient à décomposer le problème sur chaque élément de la base et de déduire la solution comme combinaison linéaire de chaque solution obtenue sur la décomposition du problème sur chaque élément de la base. Dans notre cas, la base du problème est un bit dans le message à 1 à la nième position et les autres bits à 0. Nous appliquons donc le calcul du code correcteur d’erreur à chaque vecteur [0 … 0 1 0 … 0] en déplaçant le 1 dans le vecteur, ce qui en expression polynomiale s’écrit xn. Le code correcteur d’erreur s’obtient comme reste de la division polynomiale [20] de xn, n [0..25] (les 26 positions possibles du bit dans le message émis) avec le polynôme représentant le code BCH [21, p. 251] x10 + x8 + x7 + x5 + x4 + x3 + 1 qui s’écrit sous GNU/Octave [1 0 1 1 0 1 1 1 0 0 1] (puissance la plus forte à gauche). Pour rappel, une division polynomiale s’effectue comme une division classique, avec le dénominateur multiplié par la puissance adéquate pour éliminer le terme de plus haute puissance du numérateur, et le reste calculé par soustraction de ces deux termes. La procédure se poursuit sur le reste jusqu’à atteindre une puissance inférieure à celle du dénominateur. Par exemple :

Le reste de la division polynomiale s’écrit sous GNU/Octave (et Matlab) comme [b, r] = deconv(N,D); avec N et D les vecteurs représentant respectivement les polynômes du numérateur et dénominateur, et r le reste de la division qui nous intéresse. Dans l’exemple précédent, [d, r] = deconv([1 0 1 1 1],[1 0 1]) donne d = 1 0 0 et r = 0 0 0 1 1. Ainsi la matrice G de [13] s’obtient par le script GNU/Octave suivant :

Comme la matrice identité à gauche de G place le bit de poids faible en bas, ce script calcule les lignes de la droite de G de bas en haut.


Cet exemple, un peu volumineux compte tenu de la matrice de décodage H, effectue les opérations suivantes :

  1. pour chaque séquence de 104 bits consécutifs, nous découpons 4 blocs adjacents de 26 bits chacun (ll.47–50). Chaque bloc est supposé être formé de 16 bits de données suivis de 10 bits de code de correction d’erreur auquel ont été ajoutés les bits d’identification du bloc ;
  2. nous calculons le syndrome de 10 bits de chaque bloc de 26 bits par application du produit matriciel avec H (ll. 51–54) ;
  3. nous recherchons si le syndrome ainsi calculé correspond au syndrome du bloc correspondant (ll. 55–59). Si cette condition est vérifiée, le bloc est validé, et nous considérons être synchronisés si cette condition est vérifiée pour les 4 blocs consécutifs ;
  4. si un bloc ne vérifie pas un syndrome du code correcteur d’erreur égal à la valeur prévue, nous supposons ne pas être synchronisés : nous avançons d’un cran dans la séquence de bits acquise pour redéfinir une nouvelle séquence de 104 bits, et reprenons le calcul.

Le passage de G à H tel que fourni dans [13] n’est lui non plus pas trivial. Alors que le passage de G à une forme de H telle que l’intégrité d’un message x reçu se vérifie par H · x = 0 tel que proposé dans [21, p. 244] ou [22, p. 70] ne nécessite qu’une transposition de la partie non-identité de G, l’expression de la matrice de contrôle d’erreur fournie dans [13, p.63] ne respecte pas cette expression, mais place l’identité à gauche de la matrice de décodage. Le passage d’une expression à l’autre est illustré sur http://www.di-mgt.com.au/cgi-bin/matrix_stdform.cgi qui exploite l’algorithme de [22, p. 52, 71] pour passer de l’une (issue de la matrice d’encodage) à l’autre (dite standard) par combinaison linéaire et permutation des lignes ou colonnes. D’après le site web sus-cité, nous passons de l’expression de H fournie dans [13, p. 63]

à celle issue de [21, p. 244] le morceau à droite de l’identité dans G est transposé (la colonne de gauche ci-dessous est effectivement la fin de la première ligne de G par exemple)

par cette série de transformations (noter le passage de la sous-matrice identité de gauche à droite de la matrice H).


4. Interprétation des messages

Le plus difficile est fait : nous avons une séquence de bits, dont nous sommes garantis de l’intégrité par calcul du code correcteur d’erreur, il ne reste plus qu’à interpréter les divers messages, en remplaçant le contenu des lignes 60–62 de l’exemple précédent. Toutes les transactions se font avec le bit de poids fort (MSB) transmis en premier. Nous nous sommes limités à quelques exemples simples et représentatifs pour garder le code court : nom de la station, horloge (jour/heure/minute) ou texte libre. Comme nous voulions pouvoir identifier la station en cours de réception, le premier type de bloc décodé est 0A ou 0B tel que défini par les 4 premiers bits du bloc B : si les 4 premiers bits du bloc B sont nuls, alors le bloc D contient des caractères ASCII qui contiennent le nom de la station FM émettrice. Le bloc B est le deuxième bloc dont les données sont stockées dans la variable data2 dont nous interprétons le contenu comme deux caractères ASCII, MSB en premier, consécutifs :

On notera la petite subtilité dans la conversion du tableau de bits en nombre par le produit scalaire (et non terme à terme) de data et puissance, ce dernier contenant les puissances de 2 de 128 à 1 (bit de poids le plus fort en premier).

Le résultat de ce traitement, pour des fréquences reçues à Besançon, est de la forme

pour 100,4 MHz,

pour 93,5 MHz, et

pour 96,9 MHz, qui laisse penser que nous avons enregistré des signaux de Virgin, Le Mouv’ et BIP. Finalement, Rire & Chanson sur 91.0 se traduit par :

Sellig semble être un humoriste donc son nom dans le titre de la chaîne n’est pas improbable. Plus intéressant, France Info nous donne :

qui diffuse, en plus du titre de la chaîne, un texte libre annonçant l’émission en cours.

Sans être parfaites, ces trames démontrent que le concept est convenablement implémenté, en accord avec les résultats fournis par gr_rds (Fig. 8).

Fig. 8 : En haut, gr_rds en action sur France Info : la présentation est à peine plus attractive que l’exécution d’un script dans GNU/Octave et les données affichées sont sensiblement les mêmes. Nous notons à l’exécution que le nom de la station et le texte libre s’accumulent petit à petit, en accord avec la difficulté que nousobservons d’obtenir une trame complète valide. En bas : la sortie de gr_rds sur Rire & Chanson, confirmant l’inclusion de l’auteur de l’émission en cours dans le titre de la station.

5. Correction d’erreur

Nous avons décodé les messages issus de RDS après nous être synchronisés pour aligner les phrases sur le flux continu de bits, que pouvons-nous vouloir de plus ? Le code correcteur d’erreur de 10 bits ajouté en fin de chaque message de 16 bits n’a pour le moment été exploité que pour la synchronisation et garantir l’intégrité des transactions. Le signal RDS est bruité, et un certain nombre de trames sont éliminées de l’étude parce que leur code correcteur ne correspond pas aux attentes. Pouvons-nous améliorer le rendement de la réception en tentant de corriger les erreurs grâce à la redondance introduite par le code correcteur d’erreur [23], démarche qui a contribué à la croissance du débit de communication dans les sondes spatiales (Fig. 9) [24] ? Cela nous ramène en marche arrière par rapport au paragraphe précédent, à la couche 2 de la hiérarchie OSI, mais donne l’opportunité de se confronter à une étude empirique de l’implémentation des codes correcteurs d’erreur.

Le code implémenté permet non seulement d’identifier une corruption du message, mais en plus d’identifier quel bit a été modifié : un code de Hamming [15, chapitre 8] est capable d’une telle correction pour une unique erreur. Un code BCH [21, page 252][22, chapitre 11] est une extension qui permet de corriger plus d’un bit : ici, le code proposé permettra d’aller jusqu’à la correction de deux bits corrompus lors de la transmission.

Fig. 9 : Évolution de la bande passante de communication des sondes spatiales.


Jean-Michel FRIEDT
[Institut FEMTO-ST, dpt. Temps-fréquence, Besançon]

La seconde partie de cet article sera publiée prochainement sur le blog, restez connectés 😉

Retrouvez cet article (et bien d’autres) dans GNU/Linux Magazine n°204, disponible sur la boutique et sur la plateforme de lecture en ligne Connect !

Laisser un commentaire