## 3 Implementation of the Piecewise-Linear Frequency Shifting Algorithm  
The proposed piecewise-linear frequency shifting algorithm can be implemented in the sub-bands of digital hearing aids. Figure 2 is a system block diagram showing the implementation of the proposed frequency shifting algorithm. The input signal from the microphone passes through a pre-filter before going through an analog to digital converter (ADC) and is analyzed to sub-bands by fast Fourier transform (FFT). These sub-bands are divided into N channels. The channels that contain the targeted frequency bands are first passed through non-linear compensation units which have transfer functions of wide dynamic range compression (WDRC). The outputs of the non-linear compensation units are then processed using the proposed piecewise-linear frequency shifting algorithm. The outputs are then combined using inverse fast Fourier transform (IFFT) before passing through a post filter, automatic gain control (AGC), and a digital to analog converter (DAC). Finally, they are passed to the receiving end. Specifically, within the channels that contain the targeted frequency bands, the frequencies are interpolated according to the stretching ratio and sampled according to the compressing ratio described earlier in Equations (1)-(3).  
As shown in Figure 3, \(k\) indicates the FFT spectrum series of the original input audio signal, and \(k^{\prime}\) indicates the FFT spectrum series of the processed signal. \(\left[\begin{array}{cc}n_{l}&n_{h}\\ \end{array}\right]\) indicates the spectrum region before stretching in \(k\) series, and \(\left[\begin{array}{cc}n^{\prime}_{l}&n^{\prime}_{h}\\ \end{array}\right]\) indicates the corresponding processed spectrum region in \(k^{\prime}\) series where  
\[n^{\prime}_{l}=n_{l}-\frac{(\gamma-1)}{2}(n_{h}-n_{l}),\ n^{\prime}_{h}=n_{h}+ \frac{(\gamma-1)}{2}(n_{h}-n_{l}) \tag{4}\]  
Figure 2: Piecewise-linear frequency shifting unit in the digital hearing aids. ADC, analog to digital converter; DAC, digital to analog converter; AGC, automatic gain control; FFT, fast Fourier transform; IFFT, inverse fast Fourier transform.  
Here \(\left[\begin{array}{cc}n_{l}&n_{h}\\ \end{array}\right]\) is mapped to \(\left[\begin{array}{cc}n^{\prime}_{l}&n^{\prime}_{h}\\ \end{array}\right]\), with \((\gamma-1)(n_{h}-n_{l})\) frequency points interpolated, and \(\left[\begin{array}{cc}n_{a}&n_{l}\\ \end{array}\right]\) is compressed to \(\left[\begin{array}{cc}n^{\prime}_{a}&n^{\prime}_{l}\\ \end{array}\right]\), \(\left[\begin{array}{cc}n_{h}&n_{d}\\ \end{array}\right]\) is compressed to \(\left[\begin{array}{cc}n^{\prime}_{h}&n^{\prime}_{d}\\ \end{array}\right]\) with \((\gamma-1)(n_{h}-n_{l})\) frequency points removed totally. Specifically,  
\[n^{\prime}_{a}=n_{a}=n_{l}-\frac{1}{2}\cdot\frac{\gamma-1}{1-\beta_{1}}\cdot(n _{h}-n_{l}),\ n^{\prime}_{d}=n_{d}=n_{h}+\frac{1}{2}\cdot\frac{(\gamma-1)}{(1- \beta_{2})}\cdot(n_{h}-n_{l}) \tag{5}\]  
So, \(\left[\begin{array}{cc}n_{0}&n_{a}\\ \end{array}\right]\) in sequence \(k\) is directly mapped to \(\left[\begin{array}{cc}n^{\prime}_{0}&n^{\prime}_{a}\\ \end{array}\right]\) in sequence \(k^{\prime}\), and \(\left[\begin{array}{cc}n_{d}&n_{N_{w}}\\ \end{array}\right]\) is directly mapped to \(\left[\begin{array}{cc}n^{\prime}_{d}&n^{\prime}_{N_{w}}\\ \end{array}\right]\). After the proposed frequency shifting process, the length of the sequence is unchanged and the overlap is thus avoided. It should be noted that for the stretching part, the amplitude and phase value of the interpolated points are calculated by magnitude and phase spectrums separately. Therefore, the amplitude and phase values of the original points are preserved.