Traitement du signal

sur processeurs DSP

Rémi Mégret

ENSEIRB 2009-10

sur processeurs DSP

1

Plan

• Généralités

• Architecture des DSP• Architecture des DSP

• Développement pour un DSP

• Représentation numérique du signal

• Mise en œuvre de filtres

2

Généralités surGénéralités sur

les processeurs DSP

3

DSP: une introduction

• Quel est le contexte d’utilisation du traitement numérique du signal (TNS) ?numérique du signal (TNS) ?

• De quelles solutions dispose-t-on pour effectuer ce travail ?

• Quelle est la spécificité d’un processeur DSP (Digital Signal Processor) ?

4

Chaîne de Traitement Numérique

Signal originalGrandeur physique

Capteur

Memfsfs

G

Adaptation du

signal d’entrée

Gain + Démodulation

Signal TraitéSignal analogique

5

Filtreanti-repliement

EchantillonageEchantillonage

CAN CNAFiltre delissage

DSP

PortsE/S

QuantificationQuantification

Reconstruction Reconstruction du signaldu signal

Signal analogiqueSignal numériqueSignal numérique

Chaîne de Traitement Numérique (2)

Memcalcul

Signaux analogiques(RF, capteur physique, microphone…)

DSP

PortsE/S

AdapteurAnalogique /Numérique

Démodulation analogiquegain, échantillonnage,quantification…

Adapteur

AdapteurNumérique /Analogique

Adapteur

Modulation analogiqueCNA, amplification…

Calculsnumériques

6

AdapteurNumérique / Numérique

Transmission depuis un module numérique :coprocessing, acquisition (capteur CCD)

Traduction de protocole

AdapteurNumérique /Numérique

Le cahier des charges

• Traitement temps réel– Latence maximale autorisée entre l’arrivée d’une donnée

et la disponibilité du résultat du calcul correspondant.et la disponibilité du résultat du calcul correspondant.

• Débits de données important– Signaux numériques = quantité importante de données

transmises séquentiellement

• Charge de calcul importante– Convolution, FFT…– Charge de calcul = Débit × Complexité du calcul– Charge de calcul = Débit × Complexité du calcul

• Maîtrise de la précision des calculs

• Traitements répétitifs

7

Opérations classiques en TNS

• MAC : multiplication-accumulation

– acc ← acc + bi . xi– acc ← acc + bi . xi

– Filtres à réponse impulsionelle finie (RIF):

∑−

=

−=1

0

)()()(

P

i

inxibny

8

– Filtres à réponse impulsionelle infinie (RII):

∑∑−

=

−

=

−−−=1

1

1

0

)()()()()(

Q

j

P

i

jnyjainxibny

Opérations classiques en TNS

• MAC– Filtrage (convolution)– Correlation– Correlation– Produit scalaire

• FFT– Analyse spectrale

• DCT– Compression d’images

• Compare Select and Store• Compare Select and Store– Algorithme de Viterbi (Com. num.)

• Génération de formes d’ondes– Communications numériques

9

Applications des processeurs DSP

60,0%

80,0%source : Will Strauss, Forward Concepts,publié dans Programmable Logic 2007

0,0%

20,0%

40,0%

60,0%

Wireless MultipurposeConsumer electronics

Wireline Computer Automotive

10

72,5% 8,4% 8,2% 4,7% 3,3% 2,5%

Parts de marché vente DSP programmables (2006)

Rmq: Les SoCs, et ASIC sont également très utilisés pour des applications similaires, mais ne sont pas comptabilisés ici.

Applications

• Communications– Software Defined Radio– Sans fil (cellulaires, télévision

• Image / vidéo– Compression/Codage

– Sans fil (cellulaires, télévision numérique, radio numérique)

– Filaire (DSL, cable)– Modem– Cryptage

• Audio– Mixage et édition

– Compression/Codage

– Composition

– Traitement

• Militaire– Imagerie

• radar, sonar…

– Cryptographie– Mixage et édition– Effets– Suppression de bruit– Annuleur d’echo

– Cryptographie

– Guidage de missiles

– Navigation

11

Applications

• Biomédical– Equipements de monitoring

• Signaux biophysiques

• Automatisation– Commande de machines– Contrôle de moteurs• Signaux biophysiques

• ElectroEncéphaloGramme (EEG)

• ElectroCardioGramme (ECG)

– Radiographie

• Instrumentation– Analyseurs de spectre

Générations de fonctions

– Contrôle de moteurs– Robots– Servomécanismes

• Electronique Automobile– Contrôle du moteur– Assistance au freinage– Aide à la navigation– Générations de fonctions

– Analyseurs de régimes transitoires

– Aide à la navigation– Commandes vocales

12

Constructeurs de processeurs DSP

50%

60%

70%Chiffres 2007Source : Forward Concepts

Wireless/DSP Market Bulletin, 4 Fevrier 2008

0%

10%

20%

30%

40%

50%

65% 12% 7% 3% 13%

Texas Instruments

Freescale (Agere)Analog Devices

Autres (NXP, NEC,

13

dspvillage.ti.comwww.freescale.comAgere -> LSI, Infineonwww.analog.com

Marché de 7.8 Milliards de $ en 20072006-2007: -6.7%2007-2008:+7% (prévision)

Parts de marché vente DSP programmables (2007)

Source: http://www.fwdconcepts.com/DSPBulletin_2408.pdf

Famille TMS320 Texas Instruments

C2000 C5000 C6000

Lowest Cost

Control Systems� Motor Control

� Storage

� Digital Ctrl Systems

Efficiency

Best MIPS perWatt / Dollar / Size� Wireless phones

� Internet audio players

� Digital still cameras

� Modems

� Multi Channel and Multi Function App's

� Comm Infrastructure� Wireless Base-stationsDSL

Performance &Best Ease-of-Use

virgule fixe 16 bits

14

� Modems

� Telephony

� VoIP

� DSL� Imaging� Multi-media Servers� Videovirgule fixe 16 bits

virgule fixe et flottante, 32 bits

Clients mobiles Infrastructure

15

Famille DSP Analog Devices

16

TigerSHARC : virgule flottante 24 bits, hautes performances

ADSPBFxx (Blackfin) : virgule fixe 16 bits, hautes performances

SHARC : virgule fixe ou flottante 32 bits

ADSP21xx : virgule fixe 16 bits

Traitement numérique vs. analogique

En quoi le passage par le numérique est-il intéressant,même lorsque l’entrée et la sortie sont analogiques ?

Signalanalogique

Signalanalogique

Circuit électronique à composants analogiques

17

DSPCAN CNASignalanalogique

Signalanalogique

Signalnumérique

Signalnumérique

Traitement Numérique vs. Analogique

Numérique AnalogiqueFixes et connus à l'avance

Dépend de la qualité des Précision / RSB

Fixes et connus à l'avance

Liés à la taille des mots mémoire (16/24/32 bits)

Dépend de la qualité des composants

Sources de bruitEchantillonnage

Quantification

Bruit électromagnétique,

température, humidité, vieillissement

Reconfigurabilité Changer le logiciel

Matériel

Calibration nécessaire(Arrivée récente de puces reprogrammables (Arrivée récente de puces reprogrammables incluant des composants analogiques)

Largeur de bande utilisable

Limitée par l'échantillonnagePeut travailler à très haute

fréquence

18

Un exemple: la radio logicielle(Software Defined Radio : SDR)

• Complexité accrue des traitements sur le signal– Modulation à large bande, multi-utilisateurs (CDMA, OFDMA…) et adaptative– Egalisation, estimation de canal– Codes correcteurs d’erreurs (Turbo-codes)– Codes correcteurs d’erreurs (Turbo-codes)

• Multiplicité des protocoles de communication– Reconfigurabilité logicielle du protocole utilisé

19Image: Agilent Technologie, http://www.soccentral.com/results.asp?CatID=488&EntryID=24811

SDR Development Platform(www.lyrtech.com)

TMS320DM6446 SoC ARM+DSPVirtex-4 SX35 FPGADAC/ADCRF Module

Plateformes matérielles pour le Plateformes matérielles pour le

traitement numérique du signal

20

Solutions matérielles pour le TNS

• Processeur– Processeur d’usage général– Microcontrôleur

Architectureprocesseur– Microcontrôleur

– DSP (Digital Signal Processor)

• Multiprocesseurs– GPU (Graphics Processing Unit)

• Architectures reconfigurables– FPGA (Field-Programmable Gate Array)

processeur

– FPGA (Field-Programmable Gate Array)

• Architectures figées– ASSP (Application Specific Standard Product)– ASIC (Application-Specific Integrated Circuit)

21

Architecturespécialisée

Exemple d'un filtre RIFArchitecture dédiée (FPGA / ASIC)

x(n)

p

∑−

=

−=1

0

)()()(

P

i

inxibny

b(0) b(1) b(2) b(3) b(4) b(5)

log2(p)

22

y(n)

log2(p)

Architecture systolique dédiéeTraitement fortement parallèleEfficace pour le RIF, mais peu flexible

Exemple d'un filtre RIF Architecture processeur

∑−

=

−=1

0

)()()(

P

i

inxibny

Mémoire

E/S

bx programmey

CPU

unités de

calcul

registres

23

Architecture de type processeurTraitement séquentielProgramme stocké en mémoire : facile à modifier

Microprocesseur d’usage général(General Purpose Processor, GPP)

• Intel Pentium• Motorola PowerPC, 68000• Digital Alpha Chip

• Nombreuses fonctionnalités pas toujours utiles– Augmente le coût et la • Digital Alpha Chip

• Sun SPARC• PXA250 (RISC)

• Formats de données variés– sur 32 ou 64 bits

• Adaptés aux langages évolués• Bonnes performances en calcul

numérique

– Augmente le coût et la consommation électrique

• Gestion matérielle de la mémoire virtuelle– Nécessaire pour l’utilisation de

systèmes d’exploitation avancés

• Fonctionnalités dynamiques qui compliquent la garantie temps réel– Cache de données

• Bonnes performances en calcul numérique– Instructions spécifiques (MMX,

SSE…)

• Tendance aux évolutions multi-coeurs

– Cache de données

24

Microcontrôleur

• Motorola 68HC11

• Intel 8751

• Peu adapté aux signaux numériques• Intel 8751

• MicroChip PIC16/17

• Cypress PsoC

• Faible coût

• Faible consommation électrique

– Périphériques à faible débit

– Données sur 8 ou 16 bits

• Adaptés aux tâches de contrôle– Embarqué, temps réel

– Calculs logiques

électrique

• Mémoire limitée

• Utile pour calculs peu complexes

25

Processeur DSP

• Texas Instrument TMS320Cxxxx,

• Processeur– Programme en mémoire– Exécution séquentielle• Freescale 56000, 96000

• Analog Devices ADSPxxxx, SHARC, Blackfin

• Architecture spécialisée pour les traitements numériques

– Exécution séquentielle– Jeu d'instruction spécialisé

• Calculs numériques– Addition, Multiplication– Unités de calcul spécialisées

(filtrage, FFT…)

• Entrée-sortie de données– Grand débitnumériques

– Coût, encombrement et consommation au plus juste

– Grand débit– Périphériques intégrés

26

DSP et processeur d’usage général

• Un processeur DSP est préférable pour:

– Minimiser la taille

Minimiser la consommation– Minimiser la consommation

– Traitement temps-réel à grand débit

• Un processeur d’usage général est préférable pour:

– Disposer d’une grande quantité de mémoire

– Développer sous un système d’exploitation avancé

– Nécessité de mixer calcul numérique et autres tâches– Nécessité de mixer calcul numérique et autres tâches

27

Exemple : TMS320C6200 vs. Pentium

Processor Pea k MIPS

ISR la t ency

Pow er Un i t Pr ice

Area Volum e

Pent ium III 1200

2400 1.14 µs 4.25 W $29 5.5” x 2.5” 8.789 in 3

C6200 200 MHz

1600 0.09 µs 1.94 W $25 1.3” x 1.3” 0.118 in 3

C6200 300 MHz

2400 0.06 µs $96 1.3” x 1.3” 0.118 in 3

28

BDTImarks: Berkeley Design Technology Inc. DSP benchmark

results (larger means better) http://www.bdti.com/bdtimark/results.htm

Source: http://www.ece.utexas.edu/~bevans/courses/ee382c/lectures/processors.html

GPU (Graphics Processing Unit)

• Nombreuses unités de calcul indépendantes en parallèle• Streaming Processor (SP)• Texture Filtering Unit (TF)

• Programmation spécifique (CUDA, OpenCL…)

• NVIDIA • ATI

• Programmation spécifique (CUDA, OpenCL…)• Très efficace si GPU disponible (calcul scientifique, traitement d’image)• Risqué si contraintes de pérennité et de certification (aéronautique)

SP TF

29Nvidia GeForce 8800 Series GPU Block Diagram

FPGA (Field-Programmable Gate Array)

• Altera• Xilinx

• Logique reconfigurable– VHDL compilé puis chargé sur

la puce– Facile à reconfigurer (mais

pas en cours de fonctionnement)

• Produits récents intégrentdes blocs « DSP »

• Produits récents intégrentdes blocs « DSP »– Unités arithmétiques simples

• Adapté si calculs fortement parallélisables

30

Exemple d’architecture:Altera Stratix

ASSP (Application Specific Standard Product)

• Puce spécialisée pour une application spécifique– Peut être programmable ou pas

Décodage analogique, démultiplexage, décryptage, décodage MPEG2, interface vers sortie vidéo ou numérique, télétexte…

Exemple: Micronas MDE9500 « Single-chip DigitalTV mixed-signal decoder »Fonctionnalités nécessaires pour un poste de télé numérique

31

ASIC (Application-Specific Integrated Circuit)

• Puce conçue entièrement pour l'application visée– Parfaitement adapté à

• Conception prend du temps– Développement d'un circuit

– Parfaitement adapté à l’application

• Meilleures performances– Calcul et vitesse– Consommation

• Passage par un fondeur– Coûts de développement

élevés

– Développement d'un circuit complet en VHDL

• Cœurs licenciables– Intégration d’IP

• cœurs DSP

• modules d’E/S

– Permet la réutilisation de conceptions éprouvées

élevés– Peu flexible

conceptions éprouvées

– Personnalisation possible de l’architecture

32

Compromis pour l’implantationd’algorithmes de traitement du signal

ASIC ASSP GPPDSPFPGA

Matériel dédié Matériel génériqueComplexité dans le logiciel

Performance pour une application spécifiqueContraintes temps réel Flexibilité

33

Contraintes temps réelContraintes de consommation

FlexibilitéDélai de mise sur le marché

Coût de développement plus faible

Architecture d’unArchitecture d’un

processeur DSP

• Accès mémoire et E/S• Accès mémoire et E/S

• Unités du CPU

• Pipelining

34

Architecture générale d’un processeur

Processeur

CPUUnité decontrôle

Unités detraitement

Bus internes

CPU

35

Mémoireinterne

Unité deCommunication

Périphériqueset mémoire externes

Accès à la mémoire

36

Rappels : Bus

• Le CPU est le maître du bus– Il est le seul à écrire sur les

bus adresse et contrôlePériphériqueCPU BUS

bus adresse et contrôle

• Le périphérique obtempère sur le bus données– Lecture: il fournit la donnée

demandée

– Ecriture : il récupère la donnée fournie par le CPU

– Haute impédance: il se

PériphériqueCPU

adresses

données

contrôle

37

– Haute impédance: il se déconnecte du bus

Contrôle : lire / écrire / haute impédance

Adresses : sélection du périphériqueet d’une donnée en son sein

Données : valeur de la donnée à échanger

Etapes d’une opération de calcul

11

33

22

(1) Charger une instruction (Fetch)

(2) Décoder l’instruction (Decode)

MémoireCPU33

44

55

(2) Décoder l’instruction (Decode)

(3) Charger les opérandes (Read)

(4) Effectuer les calculs (Execute)

(5) Stocker le résultat

38

Architecture Von Neuman

Mémoire

• Un seul chemin d'accès à la mémoire• Architecture des processeurs d’usage général (Pentium, 68000)

CPU BUSMémoire

Programme+ Données

• Architecture des processeurs d’usage général (Pentium, 68000)• Goulot d'étranglement pour l'accès à la mémoire• Pas de sécurisation matérielle du programme

– Responsabilité dévolue au système d’exploitation (logiciel)

39

Architecture Harvard

Mémoire Programme

• Séparation des mémoires programme et données

• Moins de risque de corruption du programme

Mémoire Données

CPU

• Moins de risque de corruption du programme

• Meilleure utilisation du CPU– Chargement du programme et des données en parallèle

40

Architecture Harvard modifiée

Mémoire ProgrammeMémoire Programme

+ Données

• Mémoire programme contient des données

• Possibilité de charger 2 données en un cycle

CPU

+ Données

Mémoire Données

• Utilisation classique en TNS– Mémoire Programme+Données → coefficients des filtres

– Mémoire Données → échantillons d’entrée

41

Accès mémoire multi-port

Mémoire Programme+ Données

• Plusieurs bus de données– Accès simultané à plusieurs données

– Nécessite une mémoire multi-accès ou multi-blocs

CPU

+ Données

Mémoire Données

– Nécessite une mémoire multi-accès ou multi-blocs

• Exemple du TMS320C54xx :– 1 bus programme (P)

– 2 bus de lecture des données (C et D)

– 1 bus d’écriture des données (E)

42

Exemple

CPUMémoire Donnéesb[0]…b[N-1]x[0]…x[N-1]

Bus C

x[0]…x[N-1] Bus D

Pour l’opérationy[n] ← b[n] * x[n]

On souhaite récupérer b[n] et x[n]

Chaque bus est capable de transmettre 1 donnée par cycle

43

Chaque bus est capable de transmettre 1 donnée par cycle

La limite est imposée par les capacités de la mémoire:- Mémoire à Simple Accès (SARAM) => 2 cycles - Mémoire à Double Accès (DARAM) => 1 cycle- Mémoire externe => temps de latence dépend de la qualité de la mémoire

Multiplexage spatial(Mémoire multi-blocs)

• Découpage en blocs indépendants– Accès simultané à deux blocs distincts

• Exemple

CPUb[0]…b[N-1]

Bus C

Bus Dx[0]…x[N-1]

• Exemple– b[n] stockés dans le bloc 1, x[n] stockés dans le bloc 2

Bus C

Utilisation desressources

Adresses@b[0] sur bus C@x[0] sur bus D

b[0] et x[0]lus par le CPU

Adresses@b[1] sur bus C@x[1] sur bus D

b[1] et x[1]lus par le CPU

Adresses@b[2] sur bus C@x[2] sur bus D

44

Bus D

Bloc 1Bloc 2

…1 cycle

b[0]

x[0] x[1]

b[1]

temps

Traitement simultané des requêtes des deux bus

Multiplexage temporel(Mémoire multi-accès)

• Plusieurs accès à la même mémoire en un cycle– Le CPU récupère cependant une donnée par cycle et par bus

CPUMémoire Donnéesb[0]…b[N-1]x[0]…x[N-1]

Bus C

Bus DDARAM fonctionne à 2f0

Fréquence decycle f0

– Le CPU récupère cependant une donnée par cycle et par bus

Bus C

Utilisation desressources

Adresses@b[0] sur bus C@x[0] sur bus D

b[0] et x[0]lus par le CPU

Adresses@b[1] sur bus C@x[1] sur bus D

b[1] et x[1]lus par le CPU

Adresses@b[2] sur bus C@x[2] sur bus D

45

Bus C

Bus D

Mémoire

1 cycle

b[0] x[0] x[1]b[1]temps

Ordonnancement des requêtes des deux bus

Mémoire interne sur les processeurs C54x

Capacité en mémoire interne de différents modèles C54x

Découpage en blocs

• Plusieurs types de RAM incluse sur le chip– Single access (SARAM) : un accès par cycle– Dual access (DARAM) : deux accès par cycle– Two-way shared : deux accès par cycle même depuis l'extérieur

• DARAM découpée en blocs– Accès simultané à deux blocs de mémoire différents– 2x2=4 accès par cycle en théorie (en réalité limité par le reste de l'architecture)

46sources : "TMS320C54x DSP Functional Overview", SPRU307A, Texas Instrument"TMS320VC5416 DSK Reference Technical", Spectrum Digital

Cache d'instructions

DSP

Mémoire Programme+ Données

cached’instructions

• Cache = mémoire associative rapide– Contient les dernières instructions exécutées

• Utile en cas de boucle

+ Données

Mémoire Données

CPU

• Utile en cas de boucle– Accès aux instructions sans accès à la mémoire programme– Libère le bus pour des données, ou pour un gain en consommation

• Cache pour les données– Peu utilisé sur DSP classiques– De plus en plus utilisé sur les DSP hautes-performances– Peut poser des problèmes pour la validation du temps réel

47

Bus externedans une architecture Harvard

DSPMémoire Programme

+ Données

Transfert entre les bus

MUX

CPU

+ Données

Mémoire Données

48

Transfert entre les bus internes et externe par multiplexage temporel

• Limitation du nombre de broches • Réduction des coûts• Diminution des performances lors des accès au bus externe

Accès Direct à la Mémoire(DMA : Direct Memory Access)

• Mouvements de données– E/S direct entre

périphérique et mémoire périphérique et mémoire interne

– Déplacements au sein de la mémoire interne

• Indépendant du CPU– Configuration par le CPU

une fois pour toutes

– CPU prévenu du déroulement par interruptions

DMA

CPU Mémoire Interne

interruptions

configurationinterruptions• Buffer plein (en réception)

/ Buffer vide (en émission)

• Buffer à demi-plein

49

configuration

E/S

Périphériques(Port Série, Mémoire externe…)

DMA et buffer ping-pongpour le traitement par blocs

CAN

McBSP2 McBSP2

CNA

DSPCAN

DRR DXRCNA

DMA4 DMA5

PINGIN

PONG

PINGOUT

PONGTraitement

PINGIN1

PINGOUT

1

PONG

PINGIN3

PONG

50

PONGIN

PONGOUT

Traitement

Source: Texas Instruments C5000 DSP Teaching Kit

Buffers en mémoire Buffers en mémoire

PONGIN2

PONGOUT

2

Chronogramme des échanges de données

temps

Entrée CAN => BSP x[0] x[N-1] x[4N]… …x[N] x[2N-1]… x[2N] x[3N-1]…

BSP => PING IN

Traitement PING

BSP => PONG IN

Traitement PONG

… …… …

Interruptionbuffer mi-plein

Interruptionbuffer plein

Interruptionbuffer mi-plein

51

PING OUT => BSP

PONG OUT => BSP

BSP => Sortie CNA y[0] y[N-1]… y[2N] y[2N-1]…

Latence de 2 blocs

Architecture interne du CPU

52

Schéma de principe des échanges

SéquenceurGénération Génération

Registres etUnités de

CPU pilotage

addr

datactrl

Séquenceur

Bus

programme

Générationadresses P

Générationadresses D

Unités decalcul

53

addr

datactrl

programme

Bus

données

Mémoire P Mémoire D périphériques

Détail des unités

• Séquenceur– Décodage des instructions

– Pilotage les autres unités– Pilotage les autres unités

• Unité de génération d’adresse programme– Compteur de programme (PC)

– Gestion matérielle des boucles

• Unité de génération d’adresses données– Adressage indirect efficace (*p++)

– Adressage circulaire, bit-reverse– Adressage circulaire, bit-reverse

• Unités de traitement– Effectuent les calculs

– Registres pour résultats intermédiaires

54

Fetch (lecture instruction)

SéquenceurGénération Génération Unités de

addr

datactrl

Séquenceur

Bus

programme

Générationadresses P

Générationadresses D

Unités decalcul

PCInstruction

55

addr

datactrl

programme

Bus

données

Mémoire P Mémoire D

Read/Write (lecture/écriture donnée)

SéquenceurGénération Génération Unités de

SéquenceurGénérationadresses P

Générationadresses D

Unités decalcul

addr

datactrl

Bus

programme

ARi Donnée

56

Mémoire P Mémoire D

addr

datactrl

programme

Bus

données

Diagramme bloc du TMS320C5416

D(15-0)

Program/Data RAM128K Words

Program/Data ROM16K Words

Mémoireinterne

JTAG Test/EmulationControl

Bus externe

Muxed GP I/O

A(23-0)

Program/Data Buses

Timer

Ch 0

Ch 1

Ch 2

Ch 3

Ch 4

Ch 5

DMA

8/16-bit Host PortInterface (HPI)

Peripheral Bus

RND, SAT

17 x 17 MPY

40-Bit Adder

MAC

Shifter

40-Bit Barrel(-16, 31)

EXP Encoder

40-Bit ALUCMPS Operator(VITERBI)

ALU

Accumulators

40-Bit ACC A

40-Bit ACC B

Multichannel BufferedSerial Port (McBSP)

Multichannel BufferedSerial Port (McBSP)

Unités decalcul

ControlMUX

57

Ch 540-Bit ACC B

8 Auxiliary Registers

2 Addressing Units

Addressing UnitMultichannel BufferedSerial Port (McBSP)

PLL Clock Generator

S/W WaitstateGeneratorPower Management

Générationd’adresses

EntréesSorties

CPU

Structure interne du TMS320C54x

58

Source : Texas InstrumentsTMS320C54x DSPReference SetVol 1 : CPU and Peripherals

Unité de controle

Générationd'adressesprogramme

Générationd'adressesdonnées

Zero overhead looping Adressage indirect :Pré- et post-incrémentation

automatique

Bus Pprogramme

Bus C / Dlecture

59

lecturedonnées

Bus Eécrituredonnées

4 bus : Accès simultané à 1 instruction + 2 opérandes + 1 écriture

ALU

Shifter

Viterbi

Registres

60

MACViterbi

Calcul MAC en un cycle Multiplication par 2k en un cycle

Architectures des unités de traitement

• Architecture accumulateur

Couplage accès mémoire et calcul Accès mémoire et calcul découplés

• Architecture Load/Store

• Architecture à registres et mémoire

ACC

RAMR0

RAMR1

R2

R3registres et mémoire

61

R0

RAMR1

R2

R3

R3

Calcul d’un filtre RIF en N+2 cycles

( ) ( )∑−

=

−=1

0

)(N

i

inxibnyGestion matérielle des boucles :Unité de génération d’adresses programme

A=0;

for (i=0; i<N; ++i) {

=0i

B[i] X[i]Y

Unité de génération d’adresses programme

Unité MAC matérielle+ Chargement simultané de l’instruction et des opérandes

SSBX FRCTSTM #B, AR2

62

for (i=0; i<N; ++i) {

A = A + B[i] * X[i];

}

Y = A >> 15;Unité de génération d’adresses données

STM #X, AR3STM #Y, AR4

RPTZ A, #N-1 (x1)MAC *AR2+,*AR3+, A (xN)

STH A, *AR4 (x1)

Equivalent ASMCode C

Boucles matérielles / Zero overhead looping

• Répétition d’une Instruction (N) fois

RPTZ A, #54 ;A � 0 et RC � 54

RC N - 1

Instructions RPT et RPTZ

• Répétition d’un Bloc d’Instructions (N) fois

BRC N - 1

RPTZ A, #54 ;A � 0 et RC � 54

MAC *AR2+, *AR3+, A ;La valeur pointée par ;AR2 est additionnée à la ;valeur pointée par AR3, ;55 fois

STM #54, BRC ;Répétition 55 fois

RPTB fin-1 ;RSA chargé avec PC+2;REA chargé avec endblk-1

63

RSA Première

Adresse

REA Dernière

Adresse

Instructions RPTB et RPTBD

;REA chargé avec endblk-1

MPY *AR2+0%, A

LMS *AR3, *AR2

ST A, *AR3+

fin :

STH A, *AR3

RSA

REA

Utilisation de l’adressage indirect

; A accumulateur; X=@X[0], Y=@Y[0]

long A;int X[100],Y[100];int *px, *py;

Produit scalaire entre deux vecteur

LD #X, AR2LD #Y, AR3

RPTZ A, #99 MAC *AR2+, *AR3+, A

int *px, *py;

px=X;py=Y;A=0;for (i=0; i<100; ++i)A = A + (long)(*px++)*(*py++);

Y[i]X[i]

64

; AR3=@Y[idx] déjà assigné

LD #X, AR2STM #N,BK

RPTZ A, #99 MAC *AR2+, *AR3+%, A

A=0;for (i=0; i<=99; ++i) {idd = idx + i;A = A + (long)X[i] * Y[idd%N];

}

Filtre RIF avec buffer circulaire (voir chapitre « Mise en œuvre de filtres RIF et RII »)

Adressage indirect bit-reverse

• Ordre des données pour la FFT

x(0)

x(1)

x(2)

x(3)

x(4)

x(5)

65

Ordrebit-reverse

Ordrenaturel

Implémentation récursive de la FFT

X(k) = TFD( x(n) )Ordrenaturel

x(6)

x(7)

Réorganisation des données

Unité d’adressage indirect(Génération d’adresses données)

Registres d'adressage Unités de calcul spécialisées

Ecriture sur les bus d'adresse des bus C, D et E

66

Optimisation de la part du compilateur C

813D toto813D PSHM 11h Sauvegarde AR1 (save-on-entry)813E FRAME -1813F SSBX SXM Manipulation de nombres signés8140 LD #100h,0,A A <= 256 (100h)

#define N 256

short in[N];short out[N];

Code C Pas d’optimisation

8140 LD #100h,0,A A <= 256 (100h)8142 ST #0h,0h Met la valeur initiale 0 de i dans pile[0h]8144 SUB 0h,A A <= A - pile[0h]8145 BC 8154h,ALEQ Si A<=0, alors aller à fin:

debut :8147 MVDK 0h,11h Copie pile[0h] dans AR18149 LD *AR1(817),A Charge in[AR1] dans A814B STL A,*AR1(1073) Stocke A dans out[AR1]814D LD #100h,0,A A <= 256 (100h)814F ADDM 1h,0h pile[0h] <= pile[0h] + 18151 SUB 0h,A A <= A - pile[0h]8152 BC 8147h,AGT Si A>0 alors reboucler sur debut:

fin:8154 FRAME 1

void toto()

{

int i;

for (i=0; i<N; i++) {

out[i]=in[i];}

}

Adresses des tableaux

67

8033 toto8033 STM 431h,13h AR3 <= @out8035 STM 331h,12h AR2 <= @in8037 RPT #0ffh Répéter 256=255+1 fois8038 MVDD *AR2+,*AR3+ *AR3 <= *AR28039 NOP 803A NOP 803B FRET

8154 FRAME 18155 POPM 11h Restaure de AR18156 FRET Retour de la fonction

Optimisation au niveau fonction (-o2)

_inputData = 331h = 817_outputData = 431h = 1073

Adresses des tableaux

Prise en compte descapacités matérielles du DSP

Pipelining

68

Pipelining

• Instructions segmentées en étages

• Exécution entrelacée de plusieurs instructions

• Exemple du TMS320C54xx :pipeline à 6 étages– Prefetch (P)

• Incrémentation du PCinstructions– Chacune à une étage différent

• Augmentation de la fréquence d'horloge– Etages plus simples donc plus

rapides

• Géré par le séquenceur

• Incrémentation du PC(Program Counter)

– Fetch (F)• Lecture de l’instruction en

mémoire

– Decode (D)• Décodage de l’instruction

– Access (A)• Calcul des adresses des

opérandesopérandes

– Read (R)• Lecture des opérandes en

mémoire• Calcul de l’adresse du résultat

– Execute (X)• Exécution du calcul• Ecriture en mémoire

69

Séquentiel vs pipeline

t1 t2 t3 t4 t5 t6 t7 t8

Instruction Instruction 1 Instruction 2

Fetch F1 F2

-

-

MemP

D1

F1

t1 t2 t3 t4 t5 t6 t7 t8

Fetch F1 F2 F3 F4 F5 … … …

Fetch F1 F2

Decode D1 D2

Read R1 R2

Execute X1 X2

Exécution séquentielle

F4 MemPF5

-

-

-

MemD

MemD

CPU D1

R1

X1

Fetch F1 F2 F3 F4 F5 … … …

Decode D1 D2 D3 D4 D5 … …

Read R1 R2 R3 R4 R5 …

Execute X1 X2 X3 X4 X5

70

Amorçage du pipeline

Exécution avec pipeline : entrelacement des instructions

D3

R2

X1

MemD

MemD

CPU D4

R3

X2

Retards dans le pipeline

• Le pipeline atteint son plein rendement une fois qu’il est amorcé

Une retard peut se produire• Une retard peut se produire

– en cas de rupture de séquence (vidange du pipeline)• branchement mal prédit

• appel de sous-programme

• interruption

– s’il existe un conflit de ressources (retard ponctuel, “bulle” – s’il existe un conflit de ressources (retard ponctuel, “bulle” dans le pipeline)• accès à la mémoire

• utilisation des bus

71

Exemple de rupture de séquence

Code à exécuter :1: Instr12: Si B==1 Alors GOTO 10:3: Instr3

…10: Instr1011: Instr11

t1 t2 t3 t4 t5 t6 t7 t8

F F1 F2 F3 F4 F5 F10 F11 F12

3: Instr34: Instr45: Instr56: Instr6

t1 t2 t3 t4 t5 t6 t7 t8

F F1 F2 F3 F4 F5 F6 … …

Si prédiction incorrecte (B=1) Si prédiction correcte (B≠1)

11: Instr1112: Instr12…

Etat du pipeline avec prédiction que B≠1 :

72

F

D D1 D2 D3 D4 ! D10 D11

R R1 R2 R3 ! ! R10

X X1 X2 ! ! !

F

D D1 D2 D3 D4 D5 D6 …

R R1 R2 R3 R4 R5 R6

X X1 X2 X3 X4 X5

Vidange du pipeline:Perte de 3 cycles

Evaluation du prédicat (B==1)=> rupture de séquence

Evaluation du prédicat (B==1)=> pas de rupture

Exemple de conflit d'accès mémoire

Programmes et Données dans la même mémoire à 1 accès par cycle

t1 t2 t3 t4 t5 t6 t7 t8

�Conflit pour l’accès mémoire entre Fetch et Read

�Les lectures de données R1/R2 empêchent les chargements d'instruction F3/F4

�Réductions des performances d'au moins 50%

Fetch F1 F2 conflit conflit F3 F4 ! !

Decode D1 D2 ! ! D3 D4 !

Read R1 R2 ! ! R3 R4

Execute X1 X2 ! ! X3

88

�Réductions des performances d'au moins 50%

�Problème réglé si

�Mémoire multi-accès

�Programmes et Données dans des mémoires différentes (ou multi-bloc)

Effets du pipeline lors du débogage

Code à exécuter :1: A=12: B=1

Watch WindowA 1B 1C 1

La flèche indique la position du PCPlusieurs cycles sont nécessaires 2: B=1

3: C=1… NOP …10: A=211: B=212: C=213: D=214: E=2…

C 1

Watch WindowA 1 ???B 1C 1

Watch WindowA 2 !!!

t1 t2 t3 t4 t5 t6 t7 t8

F F10 F11 F12 F13 F14 … … …

Plusieurs cycles sont nécessaires avant que la variable soit modifiée :Cela n’intervient qu’à l’étape X (exécution)

74

A 2 !!!B 1C 1

D D10 D11 D12 D13 D14 … …

R R10 R11 R12 R13 R14 …

X A=2 B=2 C=2 D=2 E=2

Watch WindowA 2B 2C 1

Résumé caractéristiques des DSP

• Câblage des opérations les plus critiques– Unités de calculs spécialisées

• Opération MAC cablée

– Modes d’adressages spécialisés• Accès en mémoire selon des schéma prédéfinis

– Boucle matérielle• Pas de perte de temps pour les instructions répétées

• Gestion des entrées/sorties intégrée• Gestion des entrées/sorties intégrée– Mémoire, DMA, timers

– Interfaces série / parallèle

– Interruptions à faible latence

75

Résumé caractéristiques des DSP (2)

• Augmentation du parallélisme

– Calculs• Unités de calcul en parallèle• Unités de calcul en parallèle

– Mémoire à accès multiples• Lecture/Écriture de plusieurs données simultanément

• Augmentation de la fréquence d’horloge

– Pipelining

• Découpage des instructions de façon à les exécuter à intervalles • Découpage des instructions de façon à les exécuter à intervalles plus rapprochés

76

Mesures des performances

MFLOPSMillion Floating–Point Operation Per Second

Mesure le nombre d’opérations

arithmétiques à virgule flottante que le

DSP à virgule flottante peut réaliser

en une secondeen une seconde

MOPSMillion Operation Per Second

Mesure le nombre total d’opérations

(calcul, accès DMA, transferts, etc.) que

le DSP peut réaliser en une seconde

MIPSMillion Instructions

Per Second

Mesure le nombre de codes machine

(instructions) que le DSP peut réaliser

en une seconde

MMACSMillion of MAC Mesure le nombre d’opérations MAC

(Multiply+Accumulate) que le DSP peut

77

MBPSMega-BytesPer Second

Mesure la bande passante d’un bus

particulier ou d’un dispositif d’E/S

MMACSper Second

(Multiply+Accumulate) que le DSP peut

réaliser en une seconde

Performances pour une application (benchmarking)

• Pour avoir une idée des performances concrètes des DSP, seul reste le benchmarking

• Benchmarks effectués par des sociétés de conseil telles que– Berkeley Design Technology Inc. (www.bdti.com)– Berkeley Design Technology Inc. (www.bdti.com)

– Embedded Microproc. Benchmark Consortium (www.eembc.org)

• Spécifications générales des benchmarks:– SPEC95: couvre plusieurs domaines tels que les vocodeurs, les

modems, les applications multimédia

Algorithme Standard

78

de Traitement du Signal

Temps d’exécutionConsommation électrique

Les évolutions récentes dans

• SIMD

Les évolutions récentes dans

l’architecture des DSP

• SIMD

•MIMD / VLIW

• Puces multi-cœurs

79

Perspective historique

1970 1971: Intel 40041972: Intel 80081974: 1er microcontrôleur : TMS1000

1er ordinateur personnel (8008)

1980

1990

1er ordinateur personnel (8008)1979: 1er DSP single-chip : Bell Labs Mac 4

Intel 80861980: 1er DSP autonome : NEC µPD77101981: IBM PC (8088)1983: 1er succès commercial pour un DSP : TMS320C101986: MIPS -> R2000, premier microprocesseur RISC commercial1989: Intel 486 (Utilisation d’un pipeline)1993: Intel Pentium, PowerPC 6011996: 1er DSP VLIW : TMS320C62xx

80

2000

1996: 1er DSP VLIW : TMS320C62xx1997: Jeux d’instruction MMX, 3DNow!, Altivec1999: Pentium III (Jeu d’instruction SSE)2000: Pentium 42004: Jeu d’instruction SSE32005: Cell processor2006: Pentium Core Duo2007: TMS320DM6467 (SoC DSP+ARM Traitement Vidéo)

Historique des DSP

• 1e génération 1979– Architecture Harvard

• 4e génération 1992– Image et vidéo

– Processeurs faible – Architecture Harvard

– Multiplieur cablé

• 2e génération 1985– Parallélisme

– Bus multiples

– Mémoire sur la puce

• 3e génération 1988

– Processeurs faible consommation

• 5e génération 1996– SIMD

– VLIW

• Plus récemment– SoC DSP

• 3e génération 1988– Virgule flottante

• Homogènes (Multi-DSP)

• Hybrides (RISC+DSP)

– Co-design hardware-software

81

Limites des architectures conventionnelles

Processeur DSP conventionnel = Harvard + Câblage des opérations critiques

• Performances bornées– Limite physique à l’augmentation des fréquences d’horloge

• Architecture très spécialisée– Jeux d’instructions CISC irréguliers

– Peu de portabilité

– Inefficacité des optimisation automatiques du compilateur– Inefficacité des optimisation automatiques du compilateur

– L’optimisation nécessite du savoir-faire

• Peu de parallélisme– …ou alors très limité

– Exemple: MACD = ADD + MPY + MOV

82

Vers plus de parallélisme…

• SISD = Single Instruction, Single Data

• SIMD = Single Instruction, Multiple Data• SIMD = Single Instruction, Multiple Data

• MIMD = Multiple Instruction, Multiple Data

A1 B1 A2 B2

Instruction 1ADD

Données 1 Données 2

Instruction 2MUL

MIMD

InstructionADD

Données 1 Données 2

SIMD

InstructionADD

Données 1

SISD

83

ALU1 ALU2

A1 B1 A2

R1 = A1 + B1

B2

R2 = A2 × B2

ALU1 ALU2

A1 B1 A2

R1 = A1 + B1

B2

R2 = A2 + B2

ALU1

A B

R = A + B

L’approche SIMD…

• SIMD = Single Instruction Multiple Data

• Introduit sur les processeurs d’usage général• Introduit sur les processeurs d’usage général– MMX (Intel), 3DNow! (AMD)

– SSE (x86), Altivec (PowerPC, Cell)

InstructionADD

Données 1 Données 2

SIMD par unités parallèles

A ← [A1,A2]B ← [B1,B2]

Instructionpacket_add

Données

SIMD par partage d’unité

84

ALU1 ALU2

A1 B1 A2

R1 = A1 + B1

B2

R2 = A2 + B2

Données 1 Données 2

ALU

B ← [B1,B2]

B

R = packed_add(A,B)

Données

A

R → [A1 + B1, A2 + B2]

Empaquetage des données

Dépaquetage des données

SIMD : exemple de l’extension SSE Addition de deux vecteurs

•Code C séquentiel •Code C vectoriséSSE=Streaming SIMD Extensions

r ← a + b

/* Déclaration de 4 vecteurs 32 bits */

float a[4], b[4], r[4];

/* Addition case par case */

On note pa, pb, pr les addresses respectives de a, b et r en mémoire.

/* Copie de a[0..3] dans le registre XMM */movaps xmm0,pa

/* Addition SSE SIMD (packed_add 128 bits) */addps xmm0,pbfor (i=0; i<4; ++i)

r[i] = a[i] + b[i];

addps xmm0,pb

/* Copie du résultat en mémoire r[0..3] */movaps pr,xmm0

85http://www.cs.utk.edu/~vose/Intel/IntelArchitectureOptimization.pdf

La recopie des données de/vers les registres vectorisés XMM prend du temps=> limiter au maximum les transferts entre registres XMM et mémoire RAM

SIMD: implications architecturales(exemple du TMS320C54x et du C55x)

2 bus de lecture : C+D

x y x1 y x2 y

3 bus de lecture : B+C+D

2 RegistresA, B

MAC

1 bus d’écriture : E

MAC1 MAC24 RegistresAC0,…AC3

x y x1 y x2 y

2 bus d’écriture : E+F

C54x C55x

86D’après: http://focus.ti.com/lit/ug/spru307a/spru307a.pdf D’après: http://focus.ti.com/lit/ug/spru393/spru393.pdf

Opération MAC SIMD:MAC *AR2+, *CDP+, AC0

:: MAC *AR3+, *CDP+, AC1

Opération MAC SISD:MAC *AR2+, *AR4+, A

y est partagé par les deux opérations MAC=> Coefficient commun(sinon, 4 bus de lecture auraient été nécessaires)

2 bus d’écriture : E+F

SIMD: granularité du parallélisme(exemple du TigerSHARC)

Le TigerSHARC d ’Analog Devices met en œuvre deux types de SIMD :- SIMD par unités parallèles (exemple TMS320C55x par rapport au C54x)- SIMD par partage de chaque unité de traitement (comme MMX)

MACALU Shift MACALU Shift

Instruction MAC SIMD

Unité decalcul n°1

Unité decalcul n°2

SIMD par unités parallèles 64 bits

- SIMD par partage de chaque unité de traitement (comme MMX)

87

4 multiplications 16 bitsau lieu de

1 multiplication 64 bits

4 multiplications 16 bitsau lieu de

1 multiplication 64 bits

SIMD par partage de

l ’unité de traitement

(split-MAC)

L’approche MIMD… (architecture VLIW)

• Plusieurs unités de calcul en parallèle

– Unités indépendantes (en général distinctes)– Unités indépendantes (en général distinctes)

– Augmentation forte du parallélisme

• VLIW = Very Long Instruction Word

– Notion de super-instruction (bundle)…

– …découpée en sous-instructions destinées à des unités distinctes (slots)distinctes (slots)• 1 Instruction Word = 1 bundle composé de N slots

– Taille du code machine fortement augmentée• Bande passante depuis la mémoire importante

88

Exemple de VLIW RISC(TMS320C62x, Texas Instruments)

• MIMD de type VLIW– 4 unités de calcul en parallèle

par data-path (4 slots)

• Opération MAC décomposée en opérations élémentairespar data-path (4 slots)

– Archi. Load/Store à 16 registres

• Jeu d’instruction RISC– L : Logique et Arithmétique

– S : Décalage (ALU et Shifter)

– M : Multiplication

– D : Données (Mouvement de

élémentaires– Load (Unité D)

– Multiply (Unité M)

– Add (Unité L)

Data Path 1

Register File A– D : Données (Mouvement de données de/vers la mémoire)

• Optimisation figée à la compilation

89RAM

L1

Register File A

S1

A15-A0

++

M1

xD1++

Exemple de VLIW RISC (2)(TMS320C62x, Texas Instruments)

• 2 chemins de données (data-path)– 4 unités de calcul en parallèle par

data-path

C62x/C67x CPU

Instruction Fetch Control Registers

Interru

pt

Control

data-path

• En tout– 8 slots

– Mot instruction de 256 bits = 8*32bit

• Bilan :– Augmentation du parallélisme et des

fréquences d’horloge (car unités RISC plus simples)

Data Path 2Data Path 1

L1

Register File A

M2D2 S2 L2

Instruction Decode

Instruction Dispatch Registers

Interru

pt

ControlEmulation

S1

A15-A0

+ + +x+M1

xD1+

Register File BB15-B0

+plus simples)

– Taille du code beaucoup plus grande

90

++ +

++x+x ++

Dual 32-Bit Load/Store Path(Dual 64-Bit Load Path - C67x only)

Exemple de VLIW CISC(Jazz D4, Improv Systems)

• MIMD à 4 slots VLIW

Registres locaux

Registres locaux

Registres locaux

Registres locaux

• MIMD à 4 slots VLIW– Registres locaux à chaque unité– Unités peuvent être hétérogènes

• Jeu d’instruction CISC/DSP– Présence d’unités MAC

• Design matériel reconfigurable / SoC– Processeur 16 ou 32 bits– 1 à 4 slots VLIW

Bus d’interconnection

Unité2(ALU, MAC,

Shift)

Unité3(ALU, MAC)

Unité4(ALU, MAC)

Unité1(ALU, MAC,

Shift)

Mémoire–– Compression du code machine

91

Jazz D4

http://www.improvsys.com/products/JazzDSP/Jazz_DSP.pdf

Bilan approches SIMD et MIMD

• Augmentation des performances– Par augmentation du parallélisme– Nécessaire pour les applications exigeantes

• Vidéo, TV numérique, multimédia, cartes graphiques• Téléphonie 3G et plus• Imagerie médicale, radar

• Nécessitent une optimisation spécifiqueIl faut que l’algorithme s’y prête– SIMD => Vectorisation des calculs– MIMD => Optimisation de l’utilisation des différentes unités

• Processeurs génériques avec fonctionnalités SIMD DSP• Processeurs génériques avec fonctionnalités SIMD DSP– Certains processeurs peuvent surpasser les DSP en puissance brute

• Filtre RIF: Pentium 1.3GHz plus rapide qu’un C67xx à 225MHz

– Mais moins bons pour :• la consommation électrique, la gestion des entrées-sorties, le prix

92

Puces multi-processeurs…

• Multi-cœurs– Nombre de cœurs x4 => Performances x4 ???– Nombre de cœurs x4 => Performances x4 ???

– Attention à la limitation au niveau des communications• Flux de données avec la mémoire et l’extérieur

• Echanges de données entre les cœurs

• La programmation doit explicitement prendre en compte les multiples cœurs

• Puces hybrides– Processeur générique (Pilotage du système)

+ DSP (Traitement du Signal)• Exemple: téléphone portable

– GPP = gestion du clavier, de l’affichage, du réseau…

– DSP = compression audio, communication numérique

93

Processeurs DSP conventionnels multi-cœurs

• Gravure sur la même puce de deux cœurs puce de deux cœurs DSP indépendants

• Communication entre les deux

– Mémoire partagée

– Interface FIFO– Interface FIFO

94Architecture du C5421

Shared memorytwo-way RAM : permet l'accès simultané à la mémoire par les deux cœurs DSP, par exemple

pour l'exécution parallèle du même programme

DSP System on a Chip (DSP SoC)

• ARM + DSP + modules vidéo– Spécialisé traitement

vidéo/multimédia– Encodage/décodage matériel – Encodage/décodage matériel

temps-réel

• Outils de développement– Linux embarqué– Librairies de codecs multimédia

logiciels adaptés

• Exemples– Texas Instruments: DaVinci

• DM335 : ARM+coprocesseur • DM335 : ARM+coprocesseur MPG4+vidéo

• DM6437: DSP+vidéo• DM644x, DM646x :

ARM+DSP+vidéo

95

Processeur Cell (Sony/Toshiba/IBM)CBEA = Cell Broadband Engine Architecture

• Parallélisme– 8 SPE indépendants en

parallèle– Capacités SIMD du PPE – Capacités SIMD du PPE

et des SPE

• Haut-Débit– Fréquence d’horloge

élevée / architecture simple (3.2GHz)

– Bus d’interconnexion très haut-débit (EIB)

– Usage intensif de transferts DMA asynchrones

• Programmation– Extensions vectorielles

au Langage C– SDK basée sur outils

GNU/Linux

96

1 PPE(Power Processor Element)

64 bits PowerPCContrôleur général

8 SPE(Synergistic Processor Elements)

Calcul vectorisé sur mots de 128 bitsPossèdent une mémoire locale rapide

Image: http://www-128.ibm.com/developerworks/power/library/pa-fpfeib/

Introduction to the Cell multiprocessor: http://www.research.ibm.com/journal/rd/494/kahle.html

Développement pour

la plateforme DSPla plateforme DSP

Texas Instruments

• Outils de développement• Outils de développement

• Organisation de la mémoire

97

Carte de développement (DSK 5416)Mémoireexterne

Plateforme de

Protocole JTAGsur lien USB

(CPLD)ROM

SARAM

DARAM

Mémoireinterne

Plateforme de développement

ProcesseurDSP

98

DARAM

source : "TMS320VC5416 DSK Reference Technical", Spectrum Digital

Carte DSK

Développement pour processeur DSP

• Mise au point de l ’algorithme– Prototypage, simulation haut-niveau

• Matlab• Matlab• Langage C sur PC

• Implémentation DSP– Développement sur carte d'évaluation

• Langage C• Cartes EVM, SDK• Noyau temps-réel (DSP/BIOS)

– Optimisation des parties critiques• Assembleur• Assembleur

– Outils de débogage• Simulateur• Émulateur• Boundary scan JTAG• Communication temps-réel avec un PC hôte

99

Développement pour un DSP

*.cCompilateur

C

Outils deconception

*.asm

Assembleur *.lst*.obj

Linker *.map*.cmd

IDE *.asm

Editeurde Texte

*.out

100

� Simulateur� DSP*.hex

Chargementsur la cible

C vs. assembleur

• Langage C– Langage de plus haut-niveau

• Plus rapide à coder

• Assembleur– Langage bas-niveau

• Fastidieux• Plus rapide à coder• Meilleure portabilité

– Code machine généré moins efficace• Malgré l’optimisation par le

compilateur

– Outils de développement• Noyau temps-réel

(DSP/BIOS)

• Fastidieux• Jeux d’instructions

complexes et irréguliers• Spécifique à chaque

constructeur

– Plus puissant• Accès direct à certains

registres inconnus du C• Instructions spécifiques DSP(DSP/BIOS)

• Configuration de la carte• Librairies de calculs

optimisées (DSPLIB)

•– Utile pour l’optimisation

• ...ponctuellement sur les fonctions identifiées comme critiques

101

Environnement Intégré de Développement (Integrated

Development Environment : IDE)

102

Vue synoptique des modules utiles

DsplibUser ApplicationLogiciel applicatif

CSLDSP/BIOS™Kernel/Scheduler

DsplibImglib

BSL

User Application

Abstraction du matérielet système d’exploitation

Logiciel applicatif

Drivers

103

Carte DSK

USB/JTAG DSP CODEC LED

Boutons

CPU Timer EMIF McBSP

Matériel

Support Libraries (CSL/BSL)

• Abstraction du matériel à travers une API logicielle– Améliore la portabilité

C54x™ DSP Modules

CHIP

• Chip Support Library (CSL)– Bibliothèque facilitant l'utilisation des périphériques

internes du DSP• DMA, BSP, IRQ…

– Méthodes standards d'accès aux périphériques

– Accessible depuis le langage C

• Board Support Library (BSL)

CHIP

DAA

DAT

DMA

EBUS

GPIO

HPI

IRQ

MCBSP• Board Support Library (BSL)– Bibliothèque facilitant l’utilisation des périphériques sur

la carte DSK• Switches, LEDS…

104

MCBSP

PLL

PWR

UART

WDTIM

Système temps-réel DSP/BIOS

• Noyau temps-réel– Ordonnanceur temps-réel

– Gestion multi-threads préemptive– Gestion multi-threads préemptive

• Outils d'analyse temps-réel– Débogage sans interruption de l'exécution

– Profiling, vision des threads

• Intégration avec– Real-time data exchange (RTDX)– Real-time data exchange (RTDX)

• Communication hôte↔DSP pendant l'exécution

– Chip Support Library (CSL)

105

Stratification des traitements sous DSP/BIOS

Interruptions matérielles

Hard Real-time

1st-TIER� Traitement par échantillon� Réaction à la microseconde

Interruptions logicielles

Multi-tâche

2nd-TIER� Traitement par blocs� Réaction à la milliseconde

� Réaction à la microseconde

� Traitements ordonnancés� Exécution concurrente

106

Multi-tâche

Tâche de fond (idle)

Soft Real-time

� Exécution concurrente

� S'il reste du temps

Propriétés des systèmes temps-réel

• Piloté par évènements– Synchrones (chronomètre)– Asynchrones (interruptions des E/S)– Asynchrones (interruptions des E/S)

• Contraint dans le temps– Contraintes dures (deadlines critiques)– Contraintes souples (deadlines non critiques)

• Concurrence de l'exécution– Plusieurs traitements en parallèle– Nécessite un ordonnancement

• multi-tâches (plusieurs traitements à la fois)• multi-tâches (plusieurs traitements à la fois)• préemptif (toute tâche peut être interrompue par une tâche plus

prioritaire)

• Déterministe et fiable– Comportement du système prédictible

107

Librairies spécialisées (DSPLIB, IMGLIB)

• Librairie déjà optimisée– Traitement du signal ou des images

– Déjà programmées– Déjà programmées

– Optimisées

– Utilisables depuis le langage C

• Fonctionnalités de base– FFT

– Filtrage– Filtrage

– Mathématiques et trigonométrie

– Calcul matriciel

108

Outils de débogage

• Type d’outils– Emulateur

• Communique avec le DSP à grande vitesse

Emulateurou

Contrôleur JTAG

IDEDSP

vitesse• Capable de simuler/enregistrer en

temps-réel l’état interne exact du DSP

– Boundary-scan (JTAG)• Protocole intégré au sein du

processeur• Interrompt le DSP pour accéder à

l’information

• Opérations– Interruption et relance de l’exécution

• Chargement du code

Récupération des donnéesdepuis la mémoire du DSP

Définition de breakpointset modification des variables

• Chargement du code• Breakpoints

– Accès en lecture/écriture• Visualisation et modification du

contenu mémoire• Registres internes

109

Boundary Scan (JTAG) vs In-Circuit Emulator (ICE)

Emulateur ICEGestion avancée temps-réel

Emulateur JTAG Externe(GAO XDS510PP JTAG Scan Path)

www.gaotek.com

110http://www.embedded-computing.com/products/product_guide/emulators/index.shtml

Gestion avancée temps-réel(trace, détection d’évènements complexes,

statistiques…) (Lauterbach TRACE32-ICE)

Contrôleur JTAG intégré à la carte(DSK C5416)

Image: http://www.logic-instrument.com/gamme-33.html

Affichage du code désassemblé

#define N 256

short inputData[N];short outputData[N];

void toto()void toto()

{

int i;

for (i=0; i<N; i++)

{

outputData[i] = inputData[i];

}}

111

Compilation et édition des lienspuis affichage du code désassemblé« Mixed Source/ASM »

Organisation mémoire

112

Structuration hiérarchique de la mémoire

• Carte mémoire– Carte mémoire physique

• Associe à chaque adresse une connexion vers une mémoire physique• Configuration matérielle statique spécifique à chaque processeur• Configuration matérielle statique spécifique à chaque processeur• Configurable dans une certaine mesure (MP/MC, DROM, OVLY)

– Carte mémoire logique• Blocs d’adresses logiques nommés• Position et taille définies statiquement• Doit être compatible avec la carte physique

– Sur architecture Harvard, attention à bien différencier les espaces d’adresses données et programme

• Section relogeable– A l’intérieur d’un bloc logique– A l’intérieur d’un bloc logique– Taille décidée lors de l’édition des liens, en fonction de son contenu

• Variable / Portion de code– A l’intérieur d’une section– Position dans la section décidée lors de l’édition des liens

113

Architecture mémoire logique et physique

DSP

Espace

Vue logique simplifiéede l’architecture Harvard

Vue physique

ROM

SARAM

DARAM

Mémoireinterne

CPU

SRAM Mémoireexterne

Bus Bus

Mémoire Programme

CPU

Espace d’adresses programme

Espace d’adresses données

Mémoire Données

114

Bus programme

Busdonnées

Chaque mémoire est physiquement câblée pour ne répondre qu’à certaines adresses logiques dans chaque espace d’adresses.La carte mémoire permet de déterminer le lien entre adresses logiques et mémoires physiques.

Carte mémoire Prog et Data (C5416)

PROG

Registres MMR(Accès accumulateurs et registres de configuration)

DATA

Reserved

DARAM03

registres de configuration)

Utilisé par le DSP/BIOS

DARAM03

Overlay :DARAM03 est

accessible par les deux espaces

Deux espaces mémoires distincts :0x8000 pointe sur deux cases

External

ROM

115

Routines d'interruption(géré par le DSP/BIOS)

DARAM47 accessible uniquement par adresses données

DARAM47

deux cases physiques distinctes

Carte mémoire obtenue d’après la documentation du DSK5416 lorsqueMP/MC=0, OVLY=1, DROM=0. D’autres valeurs conduiraient à des cartes différentessource : "TMS320VC5416 DSK Reference Technical", Spectrum Digital

Notion de mémoire étendue (Prog)

Mémoire accessible avec adresses 16 bits(0x0000 à 0xFFFF)

Mémoire étendue,accessible grâce à la pagination par le registre XPC

DARAM03

DARAM03 DARAM03 DARAM03 DARAM03

DARAM47 SARAM03 SARAM47

Reserved

116source : "TMS320VC5416 DSK Reference Technical", Spectrum Digital

Le registre XPC permet d’exécuter des fonctions dont le code est stocké en mémoire étendue, à l’adresse :

XPC × 0x10000 + PC

Le compilateur C gère automatiquement le XPC lorsque l’option far-calls est cochée.

Le fichier de commande

File_name1.obj

File_name2.obj

-o Name.out

Name.cmd� Noms des fichiers objet constituant l’exécutable final

� Noms des fichiers de sortie -m Name.map

MEMORY

{

PAGE 0 :

IPROG : origin = 0x7080, length = 0x0F00

VECT : origin = 0xFF80, length = 0x0080

SARAM03 : origin = 0x28000, length = 0x8000

PAGE 1 :

IDATA : origin = 0x0080, length = 0x7000

DARAM47: origin = 0x8000, length = 0x8000

� Carte mémoire :Définition des blocs mémoire statiques

� Noms des fichiers de sortie (exécutable et carte mémoire)

117

}

SECTIONS

{

.text : load = SARAM03 page0

.data : load = IDATA page1

.bss : load = IDATA page1

.coef : load = IPROG page0

}

� Positionnement des sections dans les blocs mémoire

Sections relogeables

Sections initialiséesSections initialisées Sections non initialisées pour les

donnéesCode VariablesCode ou constantes

Sections nommées (par l'utilisateur)

.sect .usect

118

Sections par défaut

.text .data .bss

Phase d'édition de liens

Positionnementdes sections en mémoire (*.cmd)

SARAM03

IDATA

mémoire (*.cmd)

119source : "TMS320C54x Assembly Language Tools User's Guide",ref. SPRU102F, Texas Instruments

Utilisation explicite des sectionsen assembleur

SECTIONS{

Déclaration des sections dans le fichier *.cmd :

{init: > IPROG page0vars: > IDATA page1 results: > IDATA page1 .text: > IPROG2 page0

}

.sect "init"

Déclaration des variables dans le fichier assembleur :

init: Section initialisée qui commence

120

.sect "init"tbl .int 1,2,3

x .usect "vars",3y .usect "result",1

.text…

init: Section initialisée qui commence à l’addresse tblvars: Section non initialisée de taille 3 qui commence à l’addresse xresult: Section non initialisée de taille 1 qui commence à l’addresse y.text: Section de code

Utilisation explicite des sectionsen Langage C

Pour placer un tableau ou une variable :

SECTIONS#pragma DATA_SECTION (tbl, "init")

Pour placer une fonction (c’est-à-dire le code machine correspondant):

Code C Fichier *.cmd

SECTIONS{init: > IPROG page1vars: > IDATA page1results: > IDATA page1

}

#pragma DATA_SECTION (tbl, "init")Int16 tbl[3]={1,2,3};#pragma DATA_SECTION (x, "vars")Int16 x[3];#pragma DATA_SECTION (y, "results")Int16 y;

121

Pour placer une fonction (c’est-à-dire le code machine correspondant):

SECTIONS{psec: > IPROG page0

}

#pragma CODE_SECTION (increment, "psec")Int16 increment(Int16 a) {return a+1;

}

Code C Fichier *.cmd

Représentation numériqueReprésentation numérique

du signal

• Echantillonnage / Quantification• Echantillonnage / Quantification

• Virgule fixe, format Qk

• Virgule flottante

122

Chaîne de Traitement Numériqueau sein d’une chaîne analogique

Signald’entrée

Signal Traité

Filtreanti-repliement

CAN CNAFiltre delissage

DSP

G

Echantillonage/Quantification Reconstruction

123

Signal analogique Signal analogiqueSignal numérique

Du signal analogique...

Signal AnalogiqueSignal Analogique

VoltsVolts • Valeurs continues de tension en fonction du temps

•Discrétisation en temps par

TempsTemps

•Discrétisation en temps par échantilloneur-bloqueur à fréquence

Signal Discrétisé en tempsSignal Discrétisé en temps

ffss = 1 / T= 1 / Tss

124

TempsTemps

TTSS

Discrétisation en temps

… vers le signal numérique

• Restriction des instants considérés

Signal EchantillonnéSignal Echantillonné

Valeurs continues

Signal NumériséSignal Numérisé

q

• Restriction des valeurs de magnitude possible

Valeurs continues

Valeurs discrètes

125

Discrétisationen amplitude

Valeurs discrètes

L’échantillonnage

126

Caractéristiques du signal échantillonné

Spectre de Fréquence du Signal AnalogiqueSpectre de Fréquence du Signal Analogique| X(f) |

fc

fs 2fs 3fs0

Spectre de Fréquence du Signal d’EchantillonageSpectre de Fréquence du Signal d’Echantillonage

127

fc fs 2fs 3fs0

Spectre de Fréquence du Signal EchantillonéSpectre de Fréquence du Signal Echantilloné| Xe(f) |

Théorème de Shannon

Fs > 2FcFs > 2Fc| Xe(f) |

fc fs 2fs 3fs0 4fs

fc fs 2fs 3fs0 4fs 5fs

Fs = 2FcFs = 2Fc| Xe(f) |

128

fc fs 2fs 3fs0 4fs 5fs 6fs 7fs

Fs < 2FcFs < 2Fc

Repliement de spectre

| Xe(f) |

Effets du repliement de spectre

AmplitudeAmplitudeSignal échantilloné à Signal échantilloné à

fs > 2fcfs > 2fc

TempsTemps

129TempsTemps

SignalSignal échantillonééchantilloné à à

fsfs < 2fc< 2fc

La quantification

• Uniforme

130

• Logarithmique

Quantification Uniforme

Pour un pas de quantification q :

=q

xX round Entier X associé au réel x

xxe −= ˆL’erreur de quantification est (écart entre la valeur réelle et la valeur quantifiée)

qXx =ˆ

=q

X round

Valeur approchée du réel x après quantification

q e

131

Erreur de granulationErreur de granulationErreur de granulationErreur de granulation Erreur de saturationErreur de saturationErreur de saturationErreur de saturationLiée à la précision q Liée à la dynamique [xmin, xmax]

0 1 2 3 4 5 6 7 8Temps

09

q

00 11 22 33 44 55 66 77 88Temps

xmax

99

ee

RSB de la quantification uniformeN bits signés

=−=

e

xdB

e

dB

xdBP

PPPRSB log10

Rapport signal sur bruit relatif à la quantification

q≤

)(log2077.402.6 max10 xPNRSB dBxdB −++≈

Le RSB de la quantification uniformede la quantification uniformede la quantification uniformede la quantification uniforme est donc, en l’absence de saturation :

2

qe ≤

12

2qPe =On peut alors montrer que la puissance de l’erreur est

Si arrondi au plus proche voisin

Pour un codage N bits signé , on a q=(2xmax)2-N

132

max10xdB

En introduisant le facteur de chargefacteur de chargefacteur de chargefacteur de charge Γ ,qui indique quelle est la dynamique utilisable par rapport à la puissance du signal x

x

σmax=Γ

( )Γ−+≈ 10log2077.402.6 NRSBdB

Seuil d’apparition de la saturation

La saturation se produit lorsque l’amplitude du signal à convertir dépasse xmax ou xmin

Le RSB se dégrade très rapidement dès qu’il y a saturation

Soit a l’amplitude du signal il y a saturation pour a>xmax

Pour un signal carré: Px=a2 saturation à 0 dB

Pour un signal sinusoïdal: Px=a2/2 saturation à -3.01 dB

Pour un signal uniforme sur [-a, a] : Px=a2/3 saturation à -4.77 dB

Pour un signal gaussien à moyenne nulle :

133

Dynamiques typiques :X sur N bits non signés => xmin=0 et xmax=q(2N-1)

X sur N bits signés en C2 => xmin=-q2N-1 et xmax=q(2N-1-1)

a ≈ 3σx (règle des 3 sigmas) d’où Px ≈ a2/9 saturation à -9.54 dB

Quantification uniforme et RSB

120Quantification uniforme 16 bits sur [-1,1]

bruit blanc gaussien

bruit blanc uniforme

saturation

dBxPx =Γ−⇒= )(log201 10maxQuantification uniforme 16 bits signés sur [-1,1]

40

60

80

100

RSB (dB)

bruit blanc uniforme

signal sinusoidal

signal carré

dBxdB PNRSB ++≈ 77.402.6

Seuil d’apparition de la saturationCarré: 0 dB

Sinus: -3.01 dB

RSB en l’absence de saturation:

134

-60 -50 -40 -30 -20 -10 0 100

20

puissance du signal (dB)

erreur de granulation

Sinus: -3.01 dB

Uniforme : -4.77 dBGaussien : -9.54 dB

Quantification Logarithmique

• Très utilisée pour la transmission de signaux audio– Permet d’obtenir un RSB à peu près constant, quelle que soit la puissance du

signalsignal

• Deux lois logarithmiques sont actuellement utilisées– la loi A est utilisée en Europe

– la loi µ aux Etas Unis et au Japon

• Peut être exprimée à l’aide d’une quantification uniforme après compression d’amplitude

y yCompression Quantification Expansion )(ˆ xQx =

135

y

)ˆ(ˆ 1 yCx −=

xCompression d’Amplitude

Quantification Uniforme

Expansion d’Amplitude

)(xCy = )(ˆ yQy u=

)(ˆ log xQx =

( )( ))()( 1log xCQCxQ u

−=

Quantification uniforme vs logarithmique

0.5

1Signal original x

x1

x2

0.5

1Signal original x

0.5

1Signal compressé y=C(x)

0 0.5 1-1

-0.5

0

0.5

1

Signal quantifié xq=Q(x)

x2

x3

0 0.5 1-1

-0.5

0

0 0.5 1-1

-0.5

0

0.5

1

Signal quantifié yq=Q(y)

0.5

1

Signal quantifié xq=C-1(y

q)

136

0 0.5 1-1

-0.5

0

0.5

quantif. uniformedomaine linéaire

quantif. logarithmiquedomaine linéaire

quantif. uniformedomaine compressé

0 0.5 1-1

-0.5

0

0.5

0 0.5 1-1

-0.5

0

0.5

Loi A

0.8

0.9

1loi de compression A

Pente élevée → bonne précision

Pente faible → augmente la dynamique

0.2

0.25

0.3

0.35

0.4

0.1

0.2

0.3

0.4

0.5

0.6

0.7

C(x)

Compression logarithmique

( ) ( )( ) ( ) 1

1;

ln1

/ln1

max

maxmax ≤≤

++

=x

x

Apourxsign

A

xxAxxC

A=87.56

Pente élevée → bonne précision

C(x)

137

0 0.01 0.02 0.030

0.05

0.1

0.15

0.2

Compression linéaire

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

x

( ) ( ) ( )Ax

xpourxsign

A

xAxC

10;

ln1 max≤≤

+=

x

Pour les signaux de très faible amplitude,équivalent à une quantification uniforme de pas ulog

ln1q

A

Aq

+=

Quantification Uniforme 8 bitsvs. Logarithmique 8 bits

• Loi A• La compression limite les effets

de la granulation50Quantif ication 16 bits sur [-1,1]

Loi A sur 8 bits Uniforme sur 8 bits

RSB pour une sinusoïde

de la granulation• RSB à peu près constant sur

une plage de 30 dB

• Quantification uniforme• Meilleur que loi A seulement 10

15

20

25

30

35

40

45

RSB (dB)

Loi AUniforme

( )ANRSBdB ln1log2077.402.6 10 +−+≈

• Meilleur que loi A seulement pour premiers 10dB

• L’effet de granulation est linéaire par rapport à la puissance du signal

138

-60 -50 -40 -30 -20 -10 0 100

5

10

puissance du signal (dB)

x1x2x3

Quantification uniformemeilleur RSB

Quantification logarithmiquemeilleur RSB

( )Γ−+≈ 10log2077.402.6 NRSBdB

Quantification Uniforme 12 bitsvs. Logarithmique 8 bits

60

70 • Pour les calculs, on reviendra toujours en quantification uniforme

RSB pour un bruit gaussien centré

-60 -50 -40 -30 -20 -10 0 100

10

20

30

40

50

puissance du signal (dB)

RSB (dB)

uniforme

– Pour éviter une augmentation du RSB,

le nombre de bits supplémentaires dépend de A uniquement

Loi A sur 8 bits

A1

logudBdB RSBRSB ≥

139

( )Γ−+≈ 10log2077.402.6 NRSBudB

( )Γ−

+++≈ 1010

log log20ln1

log2077.402.6A

ANRSBdB

++≥

A

ANNu

ln1log20

02.6

110log

bits 4log += NNu

Lorsque A=87.56 :

Le codage des entiers

140

Représentation d’entiers non signés

• Représentation binaire non-signée sur bits ∑

−

=1

2N

i

ibX bi = 0 ou 1• Représentation binaire non-signée sur N bits ∑

=

=0

2i

ibX bi = 0 ou 1

dynamique de X : 0..(2N-1)

141

• Exemple: entier en décimal, binaire et hexadécimal

010123401

16210

16101612021202121106102

1A1101026

×+×=×+×+×+×+×=×+×

==

Entiers signés : binaire décalé

Binaire DécaléBinaire DécaléBinaire DécaléBinaire DécaléEntier x codé par

Le décalage d est généralement égal àd = -2N-1

Entier x codé parla représentation binaire pure de l’entier positif

y=x+d

110011

00-210-1010111012113

Nombre Codage

234567

y

12 1 −−N

Dynamique

142

001

00-410-300-2

012

N=3

12 −− N

Entiers signés : signe et valeur absolue

Format signe et valeur absolue Format signe et valeur absolue Format signe et valeur absolue Format signe et valeur absolue Le bit de poids fort représente le signeLes autre bits, la valeur absolue de l’entierLe bit de poids fort représente le signeLes autre bits, la valeur absolue de l’entier

0011

000101002103

Nombre Codage

12 1 −−N

Deux codes

143

11000

11-301-211-101-0000

Signe

)12( 1 −− −N

Deux codes pour le zéro

Entiers signés : format complément à 1

Format complément à 1Format complément à 1Format complément à 1Format complément à 1Le bit de poids fort représente le signeNombre positif : codé comme un non-signé

ATTENTION : ne pas confondre

Format C1 et C1 d’un entier

Nombre positif : codé comme un non-signéNombre négatif : codé comme le C1 de son opposé

12 1 −−N

Deux codes

C1(x) = (2N-1) – x

avec0011

000101002103

Signé C1 Codage

Complément à 1 de x:

0

1

2

3

Non signéassocié

144Signe

Deux codes pour le zéro

Implantation efficace :Implantation efficace :Implantation efficace :Implantation efficace :inversion des bitsinversion des bitsinversion des bitsinversion des bits

avec

N fois 1

2N-1 = 111…1112

)12( 1 −− −N00110

01-311-201-111-0000

4

5

6

7

0

Entiers signés : format complément à 2

Format complément à 2Format complément à 2Format complément à 2Format complément à 2Le bit de poids fort représente le signeNombre positif : codé comme un non-signé

ATTENTION : ne pas confondre

Format C2 et C2 d’un entier

Format le plus utiliséNombre positif : codé comme un non-signéNombre négatif : codé comme le C2 de son opposé

12 1 −−N

C2(x) = 2N – x

Implantation efficace de l’opposéInversion des bits puis ajout de 1

Format le plus utiliséen arithmétique binaire

Complément à 2 de x :

Dynamique

0011

000101002103

Signé C2 Codage

0

1

2

3

Non signéassocié

145Signe

Inversion des bits puis ajout de 1

12 −− N

C2(x) = C1(x) + 1

Dynamique

00110

01----444411-301-211-1000

4

5

6

7

0

Lien entre non-signé et signé C2

• Pour une même représentation binaire

],,,,[ 0121 bbbb NN L−−

0 12-2

-10

• X entier signé C2

• Y entier non-signé

∑−

=

−− +−=

2

0

11 22

N

i

ii

NN bbX

],,,,[ 0121 bbbb NN L−− 2

3

4

5

67-7

-6

-5

-4

-3

-2 0 123

4

56

78910

11

12

131415

pour N=4 bits

• Y entier non-signé

146

∑−

=

=1

0

2

N

i

iibY

NYX 2−=

7-8-7

0≥X

12 −< NY12 −≥ NY

0<X

YX =

Propriétés de la saturation

• Modes de saturation

• Exercice:

– Montrer qu’en mode C2 pur sur 8 bits signés le calcul

C2 pur C2 avec saturation

– Montrer qu’en mode C2 pur sur 8 bits signés le calcul suivant conduit à un résultat correct, mais pas en mode de saturation• A=((100+70)+30)-150

147

Le codage des réels en virgule fixe

148

Représentation de nombres réels

• Deux exigences contradictoires:

– Précision: intervalle entre deux valeurs codées– Précision: intervalle entre deux valeurs codées• doit être le plus petit possible

– Dynamique: intervalle entre les valeurs min et max• doit être le plus étendu possible

• Les unités de calcul des DSP travaillent• Les unités de calcul des DSP travaillent– soit en format fixe (notation décimale)

– soit en format flottant (notation scientifique)

149

Format à virgule fixe : le format Qk

Définition :Définition :Définition :Définition :La représentation Qk du réel x est l'entier X défini parLa représentation Qk du réel x est l'entier X défini par

)2round( xX k=

Q0 désigne le cas du codage à l’entier le plus proche (X=round(x))

Cela correspond à une quantification uniforme de pas q=2-k

150

On peut utiliser le format Qk en signé et non-signé

Le format Qk peut également être noté Q.k

Dynamique et précision du format Qk

Précision: quantification uniforme de pas qkq −= 2

En pratique, on peut approximer les dynamiques par des intervalles

Dynamique:non-signé:

signé C2: [ ]kkNkN −−−−− −− 22 ,2 11

[ ]kkN −− − 22 ,0

q = 2

151

En pratique, on peut approximer les dynamiques par des intervalles semi-ouverts: et

D’où les formats classiques:• Dynamique sur [-1, 1[ format QN-1 sur sur sur sur N bits signésbits signésbits signésbits signés• Dynamique sur [0, 1[ format QN sur sur sur sur N bits nonbits nonbits nonbits non----signéssignéssignéssignés

[ [kN−2 ,0 [ [11 2 ,2 −−−−− kNkN

Représentation Qk sur 16 bits

kPrécision

q

Dynamique pour

16 bits signés

Dynamique pour

16 bits non signés

-1 2 [-65536, 65535] [0, 216-1]-1 2 [-65536, 65535] [0, 216-1]

0 1 [-32768, 32767] [0, 65535]

1 1/2 [-16384, 16383] [0, 32767]

14 2-14 [-2, 2[ [0, 4[

Entiers Q0

[-1 1[ Q15 sur 16 bits signés15 2-15 [-1, 1[ [0, 2[

16 2-16 [-0.5, 0.5[ [0, 1[

17 2-17 [-0.25, 0.25[ [0, 0.5[

152

[-1 1[ Q15 sur 16 bits signés

[0 1[ Q16 sur 16 bits non-signés

Quantification uniforme

Attention à l’ambigüité entre et x X

x

= x

X round

xValeur réelle exacte

exact

quantifié

qx /

Valeur réelle exacte normalisée

qXx =ˆ

Quantificationde pas q

Arrondi entier

153

x

=q

X round

Valeur réelle quantifiée Représentation entière

qXx =ˆ

Dynamique sur [qXmin, qXmax] Dynamique sur [Xmin, Xmax]

Inteprétation binaire

• Exemple : Représentation Qk non signée de x=0.1

…12 1/2 1/4 1/8 1/16 1/32 1/64 2-112-102-92-82-7 2-12

En pratique, utiliser plutôt la définition X=round(x/q)

0 0 0 0 0 1 1 0 0 1 1, 0 0 1…12 1/2 1/4 1/8 1/16 1/32 1/64 222 2

Format Q0 sur 8 bits non signés

0 00 0 0 0 0 0 ,1

0ˆ

0

=

=

x

X

Format Q sur 8 bits non signés13=X

…

Format Q12 sur 8 bit� Saturation

154

Format Q10 sur 8 bits non signés

0 1 1 0 0 1 1 02-10

…50.09960937ˆ

102

=

=

x

X

0 0 0 0 1 1 0

,

02-7Format Q7 sur 8 bits non signés

1015625.0ˆ

13

=

=

x

X

Choix du format Qk

• Pour le codage d'un ensemble de valeurs x en virgule fixe sur N bits signés, la méthode est la suivante:

1) Expliciter la dynamique prévue pour les valeurs de x

2) Estimer kmax, le k maximum permettant d'éviter la saturationéviter la saturationéviter la saturationéviter la saturation, c'est à dire vérifiant:

3) Toutes les valeurs k inférieures à k permettent d'éviter la saturation. On

maxxx ≤

1

maxmax2 −−≤ kN

x

1)(log max2max −+−= Nxk

155

3) Toutes les valeurs k inférieures à kmax permettent d'éviter la saturation. On choisit la valeur permettant la plus grande précision, c'est à dire kmax.

4) Le pas de quantification est alors:

Dans le cas non signé, on a:

max2 kq

−=

max2max

kNx

−≤ Nxk +−= )(log max2max

Quantification et précision décimale

A titre purement indicatifA titre purement indicatifA titre purement indicatifA titre purement indicatif, il est possible de déterminer le nombre de chiffres décimaux significatifs associé à un pas de quantification.

Dkq −− ≈= 102( )

Dk

Dk

3.3

10log2

≈

≈

Notons- k le nombre de bits après la virgule (format Qk),- D le nombre de chiffres décimaux significatifs après la virgule,- q le pas de quantification

-On a l'équivalence suivante:

156

En particulier, le format Q15 a une précision approximative de 4 chiffres décimaux après la virgule

Ceci est un calcul approximatif,ne pas utiliser pour justifier le choix d’un format Qk

Opérations arithmétiques virgule fixe

157

Influence des opérations sur le format Qk

• Addition:Si A, B représentations Qk de a et b,alors A+B est la représentation Qk de a+b.

A + BQk Qk

Qk

A + BQk Ql

k≠lA+B Qk a+b.

• MultiplicationSi A représentations Qk de aet B représentations Ql de b,alors A*B est la représentation Qk+l de a×b.

• DécalageSi A représentations Qk de aalors A<<2=2n A est la représentation Qk+n de a.

Qk

A * BQk Ql

Qk+l

A >> n

Qk

A << n

Qk

k≠l

alors A<<2=2n A est la représentation Qk+n de a.et A>>2=2-n A est la représentation Qk-n de a.

• TranstypageChanger le nombre de bits sur lequel est codé un nombre ne change pas le format Qk.

158

Qk-n Qk+n

(int)L

Qk

Qk

(long)I

Qk

Qk

Multiplication entière sur le C54x

Multiplication entiers 16 bits

; AR2 = @X

; AR3 = @Y

Int16 X,Y,R;

Int32 A;; AR3 = @Y

; AR4 = @R

MPY *AR2,*AR3,A

STL A,*AR4

Int32 A;

A = (Int32)X * Y;

R = (Int16)A;

s s015162931 30

X*Y sur 32 bits

159

s s

s

Réduction à 16 bitsPartie basse de l’accumulateur :STL = Store Low

R: Résultat sur 16 bits

X*Y

Multiplication virgule fixe Q15

RSBX FRCT ; FRCT←0

MPY *AR2,*AR3,A

Multiplication format Q15 sur 16 bits

A = (Int32)X * Y;

Sans

FRCT

SSBX FRCT ; FRCT←1

MPY *AR2,*AR3,A

STH A,*AR4

MPY *AR2,*AR3,A

STH A,-1,*AR4

A = (Int32)X * Y;

R = (Int16)(A>>(16-1));

015 142931 30

A = ((Int32)X * Y)<<1;

R = (Int16)(A>>16);

Avec

FRCT

Sans

FRCT

160

s s015 14

Partie haute de l’acc.(STH=Store High)Réduction à 16 bits

sDécalage à gaucheautomatique si FRCT=10

s

X*Y sur 32 bitsQ30

Q31

Q15

>>16 (STH)

<<1

R: Résultat sur 16 bits

Accumulateurs sur le C54x

15-0

ALAHAGAccumulateur A

31-16

Bits de Garde

39-32

Bits de poids fort

Bits de poids faibleGarde poids fort faible

� Sur le C54X, deux accumulateurs 40 bits : A et B� Peuvent servir de source et de destination pour l’ALU et pour le MAC� Sont mappés en mémoire (MMR)

; A accumulateur 40 bits

; AR2=@X[0], AR3=@Y[0]

; AR4=@R

; 55 répétitions

Int32 A;

Int16 X[],Y[];

Int16 R;

A=0;

161

RPTZ A, #54

MAC *AR2+, *AR3+, A

STH A,-1,*AR4

A=0;

for (i=0; i<=54; ++i)

A = A + (Int32)X[i]*Y[i];

R = (Int16)(A >> 15);

Accumulateur de 40 bitsnon accessible depuis le langage C:Dégradation dès qu’un résultatintermédiaire dépasse 32 bits.

Si le résultat final R tient sur 16 bits, possibilité de résultats intermédiaires jusqu’à 40 bits sans saturation.

Arithmétique et précision

• Divisions et décalages entraînent une erreur liée à la perte de précision

Int16 X[4]={15, 23, 7, 2};x(0)=15 x(1)=23 x(2)=7 x(3)=2

a = (x(0) + x(1) + x(2) + x(3))/4 A = ((Int32)X[0]+X[1]+X[2]+X[3])>>2;

Equivalence sur les réels

Pas d’équivalence en virgule fixe

A = floor(47/4) = 11 erreur 0≤e<1

Int16 X[4]={15, 23, 7, 2};Int16 A;

e

e e

x(0)=15 x(1)=23 x(2)=7 x(3)=2

a = 47/4 = 11.75

162

A = (X[0]>>2) + (X[1]>>2)+ (X[2]>>2) + (X[3]>>2);

a = x(0)/4 + x(1)/4 + x(2)/4 + x(3)/4

sur les réels

A = 3 + 5 + 1 + 0 = 9 erreur 0≤e<4a = 15/4 + 23/4 + 7/4 + 2/4 = 11.75

e0 e1e2 e3

Accumulation et saturation

• Exercice:1) Quelle est la dynamique de l’addition de M entiers non-signés n bits ?

2) En déduire le nombre de bits minimum N de l’accumulateur pour éviter la saturation.

1’ et 2’) Même questions en signé.

• Problème:On désire calculer le produit scalaire aM entre deux vecteurs x et h de taille m, dont toutes les valeurs sont l’intervalle ]-1, 1[. Les valeurs sont codées au format Q15 sur 16 bits signés (Int16). On note am les accumulations intermédiaires :

1) Quelle est la dynamique des résultats intermédiaires am ?

∑−

=

=1

0

)()(

m

i

m ihixa

1) Quelle est la dynamique des résultats intermédiaires am ?

2) En déduire le nombre de bits nécessaires pour pouvoir calculer aM exactement.

3) Supposons que l’on soit contraint d’utiliser uniquement les types Int16 et Int32. A quel format Qk faut-il stocker les résultats intermédiaires pour éviter la saturation ?

4) On suppose de plus que aM∈]-1, 1[, mais sans aucune garantie sur les am intermédiaires.Ecrire le code C permettant de calculer aM en Q15 sur 16 bits signés avec la meilleure précision possible sans saturation. (opérations: +, *, >>, (Int16), (Int32))

163

Le codage des réels en virgule flottante

164

Représentation en virgule flottante

ES Mx 2)1( ××−=

• Le signesignesignesigne S : 1 bit (0 ou 1)

• La mantissemantissemantissemantisse M : réel positif codé sur m bits

• L’exposantexposantexposantexposant E : entier signé sur e bits

Nem =++1

•Opération de normalisationnormalisationnormalisationnormalisation:

nombre de chiffres significatifsdynamique

165

•Opération de normalisationnormalisationnormalisationnormalisation:Pour rendre la représentation unique,M doit satisfaire en outre:

et peut donc être codé uniquement par sa partie fractionnaire F, son bit de poids fort étant implicitement à 1:

21 <≤ M

44 344 21K

F

mm bbbbM 0121,1 −−=

Format virgule flottante IEEE 754

Simple précision (N=32 bits) : float

Double précision (N=64 bits) : double

ES Mx 2)1( ××−=

Signe S (1 bit)

Exposant E (8 bits)en binaire décalé (codé par le non-signé E+127)

Fraction F (23 bits), partie fractionnaire de la mantisse�Mantisse M sur 24 bits non-signés

Double précision (N=64 bits) : double

float double

Signe S (1 bit)

Exposant E (11 bits)codé par E+1023

Fraction F (52 bits)� M sur 53 bits

166

�Mantisse M sur 24 bits non-signés

•Cas spéciauxZéro: tous les bits à 0Underflow: exposant = 0000…2

Overflow: exposant = 1111…2

� M sur 53 bits

Dynamique en format flottant

• Pour le codage en virgule flottantela dynamique est conditionnée par le nombre de bits de l’exposant:

( ) ( ){ }11loglog11log2 max22max2 ++≥⇒++≥ xexe

12 )12(max −= −ex

D’où la condition :

( ) ( ){ }11loglog11log2 max22max2 ++≥⇒++≥ xex

167

En pratique, la dynamique est beaucoup moins contraignante en virgule flottante qu’en virgule fixe, et requiert donc moins d’attention.

Virgule flottante par bloc

• Simulation de la représentation virgule flottante avec un DSP à virgule fixe

; L’accumulateur A contient

; une valeur sur 40 bits

EMx 2×=

virgule fixe– La mantisse M est un réel signé

de [-1, 1]codé au format Qm-1 sur m bits

– Un autre contient l’exposant E

• L’exposant est constant pour un bloc de données

• Les calculs se font sur les mantisses, puis les résultats sont

; Calcule l’exposant de A

; et le stocke dans T

EXP A

; Normalise A

; en fonction de T

NORM A

; Stocke:mantisses, puis les résultats sont mis à l’échelle en fonction de l ’exposant– Dans ce cas, la normalisation est

plutôt

168

; - la mantisse dans *AR3

STL A,*AR3; - l’exposant dans *AR4

ST T,*AR4

Passage de la virgule fixe à la virgule flottante simulée sur deux entiers

(ASM C54x)

15.0 <≤ M

Mise en œuvreMise en œuvre

de filtres numériques

•Méthodologie d’implémentation•Méthodologie d’implémentation

• Lookup table (LUT)

• Structures de filtres RIF et RII

• Problèmes liés à la quantification et à la saturation

169

Méthodologie d'implantation d'un filtre

numérique

170

Méthodologie d'implantation d'un filtre

• Étape 0 : Conception du filtre– Choix du filtre et calcul des coefficients

• Étape 1 : Choix de structure– Choix d'un schéma d'implantation– Écriture des équations correspondantes

• Étape 2 : Choix algorithmiques– Choix de l'implantation mémoire et des variables– Écriture de l'algorithme en virgule flottante

• Étape 3 : Choix numériques– Choix du format Qkk

– Écriture du programme en virgule fixe

• Étape 4 : Validation– Définir un protocole de test et l'appliquer

• Etape 5 : Optimisation

171

Etape 0 : Conception du filtre

Outils de conception de filtres numériquesPar exemple, sous Matlab: Signal Processing Toolbox, outil fdatool

172

Etape 0 : Conception du filtre (2)

• Conception de filtres RIF

cfirpm Complex and nonlinear-phase equiripple FIR filter designfir1 Window-based finite impulse response filter designfir2 Frequency sampling-based finite impulse response filter designfircls Constrained least square FIR multiband filter designfircls Constrained least square FIR multiband filter designfircls1 Constrained least square, lowpass and highpass, linear phase, FIR filter desigfirls Least square linear-phase FIR filter designfirpm Parks-McClellan optimal FIR filter designfirpmord Parks-McClellan optimal FIR filter order estimationfirrcos Raised cosine FIR filter designgaussfir Gaussian FIR pulse-shaping filter designintfilt Interpolation FIR filter designkaiserord Kaiser window FIR filter design estimation parameterssgolay Savitzky-Golay filter design

• Conception de filtres RII

buttord Butterworth filter order and cutoff frequency

Analyse des caractéristiques des filtres

filternorm 2-norm or infinity-norm of a digital filterbuttord Butterworth filter order and cutoff frequencybutter Butterworth analog and digital filter designcheb1ord Chebyshev Type I filter ordercheby1 Chebyshev Type I filter design (passband ripple)cheb2ord Chebyshev Type II filter ordercheby2 Chebyshev Type II filter design (stopband ripple)ellipord Minimum order for elliptic filtersellip Elliptic (Cauer) filter designmaxflat Generalized digital Butterworth filter designyulewalk Recursive digital filter design

173

filternorm 2-norm or infinity-norm of a digital filterfreqz Frequency response of digital filtersfvtool Filter Visualization Toolgrpdelay Average filter delay (group delay)impz Impulse response of digital filtersphasedelay Phase delay response of digital filtersphasez Phase response of digital filtersstepz Step response of digital filterszerophase Zero-phase reponse of digital filterszplane Zero-pole plot

Étape 1 : Schéma et équations

Exemple sur une cellule RII du 2e ordre

b1

b0

-a1

ynxn

wns

2211 −−

++=

−−= nnnn

wbwbwby

wawasxwwn-1

z-1

174

b2-a2

22110 −− ++= nnnn wbwbwby

wn-2

z-1

Forme directe II

Équations correspondantes

Étape 2 : Variables et algorithme

s

coefs

wn-1 w(n-1)

dbufferEntrées :x (contient xn)dbuffer (contient wn-1 et wn-2)coefs (contient les coefficients)

0 0

a1

a2

b2

b1

b0

wn-2 w(n-2)

tableau descoefficients

tableau desretards

Variable temporaire :w (recevra wn)

Calcul

wn ← s * xn – a1 * w(n-1) – a2 * w(n-2)

y ← b0 * wn + b1 * w(n-1) + b2 * w(n-2)

Mise à jour retards

xn

? puis yn

x

y

coefs (contient les coefficients)1

2

3

4

5

1

175

coefficientsw(n-2) ← w(n-1)

w(n-1) ← wn

? puis yn y

? puis wn w

variablestemporaires

État de la mémoirelors de l'appel de la fonction

Sorties :y (reçoit yn)dbuffer (contient wn'-1 et wn'-2 pour n'=n+1)

Étape 3 : Format Qk et programme C

x(n) Q15

s Q15 int cellule(int x) {int w;

int coefs[6];int dbuffer[2];

ai Q15

bi Q15

wk Q15/* Calcul */w=((long)coefs[0]*x

-(long)coefs[1]*dbuffer[0]–(long)coefs[2]*dbuffer[1]) >> 15;

y=((long)coefs[5]*w+(long)coefs[4]*dbuffer[1]+(long)coefs[3]*dbuffer[0]) >> 15;

/* Mise à jour retards */

int cellule(int x) {int w;int y;

Conversion algorithme (calcul sur des réels)vers programme (calcul en format Qk)

176

/* Mise à jour retards */dbuffer[1]=dbuffer[0];dbuffer[0]=w;

/* Sortie */return y;

}

s * x

devient

(coefs[0]*x)>>15

pour un résultat en Q15

Aller-retour étapes 1-2-3:correction d’erreurs, évolution des objectifs

coefsw (n-1)

dbuffer

0

Exemple: extension de l’algorithme à des cellules en cascade.L’implantation mémoire nécessite une phase de conception

s

a11

a12

b12

b11

b10

w1(n-1)

w1(n-2)

w2(n-1)

w2(n-2)cellule 1cellule 2

cellule 10

1

2

…

…

5

0

1

2+1

2+2

177

a21

a22

b22

b21

b20

cellule 2

5+1

5+2

…

H1(z) H2(z)sx(n) …

Nouvelle structure du filtre

Utilisation de lookup-table (LUT)

178

Principe de la LUT

• Précalcul d’une fonction calculatoirement y = g(x)

g(x0)

lut

0

k

g(x1)

g(x )

1calculatoirementcomplexe– Fonctions

trigonométriques

– Fonction non-linéaire(log, exp…)

– Forme d’onde ou fenêtre(triangle, hamming…)

y = g(x)

y = lut[m]

g(x2)

g(x3)

2

3

g(xM-2)M-2

g(xM-1)M-1

……

(triangle, hamming…)

• Approximation– Quantification des valeurs

d’entrée x

179

avec xm = x0+m.q

lut[m] ≝ g(xm)

Exemple : LUT pour la fonction cosinus

Une période : cos(2π t) pour t∈[0,1[

lut[m] ≝ cos(2π m/M) pour m∈[0..M-1]-0.5

0

0.5

1

cos(2π n f / f )

lut[m] ≝ cos(2π m/M) pour m∈[0..M-1]

t = m/M

Application au calcul d’une sinusoïde de fréquence f à fréquence d’échantillonnage fe

0 0.2 0.4 0.6 0.8 1-1

0 5 10 15

-3

-2

-1

0

1

2

3x 10

4

180

cos(2π n f / fe)

m = n f M / fe

t = n f / fe

fe / M = flut peut être précalculé si entier

cos(2π n f / fe) � lut[n * f / flut]

Calculs entiers uniquement

Filtres RIF

• Structure transverse• Buffer linéaire

181

• Buffer linéaire• Buffer circulaire

Structures pour filtre RIF

• Structure transverse avec ligne à retard

xxn-N+1xn-1 xn-2

• Structure en treillis (filtres adaptatifs)

xn

yn

xn-N+1xn-1 xn-2

b0 b1 b2 b3 bN-1

182

Filtre RIF par structure transverse

• Deux aspects

– Mise à jour de la mémoire– Mise à jour de la mémoire

• A chaque réception d’une nouvelle donnée x(n)

– Calcul du filtre

ACCU← 0

Insérer x(n) dans un buffer

183

ACCU← 0Pour i de 0 à N-1

ACCU ← ACCU + h(i) × x(n-i)

Retourner ACCU

x(n-1)

Buffer linéaire

0x(n-1) x(n)

x(n)xtab xtab

0

Schéma "état mémoire"

Application au filtre RIFx(n-1)

( ) ( ) ( )∑−

=

−=1

0

N

i

inxibny2

0

1

N-2

x(n-1)

x(n-2)

…

…

…

…

x(n-N+1)

x(n)

x(n-1)

x(n-2)

…

…

…

x(n-N+2)

0

1

N-2

1

pour i de 0 à N-1:A ← A + btab[i] × xtab[i]

Application au filtre RIF

184

N-2

N-1

x(n-N+1)

x(n-N)

x(n-N+2)

x(n-N+1)

x(n-N)

Mise à jour du buffer

N-2

N-1

Avant insertionde x(n)

Après insertionde x(n)

Calcul

Buffer circulaire (adressage modulo)

x(n)xtab xtab

Schéma "état mémoire"

Application au filtre RIF

x(n-N)

x(n-k+1)

…

x(n-N+1)

x(n-N)

x(n-1)

x(n-2)

x(n-k+1)

…

x(n-N+1)

x(n)

x(n-1)

x(n-2)

idx

0

1

0

1

idxpour i de 0 à N-1:

idd ← (idx + i)%NA ← A + btab[i] × xtab[idd]

Utilisation d’une variable

( ) ( ) ( )∑−

=

−=1

0

N

i

inxibny

Application au filtre RIF

Calcul

idx

185

…

x(n-k)

Mise à jour du buffer

…

x(n-k)

N-2

N-1

N-2

N-1

Utilisation d’une variable auxiliaire idd pour l’index de x(n-i) dans le tableau

Plus lisible lors de la conception de l’algorithme permet de représenter idd sur un schéma

Avant insertionde x(n)

Après insertionde x(n)

Filtre RIF avec buffer circulaire en assembleur

( ) ( ) ( )∑−

=

−=1

0

N

i

inxihnyN .set 32

; adr_x+d supposé chargé dans AR2 Adresses Contenu=0idans AR2

STM #(coef)+N-1, AR3

STM #(adr_y), AR5

STM #N, BK

STM #1, AR0

RPTZ A, #N-1

i = coef h(N-1)

Adresses Contenu

i + 1 h(N-2)

i + 2 h(N-3)

…… ……

i + N - 1 h(0)

k = adr_x x(n-N+d-1)

Adresses Contenu

…… ……

k + d - 1 x(n-N+1)

…… ……

k + d x(n)

k + N x(n-N+d)

186

RPTZ A, #N-1

MAC *AR2+0%, *AR3-, A

STH A, *AR5

i + N - 1 h(0)

Mémoire Programme

k + N x(n-N+d)

Mémoire Données

Rmq: les log2(N) bits de poids faible de adr_x

doivent être nuls pour que l’adressable modulo *AR2%0 fonctionne

Filtre RIF en virgule fixe

Entrées y(n) et sorties x(n) généralement normalisées de façon identiquePar exemple sur [-1 1] : format Qm-1 sur m bits signés

Coefficients au format Qk, dépend du filtre

( ) ( ) ( )∑−

=

−=1

0

N

i

inxihny

Coefficients au format Qk, dépend du filtre

Y = (H * X) >> k

187

Y = (H * X) >> k

Qm-1+k

Qk Qm-1

Qm-1

Qm-1

Saturation pour un filtre RIF

( ) ( ) ( )∑−

=

−=1

0

N

i

inxihny

m bitsm’’ bits m’ bits

maxmax)( xNhny ≤

Signé

)(log max2 xm =

)(log' hm =

m bitsm’’ bits m’ bits

Non-signé

1)(log max2 += xm

1)(log' += hm

(Pire cas sur x et h)

188

)(log' max2 hm =''

max 2my =

)(log''' 2 Nmmm ++=

1)(log' max2 += hm

1''max 2 −= my

)(log1''' 2 Nmmm +−+=

Bornes sur la saturation

• Lorsque le filtre h est connu, on peut être plus précis

( ) ( )∑−

<1N

xihny( ) ( ) ( )∑−

−=1N

inxihny ⇒

• Ce qui correspond à

( ) ( )∑=

<0

max

i

xihny

+= ∑ )][(log'' 2

i

iHmm

en notant H[i] l’entier correspondant au codage Qk sur m’ bits de h(i)

( ) ( ) ( )∑=

−=0i

inxihny ⇒

189

−

≥−=

sinon

0)( si 1-)(

max

max

x

nhxnx

Cette borne est atteinte pour un signal spécifique x :

en notant H[i] l’entier correspondant au codage Qk sur m’ bits de h(i)

Compromis précision/saturation (1)

T = 0pour i=0..N-1

Calcul brut Exemple:

H et X au format Q7 signé sur 8 bitspour i=0..N-1T = T+(H[i]*X[i])

Y = T >> k

T format Qk+m-1 sur m’’ bits

Y format Qm-1 sur m bits

H X

T au format Q14 sur 16 bits

T = T + H*B

Qk Qm-1

16+G bits

190

Y au format Q7 sur 8 bits

Y = T >> 7

Qm-1

Nécessité de bits de garde si filtre de taille importante.

G bits

Perte de précisionSaturation

Compromis précision/saturation (2)

T = 0pour i=0..N-1

Décalage dès les calculs intermédiaires Exemple:

H et X au format Q7 signé sur 8 bitspour i=0..N-1T = T+((H[i]*X[i]) >> p)

Y = T >> (k-p)H X

T au format Q10 sur 16 bits

T = T + (H*B)>>3

Qk Qm-1

Perte de précision sur les résultats intermédiaires, mais pas de risque de saturation à ce niveau

p=3

191

Y au format Q7 sur 8 bits

Y = T >> (7-3)

Qm-1

de saturation à ce niveau

Pas de saturation si filtre bien choisi en fonction du type de signal

Filtres RII

• Structures de filtres

192

• Décomposition en éléments simples

• Problèmes de quantification

Filtre RII

• Fonction de transfert rationnelle

−1Q −− 11 QQ

∑

∑−

=

−

−

=

−

+

==1

1

1

0

1)(

)()(

P

k

kk

Q

i

ii

za

zb

zA

zBzH

( )∏∑−

=

−−

=

− −=1

0

10

1

0

1

Q

i

i

Q

i

ii zzbzb

( )∏∑−

=

−−

=

− −=+1

0

11

1

11

P

i

i

P

i

ii zpza

Zéros zi

Pôles pi

193

• Equation aux différences

∑∑−

=−

−

=− −=

1

1

1

0

P

k

knk

Q

i

inin yaxby

Pôles pi

Forme directe I (ND)

z-1 z-1

b0xn yn )(

1)()(

zAzBzH =

∑∑−

=−

−

=− −

=

1

1

1

0

Q

k

knk

Q

i

inin yaxby

z-1

z-1

z-1

z-1

z-1

z-1

b1

b2

b3

•Forme non canonique

-a1

-a2

-a3

194

z-1 z-1

•Forme non canonique

•Nécessite Q+P mémoires Q pour les x(n-i)P pour les y(n-k)

Forme directe I (ND)

-aQ-1

B(z) 1/A(z)

bQ-1

Forme directe II (DN)

z-1

b0

yn

)()(

1)( zB

zAzH =

xn

wn

z-1

z-1

z-1

b1

b2

b3

-a1

-a2

-a3 ∑−

=−=

1

0

Q

i

inin wby

∑−

=−−=

1

1

Q

k

knknn waxw

195

z-1

bQ-1-aQ-1

•Forme canonique

•Nécessite max(Q,P) mémoires

•Risque accru de dépassement au niveau de w(n) car filtre récursif 1/A(z) appliqué en premierForme directe II (DN)

1/A(z) B(z)

Transposition de la structure du filtre

xn

z-1

wnb0 yn

b0xn yn

-a1

-a2

z-1

z-1

b1

b2b2

b1

z-1

z-1

Forme directe II Forme directe II transposée

-a1

-a2

196

22110 −− ++= nnnn wbwbwby

2211 −− −−= nnnn wawaxw

2211

22110

−−

−−

−−

++=

nn

nnnn

yaya

xbxbxby

Bilan structures RII

Formes II et II transposéeCanoniques en nombre de retards

Formes I et II transposée:Partie non récursive appliquée en premier

z-1 z-1

b1

b0xn yn

-a1

xn

b0

z-1

yn

z-1

b

b0

-a

ynxn

wn

Partie non récursive appliquée en premier� Limite les saturations dues aux résonnances dans la partie récursive

Forme II transposée:Potentielle perte de précision à chaque retard

z-1 z-1

b2 -a2

Forme directe I

197

b2

-a1

-a2

b1

z-1

z-1z-1

z-1

b1

b2

-a1

-a2

Forme directe II Forme directe II transposée

Décomposition d’un filtre RII

• en sections du deuxième ordre– choisies pour leur stabilité et robustesse

– coefficients réels (racines conjuguées)

Structure parallèle

2

2

1

1

1

10

1 −−−−−−−−

−−−−

++++++++++++

zaza

zbb

x y

Structure cascade

c0

21

2

2

1

10

1 −−−−−−−−

−−−−−−−−

++++++++++++++++

zaza

zbzbb21

2

2

1

10

1 −−−−−−−−

−−−−−−−−

++++++++++++++++

zaza

zbzbbxn yn

198

2

2

1

1

1

10

1 −−−−−−−−

−−−−

++++++++++++

zaza

zbbxn yn

Expansion partielle

∑∑∑∑−−−−

====−−−−−−−−

−−−−

++++++++++++

++++====1

02

2

1

1

1

100

1)(

)( N

i ii

ii

zaza

zbbc

zA

zB

211 ++++++++ zaza 211 ++++++++ zaza

Factorisation

∏∏∏∏−−−−

====−−−−−−−−

−−−−−−−−

++++++++++++++++

====1

02

2

1

1

2

2

1

10

1

1

)(

)( N

i ii

ii

zaza

zbzbb

zA

zB

Décomposition en cascade

s0 s1 s2 s3x(n) y(n)H1(z) H2(z) H3(z)

s0 s1 s2 s3x(n) y(n)

)()()(1

1

)(

)(3210

1

02

2

1

1

2

2

1

10 zHzHzHb

zaza

zbzbb

zA

zB N

i ii

ii =++++

= ∏−

=−−

−−

199

2

2

1

1

2

2

1

1

1

1)(

−−

−−

++++

=zaza

zbzbzH

ii

iii

avec :avec : etet03210 bssss =

Exemple

– Pour les spécifications suivantes (fs=16kHz):

– L’approximation de Chebyshev nécessite un filtre – L’approximation de Chebyshev nécessite un filtre d’ordre 6 :

200

[N,Wn]=CHEB2ORD(1800/8000,4000/8000,0.01,50);

[B,A]=CHEBY2(N,50,Wn)

Exemple

• B = [ 0.0276 0.0685 0.1194 0.1392 0.1194 0.0685 0.0276 ]

Coefficients:

• A = [ 1.0000 -1.5044 1.7003 -0.9512 0.3933 -0.0764 0.0085 ]

Fonction de transfert: freqz(B,A)

201

Exemple : décomposition en cascade

Fonction de transfert: freqz(B,A) Pôles et zéros: zplane(A,B)

12

3

symétrie

• Appariement :

• Les pôles conjugués les plus proches du cercle unité sont appariés aux zéros les plus proches. On recommence avec les deuxièmes plus proches et ainsi de suite.

• Ce choix maximise la stabilité de chaque section202

Exemple : décomposition en cascade

[SOS,G]=tf2sos(B,A);1.0000 1.7489 1.0000 1.0000 -0.2831 0.0461

1.0000 0.6667 1.0000 1.0000 -0.4695 0.2687SOS = B2

B1

A2

A1

G = 0.0276

-40

-20

0

20

H1

H2

H3

H

1.0000 0.6667 1.0000 1.0000 -0.4695 0.2687

1.0000 0.0693 1.0000 1.0000 -0.7518 0.6868B3 A3

SOS = B2 A2G = 0.0276

21

21

10461.02831.01

7489.11)( −−

−−

+−++

=zz

zzzH

216667.01 −− ++ zz

Fonctions de transfert: freqz(B1,A1)…

203

0 1000 2000 3000 4000 5000 6000 7000 8000-120

-100

-80

-60

-40

21

21

22687.04695.01

6667.01)( −−

−−

+−++

=zz

zzzH

21

21

36868.07518.01

0693.01)( −−

−−

+−++

=zz

zzzH

0276.00 =b

Filtrage en virgule fixe

• Quantification des coefficients

• Quantification des signaux

204

Erreur de quantification des coefficients

z-1

b

b0

-a

ynxn

aaa ∆+=z

z-1

z-1

b1

b2

b3

-a1

-a2

-a3

kkk aaa ∆+=

kkk bbb ∆+=

205

z-1

bQ-1-aQ-1

Forme directe II

Quantification d’un coef :

aq = round(a*q)/q

avec un pas de quantification q=2-k

Quantification des coefficients

kkk aaa ∆∆∆∆++++====∑

∑

−

=

−

+

==P

k

Q

i

ii zb

zA

zBzH 0

)(

)()(

Le dénominateur quantifié devient :

Plus le degré du polynôme est élevé, plus les pôles et

kkk

( ) ( )∏∑−

=

−−

=

− −=+=1

1

1

1

1

11

Q

l

l

Q

k

kk zpzazA

∑=

−+k

kk za

zA

1

1)(

206

Plus le degré du polynôme est élevé, plus les pôles et les zéros seront perturbés modifiant ainsi la fonction de transfert

Il est plus robuste de décomposer le filtre en sections d’ordre plus faible

Effets de la quantification (1)

207

Fonction de transfert avec coefficients quantifiés(Structure directe)

Effets de la quantification (2)

208

Fonction de transfert avec coefficients quantifiés(Structure cascade de sections du 2nd ordre)

Quantification et saturation sur les données

Apparaît quand on tronque les données de l’accumulateur pour les stocker en mémoire (bruit de quantification en)

Forme Directe IIUne source de bruit

-a1

xn

b1

b2

z-1

yn

en

z-1

b1

b0

-a1

ynxn

en

Forme Directe II TransposéeDeux sources de bruit

209

b2 -a2

z-1

z-1

b2-a2

Une seule source de bruit qui est de plus filtréeMais application des pôles du filtre en premier=> risques de saturation sur wn

Application des zéros du filtre en premier=> filtrage des fréquences susceptibles d’avoir un large gain au niveau des pôles

Cycles limites sur filtres récursifs

z-1

g

x(n) y(n) y(n) = x(n) + g . y(n-1)

zg

Y = X + ((G * Y + 1) >> 2);

Exemple pour G en Q2 et X et Y entiers

Division par 4avec arrondi au plus proche voisin

Pour g=0.75, G=3, Y(0)=3 et X(n) nul

Avec arrondiY(0)=3Y(1)=2

Sans quantification :y(0)=3y(1)=2.25

210

Y(1)=2Y(2)=1Y(3)=1Y(4)=1Y(5)=1Y(6)=1Y(7)=1Reste bloqué à 1

y(1)=2.25y(2)=1.6875y(3)=1.2656…y(4)=0.9492…y(5)=0.7119…y(6)=0.5339…y(7)=0.4004…Tend vers 0

((3 * 1 + 1) >> 2) == 1

Gestion de la saturation (1)

• Signal à bande étroite

(proche d’une sinusoïde pure de fréquence f0)(proche d’une sinusoïde pure de fréquence f0)

• On a alors la borne

max)()( xfHny∞

≤

)()()( 0 fXfHfY ≈

avec

211

max∞

)(maxarg)( fHfHf

=∞

Gestion de la saturation (2)

• Signal à bande large

– On raisonne en puissance moyenne– On raisonne en puissance moyenne

– La probabilité de non saturation dépend du type de signal et du facteur de charge

222)()()( fXfHfY ≤

y

212

∫=

==ef

fe

x dffXf

fX

0

222

2)(

1)( σ

yy

y

σmax=Γ

Saturation sur les résultats intermédiaires

z-1

b0

ynxn

wnAfin d’éviter la saturation lors du stockage de wn, ajout de facteurs d’échelles:

s en entréez-1

z-1

b1

b2

-a1

-a2

s en entrée1/s en sortie

Signal à bande étroite, utilisation de la norme L∞∞∞∞ :

Signal à bande large, utilisation de la norme L :

∞

=)(/1

1

fAs

b0 / s

yxwn

s

213

Signal à bande large, utilisation de la norme L2 :

2)(/1

1'

fAs =z-1

z-1

b1 / s

b2 / s

-a1

-a2

ynxn

Vue d’ensemble

: bruit de quantification et risque de saturation

214

210

03 αααααααααααα

ααααb

====(((( ))))∞∞∞∞

====fA0

0/1

1αααα

(((( )))) (((( )))) (((( ))))(((( ))))∞∞∞∞

====fAfAfB 1000

1/

1

αααααααα (((( )))) (((( )))) (((( )))) (((( )))) (((( ))))(((( ))))

∞∞∞∞

====fAfAfAfBfB 2101010

2/

1

αααααααααααα

Bruit en sortie

– La puissance du bruit en sortie est :

∫∫∫∫====eF

e

eo dffHfHfHF 0

2

2

2

1

2

0

2

3

2

2

2

1

22 )()()(1

αααααααααααασσσσσσσσ

∫∫∫∫++++eF

e

e dffHfHF 0

2

2

2

1

2

3

2

2

2 )()(1

αααααααασσσσ

∫∫∫∫++++eF

e

e dffHF 0

2

2

2

3

2 )(1

αααασσσσ

Bruit du premier étage

Bruit du deuxième étage

Bruit du troisième étage

215

Le facteur d’échelle atténue le signal, mais pas le bruit de quantification, il faut donc le choisir le plus élevé possible, sous la contrainte de la saturation.

Calcul du facteur d’échelle

[SOS,G]=tf2sos(B,A);

B = [ 0.0276 0.0685 0.1194 0.1392 0.1194 0.0685 0.0276 ]A = [ 1.0000 -1.5044 1.7003 -0.9512 0.3933 -0.0764 0.0085 ]

1.0000 1.7489 1.0000 1.0000 -0.2831 0.0461

1.0000 0.6667 1.0000 1.0000 -0.4695 0.2687

1.0000 0.0693 1.0000 1.0000 -0.7518 0.6868B3 A3

SOS = B2

B1

A2

A1

G = 0.0276

DécompositionG=s0s1s2s3 non fournie choix du concepteur

[SOS,G]=tf2sos(B,A);

216

H1(z) H2(z) H3(z)

s0 s1 s2 s3x(n) y(n)

Facteurs d’échelle intégrés aux filtres

[SOS,G]=tf2sos(B,A,’up’,’two’);

B = [ 0.0276 0.0685 0.1194 0.1392 0.1194 0.0685 0.0276 ]A = [ 1.0000 -1.5044 1.7003 -0.9512 0.3933 -0.0764 0.0085 ]

[SOS,G]=tf2sos(B,A,’up’,’two’);

0.2776 0.4854 0.2776 1.0000 -0.2831 0.0461

0.2681 0.1787 0.2681 1.0000 -0.4695 0.2687

0.3851 0.0267 0.3851 1.0000 -0.7518 0.6868B3 A3

SOS = B2

B1

A2

A1

G = 0.9617

Les facteurs d’échelle s1, s2, s3 sont déjà intégrés aux coefficients BLe G calculé correspond à s0

0.0276 = 0.9617 × 0.2776 × 0.2681 × 0.3851

217

H1(z) H2(z) H3(z)

Gx(n) y(n)

0.0276 = 0.9617 × 0.2776 × 0.2681 × 0.3851

Codage Qk des coefficients d’une cellule RII

• Pour des sections du second ordre,– A(z) et B(z) peuvent s’écrire: (((( )))) 221cos21 −−−−−−−− ++++−−−− zrzr θθθθ

– Dénominateur: pour la stabilité |r|<1, donc les coefficients sont dans [-2,2].

– Numérateur: en utilisant les prototypes classiques (Butterworth, Chebychev, Elliptique) les zéros sont sur le cercle unité:|r|=1 les coefficients sont dans [-2,2].

�Codage Q14 sur 16 bits OKSur l’exemple précédent, Q15 convient aussi(tous les coefficients sont entre -1 et 1)

218

Codage Qk des coefficients

0.2776 0.4854 0.2776 1.0000 -0.2831 0.0461

0.2681 0.1787 0.2681 1.0000 -0.4695 0.2687SOS =

BG = 0.9617

A

0.2681 0.1787 0.2681 1.0000 -0.4695 0.2687

0.3851 0.0267 0.3851 1.0000 -0.7518 0.6868

SOS =

SOSq = round( SOS / 2^15 );Gq = round( G / 2^15 );% plus test de saturation

9095 15906 9095 32767 -9277 1511

8786 5857 8786 32767 -15385 8803SOSq =

Gq = 31512

219

8786 5857 8786 32767 -15385 8803

12619 875 12619 32767 -24634 22505

SOSq =

Attention à la saturation:le plus grand entier signé en Q15 est 32767

et non pas 32768

Conclusion

• Filtres RIF– Structure transverse: buffers linéaires et circulaires– Implémentation virgule fixe– Implémentation virgule fixe

• Filtres RII– Structures : forme I, II, II transposée– Décomposition cascade

• Quantification des coefficients– Perturbation des pôles et des zéros– Perturbation des pôles et des zéros

• Quantification et saturation des signaux– Facteurs d’échelle– Choix des facteurs d’échelle

220

AnnexesAnnexes

221

Bibliographie

• A.Bateman, I.Paterson-Stephens. The DSP handbook. Prentice Hall.handbook. Prentice Hall.

• G.Baudoin, F.Virolleau. Les DSP - Famille TMS320C54x - Développement d'applications. Dunod.

222

Ressources en ligne

• Ressources générales sur les DSP

– www.bdti.com– www.bdti.com

– www.insidedsp.com

• Constructeurs

– dspvillage.ti.com

– www.analog.com/processors– www.analog.com/processors

– www.freescale.com

– www.starcore-dsp.com

223