100 of the interpolated ZC sequence.Finally,we get the path coefficient at 48 kHz sampling rate.After the optimization, measuring the path coefficient at a given delay only incurs one multiplication and two additions for each sample. 6 MOVEMENT MEASUREMENT 6.1 Finger Movement Model Without sampling rate increasin Finger movements incur both magnitude and phase 200 100 0 00 changes in path coefficients.Firstly,the delay for the peak I(normalized) Figure 6:Path coefficient at different sampling rate corresponding to the reflection path of the finger changes when the finger moves.Figure 8(a)shows the magnitude Received x(t) Low-pass baseband signal filter →hn of the IR estimations when the finger is first moving away from the microphone and then moves back.The movement Z-m:a fixed distance is 10 cm on the surface of the mobile device.A"hot" yclic shift of n region indicates a peak at the corresponding distance in the Transmited IR estimation.While we can observe there are several peaks baseband signal x(t-1023)】 is the raw IR estimation and they change with the move- Figure 7:Path coefficient measurement for delay n ment,it is hard to discern the reflection path as it is much cyclically shifted by n points.The key observation is that weaker than the LOS path or the structure path.To amplify ZC sequence has constant power,ie.,ZC[n]x ZC'[n] the changes,we take the difference of the IR estimation along 1,Vn.Thus,each point in the Nzc multiplication results the time axis to remove these static paths.Figure 8(b)shows in Eq.(4)contributes equally to the estimation of h,[n].In the resulting differential IR estimations.We observe that the consequence,the summation over a window with a size of finger moves away from the microphone during 0.7 to 1.3 Nzc can start from any value of t.Instead of advancing the seconds and moves towards to the microphone from 3 to value t by a full frame of 1,024 sample points as in ordinary 3.5 seconds.The path length changes about 20 cm(10 x 2) cross-correlation operations,we can advance t one sample during the movement.In theory,we can track the position of each time.In this way,we can obtain the path coefficient the peak corresponding to the reflection path and measure with a sampling rate of 48 kHz,which gives the details of the finger movement.However,the position of the peak is changes in path coefficient as shown in Figure 6. measured in terms of number of samples,which gives a low The above upsampling scheme incurs high computational resolution of around 0.7 cm per sample.Furthermore,esti- cost.To obtain all path coefficients h[n]for delay n(n=0~ mation of the peak position is susceptible to noises,which 1023),it requires 48,000 dot productions per second and each lead to large errors in distance measurements. dot product is performed with two vectors of 1,024 samples. We utilize phase changes in the path coefficient to measure This cannot be easily carried out by mobile devices.To reduce movement distance so that we can achieve mm-level distance the computational cost,we observe that not all taps in h[n] accuracy.Consider the case the reflection path of the finger is path i and its path coefficient is: are useful.We are only interested in the taps corresponding to the structure propagation paths and the reflection air paths h [ni]=Are-(2) (5) within a distance of 15 cm.Therefore,instead of calculating the cross-correlation,we just calculate the path coefficients where di(t)is the path length at time t.The phase for path at given delays using a fixed cyclic shift of n.Figure 7 shows iis,which changes by 2 when di(t) the process of measuring the path coefficient at a given delay. changes by the amount of sound wavelength Ac=c/f First,we synchronize the transmitted signal and received (1.69 cm)[28].Therefore,we can measure the phase change signal by cyclically shifting the transmitted signal with a of the reflection path to obtain mm-level accuracy in the path fixed offset of ni corresponding to the delay of the given path. length di(t) Second,we multiply each sample of the received baseband signal with the conjugation of the shifted transmitted sample. 6.2 Reflection Path Delay Estimation Third,we use a moving average with a window size of 1,024 The first step for measuring the finger movement is to to sum the complex values and get the path coefficients. estimate the delay of the reflection path.Due to the non- Note that the moving average can be carried out by just negligible main lobe width of the auto-correlation function, two additions per sample.Fourth,we use low-pass filter multiple IR estimations that are close to the reflection path to remove high frequency noises caused by imperfection have similar changes when the finger moves.We need to-200 -100 0 100 I (normalized) -200 -100 0 100 Q (normalized) With sampling rate increasing Without sampling rate increasing Figure 6: Path coefficient at different sampling rate Received baseband signal Transmitted baseband signal : a fixed cyclic shift of … Low-pass filter hˆt[n] x(t) x(t − 1023) Z−n n Z−1 Z−1 Z−1 Figure 7: Path coefficient measurement for delay n cyclically shifted by n points. The key observation is that ZC sequence has constant power, i.e., ZC[n] × ZC∗ [n] = 1,∀n. Thus, each point in the NZC multiplication results in Eq. (4) contributes equally to the estimation of ˆht[n]. In consequence, the summation over a window with a size of NZC can start from any value of t. Instead of advancing the value t by a full frame of 1,024 sample points as in ordinary cross-correlation operations, we can advance t one sample each time. In this way, we can obtain the path coefficient with a sampling rate of 48 kHz, which gives the details of changes in path coefficient as shown in Figure 6. The above upsampling scheme incurs high computational cost. To obtain all path coefficients ˆht[n] for delay n (n = 0 ∼ 1023), it requires 48, 000 dot productions per second and each dot product is performed with two vectors of 1,024 samples. This cannot be easily carried out by mobile devices. To reduce the computational cost, we observe that not all taps in ˆht[n] are useful. We are only interested in the taps corresponding to the structure propagation paths and the reflection air paths within a distance of 15 cm. Therefore, instead of calculating the cross-correlation, we just calculate the path coefficients at given delays using a fixed cyclic shift of n. Figure 7 shows the process of measuring the path coefficient at a given delay. First, we synchronize the transmitted signal and received signal by cyclically shifting the transmitted signal with a fixed offset of ni corresponding to the delay of the given path. Second, we multiply each sample of the received baseband signal with the conjugation of the shifted transmitted sample. Third, we use a moving average with a window size of 1, 024 to sum the complex values and get the path coefficients. Note that the moving average can be carried out by just two additions per sample. Fourth, we use low-pass filter to remove high frequency noises caused by imperfection of the interpolated ZC sequence. Finally, we get the path coefficient at 48 kHz sampling rate. After the optimization, measuring the path coefficient at a given delay only incurs one multiplication and two additions for each sample. 6 MOVEMENT MEASUREMENT 6.1 Finger Movement Model Finger movements incur both magnitude and phase changes in path coefficients. Firstly, the delay for the peak corresponding to the reflection path of the finger changes when the finger moves. Figure 8(a) shows the magnitude of the IR estimations when the finger is first moving away from the microphone and then moves back. The movement distance is 10 cm on the surface of the mobile device. A “hot” region indicates a peak at the corresponding distance in the IR estimation. While we can observe there are several peaks is the raw IR estimation and they change with the move￾ment, it is hard to discern the reflection path as it is much weaker than the LOS path or the structure path. To amplify the changes, we take the difference of the IR estimation along the time axis to remove these static paths. Figure 8(b) shows the resulting differential IR estimations. We observe that the finger moves away from the microphone during 0.7 to 1.3 seconds and moves towards to the microphone from 3 to 3.5 seconds. The path length changes about 20 cm (10 × 2) during the movement. In theory, we can track the position of the peak corresponding to the reflection path and measure the finger movement. However, the position of the peak is measured in terms of number of samples, which gives a low resolution of around 0.7 cm per sample. Furthermore, esti￾mation of the peak position is susceptible to noises, which lead to large errors in distance measurements. We utilize phase changes in the path coefficient to measure movement distance so that we can achieve mm-level distance accuracy. Consider the case the reflection path of the finger is path i and its path coefficient is: ˆht[ni] = Aie −j(ϕi+2π di (t ) λc ) , (5) where di (t) is the path length at time t. The phase for path i is ϕi (t) = ϕi + 2π di (t) λc , which changes by 2π when di (t) changes by the amount of sound wavelength λc = c/fc (≈1.69 cm) [28]. Therefore, we can measure the phase change of the reflection path to obtain mm-level accuracy in the path length di (t). 6.2 Reflection Path Delay Estimation The first step for measuring the finger movement is to estimate the delay of the reflection path. Due to the non￾negligible main lobe width of the auto-correlation function, multiple IR estimations that are close to the reflection path have similar changes when the finger moves. We need to