{'fraction_non_alphanumeric': 0.03459190594619037, 'fraction_numerical': 0.01740899841736378, 'mean_word_length': 4.021798365122616, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Performance Evaluation of Periodic Signal Analysis by ARS Compared with Frequency Analysis by FFT

Accumulation for real-time serial-to-parallel converter (ARS) has been proposed as a computationally-efficient method for signal analysis. Since it consists of additions and a few divisions only, it was shown that the computational load is drastically reduced compared with the fast Fourier transform (FFT). In this paper, we clarify that ARS achieves a higher resolution in low-frequency bands comparing with FFT. In addition, selection criteria between ARS and FFT are clarified theoretically in terms of the resolution. Through the performance analysis of ARS in low-frequency bands, it is expected that ARS is a powerful tool for signal analysis in the Internet of Things realizing the edge computing.


Introduction
The frequency analysis of signals based on fast Fourier transform (FFT) has been quite typical in a variety of fields [1]- [8]. Associated with the Internet of Things (IoT), the monitoring of machines [9], vital signs [10], and large structures such as bridges or buildings [11] are applications where the frequency analysis is the first step of sensor output analysis.
From the IoT perspective, edge computing [12] is a key for its implementation. Figure 1 shows an image of an IoT system. Sensor nodes installed on machines, living bodies, or large structures send data, i.e., samples of sensor output, to a cloud computing platform through wireless links. In this system, the collected data are analyzed on the cloud platform. However, as shown in Fig. 2, the bandwidth of the wireless links is often limited to cope with a number of sensor nodes. In addition, the signal power is also limited to reduce the power consumption of the sensor nodes since they are driven by batteries. Thus, it is not cost-effective to send data as it is, in terms of the bandwidth of the wireless links and the power consumption.
The concept of edge computing is attractive to solve this problem [13]. It is to analyze the data at the sensor node before sending it to the cloud, aiming to reduce the data amount sent over the wireless links. For example, we can think about the configuration of the sensor network, as shown in Fig. 3 where the output of an acceleration sensor [14] is fed into an FFT processor. This configuration allows us to selectively send interesting parts of the results obtained through frequency analysis.
Although the data amount is drastically reduced by the edge computing, the power consumption of the sensor node results in the shortage of the battery. In such systems, the battery life of the sensor node is crucial in practice [15]. Therefore, the analysis should not be complicated in order to suppress the power consumption [16]. Although FFT is known as a simple method for frequency analysis [17], another simpler approach for signal  analysis must be able to contribute to the edge computing.
In [18], the accumulation for a real-time serial-to-parallel converter (ARS) was proposed for the signal analysis applicable to non-contact vital sensing using Doppler sensors. ARS analyzes signals over the period axis, not over the frequency axis. As a result, ARS reduces the computational load up to approximately 1/100 since it consists of additions and a few divisions only without multiplications. It is suitable for the implementation of edge computing in the monitoring of vital signs such as heartbeats and respirations measured by Doppler sensors [19]- [21].
In this paper, we theoretically and numerically examine the relationship between the period analysis by ARS comparing with the frequency analysis by FFT in terms of the frequency JCMSI 0005/20/1305-0240 c 2020 SICE resolution.
As a result, it will be shown that ARS achieves higher resolution in low-frequency bands comparing with FFT. It has been known that the frequency analysis by FFT cannot achieve high resolution in the low-frequency band. Vital signs and or vibrations of large structures are typical examples where the low-frequency band is meaningful in the monitoring [22], [23]. This paper clarifies that it is better to apply the period analysis by ARS rather than FFT for low-frequency signals providing selection criteria.

Formulations of Signals
This section mathematically defines and formulates signals in the system. Figure 4 depicts a configuration of the sensor node. The sensor output x (t) is sampled by an analog-to-digital converter (ADC) where the sample period is set at T S . The sampling is expressed as follows: where k is an integer as a discrete time index. The sampled sensor output x [k] is fed into a processor where the signal analysis is performed. The result of the signal analysis is sent through a wireless link via wireless front-end. Assume that the sampled signal x [k] consists of N periodic signals s n [k] where n = 0, . . . , N − 1 and the unit-power noise η [k] as follows: where τ n denotes the unknown time offset of s n [k] while P η corresponds to the noise power. The n-th sampled sensor output is modeled by concatenating fundamental waveforms φ n [k] whose periods are T n as follows: where, P (n) S is the power of the n-th signal. In addition, M n is the number of the fundamental waveform connected in the signal s n [k].
The goal of the period estimation is to estimate T n and the number of signals (NoS) N.

An Overview of ARS
This section provides an overview of ARS to facilitate understanding followed by detailed explanations. It will be shown that ARS is realized by additions and a few divisions only without multiplication so that ARS enables us to drastically reduce the computational complexity. This must be an advantage for edge computing in IoT systems aiming to reduce the power consumption of the sensor node.

Principle of ARS
Prior to the detailed explanations, some intuitive images of ARS are explained. Figure 5 depicts an image of a serial-toparallel converter (SPC). Suppose that the SPC is equipped with u output ports. In this case, the SPC consists of u memories where the SPC input samples are sequentially stored. Then, as depicted in the figure, the SPC outputs the stored samples simultaneously when all of the memories are filled with the input samples. Based on the mechanism of the SPC, in Fig. 6, it is illustrated that a sample sequence whose period is six samples is fed into a 6-port SPC. In this case, observing the output ports of the SPC, it is certain that we will see always the same combination of six outputs values. Therefore, the accumulation of the SPC outputs during g = 0, . . . , G − 1 produces large values in terms of the amplitude. It should be noted that this situation occurs because the period of the input sequence is equal to the number of the SPC output ports. Figure 7 depicts a situation similar to the previous figure except the fact that the period of the input sequence is not equal to the number of the SPC output. The period of the input sequence is six samples while the SPC is equipped with seven ports. In this situation, we can imagine that combinations of seven output values of the SPC are not always the same, as depicted in Fig. 7. Thus, the accumulation of the SPC outputs in this situation does not produce large values in terms of the amplitude.
The essence of ARS is the following procedure for the period estimation as shown in Fig. 8 3. Identify the maximum value of the accumulated SPC outputs in terms of the amplitude at each SPC.  5. Identify the SPC having the largest amplitude value. Then, the number of output ports of the SPC corresponds to the period of the input sequence.

Detailed Definitions of ARS
Based on the principle intuitively explained in the previous section, this section clarifies the detailed processing by ARS through mathematical expressions. Figure 9 illustrates the whole configuration of ARS. There are V SPCs identified by the SPC ID #v (= 1, . . . , V). Let u v denote the number of the SPC output ports of SPC #v. Although it can be arbitrary set, here we defined it as follows: It means that SPC #1 is equipped with U output ports. Let a vector x v [g] of size (u v × 1) denote the gth output (g = 0, . . . , G − 1) of SPC#v as follows: x Then the SPC outputs are accumulated. This accumulation is formulated as follows: where the elements ofx v are defined aŝ Next, the maximum element in terms of the amplitude at SPC #v is defined as follows: Finally,x v is defined as follows: where G v is defined as where a denotes the maximum integer less than a. This division is needed if the length of the input sequence x [k] is limited at G. In such a situation, the number of outputs at each SPC is not always equal among the SPCs depending on the number of the output ports u v . The difference of the number of SPC outputs is compensated by the division in (9). Finally, NoS and the period of the multiple periodic signals are estimated as follows: The obtainedx v (v = 1, . . . , V) is sorted as where D (q) , q = 1, . . . , V is to convert the sorted order q to the SPC ID. Note that the elements of the vectorx are normalized byx D(1) , the maximum value. Aiming to identify peaks corresponding to the signals, we set a criterion δ (0 < δ ≤ 1) and identify the elements ofx larger than δ. NoS is estimated as the number of the elements ofx larger than δ. Based on (4), the periods of each of the signals are estimated as follows: In addition, according to (12), it should be noted that ARS is capable of distinguishing two signals if the difference of the periods |T n − T n+1 | is larger than T S . In other words, the period resolution of ARS is equal to T S .

Decision of the Number of SPCs
The decision of the number of SPCs is an important realistic issue. In practice, there is often a clue about the frequency or the period of target signals since we know where the target signals came from. For example, if we know that the target signal is an output signal of a sensor monitoring respirations of a human, the period of the signal must be around a few seconds. This is the information that enables us to decide V, the number of SPCs, and u v (v = 1, . . . , V), the number of output ports of the v-th SPC.
If there is completely no information about the target signal, even though it is unusual in reality, it is even difficult to identify the sampling frequency. Assuming that we could somehow decide an appropriate sampling frequency, ARS needs sufficiently large V. However, it should be noted that this is not an inherent problem of ARS. FFT also faces another problem how to decide the length of the input signal which affects the resolution of the frequency analysis.

Performance Analysis
In this section, we examine the superiority of the period analysis realized by ARS comparing with the frequency analysis by FFT. This section consists of the following two parts: The first part clarifies the superiority of the period analysis by ARS in terms of the period resolution compared with the frequency resolution by FFT. Then, the second part reveals that the period analysis by ARS reduces the sample acquisition time to achieve a certain resolution compared with the frequency analysis by FFT.
In both investigations, finally, the conditions to achieve a situation in which ARS is superior to FFT will be clarified from a theoretical point of view. Figure 10 (a) illustrates the power spectrum where the horizontal axis is converted to the period as shown in Fig. 10 (b). Naturally, the higher frequency in Fig. 10 (a) corresponds to the short period in Fig. 10 (b). In this figure, f S and N F denote the sampling frequency and the degree of FFT, i.e., the number of samples, respectively. In addition, n F (n F = 0, 1, . . . , N F − 1) is a frequency index. In FFT, the frequency resolution R F is defined as follows:

Relation between Frequency and Period Domain
So the frequency of the n F -th output of FFT corresponds to the frequency n F R F (Hz). Now, in Fig. 10 (a), let us focus on the frequency band ranging from n F = 2 to Ψ, i.e., 2R F (Hz) to ΨR F (Hz). This frequency band is mapped to the period axis, as shown in Fig. 10 (b), to 1/(ΨR F ) (s) to 1/(2R F ) (s).
Note that, as shown in Fig. 11, the frequencies mapped to the period axis cannot be equally spaced, even though they were aligned on the frequency axis with equal intervals. In other words, the resolution on the period axis is not constant.
However, as shown in the same figure, we find that the period can be estimated by ARS with the equally-spaced points on the period axis. In other words, the period resolution is constant. Therefore, if the period of the signal is relatively long, the resolution achieved by ARS is higher than that of FFT in the frequency domain. Now the problem is clarified. When is the reslution of ARS higher than that of FFT? What are the conditions? The clarification of these points is the goal of this paper.

Period Resolution of FFT and Its Limitations
As we have seen, the frequency analysis and the period analysis are different in terms of the resolution even though they seem similar. In this section, more precise discussions will be provided in order to clarify the conditions enabling us to select ARS or FFT depending on several parameters. Figure 12 shows the relationship between the frequency n F R F on the horizontal axis versus the period-converted frequency 1/(n F R F ) on the vertical axis. The sampling frequency and the number of input samples are set at f S = 100 Hz, and N F = 2 12 samples, respectively.
This figure indicates the following facts: • Around 0.4 Hz (0.39 Hz to 0.42 Hz, Δ f = R F = 100 2 12 ), the period resolution is ΔT 1 = 0.15 s.  This figure clearly shows the fact explained in the previous section. In this setting, ARS achieves the period resolution T S = 1/ f S = 0.01 s where T S < ΔT 2 < ΔT 1 , so it is found that ARS achieves higher resolution compared with FFT in these frequency bands since the period resolution of ARS is equal to T S as explained in Section 3.2.

Comparison between ARS and FFT in Terms of Period Resolution
This section clarifies the superiority of the period analysis by ARS in terms of the period estimation, compared with FFT. Let us take a look at Fig. 13. The band to be analyzed by FFT is given as B FFT while that analyzed by ARS is specified as B ARS . It should be noted that the minimum frequency of B ARS is set at 2R F because we need to obtain the output of the SPC #V at least two times to be accumulated at the accumulator. Now, recall that the frequency resolution R F becomes higher when the number of samples N F increases. So, we investigate the effect of the increase in the number of samples in terms of the period resolution. The period resolution is defined as follows: Figure 14 shows the period resolution ΔT (n F ) versus n F . In ad-  dition, Fig. 15 shows the period resolution ΔT (n F ) versus n F R F to facilitate an understanding of Fig. 14 on the frequency axis.
The sampling frequency f S is set at 100 Hz. In both figures, the curves show the period resolutions as a function of n F or n F R F of the α-degree FFT (α = 9, . . . , 18). The period resolution of ARS must be flat in these figures at 0.01 s as shown by a black solid horizontal line. So, the period resolution of ARS and FFT are equal at the cross points of the curves and the horizontal line at 0.01 s. It means that ARS is superior to FFT in terms of the period resolution in the area above the horizontal line. Table 1 provides the precise values of the cross points as well as 2R F , i.e., the lower bound of B ARS , and X defined as follows: According to these results, for example, ARS is better than 11-degree FFT in terms of the period resolution in the range 0.0977 Hz ≤ f ≤ 2.1484 Hz. This corresponds to 0.4654 s ≤ T ≤ 10.2354 s, so it is sufficient for vital sensing such as the sensing of respirations and heartbeats.

Comparison between ARS and FFT in Terms of Sample Acquisition Time
Now, we consider the number of necessary samples for ARS. As explained in Section 3.1, ARS, like FFT, does not require any specific number of samples. Therefore, we will compare the necessary number of samples for ARS and FFT under the equivalent setting in terms of the period resolution. For ARS, the period resolution is 0.01 s defined by the setting of sampling frequency f S = 100 Hz, as mentioned above. Now, we think about FFT whose period resolution is the closest to 0.01 s.   Figure 16 illustrates the image of the consideration. Figure 16 (a) shows B FFT on the frequency axis while Fig. 16 (b) shows their mapping on the period axis. Since the period is obtained as the inverse of the frequency, the interval on the period axis is not equal even though it is the equal interval on the frequency axis. Recall that n F is the frequency index. Now, we define the frequency indexn F ∈ {0, . . . , N F − 1} as the frequency index whose period difference is the closest to 0.01 which is the period resolution of ARS, i.e., Then, the necessary number of SPC input samplesN ARS at the SPC whose period is 1/(n F R F ) is given as follows: where β is an integer larger than 2, i.e., β = 2, 3, . . .. By using this variable, we can define the number of output waveforms obtained at the output ports of the SPC whose period is 1/(n F R F ). Under low SNR conditions, ARS requires large β. Table 2 shows the relationship between α, the degree of FFT, andn F , the frequency index corresponding to the period resolution 0.01 s, as defined in (16). Additionally, the values ofn F R F   Figure 17 showsN ARS 2 α as a function of β. The vertical axisN ARS 2 α shows the ratio of the necessary number of samples for ARS to that for α-degree FFT. Therefore, ARS is more advantageous than FFT in terms of the sample acquisition time in the region whereN ARS 2 α < 1.
For example, this figure shows that ARS is advantageous compared with 11-degree FFT even if β is set at 31, in terms of the sample acquisition time, under the same setting of the pe-  Table 3 lists β at the cross points of the linê N ARS 2 α = 1 and that of α = 5, . . . , 18.

Numerical Examples
This section provides numerical examples of the period analysis comparing with the frequency analysis for low-frequency signals. Through these examples, we can numerically verify the borders of the performance of ARS and FFT, derived in Chapter 4. Table 4 shows the parameter settings of two periodic signals as inputs for the numerical examples. This table contains two types of settings, namely Settings 1 and 2.

Setting 1: FFT Is Better than ARS
In Setting 1, FFT is superior to ARS in terms of the period resolution. This is confirmed as follows: There are two sine waves whose periods are set at 33 and 31 samples, corresponding to n F = 122 and 131. Then, moving onto Fig. 14 with these settings n F = 122 and 131, we can see that the cross points of n F = 122, 131 and the curve α = 12 are located in the area where FFT is better than ARS in terms of the period resolution. It is obviously verified that FFT is better than ARS comparing Figs. 18 and 19. Note that the horizontal axis in Fig. 19 is converted to the frequency. Although ARS does not separately detect the two signals in Fig. 19, FFT successfully detects the signals in Fig. 18.

Setting 2: ARS Is Better than FFT
Now, let us focus on Setting 2 in Table 4 where ARS is better than FFT. This is confirmed as follows: There are two sine waves whose periods are set at 142 and 133 samples, corresponding to n F = 29 and 31. Then, moving onto Fig. 14 with these settings n F = 29 and 31, we can see that the cross points of n F = 29, 31 and the curve α = 12 are located in the area where ARS is better than FFT in terms of the period resolution. It is obviously verified that ARS is better than FFT comparing Figs. 20 and 21. Note that, again, the horizontal axis in Fig. 21 is converted to the frequency. Although FFT does not separately detect the two signals in Fig. 20, ARS successfully detects the signals in Fig. 21. It should be emphasized that, in Setting 2, the number of samples fed into ARS is 2660 while FFT requires 2 12 = 4096 samples, i.e., ARS achieves better performance with fewer samples. It contributes to the reduction of the sample acquisition time so that the measurement can 142 (≈ 0.7 Hz (n F = 29)) Period4 (sample) 133 (≈ 0.75 Hz (n F = 31)) Sample sequence for FFT 2 12 Sample sequence for ARS 2660 Fig. 18 The power spectrum obtained by FFT for Setting 1 in Table 4. Fig. 19 The spectrum obtained by ARS for Setting 1 in Table 4. be accelerated by ARS in practice.

Conclusions
Throughout this paper, we have considered the relationship of the performance achieved by ARS and FFT. Such techniques for signal analysis are playing important roles than ever due to the emergence of the IoT, particularly from the edge computing perspective. For the realization of edge computing, the simplicity and low power consumption of ARS are attractive. This paper has aimed to clarify the superiority of ARS in terms of the period resolution and data acquisition time compared with FFT as a typical method of signal analysis which has been widely used in a variety of applications.  Table 4.  Table 4.
Firstly, focusing on the period resolution, Fig. 15 was obtained to show the area where ARS is advantageous to FFT. For example, ARS is better than 11-degree FFT in terms of the period in the range 0.0977 Hz ≤ f ≤ 2.1484 Hz. This corresponds to 0.4654 s ≤ T ≤ 10.2354 s, so it is sufficient for vital sensing such as the sensing of respirations and heartbeats.
Secondly, focusing on the data acquisition time, Fig. 17 was obtained to show the area where ARS is advantageous to FFT in terms of the data acquisition time. These points were verified through several numerical examples.
Concludingly, this paper clarifies the selection criteria of ARS and FFT. Naturally, it is emphasized that ARS is not always superior to FFT. Adding one new method in the field of signal analysis by ARS, it is expected that we will be able to expand the application of IoT based on edge computing configuration.