Peak detection of any time series data is always a hot topic in many engineering fields including chemistry, biology, biomedical, optics, astrophysics and energy systems. So these fields often require real-time peak detection. As the environment noises can affect the signals somehow, a robust peak detection, in this case, is a challenging topic. To obtain a successful peak detection method, several methods have been proposed, including automatic multiscale-based peak detection  , window-threshold techniques    , wavelet transform  -  , techniques using entropy  , and artificial neural networks   . Particularly, each method was investigated in terms of the detection method employed and the detection performance achieved. Drawbacks of the peak detection algorithms available in the literature are that many free parameters such as the window length of a threshold value have to be used in order to apply the algorithm to the signal, and to make the algorithm applicable. Generally, the algorithms with fewer parameters are restricted for use in specific applications like the detection of R-peaks in electroencephalography (ECG) signals and to obtain an adaptive and time-efficient R-peak detection algorithm for ECG processing as well as reduce the size and noise of ECG signals  -  . In addition, noise in analyzed signal is a challenge for many peak detection algorithms.
On the other hand, periodic and quasi-periodic signals are the most difficult ones to detect the peak points. However, AMPD method is suitable for all types of peak point detecting. Thus, the automatic multiscale-based peak detection (AMPD) method  has been introduced as an effective method. In this research, we used the off-line and online terms to show the scale. Off-line algorithm means to fix the scale, then analysis all input data with using stable scale for each clock. On the other hand, online algorithm means to vary the scale for each clock. However, these software methods are not suited for real-time processing but emphasized off-line sophisticated data analysis.
The use of FPGAs provides a promising approach to real-time peak analysis   . FPGAs do not run a program stored in the program memory because they are reprogrammable chips and include a lot of logic gates, which are internally connected to form a complex digital circuitry. FPGAs are not processors and are entirely different from CPUs, GPUs, and DSP. However, they offer various opportunities for efficient real-time signal processing by making the best use of pipelined structure in computing. Furthermore, in previous work, we applied AMPD method on an FPGA as off-line by changing its bite size and scales and then analyzed it in terms of speed, cost and memory  . Eventually, we realized that changes in bit size did not affect the peak detection.
This paper introduces a novel approach for robust and real-time peak detection by using the AMPD algorithm and the FPGA technology. It highlights the modification of the original AMPD algorithm to be an off-line method, and how it can be implemented on an FPGA so that a pipelined structure in computing is extracted on hardware. Thus, the optimum scaling for the off-line peak detection is obtained, and results compared with the original AMPD method are found very promising.
2. Overview of Algorithm
2.1. AMPD Method
The AMPD method  is a technique especially to find the peak points of periodic and quasi-periodic noisy signals on-line. It calculates all input data by using matrix equation to find the peak points. Also, AMPD determines the local maxima points in different time periods, each of which is named scale and is the number of compared data at a time. AMPD is divided into 4 different stages: Local Maxima Scalogram (LMS) calculation, Row-Wise summation of the LMS, LMS rescaling, and peak detection. Figure 1 shows the flowchart about the original algorithm. However, to enable off-line processing on an FPGA, Row-Wise summations of the LMS and LMS rescaling are skipped to obtain optimal scale decision and LMS rescaling, which is possible to perform in advance in a calibration phase. Number of combinations to create scale pattern like 33, 65, 129, 257, 513 and 1025 for make a simple and efficient pipeline to implement on FPGA. Fixed scales are then chosen and, based on them, the sensitivities of the peak points are analyzed.
2.1.1. LMS Calculation
Essentially, LMS calculation means analysis of all input values ( ) by using the moving window approach to fill in the Z matrix given in Equation (1) below that also indicates the size of the Z matrix. In Z matrix, k denotes the number of rows while i denotes the columns. The relation between n and L can be defined as shown in Equation (1):
Figure 1. AMPD algorithm flowchart.
When all numbers denoted by xi are analyzed, the previous value should be (Xi-1) and the next value (Xi+1) is checked and compared using the window approach, which is called distance between all the points. Furthermore, the window approach scale depends on the L.
n denotes total column number
L denotes total row number
At the same time k is changed from 1 to L in Figure 2, which shows the comparison mechanism of input values.
Elements of Z matrix can be calculated by Equation (3).
r denotes random number between 1 and 2.
If this condition point ( ) is provided,
Then, new diagonal element zL,n value assigned to is zero in the Z matrix, or else, a random number (r) assigned to is generated at every time by a random generator. The range of random numbers is between 1 < r < 2. In this way, the whole Z matrix is obtained by analyzing each element of it.
Figure 2. Compare mechanism.
2.1.2. Positive Edge and Negative Edge Peak Points Detection
The target of this study is to detect peak points by applying the variance formula. After completing the formation of the Z matrix, the zero points are detected by applying the variance formula to each column. In some cases this value may not be zero due to noises; however, detection is done when the value is smaller than a minimal threshold value. Thus, if sigma (σ), in Equation (4) is found to be zero, then this point is interpreted to correspond to the peak value. If sigma is different from zero, this point does not correspond to the peak value,
where, for then, lambda in Equation (4) should be denoted as L so that all zero points of Z matrix given in Equation (4) are detected.
3.1. Overview of the System
In the original AMPD algorithm, the best scale is automatically found by using four calculation steps Local Maxima Scalogram (LMS) calculation, Row-Wise summation of the LMS, LMS rescaling, and peak detection. On the other hand, it is necessary to reduce the amount of memory used in this AMPD algorithm while applying it to the FPGA in order to make a simple and effective pipeline design. The reason is that using more steps in application will increase memory usage and low latency. Original and modified algorithm flowcharts were given in Figure 1 and Figure 4 respectively. It was also mentioned that original algorithm flowchart in Figure 1 is more complex and has more steps than modified algorithm flowchart in Figure 4. In modified algorithm, step size is reduced and therefore the memory size is also reduced. If the time complexity (O) of algorithm is analyzed in terms of the flowchart given in Figure 3, total time complexity is found as .
Figure 3. Time complexity of off-line algorithm flowchart.
Since the main target of this study is to apply AMPD algorithm to FPGA, a new algorithm has been proposed where the number of steps of AMD algorithm have been reduced. Figure 4 shows the flowchart about the off-line algorithm. Therefore, there are only two steps in the proposed algorithms: Local Maxima Scalogram and peak detection for the best off-line calculations of peak points. The proposed system cannot straightforwardly calculate the peak points automatically with the low memory of FPGA. When the AMPD algorithm is applied on an FPGA, it can be reprogrammed for desired applications so that a logical gate is needed to make a process. Nevertheless, applying the deviation formula generates the LMS matrix and then all values are kept in registers. Figure 5 shows the hardware design of the overview of implementation where k is the window scale.
In this design, a different element of the matrix in every clock cycle is compared and generated. Matrix generators with input X and output Z are serially connected to take advantage of the pipelining. After completion of generating all values, a basic peak flag is used to determine if a value corresponds to a zero point, that is, if a peak point is detected. Matrix generators are used to shift data sequentially, with the data for each matrix generator being compared with newly sampled data. In this manner, matrix elements of each scale are generated. In
Figure 4. Off-line algorithm flowchart.
Figure 5. Overview of the algorithm flowchart.
one clock cycle, an element of the matrix will be generated, and as a result the summation and square summation are calculated sequentially. Finally, a division is performed to obtain an average and a squared average.
In the original AMPD algorithm, the standard deviation formula is utilized for detecting peak points. This involves rather complex arithmetic such as square root. To improve performance and efficiency of the FPGA implementation, the process is modified to use variance instead of standard deviation. The formula used in this design is in Equation (5), which shows the matrix designed by applying the variance formula to each column. Although both Equation (4) and Equation (5) are suitable for applying the variance, Equation (5) is used in this study due to its easy representation in hardware design.
3.2. Matrix Generator and Decision Mechanism
Figure 6 depicts a Matrix Generator block diagram that is a decision mechanism to generate a matrix by using LMS calculation. It is also a critical part of the LMS calculation. The Matrix Generator requires a decision part for comparing values, which constitutes the major design of the matrix generator module. This module generates a matrix of one scale. The data generated by matrix generator for comparison reason is reduced to store and fed into the shift. The length of the shift register depends on the shift register’s scale.
The input data is stored into the register and the data it is to be compared with will be inputted into the comparator in every clock cycle. Figure 7 is the expanded detailed hardware of the selector section of Figure 6 and it is the decision giving section on the achievement of positive and negative peak detections.
4. Results and Discussion
In this section, the original AMPD algorithm and the modified algorithm are evaluated in detail by comparing their detections of peak points of the same data
Figure 6. Matrix Generator system design.
Figure 7. Selector circuit.
series. First of all, simulation results of both algorithms are given and then compared with each other. Later on, both original and modified algorithms are evaluated at different scales. After that, the sensitivity equation below is applied to each design to find their peak sensitivities.
TP = True Positive.
FN = False Negative.
4.1. Simulation of the Original AMPD Algorithm
In this section, the peak points obtained from the original AMPD method as on-line have been introduced. A simulation has been performed with input data of the phase-to-phase effective voltage values of a medium-voltage transformer located in the Organized Industrial Zone used for the period from October 1 to October 31, 2015. The corresponding dataset contains 4470 data points recorded at 10-min intervals for each L3-L2, L2-L1 and L1-L3 phase-to-phase effective voltages. L1, L2 and L3 denote the power line in order in a 3-phase power system. The daily maximum and minimum peak points detected by the original AMPD method are shown in Figures 8(a)-(c) for L3-L2 (VL3-L2), L2-L1 (VL2-L1) and L1-L3 (VL1-L3) line voltage values, respectively. When these figures are compared in detail, the original AMPD method detects the daily maximum peak points with the sensitivities of 93.75% for VL3-L2, 96.96% for VL2-L1 and 90.90% for VL1-L3. Thus, high numbers of the daily maximum peak points are observed at the time of 06:20, 06:30, 06:50, 07:00, 07:10 and 07:50. Moreover, it detects the daily minimum peak points with the sensitivities of 93.75% for VL3-L2, 96.77% for VL2-L1 and 93.75% for VL1-L3. In addition, identification of most of the daily minimum peak points are done at the time of 10:40, 11:00, 11:10, 17:30 and 19:00. Nevertheless, it should be noted that the original AMPD method introduced in this section has been designed in C Programming Language and it has been run as on-line. Max-Peak Sensitivities and Min-Peak Sensitivities concerning the line voltages are shown in Table 1.
4.2. Simulation of the Modified Off-Line Algorithm
In this section, a similar simulation as in 4.1 has been repeated for the designed Verilog algorithm using the same data. Hardware Description Language (HDL) simulations were performed with a Cadence NC-Verilog simulator. Figures 9(a)-(c) and Figures 10(a)-(c) illustrate the real data in red color with plus sign and modified Verilog algorithm data in green color with a star sign. However, in this case simulation results are obtained from the Verilog design algorithm as off-line.
The daily maximum and minimum peak points detected by the modified AMPD method are depicted in Figures 9(a)-(c) for scale 33 for L3-L2 (VL3-L2), L2-L1 (VL2-L1) and L1-L3 (VL1-L3) line voltage values, respectively.
The daily maximum and minimum peak points detected by the modified AMPD method are depicted in Figures 10(a)-(c) for scale 1025 for L3-L2 (VL3-L2), L2-L1 (VL2-L1) and L1-L3 (VL1-L3) line voltage values, respectively.
Table 2 represents the positive edge sensitivities at different scales. When the scale was increased, the sensitivities of L3-L2 line voltage were reduced gradually, but positive edge sensitivity of 87.87% was obtained at scales 33, 65 and 129 for L2-L1 line voltage values. Furthermore, the sensitivities of L2-L1 line voltage
Table 1. Max-peak sensitivities and min-peak sensitivities concerning the line voltages.
Figure 8. (a) Daily maximum and minimum peak points detected by the original AMPD method for L3-L2 line voltage values; (b) daily maximum and minimum peak points detected by the original AMPD method for L2-L1 line voltage values; (c) daily maximum and minimum peak points detected by the original AMPD method for L1-L3 line voltage values.
Figure 9. (a) Daily maximum and minimum peak points detected by the modified AMPD method for L3-L2 line voltage values; (b) daily maximum and minimum peak points detected by the modified AMPD method for L2-L1 line voltage values; (c) daily maximum and minimum peak points detected by the modified AMPD method for L1-L3 line voltage values.
Figure 10. (a). Daily maximum and minimum peak points detected by the modified AMPD method for L3-L2 line voltage values; (b) daily maximum and minimum peak points detected by the modified AMPD method for L2-L1 line voltage values; (c) daily maximum and minimum peak points detected by the modified AMPD method for L1-L3 line voltage values.
Table 2. Positive edge sensitivities for different scales and line voltages.
and L1-L3 line voltage remain constant for scales 33, 65 and 129. Nevertheless, they are also reduced at scales 257, 513 and 1025 because of the low frequencies of compared data at these scales. Finally, it is seen that maximum sensitivities are obtained at scales 33 and 65 for all line voltage values. They give almost the same results as the original algorithm.
Table 3 shows the negative edge sensitivities at different scales. As the scale is increased from 33 to 1025, the big changes in sensitivities have been observed for L1-L3 line voltage values. On the other hand, it was seen that maximum sensitivities of 93.54% were obtained at scales 33 and 65 for L2-L1 line voltage values that were almost the same as the original algorithm results. The sensitivities of L2-L1 line voltage values remain constant for scales 33 and 65. However, they are also reduced for the scales 129, 257, 513 and 1025 due to the low frequencies of compared data at these scales. Nevertheless, the sensitivities of L3-L2 line voltage values are constant for the scales 33, 65, 129 and 257, but they are also reduced for the scales 513 and 1025. Lastly, it is seen that negative edge sensitivities are obtained at scales 33 and 65 for all line voltage values. Almost the same results were obtained at scales 33 and 65 as the original algorithm.
Finally, sensitivities of all line voltages of L3-L2, L2-L1 and L1-L3 at higher scales were found very low due to very high sampling periods so that it caused missing the detection of peaks. This can also be explained simply by looking at Equation (1) and Figure 2, where it was seen that, when the scale is increased, the number of detected points are reduced due to an increased number of L in Z matrix. In another case, the sensitivity is also decreased at higher scales due to availability of noises in the signal.
4.3. Evaluation Environments and Method
In this section, the aforementioned hardware designed in Verilog HDL is explained and then device utilization and performance of the modified algorithm on the Kintex-7 XC7K325T  FPGAs are evaluated. As a mapping tool, a Vivado 2016.3 tool was used. Furthermore, the analog-to-digital converters (ADCs) transform analog electrical signals, generally the voltage amplitude, into a sequence of discrete values for data processing purposes. In this study, it was preferred to use a DC919af ADC with 100 MHz maximum system frequency
Table 3. Negative edge sensitivities for different scales and line voltages.
(sampling rate) and it was implemented on the FPGA board. The main target in this study was to increase the scale to observe and analyze the latency, memory usage and performance of the FPGA board. Therefore, different window lengths at various scales were designed to implement and analyze them on the FPGA board. Firstly, the bit size factor was fixed at 12 because there are many ADC compatible with 12 bits. Then the scale of input data was varied such as 33, 65, 129, 257, 513 and 1025 scales for comparison of resource usage, the result of which is shown in Table 4.
As seen in Table 4, when the scale is increased, an increase is detected directly from some slice logic utilization such as the number of slice LUTs, BRAMs, FFs, and DSP48E1 blocks, as well as the latency. In addition, design algorithm uses on-chip memory blocks (BRAMs) since the entire process is mapped on a pipelined structure based on shift registers. In terms of performance, the latency of peak detection was 23 clock cycles for the scale of 33. When each input data element has 12 bits, the maximum clock frequency is 144.927 MHz in Table 4. Furthermore, the maximum frequency was adjusted to 126.438 MHz in Table 4 by using scale 1025 input sources.
4.4. Evaluation of the AMPD Method with an FPGA Board
An evaluation of the AMPD method with an FPGA board is done in this section. Table 5 gives information on the performance of latency at 100 MHz timing constraint for two different scales. To state the purpose of detecting the peak points efficiently, the approach in this study achieves the real-time peak detection based on AMPD algorithm on an FPGA. When implementing AMPD algorithm on the FPGA board, bit size was chosen as 12, which was compatible with the ADC and 100 MHz maximum system frequencies.
Figure 11 shows the overview of the experiment system. First, FPGA sends the starting signal to the ADC. Then ADC sends 12 bits input data and 100 MHz system clock signal to the FPGA. Finally, the designed algorithms successfully detect all peak points as illustrated in Figure 14 and Figure 15. In particular, two different AMPD algorithms were designed with scales 65 and 33 due to having best sensitivities. Although the system can successfully detect peak points at both scales, the latency is taken into account for the performance. When scale
Figure 11. Overview of the proposed system.
Table 4. Resource usage with different scales.
Table 5. Performance of different scales.
33 is selected, the latency is around 320 ns. This latency is a combination of ADC latency and algorithm calculation latency. When scale 65 is selected, total latency becomes around 502 ns because the window scale increases. Accordingly, the more the scale increases, the less the upper limit frequency becomes. The upper limit frequency is obtained by increasing the frequency from signal generator up to losing output signal.
Table 5 provides information on latency and maximum upper limit frequency for different scales with a fixed bit size and system clock frequency. This table shows the evaluation result of the two different scales of 33 and 65. Furthermore, upper limit frequencies indicated the maximum time step of execution of the algorithm.
While the system is operating, the delay time is composed of two critical parts as algorithm calculation and converter as well as transmitting wire. For instance, when we implemented scale 65, we detected 502 ns total latency time from the oscilloscope screen depicted in Figure 14. To calculate its component for the calculation of algorithm, latency clock cycle at scale 65 in Table 4 is divided by constraint system clock frequency (100 MHz) first so that algorithm calculation time is found as 40/100 = 0.4 [μs] = 400 [ns]. Then, it was subtracted from the total latency time, 502 ns, read from the oscilloscope in Figure 14, in order to calculate the converter and transmitting wire part as 502 [ns] - 400 [ns] = 102 [ns]. Figure 12 shows detail about latency for scale 65.
This calculation is repeated for the scale 33 to make the distribution of latency time clearer and understandable. At scale 33, total latency time is measured as 320 ns from the oscilloscope screen in Figure 15. From Table 4, algorithm calculation time is found by dividing the latency clock cycle by constraint system clock frequency (100 MHz). So it is calculated as 23/100 = 0.23 [μs] = 230 [ns]. After that, when this time is subtracted from total latency measure, converter and transmitting wire part can be calculated as 320 [ns] - 230 [ns] = 90 [ns]. Figure 13 shows detail about latency for scale 33.
Figure 12. Latency of scale 65.
Figure 13. Latency of scale 33.
Figure 14. Peak detect with 3.005 MHz sinusoidal signal.
Figure 15. Peak detect with 6.148 MHz sinusoidal signal.
algorithm can effectively detect all peak points on the positive edge. Figure 14 illustrates that designed algorithm can fully detect all peak points on the positive edge. This algorithm produces the peak points with synchronized 3.00 MHz sinusoidal signals. This implementation result shows scale 65, 12 bit size and around 502 ns total latency time and a maximum frequency of around 3 MHz. Figure 15 shows all of the peak points on positive edge with synchronizing 6.148 MHz sinusoidal signal. This implementation result shows scale 33, 12 bit size, around the 320 ns latency time and a maximum frequency of around 6 MHz.
In this paper, a novel modified AMPD method was implemented on an FPGA. It was highlighted that the modified AMPD mechanism could be implemented as a pipelined hardware on an FPGA, and that fast detection latencies (320 ns and 502 ns for scales 33 and 65) could be achieved with a reasonable amount of hardware resources by slightly modifying the original on-line algorithm to fit the off-line processing. It was also demonstrated that the modified AMPD mechanism detects peak points from noisy time series data of the phase-to-phase effective voltage values of a medium-voltage transformer located in the Organized Industrial Zone.
Thus, modified AMPD algorithm has been proposed and evaluated by using different scales on an FPGA board. The proposed approach has achieved real-time peak detection based on AMPD algorithm on an FPGA. The latency was also presented at different scales from 33 to 1025. The codes written in real time were implemented and results were compared with simulation results to achieve the main target of this study. Although both scales can effectively detect the peak points, the latency was taken into account for the performance on the ADC and algorithm calculating time. So peak sensitivities obtained from on-line original AMPD were compared with the sensitivities obtained from off-line modified algorithm using the same data. It was observed that scales 33, 65, 129 and 257 produced more or less successful results. In terms of the peak sensitivities, scales 33 and 65 produced similar results as the original AMPD that was proposed in this study. That means the proposed novel mechanism can be used as an off-line robust and real-time peak detection algorithm by combining the AMPD algorithm and the FPGA technology.