Floating-point To Fixed-point Transformation For Digital Signal Processing Systems

Modern digital signal processing (DSP) algorithms are usually developed in?oating-point arithmetic, for fast algorithm verification and system prototyping. Afterthat they can be implemented on ?oating-point devices, such as ?oating-point DSP de-vices from Texas Instruments. Besides, they can be transformed to fixed-point arithmeticto implement on fixed-point devices, such as field-programmable gate arrays (FPGAs)from Xilinx or application-specific integrated circuits (ASICs), which can provide higherspeed, smaller area and low power. The ?oating-point to fixed-point transformation con-sists of two steps: range analysis and precision analysis. Range analysis is to find ade-quate integer wordlengths for signals to prevent their over?ow. Precision analysis is tofind the optimal fractional wordlengths combination for minimum implementation costwhile maintaining the system output accuracy, except for preventing signals'under?ow.Thus, ?oating-point to fixed-point transformation is also often called wordlength opti-mization, which is an NP-hard problem.Based on the detailed discussion of current research status of wordlength optimiza-tion methods, we propose refined and more efficient novel algorithms for range analysisand precision analysis respectively. Moreover, we demonstrate their efficiencies and ad-vantages by applying them to ABS–S (Advanced Broadcast System– Satellite) demodu-lator ASIC design. The main works of this dissertation are listed as following:Firstly, the state-of-the-art range analysis methods are analytical ones based onAffine Arithmetic (AA). AA mainly provides two methods, Chebyshev approximationand trivial range estimation, to approximate nonlinear multiplication results into affineforms. The Chebyshev approximation provides the best approximation result. How-ever, its computation is prohibitive expensive. Although the trivial range estimation oftenlargely overestimates the range result, it is very efficient for computation. In order to takeboth the advantages of accurate Chebyshev approximation and fast trivial range estima-tion, we propose a new approach to let user decide the trade-offs between approximationaccuracy and computational complexity of AA.Secondly, AA needs approximation after every nonlinear multiplication, so there nolonger fully preserves correlations among resulted affine form and former signals. That will gradually magnify all the signal ranges in the following data?ow graph. To overcomethis problem, we propose Refined Affine Arithmetic (RAA), which can directly resultits refined affine forms when performing nonlinear multiplications. These refined affineforms keep full track of the correlations between signals and they can directly take partin the following computations. Compared to AA using trivial range estimation, RAA hascomparable computation efficiency, but it provides much tighter range analysis results.Moreover, RAA results are not affected by various DSP algorithms, which provides morereliable range results than AA does.Thirdly, inspired by that Extreme Value Theory (EVT) has been employed to ana-lyze the ranges of integer variables in embedded systems, we present a novel precisionanalysis approach based on EVT. Compared to traditional simulation-based methods, ituses lightweight simulations to study the characteristics of extreme conditions becauseof fractional wordlengths variations. Besides, it can provide solutions with theoreticalprobabilities to meet the output error constraint.To the best of our knowledge, there is no work has formulated the explicit rela-tionship between output accuracy and implementation cost, because of wordlength as-signment. That's why the existing methods are inefficient on fractional wordlength opti-mization. A novel quantization error propagations model, Quantization-Operation-Error(QOE), is proposed in this dissertation to address this problem. Based on QOE, a greedysearch algorithm is developed to find the minimum hardware cost solution while meetingan output error constraint. The greedy search can not only find an accuracy-guaranteedsolution very quickly, but also provide a near Pareto-optimal front, which gives design-ers the opportunity to make trade-offs between output accuracy and implementation cost,including area, power, speed and etc.Besides, based on the research of accuracy-guaranteed fractional wordlength opti-mization, we study the possibility of further saving power of DSP systems. A powerreduction technique is proposed to dynamically reduce the switching activities in multi-pliers, without sacrificing required accuracy at output.Finally, taking the advantages of our research on wordlength optimization, we ap-ply the proposed techniques to optimize the key modules in ABS–S demodulator ASICdesign. Compared to the industrial simulation-based method, efficient wordlength op-timization techniques can provide similar implementation solutions, however they can greatly shorten the DSP system design cycle. The most important is that these solutionscan guarantee or provide high theoretical probabilities to prevent signal over?ow and meetoutput error constraint.