article
prepared by P. Bakowski
Content: introduction, methodology, application, static analysis, simulation, implementation: VHDL code, netlist, Xilinx report, conclusion
Abstract
This paper presents a complete flow of Computer Aided Design process starting from functional level description and ending at circuit level. The main interest of this study is to show the possibility to rapidly implement a DSP algorithm in a specific circuit by using high-level synthesis techniques. The implementation of a multisensor receiver for DS-CDMA applications is reported to show the effectiveness of the method and of the developed tool.
Nowadays, the design of effective electronic circuits cannot be realized without CAD tools based on the specification, the transformations and the synthesis.
Techniques of high-level synthesis [1] allow the designer to obtain the architecture of a circuit from its specifications. High-level specifications facilitate the description and the validation of the algorithm and reduce the design time. These different techniques are essential to design specific circuits and make the maintenance as well as the evolution of the product easier.
In most applications, DSP algorithms require high performances. Then, it is imperative to implement them on specific circuits. These technological supports allow the designer to reach the demanded performances, such as the cost of the final circuit, the processing speed and the consumption power.
We have developed a tool allowing the high-level synthesis of the algorithms for digital signal processing while respecting time or cost constraints[2] [3]. In the first step, the algorithm is described at a functional level. The functional specification corresponds to a schematic description of the system. It is achieved by interconnecting functional blocks. This definition is obtained with the SPW tool of the Alta Group company by using the HDS (Hardware Design System) library.
The generated architecture is described in VHDL language. The techniques of high-level synthesis such as the scheduling and the allocation of resources permit to confirm the trade-off cost/performances required. Sharing resources techniques are essential when the number of operations to be execute in an algorithm increases. Indeed, the characteristics of the circuit depend on the number of available functional units.
In this class of design methodology, the main problem is to determine the best trade-off between the cost (silicon area) and the allowed sampling frequency (speed). The estimation of the implementation requirements permits to limit the design space and thus to reduce the development time [4] [5]. An additional transformation, the retiming [6], optimizes of the resources utilization by adding or shifting delay blocks onto the critical path. This transformation preserves the functionality of the algorithm. A particular case is the pipeline. This phase consists in associating a delay with each functional block output. This transformation significantly increases the rate of processing while introducing an additional latency time. On the other hand, it generates an increase of the required silicon area.
The design tool developed at the laboratory allows fast implementation of DSP algorithms on specific circuits (ASIC and FPGA).
Figure 1 represents the design flow used for the synthesis of an application firstly described at an algorithmic level. The aim is to get a specific circuit such as an FPGA or an ASIC. The dark zone represents the tool developed at our laboratory.
Six main steps can be distinguished:
1) The algorithm is detailed in a schematic form by interconnecting available functional blocks in the SPW-HDS library, then simulated with the same tool. Moreover this tool generates a SPW netlist [7], which is a textual description of the schematic.
2) The netlist is translated into a data control flow graph (CDFG). Each elementary block is translated into a node and each connection into an edge.
3) This graph is submitted to an optimization phase in order to restructure the graph and get the best trade-off cost/performances.
4) Once the optimized graph and the number of resources have been fixed, the operations, contained in the graph, are scheduled [3]. Then the allocation of resources is executed according to constraints imposed by the user via the optimization phase.
5) This graph is translated into synthesizable VHDL. This code is composed of three distinct parts: functional blocks, the controller and the top component.
6) The COMPASS tool undertakes the logical synthesis. This step corresponds to the translation of the VHDL code in a usable format for the tools achieving the placement and routing according to the target technology (COMPASS for an ASIC technology or XACT for a solution on FPGAs).
The design of the multisensor terminal for digital mobile radio communications is presented in fhe figure below.
The algorithm is composed of five distinct parts. As it must be implemented using FPGA technology, a partitioning is obligatory. The three subsets: linear combiner, matched filter and LMS algorithm, constitute the major arithmetical processing part. The first block combines the two signals Xk1 and Xk2 stemmed from each sensor, with two weights. These coefficients are computed from the LMS algorithm. It permits to minimize the error between the output of the linear combiner and the signal DS-CDMA [8] generated after decision. The matched filter block is adapted to the sequence used for spreading. It allows the synchronization of the system at each sequence end. The length of the used coding sequence is L (31). This sequence corresponds to a maximal length code, so a peak of intercorrelation is obtained. This allows the synchronization of the control block. When there are no noise and no jammer, the output of the adapted filter can take two values: L or -1.
The two main functions of the control block are the decision and the computation of the error e to adjust the weights Wk.
Static analysis is a part of the optimization phase. It allows the designer to investigate [9] the different possibilities of transformations for the different parts of the algorithm.
As the control block comprises few functional units needing an important implementation surface, the sharing of resources is useless.
The matched filter is submitted to two successive transformations: retiming and associativity.
The expression of Y after transformations is defined by the equation below:
These two transformations allow to get the best rate of resources utilization and a reduction of the critical path. Moreover, this solution permits to obtain a reduced circuit area. As this filter is matched to the coding sequence, the weights Wk are equal to 1 or to -1. Consequently, the multiplication-addition block used in the general case, can be replaced by adders or by substracters. Thereby, in this case a resource sharing is inadequate. It would not reduce sufficiently the useful surface, and as a consequence would increase the execution time.
This block executes the following processing:
Wk and Xk are two complex vectors.
A direct implementation of this block in a single FPGA is impossible because the required number of arithmetical operators is too important. A resource sharing is required and more specifically, a sharing of the multipliers, because these components need an important implementation surface.
The static analysis has allowed us to make obvious a transformation allowing to improve the use of each operator. The optimization phase permits us to rapidly study different cases of retiming, in order to get the best solution.
This block computes weights to minimize the least mean square error between the signal after decision d(t) and the signal stemmed from the linear combiner, y(t). The optimal weights are computed with a gradient algorithm. Its equation is the following:
The number of operations being important, a resource sharing is necessary to implement this module in a single FPGA. The static analysis has showed that a global pipeline of this module permits to get the optimal solution. The introduction of a pipeline leads to an increase of the useful area. Nevertheless, it is possible to implement the transformed algorithm in an FPGA of identical size to the one used for the initial algorithm (with resource sharing and without transformation). Thereby, the pipeline significantly improves, temporal performances of this block without increasing the cost. This transformation executes the LMS algorithm in five cycles. In the initial case (without pipeline), the number of cycles was seven.
The algorithm which describes the multisensor receiver has been simulated in fixed-point with the SPW tool. The useful signal is composed of a typical DS-CDMA signal and each sensor undergoes the influence of a jammer.
Jammer signals are of the following form:
The real signal Sb(t) is a pseudo-random logical sequence.
The useful signal is a spread spectrum signal using direct sequence. The spreading code is a maximal length code of 31. A white complex gaussian noise is added on each sensor, the signal noise ratio is 8 dB.
The LMS algorithm allows to compute the Wk weights so as to minimize the mean square error between the received signal after combination and the DS-CDMA signal after decision.
The gain difference between the useful signal and the jammer is about 14 dB.
As we said before, the system is partitioned in five modules. Each of these blocks is implemented in a FPGA circuit of the Xilinx family.
Table 1 presents the FPGAs used, the number of necessary cycles and the maximal sampling frequency allowed for each block.
Five cycles are necessary to execute the linear combiner and LMS algorithm. Consequently, the maximal sequence rate is equal to 1.9 Mchips/s. Thereby, the data rate has to be inferior to 60 kbits/s, for a spreading factor of 31.
In the fifth FPGA, the four delay lines for the application are implemented. These memorizations are made up of 4 x 33 x 8 bits. They make good the delays introduced by the matched filter and by the retiming in the LMS algorithm and the linear combiner.
The VHDL code elaborated for the implementation of is given here.
The corresponding netlist follows here. Finally, the synthesis results are provided in the report.
In this article, the implementation of a multisensor receiver using DS-CDMA techniques has been described. The utilization of the diversity in reception reduces the effect of jammers.
Similarly we have shown the efficiency of the architectural synthesis tool developed at our laboratory. Indeed, this tool allows to synthesize digital signal processing algorithms and implement them, on FPGAs or on ASICs. Moreover, this tool allows to rapidly study different architectures for a same application.
[1] D. D. Gajski, N. D. Dutt, A. C-H Wu and S. Y-L Lin, "HIGH-LEVEL SYNTHESIS Introduction to Chip and System Design", in Kluwer Academic Publishers, 1992.
[2] K. Djigandé, "Synthèse et évaluation des performances d'architectures pour le traitement du signal", Thèse de doctorat, IRESTE, Université de Nantes, France, Déc. 1995.
[3] S. Crand, K. Djigandé, P. Bakowski, J-F. Diouris and D. Jeuland, "Resource constrained VHDL synthesis from algorithmic description", VHDL-forum 95, IRESTE, Nantes, FRANCE, April 1995.
[4] A. Sharma and R. Jain, "Estimating architectural resources end performances for high-level synthesis applications", IEEE Trans. on VLSI, Vol. 11, No. 6, june 1993.
[5] J. Rabaey and M. Potkonjak, "Estimating implementation bounds for real time DSP application specific circuits", IEEE Trans. on computer-aided design of integrated circuits and systems, Vol. 13, No. 6, June 1994.
[6] J. Rabaey and M. Potkonjak, "Retiming for scheduling", VLSI Signal Processing Workshop, pp 23-32, San Diego, Nov. 1990.
[7] Alta Group "SPW user's guide manuals".
[8] S. K. Barton, "Introduction to CDMA", Annales des télécommunications. 48, No. 7-8, 1993.
[9] L. Guerra, M. Potkonjak and J.Rabaey, "System-level design guidance using algorithm properties", IEEE Workshop an VLSI Signal Processing, San Diego, Oct. 94, pp 73-82.
back to introduction