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

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.

 

 

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.

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.

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.

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.

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.

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.

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).

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.

5.1 Une erreur

L’annexe C de [13]nous explique que le code correcteur d’erreur est implémenté, lors de l’émission, comme une combinaison linéaire (somme modulo 2, ou XOR) des bits à émettre.

Une transformation linéaire s’implémente soit de façon logique par un registre à décalage avec des points de ponction pour alimenter les portes XOR (Fig. 7), mais comme nous prototypons sous GNU/Octave, nous continuons à exploiter l’approche matricielle [21, p. 244] : une matrice de 16 x 10 calcule les 10 bits de sortie compte tenu des 16 bits d’entrée. Nous avons vu que nous ajoutons un identifiant de bloc pour la synchronisation à ce code de correction d’erreur : le message transmis comprend donc les 16 bits de données suivis des 10 bits de correction sommés au code de bloc. En terme GNU/Octave, cela s’écrit :

Si tout se passe bien, ce message 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 0 1 0 0 1 0 1 0 1 0 qui contient encore les deux caractères ASCII JM est transmis, et reçu sans corruption de bit, donc le décodage que nous avons vu s’obtient côté récepteur par :

et le message reçu mIr doit donner 0 après soustraction du syndrome correspondant au bloc A, nommé ici sA2. Cette petite expérience numérique valide le bon fonctionnement du décodage des messages.

Supposons maintenant qu’entre l’émission et la réception, une erreur survienne :

Pouvons-nous faire mieux que rejeter le paquet ? En affichant le résultat du calcul du syndrome, nous constatons qu’en insérant une erreur sur le troisième bit, le syndrome nous indique :

qui dit bien que le troisième bit est corrompu. Cela correspond au fait que les 10 premières lignes de H forment une matrice identité. De façon générale, une erreur sur le Nième bit se détecte par un syndrome égal à la ligne N de H. En effet, une erreur peut survenir sur n’importe quel bit des 26 bits du message : si une erreur survient sur le bit 25 :

nous obtenons :

qui est bien l’avant-dernière ligne de H. La recherche du bit corrompu se généralise donc par

avec num nous indiquant si le syndrome a été trouvé comme ligne de H, et si c’est le cas, ligne nous indique quel bit a été corrompu. Nous améliorons donc notre capacité de décodage de RDS, avec par exemple 24 caractères en plus des 680 déjà acquis sur l’identification de Le Mouv’ (+4%), 9 caractères en plus des 79 déjà acquis pour Virgin (+11%) et 10 en plus des 60 pour BIP (+17%).

Quelques expérimentations avec les deux expressions de la matrice de décodage H constatées auparavant nous convainquent qu’elles fonctionnent de la même façon, puisque les propriétés du code sont conservées par permutation des lignes et colonnes. Ainsi, nous observons par

qu’en encodant un message, y compris l’identifiant (optionnel dans ces expérimentations) de bloc, nous sommes capables d’une part de valider le transfert d’information sans erreur : commenter l’introduction de l’erreur en ligne 19 pour constater que le résultat des deux décodages, avec H1 ou H2, sont tous deux nuls. Par ailleurs, en cas d’introduction d’une erreur, le résultat est bien le contenu de la ligne d’indice égal au numéro du bit erroné.

5.2 Deux erreurs

Retrouver un bit corrompu fonctionne bien, et nous avons compris comment identifier quel bit est corrompu en recherchant la ligne de H qui contient le syndrome après décodage d’un message avec un bit qui a été modifié. Cependant, que se passe-t-il si deux bits sont corrompus ?

Une rapide petite expérience numérique nous met sur la voie :

se traduit par

Deux bits sont désormais à 1 après décodage du syndrome, celui de la deuxième et de la cinquième ligne. L’analyse est donc triviale tant que deux des dix premiers bits ont changé : le numéro des bits modifiés apparaissent dans le syndrome calculé en réception, toujours parce que les 10 premières lignes de H forment la matrice identité. Ce concept se généralise en citant le cours [25] : « Suppose we wish to correct all patterns of t errors. In this case, we need to pre-compute more syndromes, corresponding to 0, 1, 2,... t bit errors. Each of these should be stored by the decoder. ».

Nous devons donc calculer une nouvelle matrice, déduite de H, que nous noterons m2r, qui contient tous les syndromes de 10 bits correspondant aux sommes de toutes les combinaisons possibles de 2 lignes de H. Une approche par boucle for, pas nécessairement la plus élégante pour GNU/Octave, mais qui a le bon goût de fonctionner, donne :

Évidemment, m2r est beaucoup plus grande que H puisque cette fois nous avons tous les couples d’erreurs possibles représentés dans chaque ligne de la nouvelle matrice. Nous nous assurons que toutes les lignes sont uniques – propriété du code capable de corriger deux erreurs de communication :

ne renvoie par de réponse (question : pourquoi [m2runiq,m,n]=unique(m2r,'rows'); renvoie moins de lignes dans m2runiq qu’il n’y en a dans m2r, alors que toutes les lignes sont uniques ?).

Nous pouvons maintenant rechercher quelle paire de bits a changé lors de la transmission par

et comme nous avions pris soin de placer dans solution le couple j et k des lignes de H qui ont été sommées pour donner la ligne de m2r, nous connaissons l’indice k et j des bits modifiés. En effet,

se traduit bien par

dans laquelle nous constatons que la recherche du syndrome mIr dans la matrice H (une modification) ne donne pas de résultat (num=0), mais que la recherche dans m2r donne un résultat, avec le syndrome présent dans la 314ème ligne de m2r, qui a été calculée lorsque j=21 et k=25. Le décodage fonctionne bien. RDS n’annonce que la capacité à corriger 1 ou 2 bits corrompus lors de la transmission, nous arrêtons donc là notre étude du code correcteur d’erreurs.

Le nombre de bits qui peut ainsi être corrigé par un code est déterminé par le concept de distance de Hamming, qui se représente graphiquement comme la distance entre le « bon » message et le message corrompu reçu, en deçà de laquelle la correction est possible (http://fr.wikipedia.org/wiki/Code_correcteur).

La capacité de corriger des transmissions corrompues est au cœur du gain de débit de communication (Fig. 10), que ce soit dans une liaison avec les sondes spatiales lointaines (deep space network) [24]ou en liaison courte portée à faible consommation [26]. Ce survol rapide d’un exemple simple ouvre donc des perspectives d’approfondissement qui restent d’actualité : sans prétendre comprendre comment générer ces codes, l’expérimentation sur des données réelles avec un résultat concret fournit la motivation à approfondir les ouvrages plus théoriques sur le sujet tels que [21]et son excellente mise en relation de compression, cryptographie et correction d’erreurs.

Conclusion

Nous avons analysé le protocole RDS, exploité pour la transmission numérique d’informations associée aux chaînes FM de la bande commerciale incluant le nom de la station ou la nature du programme, en partant de l’acquisition de l’information analogique depuis un récepteur de télévision numérique terrestre, puis extraction de l’information numérique sur la sous-porteuse à 57 kHz, avant d’extraire les trames (en ayant résolu la synchronisation des phrases) et d’en interpréter le contenu. Nous avons finalement abordé la correction d’erreurs pour constater que nous pouvions simuler des erreurs connues et les identifier. En appliquant cette méthode de traitement aux données reçues expérimentalement, nous avons pu retrouver plus de 10% de signaux exploitables additionnels par rapport au cas où nous ne traitions que les informations transmises dans leur intégralité.

Bien des développements seraient nécessaires avant que cette démonstration de principe ne puisse être considérée comme robuste pour un environnement en production, en particulier sur la synchronisation du décodage des trames transmises à 1187,5 bps de façon asynchrone, mais cela se ferait en alourdissant le code proposé au détriment de sa lisibilité. Il nous semble que la démonstration des principes de base de ce mode de modulation est explicite, avec des messages intelligibles et cohérents avec les informations transmises par chaque station. Cet exercice a nécessité environ 2 mois de travail pour aboutir : il s’agit donc d’un bon exercice pour se familiariser avec les diverses couches d’un protocole de communication, en allant de la couche matérielle à la couche session.

Un point décevant est l’absence de transfert précis de temps par ce médium. Nous n’avons reçu que peu de trames de datation (CT, groupe 4A) qui nous permettent de connaître la date et l’heure qu’avec une précision de ±0,1 s au début de chaque minute. Cette déficience sera bientôt corrigée avec le décodage logiciel de DCF77 que nous présenterons dans un autre numéro.

Une archive contenant les scripts GNU/Octave, configuration de GNURadio Companion et fichiers d’exemples, est disponible à http://jmfriedt.free.fr/lm_rds.tar.gz.

Remerciements

Je remercie Thomas Lavarenne pour avoir motivé cette étude par ses interrogations et des échanges constructifs, et Bastien Bloessl pour avoir exprimé l’opinion que le décodage de RDS est trivial [27], un commentaire inacceptable tant que ce protocole avait résisté à nos investigations. Ce défaut de compréhension est maintenant corrigé. G. Cabodevila a amélioré la qualité du code GNU/Octave lors de sa relecture, et É. Carry a clarifié un certain nombre de points. Bien que nous ayons acquis une copie papier de l’ouvrage de Dunod[21], les autres références ont été obtenues auprès de Library Genesis, http://gen.lib.rus.ec, une source indispensable pour nos recherches.

Annexe A : phase ou amplitude ?

Nous avons pris le parti au cours de cette étude de considérer le signal transmis par RDS comme une information modulée en phase, car nos premières tentatives consistant à afficher l’amplitude du signal filtré (Band Pass Filter autour de 57 ± 2,5 kHz) se traduisaient par un signal inexploitable. Bien que la boucle de Costas pour asservir en phase reste nécessaire, afficher la partie réelle au lieu de la phase donne aussi un signal parfaitement exploitable (Fig. 11). Quelques petites oscillations sont visibles sur les symboles les plus longs, qui pourraient se traduire par une fausse détection d’un symbole court si on n’y prend garde : un filtre passe-bas optimisé retire cette fluctuation et garantit une meilleure détection de la nature du signal transmis. En effet, filtrer par une fonction de transfert spectrale quasi-rectangulaire se traduit, par transformée de Fourier de la porte rectangulaire, par une convolution par un sinus cardinal (sin(x) / x) et donc un étalement de chaque symbole sur ses voisins compte tenu du temps de décroissance lent du filtre. Quel que soit le filtrage, tracer l’amplitude du signal (module du complexe) donne une information inexploitable pour la détection des bits : seules la phase ou la partie réelle sont exploitables.

Annexe B : ajustement de l’horloge de la trame numérique

La modulation de phase nécessite une copie locale de la porteuse du signal radiofréquence sans modulation, une tâche résolue par la boucle de Costas qui élimine la modulation de phase. Une fois les bits visibles sous forme de phase à   ou π (pour BPSK), il reste le problème de connaître le rythme auquel les bits sont transmis. L’horloge qui cadence la transmission numérique (par exemple un microcontrôleur sur l’émetteur) n’a aucune raison d’être la même source de fréquence que la porteuse radiofréquence, et il faut donc de nouveau retrouver une copie locale de l’horloge qui cadence le signal numérique pour le décoder (Fig. 13). Diverses stratégies sont disponibles, telles que maximiser le nombre de transitions dans le signal transmis pour permettre l’asservissement de l’horloge locale (cas du codage Manchester qui garantit au moins une transition à chaque bit). GNURadio fournit divers blocs pour la synchronisation de l’horloge cadençant le flux numérique, tels que Clock Recovery (selon l’algorithme publié dans [27]) ou MPSK Receiver. Ces blocs s’alimentent de la sortie de la boucle de Costas qui a éliminé l’erreur grossière de fréquence, et manipulent maintenant les symboles numériques issus du traitement précédent pour ajuster le flux de données. Ces blocs fournissent un échantillon par symbole, rendant le traitement ultérieur très simple (saturation par comparaison – nommé Binary Slicer dans GNURadio – puis analyse de la séquence numérique ainsi formée). Nous validons le bon fonctionnement de ces blocs en affichant le diagramme de constellation, qui comporte en ordonnée la partie imaginaire de la sortie du bloc de traitement et en abscisse la partie réelle. Puisque dans le plan complexe l’angle à l’axe des abscisses est la phase et la distance à l’origine la magnitude, un nuage de points à angle constant et distance constante indique une synchronisation efficace. Un nuage de points « qui danse » ou forme un cercle indique l’absence de synchronisation. La sortie directe de la boucle de Costas fournit une illustration du second point (Fig. 14, droite) tandis que le passage dans un bloc chargé de synchroniser l’horloge cadençant le flux numérique donne bien deux nuages (Fig. 14, gauche) qui sont les deux états possibles attendus en BPSK. Nous constatons ici que le filtre RRC que nous avons vu auparavant, même s’il ne change pas de façon significative la forme du signal d’un point de vue visuel, assiste la synchronisation de l’horloge en réduisant la diffusion de puissance dans un état des symboles numériques vers l’autre. Un filtre passe-bas atteint le même résultat, mais moins efficacement.

 

La configuration des blocs de synchronisation telle que décrite dans http://gnuradio.org/redmine/projects/gnuradio/wiki/Guided_Tutorial_PSK_Demodulation nous informe que nous devons tenter de minimiser le nombre d’échantillons par symbole, tout en le maintenant au-dessus de 2. Pour ce faire, un RRC est inséré entre la boucle de Costas et le bloc de synchronisation d’horloge, avec un facteur de décimation qui permet d’atteindre un facteur Omega (ratio de la fréquence d’échantillonnage au débit du flux numérique) proche, mais au-dessus de 2. Dans notre exemple, Omega vaut samp_rate/128/(1187.5*2) avec 128 le produit des décimations des divers blocs de traitements entre la source et la synchronisation d’horloge, 1187,5 x 2 le débit de bits en encodage Manchester, et samp_rate le débit de données issues de la source. Les autres paramètres du bloc de synchronisation restent inchangés. Le RRC est quant à lui configuré avec un débit d’entrée égal au débit de la source divisé du produit des divers facteurs de décimations dans la chaîne de traitement qui le précède, et un débit de symboles égal à 1187,5 x 2 de nouveau, déterminant donc sa fréquence de coupure.

Le fichier issu d’une synchronisation de la porteuse (Costas) et du flux numérique (Clock Recovery ou MPSK) se décode parfaitement avec les scripts proposés dans le texte (section 3), en retirant les 4 premières lignes puisque nous avons désormais 1 échantillon/symbole, et en ne gardant des lignes 8 à 24 que p=angle(r);p=p-mean(p);s=(p>0);s=s-mean(s);s1=s(2:2:end);s2=s(1:2:end-1);. En effet, s est la version saturée de la phase p, dont le décodage par Manchester différentiel considère les valeurs successives des paires d’échantillons initiaux. La suite du traitement (synchronisation sur le syndrome des séquences de 16 bits) reste identique, pour par exemple donner

qui est cette fois parfaite, ou

de nouveau sans corruption de données, voir

ou

qui est proche de la perfection. La date est en accord avec nos attentes : la date est le jour julien modifié 57811, que http://www.csgnetwork.com/julianmodifdateconv.html convertit en 27 Février 2017, l’heure est 7h5{1,4} décalée de 2 demi-heures, qui est bien 8h5{1,4}, heure de l’enregistrement. La trame 4A [13, p.28]est donc convenablement décodée et permet de recevoir l’heure par RDS, avec une mise à jour chaque minute annoncée comme exacte à ±0,1 s près. Ce n’est qu’après avoir inclus la synchronisation d’horloge de la trame numérique que nous obtenons des trames de datation de la forme 4A qui ne sont émises qu’une fois chaque minute. Une proportion trop faible de trames convenablement décodées a toutes les chances de nous faire rater cette séquence exceptionnelle de bits transmis :

Tous les exemples de cette annexe ont été acquis au rythme d’un échantillon complexe (2 x 4 octets) par symbole, tel que le propose la sortie du bloc Clock Recovery MM. Au rythme de 1187,5 x 2 = 2375 Hz, les fichiers d’enregistrement sont typiquement de quelques centaines de kilo-octets pour des acquisitions d’une dizaine de secondes (19000 kB/s).

Annexe C : code PI

Chaque trame RDS transmise contient, dans son premier paquet (bloc A [13, p. 15]), le code PI de la station. Il a été suggéré [13, p. 66]que connaissant ce code PI, unique à chaque station radio, il serait possible de se synchroniser sur cette séquence de bits qui se répète tous les 104 bits (4 blocs de 26 bits), au lieu de se battre avec le code correcteur d’erreur et calculer pour chaque séquence de 26 bits reçus si les 10 derniers bits correspondent au syndrome des 16 premiers bits tel que nous l’avons implémenté. Nous aurions pu réécrire l’histoire de cet article en démontrant ce concept avant d’entreprendre l’implémentation du code correcteur d’erreur, mais la vérité est que la liste des codes PI n’a été trouvée qu’une fois cette prose achevée. En effet, le site http://www.csa.fr/maradiofm/radiords_tableau fournit la liste des codes PI des diverses stations autorisées. Par exemple pour Radio Campus à Besançon, nous apprenons que son code PI est FC3A. En ajoutant dans la boucle de décodage des trames, au même titre que le texte libre ou le nom de la station, le décodage du PI par

en ayant pris soin d’initialiser PI=0 en dehors de la boucle, notre script GNU/Octave de décodage identifie bien PI = FC3A lorsque nous écoutons 102,4 MHz. Le code est bien identifié de cette façon.

Notes et Références

[1] BARISANI A. et BIANCO D., « Hijacking RDS-TMC Traffic Information signals », Phrack 64 (5), 2011 sur http://phrack.org/issues/64/5.html#article, et son archive : http://dev.inversepath.com/rds/

[2] LI L., XING G., SUN L., HUANGFU W., ZHOU R., et ZHU H., « Exploiting FM radio data system for adaptive clock calibration in sensor networks », Proc. of the 9th ACM International Conference on Mobile systems, applications and services, p. 169 à 182, 2011.

[3] SYMEONIDIS D., « RDS-TMC spoofing using GNU Radio », Proc. 6th Karlsruhe Workshop on Software Radios, p. 87 à 92, mars 2010, avec une copie fournie par l’auteur de ce papier placée sur http://jmfriedt.free.fr/Symeonidis.pdf

[4] FERNANDES E., CRISPO B., et CONTI M., « FM 99.9, Radio Virus: Exploiting FM Radio Broadcasts for Malware Deployment », IEEE Trans. on Information Forensics and Security 8 (6), p.1027 à 1037, 2013.

[5] GNURadio : http://gnuradio.org

[6] GNU/Octave : http://www.gnu.org/software/octave

[7] Communication Toolbox : http://octave.sourceforge.io/communications/overview.html

[8] Le repliement est un effet de l'échantillonnage périodique à intervalles de temps
discrets 1/fe, qui suppose que le spectre entre-fe/2 et fe/2 se répète tous les fe. De ce fait lors de la décimation d'un facteur N, toutes les composantes spectrales du signal comprises entre fe/(2N) et fe/2 se ramènent entre -fe/(2N) et fe/(2N) par translations par pas de fe/(2N). Cet effet est évité en précédant
la décimation d'un filtre passe-bas qui élimine efficacement toute composante du signal au-dessus
de fe/(2N).

[9] Nous avions introduit le Xlating FIR Filter comme un bloc implémentant une étape fondamentale de la démodulation, à savoir transposition en fréquence, filtrage passe-bas et décimation [10]. Pour rappel, le filtre passe-bas a pour vocation d’atténuer les composantes spectrales du signal après transposition en fréquence au-dessus de la fréquence d’échantillonnage atteinte suite à la décimation : sans ce filtre, tous les signaux au-dessus de la nouvelle fréquence d’échantillonnage se retrouveraient dans la bande de base par repliement spectral lors de la décimation et pollueraient la séquence de traitement qui suit.

[10] FRIEDT J.-M., « La réception de signaux venus de l’espace par récepteur de télévision numérique terrestre », Open Silicium n°13, décembre 2014/janvier-février 2015 : https://connect.ed-diamond.com/Open-Silicium/OS-013/La-reception-de-signaux-venus-de-l-espace-par-recepteur-de-television-numerique-terrestre

[11] https://bitbucket.org/azimout/gr-rds/

[12] https://github.com/bastibl/gr-rds

[13] European Standard EN 50067, « Specification of the radio data system (RDS) for VHF/FM sound broadcasting in the frequency range from 87,5 to 108,0 MHz », avril 1998, disponible sur http://www.interactive-radio-system.com/docs/EN50067_RDS_Standard.pdf ou pour sa version américaine http://www.nrscstandards.org/DocumentArchive/NRSC-4%201998.pdf

[14] TRETTER S.A., « Communication System Design Using DSP Algorithms, With Laboratory Experiments for the TMS320C30 », Chap. 6 « Double-Sideband Suppressed-Carrier Amplitude Modulation and Coherent Detection », Springer, 1995.

[15] FRIEDT J.-M, CABODEVILA G., « Exploitation de signaux des satellites GPS reçus par récepteur de télévision numérique terrestre DVB-T », Open Silicium n°15, juillet-septembre 2015 : https://connect.ed-diamond.com/Open-Silicium/OS-015/Decodage-des-signaux-de-satellites-GPS-recus-par-recepteur-de-television-numerique-terrestre-DVB-T

[16] http://www.mathworks.com/examples/simulink-communications/mw/rtlsdrradio_product-RBDSSimulinkExample-rbds-rds-and-radiotext-plus-rt-fm-receiver

[17] FRIEDT J.-M, GOAVEC-MÉROU G., « La réception radiofréquence définie par logiciel (Software Defined Radio –SDR) », GNU/Linux Magazine n°153, octobre 2012, p.4 à 33 : https://connect.ed-diamond.com/GNU-Linux-Magazine/GLMF-153/La-reception-radiofrequence-definie-par-logiciel-Software-Defined-Radio-SDR

[18] WESLEY PETERSON W. et WELDON E.J., « Error-Correcting Codes », 2nd Ed., MIT Press, 1996.

[19] TOPPING P., « RDS decoding for an HC11-controlled radio », Motorola AN495/D, 1994.

[20] GUIDON Y., « Comprendre les générateurs de nombres pseudo-aléatoires », GNU/Linux Magazine n°81, p. 64 à 76, 2006.

[21] DUMAS J. G., ROCH J. L., VARRETTE S., et TANNIER E., « Théorie des codes : compression, cryptage, correction », Dunod, 2007.

[22] HILL R. A., « A First Course in Coding Theory », Oxford University Press, 1990.

[23] PATROIS N., « Réparer un code QR », GNU/Linux Magazine n°198, novembre 2016

[24] http://descanso.jpl.nasa.gov/performmetrics/profileDSCC.html fait apparaître les modes de codage dans les gains significatifs de bande passante de communication, tandis que la Fig. 7-11 (page 477) de https://history.nasa.gov/SP-4227/Chapter07/Chapter07.PDF indique la chute du taux d’erreur avec les améliorations sur les modes de codage de canal.

[25] Notes du cours du MIT 6.02, BALAKRISHNAN H. et VERGHESE G., « Introduction to EECS II : Digital Communication Systems », chapitre 6 : « Linear Block Codes : Encoding and Syndrome Decoding », disponible sur https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-02-introduction-to-eecs-ii-digital-communication-systems-fall-2012/readings/MIT6_02F12_chap06.pdf, 2012

[26] TSIMBALO E., FAFOUTIS X. et PIECHOCKI R., « Fix it, don’t bin it! CRC error correction in Bluetooth Low Energy », Proc. 2nd IEEE World Forum on Internet of Things (WF-IoT), 2015 sur http://eis.bris.ac.uk/~xf14883/files/conf/2015_wfiot_crc.pdf

[27] MEYR H., MOENECLAEY M., FECHTEL S.A ., « Digital Communication Receivers: Synchronization, Channel Estimation, and Signal Processing », John Wiley & Sons, 1998.

[28] CUBUKCU E., « Root Raised Cosine (RRC) Filters and Pulse Shaping in Communication Systems », 2012, sur https://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/20120008631.pdf

[29] BARRY J. R., LEE E. A. et MESSERSCHMITT D. G., « Digital Communication », Springer, 2004.

[30] http://www.dsplog.com/2008/04/22/raised-cosine-filter-for-transmit-pulse-shaping/ qui fournit un script GNU/Octave pour expérimenter avec le filtre RRC.