Ann´ee 2014-2015
Camille LEROUX
´rique
Electronique Nume
EN 218
Fili`ere : TELECOM 2eme ann´ee
Semestre : 7
Septembre 2014
Bascules D Flip-Flop
Exercice 1 : Le verrou D : ”D-Latch”
La structure d’un D-latch CMOS est donn´ee en figure 1. Ce latch contient deux interrupteurs (T1, T2) et deux
inverseurs (I1, I2). Le signal de commande E* est obtenu par inversion de E (inverseur I3).
Figure 1: D-LATCH en technologie CMOS
Question 1 En consid´erant des temps de commutation nuls (tp temps de propagation, tr temps de mont´ee et
´
tf temps de descente), compl´eter les chronogramme de la figure 2. Etablir
la table de transition de ce latch.
´
Question 2 Elaborer
un latch avec une remise `a z´ero prioritaire (reset).
Exercice 2 : La bascule D : ”D-Flip-Flop”
La figure 3 repr´esente une structure maˆıtre-esclave de la bascule D constitu´ee de deux D-latch mis en s´erie.
Question 1 Compl´eter les chronogrammes de la figure 4 (tp = tr = tf = 0) et ´etablir la table de transition de
la bascule D.
Question 2 Modifier la structure de la bascule D pour disposer d’une remise `a z´ero asynchrone.
1
Figure 2: Chronogramme D-latch `a compl´eter
Figure 3: Bascule D (D-Flip-Flop) maˆıtre-esclave
Question 3 Modifier la structure de la bascule D pour disposer d’une remise `a z´ero synchrone.
Question 4 On boucle la sortie Q* sur l’entr´ee D. Quelle fonction a-t-on r´ealis´e ? A quelle fr´equence maximale
peut fonctionner un tel montage ?
Exercice 3 : Additionneur s´
erie
Question 1 Rappeler l’architecture d’un additionneur `a deux entr´ees de 4 bits en utilisant les fonctions de
base de l’´electronique num´erique (portes logiques ´el´ementaires, full adder et multiplexeurs).
Question 2 On souhaite maintenant effectuer la mˆeme op´eration avec un seul full adder. Proposer une
architecture qui permette de r´ealiser une telle structure. Quels sont les avantages et les inconv´enients d’un telle
architecture ?
2
Figure 4: Chronogramme bascule D (`
a compl´eter)
3
Ann´ee 2013-2014
Camille LEROUX
Electronique Num´
erique
EN 218
Fili`ere : TELECOM 2eme ann´ee
Semestre : 7
Septembre 2013
Les registres
Exercice 1 : QCM
Question 1: Chaque ´etage d’un registre `a d´ecalage repr´esente une capacit´e de stockage de :
• un bit
• deux bits
• quatre bits
• huit bits
Question 2: Dans quel type de registre `a d´ecalage la sortie (Q ou Q*) d’un ´etage n’est pas
connect´ee `a l’entr´ee de l’´etage voisine ?
• entr´ee parall`ele / sortie s´erie
• entr´ee s´erie / sortie parall`ele
• entr´ee s´erie / sortie s´erie
• entr´ee parall`ele / sortie parall`ele (registre tampon)
Question 3: Soit un registre `a d´ecalage de 8 bits `a entr´ee s´erie / sortie parall`ele. Si ce registre
ne dispose pas d’une entr´ee RAZ (remise `a z´ero), combien de cycles d’horloges sont n´ecessaires
pour qu’un z´ero appliqu´e `a son entr´ee garantisse une telle r´einitialisation ?
1
• 1
• 7
• 8
• 9
Question 4: Soit un registre `a d´ecalage de 4 bits `a entr´ee parall`ele / sortie s´erie. Si un mot (de
4 bits) a ´et´e charg´e dans ce registre, combien de cycles d’horloges sont n´ecessaires avant que le
premier bit du mot charg´e apparaisse sur la sortie ?
• 0
• 1
• 2
• 3
Question 5: Avec une fr´equence d’horloge de 200 kHz, huit bits peuvent ˆetre charg´es s´equentiellement
dans un registre `a d´ecalage en :
• 4 µs
• 40 µs
• 400 µs
• 40 ms
Question 6: Un registre `a d´ecalage de 8 bits `a entr´ee s´erie / sortie s´erie est utilis´e avec une
fr´equence d’horloge de 2 MHz pour r´ealiser un retard de temps de :
• 16 µs
• 8 µs
• 4 µs
• 2 µs
Question 7: Quand un registre `a d´ecalage de 8 bits `a entr´ee s´erie / sortie s´erie est utilis´e pour
r´ealiser un retard de temps de 20 ?s, la fr´equence d’horloge doit ˆetre r´egl´ee `a :
• 40 KHz
• 50 KHz
• 400 KHz
2
• 500 KHz
Question 8: Un registre `a d´ecalage de 8 bits, `a entr´ee s´erie / sortie parall`ele, est d´eclench´e par
une horloge de 4 MHz pour retarder un flux de donn´ees num´eriques s´equentielles de 1,25 µs.
Quelle est la sortie qui assure ce d´elai ?
• Q5
• Q6
• Q7
• Q8
Exercice 2 : Circuit arithm´
etique
Soit le circuit synchrone suivant compos´e de bascules D et de multiplexeurs.
Question 1: Compl´etez le chronogramme suivant.
Question 2: Quelle fonction arithm´etique est r´ealis´ee par ce circuit ? En vous appuyant sur le
chronogramme, expliquez les ´etapes de fonctionnement du circuit.
Question 3: Modifiez le circuit pour que celui-ci effectue une division par une puissance de 2.
Exercice 3 : Linear Feedback Shift Register (LFSR)
Question 1: Soit les circuit de la figure 1. En supposant que les bascules D qui le compose
sont initialis´ees `a la valeur ”0001”, d´ecrivez l’´evolution du contenu des bascules au cours du
temps. Quelle est la propri´et´e de la s´equence g´en´er´ee ?
Question 2: Mˆeme question pour le circuit 2.
3
Figure 1: Circuit 1
4
Figure 2: Circuit 2
5
IPB ENSEIRB-MATMECA
Département Télécommunications
2ième Année - 2012/2013
EN218 - Architecture des systèmes numériques
Série de travaux dirigés sur le thème
LES COMPTEURS SYNCHRONES
Exercice 1 : Décompteur synchrone – synthèse
Question 1
Faire la synthèse d?un décompteur à cycle complet sur 3 bits. En déduire les équations
d?un décompteur modulo 2n .
Question 2
Faire la synthèse d’un décompteur binaire modulo 6 synchrone passant par les états (en
décimal) 5, 4, 3, 2, 1 et 0. Remarques ?
Question 3
Comment peut-on modifier ce décompteur pour lui ajouter une commande de remise à zéro
synchrone (statique) ?
Question 4
Proposer une modification de ce schéma, incluant une nouvelle entrée statique CE (Chip
Enable), autorisant ou inhibant le décomptage ou le chargement parallèle (blocage du compteur
dans l’état présent).
1
Exercice 2 : Analyse système synchrone
Soit le schéma suivant :
Question 1
A l’aide d’un chronogramme et en considérant Q0 = Q1 = Q2 = 0 à l’instant initial, donner
la fonction du montage ci-dessus.
Question 2
Quelle est la particularité du code engendré par les sorties Q0 , Q1 , Q2 des bascules?
Question 3
En remplaçant B1 par (n − 2) bascules connectées de manière identique, généraliser le
résultat de la première question.
Question 4
Que se passe-t-il si l’état initial est Q0 = Q2 = 0 et Q1 = 1 ? Comment peut-on modifier
ce montage pour retrouver le fonctionnement normal (sans utiliser les entrées prioritaires de
remise à zéro ou à un) ?
2
IPB ENSEIRB-MATMECA
Département Télécommunications
2ième Année - 2012/2013
EN218 - Architecture des systèmes numériques
Série de travaux dirigés sur le thème
LES MACHINES À ÉTATS FINIS (FSM)
Exercice 1 : BUS et gestion périphérique
Deux cartes logiques C1 et C2 ont accès à un même bus B:
D1
Carte
C1
P1
D2
Bus
B
P2
Carte
C2
Chacune des deux cartes demande sa connexion au bus en activant une entrée D qui est maintenue à 1 jusqu’à la fin de l’utilisation du bus. Lorsque le bus établit la connexion avec l’une
des cartes, le signal P correspondant est activé. Ce signal reste à 1 pendant toute la durée
de la liaison. La carte qui a utilisé le bus en dernier n’est pas prioritaire en cas de demande
simultanée du bus. (à l’initialisation C1 est prioritaire)
Sachant qu’une demande de connexion doit être servie le plus rapidement possible, réaliser un
automate synchrone, dont les entrées sont D1 et D2 et les sorties P1 et P2, qui permet de gérer
l’accès au bus.
Question 1
Etablir un graphe d’états permettant de décrire le comportement de l’automate.
Question 2
Tracer les chronogrammes dans les deux cas suivants :
✓ Une demande de connexion de la carte C1 (D1=1, D2=0)
✓ Deux demandes simultanées de connexion au bus (D1=D2=1)
1
Tous les signaux (horloge, entrées, sorties, état présent, état futur) de la machine à états finis
doivent être tracés.
2
Ann´ee 2012-2013
Camille LEROUX
Electronique Num´
erique
EN 218
Fili`ere : TELECOM 2eme ann´ee
Semestre : 7
Novembre 2012
Implantation mat´
erielle de l’algorithme de Viterbi
Avertissement : Ce document n’a pas pour ambition d’expliquer de mani`ere exhaustive la th´eorie li´ee au
codes convolutifs et au d´ecodage de Viterbi. L’objectif est ici de comprendre le fonctionnement du d´ecodeur en
vue de son implantation mat´erielle. Les personnes interess´ees par la th´eorie pourront se r´ef´erer `a [1][2].
1
Le codeur convolutif
Un codeur convolutif peut ˆetre vu comme une machine s´equentielle `a ´etats finis, dont l’´evolution est command´ee par la suite des bits du message que l’on veut transmettre. A chaque cycle, une information est ´emise
sur l’´
evolution de l’´
etat interne du codeur. Ces informations seront transmises, via un canal bruit´e, au
r´ecepteur qui d´eterminera a posteriori l’´evolution du codeur la plus probable (au sens math´ematique du terme)
en fonction des symboles re¸cus. En reconstituant ainsi l’´evolution probable du codeur, le r´ecepteur sera capable
de retrouver la s´equence des bits qui l’ont fait ´evoluer, c’est `a dire le message `a transmettre.
Le codeur ´etudi´e sera constitu´e d’un registre `a d´ecalage d’une profondeur de 3 bits (Fig. 1); le codeur pourra
donc prendre 23 = 8 ´etats possibles. Nous pouvons naturellement repr´esenter l’´etat du codeur par le contenu
de 3 bascules D, par exemple l’´etat du codeur de la figure 1 sera not´e E011 .
Figure 1: Codeur dans l’´etat E011 .
1.1
Diagramme de transition du codeur : le treillis
Nous allons tout d’abord ´etudier l’´evolution de l’´etat interne du codeur en fonction des bits `a transmettre.
Supposons que le codeur soit dans l’´etat EABC `a l’instant t. A l’instant t + 1, le codeur sera `a l’´etat E0AB si
le bit suivant `a transmettre est 0, ou `
a l’´etat E1AB dans le cas contraire (Cf fig. 2). Nous pouvons caract´eriser
1
Figure 2: Transition de l’´etat E011 `a l’´etat E101 .
graphiquement l’ensemble des transitions possibles du codeur par un diagramme de transition ou treillis, comme
indiqu´e dans la figure 3.
Figure 3: Diagramme de transition du codeur convolutif.
Par d´efinition, les ´etats du codeur seront appel´es noeuds du treillis (que l’on notera toujours EABC et les
transistions entre deux noeuds successifs seront appel´es branches. Dans notre exemple (codeur sur 3 bits), ces
branches sont au nombre de 16.
Remarque : Chaque noeud EABC est connect´e aux noeuds E0AB et E1AB . Chaque noeud EABC est a comme
ant´ec´edent les noeuds EBC0 et EBC1 .
La suite des ´etats du codeur peut se caract´eriser par un chemin dans le treillis repr´esentant les ´etats successifs du codeur. R´eciproquement, `
a chaque chemin dans le treillis correspond une suite d’´etats du codeur et
donc, une suite de bits `
a transmettre (Cf fig. 4). Il suffit donc au r´
ecepteur de reconstituer le chemin
des ´
etats du codeur dans le treillis pour d´
eterminer la suite des bits transmis.
1.2
Signature d’une transition
Le codeur calcule une caract´eristique des transitions du codeur sur deux bits y1 y2 , comme indiqu´e dans la
figure 5. La transition E011 → E101 aura comme signature le couple y1 = 0, y2 = 1, ou, de fa¸con abr´eg´e, Y01 .
Cette caract´eristique sera transmise, via un canal bruit´e, au r´ecepteur. Le tableau 1 donne de fa¸con exhaustive
l’ensemble des caract´eristiques des 16 transitions possibles.
En partant de l’´etat E011 , la transmission des bits 1001 (Cf fig. 4) s’effectuera donc par la transmission des
caract´eristiques: Y01 ,Y01 ,Y01 ,Y00 .
Le fonctionnement du codeur peut se d´efinir comme un chemin dans un treillis. A chaque transition (correspondant `a une information sur un bit), le codeur transmet une information redondante: la caract´eristique de
la transition (deux bits). Le rendement du codeur sera donc de 1/2.
2
Figure 4: Exemple de chemin dans le treillis.
Figure 5: G´en´eration de la signature d’une transition.
2
Canal de transmission
La transmission des bits y1 et y2 s’effectue via un canal analogique bruit´e. A la sortie du canal, le d´emodulateur
ne prendra pas de d´ecision d´efinitive (0 ou 1) sur la signification du signal analogique re¸cu, mais le quantifiera
sur huit niveaux (soit trois bits de quantification) comme indiqu´e dans le tableau 2.
Nous parlerons de d´
ecision ”pond´
er´
ee” ou ”souple” cod´ee sur 3 bits.
En r´eception, nous recevons donc deux symboles ye1 et ye2 cod´es chacun sur trois bits. Nous pouvons repr´esenter
l’ensemble des couples y1 y2 et ye1 ye2 possibles par un diagramme bidimenseionnel comme montr´e sur la figure 6.
A partir de cette repr´esentation bidimensionnelle, nous pouvons d´efinir une distance entre les symboles re¸cus ye1 ye2
et les caract´eristiques des transitions possibles: Y00 ,Y01 ,Y10 et Y11 . Ces distances seront appel´ees m´
etriques
de branches et not´ees d(e
y1 ye2 , Yy1 y2 ). On peut d´emontrer que les m´etriques de branches sont inversement
proportionnelles `
a la probabilit´e P r(e
y1 ye2 |Yy1 y2 ), ce qui correspond `a la notion intuitive de proximit´e. Le lecteur
pourra trouver une justification th´eorique de cette propri´et´e dans [2].
Nous avons dans l’exemple de la figure 6:
p
d(e
y1 ye2 , Y00 ) = 32 + 52 = 5.83
p
d(e
y1 ye2 , Y01 ) = 32 + (7 − 5)2 = 3.61
p
d(e
y1 ye2 , Y10 ) = (7 − 3)2 + 52 = 6.40
p
d(e
y1 ye2 , Y11 ) = (7 − 3)2 + (7 − 5)2 = 4.47
3
Etat initial
E000
E010
E100
E110
E000
E010
E100
E110
Etat final
E000
E001
E010
E011
E100
E101
E110
E111
Caract´eristique
Y00
Y01
Y10
Y11
Y11
Y10
Y01
Y00
Etat initial
E001
E011
E101
E111
E001
E011
E101
E111
Etat final
E000
E001
E010
E011
E100
E101
E110
E111
Caract´eristique
Y11
Y10
Y01
Y00
Y00
Y01
Y10
Y11
Table 1: Caract´eristique des 16 transitions possibles dans le trellis.
Niveau du signal analogique
000
001
010
011
100
101
110
111
Signification ”logique”
0 fort
0 moyen fort
0 moyen faible
0 faible
1 faible
1 moyen faible
1 moyen fort
1 fort
Table 2: Quantification du signal re¸cu.
3
D´
ecodeur de Viterbi
Le d´ecodeur va proc´eder en calculant, pour chaque symbole re¸cu, les chemins les plus probables dans le treillis
permettant d’arriver `
a chacun des noeuds.
3.1
Principe de fonctionnement
Au d´epart, le d´ecodeur ne connait pas l’´etat dans lequel se trouve le codeur. Tous les noeuds sont ´equi-probables,
on leur attribue une m´etrique de noeud, not´ee Mabc , nulle. Apr`es r´eception du premier symbole, il est possible de commencer `
a faire des hypoth`eses sur la transition du codeur ayant conduit `a l’´emission du symbole re¸cu.
Soit ye1 ye2 = (011, 101) le symbole re¸cu `
a t = 1. Examinons le noeud E000 et ses deux ant´ec´edents: E000 et
E001 .
La transition de E000 → E000 a comme caract´eristique Y00 . La m´etrique de cette branche sera donc d(e
y1 ye2 , Y00 ) =
5.83. De mˆeme, la m´etrique de branche correspondant `a la transition E001 → E000 sera d(e
y1 ye2 , Y11 ) = 4.47. La
deuxi`eme transition a la m´etrique la plus petite: c’est donc la plus probable. La nouvelle m´etrique de noeud
de E000 sera 4.47 et la d´ecision prise sera not´ee not´ee b (basse) pour indiquer que la branche basse arrivant au
noeud a ´et´e s´electionn´ee (Cf fig. 7). Dans le cas contraire, on notera la d´ecision par h (haut).
En proc´edant de mˆeme pour chacun des noeuds, nous obtenons le treillis de la figure 8:
Remarque : En attribuant le bit 0 `
a h et le bit 1 `a b, nous pouvons reconstituer exactement l’´evolution la plus
probable du codeur. En effet, si h (branche haute) est la d´ecision du noeud `a l’instant t alors son ant´ec´edent
est EBC0 , si la d´ecision est b (branche basse), l’ant´ec´edent est EBC1 .
Pour chaque symbole re¸cu, le d´ecodeur recommence le mˆeme calcul en tenant compte des nouvelles m´etriques
de noeuds :
Soit ye1 ye2 = (001, 110) le symbole re¸cu `
a t = 2. Nous obtenons alors :
p
d(e
y1 ye2 , Y00 ) = 12 + 62 = 6.08
p
d(e
y1 ye2 , Y01 ) = 12 + (7 − 6)2 = 1.41
p
d(e
y1 ye2 , Y10 ) = (7 − 1)2 + 62 = 8.48
p
d(e
y1 ye2 , Y11 ) = (7 − 1)2 + (7 − 6)2 = 6.08
Examinons le noeud E000 `
a t = 2 et ses deux ant´ec´edents : E000 et E001 .
4
Figure 6: R´eception de ye1 ye2 = (011, 101).
Figure 7: S´election de la branche basse pour le noeud E000 .
Transition E000 → E000 : M000 (t = 1) + d(e
y1 ye2 , Y00 ) = 4.47 + 6.08 = 10.55
Transition E001 → E000 : M001 (t = 1) + d(e
y1 ye2 , Y11 ) = 3.61 + 6.08 = 9.69
La transition E001 → E000 a la m´etrique la plus petite, elle est donc s´electionn´ee. La nouvelle m´etrique
du noeud E000 est 9.69 et sa d´ecision `
a t = 2 est b. En proc´edant de mˆeme pour chacun des noeuds, nous
obtenons le treillis de la figure 9:
3.2
Le chemin survivant
Nous appelerons chemin survivant d’un noeud le chemin g´en´er´e en partant du noeud et en remontant le treillis,
en suivant syst´ematiquement les branches s´el´eectionn´ees rencontr´ees. Par exemple, dans la figure 9, `a t=2, le
chemin survivant du noeud E010 sera: 010 → 101 → 011.
Le chemin survivant d’un noeud est le chemin du treillis le plus probable (au sens o`
u il minimise la distance entre la suite des signatures des transistions du chemin et la suite des symboles
re¸
cus) permettant d’acc´
eder au noeud.
Soit (3,5); (1,6); (4,7); (2,0); (2,7); (7,6); (1,7); (0,6); (7,2); (1,6); (2,3); (1,4) la suite des 12 premiers symboles
re¸cus -exprim´es en d´ecimal- par le d´ecodeur. Le tableau 1 donne les m´etriques de noeud aux instants t = 1 et
t = 12.
A partir de t = 12, il ne reste qu’un seul chemin survivant entre les instants t = 1 et t = 7, cela nous permet de
connaitre les sept premiers bits transmis 1, 1, 0, 1, 0, 0, 1 (voir la figure 11.b).
On peut constater que les chemins survivants convergent vers un chemin unique avec une tr`es grande probabilit´e, apr`es une remont´ee du treillis sur une longueur L suffisamment grande (de l’ordre de 20 pour le d´ecodeur
consid´er´e). On peut d´emontrer que ce noeud de convergence est la meilleure des solutions en fonction des L
symboles suivants re¸cus. Il s’agit de l’´etat d´ecod´e.
5
Figure 8: Etat du treillis `a t = 1.
Figure 9: Etat du treillis `a t = 2.
Un chemin survivant est d´efini tr`es naturellement par la suite des d´ecisions rencontr´ees lors de sa remont´ee
dans le treillis. Par exemple, le chemin survivant issu du noeud E100 `a l’instant t = 11 peut s’exprimer par la
suite des d´ecisions: b,h,h,b,h,h,h,h,b,h,b (voir fig. 11.a. La figure 10 explicite le proc´ed´e de reconstitution de
ce chemin survivant.
6
E000
E001
E010
E011
E100
E101
E110
E111
t=1
4.47
3.61
3.61
4.47
4.47
3.61
3.61
4.47
t=2
9.69
5.02
5.02
9.69
9.69
5.89
5.89
9.69
t=3
8.02
9.02
9.89
8.89
12.7
12.6
13.5
12.7
t=4
10.0
13.9
17.7
14.7
11.0
14.9
17.6
15.5
t=5
17.3
19.7
16.9
22.6
15.0
16.7
13.0
20.5
t=6
20.7
24.0
21.0
14.0
18.3
22.9
22.1
21.5
t=7
27.8
22.0
23.9
28.0
26.7
15.0
19.3
27.5
t=8
29.1
24.9
16.2
26.7
28.0
29.1
24.2
25.3
t=9
29.1
24.6
30.0
29.2
32.2
18.0
31.1
30.3
t = 10
30.7
31.4
19.4
36.4
30.7
30.7
26.5
36.4
t = 11
34.3
23.9
35.1
32.9
35.0
25.3
35.2
30.1
t = 12
30.6
38.3
28.4
34.2
28.0
36.1
32.5
36.8
t = 11
h
h
b
h
b
h
h
h
t = 12
b
h
b
b
b
b
b
b
Table 3: Evolution des m´etriques de noeuds dans le temps.
E000
E001
E010
E011
E100
E101
E110
E111
4
t=1
b
h
b
h
h
b
h
b
t=2
b
h
b
h
b
b
h
h
t=3
b
h
b
h
h
h
b
b
t=4
h
b
h
b
b
h
b
h
t=5
h
h
b
h
h
b
h
b
t=6
b
h
h
h
h
h
h
b
t=7
h
h
b
h
h
b
h
b
t=8
b
h
b
h
b
b
b
h
t=9
b
h
h
h
b
h
b
b
t = 10
b
h
b
b
b
b
b
b
Exercices d’applications sur l’algorithme
Les exercices suivants permettront de mieux comprendre le fonctionnement de l’algorithme de Viterbi.
Exercice 1
Soit {x0 , x1 , x2 , x3 , x4 , x5 , x6 , x7 , ...} = (10011010...) les premiers bits d’un message `a transmettre:
1. Reconstituer le chemin dans le treillis
2. Quelle est l’influence du noeud initial ?
3. En partant du noeud E000 , reconstituer la suite des caract´eristiques `a transmettre.
Exercice 2
Expliquer pourquoi dans le tableau 1 la m´etrique du noeud E000 diminue entre t = 2 et t = 3.
Exercice 3
A partir de la table des d´ecisions des noeuds ci-dessous, retrouver le premier ´etat d´ecod´e (on supposera que tous
les chemins survivants ont converg´e)
E000
E001
E010
E011
E100
E101
E110
E111
t=1
b
h
h
h
h
h
h
b
t=2
h
b
h
b
b
b
h
h
t=3
h
b
h
b
b
b
h
h
t=4
b
b
h
h
h
b
h
b
t=5
h
h
h
b
h
b
h
b
t=6
h
h
h
h
b
h
h
h
t=7
b
b
h
b
h
b
h
b
t=8
h
b
h
b
b
b
h
b
t=9
h
b
b
b
h
b
h
b
t = 10
b
b
b
h
b
h
b
h
Exercice 4
Soit la table indiquant les chemins survivants des noeuds du treillis `a un instant t. NB: la d´ecision `a l’instant t
se trouve `a gauche et les d´ecision ant´erieures a` t se trouvent `a sa droite.
A l’instant t + 1, le noeud E110 prend la d´ecision: “b”. Quel sera son nouveau chemin survivant ?
7
Figure 10: Chemin survivant issu du noeud E100 .
Noeud
E000 :
E001 :
E010 :
E011 :
E100 :
E101 :
E110 :
E111 :
t
b
b
h
h
h
b
h
b
t−1
b
h
b
h
b
b
b
h
t−2
h
b
b
h
b
h
h
h
t−3
h
h
b
h
h
b
h
b
t−4
h
b
h
b
b
h
b
b
t−5
b
b
h
b
b
h
b
b
t−6
b
h
h
b
b
h
b
h
t−7
h
b
b
h
h
b
h
b
t−8
b
b
b
b
b
b
b
h
t−9
h
h
b
h
h
b
h
b
t − 10
h
h
h
h
h
h
h
b
t − 11
b
b
b
b
b
b
b
h
Exercice 5
1. Que peut-on dire de l’´evolution temporelle de la m´etrique d’un noeud ? Comment ´evolue la quantit´e
Min(t)=Minimum{M´etriques de noeud `
a un instant t} en fonction du temps ?
2. Dans le cas d’une transmission sans bruit, que vaut Min(t) ?
3. Que peut-on dire sur la fonction D(t)=Max(t)-Min(t) ?
4. Trouver une borne `
a D(t).
5
Exercices d’applications sur l’architecture
Exercice 1 - Unit´
e de calcul des m´
etriques de branches
1. D´eterminer les ´equations du traitement qui doit ˆetre effectu´e dans ce bloc (distance Euclidienne).
2. Proposer une architecture combinatoire
3. Proposer une architecture `
a base de m´emoires
4. On remplace les calculs de distance Euclidiennes par des distance de Manhattan, proposer l’architecture
correspondante.
5. Sachant que y1 et y2 sont cod´es sur 3 bits, d´eterminer quelle doit ˆetre la pr´ecision des m´etriques de
branches.
Exercice 2 - Unit´
e de calcul des m´
etriques de noeuds
1. D´eterminer les ´equations du traitement qui doit ˆetre effectu´e dans ce bloc
2. D´eterminer la pr´ecision des m´etriques de noeuds.
3. Proposer une architecture pour cette unit´e de calcul.
4. Pour ´eviter tout d´ebordement des m´etriques de noeuds, lorsque toutes les m´etriques d´epassent la valeur
m´ediane (64), il faut soustraire la valeur 64 `a chacune des m´etriques de noeuds. Proposer une fonction
combinatoire qui permette de r´e´echelonner les m´etriques.
8
(a) Chemins survivants `
a t = 11.
9
(b) Chemins survivants `
a t = 12.
Figure 11: Chemins survivants `a t = 11 et t = 12.
Exercice 3 - Unit´
e de calcul du chemin survivant
Proposer une architecture `
a base de registres et de multiplexeurs
References
[1] A.J. Viterbi ”Errors bounds for convolutionnal codes and an asymptotically optimum decoding algorithm”
IEEE Transaction on Information THeory, Vol. IT-13 pp 260-269, Apr. 1967.
[2] ”Architecture VLSI pour le d´ecodage Viterbi”,
T´el´ecommunications, Juin 1991.
10
Th`ere
de
l’Ecole
Nationale
Sup´erieure
des
© Copyright 2024 ExpyDoc
