Development of Reusable Algorithms Based on C and C++

by Doug Johnson (doug_johnson@frontierd.com)
Business Development Manager, Frontier Design, Inc.

INTRODUCTION

Today many complex communications and digital signal processing (DSP) systems are described using ANSI C or C++ with floating-point mathematics. ANSI C or C++ is the language most commonly used by system engineers since the language has been incorporated into university programming courses and a variety of environments are available for code development, compilation and debug. The system engineer defines global functionality using the built-in operators, data types and expressions in C and classes in C++. Often, the functions are algorithms that perform filtering, modulation, demodulation, compression, coding and other operations on digital signals. Initially, these algorithms are developed in a pure mathematical environment using idealized representations of the signals and operators. Floating-point mathematics is typically used in operations on signals with infinite precision, where no assumptions are made on the limitations of the signal dynamics or timing.

Floating-point mathematics is used for DSP algorithm and communication system development because it offers extensive dynamic range and accuracy and it accommodates virtually limitless word-widths and precision. In addition, an enormous number of floating-point algorithms have been developed and refined by universities, research centers and advanced product groups. These "legacy" DSP and communications system algorithms represent vast amounts of engineering expertise and financial outlay. To be exploited to its full value, this legacy code should be implemented as re-usable intellectual property that will accurately represent the behavior of the system. This intellectual property ideally will be fixed-point ANSI C or C++ code and models written in hardware description languages such as Verilog HDL or VHDL. Converting floating-point C or C++ code to fixed-point code is the mandatory first step in the creation of reusable algorithms since most implementations in hardware and software will limit the word-length and precision of operations. However, making the floating-point algorithm work within the fixed and limited dynamics and precision of the fixed-point representation, while maintaining the same overall system response as the floating point equivalent is exceptionally difficult.

CONVERTING FLOATING-POINT CODE TO FIXED-POINT CODE

Fixed-point number representations can lead to a variety of problems that adversely affect system behavior. Simply specifying a fixed number of bits for the word-width and precision of a variable is likely to fail because the result of many operations may not fit in the fixed-point data types. Typical effects of using fixed-point math include both overflow and quantization. A value to be stored could be too large to fit the fixed word-width (overflow). Or its precision could exceed that of the fixed-point specification or it could have too few precision bits (quantization). In order to ensure that the fixed-point algorithm behaves in an acceptable way, you must model and analyze those effects correctly.

Overflow occurs whenever a value that needs to be stored exceeds the maximum or minimum value that can be represented with a given fixed-point data type. For example, the number 100 cannot be stored in a 6-bit number, as it can only hold values between —32 and +31. In this case overflow occurs and the number 100 will actually wrap around to yield a value of -28. Overflow behavior will drastically change system behavior. Quantization occurs whenever a value needs to be stored with less precision than is required to represent the actual value. For example, the value 3.3 cannot be correctly represented with only 2 bits of precision. The closest approximation of the value 3.3 with 2-bits of precision is 3.25. The result of this change in precision introduces an "error" compared to the original value, which is typically experienced as "digital noise."

Re-specifying floating-point algorithms in fixed-point math is difficult because the C language doesn’t support fixed-point data types. For example, there is no C data-type with configurable word-length and precision. Nor are there any classes to specify different quantization and overflow behavior, other than wrapping and truncation. As a result, system engineers writing in ANSI C have had to write ad-hoc code to model their originally floating-point algorithms in a fixed-point way. C++ alleviates this problem for the system engineer by allowing the user to define data types and classes but there is still no built-in mechanism in the language to handle bit accurate modeling of finite precision mathematics. Developing useful data-types in C and C++ to model fixed-point behavior is the most critical step to providing reusable intellectual property.

DEVELOPING FIXED-POINT CLASSES

To effectively model the effects of fixed-point mathematics, the C language must be expanded to include fractional data types and the functions and operators to manipulate data of these types. During the design of the library of fractional data types, care must be given to make the fractional data types look like they were built-in C types (i.e. all standard C operators are available on those types). For this purpose, the library can exploit a C++ feature, called templates which will retain the "natural C look" of the fractional data types. A template is a generic, or parameterized class, which is instantiated at compile time that results in a class and behaves like an ordinary C++ class and data type. To completely model an algorithm with bit accuracy, the library must include support for a minimum of these variable types: fixed-point, integer, unsigned fixed-point and unsigned integer. A C++ class hierarchy is established to allow the system engineer to access the data-types appears in Figure 1:

Once the class hierarchy is defined, floating-point variables can easily be specified in fixed-point form by using the following data class "Fix<w,p>", where "w" is the fixed word-width and "p" is the fixed number of precision bits. For example, a variable with an 8-bit word length and 5 bits of precision would be specified as follows: "Fix<8,5>". Fixed-point values can be specified as signed or unsigned fixed-point (i.e. Fix<w,p> or Ufix<w,p>, as signed or unsigned integers (Int<w>, Uint<w>). The following is a code fragment showing the use of the overloading properties of ANSI C and C++ when writing code with the template library:

#include <fxp.h>

Fix<14,10> abs(
Fix<14,10> in
)
{
Fix<14,10> out = in;
If (in < 0.0)
{
out = -in;
}
return out;
}

The code fragment shows a simple assignment to a fixed-point number. The following examples show how to assign a variable with representations in double precision or binary, which exploit the overloading properties of C and C++:

1. By using a string containing the representation of the number

Fix<8,7> a= "0.1" ; // decimal value

Fix<8,7> a= "0bt0.1011011" // binary 2s complement

2. By using a double precision number

Fix<8,7> a = 0.2;

Fix<8,7> A[3]= {0.1,0.2,0.3};

3. By using a unary or binary operation

Fix<8,7> a = 0.1;

Fix<9,8> c = +a; // unary operation

Fix<8,7> b = 0.2;

Fix<9,8> d = a+b;

4. By using the cast function

Fix<8,7> a = 0.1;

Fix<9,8> d = a.cast();

Two Fix or Ufix numbers with different width or precision are different C++ objects and cannot directly be assigned to each other. The unary + operator or the cast function can be employed to do the assignment. For example:

Fix<8,7> a=0.1;

Fix<9,8> b = a; // gives error since no matching constructor

Fix<9,8> c = +a; // correct

Fix<9,8> d = a.cast(); // correct

BIT-ACCURATE MODELING OF QUANTIZATION AND OVERFLOW EFFECTS

When fixed-point arithmetic is used, quantization is an inevitable side effect that typically exhibits itself as "noise." The template library can be extended to allow system engineers to specify how quantization effects are handled, simulate the response and refine the quantization again until the desired behavior is achieved. Similarly, the results generated by the vast numbers of multiply-and-accumulate operations used in digital signal processing and communications algorithms are frequently larger than the fixed word-width that has been specified by the design, causing overflow. Overflow can cause the signal to be distorted or can introduce unpredictable non-linear behavior. A general mechanism needs to be established to define specific overflow and quantization behavior.

An additional class is added called fxpOqc, which is short for "overflow and quantization characteristic" and can be incorporated as a function to an operation in the C or C++ code. The fxpOqc class is a general mechanism that allows the system engineer to define specific overflow and quantization behavior. The fxpOqc class has the following constructor:

fxpOqc(

quantizationType quantization = TRUNCATED,

overflowType overflow = WRAPPED,

int nrofBits = 0

);

By default "TRUNCATED" quantization and "WRAPPED" overflow are used since this is the behavior of hardware designed to perform 2’s complement arithmetic. A given overflow and quantization behavior, defined by a fxpOqc class can be applied to an expression by means of the "oqc" function and a code fragment illustrating its use is as follows:

fxpOper oqc(fxpOper an_operation, const fxpOqc* an_oqc);

The following example illustrates how the "oqc" should be used:

Fix<8,7> a=0.1;

Fix<8,7> b=0.2;

fxpOqc myChar (ROUNDED0, WRAPPED);

Fix<8,7> d= oqc (a+b, &myChar); // custom characteristic

The templates must provide accurate representation of a variety of quantization methods including truncated, truncated-zero, rounded-infinity, rounded-plus-infinity, rounded-minus-infinity convergent rounding or rounded-zero. In addition, the templates must provide accurate representation of all overflow characteristics. The following tables show the complete characteristics of the required quantization and overflow characteristics:

The add and accumulate operation of the above FIR filter will result in an output value of 24 bits wide with 15 bits of precision to the right of the binary point. When applying quantization and overflow characteristics, the numbers in template library can be signed or unsigned. Some overflow and quantization characteristics favor a 2’s complement representation, while others favor a 1’s complement representation. The determination of the quantization and overflow works in the following sequence:

· The operation is performed with a temporary result type that does not generate any overflow or quantization effect; i.e. the operation is performed with maximum precision.

· The temporary result is quantized as specified. Overflow may occur at this step.

· The appropriate overflow behavior is applied to this intermediate result, which returns the final value.

To summarize, the system engineer has a choice: develop and validate a C++ template library or procure a library to allow the accurate modeling and simulation of fixed-point arithmetic. Legacy C code can be modified using this template based approach to transform the C code into reusable intellectual property. Once bit accurate functionality has been written into in the code, simulation and debugging can take place in the user’s environment. The user’s environment could be a proprietary C based simulator customized to an application or an industry standard software tool. For instance, many large telecommunications companies have developed proprietary C or C++ based system simulators that completely characterize the end-to-end performance of wireless communications using GSM, CDMA and AMPS standards. Bit-accurate simulation is critical to the analysis of forward error correction and modulation schemes and the detrimental effects of channel noise and inter-symbol interference prior to building dedicated hardware.

Another example of the utility of a universal template based library to simulate bit accurate behavior would be to model the behavior of algorithms in off-the-shelf, fixed-point DSP processors. The template data-types and operators can be used to model the arithmetic behavior of a particular fixed-point DSP processor. Using this method, system engineers can accurately model the behavior of C code in several different DSP processors to determine which will provide the optimal implementation.

Ultimately, the system design must be implemented in hardware. This template- based approach can be exploited to define and analyze a variety of hardware implementations of an algorithm prior to converting it to a hardware description language like VHDL or Verilog HDL. HDL simulations for large designs have long run times whereas a simulation in C can run potentially 100 times faster than a HDL simulation. Using this approach, system engineers stay in a C based system level environment longer which eases the system verification of each alternative solution.

HARDWARE DESCRIPTION LANGUAGE CODE DEVELOPMENT

Re-usable intellectual property cores of algorithms or sub-systems are specified in hardware description languages such as Verilog HDL or VHDL. Once the system engineer is satisfied with the behavior of the fixed-point algorithm developed in ANSI C or C++, the algorithm must be converted to a hardware description language. In the past, the system engineer was forced to do this by hand and then verify that the C simulation results match simulations performed on the hand-coded HDL. This process can take days or weeks to complete and requires many verification runs.

Recent advances in electronic design automation tools now allow a system engineer to automatically generate useful VHDL or Verilog HDL code directly from the C code. These tools typically support a useful subset of ANSI C including all numeric constant formats, all basic data-types, operators, iteration statements and function calls. Most importantly, the resulting HDL description of the design must match the bit accurate behavior specified in the original C model. Therefore, a simple syntax translation of the source C model is inadequate. The tool must use the fixed-point data types, quantization and overflow characteristics specified in the original C code to drive the HDL generation. In fact, the system engineer needs to control the hardware dimensions from within the C code.

A generic IP design flow based on tools capable of automatic code generation is as follows:

The C code is compiled into synthesizable register transfer level (RTL) Verilog HDL or VHDL by the HDL generator according to the design hierarchy. A Verilog HDL or VHDL simulator can then generate the clock-cycle response to the functional behavior obtained during high-level C execution. Once the simulation results correlate, the RTL model can be synthesized using logic or behavioral synthesis tools to obtain an ASIC or FPGA netlist.

The HDL generation tool creates a C test bench that allows simulation and debugging in the C development environment. This test bench is capable of reading an input file containing stimuli and generating output files of results. By adding a few extra statements to the C code, stimuli and reference files can verify the RTL description against the C specification. An automatic HDL test bench generation facility is employed to assist in the verification of the generated RTL model against the original high-level C model.

It is of paramount importance to allow the system engineer to take full control of the dimensions of the datapath and the arithmetic operators that are used, by refining the input C-description with fixed-point data-types and operators, as provided by template library. The HDL generation tool will then create a datapath with the exact word-sizes and resources that are required to bit-accurately implement the fixed-point enriched specification. Once the fixed-point C code has been written, it can now be reused by system engineers in new designs requiring the same algorithm or sub-system block and debugged in any C development environment. The same C code can then be used to generate synthesizable VHDL and Verilog HDL code which can be used by engineers to implement a design in hardware.

Libraries exploiting the template capabilities of C++ can be developed on a project basis or developed by a software-engineering group for use throughout an organization. However, commercially available products like A|RT Library from Frontier Design can be used enterprise wide as a universal template library. A design modeled in C or C++ using A|RT Library can be used to drive a HDL generation tool like A|RT Builder.

CONCLUSION

C code can become the solution to providing intellectual property across large organization since it is inherently portable and is the most commonly used language by system engineers to do architectural development. Enriching the C code with fixed-point data-types allows a system engineer to further refine the system or algorithm by accurately modeling the effects of quantization and overflow prior to detailed hardware design. Employing code generators capable of transferring the fixed-point effects from C code to HDL code will quickly speed the development and verification of reusable intellectual property.

		Click here to get your listing up.