Recent advances in crest factor minimization of multisine.
The multisine signal is widely used in many applications. It allows faster estimation of the frequency response function (FRF) in comparison with stepped-sine at different frequencies  and faster impedance spectroscopy measurements . There are many other fields of application of multisine like acoustics  and communications . The multisine signal s(t) is defined as a sum of harmonically related sinusoids
s(t) = [[summation].sup.k.sub.i=1][A.sub.i] x sin[2[pi][f.sub.i]t + [[PSI].sub.i]], (1)
where [A.sub.i] is the amplitude, [f.sub.i] is the frequency of i-th component, and k is a number of components. Note that [[PSI].sub.i] refers the initial phases of sine waves, but not cosine waveforms, which are often used when discussing minimization algorithms of crest factor (CF) as in . If the signal does not have DC component, i is an integer in the range from 1 to k. The index i also denotes normalized frequency bin that is normalized against the unit frequency [f.sub.1] that is [f.sub.i] = [f.sub.1] x i.
Multisine has the flexibility to create a signal with an arbitrary spectrum. However, the multisine with random phases typically produces relatively high peak values of the waveform which is usually characterized by the crest factor (CF), the ratio of signal peak value to its root mean square (RMS) value. In practice, peak values of the signal are limited, and the maximum power of the signal is directly related to its CF. Moreover, signal to noise ratio (SNR) depends on signal power. It follows that lower CF of the excitation signal provides higher accuracy of FRF and impedance spectroscopy measurements.
CF of the multisine signal with a given magnitude spectrum depends only on its initial phases <J>,. Much research has been done for the minimization of CF during last five decades, but the solution is still an open mathematical problem .
A. Analytical Method
Schroeder  noticed a low peak factor of the frequency-modulated signals and his formulas are based on intuitive concept concerning an asymptotic relationship between the power spectra of signals and their instantaneous frequencies. He proposed an analytical solution for the multisine CF minimization through a simple formula
[[PSI].sub.i] = [[PHI].sub.1] - 2[pi] [[summation].sup.k-1.sub.i=1] (k - i)[p.sub.i], (2)
where [p.sub,i] is a relative power of the i-th component. In the case of equal powers (also amplitudes) of the signal components (2) reduces to
[[PHI].sub.i] = [[PHI].sub.1] - [pi] [i.sup.2]/k. (3)
where [[PHI].sub.1] is an ad hoc addend in (2) and (3), which was added by Schroeder  empirically to obtain more appropriate values for the initial phases [[PHI].sub.i] of signal components enabling so to achieve the lowest CF.
Later here we use phase angle units in degrees. CF of the multisine signal with [[PHI].sub.i] according to (2) and (3) depends not only on variables i and k but also on the distribution of normalized frequencies and value of the parameter [[PHI].sub.1]. The Schroeder's method produces acceptable but not the best CF for the signal with equal amplitudes of components and consecutive frequencies (i = 1, 2, 3, 4, ..., k), see Fig. 1. Minimal CF (solid line in Fig. 1) is obtained when optimal values of [[PHI].sub.1] are used for calculation of [[PHI].sub.i]. Optimal values are found by the minimum of the CF when varying [[PHI].sub.1] in the range from 0 to 180 degrees in steps of 1. For the best results, it means that this method is not fully analytical since the 180-step search is required for each value of k.
In the case of sparse distributions, e.g. with the logarithmic distribution of frequencies, minimization results are not as good as shown in the next section.
Several other analytical formulas have been proposed but all with less performance compared to Schoeder's formula as discussed in  and also confirmed by our calculations.
B. Numerical Methods
Unlike the analytical approaches, numerical methods have no explicit formula but generate lower CF multisines using iterative algorithms. Typically these methods start with random initial phases of components - or with initial phases calculated using Schoeder's formula e.g. in , . In the next steps, some parameters of the signal are varied, and the process is repeated when registering <J>, of variants with lower CF.
An exhaustive search of all the possible phase combinations provides the best results, but the number of calculation steps [n.sub.stp] increases in the power of k-1 and therefore is practical only for k < 6. In  an algorithm is proposed that drastically decreases Htp. However, it is still too high for k > 20. Other solutions, as nonlinear Chebyshev method  and genetic algorithm  provide relatively good results
but become time-consuming with large k .
In the iterative algorithm described in  and , extremal amplitudes of the multisine signal are clipped by a fixed level. Then the modified multisine is calculated using the discrete Fourier transform (DFT). The obtained phases are recognized as the improved ones, if the multisine acquires lower CF. The algorithm will be repeated from inverse DFT (IDFT) to DFT using the new [[PHI].sub.i] until the clipped multisine no longer has lower CF. An improved VDO algorithm  modifies this method. It adopts the Schroeder phases as the initial phases and uses variable clipping level based on logarithmic function in the iteration procedure. This algorithm produces low CF similar to values obtained by method  but is significantly faster in the case of large k.
II. NEW FORMULAS
Investigation of different variants resumes in following three simple formulas that behave better with sparse frequency distributions and in the first case also with denser distributions, e.g. i = 11, 12, 13, ... k:
[[PHI].sub.i](k) = [[summation].sup.k.sub.i=1] B x i = (I x B) x i = B [i.sup.2], (4)
[[PHI].sub.i](k) = 180B/i, (5)
[[PHI].sub.i](k) = 180B / [square root of i]. (6)
The concept of our formula (4) is based on the uniform increase of initial phases of multisine components that is achieved by summation of the value of parameter B. Additional multiplication by i ensures equal phase shift of signal components of harmonically related frequencies. Formulas (5) and (6), in the opposite, are producing nonuniformly decreasing initial phases of multisine components. In all cases, a step size of phase changes depends on the value of B.
Results of the CF calculations with different formulas for the consecutive frequency distribution is shown in Fig. 2, for the logarithmic distribution in Fig. 3 and the denser distribution in Fig. 4. In all cases, parameter B is varied in the range from 0 to 180, and minimal values of CF are selected. In Fig. 3, the best-known optimization results obtained with an iterative algorithm are also shown.
Calculations with other sparser frequency distributions also showed better performance in comparison with Schroeder's formula. Use of (5) and (6) is not efficient in the case of consecutive or dense frequency distributions as shown in Fig. 2 and Fig. 4. Nevertheless, these formulas may be still valuable for the calculation of initial phases in iterative algorithms.
III. ENHANCED ITERATIVE ALGORITHM
In the case of using iterative algorithms, the converging of the minimization to the global minimum is not guaranteed even in the case of using sophisticated algorithms , . Also recently introduced improved VDO method  may stuck in local minima. Our investigation shows that the variation of the parameter <J>i in (3) may considerably influence the minimization result, see Fig. 5. Here the CF is normalized against the CF of single sinewave ([square root of 2]).
Moreover, use of (4)-(6) instead of (3) may provide in some cases better results as illustrated in Fig. 6. The specific situation depends on the distribution of frequencies, the number of components k and their magnitudes.
Further investigation of the algorithm  shows that the minimization results can be further improved if the logarithmic clipping sequence is calculated more than once see an illustration of the minimization process in Fig. 7.
Note that after the end of the clipping sequence, the next sequence is shown below at the same starting time, i.e., the time scale is relative in Fig. 7.
Considering the described circumstances the flow chart of the iterative algorithm described in  was modified for better performance as shown in Fig. 8.
Two additional iteration loops are added. The first one varies the value of parameter B and the second repeats clipping sequences. Furthermore, different formulas may be selected for the calculation of initial phase set of the iterative algorithm. The drawback is a longer calculation time, but this is not crucial. As an example, optimization result of the multisine with 152 components and normalized frequencies from 100 to 10000 is shown in Fig. 9. The PC has Intel[R] Core[TM] i7-2600K CPU running at 3.40GHz, 4 cores, 8 logical processors and 16 GB of RAM. The software was developed with the National Instruments Lab VIEW software environment running the 64-bit Microsoft Windows 7 operating system.
The CF values in lower plots of Fig. 1 and Fig. 3 are also obtained with the enhanced iterative algorithm. As an example, CF of multisine with 26 components is 1.365.
Several new formulas were developed for the CF minimization of multisine signals that outperform well-known Schroeder's formula in the case of the sparser frequency distribution of components. Most efficient is the formula (4) that also has a good performance with denser frequency distributions, e.g., see results in Fig. 4.
The drawback of proposed formula is that it is not fully analytical--a search with several hundreds of calculation steps is required. However, it is still a good alternative in comparison with more complicated iterative algorithms, which require substantially more computational resources.
Moreover, it is shown that new formulas may improve the minimization efficiency when used for calculation of an initial set of phases for iterative algorithms.
Enhanced iterative CF minimization algorithm developed by us (Fig. 8) was tested with different frequency distributions. The lowest known values for the crest factor CF were obtained. The influence of implemented parameters as values of initial conditions, formulas used for their calculation, and repeated clipping sequence are discussed. Better avoiding of local minima with proposed algorithm allows moving toward the global minimum.
 Y. Yang, F. Zhang, K. Tao, B. Sanches, H. Wen, Z. Teng, "An improved crest factor minimization algorithm to synthesize multisines with arbitrary spectrum", Physiol. Meas., vol. 36, no. 5, pp. 895-910, 2015. [Online]. Available: https://doi.org/10.1088/09673334/36/5/895
 J. Ojarand, M. Min, "Crest factor optimization of the multisine waveform for bioimpedance spectroscopy", Physiol. Meas., vol. 35, pp. 1019-1033. 2014. [Online]. Available: https://doi.org/10.1088 /0967-3334/35/6/1019
 A. Homer, J. Beauchamp, "A genetic algorithm-based method for synthesis of low peak amplitude signals", J. Acoust. Soc. Am.. vol.99, no. 1. pp. 433-443. 1996. [Online]. Available: https://doi.org/10.1121/l.414555
 A. De Angelis, J. Schoukens, K. R. Godfrey, P. Carbone, "Practical issues in the synthesis of ternary sequences", IEEE Trans. Instrum. Meas., vol. 66. no. 2. pp. 212-222. 2017. [Online]. Available: https://doi .org/10.1109/TIM.2016.2622778
 M. Schroeder, "Synthesis of low-peak-factor signals and binary sequences with low autocorrelation", IEEE Trans. Inf. Theory. vol. 16. pp. 85-89. 1970. [Online]. Available: https://doi.org/ 10.1109/TIT.1970.1054411
 A. Van den Bos, "A new method for synthesis of low-peak-factor signals", IEEE Trans. Acoust. Speech Process., vol. 35, pp. 120-122, 1987. [Online]. Available: https://doi.org/10.1109/TASSP.1987. 1165028
 e. Van der Ouderaa, J. Schoukens, J. Renneboog, "Peak factor minimization of input and output signals of linear systems", IEEE Trans. Instrum. Meas., vol. 37, no. 2, pp. 207-212, 1988. [Online]. Available: https://doi.org/10.1109/19.6053
 e. Van der Ouderaa, J. Schoukens, J. Renneboog, "Peak factor minimization using a time frequency domain swapping algorithm", IEEE Trans. Instrum. Meas., vol. 37. no. 1. pp. 145-147. 1988. [Online]. Available: https://doi.org/10.1109/19.6053
 P. Guillaume, J. Schoukens, R. Pintelon, I. Kollar, "Crest-factor minimization using nonlinear Chebyshev approximation methods", IEEE Trans. Instrum. Meas., vol. 40. pp. 982-989. 1991. [Online]. Available: https://doi.org/10.1109/19.119778
 M. S. Ong. Y. C. Kuang. P. S. Liam. M. P. Ooi. "Multisine with optimal phase-plane uniformity for ADC testing", IEEE Trans. Instrum. Meas., vol. 61. pp. 566-578. 2012. [Online]. Available: https://doi .org/10.1109/TIM.2011.2169614
Jaan Ojarand (1), Mart Min (1)
(1) Thomas Johann Seebeck Department of Electronics, Tallinn University of Technology, Ehitajate tee 5, 19086 Tallinn, Estonia
Manuscript received 3 November, 2016; accepted 11 March, 2017.
This research was supported by Estonian Research Council grant IUT1911 and the European Regional Development Fund in frames of the Estonian Center of Research Excellence EXCITE. The work was partly financed also through the European Research Area project H2020WIDESPREAD-2014-2-668995-Cognitive Electronics.
Caption: Fig. 1. Crest factors of the multisine signal with normalized frequencies i = 1, 2, 3, 4, ..., 30; initial phases are optimized with the best known numerical method (the lowest dashed line), with Schroeder's method using optimal [[PHI].sub.1] (solid line), with Schroeder's method using [[PHI].sub.1] = [+ or -] 90[degrees] (dotted line), and Shroeder's method using [[PSI].sub.1] = 0[degrees] (upper dashed line).
Caption: Fig. 2. CF of the multisine signal with normalized frequencies i = 1, 2, 3, 4, ..., 30 calculated with (3)--solid line, with (4)--line with shorter dashes, with (5)--line with longer dashes, and with (6)--dotted line.
Caption: Fig. 3. CF of the multisine signal with normalized frequencies i = 3, 5, 7, 17. 31. 67. 127. 257. 511. 1021 calculated with (3)--upper solid line, with (4)--line with shorter dashes, with (5)--line with longer dashes, with (6) dotted line, and with iterative numerical method--lower solid line.
Caption: Fig. 4. CF of the multisine signal with normalized frequencies i = 11, 12, 13, 14, ..., 20 calculated with (3)--solid line, with (4)--line with shorter dashes, with (5)--line with longer dashes, and with (6)--dotted line.
Caption: Fig. 5. Variation of the relative CF on parameter [[PSI].sub.1] in (3) of the multisine with 18 normalized frequencies (i = 1, 2, 3, 4, ..., 18) and equal amplitudes of components.
Caption: Fig. 6. Variation of the relative CF on the formula used for calculation of initial phases of the multisine with 18 normalized frequencies (i = 1, 2, 3, 4, ..., 18) and equal amplitudes of components; first parts of the plots calculated with (4) and (5) coincide.
Caption: Fig. 7. The decrease of the relative CF (RCF) in the case of repeating of the clipping sequence 15 times. The multisine has 18 normalized frequencies (i = 1, 2, 3, 4, ..., 18) and equal amplitudes of components; starting points of the RCF values at [[PHI].sub.1] =11 and [[PHI].sub.1] =142 are the same as shown in Fig 5.
Caption: Fig. 8. The flow chart of the enhanced multisine CF minimization algorithm. [B.sub.max] is a maximum value of parameter B, [n2.sub.max] is a maximum number of clipping sequences, and [n1.sub.max] is a number of points of the clipping function. [phi][(i).sub._opt] is a final set of initial phases which corresponds to the lowest CF of multisine.
Caption: Fig. 9. The decrease of the CF (lower plot) and relative CF (RCF) of the multisine during the process of minimization with enhanced iterative algorithm. The signal contains 152 components in the range of i from 100 to 10000.
|Printer friendly Cite/link Email Feedback|
|Author:||Ojarand, Jaan; Min, Mart|
|Publication:||Elektronika ir Elektrotechnika|
|Date:||Feb 1, 2017|
|Previous Article:||A low complexity based spectrum partitioning--ESPRIT for noncontact vital radar.|
|Next Article:||A deep neural network classifier for decoding human brain activity based on magnetoencephalography.|