Very High Speed Integrated Circuit Hardware Description Language/Réalisation d'un coprocesseur CORDIC

Leçons de niveau 16
Une page de Wikiversité, la communauté pédagogique libre.
Début de la boite de navigation du chapitre
Réalisation d'un coprocesseur CORDIC
Icône de la faculté
Chapitre no 17
Leçon : Very High Speed Integrated Circuit Hardware Description Language
Chap. préc. :Le NIOS d'Altera
Chap. suiv. :Commande de robot mobile et périphériques associés
fin de la boite de navigation du chapitre
En raison de limitations techniques, la typographie souhaitable du titre, « Very High Speed Integrated Circuit Hardware Description Language : Réalisation d'un coprocesseur CORDIC
Very High Speed Integrated Circuit Hardware Description Language/Réalisation d'un coprocesseur CORDIC
 », n'a pu être restituée correctement ci-dessus.

Nous appellerons un coprocesseur dans la suite de ce cours tout périphérique suffisamment sophistiqué pour :

  • faire des calculs arithmétiques au sens large
  • nécessiter un processeur pour être testé
  • éventuellement être capable d'exécuter un programme

Les GPU (des cartes graphiques) se rangent dans cette catégorie mais aussi les processeurs mathématiques (Unités de calcul en virgule flottante (ou FPU)) capables de calculer des fonctions simples ou compliquées comme les fonctions trigonométriques ou les fonctions hyperboliques.

Introduction à CORDIC[modifier | modifier le wikicode]

L'algorithme CORDIC est un algorithme itératif permettant de faire des calculs de fonctions trigonométriques, de fonctions hyperboliques ou de fonctions linéaires. Cet algorithme est difficile à appréhender lors d'une première approche. Heureusement, utiliser un algorithme ne nécessite pas de comprendre comment il fonctionne dans les détails. Mais sa modification ou son adaptation par contre le nécessite.

Domaines d'utilisation de l'algorithme CORDIC[modifier | modifier le wikicode]

L'algorithme CORDIC peut naturellement être simplement utilisé pour des calculs. Pourtant, dans un livre sur les processeurs enfouis, nous ne resterons pas dans le domaine de l'abstraction. Nous allons donc lui consacrer au moins deux domaines d’applications :

  • robotique mobile : calcul des coordonnées x et y d'un robot se déplaçant à l'aide de deux moteurs à courant continu. Lisez AVR et robotique : ASURO dans un autre projet et particulièrement la section "Marier l'électronique et la cinématique" vous y trouverez des formules faisant intervenir des sinus et cosinus.
  • commande de moteur synchrone

Propriétés des fonctions trigonométriques[modifier | modifier le wikicode]

Les calculs se font avec des nombres. Puisqu'ici nous désirons étudier des "sinus" et "cosinus" et que ces nombres sont entre 0 et 1 il nous faudra réfléchir sur la façon de représenter ces nombres. C'est l’objet de la prochaine section.

Représentation des nombres à virgule[modifier | modifier le wikicode]

Il existe au moins deux méthodes pour faire cela :

Nous allons présenter les deux méthodes même si nous avons l'intention de nous attarder beaucoup plus sur la virgule fixe.

La représentation virgule flottante[modifier | modifier le wikicode]

L'article Virgule_flottante de wikipédia est suffisamment complet pour ne pas être repris ici. Il peut d'ailleurs être complété par la lecture de l’article détaillé sur la norme IEEE 754 correspondante.

Voici en figure récapitulative le codage des nombres flottants.

Format général de représentation des flottants
Format général de représentation des flottants

Il existe essentiellement deux formats :

Encodage Signe Exposant Mantisse Valeur d'un nombre Précision Chiffres significatifs
Simple précision 32 bits 1 bit 8 bits 23 bits 24 bits environ 7
Double précision 64 bits 1 bit 11 bits 52 bits 53 bits environ 16

Sur ces deux formats, seul le format simple précision sur 32 bits nous intéresse. Il peut se résumer avec la figure :

Format de représentation des flottants en simple précision
Format de représentation des flottants en simple précision

Pour un nombre normalisé, le bit de poids fort de la mantisse est toujours à 1 et il n'est alors pas représenté. Il est alors qualifié de bit implicite. La conséquence est que l'expression du tableau pour la représentation 32 bits doit être comprise comme :

  • une différence entre le M de la formule et la Mantisse : M = 1,Mantisse
  • la valeur du nombre est donnée par

Si le bit de poids fort de la mantisse (ici bit 23 implicite) est nul (en général pour un exposant décalé nul) alors le nombre est dit dénormalisé.

La représentation virgule fixe[modifier | modifier le wikicode]

Le format Virgule fixe n’est pas normalisé contrairement au format virgule flottante. Le seul point commun que l’on retrouve dans tous les formats virgule fixe est qu’il est signé. Il peut donc représenter des nombres positifs ou négatifs en complément à 2. La virgule étant placée par défaut à un endroit fixe on utilise en général une notation du genre Qm.n pour le désigner où m représente le nombre de bits avant la virgule et n le nombre de bit après la virgule et donc m+n est la taille de la représentation.

Par exemple nous allons utiliser un format Q3.13 dans la suite de ce chapitre.

S

Il s'agit d'un format 16 bits (3+13) et adapté à la trigonométrie en radian.

Pour manipuler ce format nous proposons quelques utilitaires en C. Ils sont basés sur le fait que la librairie standard du compilateur C sait manipuler les nombres à virgule à partir du moment où ils sont en virgule flottante. La lecture à partir du clavier ainsi que l’affichage sur un écran de ces nombres est aussi dans la librairie standard.

Début d’un principe
Fin du principe

Nous proposons donc deux routines permettant les transformations de notre format virgule fixe Q3.13 vers le format flottant.

Format Q3.13 vers flottant[modifier | modifier le wikicode]

Nous vous proposons deux sous-programmes destinés à une conversion du format Q3.13 vers le format float du C. Nous avons écrit ces sous-programme avec l'intention un jour de les implanter en matériel. C'est pour cela qu'ils peuvent vous paraître obscurs. En effet une simple division flottante peut naturellement faire l'affaire.

Sans entrer dans les détails, nous vous proposons des sous-programmes réservés aux architectures de type PC :

// Serge MOUTOU Avril 2013
// destiné à une architecture 32 bits et non aux AVRs ciblés
// Sur un PC cela fonctionne normalement
float HexQ3_13ToFloat(int val){ //conversion Q3.13 vers float
   float temp; 
   int i_temp; 
   char i; 
   if (val < 0) i_temp = -val; else i_temp = val; 
   temp = ((i_temp & 0x6000)>>13); 
   for (i=0;i<13;i++) 
     if (i_temp & (1<<i)) temp += pow(2,(i-13)); 
   if (val < 0) return -temp; else return temp; 
}
//******* version sans pow
/**************************************************
/* Ne peut pas fonctionner avec AVR car
/* int et float n'ont pas la même taille !!!!
/**************************************************/
float HexQ3_13ToFloat2(int val){
   union {
     float temp;
     int f_temp;
  } u;
  int i_temp;
  unsigned char exposant=129;//,*p;
  signed char i;
  if (val < 0) i_temp = -val; else i_temp = val;
  for (i=15;i>=0;i--) {
    if (i_temp & (1<<i)) { 
    // on efface le '1' trouvé :
      i_temp= i_temp & ~(1<<i);
      break;// on sort de la boucle
    }
    exposant--;   
  }
  u.f_temp = exposant; 
  u.f_temp <<=23; 
  u.f_temp = u.f_temp|(i_temp << (23-i));
  if (val < 0) return -(u.temp); else return u.temp;
} 

//******* version sans pow
/**************************************************
/* Version pour AVR : Arduino OK et SOC OK
/* Serge MOUTOU Fevrier 2019
/**************************************************/
float HexQ3_13ToFloat_AVR(int16_t val){
   union {
     float f_temp;
     int32_t li_temp;
  } u;
  uint32_t i_temp;
  unsigned char exposant=129;//,*p;
  signed char i;
  u.li_temp = 0;
  if (val < 0) i_temp = -val; else i_temp = val;
  for (i=15;i>=0;i--) {
    if (i_temp & (1<<i)) { 
    // on efface le '1' trouvé :
      i_temp= i_temp & ~(1<<i);
      break;// on sort de la boucle
    }
    exposant--;   
  }
  u.li_temp = exposant; 
  u.li_temp <<=23; 
  u.li_temp = u.li_temp|(i_temp << (23-i));
  if (val < 0) return -(u.f_temp); else return u.f_temp;
}

La deuxième routine n'utilisant pas "pow" n'a pas beaucoup d'intérêt pour un PC. Mais elle a été développée en vue d'un portage sur AVR, ce qui a été fait quelques années après (2019).

Comme nous l'avons énoncé au tout début de cette section, une simple routine universelle pourrait donc être réalisée par :

// Serge MOUTOU Juin 2018
// destiné à une architecture quelconque
float HexQ3_13ToFloat3(int val){ //conversion Q3.13 vers float
  return (val * 1.0 / (0x2000)); // 0x2000 = 1 en Q3.13
}

Attachons-nous maintenant à la transformation inverse.

Format flottant vers Q3.13[modifier | modifier le wikicode]

La transformation du format flottant vers le Q3.13 se fait par :

// Serge MOUTOU Avril 2013
// destiné à une architecture 32 bits et non aux AVRs ciblés
// Sur un PC cela fonctionne normalement
int float2HexQ3_13(float val){ //conversion float vers Q3.13
   int temp; 
   char i; 
   float f_temp; 
   if (val < 0) f_temp = -val; else f_temp = val; 
   temp = ((int) floor(f_temp)<<13); 
   f_temp = f_temp - floor(f_temp); 
   for (i=0;i<13;i++) { 
     temp|=((int)floor(2*f_temp)<<(12-i)); 
     f_temp = 2*f_temp - floor(2*f_temp); 
    } 
    if (val < 0) return -temp; else return temp; 
}
//************************************************************************
// function float2HexQ3_13_2()
// purpose: transformation of a 32-bit float number into 16-bit Q3.13 number 
// arguments:
//      corresponding float number
// return: 16-bit int 
// note: This function works on Linux but not with AVR
//************************************************************************
typedef union {
     float f_temp;       //taille : {{unité|4|octets}}
     int li_temp;        //taille : {{unité|4|octets}}
  } t_u;
// version sans calcul float
int float2HexQ3_13_2(float val){ //conversion float vers Q3.13
  t_u u,v;
  unsigned char exposant;
  int mantisse;
  int result=0;
  u.f_temp = val;
  if (val < 0) u.f_temp = - u.f_temp;
  v = u;
  // recupération de l'exposant
  v.li_temp >>= 23;
  exposant = v.li_temp;
  // recuperation mantisse
  if (exposant < 129) {
    mantisse = (u.li_temp & 0X007FFFFF);
    // mise à 1 du bit manquant
    result |= (1 << (exposant-114));  // (15-129+exposant)); semble OK
    mantisse >>= (137-exposant);      //(22-(14-129+exposant));
    result |= mantisse;
    if (val < 0) return -result; 
    else return result;
  } else {printf("Erreur conversion : nombre trop grand\n");
    return 0x7FFF; // le plus qu'on puisse faire pour 16 bits
  }
}

//************************************************************************
// function float2HexQ3_13_AVR()
// purpose: transformation of a 32-bit float number into Q3.13 for AVR
// arguments:
// corresponding float number 
// return: integer in Q3.13 format
// note: idem to float2HexQ3_13 but without float library
// Juin 2018
//************************************************************************
int float2HexQ3_13_AVR(float val){ //conversion float vers Q3.13
  union {
     float f_temp;       //taille : 4 octets
     long int li_temp;  //taille : 4 octets
  } u,v;
  unsigned char exposant;
  long int mantisse;
  int result=0;
  u.f_temp = val;
  if (val < 0) u.f_temp = - u.f_temp;
  v = u;
  // recupération de l'exposant
  v.li_temp >>= 23;
  exposant = v.li_temp;
  // recuperation mantisse
  if (exposant < 129) {
    mantisse = (u.li_temp & 0X007FFFFF);
    // mise à 1 du bit manquant
    result |= (1 << (exposant-114));  // (15-129+exposant)); semble OK
    mantisse >>= (137-exposant);      //(22-(14-129+exposant));
    result |= mantisse;
    if (val < 0) return -result; 
    else return result;
  } else {
    //**** "Erreur conversion"*****
    return 0;
  }
}

Cette première routine ne contient pas de vérification d'erreur tandis que la deuxième affiche une erreur mais retourne quand même un nombre. Le format "float" du c étant plus précis que notre format Q3.13, cette routine peut échouer. Elle reste cependant utile dans le cadre de CORDIC.

Tests des deux routines précédentes avec un Arduino[modifier | modifier le wikicode]

Pour tester le bon fonctionnement des transformations de formats, rien de tel qu'un programme qui transforme dans les deux sens pour constater si oui ou non on retrouve le même résultat. Voici donc un exemple sous Arduino.

Un peu de théorie sur CORDIC[modifier | modifier le wikicode]

Bloc de calcul CORDIC

Dans cette section, nous allons détailler l'algorithme CORDIC. Nous présentons un schéma simplifié de principe de calcul où vous voyez apparaître trois entrées et trois sorties . Ce schéma est simplifié dans le sens où l’on a omis l'horloge en entrée (il faut bien une horloge pour faire avancer un calcul).

Les données à gauche représentent l'initialisation de l'algorithme. La donnée essentielle est qui représente un angle qui pour nous sera exprimé en radians. Les autres données seront prises comme et dans un premier temps pour expliquer l'algorithme.

Les sorties à droites représenteront le sinus et le cosinus ainsi que l'erreur réalisée sur l'angle.

Qu'y a-t-il dans le bloc ? Un ensemble de trois équations de récurrences que nous allons examiner maintenant.

Des équations de récurrences simples[modifier | modifier le wikicode]

Début des itérations CORDIC

Nous avons au départ trois équations de récurrences simples :

avec .

On expliquera plus tard les relations

et (constantes prédéfinies).

Ce que font ces trois équations est représenté sur la figure ci-contre où les variables ont été remplacées par une notation plus conventionnelle pour des angles. Nous allons expliciter cette figure maintenant.

Dans cette figure vous voyez apparaître un ensemble de rotations qui aboutissent à l'angle dont on cherche le sinus et le cosinus (vecteur rouge de la figure). Vous avez certainement remarqué que les rotations ne sont pas des vraies rotations (qui conservent les longueur) puisqu'elles sont systématiquement associées à une dilatation. La dilatation dépend de l'angle mais :

Ce qui n’apparaît pas sur la figure est que les angles sont déterminés à l'avance (on reviendra sur cette propriété plus tard).

Ces trois propriétés justifient la méthode CORDIC. Mais regardons d'un peu de plus près les équations de récurrence et donnons-en quelques caractéristiques à travers des remarques.


Maintenant que tous les lecteurs ont entraperçu une relation entre CORDIC et les rotations, nous allons examiner cela de manière un peu plus formelle.

Relation avec les rotations[modifier | modifier le wikicode]

Cette partie s'inspire un peu d'un sugjet d'agrégation Génie électrique (2006) : sujets agrégation. Les sujets d'agrégation ne sont pas soumis au copyright. De toute façon ce sujet d'agrégation a été fortement remanié pour le rendre plus accessible. Il en résulte un ensemble de questions avec ses solutions.

Écriture matricielle de CORDIC[modifier | modifier le wikicode]

Écrire les deux premières équations sous la forme matricielle en calculant la matrice Ci :

avec et . (On note donc tout simplement l'entrée et la sortie sous forme de deux composantes vectorielles pour pouvoir introduire cette matrice).

Comment introduire les matrices de rotation[modifier | modifier le wikicode]

La figure montre clairement un ensemble de rotations. Rappelons que les rotations dans un plan sont décrites par des matrices de rotation rappelées ci-après : (rotation d'angle α)

Cette matrice fait tourner le plan d'un angle α.

Elle peut être généralisée sous la forme indicée :

où le paramètre pour décrire le sens de rotation ( rotation dans le sens trigonométrique).

L'idée qui vient à l'esprit est donc de tenter d'écrire la matrice de la section précédente à l'aide d'une matrice de rotation

Écrire la matrice sous la forme en prenant soin d'expliciter et finalement .

Arrivé à ce point, nous espérons que le lecteur a compris (ou au moins entrevu) la relation entre les équations de récurrences CORDIC et les rotations. Rappelons que l’on cherche à calculer un cosinus et un sinus. Il reste cependant des détails à régler pour faire fonctionner CORDIC.

Calculer les équations de récurrences[modifier | modifier le wikicode]

Soit la valeur initiale de , exprimer en fonction de , , , ... puis en fonction de , , , , ...

Il est temps de travailler sur la troisième équation de récurrence que nous avons laissé tombé jusqu'à présent.

Travail sur les angles[modifier | modifier le wikicode]

Premier détail : nous allons prendre à partir de maintenant . C'est cette subtilité qui fait toute la valeur de l'algorithme CORDIC. Pourquoi ? Parce que ce terme apparaît toujours comme terme multiplicatif dans les équations de récurrences :

et qu'une propriété intéressante d'une multiplication par une puissance de 2 est qu'elle peut être remplacée par un simple décalage. Autrement dit choisir va permettre d'économiser des multiplications (qui est un opérateur arithmétique considéré comme complexe, lent et cher).


Calculer pour i=0, 1, 2, ..., 13 si, comme on le rappelle, (question précédente).

Réponse : On donne les valeurs précalculées :

i αi = tan−1 (2−i)
Degrees Radians
0 45.00 0.7854
1 26.57 0.4636
2 14.04 0.2450
3 7.13 0.1244
4 3.58 0.0624
5 1.79 0.0312
6 0.90 0.0160
7 0.45 0.0080
8 0.2238 0.0039
9 0.1119 0.0019
10 0.05595 0.00098
11 0.02798 0.00049
12 0.01399 0.00024
13 0.00699 0.00012

Deuxième détail : nous avons laissé de côté qui est un signe + ou -. Il est grand temps de voir comment il est calculé. C'est tout simplement le signe de l'angle calculé : . Ce signe est connu (puisque l'est) lors du calcul. Le calcul précédent peut être réalisé tel quel dans du matériel (qui peut calculer en parallèle).


Le problème du gain[modifier | modifier le wikicode]

Depuis le début de ce chapitre nous savons qu'un problème de gain était à prendre en compte. En effet, nous avons montré très tôt que l'algorithme réalisait en fait une rotation mais multiplié par . Pour avoir un cosinus et un sinus il nous faudra donc calculer et multiplier le résultat final par cette valeur.

On peut éviter cependant cette multiplication si au lieu d'initialiser à 1, on réalise : .

Les valeurs numériques correspondantes sont facilement évaluées avec un tableur ( d'inverse 0,60725).

Voila. Maintenant tous les détails de calculs sont en place. Pour mettre cela en œuvre dans un premier temps, nous allons utiliser un tableur et regarder CORDIC fonctionner puis nous ferons la même chose en langage C pur.

Utiliser un tableur pour faire fonctionner CORDIC[modifier | modifier le wikicode]

Nous nous proposons dans cette section d’utiliser le tableur LibreOffice pour examiner comment fonctionne CORDIC. Nous pensons, même si nous n'avons pas essayé, que EXEL utiliserait les mêmes primitives.

Nous allons décomposer le travail en deux parties.

Faire fonctionner la troisième équation de récurrence[modifier | modifier le wikicode]

La troisième équation de récurrence est un calcul d'angle en fonction de . Comme nous l'avons déjà affirmé, cette équation peut fonctionner seule. Voici comment on peut procéder avec un tableur (pour lequel les colonnes sont des lettres et les lignes des chiffres, format par défaut de LibreOffice):

A B C D E F
1 i delta_i alpha_i K_i z_i sigma_i
2 0 =PUISSANCE(2;-A2) =ATAN(B2) =1/COS(C2) =PI()/3 =SI(E2<0;-1;1)
3 1 =PUISSANCE(2;-A3) =ATAN(B3) =1/COS(C3) =E2-C2*F2 =SI(E3<0;-1;1)

que l’on peut étendre vers le bas.

Le point essentiel du tableau est la case E2 (qui contient =PI()/3) qui est l'angle duquel on cherche le sinus et le cosinus. C'est la seule case à changer pour faire le calcul sur un autre angle.

L'intérêt d’utiliser un tableur est de voir comment varie cette variable z_i avec les itérations : elle converge toujours vers 0 !

Voici le résultat complet :

CORDIC : équation des angles

Ce graphe montre une convergence vers 0 qu’il n’est pas inutile de retenir pour comprendre les différentes utilisations de CORDIC évoquées plus loin.

Faire fonctionner l'ensemble[modifier | modifier le wikicode]

On complète le tableau par les deux colonnes représentant les deux équations manquantes (colonnes G et H) :

A B C D E F G H I
1 i delta_i alpha_i K_i z_i sigma_i x_i y_i angle_i
2 0 =PUISSANCE(2;-A2) =ATAN(B2) =1/COS(C2) =PI()/3 =SI(E2<0;-1;1) 0,6073 0 0
3 1 =PUISSANCE(2;-A3) =ATAN(B3) =1/COS(C3) =E2-C2*F2 =SI(E3<0;-1;1) =G2-F2*H2*B2 = H2+G2*F2*B2 =I2+F2*C2

On a ajouté pour information une colonne à droite qui calcule la somme des rotations pour montrer qu'elle converge bien vers l'angle souhaité.

Voici le résultat complet :

CORDIC complet

Encore une fois, seule la case E2 est à changer pour réaliser un autre calcul.

Utiliser et adapter l'algorithme de Wikipédia[modifier | modifier le wikicode]

L'article CORDIC dans wikipédia propose un algorithme en C (enfin proposait : voir remarque ci-dessous). Prenez-le avec un copier coller et à l'aide d'un éditeur faites-en un fichier que l’on peut appeler "cordicWiki.c" par exemple. Sa compilation sous Linux ainsi que son exécution peut se faire par :

gcc -o cordic cordicWiki.c -lm 
./cordic
 Veuillez entrer beta 
0.785 
Veuillez entrer le nombre d'iterations voulues 
16 
cos(beta) = 0.707431 , sin(beta) = 0.706892 

L'utilisation en cours de wikipédia nous amène à faire la remarque suivante :

Le fonctionnement de cet algorithme semble parfait. Pourtant, nous allons essayer de l'améliorer pour un fonctionnement dans une architecture bien plus petite qu'un PC. En effet, compilé tel quel avec le compilateur avr-gcc, il faut plus de 8 ko de mémoire, ce qui n’est pas toujours possible pour certains processeurs (ATMega8 et ATTiny861) que nous utilisons dans ce cours.

Analyse des ressources calculs nécessaires[modifier | modifier le wikicode]

Une lecture de ce programme montre qu’il utilise le type "double" qui est le type flottant sur 64 bits. C'est un type peu adapté aux architectures 8 bits que nous désirons cibler.

Ce programme fonctionne avec les librairies de calcul en double (librairie mathématique qu'utilisent pow(2,-i) et atan(Pow2)) et nous désirons à tout prix l'éviter.

Simplifier le programme[modifier | modifier le wikicode]

La technique habituelle pour faire cette simplification est de choisir un format virgule fixe en lieu et place des variables de type "double". Nous allons utiliser le format Q3.13 qui veut dire que trois bits de poids forts sont la partie entière et les treize bits restants sont la partie fractionnaire.

D'autre part les multiplications par pow(2,-i) (soit avec des notations plus habituelles ) sont remplacées par de simples décalages comme cela a déjà été évoqué.

Enfin le calcul atan(Pow2) (soit avec des notations plus habituelles ) sera remplacé par un tableau de valeurs pré-calculées.

Ce travail a déjà été fait dans ICI (dans un autre livre) où vous avez un programme complet sans aucune multiplication.

Problème d'arrondi[modifier | modifier le wikicode]

Sans entrer dans les détails, notons que cet algorithme peut être amélioré. Toute représentation des nombres présente des imperfections. Ici, supposons que l’on ait 0xFFFF en format Q3.13. Un décalage vers la droite le transformerait en 0xFFFF alors qu’il faudrait le transformer en 0x0000 !

Voir aussi[modifier | modifier le wikicode]


Après avoir examiné CORDIC d'une manière logicielle, nous allons nous intéresser maintenant à sa réalisation matérielle. Autre manière de dire les choses, le calcul devra donc être réalisé par une partie matérielle adaptée.

Implantation matérielle de l'algorithme CORDIC[modifier | modifier le wikicode]

Il y a typiquement deux façons de réaliser un coprocesseur CORDIC :

  • utilisation d'un pipeline
  • utilisation d'un séquenceur

En effet, un algorithme récursif représente une boucle et il y a deux moyens pour la réaliser : la séquencer (avec un compteur) comme on le ferait en programmation, ou la développer.

Nous allons présenter les deux façons maintenant.

Réalisation avec pipeline[modifier | modifier le wikicode]

La réalisation avec pipeline se fait de la manière suivante :

Pipeline complet pour calcul CODIC
Panneau d’avertissement Dans cette figure le signe se propage sur les trois additionneur soustracteur de l'étage !

Nous avons réalisé ce cœur sans utiliser les boucles du VHDL ce qui allonge un peu le code de ce coprocesseur CORDIC, c’est pourquoi nous le mettons dans une boite déroulante.

Ce code n'a pas été développé avec une boucle VHDL pour des raisons d'optimisation.

Passons maintenant à la version séquentielle de ce même coprocesseur.

Réalisation séquentielle[modifier | modifier le wikicode]

Gilles Millon, Maître de conférences à l’IUT de Troyes, a fait une modification du cœur précédent pour qu’il fasse le même calcul mais de manière séquentielle. Nous allons en présenter son schéma de principe (et non son code complet) car il est encore utilisé en enseignement. Son principe est décrit dans la figure ci-contre.

Calcul CORDIC séquentiel

Augmenter l'intervalle de calcul des angles[modifier | modifier le wikicode]

Gilles Millon a profité du passage du mode pipeline au mode séquentiel pour réaliser un coprocesseur CORDIC capable de traiter des angles de à au lieu de à . Ceci peut être fait avec le code VHDL suivant :

	-- pretraitement angle
	process(angle) begin
		if ( angle>=zero and angle< ppi_2) then 	-- 	0<angle<pi/2
			s_angle <= angle;
			coeffx <= '1'; -- +1
			coeffy <= '1'; -- +1
		elsif ( angle>ppi_2 and angle<ppi) then 	-- 	pi/2<angle<pi
			s_angle <= ppi - angle ;
			coeffx <= '0'; -- -1
			coeffy <= '1'; -- +1
		elsif ( angle>=mpi_2 and angle<=x"FFFF") then 	-- 	-pi/2<angle<0
			s_angle <= angle;
			coeffx <= '1'; -- +1
			coeffy <= '0'; -- -1
		elsif ( angle>=mpi and angle<=mpi_2) then 	-- 	-pi<angle<-pi/2
			s_angle <= ppi - ( not(angle) +1 ) ;
			coeffx <= '0'; -- -1
			coeffy <= '0'; -- -1
		else
			s_angle <= angle;
			coeffx <= '1';
			coeffy <= '1';
		end if;
	end process;

où vous voyez une mémorisation dans coeffx et coeffy du quadrant concerné.

Version presque complète du coprocesseur CORDIC séquentiel[modifier | modifier le wikicode]

Schéma de principe d'un coprocesseur CORDIC séquentiel

Nous présentons maintenant la version presque complète du processeur CORDIC séquentiel. Ce qui manque a été demandé plusieurs fois à des étudiants :

et sera certainement demandé encore (d'où sa suppression). Il s'agit du séquenceur de trois états que nous allons décrire maintenant et que vous pouvez trouver après les commentaire "--TODO" dans le code un peu plus loin.

Voici de manière schématique ci-contre,l'ensemble à réaliser. Portez votre attention surtout sur le séquenceur, c’est lui qu’il faudra ajouter au code VHDL.

Et voici le code correspondant sans le séquenceur :

Toutes les précédentes présentations de CORDIC ne sont pas faciles à tester sans processeur. Nous allons nous intéresser maintenant à la réalisation d'une interface avec un processeur. Bien sûr les processeurs déjà utilisés dans ce cours auront notre préférence.

Transformer notre coprocesseur CORDIC en périphérique[modifier | modifier le wikicode]

Nous allons nous intéresser maintenant à l’utilisation du coprocesseur CORDIC par un processeur. Cela consiste donc à le transformer en périphérique.

Un périphérique pour l'ATMega[modifier | modifier le wikicode]

Coprocesseur CORDIC comme périphérique

Le processeur que nous avons utilisé le plus dans ce livre étant l'ATMega, nous allons nous intéresser à réaliser ce périphérique pour ce processeur. Comme nous l'avons déjà présenté dans Embarquer un Atmel ATMega8 et plus en détail dans Améliorer l'ATMega8 avec l'ATMega16 et l'ATMega32 nous allons reprendre la terminologie graphique correspondante. Rappelons donc que tout se passe dans un fichier appelé "io.vhd" dans lequel deux process sont présents :

  • un pour l'écriture dans les PORTs/Registres : IOwr
  • un pour la lecture des PORTs/registres : Iord

Si vous partez du coprocesseur CORDIC, vous voyez que son entrée "Ain(15:0)" est réalisée à l'aide de deux PORTs (PORTB et PORTA), que son entrée "Ena" est réalisée à l'aide d'un bit du PORTD.

Les sorties de ce coprocesseur deviennent PINA et PINB pour le sinus et PINC et PIND pour le cosinus.

Voici comment tout ceci est réalisé :

Une remarque pour terminer.


Le contenu de cette remarque sera pris en compte lors des exercices complémentaires.

Quelques utilitaires pour tester[modifier | modifier le wikicode]

Le coprocesseur CORDIC fournit un calcul à l'ATMega et c’est ce dernier qui est chargé de le donner à l'extérieur pour tester. Le meilleurs moyen de réaliser tout cela est d’utiliser la liaison série. On entre l'angle sur lequel on veut faire le calcul dans un hyperterminal, le calcul se fait et le résultat s'affiche sur l'écran de l'hyperterminal. Mais pour faire cela il faut transformer la chaîne fournie par l'hyperterminal en format Q3.13 et inversement, le résultat Q3.13 devra être converti en chaîne de caractères avant d’être envoyé. Pour faciliter ces conversions, nous proposons quelques utilitaires regroupés ci-dessous :

Si ces utilitaires ne fonctionnent pas cela peut être dû à un problème dans la vitesse de transmission. Toutes ces routines sont commentées pour 38400 bauds mais peuvent fonctionner à des vitesses doubles ou moitié selon votre horloge système !

Un programme principal pour tester[modifier | modifier le wikicode]

On donne un exemple partiel de programme principal pour tester :

do {
      nbOK=0;
     // on boucle tant que la syntaxe n’est pas bonne
      do {
        usart_puts("Entrez un nombre au format +x.xxxx ou -x.xxxx");
        usart_send(0X0D);usart_send(0X0A);
        usart_gets(chaine);
        nbOK=check_syntaxe(chaine);
        if (!nbOK) {
          usart_puts("!!!! Mauvais nombre !!!!");
          usart_send(0X0D);usart_send(0X0A);
        }
      } while(!nbOK);
// verification visuelle de saisie correcte :
      beta = StringToQ3_13(chaine);
      usart_puts("beta=");
      HexQ3_13ToString(beta,chaine);
      usart_puts(chaine);
      usart_send(0X0D);usart_send(0X0A);
// fin verification visuelle
      //    saisie de l'angle dans les deux PORTs
      PORTB = beta; //
      PORTC = beta>>8; 
      PORTD = 1; // start
  // attente obligatoire du calcul :
      _delay_ms(50);
      x = PINB;
      x <<=8; // poussé dans poids forts
      x += PINA;
      y = PIND;
      y <<= 8; // poussé dans poids forts
      y += PINC;
  // Affichage du résultat
      HexQ3_13ToString(x,chaine);
      usart_puts(chaine);
      usart_send('=');usart_puts_hexa(x);
      usart_send(' ');usart_send(' ');usart_send(' ');
      HexQ3_13ToString(y,chaine);
      usart_puts(chaine);usart_send('=');usart_puts_hexa(y);
      usart_send(0x0D);usart_send(0x0A);
      _delay_ms(500);
    } while(1);

Nous allons proposer quelques exercices matériels pour ceux qui veulent aller plus loin.

Quelques idées pour des exercices complémentaires[modifier | modifier le wikicode]

Nous allons présenter dans cette section un ensemble d'exercices pour aller plus loin avec CORDIC sur une petite architecture 8 bits. Certains de ces exercices ont été réalisés mais pas d'autres. Nous les laissons pour les étudiants ou enseignants qui désirent aller plus loin.

Transformer le cœur pipeline en périphérique[modifier | modifier le wikicode]

Le cœur pipeline du CORDIC que nous avons donné plus haut est assez mal adapté à la notion de périphérique. Il est en effet trop indépendant du processeur. Traditionnellement les périphériques sont configurables par des registres, et un drapeau indique la fin du travail. Ce bit peut d'ailleurs, en général, être utilisé pour déclencher une interruption...

Un pipeline est, quant à lui, destiné à traiter des informations au fur et à mesure. D'une certaine manière, il ne termine jamais son travail. Notre problème va donc consister à le transformer en un périphérique digne de ce nom.

Ajouter un fonctionnement correct de l'entrée "ena"[modifier | modifier le wikicode]

L'entrée "ena" présente dans l'entité du cœur CORDIC ne sert absolument à rien. Vous allez transformer le fichier "cordic2.vhd" pour la rendre utile : s'il elle n’est pas à '1' le cœur ne calcule pas. Fonctionnement assez traditionnelle pour ce type d'entrée.

L'utilisation d'un tel cœur consistera alors à :

  • positionner l'angle en écrivant dans deux PORTs
  • positionner "ena" à 1 pour lancer le calcul.
  • perdre un peu de temps et repositionner "ena" à 0
  • lire les sinus et cosinus

Ce qui nous déplait dans cette façon de faire est l'attente par perte de temps. À ce stade, il n'y a pas grand chose d'amélioré par rapport au cœur d'origine, sauf la possibilité de l'arrêter. Nous allons améliorer cela mais nous vous conseillons de réaliser cette étape et de la tester.

Ajouter une détection de la fin de calcul[modifier | modifier le wikicode]

Un bit de sortie sera prévu pour détecter la terminaison du calcul. Ce travail n’est pas difficile à faire. Il s'agit d'ajouter un compteur dans CORDIC sur 4 bits qui s'incrémente aussi avec "ena" (et l'horloge bien sûr). Quand le compteur est à une certaine valeur (14 pour nous) et bien on positionne un bit (appelé "done") à 1 (et l’on pourrait automatiquement positionner "ena" à 0 mais cette option ne sera pas choisie).

L'utilisation d'un tel cœur consistera alors à :

  • positionner l'angle en écrivant dans deux PORTs
  • positionner "ena" à 1 pour lancer le calcul.
  • Attendre le positionnement du bit "done" (de fin de calcul) et repositionner "ena" à 0 (avec le processeur)
  • lire les sinus et cosinus


Et voici donc une correction partielle correspondant aux deux versions améliorées proposées ci-dessus :

  • Ajouter un fonctionnement correct de l'entrée "ena"
  • Ajouter une détection de la fin de calcul

Réalisation matérielle de la conversion virgule fixe vers virgule flottante[modifier | modifier le wikicode]

Cette conversion était l'objectif de la fonction donnée et déjà utilisée dans un exercice précédent :

float HexQ3_13ToFloat(int val)

Un coup d'œil sur le code source de cette fonction montre des calculs de puissance de deux en flottant et notre objectif ici est de les éliminer en laissant le matériel les réaliser. Pour ce faire, il est possible d’utiliser un cœur de calcul flottant, il en existe chez Opencores.org. Mais on va être plus subtil car notre conversion se fait dans un cas suffisamment simple et nous allons tenter une réalisation sans multiplication.

1°) Tester en C une conversion du type : Exposant = 129

Recherche du premier 1 dans le nombre Q3.13 en partant des poids forts et en décrémentant l'exposant.

Une fois trouvé supprimer ce 1, puis mettre l'exposant à sa place (E dans la figure ci-dessous) et mettre la mantisse (dans M) aussi à sa place.

On rappelle la documentation des nombres flottants :

Format général de représentation des flottants
Format général de représentation des flottants
Encodage Signe Exposant Mantisse Valeur d'un nombre Précision Chiffres significatifs
Simple précision 32 bits 1 bit 8 bits 23 bits 24 bits environ 7
Double précision 64 bits 1 bit 11 bits 52 bits 53 bits environ 16

Voici comment les choses se font sous Linux/Windows (en format simple précision) : on remarquera l'absence de multiplication et de calcul flottant :

// Serge Moutou avril 2013 version 0.9
// ************ Mai 2014 version 1.0 : remplacement pointeur par union
//** Ne peut pas fonctionner avec avr-gcc pour lequel les tailles
//** float (32 bits) et int (16 bits) ne correspondent pas !
//** Sous Linux/Windows les tailles sont toutes les deux 32 bits
float HexQ3_13ToFloat2(int val){
   union {
     float temp;
     int f_temp;
  } u;
  int i_temp;
  unsigned char exposant=129;//,*p;
  signed char i;
  if (val < 0) i_temp = -val; else i_temp = val;
  for (i=15;i>=0;i--) {
    if (i_temp & (1<<i)) { 
    // on efface le '1' trouvé :
      i_temp= i_temp & ~(1<<i);
      break;// on sort de la boucle
    }
    exposant--;   
  }
  u.f_temp = exposant; 
  u.f_temp <<=23; 
  u.f_temp = u.f_temp|(i_temp << (23-i));
  if (val < 0) return -(u.temp); else return u.temp;
}

2°) On va réaliser la conversion ci-dessus dans le matériel (en VHDL donc). En clair, notre cœur CORDIC va continuer à travailler en virgule fixe, mais le résultat sera converti en flottant par le matériel puis retourné au processeur.

Pour éviter de multiplier les PORTs de l'AVR, on va utiliser un FIFO dans lequel on viendra ranger les 8 octets correspondants aux deux nombres flottant du résultat.

Trouver une machine d'états qui fait le calcul de conversion de la question 1 et remplit un FIFO avec les 8 octets des deux résultats de CORDIC.

Conversion du résultat en chaîne de caractères de manière matérielle[modifier | modifier le wikicode]

Nous nous proposons maintenant de réaliser une conversion en chaîne de caractères des résultats en vue d'un affichage dans l'hyperterminal comme dans l'exercice qui utilisait "HexQ3_13ToString". Notre résultat devra avoir le format :

signe digit1 '.' digit2 digit3 digit4

c'est-à-dire 6 caractères (7 en ajoutant le zéro de fin de chaîne) et ceci pour le sinus et le cosinus. Pour éviter d’avoir un nombre de PORTs trop important, vous allez utiliser un FIFO comme dans l'exercice précédent.

Remplacer CORDIC par des valeurs pré-calculées en mémoire[modifier | modifier le wikicode]

Avant toute discussion, rappelons que le calcul CORDIC nécessite des valeurs pré-calculées donc de la mémoire. Calculons la taille mémoire que l’on a utilisé dans notre implantation.

Les mémoires peuvent mémoriser des valeurs prédéterminées.

Mémoire pour notre cœur CORDIC[modifier | modifier le wikicode]

Le cœur CORDIC déjà présenté nécessitait de la mémoire : il devait mémoriser les valeurs de . Mais cela représente une très petite taille car i varie de 0 à 13 (ce n’est pas la peine d'aller au-delà pour le format Q3.13). Cela fait donc 14 valeurs en format Q3.13 soit 14x16 bits = 28 octets. Trouver cela dans un FPGA ne pose aucune difficulté !

Bien sûr si l’on augmente la précision il faudra plus de mémoire mais la croissance est linéaire en i.

Mémoire pour éviter les calculs[modifier | modifier le wikicode]

Si l’on désire concurrencer CORDIC par une mémoire vous avez deux solutions :

  • on mémorise toutes les possibilités sur les angles en format Q3.13
  • on mémorise quelques valeurs et si l’on tombe en dehors on fait une interpolation linéaire.

Calculons la taille de la mémoire pour le premier cas qui est le plus défavorable. Il est facile de voir que l'angle varie entre les valeurs hexadécimales . Cela fait 12868 cases mémoires pour la partie positive si l’on s'en tient à mémoriser cette seule partie. Chacune des cases étant de deux octets on voit qu’il faut 25 736 octets soit environ 32 ko.

Généralisation de CORDIC[modifier | modifier le wikicode]

En introduisant un facteur μ, on peut généraliser au cas linéaire et aux fonctions hyperboliques:



Résumé pour CORDIC universel[modifier | modifier le wikicode]



Mode Rotation Vectoriel
Circulaire

μ = 1
αi = tan−12−i

Linéaire

μ = 0
αi = 2−i

Hyperbolique

μ = -1
αi = tanh−12−i

  • En mode hyperbolique, les iterations 4, 13, 40, 121, ..., j, 3j+1,... doivent être répétées. La constante K' donnée ci-dessous prend cela en compte.
  • K = 1.646760258121...
  • 1/K = 0.607252935009...
  • K' = 0.8281593609602...
  • 1/K' = 1.207497067763...

Exercice[modifier | modifier le wikicode]

Pour comprendre les dessins ci-dessus et négliger les détails de l'implémentation (matérielle ou logicielle), on vous demande de prendre le mode circulaire, d'initialiser x à 1/K et y à 0 (les entrées sont à gauche) et de dire ce qui sortira du coprocesseur CORDIC.

Étude d'un cœur CORDIC généralisé[modifier | modifier le wikicode]

Nous avons trouvé chez Opengores.org cœur CORDIC de Richard Herveille fonctionnant en mode rotation et en mode vectorisé. Nous allons l'étudier brièvement maintenant.

Un coprocesseur qui réalise un programme[modifier | modifier le wikicode]

Dans cette section nous allons nous intéresser au cœur CORDIC généralisé de la section précédente et le transformer en une entité possédant suffisamment d'instructions pour pouvoir réaliser l'un des calculs CORDIC généralisé. D'une certaine manière notre coprocesseur deviendra donc un processeur avec une UAL un peu spéciale, un compteur programme, une mémoire programme et données.

Généralité sur l'interfaçage d'un coprocesseur[modifier | modifier le wikicode]

Interfaçage avec des PORTs[modifier | modifier le wikicode]

Interfaçage avec des mémoires[modifier | modifier le wikicode]

Voir aussi[modifier | modifier le wikicode]

Liens internes[modifier | modifier le wikicode]

Challenges[modifier | modifier le wikicode]

Articles[modifier | modifier le wikicode]

Code C pour démarrer l'arithmétique virgule flottante[modifier | modifier le wikicode]

Panneau d’avertissement Le premier lien (Mike Field) ci-dessous n'est plus disponible et c'est bien dommage !

Custom flotaing point (Mike Field) nous a servi de point de départ dans un autre chapitre. Nous y présentons un code fonctionnel pour l'addition en nombre flottant en C (sans la librairie standard de calcul flottant).

Livres[modifier | modifier le wikicode]

  • Patrick R. Schaumont "A Practical Introduction to Hardware Software Codesign" Springer (2010). Le chapitre 12 est consacré à CORDIC
  • Reconfigurable Computing: The Theory and Practice of FPGA-Based Computation édité par Hauck, Scott et DeHon, Andre (2010). Le chapitre 25 aborde les architectures CORDIC