Brevet FR2119958A1 — publié le 19720811

Cette invention a trait à un ensemble du type à registre à-décalage à réaction linéaire, et plus particulièrement à un tel ensemble pour traiter des multiplets de données dans lequel les bits sont traités en parallèle. On sait que les données binaires sous la forme d'un message peuvent 5 être après utilisation ou transmission, contrôlées pour les erreurs. On sait également qu'un registre à décalage peut être utilisé pour effectuer le codage des données transmises et le décodage des données reçues. Le registre à décalage est combiné conformément à un polynome générateur spécialement sélectionné. Le générateur de polynome détermine les connexions 10 de réaction qui doivent être réalisées dans le registre à décalage de façon à créer une division du polynome entrant de message binaire par le générateur de polynome. Le résultat de la division est un reste qui est défini comme le caractère de contrôle. Pour chaque message binaire différent il y a une combinaison unique d'un quotient et d'un reste. Ce reste, porte en lui 15 même suffisamment d'information de détection d'erreur pour être transmis seul comme les bits de contrôle. Comme on peut le voir par analogie avec la division décimale, le reste varie de façon cyclique sur l'éventail des polynomes de message. Ces codes sont donc appelés "codes cycliques". A cause de cette propriété cyclique, des messages ayant le même type de configuration 20 (jB contrôle restent numériquement éloignés les uns des autres. Il y a des règles bien connues pour sélectionner le polynome générateur afin d'avoir des propriétés précises de détection et de correction. Un registre à décalage identique est utilisé dans le décodage du message transmis. Le message est divisé par le même générateur de polynome pour 25 obtenir le reste. Si le message a été transmis correctement, le reste devrait être le même que le reste généré dans le registre à décalage pour le codage. Le brevet U.S. n° 3 465 287 décrit un registre à décalage et à réaction à plusieurs canaux adapté pour coder et décoder des codes cycliques dans lesquels les bits de données sont traités en parallèle. 30 Un objet de cette invention est de fournir un registre à décalage et à réinjection avec plusieurs canaux, amélioré, pour traiter des données parallèles. Un autre objet de cette invention est de fournir un registre à décalage à plusieurs canaux pour traiter des données d'entrée parallèles, dans lequel 35 le message d'entrée binaire est appliqué aux étages les plus hauts du registre à décalage. Un autre objet encore est de fournir un registre à décalage et à réaction avec plusieurs canaux dans lequel la circuiterie est simplifiée par découpage des éléments d'état du registre à décalage. 40 En résumé, ces objets sont réalisés avec un registre à décalage et à 71 44314 2 2119958 réaction à entrée parallèle pour coder et décoder un message binaire dans lequel plusieurs étages r du registre à décalape sont connectés selon l'expression suivante: Vf -x t co » Vf} (X t S ZJ CD] t t ou 10 Xt+f " [V V *r-1 't+f montre le contenu du registre à décalage au temps t + f où f est égal au nombre de canaux parallèles: X t = (x0* *1' Xr-f-13 v2 , r-f r-f+1 r-1, X = ix , x ,...,x J montre la division du vecteur d'état X.; t Zt " Czt+f-1' Zt+f-2' > z t+1 montre la séquence de données d'entrées [°l W 15 est une matrice de (r-f) rangées et r colonnes dans laquelle les f premières colonnes sont des 0 et les (r-f) colonnes suivantes forment une matrice d'identité (r-f); et G 20 D = 25 où G est le vecteur: ^ GQ » G^j t G2 » • ■ • * 1 qui est obtenu du générateur de polynome G(x) = G S G x B G x , ... t G x U 1 Z r et T est donné par: 71 44314 3 2119958 T = 0 0 Vi G0' G1' Gr-1 10 15 20 25 30 et la matrice est la puissance flemB jg ia matrice T. L'invention présente en outre l'avantage suivant: le registre à décalage parallèle formé conformément aux connexions ci-dessus est capable de traiter f bits en parallèle. Cette invention présente également l'avantage suivant: elle peut fonctionner avec tout code pouvant être utilisé avec des circuits de registre à décalage à réaction. D'autres objets, caractéristiques et avantages de la présente invention ressortiront mieux de l'exposé qui suit, fait en référence aux dessins annexés à ce texte, qui représentent un mode de réalisation oréféré de celle-ci. La figure 1 est un schéma d'un registre à décalage et à réaction de la technique antérieure adapté pour le codage et le décodage. La figure 2 est un schéma d'un registre à décalage à réaction avec plusieurs canaux pour coder et décoder une information d'entrée parallèle. Le circuit de registre à décalage série montré sur la figure 1 est 2 5 1B prévu sur la base du contrôle avec un polynome générateur 1 + x + x + x . Le polynome détermine les connexions de réaction dites aussi de réinjection 10 qui vont de la sortie 12 du registre à décalage aux entrées des différents étages du registre à décalage. Par exemple, la sortie 12 du registre à décalage est connectée à l'étage initial x du registre à décalage. Elle est également 2 connectée à un circuit exclusif OU 14 avant d'être connectée à l'étage x . De même, la réinjection est connectée à un circuit EXCLUSIF OU 16 juste 15 avant l'étage x du registre à décalage. Ces circuits OU Exclusif ont comme autre entrée, l'entrée venant de l'étage précédent du registre à décalage. 11 faut noter que l'entrée 18 au registre à décalage est à l'extrémité supérieure du registre à décalage plutôt qu'à l'extrémité inférieure comme cela était le cas dans le brevet US n° 3 465 287 mentionné plus haut. L'entrée 18 est connectée à un circuit OU Exclusif 20 avec la sortie du dernier étage 15 x du registre à décalage qui, dans cet exemple est connecte comme autre entrée du circuit OU. Bien que l'entrée 18 du registre de décalage se trouve 35 71 44Si 4 4 2119958 à l'extrémité supérieure, le contenu du registre à décalage est quand même décalé vers l'extrémité supérieure à partir de 1'extrémité inférieure. Ainsi, lorsque le dernier bit de la séquence de message est entré, le contenu du registre à décalage représente le caractère de contrôle ou reste. En 5 fait, la connexion du registre à décalage crée une division du message d'entrée binaire par le générateur de polynome GCx) qui est, comme cela 2 15 16 a été dit précédemment: 1 + x + x + x dans l'exemple de la figure 1. Le reste de -la division est le caractère de contrôle qui reste dans le registre. Le registre à décalage en série de la figure 1 a 16 étages 10 désignés par la lettre x et un nombre en indice qui indique la place du terme correspondant dans le générateur de polynome. Il faut noter que les termes qui ne sont pas zéro dans le générateur de polynome sont représentés dans le registre à décalage et à réinjection linéaire par les étages de registre ayant une connexion à partir d'une ligne de réinjection, alors 15 que, les termes ayant le coefficient 0 dans le polynome sont représentés par les étages de registre qui n'ont pas de connexion de réinjection directe. Le même registre à décalage peut être utilisé pour le décodage. Les bits de message reçus entrent dans le registre à décalage à l'entrée 16 à l'extrémité supérieure comme lorsque le registre à décalage est utilisé 20 pour le codage. Le caractère de contrôle généré dans le registre à décalage de codage est également décalé dans le registre à décalage de décodage. Lorsque le dernier bit du caractère de contrôle est entré, le contenu du registre à décalage de décodage représente le syndrome. Un syndrome qui n'est pas zéro indique une erreur dans les données reçues. 25 Supposons qu'un message binaire ayant une longueur de 16 bits: 110101 1 110010011 soit traité dans le registre à décalage de la figure 1, le tableau I suivant définit les différents stades de transition du registre. La figure 2 montre un registre à décalage et à réinjection avec plusieurs 30 canaux qui traite 8 bits en parallèle, ces bits formant un multiplet d'information. Dans ce circuit, un seul décalage avec un des 8 bits de la séquence d'entrée équivaut à 8 décalages successifs dans le circuit en série de la figure 1, avec la même séquence d'entrée. Le circuit est montré comme ayant une séquence binaire d'entrée de 8 bits parallèles z^, z^, ... z^. Ces 35 entrées sont introduites chacune dans un circuit OU Exclusif 22 associé à chacun des étages supérieurs du registre à décalage. L'entrée z^ es introduite dans le circuit OU Exclusif 22 qui a comme autre entrée la sortie de 15 l'étage x du registre à décalage. Les entrées désignées par des nombres dans un ordre croissant sont envoyées aux étages du registre à décalage 4° désignés par des nombres dans un ordre décroissant. La sortie 24 du registre TABLEAU I TABLEAU DES STADES DE TRANSITION DU REGISTRE A DECALAGE EN SERIE CONTENU DU REGISTRE A DECALAGE Temps t Entrée 0 X 1 X 2 x 3 X 4 x 5 x 6 x 7 x 8 X 9 X x10 x11 12 X 13 x x14 15 X 0 -- □ 0 D 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 D 0 0 1 2 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 □ 1 0 1 0 0 0 0 Q 0 0 0 0 0 0 4 1 1 0 1 1 Q 1 0 0 0 0 0 0 0 0 0 1 5 0 1 1 1 1 1 0 1 0 ' 0 0 0 0 D 0 0 1 6 1 0 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 7 1 1 0 0 1 1 1 1 0 1 0 0 0 0 0 0 1 8 1 0 1 0 D 1 1 1 1 0 1 □ 0 0 0 0 0 g 1 1 0 0 0 0 1 1 1 1 0 1 0 0 0 0 1 10 0 1 1 1 0 0 0 1 1 1 1 0 1 0 0 0 1 11 0 1 1 0 1 0 0 0 1 1 1 1 0 1 0 0 '1 12 1 0 1 1 0 1 0 0 0 1 1 1 1 0 1 0 0 13 o 0 0 1 1 0 1 0 0 Q 1 1 1 1 0 1 0 14 0 0 0 0 1 1 0 1 0 0 D 1 1 1 1 0 1 15 0 0 0 ' G 0 1 1 0 .. 1 D 0 0 1 1 1 1 0 16 1 1 0 1 0 0 1 1 0 1 0 0 0 1 1 1 0 . Caractère de Contrôle 1 0 1 0 0 1 1 0 1 0 0 0 1 1. 1 0 71 44314 6 2119958 à décalage est donc prise dans les étages supérieurs du registre qui, dans 8 15 le cas présent, sont désignés de x à x .Le circuit est prévu pour utiliser le même polynome générateur 1 + x2 + x''5 + x**6 que celui utilisé dans le registre en série de la figure 1. Il est évident que les différentes connexions 5 et l'agencement des étages du registre à décalage parallèle ne peuvent pas être facilement déduits de l'agencement du registre à décalage en série. Le tableau II est le tableau des stades de transition du registre à décalage et à réinjection avec plusieurs canaux de la figure 2 quand il traite le même message binaire c'est-à-dire: 10 1101011110010011 que celui qui était traité dans le registre à décalage de la figure 1 montré sur le tableau I. Le message binaire dans le registre à décalage parallèle est traité sous forme de 2 multiplets: 15 C 1 1 0 1 0 1 1 1) et ( 1 0 0 1 0 0 1 1 3 Le premier multiplet se compose de la première moitié (8) des bits du message de 1B bits. Chaque bit successif du multiplet correspondant aux entrées zQ ... z? du registre. Ceci a pour résultat que le circuit parallèle de la figure 2 produit le même caractère de contrôle que celui produit par 20 le circuit de la figure 1, mais, 8, fois plus vite. On verra d'après ce tableau qu'on arrive au même caractère de contrôle en deux décalages, chaque décalage étant provoqué par l'entrée d'un multiplet de 8 bits en parallèle comme cela a été décrit plus haut. Comme on peut le voir sur la figure 0 15 2, les étages x ... x du registre à décalage sont agencés en deux groupes 25 x ... x et x ... x15. Les sorties,du premier groupe x^ ... x sont envoyées aux étages du registre à décalage qui sont successivement 8 canaux plus loin. Par exemple, la sortie 36 de stade de registre x^ est envoyée à un Q circuit OU Exclusif 34 précédent l'étage x . De même, la sortie 36 de l'étage 1 9 x est envoyée au circuit OU Exlcusif 34 qui précède l'étage x . Cette 30 suite de connexions continue, la sortie de l'étage x étant connectée comme 15 une entrée a l'etage x du registre à décalage. Les sorties du second 8 15 groupe d'étages du registre à décalage x ... x sont envoyées directement aux circuits OU Exclusif 22 comme l'une des entrées, les autres étant les bits de message z^ ... z^. La sortie 30 de chacun de ces circuits OU Exclusif 35 22 est également connectée via une connexion de réinjection 32 aux deux canaux suivants du registre à décalage. Par exemple, la sortie 30 de l'étage Q x du registre à décalage est renvoyée du circuit OU Exclusif 22 au circuit 2 OU Exclusif 34 précédent l'étage x . De même, la sortie 30 du circuit OU g Exclusif 22 suivant l'étage x du registre à décalage est renvoyée aux 2 3 40 circtJits OU Exclusif précédant les étages adjacents x et x du registre TABLEAU II ^ LU TABLEAU DES STADES DE TRANSITION DU REGISTRE A DECALAGE ET A REINJECTION AVEC PLUSIEURS CANAUX ^ Numéro du décalage Entrée Contenu du registre à décalage Z0 Z1 Z2 Z3 Z4 Z5 Z6 Z7 0 x 1 x 2 3 x x 4 x 5 6 x x 7 x 8 X g X 10 x 11 x 12 13 X x 14 x x15 - 0 0 0 0 0 0 Q D 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 1 1 0 1 0 0 1 1 1 1 0 1 0 0 0 0 0 0 2 1 0 0 1 0 0 1 1 1 0 1 0 0 1 1 0 1 0 0 0 1 1 1 0 Caractère de contrôle 1 0 1 0 Q 1 1 0 1 0 0 0 1 1 1 0 hO vO en 00 71 44J14 0 2119958 10 15 20 à décalage. Cette suite de connexions continue, le circuit OU Exclusif 15 22 suivant l'étage x du registre à décalage étant connecté aux circuits 8 9 OU Exclusif 34 précédant les étages x et x . La sortie des additionneurs modulo- 2 ou circuit OU Exclusif 22 est envoyée dans un circuit OU Exclusif commun 26 qui a une sortie 28. La connexion de sortie 28 du circuit OU Exclusif commun 26 est connectée comme une entrée à l'étage x^ du registre à décalage dans le premier groupe d'étages et est également connectée au circuit 1 OU Exclusif 34 précédant l'étage x . Cette même sortie 28 du circuit OU Exclusif commun 26 est envoyée comme une entrée au circuit OU Exclusif 34 qui 15 précédé l'etage x . Ces connexions sont déterminées par la matrice de connexion 0, D étant dérivé du générateur de polynome. Afin de mieux comprendre le fonctionnement et les différentes connexions qui doivent être faites en construisant un registre à décalage et à réaction pour le codage et le décodage, nous allons exprimer mathématiquement la conception de celui-ci. Ainsi, le registre à décalage a, f canaux et peut traiter f bits en parallèle pour générer, dans le codage, un caractère de contrôle et pour générer, dans le décodage, le syndrome. Il est appréciable qu'un décalage dans le circuit parallèle équivaut à f décalages dans le registre à décalage série expliqué précédemment. Le nombre, f, est un nombre entier positif, plus petit que le degré, r, du polynome générateur qui est choisi. Le polynome générateur ou polynome de contrôle est décrit par: Glx) = Gn + G„x + G_x 0 1 2 + G x r (1) le vecteur d'état X^= tx^, x^. r-1 t définit le contenu du circuit 25 de registre à décalage au temps t. La matrice du polynome G(x) est dénommée par T. La matrice T montrée ici est la matrice pour les connexions données dans le registre à décalage série précédemment décrit. Si Z^_ définit le bit de données entrant dans le registre à décalage série au temps t, le fonctionnement de décalage du registre à décalage série est alors donné 30 par l'équation de matrice modulo-2: Xt+1 = V 8 ztG l2) 35 où G est le vecteur (G^, V V .., G . ] et r-1 0 1 I O • • a 0 0 1 ...0 T = 0 0 0 ...1 Go G1 G2'"Gr-1 (3) 71 44314 9 2119958 10 15 20 25 Supposons que Z, Z «j, Z^. sont les f bits de données (un multiplet) entrant successivement dans le registre à décalage série pendant f opérations successives de décalage. Le contenu du registre à décalage à la fin des f décalages est défini par le vecteur X . En utilisant l'équation (2) f fois, on obtient: X, _ = XJTf 8 z,. GTf_1 0 z . GT^ 2 0 ... z,. ^ „G t+f t t t+1 t+f-1 (4) i iLème Dans cette équation T est j puissance de la matrice T. Si Z^ définit la séquence de données d'entrée comme suit: Zt = Czt+f-1' Zt+f-2' "" Zt+1' Zt] Si D définit la matrice divisée suivante: D = (5) L'équation (4) peut alors se réécrire ainsi: rf X 't+f V Zt° (6) Le circuit réalisé à partir de l'équation (6) a la propriété suivante: avec un multiplet d'entrée Z^ (f bits en parallèle), il passe de l'état en un seul décalage. Ceci est l'opération équivalente X. à l'état X t t+f à f décalages du registre à décalage série avec les mêmes données d'entrée introduites en série. La matrice T peut être divisée comme suit: 0 r-1 T = (7) 30 0{j j es-t ia matrice d'identité m x m. En général, on peut montrer que f m T est égale à la matrice divisée suivante: 71 44314 10 2119958 0 I „ r-f D (8) 10 15 où D est donné par l'équation (53 ci-dessus. La matrice D peut être obtenue par la méthode suivante utilisant l'exemple donné dans l'explication précédente du registre à décalage série où le polynome générateur 1 + x2 + x''5 + x^6 2 f-1 est utilisé. Notons que les vecteurs G, GT, GT , ... GT représentent le contenu du registre à décalage série, le vecteur G étant décalé f-1 fois. Le tableau III établit la liste de ces vecteurs pour l'exemple du f polynome générateur. Les matrices D et T peuvent être obtenues en utilisant le tableau III et les équations (5) et (8). Il faut noter que la réalisation f de l'équation (63 produit un cirdcuit parallèle. La matrice T contient D comme sous-matrice. On a trouvé que la division appropriée du vecteur d'état a pour résultat me économie considérable dans la circuiterle pour la version parallèle du registre à décalage à réaction. Le vecteur d'état peut être divisé en deux parties : 1 xt * lxt [9) ou = Cx0. Xy Vf-A (103 20 2 X, = (x _, x . .i ..., x .), t r-f r-f+1 r-1 t (113 En utilisant les équations (83 et (9), l'équation (63 peut se réécrire corcme suit: Xt+f = Xt (0 Vf5 8 cxt V tD1 (12) 25 30 La réalisation de l'équation (12) produit le circuit parallèle de la figure 2. Ainsi, il faut savoir qu'avec tout polynome G(x) de degré r, un registre à décalage parallèle peut être généré qui traite f bits en parallèle (f ^ r). Il faut également savoir que la circuiterie peut être réduite par une division appropriée des matrices dans l'équation de transition d'état pour le circuit parallèle Dans le cas où f > r, la théorie peut être appliquée sans changement, excepté que la division sera appliquée à la matrice D Dlutôt f f qu'à la matrice T .étant donné que D dans ce cas, contient T comme l'une de ses divisions. -4 -t* TABLEAU III "k* ou RANGEES DE LA MATRICE D T* CONTENU DU REGISTRE EN SERIE ^ Nombre de décalage 0 x 1 X 2 X 3 x 4 x 5 x B x 7 X 8 x a x 10 X x11 x12 x13 x14 x15 0 G 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 GT 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 2 GT2 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 3 GT3 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 4 i— CD 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 5 GT5 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 6 GT6 1 1 0 0 D 0 0 1 1 0 0 0 0 0 0 1 7 GT7 r 1 0 D 0 0 o- 0 1 1 0 0 0 0 0 1 «X> Ln 1 44314 12 2119958 Bien que l'on ait décrit dans ce qui précède et représenté sur le dessin, les caractéristiques essentielles de l'invention appliquées à un mode de réalisation préféré de celle-ci, il est évident que l'homme de l'art peut y apporter toutes modifications de forme ou de détail qu'il juge utiles, sans pour autant sortir du cadre de ladite invention. 71 44314 13 2119958 REVENDICATIONS 10 1.- Ensemble permettant d'effectuer aussi bien le codage que le décodage d'informations en parallèles, caractérisé en ce qu'il comprend une pluralité d'étage de registre à décalage dont les connexions vérifiant l'expression Vf ■ Xt1 I Vf10 dans laquelle: Xt+f = (X0' X1* "" Xr-13 t+f définit le contenu du registre à décalage au temps t » f avec f égal au nombre de canaux parallèles f £ r, en ce que ce registre à-décalage comprend les deux parties vérifiant les relations: 1 - CxQ, x1. " Vf-11, Xt " (xr-f' xr-f+1* "* " xr-1Jt 15 20 et où (0 w est une matrice de (r-f} rangées et r colonnes ou les premières colonnes f sont des zéros et les Cr-f) colonnes suivantes forment une matrice d'identité 1 qui définit les connexions correspondant a la premiere partie X du registre et où Z^ fléfinit la séquence de données d'entrée Z^_ = {zt+f-1* zt+f-2* Zt+1' Zt]' ° définit la matrice: 25 D = où G est le vecteur : (G„, G., G„, ...» G . ) 0 12 r-1 qui est obtenu à partir du polynome générateur: GCxî = G 0 2 r G/) x @ G2 x , ..., G^x "f 3° et T et T sont des matrices définies comme suit: 71 44314 14 2119958 0 Ir-1 O CD I S G2 * • Gr-1 èrns et T est le f puissance de la matrice T. 2.- Ensemble conforme à la revendication 1, caractérisé en ce que la séquence de données d'entrée parallèle z à z est envoyée aux sorties des étages r-1 r-2 r-f+1 x , x , ..., x du registre eespectivement. 3.- Ensemble conformë à la revendication 2, caractérisé en ce que les entrées r r-f+1 Zg a z ^ et les sorties de l'etage correspondant x à x sont respective ment sommées module 2 dans un circuit OU Exclusif. 10 30 4.- Ensemble conforme à la revendication 1 dans lequel la matrice D est divisée au lieu de la matrii les étages r lorsque f > r. f divisée au lieu de la matrice T , pour définir les interconnexions entre 5.- Ensemble conforme à une quelconque des revendications précédentes, caractérisé en ce que le reste obtenu dans le registre à décalage fonctionnant 15 comme codeur y est envoyé pour produire ainsi un syndrome d'erreur qui doit être égal à 0 si il n'y a pas d'erreur dans le message reçu. 6.- Ensemble effectuant aussi bien le codage que le décodage destiné à opérer sur plusieurs f entrées parallèles selon un polynome générateur donné pour produire un caractère de contrôle, caractérisé en ce qu'il comprend r étages 20 de registres à décalage X ... X , chacun correspondant à l'un des termes du polynome générateur, une première pluralité de moyen d'addition module 2 connectant chacun f entrées de données Zt = Czt+f-1* Zt+f-2* Zt+1* Zt3 25 du registre à décalage aux sorties des, f autres étages du registre: Xt = Cxr-f Xr+f+1J xr-1}t conforment à la relation zt+f-1 SUr Vf Zt+f-2 SUr xI"f+1 Zt SUr Xr-1; une seconde pluralité de moyen d'addition modulo 2 connectant chaque sortie de la première pluralité de moyen d'addition modulo 2 aux différents 71 44314 15 2119958 étages de registre déterminés conformément aux coefficients non nuls dans la matrice de donnexion D; et 0 1 r-f-1 plusieurs connexions r-f, une issue de chaque étage X , X , X f f+1 r-1 et reliée aux étages respectifs X , X , X .... X