Received x(t) Low-pass of the interpolated ZC sequence.Finally,we get the path baseband signal fiiter coefficient at 48 kHz sampling rate.After the optimization, Z-m:a fixed measuring the path coefficient at a given delay only incurs one multiplication and two additions for each sample. Transmited baseband signal 21 6 MOVEMENT MEASUREMENT x(t-1023) Figure 7:Path coefficient measurement for delay n 6.1 Finger Movement Model We use the property of the circular cross-correlation to Finger movements incur both magnitude and phase upsample the path coefficient measurements.For a given changes in path coefficients.First,the delay for the peak delay of n samples,the IR estimation at time t is given by corresponding to the reflection path of the finger changes the circular cross-correlation of the received signal and the when the finger moves.Figure 8(a)shows the magnitude of transmitted sequence: the IR estimations when the finger first moves away from the microphone and then moves back.The movement distance is 10 cm on the surface of the mobile device.A"hot"region h,[m= ZCR[t+]×ZC[(l-n) mod Nc](4) indicates a peak at the corresponding distance in the IR esti- (=0 mation.While we can observe there are several peaks in the This is equivalent to take the summation of Nc point of raw IR estimation and they change with the movement,it is the received signal multiplied by a conjugated ZC sequence hard to discern the reflection path as it is much weaker than cyclically shifted by n points.The key observation is that the LOS path or the structure path.To amplify the changes, ZC sequence has constant power,i.e.,ZC[n]x ZC"[n] we take the difference of the IR estimation along the time 1,Vn.Thus,each point in the Nc multiplication results axis to remove these static paths.Figure 8(b)shows the re- in Eq.(4)contributes equally to the estimation of h [n].In sulting differential IR estimations.We observe that the finger consequence,the summation over a window with a size of moves away from the microphone during 0.7 to 1.3 seconds Nc can start from any value of t.Instead of advancing the and moves towards to the microphone from 3 to 3.5 seconds. value t by a full frame of 1,024 sample points as in ordinary The path length changes about 20 cm(10 x 2)during the cross-correlation operations,we can advance t one sample movement.In theory,we can track the position of the peak each time.In this way,we can obtain the path coefficient corresponding to the reflection path and measure the finger with a sampling rate of 48 kHz,which gives the details of movement.However,the position of the peak is measured in changes in path coefficient as shown in Figure 6. terms of the number of samples,which gives a low resolution The above upsampling scheme incurs high computational of around 0.7 cm per sample.Furthermore,estimation of the cost.To obtain all path coefficients h [n]for delay n(n=0~ peak position is susceptible to noises,which leads to large 1023),it requires 48,000 dot productions per second and each 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 are useful.We are only interested in the taps corresponding is path i and its path coefficient is: to the structure propagation paths and the reflection air paths h [ni]=Are24) (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 n;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 imperfections have similar changes when the finger moves.We need toReceived 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 We use the property of the circular cross-correlation to upsample the path coefficient measurements. For a given delay of n samples, the IR estimation at time t is given by the circular cross-correlation of the received signal and the transmitted sequence: ˆht[n] = N ′ ZCX−1 l=0 ZCR[t + l] × ZC∗ T [(l − n) mod N ′ ZC] (4) This is equivalent to take the summation of N ′ ZC point of the received signal multiplied by a conjugated ZC sequence 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 N ′ ZC multiplication results in Eq. (4) contributes equally to the estimation of ˆht[n]. In consequence, the summation over a window with a size of N ′ ZC 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 imperfections 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. First, 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 first moves 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 esti￾mation. While we can observe there are several peaks in the raw IR estimation and they change with the movement, 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 re￾sulting 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 the number of samples, which gives a low resolution of around 0.7 cm per sample. Furthermore, estimation of the peak position is susceptible to noises, which leads 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