# FPGA Implementation of a Higher SFDR Upper DDFS Based on Non-Uniform Piecewise Linear Approximation
## 2 Non-Uniform PWL Approximation Method
### PWLMMAE  
The core idea of the algorithm is to determine the subinterval straight line by least squares, then calculate the maximum absolute error between the line and the real curve and find the maximum absolute error less than the predetermined error through continuous iteration, the steps of the algorithm are as follows.  
1. Input range discretization Considering the hardware implementation, the input range should be discretized. For a given input interval \([X,Y]\), the input \(x\) should be defined as a vector \[x=x(1:NUM)=X,X+\frac{1}{2^{Q}},X+\frac{2}{2^{Q}},...,Y\] (5) where \(Q\) is the number of fractional bits setting in hardware and \(NUM\) is the length of the vector.
2. Minimization of MAE for a given width of subinterval The slope \(a\) and intercept \(b\) of the subinterval approximation line are first calculated using the least squares method by Equations (6) and (7), and we can use \(h(x)\) to represent the approximation line. \[bn+a\sum x=\sum f(x)\] (6) \[b\sum x+a\sum x^{2}=\sum xf(x)\] (7) where \(n\) is the number of discrete points in the subinterval, then, the objective function is denoted by \(f(x)\) with \(x\in(j:k),1\leq j\leq k\leq NUM\), so the error vector can be expressed as Equation (8). \[\delta=f(x(j:k))-h(x(j:K))\] (8) The corresponding MAE can also be calculated as \[MAE=max\{|max(\delta)|,|min(\delta)|\}\] (9) To minimize MAE, we shift line \(h(x)\) vertically such that \(|max(\delta)|=|min(\delta)|\), and the distance \(T\) moved can be calculated by Equation (10). The MAE after movement is shown in Equation (11). \[T=max(\delta)-\frac{max(\delta)-min(\delta)}{2}=\frac{max(\delta)+min(\delta)} {2}\] (10) \[MAE=\frac{max(\delta)-min(\delta)}{2}\] (11)
3. segmentation points To obtain the maximum segmentation interval, we determine the segmentation points from right to left. Initially, we set \(\text{START}=x(1)\), \(\text{END}=x(NUM)\), then perform the PWL method on \(x\)(START: END) to calculate MAE by Equations (8) and (9). If \(MAE\leq E_{c}\), where \(E_{c}\) is a predefined error, approximation succeeds and set \(b=b+T\); otherwise \(\text{END}=\text{END}-1\) and repeat above step. Once approximation succeeds, we will update \(\text{START}\) and \(\text{END}\) to find the next subinterval, where \(MAE\leq E_{c}\). The values of \(\text{START}\) and \(\text{END}\) record the segmentation points, the index \(i\) records the number of segments. Figure 2 shows the process of finding the \(i\)th segment. \(h_{1},h_{2},...,h_{i-1}\) represent the approximate lines of the previous \(i-1\) segments respectively, \(x(END_{i-1})\) is the start point of the \(i\)th segment. The end point of first approximation of \(i\)th segment is \(x(NUM)\).Continuously move the end point to the left in steps \(\frac{1}{2^{Q}}\) until the error between the approximate line and the objective curve is less than \(E_{c}\). Then, we can obtain the end point \(x(END_{i})\) of the \(i\)th segment and the approximate line \(h_{i}(x)=a_{i}x+b_{i}\)In summary, the implementation of PWLMMAE is as follows (Algorithm 1). On the fifth line, \(polyfit\) is a function that uses the least squares method to fit the curve and the argument \"1\" indicates first-order.  
```
1\(x=M:\frac{1}{2^{Q}}:N,NUM=length(x)\);
2\(j=1,END=NUM,i=1,F=1\);
3 while\(j!=NUM\)do
4 while\(F==1\)do
5\(a_{i},b_{i}=polyfit(x(j:END),f(x(j:END)),1)\);
6\(h(x)=a_{i}*x+b_{i}\);
7\(\delta=f(x(j:END))-h(x(j:END))\);
8\(MAE=(max(\delta)-min(\delta))/2\);
9 if\(MAE\leq E_{c}\)then
10\(b_{i}=b_{i}+\frac{max(\delta)+min(\delta)}{2}\);
11 store \(a_{i},b_{i},x(j),x(END)\);
12\(F=0\);
13
14 end if
15
16 end for
17\(i=i+1,j=END,END=NUM,F=1\);
18
19 end while
```  
**Algorithm 1**PWLMMAE  
In summary, the implementation of PWLMMAE is as follows (Algorithm 1). On the fifth line, \(polyfit\) is a function that uses the least squares method to fit the curve and the argument \"1\" indicates first-order.