Analytical accuracy evaluation of fixed-point systems for digital communication applications
Evaluation analytique de la précision des systèmes en virgule fixe pour des applications de communication numérique
Résumé
In designing applications of signal processing, the traditional approach leads the designer of appli- cations to use initially floating point arithmetic in order to avoid problems related to the accuracy of calculations. However, the implementation of these applications requires the use of fixed-point arithmetic because it is more advantageous in terms of constraints of cost and consumption. Therefore, the designed application in floating point arithmetic must be converted to fixed-point arithmetic. This conversion is tedious, so tools for automatic conversion of floating-point arithmetic to the fixed point were established to meet the requirements of time-to-market of these applications. In this conversion process, one of the basic steps concerns the evaluation of the accuracy of the fixed-point specification. Indeed, the change of the data format of the application is performed by removing bits. This conversion results in the generation of quantization noise propagating within the system and degrading the accuracy of calculations of the application output. Therefore, this reduction in the calculation accuracy must be mastered and evaluated in order to ensure the integrity of the algorithm and meet the initial requirements of the application. Traditionally, evaluation of accuracy is performed through two different approaches. The first approach is to perform simulations fixed-point implementation in order to assess its performance. These approaches based on simulation require large computing capacities and lead to prohibitive time evaluation. To avoid this problem, the work done in this thesis focuses on approaches based on the accuracy evaluation through analytical models. These models describe the behavior of the system through analytical expressions that evaluate a defined metric of precision. Several analytical models have been proposed to evaluate the fixed- point accuracy of Linear Time Invariant systems (LTI) and of non-LTI non-recursive and recursive linear systems. The objective of this thesis is to propose analytical models to evaluate the accuracy of digital communications systems and algorithms of digital signal processing made up of non-smooth and non-linear operators in terms of noise. In a first step, analytical models for evaluation of the accuracy of decision operators and their iterations and cascades are provided. In a second step, an optimization of the data length is given for fixed-point hardware implementation of the Decision Feedback Equalizer DFE based on analytical models proposed and for iterative decoding algorithms such as turbo decoding and LDPC decoding-(Low-Density Parity-Check) in a particular quantization law.
The first aspect of this work concerns the proposition analytical models for evaluating the accuracy of the non-smooth decision operators and the cascading of decision operators. So, the characterization of the quantization errors propagation in the cascade of decision operators is the basis of the proposed analytical models. These models are applied in a second step to evaluate the accuracy of the spherical decoding algo- rithm SSFE (Selective Spanning with Fast Enumeration) used for transmission MIMO systems (Multiple- Input Multiple - Output). In a second step, the accuracy evaluation of the iterative structures of decision operators has been the interesting subject. Characterization of quantization errors caused by the use of fixed-point arithmetic is introduced to result in analytical models to evaluate the accuracy of application of digital signal processing including iterative structures of decision. A second approach, based on the estimation of an upper bound of the decision error probability in the convergence mode, is proposed for evaluating the accuracy of these applications in order to reduce the evaluation time. These models are applied to the problem of evaluating the fixed-point specification of the Decision Feedback Equalizer DFE. An extension of these models is introduced for the evaluation of DFE in its adaptive version.
The second aspect of our work focuses on the optimization of fixed-point data widths. This optimi- zation process is based on minimizing the decision error probability through the implementation on an FPGA (Field-Programmable Gate Array) of the complex DFE algorithm under the constraint of a given accuracy. Therefore, for each fixed-point specification, accuracy is evaluated through the proposed analy- tical models. The estimation of resources and power consumption on the FPGA is then obtained using the Xilinx tools to make a proper choice of the data widths aiming to a compromise accuracy/cost.
The last step of our work concerns the fixed-point modeling of iterative decoding algorithms. A model of the turbo decoding algorithm and the LDPC decoding is then given. This approach integrates the particular structure of these algorithms which implies that the calculated quantities in the decoder and the operations are quantified following an iterative approach. Furthermore, the used fixed-point representation is different from the conventional representation using the number of bits accorded to the integer part and the fractional part. The proposed approach is based on the dynamic and the total number of bits. Besides, the dynamic choice causes more flexibility for fixed-point models since it is not limited to only a power of two. In a second step, the memory size reduction using saturation and truncation techniques is given in order to be able to target low - complexity architectures. Finally, the fixed-point performance analysis is done through the evaluation of Frame Error Ratio FER versus SNR (Signal to Noise Ratio) package.
Lors de la conception d’applications de traitement de signal, la démarche classique conduit le concep- teur d’applications à utiliser dans un premier temps une arithmétique en virgule flottante pour éviter les problèmes liés à la précision des calculs. Cependant, l’implémentation de ces applications nécessite l’utili- sation de l’arithmétique virgule fixe puisqu’elle est plus avantageuse en termes de contraintes de coût et de consommation. Par conséquent l’application conçue en arithmétique virgule flottante doit être convertie en arithmétique virgule fixe. Cette opération de conversion se révèle être fastidieuse, aussi des outils de conversion automatique de l’arithmétique virgule flottante vers celle en virgule fixe ont été mis en place afin de répondre aux exigences de temps de mise sur le marché de ces applications. Au sein de ce processus de conversion, l’une des étapes primordiales concerne l’évaluation de la précision de la spécification en virgule fixe. En effet, le changement du format des données de l’application s’effectue en éliminant des bits. Cette conversion conduit à la génération de bruits de quantification qui se propagent au sein du système et dégradent la précision des calculs en sortie de l’application. Par conséquent, cet abaissement dans la précision de calcul doit être maitrisé et évalué pour garantir l’intégrité de l’algorithme et répondre aux spécifications initiales de l’application. Traditionnellement, l’évaluation de la précision s’effectue par le biais de deux approches différentes. La première approche consiste à réaliser des simulations en virgule fixe de l’application afin d’en estimer ses performances. Ces approches basées sur la simulation nécessitent de grandes capacités de calculs et conduisent à des temps d’évaluation prohibitifs. Pour éviter ce problème, le travail mené dans le cadre de cette thèse se concentre sur des approches basées sur l’évaluation de la précision à travers des modèles analytiques. Ces modèles décrivent le comportement du système à travers des expressions analytiques qui permettent d’évaluer une métrique de précision bien définie. Plusieurs mo- dèles analytiques ont été proposés pour évaluer la précision en virgule fixe des systèmes linéaires invariants dans le temps LTI (Linear Time Invariant) et des systèmes linéaires non-LTI non récursifs et récursifs. L’objectif de cette thèse est de proposer des modèles analytiques permettant l’évaluation de la précision des systèmes de communications numériques et des algorithmes de traitement numérique de signal formés d’opérateurs non lisses et non linéaires en terme du bruit. Dans un premier temps, des modèles analytiques pour l’évaluation de la précision des opérateurs de décision et leurs cascades et itérations sont proposés. Dans une seconde étape, une optimisation des largeurs de données est proposée pour l’implémentation matérielle en virgule fixe de l’égaliseur à retour de décision DFE (Decision Feedback Equalizer) en se basant sur les modèles analytiques proposés ainsi que pour les algorithmes de décodage itératif du type turbo-décodage et décodage-LDPC (Low-Density Parity-Check) selon une loi se quantification particulière.
Le premier aspect de ce travail concerne la proposition de modèles analytiques pour l’évaluation de la précision des opérateurs non lisses de décision et de la cascade des opérateurs de décision. Par conséquent, la caractérisation de la propagation des erreurs de quantification dans la cascade d’opérateurs de décision est le fondement des modèles analytiques proposés. Ces modèles sont appliqués dans une seconde étape pour l’évaluation de la précision de l’algorithme de décodage sphérique SSFE (Selective Spanning with Fast Enumeration) utilisé pour les systèmes de transmission de type MIMO (Multiple-Input Multiple-Output). Dans une seconde étape, l’évaluation de la précision des structures itératives d’opérateurs de décision a fait l’objet d’intérêt. Une caractérisation des erreurs de quantification engendrées par l’utilisation de l’arith- métique en virgule fixe est introduite pour aboutir à des modèles analytiques permettant l’évaluation de la précision des applications de traitement numérique de signal incluant des structures itératives de déci- sion. Une deuxième approche, basée sur l’estimation d’une borne supérieure de la probabilité d’erreur de décision dans le mode de convergence, est proposée pour l’évaluation de la précision de ces applications et ceci dans un but de réduire les temps d’évaluation. Ces modèles sont appliqués à la problématique de l’évaluation de la spécification virgule fixe de l’égaliseur à retour de décision DFE. Une extension de ces modèles est introduite pour l’évaluation du DFE dans sa version adaptative.
Le second aspect de notre travail s’articule autour de l’optimisation des largeurs de données en virgule fixe. Ce processus d’optimisation est basé sur la minimisation de la probabilité d’erreur de décision dans le cadre d’une implémentation sur un FPGA (Field-Programmable Gate Array) de l’algorithme DFE com- plexe sous contrainte d’une précision donnée. Par conséquent, pour chaque spécification en virgule fixe, la précision est évaluée à travers les modèles analytiques proposés. L’estimation de la consommation des ressources et de la puissance sur le FPGA est ensuite obtenue à l’aide des outils de Xilinx pour faire un choix adéquat des largeurs des données en visant à un compromis précision/coût.
La dernière étape de notre travail concerne la modélisation en virgule fixe des algorithmes de décodage itératif. Une modélisation de l’algorithme de turbo-décodage et du décodage LDPC est ensuite proposée. Cette approche intègre la structure particulière de ces algorithmes ce qui implique que les quantités calcu- lées au sein du décodeur ainsi que les opérations, sont quantifiées suivant une approche itérative. De plus, la représentation en virgule fixe utilisée est différente de la représentation classique utilisant le nombre de bits accordé à la partie entière et la partie fractionnaire. L’approche proposée repose sur le couple dynamique et le nombre de bits total. De plus le choix de la dynamique engendre davantage de flexibilité pour les modèles en virgule fixe puisqu’elle n’est plus limitée uniquement à une puissance de deux. Dans une seconde étape, la réduction de la taille des mémoires par des techniques de saturation et de troncature est proposée afin d’être en mesure de cibler des architectures à faible-complexité. Finalement, l’analyse des performances en virgule fixe est faite à travers l’évaluation du taux d’erreur par paquet FER (Frame Error Ratio) en fonction du SNR (Signal to Noise Ratio).