Brevet FR2669445A1 — publié le 19920522

Il à Dispositif prévu pour le traitement de l'algorithme de Viterbi comprenant un processeur et un opérateur spécialisé. La présente invention concerne un dispositif comprenant un processeur qui est prévu notamment pour effectuer le traitement de l'algorithme de Viterbi. L'algorithme de Viterbi connu en traitement numérique du signal, est employé dans plusieurs domaines o il s'agit de faire l'estimation de la valeur des bits d'une suite numérique Parmi ces domaines figurent, entre autres, le décodage convolutionnel et l'égalisation en démodulation numérique. Cet algorithme peut être mis en oeuvre au moyen d'un processeur de traitement de signal numérique de type généraliste. Un tel processeur n'est pas particulièrement prévu pour le traitement de cet algorithme et nécessite, pour ce faire, un très15 grand nombre d'instructions Le temps de traitement, lié au nombre d'instructions à effectuer, est donc important. Il est par ailleurs courant, dans un circuit de traitement du signal, qu'il soit nécessaire d'effectuer des traitements supplémentaires. Une première solution consiste à prévoir, le processeur de traitement du signal avec une puissance permettant d'effectuer le traitement de l'algorithme de Viterbi et ces traitements supplémentaires A supposer qu'un processeur doté d'une telle puissance soit disponible, il sera nécessairement assez coûteux. Une deuxième solution consiste à confier le traitement de l'algorithme de Viterbi à un composant spécifiquement prévu à cet usage, le processeur de Viterbi commercialisé par FUJITSU sous la référence MB 86620, par exemple Dans ce cas, le circuit de traitement du signal nécessite au moins deux composants, sa taille30 est donc plus importante et son prix plus élevé De plus il se prête mal à une miniaturisation, indispensable dans certaines applications. La présente invention a ainsi pour objet un dispositif prévu notamment pour le traitement l'algorithme de Viterbi, ce dispositif n'employant pas de composant spécialisé mais un processeur de -2- signal de type généraliste pour lequel la puissance nécessaire à ce traitement a été réduite Ce dispositif est également conçu pour être intégré dans un seul composant. Le dispositif selon l'invention comprend un processeur et est prévu pour le traitement de l'algorithme de Viterbi, cet algorithme étant défini par sa longueur de contrainte de valeur n+l et ses 2 états associés à des suites de bits, le traitement ayant pour objet l'estimation d'une suite initiale de bits b(i), à partir d'une suite transmise résultant d'une opération de transmission effectuée sur la suite initiale Il comprend de plus un opérateur pour établir la métrique maximale au rang r de l'état E dénommée J Met (Ej), pour r supérieur à n, et le (r-n)ième bit de la suite correspondant à cette métrique, à partir de valeurs d'entrées que sont les métriques maximales au rang r-1 des états E 2 k et E 2 k+ notées Metr_l (E 2 k) et Metr l(E 2 k+l), et les probabilités conditionnelles en rapport auxdits états E 2 k, E 2 k+l que le rième bit des suites associées à ces états ait une valeur déterminée dénommées Pr(b(r)=O/E 2 k) et Pr(b(r)=O/E 2 k+l) par exemple, k étant n-i n-i égal à 2 j pour tout j inférieur à 2 nl et valant 2 (j-2) pour tout j supérieur ou égal à 2 n, de sorte que Metr(Ej) prenne la valeur de la plus grande des deux expressions suivantes, la première étant Metr l(E 2 k)+Pr(b(r)=O/E 2 k) et la seconde étant Met (E 2 k+l) + Pr(b(r)=O/E 2 k+l) L'opérateur décharge ainsi le processeur de certaines opérations qui sont effectuées un très grand nombre de fois avec des moyens relativement simples. De plus dans le dispositif prévu pour le traitement de l'algorithme de Viterbi comprenant un processeur, l'opérateur comprend des moyens additionnels pour établir quel que soit j30 inférieur à 2 n-1 à partir des valeurs d'entrée non seulement la métrique maximale au rang r de l'état Ej Metr(Ej) et le (r-n)ième bit correspondant, mais également la métrique maximale au rang r de l'état E j+a Metr(Ej+a) et le (r-n)ième bit correspondant o a vaut n-l1 + 2 r-, de sorte que Metr(Ej+ a) prenne la valeur de la plus grande des deux formules suivantes, la première étant Metr l(E 2) - Pr(b(r)=O/E 2 j) et la seconde étant Met r (E 2 j+l) - -3- Pr(b(r)=O/E 2 j+l) Dans un premier mode de réalisation du dispositif prévu pour le traitement de l'algorithme de Viterbi comprenant un processeur, l'opérateur étant relié au processeur par au moins un bus de données et un bus de commande, il comprend quatre registres d'entrée dont les entrées sont connectées chacune à l'un des bus de données, le premier étant prévu pour recevoir la valeur de Met 1 (E 2 j), le second la valeur de Pr(b(i)=O/E 2 j), le troisième la valeur de Met r 1 (E 2 j+l) et le quatrième la valeur de10 Pr(b(i)=O/E 2 j+ 1), il comprend également un premier et un deuxième circuits de calcul prévus pour produire respectivement un premier et un deuxième résultats prenant la valeur en réponse à un signal de commande de la somme ou de la différence des contenus respectivement des deux premiers registres d'entrées et des deux15 derniers registres d'entrée, il comprend un comparateur délivrant un signal de sortie de valeur 1 lorsque ledit premier résultat est inférieur audit deuxième résultat et de valeur O dans le cas contraire, un multiplexeur commandé par le comparateur produisant comme signal de sortie celui des résultats qui présente la plus20 forte valeur, il comprend de plus trois registres de sortie dont les sorties sont raccordées chacune à l'un des bus de données, le premier et le deuxième recevant le signal de sortie du multiplexeur et étant prévus pour enregistrer les valeurs de respectivement Metr(E) et Met (E j+a), le troisième recevant le signal de sortie25 du comparateur qui est le (r-n)ième bit des suites correspondant à ces métriques, et il comprend un module de commande prévu pour commander ses différents éléments en fonction des informations adressées par le processeur sur le bus de commande. De plus, dans le dispositif prévu pour le traitement de l'algorithme de Viterbi comprenant un processeur, le troisième registre de sortie est prévu pour enregistrer le (r-n)ième bit de toutes les suites correspondant aux 2 N métriques maximales à un rang déterminé. En outre, dans le dispositif prévu pour le traitement de l'algorithme de Viterbi, comprenant un processeur, ce processeur -4comprenant deux bus de données, les premier et troisième registres d'entrée ont leur entrée connectée au premier des bus de données, les deuxième et quatrième registres d'entrée ont leur entrée connectée au second bus de données, tandis que lesdits premier et5 second registres de sortie ont leur sortie connectée chacune à un bus de donnée distinct. De manière avantageuse, dans le dispositif prévu pour le traitement de l'algorithme de Viterbi comprenant un processeur, l'opérateur comprend des moyens supplémentaires pour établir les10 probabilités conditionnelles en rapport aux états E 2 k, E 2 k+l que les rièmes bits des suites associées à ces états ait un état déterminé en fonction des pondérations des bits de la suite transmise liés à ces rièmes bits, du nombre k associé aux états E 2 k' E 2 k+l et des relations définissant l'opération de15 transmission. Ainsi, l'opérateur, s'il comprend plus d'éléments, décharge également le processeur de ces calculs afin de diminuer encore le temps qu'il consacre à ce traitement. Dans un deuxième mode de réalisation du dispositif prévu pour le traitement de l'algorithme de Viterbi comprenant un processeur, l'opérateur étant relié au processeur par au moins un bus de données et un bus de commande, il comprend des registres de transfert dont les entrées sont reliées chacune à l'un des bus de données, ces registres de transfert étant prévus pour mémoriser25 chacun une des pondérations, et une unité arithmétique cablée connectée aux sorties des registres de transfert, ayant accès à la valeur j identifiant un état, et établissant les relations définissant l'opération de transmission pour produire les probabilités conditionnelles, il comprend quatre registres30 d'entrée, le premier dont l'entrée est raccordée à l'un des bus de données étant prévu pour recevoir la valeur de Met 1 (E 2 j), le second mémorisant la valeur de Pr(b(r)=O/E 2 j) fournie par l'unité arithmétique, le troisième dont l'entrée est raccordée à l'un des bus de données étant prévu pour recevoir la valeur de Met 1 (E 2 j 1)35 et le quatrième mémorisant la valeur de Pr(b(r)=O/E 2 j) fournie -5- par l'unité arithmétique, il comprend également un premier et un deuxième circuits de calcul prévus pour produire respectivement un premier et un deuxième résultats prenant la valeur en réponse à un signal de commande de la somme ou de la différence des contenus respectivement des deux premiers registres d'entrée et des deux derniers registres d'entrée, il comprend un comparateur délivrant un signal de sortie de valeur 1 lorsque le premier résultat est inférieur au deuxième résultat et de valeur O dans le cas contraire, et un multiplexeur commandé par le comparateur produisant comme signal de sortie celui des résultats qui présente la plus forte valeur, il comprend de plus trois registres de sortie dont les sorties sont raccordées chacune à l'un des bus de données, le premier et le deuxième recevant le signal de sortie du multiplexeur et étant prévus pour enregistrer les valeurs de respectivement Met r(Ej) et Metr(E ja), le troisième recevant le signal de sortie dudit comparateur qui est le (r-n)ième bit des suites correspondant à ces métriques, et il comprend un module de commande prévu pour commander ses différentes éléments en fonction des informations adressées par le processeur sur le bus de commande. De plus, dans le dispositif prévu pour le traitement de l'algorithme de Viterbi comprenant un processeur, le troisième registre de sortie est prévu pour enregistrer le (r-n)ième bits de toutes les suites correspondant aux 2 N métriques maximales à un rang déterminé. En outre, dans le dispositif prévu pour le traitement de l'algorithme de Viterbi comprenant un processeur, le processeur comprenant deux bus de données, les registres de transfert ont leurs entrées réparties sur le premier et sur le second bus de données, le premier et le troisième registres d'entrées ont leurs entrées reliées chacune à un bus de données distinct, tandis que les premier et second registres de sortie ont leur sortie connectée chacune à un bus de données distinct. Quel que soit le mode de réalisation adopté, on peut prévoir dans le dispositif prévu pour le traitement de l'algorithme de -6- Viterbi comprenant un processeur, que certains des éléments de l'opérateur soient implantés dans le processeur. Une première application du dispositif prévu pour le traitement de l'algorithme de Viterbi comprenant un processeur consiste, l'opération de transmission étant un codage convolutionnel, à effectuer le décodage de la suite transmise. Une deuxième application du dispositif prévu pour le traitement de l'algorithme de Viterbi comprenant un processeur consiste, l'opération de transmission introduisant une interférence intersymbole dans la suite transmise, à effectuer l'égalisation de cette suite. Les différents objets et caractéristiques de la présente invention apparaîtront maintenant plus précisément dans le cadre de la description d'exemples de réalisation donnés à titre non15 limitatif en se référant aux figures annexées qui représentent la figure 1, le schéma d'un circuit correspondant à un premier mode de réalisation de l'invention, la figure 2, le schéma d'un autre circuit correspondant à un deuxième mode de réalisation de l'invention. Les éléments communs aux deux figures seront affectés d'une seule référence. L'algorithme de Viterbi apporte une solution au problème de l'estimation d'une suite initiale à partir d'une suite transmise. La suite transmise est obtenue après modification de la suite initiale par un milieu de transmission, par un codage ou par tout autre moyen dont l'effet est connu On adoptera le terme générique d'opération de transmission pour qualifier ces modifications. L'estimation se fait par le calcul des probabilités, pour chaque suite initiale, que celle-ci produise la suite transmise La suite30 initiale solution est celle qui présente la plus forte probabilité. L'algorithme de Viterbi sera maintenant exposé de manière à introduire les grandeurs qui font l'objet d'un traitement dans l'invention. Les grandeurs d'entrée sont L'ensemble des Lt probabilités caractérisant la suite -7- transmise de longueur Lt, chacune de ces probabilités caractérisant la valeur d'un bit de la suite transmise BT (i), o i prend toutes les valeurs comprises entre 1 et Lt Les paramètres caractérisant l'environnement dans lequel s'est effectué l'opération de transmission. Dans l'algorithme, on utilise plus généralement la notion de pondération, ceci pour des raisons de normalisation des calculs La pondération est définie par rapport à la probabilité de valeur d'un bit comme l'indique la formulation ci- dessous:10 Pond (BT (i)) = 92 Probabilité (BT (i)=l)-ll Pondmax tl- 2 Probabilité (BT (i)=OJl Pondmax On considère donc que l'on a en entrée la suite des Lt pondérations correspondant aux Lt probabilités de valeur des bits de la suite-transmise, chacune de ces pondérations pouvant varier15 entre pondmax et -pondmax Les paramètres caractérisant l'environnement dans lequel s'est effectués la transmission permettent de définir la relation existant entre les bits de la suite initiale et les bits de la suite transmise Il permettent donc de définir une redondance éventuelle qu'introduit la20 transmission On considère donc que la longueur de la suite transmise Lt vérifie: Lt = L T, L étant la longueur de la suite initiale, et T l'ordre de redondance. Plus précisément, ces paramètres définissent les relations entre un bit BT(i) de la suite transmise, et les n+l bits b(i) de la suite initiale dont il dépend Il y a donc T relations qui peuvent s'exprimer par: BT (i T) = F 11 b (i), b (i-l), b(i-n)3 BT (i T+l) F 21 b (i), b(i-l), bit(i-n)l30 BT (i T+T-l) = FTE(b(i), b (i-l), b (i-n)2 Par exemple: le codage convolutionnel de taux 1/T introduit une redondance d'ordre T et décrit T relations entre les bits transmis et ceux à transmettre. 35 la transmission d'un signal numérique sur des voies -8- affectées d'interférence intersymbole n'introduit pas de redondance et ne définit qu'une seule relation (T=l et donc Lt =L). Les grandeurs d'entrée permettent d'obtenir en sortie de l'algorithme de Viterbi, la suite des L bits correspondant au maximum de vraisemblance d'être la suite initiale correspondant à la suite transmise. L'application directe de la règle du maximum de vraisemblance voudrait que l'on calcule, pour une suite de longueur L, les 2 L probabilités pour les 2 suites possibles, ce qui nécessiterait un temps considérable au vu des ordres de grandeur de L L'algorithme de Viterbi va permettre de résoudre le problème en réduisant fortement le nombre de calculs de probabilités Cette réduction est obtenue par l'estimation progressive (bit par bit) des suites les plus probables en prenant en compte les relations liant chaque bit15 transmis et les n+l bits à transmettre correspondants pour le calcul des probabilités de vraisemblance des suites. A partir de ces T relations, on définit T nouvelles relations qui décrivent T expressions de la probabilité que le bit b(i) de la suite initiale soit égal à X, symbole binaire, connaissant ses n20 bits antécédents et la pondération des bits transmis: Pr 1 (b (i)= X) = G 1 t Pond (BT(i T), X, b(i-l),,b(i-n)l Pr 2 (b(i)= X) = G 2 t Pond (BT (i T+ l), X, b(i-l),,b(i-n)3.-2 ee 2 l m e e e e m e ee m e l e e e e e e Pr T (b(i) = x) = GT lPond (BT(i T+T-1), X, b(i-1),,b(i- n)3 Il est délicat de donner une description générale du passage des fonctions F aux fonctions G (m=l à T) car ces relations m m dépendent uniquement de l'opération de transmission Néanmoins, la connaissance des fonctions F et de la pondération des bits m transmis entraîne implicitement celle des fonctions G m Des exemples concrets sont décrits par la suite. Les fonctions G définissent une expression des probabilités mde valeur de b(i) qui vérifie: de valeur de b(i) qui vérifie: -9- Pr (b(i)= X) = ú 2 Proba (b(i)=X)-13 *Gmax m = tl-2 Proba (b(i)=l-X)I*Gmax donc: Pr (bit(i)=X) = Pr (bit(i)=l-X) m m On définit alors une expression de la probabilité totale de la valeur de b(i) par: T Pr (b(i)=X) = (l/T) 7 Pr (b(i)=X) m=l m Cette expression correspond donc à la probabilité conditionnelle de valeur de b(i) connaissant les N bits antécédents à b(i) On prend comme notation: Pr (b(i)=X/n). On définit ensuite la métrique de la suite à estimer formée des L symboles binaires Xi par: L Met (suite) =il Pr (b(i)=Xi/n) ( 1) = Pour les N premiers bits de la suite initiale: Ces bits forment une soussuite numérique de la suite à estimer de longeur n On effectue alors le calcul des 2 métriques des 2 suites possibles selon la formule ( 1). Pour le bit suivant: Il y a 2 n+ suites possibles, on réduit ce chiffre aux 2 N suites les plus probables par élimination de suites éronnées suivant le critère de la vraisemblance maximale de ces suites, donc de la plus forte métrique, en se servant des calculs des métriques précedentes par récurence. On choisit la suite de n+l bits qui a la plus forte métrique entre les deux suites binaires suivantes o les bits b (i= 2 à n+l) sont figés: SO: O, b 2, b 3,, bn, bn+ Sl: 1, b 2, b 3,bn, bn+l -10- Pour effectuer ce choix, il faut calculer les deux métriques des deux suites SO et Si, Met (SO) et Met (Sl), par la formule de récurence suivante: Met (SO) = Met (O,b 2,b 3,,bn) + Pr(bit(n+ 1)=bn+ 1 /n) Met ( 51) = Met ( 1,b 2,b 3,,bn) + Pr(bit(n+ 1)=bn+ 1 /n) On connait les métriques situées à droite de l'égalité par les calculs précédents Il reste donc à calculer Pr(b(n+l)=bn+ 1 /n) qui représente une expression de la probabilité conditionnelle de bn+ 1 connaissant la valeur des N bits précédents. On garde alors en mémoire la suite de métrique maximale, sa métrique associée, et le choix du premier bit de la suite de métrique maximale. Il y a 2 couples de suites SO et 51 possibles On effectue donc ce processus 2 fois et on voit donc que l'on a calculé les 2 n métriques correspondant aux 2 suites les plus probables parmi les 2 n+l proposées en effectuant des choix sur la valeur du premier bit de chacune de ces suites. Ces choix correspondent à la probabilité maximale de vraisemblance du premier bit dans les suites On a donc fixé les valeurs des premiers bits des 2 N suites présélectionnées formées de n+ 1 bits. Pour les bits suivants Pour le bit suivant (qui correspond au n+ 2 i 2 me), on effectue le même processus que celui décrit dans le paragraphe précédent qui va permettre d'estimer les 2 N suites les plus probables parmi les 2 n+ suites formées des n+ 2 premiers bits. En effet, il ya au total 2 n+l suites possibles formées par les n+ 2 premiers bits, car on prend en compte les choix du premier bit sur ces suites qui ont été fait précédemment On a donc seulement n+ 1 bits variables sur ces suites, donc 2 n+ 1 combinaisons possibles. On va, comme précédemment, estimer les 2 N suites les plus probables parmi les 2 n+ proposées, en fixant le deuxième bit des -11- n+l -é 2 n+ 1 suites possibles: On choisit la suite de n+ 2 bits qui a la plus forte métrique entre les deux suites binaires suivantes o les bits b (i= 3 à n+ 2) z sont figés ainsi que les bits Blso, et Bisl, qui sont les premiers bits choisis précédemment: SO': Bl so O,b 3,bn+l bn+ 2 so' '" n+l'bn+ 2 Sl': Blsl,l,b 3,,bn+l,bn+ 2 On calcule alors les deux métriques des deux suites SO' et Sl', Met (SO') et Met (SV'), par la formule de récurence suivante avec les deux suites SO'" 1, 511 ", caractérisant les N bits antécédents et avec les probabilités conditionnelles liées à ces suites: SO'': O, b 3,bn+ 1 51 ": 1, b 3 bn+ 1 Met (SO') = Met (Blso, O,b 3,bn+) + Pr (b(n+ 2)=b n+ 2/SO'') Met (Si') = Met (Blsl, 1, b 3 bn+ 1) + Pr (b(n+ 2)=bn+ 2/Sl'') On connatt les métriques situées à droite de l'égalité par les calculs précédents, il ne reste donc qu'à calculer les probabilités conditionnelles. On garde alors en mémoire la suite de métrique maximale, sa métrique associée, et le choix du premier bit de la suite de métrique maximale. On effectue donc ce processus 2 fois pour les 2 suites possibles SO' et Sl' et on voit, comme précédemment, que l'on a calculé les 2 suites les plus probables parmis les 2 n+ proposées,30 en effectuant des choix sur la valeur du second bit des 2 n+l suites, ces choix correspondant à la probabilité maximale de vraisemblance du bit dans la suite. Pour les bits suivants (de rang n+ 3 à L), on va effectuer le n même processus qui va permettre de choisir les 2 suites les plus probables en choisissant, l'un après l'autre, les L-n premiers bits des 2 suites suivant la vraisemblance maximale de ceux-ci. -12- A la fin de l'algorithme, on choisit alors la suite solution qui correspond à celle possédant la plus forte vraisemblance, c'est à dire la plus forte métrique, parmis les 2 suites proposées. On définira maintenant des variables qui seront utiles par la suite. La longueur de contrainte est égale à n+l et définit le nombre de bits consécutifs à transmettre reliés par les relations traduisant l'opération de transmission. Un état de l'algorithme définit une suite possible de longueur 1 supérieure à n, ne possédant que ses N derniers bits variables. Chaque état E caractérise donc une suite Sj possible de N bits et J peut être représentée par le nombre j: Sj.'b n+,b l bl È l-n+l' -n+ 2 ',b'1 n -1 j = i_=O b 1 i 2-i Dans une formulation plus génerale de l'algorithme de Viterbi, il s'agit de choisir l'une des deux suites suivantes S Oj, Slj o les bits BS Oj (i) et B Slj(i) (i=l à r-n-l) ont été fixés par les20 étapes précédentes et o r représente un rang: S Oj: BS Oj ( 1), BS Oj ( 2),,BS Oj (r-n-l),O,brn+ 1,brlbr Slj: B Slj ( 1), B Slj ( 2),,B Slj (r-n-l),l,b n+,br l,b Ces deux suites binaires de longueur r correspondent au même état E car elles possèdent les mêmes N derniers bits; par J convention, les métriques qui leur sont associées sont dites de rang r et notées Met r On calcule alors, pour chaque j (j=O 2 -1), les deux métriques au rang r, Metr (S Oj) et Metr (Slj) des deux suites S Oj et Slj, et on choisit comme suite la plus probable celle qui a la plus forte métrique: Metr (S Oj) = Metr 1 (SO'j) + Pr (b(r)=b /SO"j) Metr (Slj)= Metr_ 1 (Si') + Pr (b(r)=br/Sî") -13- avec: SO': BSO ( 1), BS Oj, ( 2),,BS Oj (r-n-l), O, brn+l,br 1 J j Sl'j: B Sl ( 1), B Sl ( 2), B Slj(r-n-1), 1, brn+ l,,br 1 SO":O, b b s r-n+i 1 ',r-i Sl":1, b b j r-n±l"' ' r-i En reprenant la définition d'un état d'une suite donnée précédemment et en introduisant le nombre c = b 2, on voit que r les suites SO' et Si'j correspondent respectivement aux états E 2 j-c et E 2 j+l-c de suites retenues lors de l'étape précédente dont les derniers bits forment respectivement les suites SO"' et Sl" On peut alors définir une nouvelle formulation équivalente à la précédente en remplaçant l'identification d'une suite par l'état qui lui est associé o Metr(S Oj) et Metr(Slj) sont respectivement qui r jr j notées Met Or(Ej) et Metlr(Ej): Met O (Ej) = Metr_ 1 (E 2 j-c) + P (b(r) = br /E 2 jc) Metlr(Ej) = Metr 1 (E 2 j+l-c) + P (b(r)=br/E 2 j+lc) r r-i 2 j+ 1-c r r 2 j-i 1-c On définit alors la métrique maximale au rang r de l'état E. 3 de la suite par la relation suivante o MAX CA,Bl représente la plus grande des deux valeurs A, B: Met (Ej) = MAX (Metlr (Ej), Met O (Ej) à On choisit le (r-n)ième bit des 2 N suites solutions suivant la métrique maximale. On voit donc que le processus revient à calculer les 2 n métriques maximales, au rang r, des états E (j = O,,2 n-1) des 2 N suites de r bits les plus probables à partir des 2 N métriques maximales au rang r- 1 des 2 N états des suites de r-1 bits les probables calculées précédemment. Considérons maintenant deux états particuliers Ej, E j+a pour j inférieur à 2 n-1 qui correspondent à deux suites de bits différant n-i uniquement par leur dernier bit, c'est-à-dire lorsque a = 2 Ej = br-n+ l' br-n+ 2 ' br-2 ' br-l' O E =b, b, j+a r-n+l' r-n+ 2 ' ' Br-2 ' br-l'1 Pour les métriques associées à l'état Ej, le nombre c précédemment défini est nul puisque son dernier bit br est nul On -14- peut donc reformuler les métriques au rang r associée à l'état E: MetOr (Ej) = Metr (E 2 j) + Pr (b(r) = O/E 2 j)J Met Or (Ej) = Metr-l (E 2 j+l) + Pr (b(r) = O/E 2 j) Metir (Ej) = Metr_ 1 (E 2 j+I) +i Pr (b(r) = O/E 2 j+I) Pour les métriques associées à l'état Ej+a, le nombre c précédemment défini vaut 2 N puisque son dernier bit br vaut 1. Compte-tenu du fait que P (b(r) = 1/Ej) et Pr (b(r) = O/Ej) sont de même valeur absolue et de signes opposés, on peut reformuler les métriques au rang r associés à l'état E: j+a c = 2 a 2 (j+a) c = 2 j 2 (j+a) + 1 c = 2 j+l Met Or (Ej+a = Metr_ (E 2 j) -Pr (b(r) = O/E 2 j Met 1 r (Ej+a = Metr-i (E 2 j+ 1) Pr (b(r) = O/E 2 j+ 1) Il s'ensuit que les métriques maximales au rang r associées aux états Ej, Ej+a peuvent être calculées au moyen des métriques maximales au rang r-l associées aux états E 2 j, E 2 j+ et des expressions des probabilités conditionnelles du rième bit b(r) relatives à ces deux derniers états. L'invention propose une solution pour effectuer ces calculs en employant, dans un dispositif, un opérateur spécialisé couplé à un processeur de traitement numérique du signal Elle s'applique à fortiori si seule la métrique maximale au rang r associée à l'état E est calculée, moyennant quelques modifications à la portée de 3 l'homme de l'art. Le traitement de l'algorithme de Viterbi peut se décomposer en trois phases, une phase initiale, une phase récurrente et une phase finale. La phase initiale consiste à établir les métriques maximales de rang N Metn(Ej). Selon une technique connue, ces métriques sont calculées à partir de N bits de garde connus transmis avant la suite initiale. S'il n'est pas prévu de bits de garde, ces métriques sont calculées directement à partir des pondérations des bits transmis au lieu d'utiliser les probabilités conditionnelles des bits de la suite35 initiale. -15- La phase de récurrence sur laquelle porte plus précisément l'invention sera décrite plus loin C'est elle qui nécessite le plus d'opérations et donc celle qui prend le plus de temps. La phase finale consiste à définir la suite initiale la plus probable à partir des métriques maximales au rang L calculées lors de la phase précédente Tout comme la phase initiale, elle est connue de l'homme de l'art. La phase de récurrence sera donc maintenant décrite Elle consiste à établir les métriques maximales au rang L à partir des métriques maximales au rang n. Elle peut se présenter sous la forme d'une première boucle o l'indice i du bit b(i) de la suite initiale prend toutes les valeurs de n+l à L, cette première boucle comprenant une deuxième boucle dans laquelle c'est l'indice j associé aux états E de 'J l'algorithme qui est incrémenté pour prendre toutes les valeurs n-i entre O et 2 N 1. On note ch(i,j) la valeur du (i-n)ième bit de la jième suite associée àl'état Ej Il vaut 1 si Met li(Ej) est supérieur à Met Oi(Ej) et O le cas contraire. Boucle 1: pour i=n+l à L faire: initialisation Boucle 2: pour j=O à 2 nl-1 faire: Met Oi (Ej) = Metii (E 2 j) + Pr(b(i)=O/E 2 j) Meti (Ej) = Meti_ 1 (E 2 j+) + Pr(b(i)= O/E 2 j+) Meti(Ej) = MAX lMetli (Ej), Met Oi (Ej) Z ch (i,j) = (i-n)ième bit de la jième suite correspondant à Meti(E j) 4 et Oi(Ej+a) = Meti_ 1 (E 2 j) Pr (b(i) =O/E 2 j) Metli(Ej+a) = Meti-1 (E 2 j+i) Pr(b(i) = O/E 2 j+) Met (Ej+a) MAX lMetli(E), Met Oi(Ej)J ch (i, j +a) = (i-n)ième bit de la (j+a)ième suite correspondant à Meti(Ej+a) Fin boucle 2. Mise à jour. Fin boucle 1 -16- Les étapes "initialisation" et "mise à jour" sont mentionnées pour mémoire Elle sont connues de l'homme de l'art et permettent notamment d'agencer de manière optimale la mémoire associée au processeur. Dans un premier mode de réalisation de l'invention, l'opérateur effectue toutes les opérations de la deuxième boucle, hormis les calculs de probabilités conditionnelles qui sont effectués par le processeur. L'opérateur reçoit en entrée, pour chaque itération de la deuxième boucle Met i 1 (E 2 j) Pr (b(i)=O/E) Met i 1 (E 2 j+l) Pr(b(i)=O/E 2 j+ 1) L'opérateur fournit en sortie pour chaque itération de la deuxième boucle. meti(E j) Meti(E j+a) L'opérateur fournit en sortie pour chaque itération de la première boucle: ch(i,j) pour j=O à 2 n-l On peut considérer que l'opérateur n'a pas besoin de connaître la valeur de j, en supposant que l'on initialise j à O à l'extérieur de la deuxième boucle dans l'étape d'initialisation de25 la première boucle, la valeur de j s'incrémentant automatiquement à chaque itération de la boucle. De plus, on considère que les valeurs des (i-n)ièmes bits des différentes suites seront lues à l'extérieur de la deuxième boucle dans l'étape de mise à jour de la première boucle.30 Le processeur possède une architecture dite de type "HARVARD", c'est à dire une architecture multi-bus parallèle Il possède donc plusieurs bus de données permettant d'effectuer plusieurs transferts de données en parallèle. On considère dans le cas présent que le processeur possède au moins deux bus de données permettant le transfert en parallèle de deux données indépendantes. L'invention s'applique également si le processeur possède un -17- seul bus de données moyennant quelques modifications à la portée de l'homme de l'art Le temps de traitement sera alors augmentée. La commande de l'opérateur peut se faire par le bus d'adresse du processeur en prévoyant un décodage des informations présentes sur ce bus Elle peut également se faire par le bus d'instruction du processeur, ce qui permet une plus grande souplesse Quelle que soit la solution retenue on parlera d'un bus de commande du processeur qui permet de commander l'opérateur. Le traitement de l'algorithme de Viterbi sera maintenant présenté à l'aide d'un circuit particulier représenté dans la figure 1 Ce circuit est donné à titre d'exemple et bien d'autres variantes sont possibles sans sortir du cadre de l'invention. L'opérateur O 1 est relié au processeur DSP par deux bus de données DB 1, DB 2 et un bus de commande CB Il comprend quatre registres d'entrée, le premier Il et le troisième I 3 ayant leur entrées raccordées au premier bus de données DB 1, le deuxième I 2 et le quatrième I 4 ayant leurs entrées raccordées au deuxième bus de données DB 2 Il comprend un premier circuit de calcul A 51 produisant sur commande un premier résultat RI de l'addition ou de la soustraction des données présentes dans les premier Il et deuxième I 2 registres d'entrée Il comprend également un deuxième circuit de calcul A 52 produisant sur commande un second résultat R 2 de l'addition ou de la soustraction des donnés présentes dans les troisièmes I 3 et quatrième I 4 registres d'entrée L'opérateur 01 comprend de plus un comparateur COMP qui produit un signal de choix CH à l'état 1 lorsque le deuxième résultat R 2 est supérieur au premier RI et à l'état O dans le cas contraire Il comprend aussi un multiplexeur MUX qui produit comme signal de sortie M le premier Rl ou le deuxième R 2 résultat selon que le signal de choix vaut respectivement O ou 1 Il comprend trois registres de sortie, le premier Si et le deuxième 52 recevant entrée le signal de sortie M du multiplexeur, tandis que le troisième 53, du type registre à décalage mémorise les différentes valeurs prises successivement par le signal de choix CH Les premier Si et troisième 53 registres de35 sortie ont leur sortie raccordée au premier bus de données DB 1, tandis que le deuxième registre de sortie 52 à sa sortie raccordée au deuxième bus de données DB 2 Il comprend enfin un module de -18- commande C qui produit les signaux de commande des différents éléments de l'opérateur en réponse aux informations présentes sur le bus de commande CB Ces signaux sont: le premier signal de commande Cl à destination des premier Il et deuxième I 2 registres d'entrée, le deuxième signal de commande C 2 à destination des troisième I 3 et quatrième I 4 registres d'entrée, le troisième signal de commande C 3 pour positionner les deux circuits de calcul A 51, A 52 en mode addition ou soustraction. le quatrième signal de commande C 4 à destination du premier registre de sortie Sl, le cinquième signal de commande C 5 à destination du deuxième registre de sortie 52, le sixième signal de commande C 6 à destination du troisième registre de sortie 53. Le module de commande C qui consistera généralement en un simple circuit de logique combinatoire ne sera pas détaillé car sa fonction apparaîtra clairement à l'homme de métier au vu de la succession des opérations effectuées par le dispositif décrite ci-après. Le traitement de l'algorithme de Viterbi présenté plus haut peut maintenant être complété en précisant le rôle de l'opérateur et du processeur. Boucle 2: Calcul de la valeur de Pr (b(i) =O/E 2 j) par le processeur DSP, Calcul de la valeur de P r(b(i)=O/E 2 j+ 1) par le processeur, Transfert de la valeur de Met i 1 (E 2 j) et de la valeur de Pr(b(i)=O/E 2 j) du processeur vers l'opérateur 01, Transfert de la valeur de Met 1 (E 2 j+l) et de la valeur de Pr(b(i)=O/E 2 j+ 1) du processeur vers l'opérateur 01, calcul de Met (E), calcul et stockage du (i-n)ième bit CH de la jème suite par l'opérateur, calcul: de Meti(E j+ a), calcul et stockage du (i-n)ième bit CH de la (j+a)ième suite par l'opérateur, -19- transfert de la valeur de Meti(E) et de la valeur de Meti(E j+a) de l'opérateur au processeur. Fin boucle 2. Transfert des 2 valeurs de (i-n)ièmes bits des suites de l'opérateur au processeur. Il faut optimiser le nombre de cycles d'instruction pris par la deuxième boucle pour effectuer les opérations décrites ci-dessus. Il est délicat d'effectuer une estimation exacte de ce nombre de cycles car il dépend du type du processeur couplé à l'opérateur et de l'application de l'algorithme de Viterbi qui est envisagée Néanmoins, on fera les hypothèses suivantes Le calcul des probabilités conditionnelles ne prend qu'un seul cycle d'instruction du processeur et est effectué à l'intérieur de la deuxième boucle,15 Le processeur peut effectuer une opération et deux transferts de données en un seul cycle d'instruction. Dans ce cas, les 7 étapes de la deuxième boucle se font en 5 cycles d'instructions du processeur en effectuant des traitements en parallèle entre l'opérateur et le processeur, ce que l'homme de20 l'art a pour pratique d'appeler "pipe-line" Ces deux organes travaillent simultanément pour deux valeurs consécutives de j: jo et j +l, en relation avec les deux états correspondants de l'algorithme E 2 jo O E 2 jo+ 2 ' Pendant le premier cycle, le processeur DSP transfère la valeur de Met i_ (E 2 jo) et la valeur de Pr(b(i)=O/E 2 jo), valeurs calculées précédemment, respectivement par les bus de données D Bl, DB 2 respectivement aux premier Il et deuxième I 2 registres d'entrée au moyen du premier signal de commande Cl. Pendant le deuxième cycle, le processeur DSP transfère la valeur de Meti l (E 2 jo+ l) et la valeur de Pr(b(i)=O/E 2 jo+l), valeurs calculées précédemment, respectivement par les bus de données D Bl, DB 2, respectivement aux troisième I 3 et quatrième I 4 registres d'entrée au moyen du deuxième signal de commande. -20- Pendant le troisième cycle, le processeur DSP calcule la valeur de Pr (b(i)=O/E 2 jo+ 2), tandis que l'opérateur Qi calcule la valeur de Meti(Ejo) en positionnant les deux circuits de calcul A 51, A 52 en mode addition au moyen du troisième signal de commande5 C 3, mémorise cette valeur dans le premier registre de sortie S au moyen de quatrième signal de commande C 4, et mémorise le (i-n)ième bit correspondant CH dans le troisième registre de sortie 53 au moyen du sixième signal de commande C 6. Pendant le quatrième cycle, le processeur DSP calcule la valeur de Pr(b(i)=O/E 2 jo+ 3), tandis que l'opérateur Oi calcule la valeur de Meti(Ejo+a) en mode soustraction au moyen du troisième signal de commande C 3, mémorise cette valeur dans le deuxième registre de sortie 52 au moyen du cinquième signal de commande C 5, et mémorise le (i-n)ième bit correspondant CH dans le troisième15 registre de sortie 53 au moyen du sixième signal de commande C 6. Pendant le cinquième cycle, le processeur DSP fait l'acquisition des valeurs de Meti(Ejo) et de Meti(Ejo+a) par les deux bus de données D Bl, DB 2. A la suite des 2 itérations de la deuxième boucle, l'opérateur Qi transfère les différentes valeurs des (i-n)ièmes bits au processeur DSP par le premier bus de données DBU au moyen du sixième signal de commande C 6. Il apparaît qu'il est nécessaire de prévoir une initialisation supplémentaire des valeurs des probabilités conditionnelles pour jo=O Cette étape ne présente pas de difficulté pour l'homme du métier. Il est également implicite que l'opérateur puisse effectuer les traitements prévus dans le troisième et quatrième cycle dans une durée compatible avec celle de ces cyles. On voit donc que le nombre total Ni de cycles pour effectuer les deux boucles imbriquées si l'on note El le nombre de cycles externes à la deuxième boucle compris dans la première boucle, vaut Ni = (L- n) ( 2 N 5 +El) Si l'on note N 2 le nombre total de cycles nécessaires dans le -21cas d'un processeur de traitement de signal unique effectuant le calcul d'une seule métrique maximale à partir de deux métriques au rang inférieur, et en notant E 2 le nombre de-cycles externes à la deuxième boucle compris dans la première boucle, ce nombre vaut: n N 2 = (L-n) ( 28 +E 2) El et E 2 étant couramment inférieur à dix, et N étant généralement compris entre 4 et 7, il s'ensuit que N 1 est sensiblement trois fois plus petit que N 2. Dans un deuxième mode de réalisation de l'invention, l'opérateur effectue toutes les opérations de la deuxième boucle, c'est-à-dire qu'outre les opérations présentées dans le mode de réalisation précédent, il effectue les calculs de probabilités conditionnelles. L'opérateur reçoit en entrée, pour chaque itération de la deuxième boucle: Pond (BT(I)) pour I i T,i T+ 1,,i T+T-1 Meti-1 (E 2 j) Meti-l (E 2 j+ 1) L'opérateur fournit en sortie pour chaque itération de la deuxième boucle: Meti(E j) Meti(Ej+a) L'opérateur fournit en sortie pour chaque itération de la première boucle: ch(i,j) pour j=O à 2 n-1 On considère, comme précédemment, que l'on initialise j à O à l'extérieur de la deuxième boucle dans l'étape d'initialisation de la première boucle, la valeur de j s'incrémentant automatiquement à chaque itération de la boucle De plus, l'opérateur n'a pas besoin d'avoir les pondérations des bits transmis à chaque itération de la deuxième boucle, une seule fois suffisant On considère donc que l'on transfère ces valeurs à l'opérateur à l'extérieur de la deuxième boucle mais dans la première boucle, à l'initialisation des valeurs. Comme précédemment, on considère que les valeurs des -22- (i-n)ièmes bits des différents suites seront lues à l'extérieur de la deuxième boucle dans la première boucle à l'étape de mise à jour. Le traitement de l'algorithme de Viterbi sera maintenant présenté à l'aide d'un autre circuit représenté dans la figure 2, le processeur étant identique à celui employé dans le premier mode de réalisation. Dans l'exemple choisi, T est fixé égal à 4, ce qui permet de clarifier la description Il ne faut pas voir là une restriction de l'invention qui s'applique quelle que soit la valeur de T moyennant quelques modifications mineures à la portée de l'homme du métier. L'opérateur 02 se distingue de celui 01 décrit précédemment par les éléments suivants Il comprend quatre registres de transfert, le premier Tl et le troisième T 3 ayant leurs entrées15 raccordées au premier bus de donnée DB 1, le deuxième T 2 et le quatrième T 4 ayant leurs entrées raccordées au deuxième bus de données DB 2 Il comprend également une unité arithmétique UA qui calcule les expressions des probabilités conditionnelles à partir des signaux de sortie des quatre registres de transfert prévus pour20 mémoriser Pond (BT(i 4)), Pond (BT(i 4 + 1)), Pond (BT(i 4 + 2)) et Pond (BT(i 4 + 3)). Cette unité arithmétique est un circuit câblé qui ne pose pas de difficultés de réalisation. Le deuxième registre d'entrée I 2 reçoit la valeur de Pr(b(i=O/E 2 j) non plus par le deuxième bus de données DB 2, mais directement de l'unité arithmétique UA De même, le quatrième registre d'entrée I 4 reçoit désormais la valeur de Pr(b(i)=O/E 2 j+) directement de l'unité arithmétique UA. On prévoit de plus des signaux de commande additionnels pour la commande des registres de transfert et de l'unité arithmétique. Ces signaux ayant une fonction analogue à celle décrite dans le premier mode de réalisation, ils ne seront pas plus détaillés et ne sont pas représentés dans la figure On prévoit également un signal d'état E qui transmet la valeur de j correspondant au nombre35 d'itérations de la deuxième boucle du module de commande C à -23- l'unité arithmétique UA. Le traitement de l'algorithme de Viterbi présenté plus haut peut maintenant être complété en précisant le r 8 le de l'opérateur et du processeur. s Boucle 1: pour i=n+l à L faire initialisation comprenant le transfert de Pond (BT(i 4)), Pond (BT(i 4 + 1), Pond (BT(i 4 + 2) et Pond (BT(I 4 + 3)) du processeur DSP aux quatre registres de transfert T 1,T 2, T 3, T 4. Boucle 2: pour j=o à 2 n 1 faire calcul de la valeur de Pr(b(i)=O/E 2 j) par l'opérateur 02, calcul de la valeur Pr(b(i)=O/E 2 j+l) par l'opérateur 02, Transfert de Meti l(E 2 j) du processeur DSP à l'opérateur, Transfert de Meti 1 (E 2 j+l) du processeur DSP à l'opérateur, Calcul de Meti(Ej), calcul et stockage du (i-n)ième bit de la jième suite par l'opérateur. Calcul de Meti(Ej+a), calcul et stockage du (i-n)ième de la (j+a)ième suite par l'opérateur, Transfert des valeurs de Met (Ej) et de Met (Ej+a) de 1 1 l'opérateur au processeur, Fin boucle 2. Transfert des 2 N valeurs des (i-n)ièmes bits des différentes suites de l'opérateur au processeur et mise à jour. Fin boucle 1. On fera les mêmes hypothèses que dans le mode de réalisation précédent: Le calcul des probabilités conditionnelles ne prendrait qu'un seul cycle d'instruction du processeur DSP si il était effectué dans celui-ci, Le processeur DSP peut effectuer une opération et deux transferts de données en un seul cycle d'instruction. Dans ce cas, les 7 étapes de la deuxième boucle se font en 2 cycles d'instructions du processeur en effectuant des traitements -24- en parallèle entre le processeur et l'opérateur. Ces deux organes travaillent simultanément pour deux valeurs consécutives de j: j et j + 1, en relation avec les deux états correspondants de l'algorithme E 2 jo E 2 jo+ 2. Pendant le premier cycle, le processeur DSP transfère la valeur de Met i (E 2 jo+ 2) et la valeur de Meti 1 (E 2 j 3) - respectivement au premier Il et troisième I 3 registres d'entrée, tandis que l'opérateur 02 calcule les valeurs de Meti(Ejo) et de Meti(Ejo+a), les mémorise et enregistre les (i-n)ièmes bits10 correspondants CH comme dans le mode de réalisation précédent. Pendant le deuxième cycle, le processeur DSP fait l'acquisition des valeurs de Meti(Ejo) et de Met(Ejo+a), tandis que l'opérateur 02 calcule les valeurs de Pr(B(i)=O/E 2 jo+ 2) et de Pr(b(i)=O/E 2 jo+ 3) dans l'unité arithmétique UA pour les fournir15 respectivement aux deuxième I 2 et quatrième registres d'entrée. A la suite des 2 N itérations de la deuxième boucle, l'opérateur 02 transfère les différentes valeurs des (i-n)ièmes bits au processeur DSP. Il apparaît qu'il est nécessaire de prévoir une initialisation supplémentaires des valeurs des probabilités conditionnelles pour jo=O Cette étape ne présente pas de difficulté pour l'homme de métier. Il est également implicite que l'opérateur puisse effectuer les traitements prévus dans les deux cycles d'instruction chacun dans une durée compatible avec celle d'un cycle. On voit donc que le nombre total N 3 de cycles pour effectuer les deux boucles imbriquées, si l'on note E 3 le nombre de cycles externes à la deuxième boucle compris dans la première boucle, vaut30 N 3 = (L- f) ( 2 n 2 +E 3) Si l'on note N 4 le nombre total de cycles nécessaires dans le cas d'un processeur de traitement de signal unique effectuant le calcul d'une seule métrique maximale à partir de deux métriques au rang inférieur, et en notant E 4 le nombre de cycles externes à la35 deuxième bouche compris dans la première boucle, ce nombre vaut: -25- N 4 = (L-n) ( 2 8 +E 4) On peut considérer que N 3 est un peu supérieur à N 4 mais deux valeurs sont petites par rapport à 2 Les ordres de grandeur donnés dans le cadre du premier mode de réalisation restant5 valables, il s'ensuit que N 3 est sensiblement huit fois plus petit que N 4. Ainsi, des deux modes de réalisation présentés, le second possède des meilleurs performances en terme de vitesse de traitement mais il nécessite une unité arithmétique cablée pour10 effectuer le calcul des expressions des probabilités conditionnelles Sa mise en oeuvre dépend du contexte de transmission et n'est donc pas très souple En effet, si on veut que le même opérateur puisse permettre plusieurs utilisations de l'algorithme de VITERBI, il faut alors que celui-ci possède15 plusieurs unités arithmétiques, chacune d'elles permettant de calculer les expressions des probabilités conditionnelles associées à une utilisation de l'algorithme Ceci entratne donc une augmentation de la taille de l'opérateur. Par contre, le premier permet différentes utilisations de l'algorithme, ceci sans modification En effet, d'une utilisation à l'autre, la seule chose qui change dans l'algorithme est la définition des expressions des probabilités conditionnelles qui sont calculés par le processeur. Ces deux modes de réalisation possèdent des performances différentes pour un co t différent et le choix de l'un ou de l'autre se fait suivant les spécifications souhaitées. Les opérateurs de l'invention peuvent être réalisées de deux façons différentes, soit totalement externe au processeur auquel ils sont couplés, soit partiellement inclus dans ce processeur.30 Dans le premier cas, l'opérateur est indépendant du processeur. Dans le deuxième cas, on peut remplacer certains registres de l'opérateur par les registres contenus dans l'unité arithmétique et logique des données du processeur La surface prise par l'opérateur -26- est donc réduite en conséquence. Le premier cas s'applique que l'opérateur et le processeur soient o ne soient pas dans un même composant tandis que le second cas ne peut s'envisager que dans une solution ou l'on intègre le5 processeur et l'opérateur dans un même composant. L'invention étant décrite dans sa structure, certaines applications dans le domaine de la transmission en seront maintenant présentées. Les deux utilisations les plus courantes de l'algorithme de Viterbi en traitement numérique du signal sont le décodage de codes convolutionnel et l'égalisation en démodulation de signaux affectés d'interférence intersymbole. Dans le cadre du décodage d'un code convolutionnel, pour traiter l'algorithme de Viterbi il faut: les pondérations des probabilités de valeur des bits de la suite transmise, la relation traduisant l'opération de transmission. Usuellement, en traitement du signal, le décodage de se fait après la démodulation C'est le démodulateur qui fournit les pondérations La relation traduisant l'opération de transmission est le codage convolutionnel Ce codage relie un bit codé BC à (n+l) bits b de la suite initiale au moyen des relations suivantes: BC(T k) =b(k) 8 all b(k-1), , anl b(k-n) BC (T k+l) = b(k)@a 12 b(k-l)9,,e an 2 b(k- n) BC (T k+T-1) = b(k)( 9 al T b(k-1)@,,q a T b(k-n) o: D représente un "ou exclusif" logique k = 1,,L; L étant égal au nombre de bits de la suite initiale a ij = O ou 1 suivant le codage choisi. On connaît les pondérations Pond (BT(i)= B(i)),i=l,,T L, qui correspondent aux probabilités de valeur des bits transmis En effectuant une inversion de variable entre b(i) et BC(T i), en -27- remplaçant dans l'expression précédente les bits codés BC(I) par les pondérations correspondantes Pond (BT(I)), et en normalisant les expressions, on obtient les T expressions suivantes: Pr 1 (b(k)=X/n)= Pond (BT(T k)) NCX(all b(k-l)E,,D anl b(k-n)3 Pr 2 (b(k)=X/n)= Pond (BT(T k+l)) NMX$a 12 b(k-l)$,,( an 2 b(k-n)3 Pr T(b(k)=X/n = Pond (BT(T k+T-l) NEX Eal T b(k-l), , an T b(k-n)l ou: X est un symbole binaire N Ebit 1: fonction normalisante définie par: N Ebità = 1 si bit = 1, = -l si bit = O. Ces T expressions correspondant donc aux probabilités conditionnelles du bit b(k) d'être égal à X connaissant la valeur des N bits antécédents On regroupe tous ces termes en un seul pour avoir une expression correspondant à la probabilité conditionnelle totale: Pr(b(k)=X/Ej) = Pr (b(k)=X/n) o E est l'état défini par les N bits antecédents. J Cette expression définit donc l'expression de la probabilité conditionnelle totale correspondant à celle utilisée dans l'invention. Dans le cadre de l'égalisation en démodulation de signaux affectés d'interférence intersymbole, pour traiter l'algorithme de Viterbi il faut: les pondérations expressions des probabilités de valeur des bits de la suite transmise, La relation traduisant l'opération de transmission. Usuellement, en traitement du signal, l'égalisation se fait après le filtrage adapté à la réponse impulsionnelle du canal transmission C'est le filtre adapté qui fournit les pondérations. La relation traduisant l'opération de transmission est celle qui caractérise un signal numérique modulé dans un canal affecté -28- d'interférence intersymbole Cette relation n'introduit pas de redondance (T= 1) et relie chaque bit à transmettre aux N bits précédents de la suite initiale. Cette relation s'exprime directement par la formulation suivante qui définit une expression de la probabilité conditionnelle de valeur du ième bit de la suite initiale connaissant ses N antécédents qui définissent l'état E et la pondération du ième bit transmis: Pr(b(i)=O/Ej) = -Pond (BT(i)) +t U(i-k) S(k) k=l o U(k) = 2 b(k)-l, S(k) = kième coefficient d'interférence intersymbole. Le deuxième opérande du membre de droite de l'égalité correspond à ce que l'on peut définir comme terme d'interférence des N bits antécédents au bit b(i) En effet, les termes U(i-k) (pour k=l à n-l) représentent les N bits antécédents au bit b(i), et les termes S(k) sont les coefficients d'interférence intersymbole associés aux bits antécédents b(i-k). Ces coefficients d'interférence intersymbole sont constants n durant la transmission d'une suite de L bits Ils engendrent 2 termes d'interférence correspondant aux 2 N états E possibles On calcule donc ces 2 termes à l'extérieur de la première boucle Le calcul d'une probabilité conditionnelle se réduit alors à l'addition d'une pondération et d'un terme d'interférence.25 -29- REVENDICATIONS 1) Dispositif prévu pour le traitement de l'algorithme de Viterbi comprenant un processeur, cet algorithme étant défini par sa longueur de contrainte de valeur n+l et ses 2 N états associés à des suites de bits, le traitement ayant pour objet l'estimation d'une suite initiale de bits b(i), à partir d'une suite transmise résultant d'une opération de transmission effectuée sur ladite suite initiale, caractérisé en ce qu'il comprend un opérateur (C, COMP, MUX, 51, 53) pour établir la métrique maximale au rang r de l'état Ej dénommée Metr(Ej), pour r supérieur à n, et le (r-n)ième bit de la suite correspondant à cette métrique, à partir de valeurs d'entrées que sont les métriques maximales au rang r-l des états E 2 k et E 2 k+l notées Metrl(E 2 k) et Metrl( 2 k+ l), et les probabilités conditionnelles en rapport auxdits états E 2 k, E 2 k+l que le rième bit des suites associées à ces états ait une valeur déterminée dénommées, Pr(b(r)=O/E 2 k) et Pr(b(r)=O/E 2 k+ 1) par exemple, k étant égal à 2 j pour tout j inférieur à 2 et valant 2 (j- 2 N -) pour tout j supérieur ou égal à 2 n, de sorte que Metr(Ej) prenne la valeur de la plus grande des deux expressions suivantes, la première étant Metr l(E 2 k)+Pr(b(r)=O/E 2 k) et la seconde étant Met r-l(E 2 k+l) + Pr(b(r)=O/E 2 k+l). 2) Dispositif prévu pour le traitement de l'algorithme de Viterbi comprenant un processeur selon la revendication 1, caractérisé en ce que ledit opérateur comprend des moyens additionnels (A 51, A 52, 52) pour établir quel que soit j inférieur à 2 n-1 à partir desdites valeurs d'entrée non seulement la métrique maximale au rang r de l'état Ej Metr(Ej) et le (r-n)ième bit correspondant, mais également la métrique maximale au rang r de l'état E. nita Metr(Ej+a) et le (r-n)ième bit correspondant o a vaut 2, de sorte que Metr(Ej+a) prenne la valeur de la plus grande des deux formules suivantes, la première étant Metrl(E 2 j) Pr(b(r)=O/E 2 j) et la seconde étant Met r (E 2 j+ 11) Pr(b(r)=- O/E 2 j+ 11). 3) Dispositif prévu pour le traitement de l'algorithme de Viterbi comprenant un processeur selon la revendication 2, caractérisé en ce que, ledit opérateur étant relié audit processeur (DSP) par au -30- moins un bus de données (DB 1, DB 2) et un bus de commande (CB), il ( 01) comprend quatre registres d'entrée dont les entrées sont connectées chacune à l'un desdits bus de données, le premier (Il) étant prévu pour recevoir la valeur de Met rl(E 2 j), le second (I 2) la valeur de Pr(b(i)=O/E 2 j), le troisième (I 3) la valeur de Met 1 (E 2 j+l) et le quatrième (I 4) la valeur de Pr(b(i)=O/E 2 j+l), il comprend également un premier (A 51) et un deuxième (A 52) circuits de calcul prévus pour produire respectivement un premier (R 1) et un deuxième (R 2) résultats prenant la valeur en réponse à un signal de commande (C 3) de la somme ou de la différence des contenus respectivement des deux premiers registres d'entrées (Il, I 2) et des deux derniers registres d'entrée (I 3, I 4), il comprend un comparateur (COMP) délivrant un signal de sortie (CH) de valeur 1 lorsque ledit premier résultat (R 1) est inférieur audit deuxième résultat (R 2) et de valeur O dans le cas contraire, un multiplexeur (MUX) commandé par ledit comparateur produisant comme signal de sortie (M) celui desdits résultats qui présente la plus forte valeur, il comprend de plus trois registres de sortie dont les sorties sont raccordées chacune à l'un desdits bus de données, le20 premier ( 51) et le deuxième ( 52} recevant le signal de sortie (M) dudit multiplexeur et étant prévus pour enregistrer les valeurs de respectivement Metr(Ej) et Metr(Ej+a), le troisième ( 53) recevant le signal de sortie (CH) dudit comparateur qui est le (r-n)ième bit des suites correspondant à ces métriques, et il comprend un25 module de commande prévu pour commander ses différents éléments en fonction des informations adressées par ledit processeur (DSP) sur ledit bus de commande (CB). 4) Dispositif prévu pour le traitement de l'algorithme de Viterbi comprenant un processeur selon la revendication 3, caractérisé en ce que ledit troisième registre de sortie ( 53) est de plus prévu pour enregistrer le (r-n)ième bit de toutes les suites correspondant aux 2 N métriques maximales à un rang déterminé. 5) Dispositif prévu pour le traitement de l'algorithme de Viterbi comprenant un processeur, selon la revendication 3 ou 4 caractérisé en ce que, ledit processeur (DSP) comprenant deux bus de données, -31- lesdits premier (Il) et troisième (I 3) registres d'entrée ont leur entrée connectée au premier (DB 1) desdits bus de données, lesdits deuxième (I 2) et quatrième (I 4) registres d'entrée ont leur entrée connectée au second (DB 2) desdits bus de données, tandis que lesdits premier (Si) et second ( 52) registres de sortie ont leurs sorties connectées chacune à un bus de donnée distinct. 6) Dispositif prévu pour le traitement de l'algorithme de Viterbi comprenant un processeur, selon la revendication 2 caractérisé en ce que ledit opérateur comprend des moyens supplémentaires (UA)10 pour établir lesdites probabilités conditionnelles en rapport aux états E 2 k, E 2 k,+ que les rièmes bits des suites associées à ces états ait un état déterminé en fonction des pondérations des bits de ladite suite transmise liés auxdits rièmes bits, du nombre k associé auxdits états E 2 k, E 2 k+l et des relations définissant ladite opération de transmission. 7) Dispositif prévu pour le traitement de l'algorithme de Viterbi comprenant un processeur, selon la revendication 6 caractérisé en ce que, ledit opérateur étant relié audit processeur (DSP) par au moins un bus de données (DB 1, DB 2) et un bus de commande (CB), il20 ( 02) comprend des registres de transfert (Tl, T 2, T 3, T 4) dont les entrées sont reliées chacune à l'un desdits bus de données, ces registres de transfert étant prévus pour mémoriser chacun une desdites pondérations, et une unité arithmétique cablée (UA) connectée aux sorties desdits registres de transfert, ayant accès à25 la valeur j identifiant un état, et établissant les relations définissant ladite opération de transmission pour produire lesdites probabilités conditionnelles, il comprend quatre registres d'entrée, le premier (Il) dont l'entrée est raccordée à l'un desdits bus de données étant prévu pour recevoir la valeur de30 Met r-i (E 2 j), le second (I 2) mémorisant la valeur de Pr(b(r)= 0/E 2 j) fournie par ladite unité arithmétique (UA), le troisième (I 3) dont l'entrée est raccordée à l'un desdits bus de données étant prévu pour recevoir la valeur de Met r-i (E 2 j+ 1) et le quatrième (I 4) mémorisant la valeur de Pr(b(r)= 0/E 2 j+ 1) fournie par ladite unité35 arithmétique (UA), il comprend également un premier (A 51) et un -32- deuxième (A 52) circuits de calcul prévus pour produire respectivement un premier (Ri) et un deuxième (R 2) résultats prenant la valeur en réponse à un signal de commande (C 3) de la somme ou de la différence des contenus respectivement des deux5 premiers registres d'entrée (Il, I 2) et des deux derniers registres d'entrée (I 3, I 4), il comprend un comparateur (COMP) délivrant un signal de sortie (CH) de valeur 1 lorsque ledit premier résultat (Ri) est inférieur audit deuxième résultat et de valeur O dans le cas contraire, et un multiplexeur (MUX) commandé par ledit comparateur produisant comme signal de sortie (M) celui desdits résultats qui présente la plus forte valeur, il comprend de plus trois registres de sortie dont les sorties sont raccordées chacune à l'un desdits bus de données, le premier (Si) et le deuxième ( 52) recevant le signal de sortie (M) dudit multiplexeur et étant prévus pour enregistrer les valeurs de respectivement Metr (E) et Metr(E j+a), le troisième ( 52) recevant le signal de sortie (CH) dudit comparateur qui est le (r-n)ième bit des suites correspondant -à ces métriques, et il comprend un module de commande prévu pour commander ses différentes éléments en fonction des informations adressées par ledit processeur (DSP) sur ledit bus de commande (CB). 8) Dispositif prévu pour le traitement de l'algorithme de Viterbi comprenant un processeur, selon la revendication 7, caractérisé en ce que ledit troisième registre de sortie ( 53) est de plus prévu pour enregistrer le(r-n)ième bit de toutes les suites correspondant aux 2 métriques maximales à un rang déterminé. 9) Dispositif prévu pour le traitement de l'algorithme de Viterbi comprenant un processeur, selon la revendication 7 ou 8 caractérisé en ce que, ledit processeur (DSP) comprenant deux bus de données,30 lesdits registres de transfert ont leurs entrées réparties sur le premier (DB 1) et sur le second (DB 2) desdits bus de données, le premier (Il) et le troisième (I 3) desdits registres d'entrées ont leurs entrées reliées chacune à un bus de données distinct, tandis que lesdits premier (Si) et second ( 52) registres de sortie ont35 leurs sorties connectées chacune à un bus de données distinct. -33- ) Dispositif prévu pour le traitement de l'algorithme de Viterbi comprenant un processeur selon l'une quelconque des revendications précédentes, caractérisé en ce que certains des éléments dudit opérateur sont implantés dans ledit processeur (DSP). 11) Application du dispositif pour le traitement de l'algorithme dé Viterbi comprenant un processeur selon l'une quelconque des revendications précédentes caractérisée en ce que, ladite opération de transmission étant un codage convolutionnel, elle permet le décodage de ladite suite transmise.10 12) Application du dispositif prévu pour le traitement de l'algorithme de Viterbi comprenant un processeur, selon l'une quelconque des revendications 1 à 10 caractérisée en ce que, ladite opération de transmission introduisant une interférence intersymbole dans ladite suite transmise, elle permet l'égalisation de cette suite.