A Programmable Look-Up Table-Based Interpolator with Nonuniform Sampling Scheme

1. Introduction

Nowadays, the world is facing a boom on the fusion between telecommunications and information technology. The merging of these two fields spreads over all kinds of information systems, requiring efforts for ensuring the integration among many kinds of organizations [1], from tactical to strategic operations, in different levels of information system interoperability [2]. The ISO/OSI seven-layer model arises as a lighthouse for seeking the interoperability on many different layers of networked solutions [3]. Many standards and protocols arise from this model, including cryptographic ones.

Encryption solutions can be implemented on both software and hardware. Software implementations are more related to the protection of the information itself, while hardware ones can be also used to protect the communication channels [4]. In the case of tactical telecommunication systems, which require both channel and information security, the hardware implementation of such encryption algorithms arises as a better compromise. The need to test the behavior of such systems against different sources of noise and jamming becomes the motivation to implement, on FPGA (Field-Programmable Gate Array), a programmable noise generator.

A Look-Up Table- (LUT-) based interpolation system is the core of the programmable noise generator developed in this work. Using a LUT, complex and otherwise slow calculations can be sped up by storing precomputed values of the function, interpolating the desired values in between, achieving high-speed designs [5]. Look-Up Tables are very common microelectronic blocks for many applications [5–19]. Ba et al. [9] proposed a linearly interpolated LUT predistorter used to mitigate the effects of nonlinear amplifiers. Monga and Bala [10] proposed an algorithm for minimizing the approximation error on multidimensional LUTs where both samples values and distributions are optimized.

Some authors used nonuniform sampling schemes as a solution for minimizing the LUT memory size: Seidner [11] reduced the memory usage on the implementation of a 10^Y conversion circuit with a LUT scaling sample scheme; Yan and Mämmelä [15] used a nonuniformly segmented interpolation LUT for simulating nonlinear radio frequency power amplifiers; Cavers [16] proposed a systematic way to describe and analyze arbitrary nonuniform LUT sampling schemes as a companding function, which was further improved by Hassani and Kamarei [17] with a LUT segmentation concept; Boumaiza et al. [18] proposed a new companding function for amplifier predistortion with built-in dependence on the nonlinearity of the power amplifier; Dutra et al. [19] used a nonuniform but fixed sampling scheme to minimize the memory size of a LUT-based interpolator designed to represent the Inverse Error Function (erf⁻¹).

All works previously mentioned used a fixed, uniform or not, sampling scheme to characterize a given function or class of functions. The main contribution of this work is to implement on FPGA a LUT-based interpolator system with a sampling scheme that is not-fixed (it can be programmed on the fly) and not-uniformly distributed (it uses not equally spaced sampling points).

The remaining of the paper is organized as follows: based on the definition of partitions, Section 2 will present the offline calculations performed to define the parameters that configure the proposed programmable LUT-based interpolator. Section 3 will describe the interpolator architecture, including the description of the subsystem that calculates the nonuniformly distributed addresses and the corresponding displacements. An application of the proposed interpolator will be presented on Section 4, where its flexibility will be discussed with the usage of a gamma of different functions g(x), using different not-fixed and not-uniformly distributed sampling schemes. Section 5 will end this paper with a summary of the achieved results and a flavor of future works.

2. Configuration Parameters

To discuss the determination of the configuration tables for the LUT-based interpolator, discussed hitherto, we will consider a generic function g(x) which will have notable values stored on the appropriate tables. To set an example, values that define a set of arbitrary intervals are stored in Table 1. The number of intervals is related to the number of resources used on the FPGA implementation. As a project decision, P = 22 partitions were used in order to minimize the final approximation error. Although we focus on a specific example, the underlined method is revealed in its generality.

The configuration parameters of the LUT-based interpolator, including the content of the memories that store the ordinates and derivatives, are previously calculated and imported into the FPGA. These parameters are calculated according to a scheme of P not-fixed and not-uniformly distributed partitions, or sampling regions, as exemplified in Table 1. In this table, each partition n is defined by the interval [x_n, x_n+1) and a sampling frequency f_n. For example, in Table 1, the fourth partition (n = 4) is defined on the interval (x₄, x₅] = (−0.9903, −0.9805], with a sampling frequency f_n = 4096. Note also in Table 1 that x_P+1 = 0.99993896484375.

The interval and sampling frequency of each partition should be chosen in order to allow the representation of g(x) with a minimum approximation error. Therefore, higher sampling frequencies f_n should be expected on n intervals where g(x) changes more abruptly, presenting higher curvature. Based on the data of Table 1, we calculate the configuration parameters of the LUT-based interpolator, as illustrated in Table 2 and explained ahead.

The quantities QMR, SMN, EMN, MNM, SMP, and IMN are intermediate variables necessary for the recursive calculation of the Address Logic in (8). They are related, respectively, to the following entities: the Quantity of Memories Required (QMR) on each partition n, the Starting Memory Number (SMN) and the Ending Memory Number (EMN) on each partition n, the Maximum Number of Memories (MNM) considering that the specific sampling frequency was applied to the entire domain [x₁, x_P+1), the Starting Memory Position (SMP) considering that the specific sampling frequency was applied to the entire domain [x₁, x_P+1), and the Initial Memory Number (IMN) used on the specific sampling frequency.

Based on the characterization of the P = 22 partitions (exemplified in Table 1), the equations described in this section are used to calculate the configuration parameters (exemplified in Table 2) used by the proposed nonuniform LUT-based interpolator. Section 3 is going to discuss the internal structure of this interpolator and how it uses the configuration parameters present in Table 2 to perform its tasks.

3. Interpolator Architecture

The LUT-based interpolator designed in this paper maps a 15-bit wide input x, with binary point position d = 14, belonging to the domain [x₁, x_P+1) = [−1, +0.99993896484375), using a two’s complement signed fixed-point arithmetic, into a desired output g(x). The LUT-based interpolator can be used with different g(x) functions, no matter how wide their domains are. For example, for a domain [−|M | , +|N|), where |N | >|M|, we have to scale the input from the interval [−|N | , +|N|) to [−1, +1) and neglect the values on the interval [−|N | , −|M|).

The first-order Taylor’s approximation arises as the best compromise between hardware costs and approximation error. It presents the biggest marginal improvement regarding the average approximation error, with the lower hardware cost: one multiplier and two RAM blocks for storing the $$ ordinate and the $$ derivative, which are calculated according to the nonuniform spaced sampling points (abscissas $$) by using (9) and (10), as demonstrated in Table 2 (columns SPS_n and SPF_n).

When using a uniform sampling scheme, the addresses and differences can be calculated by extracting, respectively, the most (MSB) and less (LSB) significant bits from the input x. But in our case, because the values stored inside the RAM blocks come from a nonuniform sampling scheme, we have to apply a more complex operation for calculating these values. This task is performed by the specific designed subsystem Difference_Address, as can be seen in the schematic top view (Figure 1) of the nonuniform LUT-based interpolator. Figure 1 shows the Difference_Address subsystem, two RAM blocks for storing the $$ ordinate and the $$ derivative, a block that multiplies the $$ output of derivative RAM block with the difference $$, a block that adds this product with the output $$gotten from ordinate RAM block, and three delay blocks used to synchronize the data flow.

The subsystem Difference_Address can be seen in details in Figure 2. It has two outputs and two branches, one for calculating the addresses to be used by the RAM blocks and the other related to the calculation of the Differences $$. It is directly programmed by the parameters presented in Section 2 and illustrated in Tables 1 and 2. When we change the configuration parameters in accordance with the contents of the ordinate and derivative RAM blocks, we enable the LUT to interpolate different g(x) functions, according to different nonuniform sampling schemes. The Difference_Address subsystem is composed of nine blocks (six subsystems, two adders, and one binary point forcer), as it will be discussed in the following.

The first subsystem (Sampled Region and Corrected Superior Limit) in Figure 2 is configured by the Corrected Superior Limit (CSL_n) parameters calculated by (3) and exemplified in column 3 of Table 2. It senses the input x, and outputs a selector signal that identifies the partition n where this input belongs. For instance, in the case of using the sampling scheme illustrated by Tables 1 and 2, for x = −0.97, it outputs a selector signal equal to 5, meaning that the input x belongs to the partition [x₅, x₆) = [−0.95904541015625, −0.98052978515625).

Based on the selector signal provided by subsystem Sampled Region and Corrected Superior Limit, the next two subsystems, Displacement and AddLog, output the values Dsp_n and Add log _n   calculated by (7) and (8). These both values are used to calculate the nonuniform RAM addresses via the two blocks named Displacement_Adder and Add_Log_Adder. Continuing on the example above, the provided selector signal equals to 5, implying Dsp_n = 1024 and Add log_n = 78.

Keeping on the description of the Address branch of Figure 2, we have two subsystems that select a configurable number of bits from their inputs. The first one, named Add_MSB, slices a configurable number of the most significant bits of input x. This configurable number of selected bits is defined by the parameter B_n in (4). This output is added with the Displacement value Dsp_n, and a configurable number of its less significant bits, defined by the parameter D_n in (5), is selected by subsystem Add_LSB. Finally, the Address is calculated by adding this value with the parameter Add log _n   explained above and calculated by (8).

The output Difference is calculated by the configurable subsystem named Dif_LSB. It is configured by the parameters S_n in (6) and the sampling frequency f_n in Table 1. This subsystem slices a configurable number (defined by parameter S_n) of the less significant bits of the input x and forces the binary point to a fixed position d = 14. An exception must be done on the sampling regions where f_n = 2¹⁵ because no interpolation is necessary: all possible values x of these regions are mapped one to one to a corresponding $$, and the differences are always made equal to zero.

The six subsystems discussed above are configured on the fly by the parameters enumerated in the example in Tables 1 and 2. These parameters are stored inside each subsystem by means of 28 memories (22 RAM blocks storing 2 positions each and 6 storing 22 positions). Their contents, as well as the contents of the 512 positions wide ordinate and derivative RAM blocks, can be changed on the fly, what enables this nonuniform LUT-based interpolator to represent different g(x) functions, according to different sampling schemes, as it will be seen in Section 4. The reconfiguration time is defined by the depth of the longest RAM block, the ordinate or derivative RAM blocks: the interpolator requires 512 clock cycles for a full reconfiguration.

The presented design was implemented using the softwares Integrated Software Environment (ISE) and System Generator (SysGen) from Xilinx, on a Spartan-3 development kit from Avnet with a XC3S2000-5 FG676 Spartan 3 FPGA. The synthesis details of this realization can be seen on Table 3.

4. Programmable Noise Generator

As a study case, the proposed nonuniform LUT-based interpolator was used as a programmable noise generator able to output noise with different Probability Density Functions (PDFs). A controlled level of approximation error is achieved by using the proposed programmable nonuniform sampling scheme.

The transformation function g₁(x) has two poles located at the abscissas x = −1 and x = +1, which are characterized by high values of curvature and derivatives. Both the uniformly distributed input signal and the domain of g₁(x) are represented by the interval [x₁, x_P+1) = [−1, +0.99993896484375). The ordinate of this function ideally goes from −∞ to +∞, what is expected since the output is an unlimited normally distributed signal.

One advantage of implementing a nonuniform sampling scheme for the interpolation of g₁(x) is the lower RAM space necessary for storing both the $$ ordinates and $$ derivatives, allied to a lower approximation error. As a counterexample, if we use a uniform sampling scheme instead of the proposed nonuniform one, we would face high approximation error around the poles of (14), even using high frequency samplings, as seen in Figure 3. These graphs show the absolute approximation error verified when two different uniform sampling schemes were applied to the whole [x₁, x_P+1) domain: the upper graph shows the error for f_n = 128, what requires the storage of i_n = 256 positions of $$ ordinates plus i_n = 256 for $$ derivatives; and the lower graph (observe the zoom on x axis) shows the error for the case where f_n = 16384, that results in i_n = 32768 + 32768 = 65536 positions for both RAM blocks. The horizontal line in Figure 3 represents a boundary approximation error limit equal to 3.0518 × 10⁻⁵: the input values are 15 bits long, and any error lower than that boundary does not decrease the quality of the interpolation.

If a uniform sampling scheme is used, the only solution to keep the absolute approximation error below this boundary for all abscissas x would be to use f_n = 32768, what makes the approximation error equal to zero for all possible abscissas x. This happens because, in this extreme case, there is not a really interpolation, but a one-to-one mapping of all possible input values x. But such linear sampling scheme requires a RAM block with a high depth equal to i_n = 65536 positions for storing $$, hard to implement on an FPGA due to the number of bits necessary to represent each stored value.

The solution is to use the proposed nonuniform sampling scheme which stores less $$ ordinates and $$ derivatives for input values around x = 0, and more samples near the poles x = +1 and x = −1, where the approximation error is bigger, saving significant amount of memory space (the proposed LUT-based interpolator reserves only 512 positions for each ordinate and derivative RAM blocks). This approach is graphically presented in Figure 4, where you can see the 1st quadrant of g₁(x)—the 3rd quadrant is not displayed since it is symmetric in relation to the origin (0,0). The absolute approximation error obtained with this nonuniform approach remains under the boundary limit (3.0518 × 10⁻⁵) even near the poles of g₁(x), as seen in Figure 5.

When the proposed programmable nonuniform LUT-based interpolator is configured to represent (14), according to the sampling scheme of Tables 1 and 2, it works as a Gaussian noise generator: by applying to its input a signal with a uniform PDF (Figure 6(a)), it outputs a signal with Gaussian PDF (Figure 6(b)).

Tables 1 and 2 are just one example of configuration data for the proposed programmable LUT-based interpolator. In this work, 3 different sampling schemes (α, β, and γ) were formulated. The sampling scheme α was the one demonstrated in Tables 1 and 2. The abscissas $$ of sampling schemes α, β, and γ are plotted in Figure 7. As can be seen in these figures, there are $$ sampling points on scheme α, $$ on scheme β, and $$ on scheme γ. As expected, the amount of sampling points is always smaller than the depth (equal to 512) of the two RAM blocks that store the corresponding ordinates $$ and derivatives $$. Observe that the inclination on these graphs is inversely proportional to the sampling frequency f_n of each partition n: the higher the frequency f_n, the bigger the number of abscissas $$, and the smaller the inclination in Figure 7.

Each sampling scheme was designed to minimize the approximation error for x abscissa values belonging to the sampling region with higher f_n values. As a matter of fact, high frequencies should be used for regions where g(x) presents a strong nonlinear behavior and low frequencies for regions with a linear behavior. For example, the sampling scheme α was specifically designed for the Gaussian transformation function (14). It applies high frequencies (f_n = 16384) near the poles x = +1 and x = −1 and low frequencies (f_n = 32) near the origin x = 0. The approximation error for the three sampling schemes α, β, and γ can be seen in Figure 8, in a case of using the displaced Gaussian transformation function (15), and in Figure 9, for the Cubic Function (18) case.

The frequency assignment of the P = 22 partitions for sampling schemes β and γ is presented in Table 4. The corresponding configuration parameters for these sampling schemes are calculated via (2) to (12) and are presented in Tables 5 and 6. Observe that the sampling limits x_n for sampling scheme β are the same as sampling scheme α, only the frequencies f_n are distributed differently. But in the sampling scheme γ, both sampling limits x_n and the frequencies f_n are distributed differently from sampling schemes α and β, what shows the flexibility for reconfiguring the designed programmable noise generator.

As seen in Table 1, the scheme α distributes the P = 22 sampling frequencies f_n symmetrically to the origin, with the lower frequencies near the origin, as can be graphically seen in Figures 8 and 9 (upper graphs): the semiarcs with bigger diameters (related to f_n = 32) are located around the origin, in the interval −0.125 < x < 0.125. As seen in Table 4, the schemes β and γ distribute the lower sampling frequencies (f_n = 32) on the intervals −0.64 < x < 0.34 and −0.5 < x < 0.0, respectively, as can be graphically seen in Figures 8 and 9((b) and (c) graphs, resp.).

The designed programmable noise generator can generate different noise signals by properly filling the ordinate $$ and the derivative $$ RAM blocks (Figure 1) and configuring its internal parameters on the Difference_Address subsystem (Figure 2). For example, Figure 10 shows the Probability Density Functions (PDFs) of four different signals produced by the programmable noise generator when: (1) its input is fed with a uniform distributed noise, (2) it is configured with the sampling scheme α, and (3) it was configured to interpolate four different functions: the Displaced Error Function (15), the Cubic Function (18), the first (19), and the second (20) Quadratic Function.

5. Conclusion

A programmable Look-Up Table-based interpolator with nonuniform sampling scheme was implemented using a Avnet development kit containing an XC3S2000-5 FG676 Xilinx Spartan-3 FPGA. This LUT-based interpolator can be programmed on the fly by loading the proper configuration parameters presented in Section 2, including the $$ ordinate and $$ derivative, inside RAM blocks. The complete reconfiguration takes 512 clocks cycles. When these parameters are changed, they can interpolate different g(x) functions, sampled according to different nonuniform sampling schemes. The ability of changing the sampling scheme allows the minimization of both the approximation error and memory space: for instance, the sampling schema α (Table 1) applied to (14) was able to keep the approximation error below a threshold of 3.0518 × 10⁻⁵ while reducing the memory usage to 2.71% for a Gaussian noise generator application.

As a study case, the LUT-based interpolator was used as the core of a programmable noise generator able to output signals with different Probability Density Functions (PDFs). The flexibility of this design was proved by interpolating 8 different g(x) functions, according to 3 different nonuniform sampling schemes (α, β, and γ) described in Tables 1 and 4, each one defining P = 22 partitions each characterized by a chosen sampling frequency f_n.

As future work, we recommend the implementation of a programmable nonuniform LUT-based interpolator with a domain not fixed to [x₁, x_P+1) = [−1, +1) and where the number P of sampling regions can be changed on the fly.