Brevet FR2944168A1 — publié le 20101008

DEMANDE DE BREVET B07-1077FR - ODE/EVH Société Anonyme dite : STMicroelectronics SA Procédé de transmission d'un mot d'information binaire Invention de : David FURODET Procédé de transmission d'un mot d'information binaire L'invention concerne de manière générale la transmission de mots d'informations binaire, et plus particulièrement la détection des bits erronés de ces mots d'information à l'issue de la transmission. Classiquement, on utilise un code dit CRC (� Cyclic Redundancy Check � en langue anglaise) pour détecter les bits erronés dans l'information transmise entre deux systèmes à savoir, un système source (émetteur) et un ou plusieurs systèmes de réception (récepteurs). L'émetteur et les récepteurs sont couplés par un moyen de transmission généralement peu fiable, qui peut perturber le contenu de l'information transmise. Par exemple, un mot d'information s'écrivant sous la forme d'une séquence de bits � 100011011 � peut devenir à la réception � 001011011 �. Les valeurs du premier et du troisième bits ont été altérées lors de la transmission. Pour que les récepteurs détectent que le mot d'information reçu est incorrect, on ajoute quelques bits appelés � signature �, au mot d'information. Cette signature est obtenue en appliquant une fonction de hachage au mot d'information à transmettre, tel que : H(MI) =CRC , avec H la fonction de hachage, MI un mot d'information à transmettre, CRC sa signature. Cette fonction de hachage est communément appelée � Checksum � par l'homme du métier. I1 existe de nombreuses fonctions aptes à générer la signature (comme l'addition). Une telle fonction (� Checksum �) est considérée comme efficace si la signature indique systématiquement l'apparition d'un bit erroné. Un exemple de fonction � Checksum � est la division euclidienne. Plus précisément, la signature, encore appelée � redondance �, est générée en divisant le mot d'information à transmettre par un polynôme générateur. La redondance est alors égale au reste de cette division euclidienne. On considère qu'un polynôme générateur fournit une redondance efficace si celle-ci permet la détection d'un maximum de bits erronés dans le mot d'information reçu. La qualification d'un bon polynôme générateur dépend alors du type des erreurs les plus fréquentes liées au moyen de transmission. I1 existe principalement deux types d'erreurs, à savoir les erreurs aléatoires indépendantes (suivant le schéma de Bernouilli) et les erreurs en rafale (� burst �, en langue anglaise), autrement dit un certains nombres de bits consécutifs erronés. I1 est particulièrement difficile de trouver un polynôme générateur apte à engendrer une redondance permettant la détection de toutes ces erreurs, qu'elles soient de type aléatoire ou en rafale. Selon premier aspect, il est proposé un procédé de transmission d'un mot d'information binaire codé sur r bits auquel on accole une redondance codée sur s bits, s et r étant des nombres entiers, la redondance signalant l'apparition de bits erronés à l'issue de la transmission, et étant obtenus en effectuant une division euclidienne du mot d'information à transmettre par un polynôme générateur codé sur au plus s bits. Selon une caractéristique générale de cet aspect, on choisit le polynôme générateur de manière qu'il respecte au moins l'une des conditions suivantes, à savoir que : - le poids de Hamming des multiples dudit polynôme générateur est supérieur ou égal à un seuil choisi, - le polynôme générateur permet la détection d'au moins 2s-1-3 bits erronés consécutifs. En d'autres termes, de manière à générer une redondance optimale, le polynôme générateur doit respecter au moins l'une des deux règles définies ci-avant et de préférence les deux règles simultanément. Un polynôme générateur respectant la première des règles (poids de Hamming) permet de générer une redondance signalant au mieux les erreurs aléatoires. Un polynôme générateur respectant la deuxième règle (détection d'au moins 2s-1-3 bits erronés consécutifs) permet de générer une redondance signalant au mieux les erreurs en rafale. Les paramètres mis en oeuvre dans chacune des règles précitées sont ajustés en fonction de l'application choisie (environnement, type de récepteurs...) Selon un mode de mise en oeuvre, le polynôme générateur est de préférence codé sur huit bits. Dans ce cas, ledit seuil est par exemple supérieur ou égal à 4. Toujours dans le cas où le polynôme générateur est codé sur huit bits, ce dernier permet de préférence la détection d'au moins 125 bits erronés consécutifs. En variante, ledit seuil peut être supérieur ou égal à 3. Dans ce cas, le polynôme générateur peut permettre la détection d'au moins 126 bits erronés consécutifs. Selon un mode de mise en oeuvre, le choix d'un polynôme générateur peut comprendre : - pour chaque polynôme appartenant à un ensemble choisi, un premier test, où l'on vérifie en parallèle si le polynôme permet la détection d'un premier nombre de bits erronés consécutifs égal à 126 d'une part, et d'un deuxième nombre de bits erronés consécutifs égal à 125 d'autre part, - pour les polynômes vérifiant le premier test par rapport au premier et au deuxième nombre de bits erronés, un deuxième test où l'on vérifie si ces polynômes permettent la détection d'un nombre de bits erronés consécutifs. • inférieur à 126 dans le cas où le 15 polynôme permette déjà la détection de 126 bits erronés consécutifs, ou, • inférieur à 125 bits erronés dans le cas où le polynôme permette déjà la détection de 125 bits erronés consécutifs, 20 - pour les polynômes ne vérifiant pas le deuxième test, un troisième test, où l'on vérifie si le poids de Hamming des multiples de ces polynômes est supérieur ou égal à 4, - un classement des polynômes vérifiant le troisième 25 test dans une première famille de polynômes générateurs, - pour les polynômes ne vérifiant le troisième test, un quatrième test, où l'on vérifie si le poids de 10 Hamming des multiples de ces polynômes est supérieur eu égal à trois, - un classement des polynômes vérifiant le quatrième test dans une deuxième famille de polynômes générateurs. Par exemple, un polynôme générateur appartenant à la première famille peut être de la forme x'+ x 4+ x 2+1. Un polynôme générateur appartenant à la deuxième famille peut être choisi parmi x'+x6+x3+x+l, x'+x6+x4+x+l, x'+x+l, ou x'+x6+xs+x3+x. Selon un autre aspect, il est proposé un système de transmission d'un mot d'information binaire comprenant un émetteur et au moins un récepteur couplé via un moyen de transmission, ledit système étant apte à mettre en oeuvre le procédé tel que défini ci- dessus. D'autres avantages et caractéristiques des différents aspects apparaîtront à l'examen de la description détaillée d'exemples nullement limitatifs et des figures dont : - la figure 1 illustrant un système de transmission, et ; - la figure 2 illustrant à titre d'exemple le choix d'un polynôme générateur codé sur huit bits. Sur la figure 1, la référence SYS illustre un système de transmission de mot d'information binaire. Ce système SYS comprend un émetteur EM et un récepteur RC. Cet exemple n'est pas limitatif et le système SYS peut comprendre plusieurs récepteurs. L'émetteur EM et le récepteur RC sont couplés via des moyens de transmission MT. L'émetteur EM transmet au récepteur RC un mot d'information MI codé sur r bits (ici 12 bits), dans cet exemple la séquence 010011101101 �. A partir du mot d'information MI on génère une redondance CRC. Plus précisément, le mot d'information MI est transmis à un diviseur DIV qui procède à une division euclidienne du mot d'information MI par un polynôme générateur dont les caractéristiques seront décrites plus en détail ci-après. La redondance CRC est codée sur s bits (s On procède à un premier test, test 1, qui consiste notamment à vérifier si le polynôme P permet la détection d'au moins 126 bits erronés consécutifs, c'est-à-dire 2s-' ù 2 bits erronés consécutifs, avec s = 8. On procède au même test sur les polynômes P mais l'on vérifie dans ce cas ce qui permet la détection de seulement 125 bits erronés consécutifs, soit c'est-à-dire 2s-' ù 3 bits erronés consécutifs, avec s = 8. Pour les polynômes dont le résultat du test est OUI, on procède à un deuxième test, test 2, à savoir si le polynôme permet la détection de moins de 126 bits erronés consécutifs dans le cas où le test 1 concerne 126 bits, et de moins de 125 bits erronés consécutifs dans le cas où le test 1 concerne 125 bits. Si le polynôme P en question vérifie ces deuxièmes tests, il n'est pas un candidat pour être un polynôme générateur optimal. Par contre, les polynômes ne vérifiant pas ce deuxième test sont alors soumis à un troisième test, test 3, à savoir si le poids de Hamming des multiples de ces derniers est supérieur ou égal à 4. Si tel est le cas, les polynômes P sont alors classés dans une première famille, FAMILLE 1. Sinon, ils sont soumis à un autre test, test 4, afin de voir si le poids de Hamming des multiples de ces polynômes est supérieur ou égal à 3. Si tel est le cas, ces polynômes sont classés dans une deuxième famille, FAMILLE 2. Dans le tableau ci-dessous, sont répartis des exemples de polynômes appartenant à la FAMILLE 1 ou à la FAMILLE 2 telles que définies ci-dessus. Famille 1 Famille 2 x 7+x 5+x 4+x 2+x+1 x 7 +x+1 x '+x 6+x 5+x 3+x 2+1 x '+x 6 +1 x 7+x 5+x+1 x7+x3 +1 x '+x 6+x 2+1 x '+x 4 +1 x 7+x 4+x 2+1 x 7+x 5+x 4+x 3+x 2 +x +1 x7+x5+x3+1 x7+x6+x5+x4+x3+x2 +1 7+x 4+x 3+x 2 x +1 7+x 5+x 4+x 3 x +1 7+x 5+x 2 x +x+1 7+x 6+x 5+x 2 x +1 7 +x 6+x 5+x 3+x 2 x +x +1 7 +x 6+x 5+x 4+x 2 x +x +1 7+x 3+x 2 x +x+1 7+x 6+x 5+x 4+ x 1 7+x 5+x 3 x +x+1 7+x 6+x 4+x 2 x +1 7+x 6+x 3 x +x+1 7+x 6+x 4 x +x+1 Le tableau ci-dessus reprend les polynômes générateurs codés sur huit bits permettant d'avoir les meilleurs résultats, c'est-à-dire le 5 pourcentage d'erreurs non détectées le plus faible. Les polynômes générateurs x'+x6+x3+x+1 et x7+x6+x4+x+1 sont particulièrement efficaces pour la détection d'erreurs potentielles aléatoires qui peuvent arriver sur des transmetteurs sensibles aux perturbations électromagnétiques. Les polynômes x7+x+l, x7+x6+1, x7+x3+1 et x7+x4+1 sont quant à eux très efficace lorsque le circuit est de petite dimension c'est-à- dire quand la distance entre l'émetteur et le récepteur est petite. L'exemple ci-dessus est donné dans le cadre d'un polynôme générateur codé sur huit bits mais n'est absolument pas limité à cet exemple. Le procédé peut s'appliquer au choix d'un polynôme générateur de n bits, n étant un entier quelconque.10 REVENDICATIONS1-Procédé de transmission d'un mot d'information binaire (MI) codé sur r bits auquel on accole une redondance (CRC) codée sur s bits, s et r étant des nombres entiers, la redondance (CRC) signalant l'apparition de bits erronés à l'issue de la transmission, et étant obtenue en effectuant une division euclidienne du mot d'information (MI) à transmettre par un polynôme générateur codé sur au plus s bits, caractérisé par le fait que l'on choisit le polynôme générateur de manière qu'il respecte au moins l'une des conditions suivantes, à savoir que : - le poids de Hamming des multiples dudit polynôme générateur est supérieur ou égal à un seuil choisi, - le polynôme générateur permet la détection d'au moins 2s-1-3 bits erronés consécutifs. 2-Procédé selon l'une des revendications précédentes, dans lequel le polynôme générateur est codé sur 8 bits. 3-Procédé selon la revendication précédente, dans lequel ledit seuil est supérieur ou égal à 4. 4-Procédé selon l'une des revendications 2 ou 3, dans lequel le polynôme générateur permet la détection d'au moins 125 bits erronés consécutifs. 5- Procédé selon la revendication 2, dans lequel ledit seuil est supérieur ou égal à 3. 6-Procédé selon l'une des revendications 2 ou 5, dans lequel le polynôme générateur permet la détection d'au moins 126 bits erronés consécutifs. 7-Procédé selon l'une des revendications 2 à 6, dans lequel le choix d'un polynôme générateur comprend- pour chaque polynôme appartenant à un ensemble choisi, un premier test (testl), où l'on vérifie en parallèle si le polynôme permet la détection d'un premier nombre de bits erronés consécutifs égal à 126 d'une part et d'un deuxième nombre de bits erronés consécutifs égal à 125 d'autre part, - pour les polynômes vérifiant le premier test par rapport au premier ou au deuxième nombre de bits erronés, un deuxième test (test 2) où l'on vérifie si ces polynômes permettent la détection d'un nombre de bits erronés consécutifs • inférieur à 126 dans le cas où le polynôme permet déjà la détection de 126 bits erronés consécutifs, ou • inférieur à 125 bits erronés dans le cas où le polynôme permet déjà la détection de 125 bits erronés consécutifs, - pour les polynômes ne vérifiant pas le deuxième test (test 2), un troisième de test (test 3), où l'on vérifie si le poids de Hamming des multiples de ces polynômes est supérieur ou égal à 4, - un classement des polynômes vérifiant le troisième test dans une première famille de polynômes générateurs, - pour les polynômes ne vérifiant pas le troisième test (test 3), un quatrième test (test 4), où l'on vérifie si le poids de Hamming des multiples de ces polynômes est supérieur ou égal à 3, - un classement des polynômes vérifiant le quatrième test dans une deuxième famille de polynômes générateurs. 8-Procédé selon la revendication précédente, dans lequel un polynôme générateur appartenant à la première famille est de la forme x' +x4 +x' + 1. 9- Procédé selon la revendication 8 ou 9, dans lequel un polynôme générateur appartenant à la deuxième famille est choisi parmi x' +x6 +x3 +x+1 x' +x6 +x4 +x+l, x' +x+1 ou ' 6 5 3 x +x +x +x +x.30 10-Système de transmission d'un mot d'information binaire comprenant un émetteur (EM) et au moins un récepteur (RC) couplés via un moyen de transmission, ledit système étant apte à mettre en oeuvre le procédé selon l'une des revendications précédentes.5