Echo cancellation for ultrasound

A method includes accessing signal data descriptive of a transmission sequence and pre-determined values associated with the transmission sequence. The signal data and the pre-determined values may be stored in a memory. The method includes transmitting a signal from a speaker of an electronic device according to the transmission sequence. The method includes generating a frame based on one or more signals received at a microphone of the electronic device. The one or more signals include an echo signal associated with the transmitted signal. The method includes processing the frame using the pre-determined values to produce an output frame in which a contribution associated with the echo signal is reduced.

The present disclosure is generally related to echo cancellation at an electronic device.

III. DESCRIPTION OF RELATED ART

Electronic devices may include one or more microphones for receiving signals (e.g., audio signals and/or ultrasound signals) and speaker(s) configured to transmit a signal (e.g., an audio signal and/or an ultrasound signal). A first electronic device may transmit a signal using its speaker(s) and the transmitted signal may be received at one or more microphones of other electronic devices. When a speaker of the first electronic device and a microphone of the first electronic device are in close proximity, echo signals may interfere with signals received at the first electronic device from the other electronic devices. The echo signals may occur when the first electronic device receives its own transmitted signal at one or more of its microphones.

For example, the first electronic device may be a wireless communication device (e.g., a cellular communication device). When an operator of the first electronic device speaks, a signal that represents the speech may be detected by a microphone of the first electronic device and transmitted to a second electronic device (e.g., a second cellular communication device) via a communication network (e.g., via a cellular network). The second electronic device may receive and process the signal (e.g., far end signal) from the first electronic device. Processing the signal (e.g., the speech of the operator of the first electronic device) may include outputting the far end signal at a speaker of the second electronic device. The far end signal output by the speaker of the second electronic device may be detected at a microphone of the second electronic device. In addition to detecting the far end signal, the microphone of the second electronic device may detect a near end signal (e.g., speech of an operator of the second electronic device).

An echo signal may occur when the second electronic device transmits the far end signal (or a signal correlated to the far end signal) to the first electronic device. Stated another way, when the second electronic device transmits a signal that represents the speech of the operator of the first electronic device back to the first electronic device, the operator of the first device will hear himself talking (i.e., the operator will hear an echo). To mitigate the interference caused by the echo signal, the second electronic device may include an adaptive filter, such as an adaptive feedback filter. The adaptive filter is configured to reduce echo by filtering the far end signal from the received signal detected at the microphone of the second electronic device prior to transmitting the near end signal to the first electronic device.

An electronic device includes a filter, one or more microphones, and a transmitter configured to transmit a signal (e.g., an ultrasound signal) according to a pre-determined transmission sequence. The pre-determined transmission sequence is distinct from an indeterminate far end signal, such as voice from a remote party to a teleconference. The electronic device includes a memory storing pre-determined values associated with the pre-determined transmission sequence. The pre-determined values characterize a signal transmitted according to the pre-determined sequence. The one or more microphones of the electronic device may receive other signals (e.g., other ultrasound signals) transmitted by other electronic devices. Additionally, the signal transmitted by the transmitter of the electronic device may be received at the one or more microphones of the electronic device as an echo signal. A frame may be generated that includes samples of the signals (e.g., the other signals from other electronic devices and the echo signal) received at the one or more microphones of the electronic device, and the frame may be provided to a filter. The filter may be configured to perform echo cancellation operations on each of the samples included in the frame based on the pre-determined values associated with the pre-determined transmission sequence to generate a new frame. In the new frame, a contribution of the echo signal to the received signal may be reduced.

In a particular embodiment, a method includes accessing signal data descriptive of a transmission sequence and pre-determined values associated with the transmission sequence. The method includes transmitting a signal from a speaker of an electronic device according to the transmission sequence. The method includes generating a frame based on one or more signals received at a microphone of the electronic device. The one or more signals may include an echo signal associated with the transmitted signal. The method includes processing the frame using the pre-determined values to produce an output frame in which a contribution associated with the echo signal is reduced (as compared to the frame).

In another embodiment, an apparatus includes a transmitter configured to transmit a signal according to a transmission sequence, a receiver configured to receive one or more signals, a memory storing pre-determined values associated with the transmission sequence, a first processing path, and first logic. The first processing path may be configured to receive an input that is generated based on the one or more received signals, to retrieve the pre-determined values from the memory, and to process the input based on the pre-determined values to produce an output indicative of echo in the received signal. A second processing path may be configured to receive the input and the output from the first processing path, and to generate a second output (e.g., an echo cancelled or echo reduced output) based on a difference between the input and the output.

In another embodiment, a computer-readable storage medium includes instructions executable by a processor to cause the processor to access signal data descriptive of a transmission sequence and pre-determined values associated with the transmission sequence. The instructions, when executed by the processor, cause the processor to instruct a speaker of an electronic device to transmit a signal according to the transmission sequence. The instructions, when executed by the processor, cause the processor to generate a frame based on one or more signals received at a microphone of the electronic device. The one or more signals include an echo signal associated with the transmitted signal. The instructions, when executed by the processor, cause the processor to process the frame using the pre-determined values to produce an output frame in which a contribution associated with the echo signal is reduced.

In another embodiment, an apparatus includes means for transmitting a signal according to a transmission sequence and means for receiving one or more signals. The apparatus includes means for storing pre-determined values associated with the transmission sequence. The apparatus also includes means for generating an input based on the one or more received signals and means for processing the input based on the pre-determined values to produce a first output. The first output is indicative of a contribution of the transmitted signal to the input. The apparatus includes means for generating a second output based on a difference between the input and the first output.

A particular advantage provided by at least one of the disclosed embodiments is a filter configured to perform echo cancellation that has a reduced computational complexity and improved performance as compared to other echo cancellation filters, such as an adaptive feedback filter. For example, improved performance may be realized because the filters of the embodiment described herein do not include a feedback loop, as found in adaptive filters. Another advantage provided by at least one of the disclosed embodiments is reduced power consumption due to the reduced computational complexity of the filter. Other aspects, advantages, and features of the present disclosure will become apparent after review of the entire application.

VI. DETAILED DESCRIPTION

Particular embodiments of the present disclosure are described further with reference to the drawings (which are not to scale, although relative positions of certain features illustrated in the drawings may be indicated). In the description, common features are designated by common reference numbers throughout the drawings. The embodiments disclosed herein may describe a device including a filter configured to perform echo cancellation based on pre-determined values. The pre-determined values may be associated with a pre-determined transmission sequence used by the device to transmit a signal. The filters of the various embodiments disclosed herein may be described as non-adaptive filters in that the filters remove or reduce echo associated with a predetermined signal, as opposed to an adaptive feedback filter that reduces echo associated with an indeterminate signal, (e.g. a far end signal).

Referring toFIG. 1, an illustrative embodiment of a system including a device100including a filter configured to perform echo cancellation using a pre-determined values associated with a pre-determined transmission sequence is shown. In an embodiment, the device100may be a mobile communication device (e.g., a cell phone), a smart phone, a tablet computing device, a laptop computing device, a portable digital assistant (PDA) device, or other electronic device. The device100includes a transmitter110(e.g., a speaker or transducer), one or more receiver(s)120(e.g., one or more microphones), a memory130, and a filter140.

The transmitter110may be configured to transmit a signal112according to a pre-determined transmission sequence. In an embodiment, the transmitter110may be an ultrasound transmitter configured to transmit an ultrasound signal according to the pre-determined transmission sequence. As shown inFIG. 1, the memory130may store signal data134. The signal data134may include information descriptive of the pre-determined transmission sequence. The pre-determined transmission sequence may be a pseudorandom noise (PN) sequence that may be locally unique to the device100. In an embodiment, the signal data134may include information descriptive of a plurality of transmission sequences (e.g., a plurality of gold codes, a plurality of kasami codes, a plurality of barker codes, etc.), and the device100may select the pre-determined transmission sequence from among of the plurality of transmission sequences such that the signal112transmitted from the transmitter110is locally unique to the device100. In addition to the signal data134, the memory130may store pre-determined values132associated with the pre-determined transmission sequence. The filter140may be configured to perform echo cancellation operations on input signals received at the receiver(s)120using the pre-determined values132. The pre-determined values132may include values of the signal data134after particular mathematical operations have been performed on them. For example, since the signal data134are pre-determined, computational demanding calculations related to the signal data134be performed in advance (e.g., before the predetermined signal is transmitted) and stored as the pre-determined values132to reduce computational burden during operation of the device100.

During operation, one or more signals (e.g., one or more ultrasound signals) may be received as an input signal at the receiver(s)120. The one or more signals may include a signal182received from a source180(e.g., a transmitter of another device not shown inFIG. 1) and an echo signal112). As described with reference toFIG. 3, the device100may be configured to determine a position of the source180(or another operation) based on the signal182. An input signal may be filtered to remove the echo signal112to facilitate accurate determination of the position of the source180. To mitigate the noise caused by the echo signal112, the device100processes the input signal at the filter140based on the pre-determined values132to reduce or eliminate the signal112from the input signal.

As shown inFIG. 1, the filter140may include a first processing path142and a second processing path144. The first processing path142includes a plurality of processing blocks, such as a first processing block150, a second processing block154, and a third processing block158. The second processing path144includes a fourth processing block162. The terms processing path and processing block are used to describe each of the elements142,144, and150,154,158,162for simplicity of description. The terms processing path and processing block are not intended to require particular physical circuitry; rather, processing paths and processing blocks are used to describe particular portions of the filter140that are operable to implement particular functions, such as the functions described with reference to each of the processing paths142,144and the processing blocks150,154,158,162. As such, the terms processing path and processing block may, in a particular embodiment, refer to one or more circuits or portions of a circuit that perform a particular function associated with the filter140. In another embodiment, the terms processing path and processing block may refer to instructions stored in a computer-readable storage medium that, when executed by a processor, cause the processor to initiate execution of a particular function associated with the filter140.

The input signal may be sampled by the one or more receiver(s)120. A sample of the input signal may be provided to the filter140as a frame170(e.g., a digitized representation of the echo signal112and the signal182combined). The filter140may perform echo cancellation on the frame170using the pre-determined values132to reduce or eliminate the echo signal112. The frame170,X, (i.e., a sample of the input signal received at the receiver(s)120) may be represented mathematically asX=H0⊕PN0+H1⊕PN1, and whereH0corresponds to an impulse response114affecting the signal112,PN0corresponds to the pre-determined transmission sequence of the signal112,H1corresponds to an impulse response184affecting the signal182,PN1corresponds to a pre-determined transmission sequence of the signal182, wherePN0is different thanPN1, and where the symbol ⊕ indicates convolution.

In the frameX,H0⊕PN0corresponds to the signal112(e.g., the echo signal to be cancelled by the filter140) andH1⊕PN1corresponds to the signal182received from the source180. The impulse response114may indicate how acoustics of an area surrounding the device100(e.g., a room where device100is located) affect the signal112, and the impulse response184may indicate how acoustics of an area surrounding the source180(e.g., a room where source180is located) affect the signal182. The impulse response114may be different from the impulse response184even when the device100and the source180are located in the same area.

The filter140may receive the frame170from the receiver(s)120and provide the frame170to the first processing path142and the second processing path144. The first processing path142may provide the frame170to the first processing block150. The first processing block150may be configured to perform convolution of the frame170with the pre-determined values132to produce a second frame152. The second frame152,Vmay be mathematically represented asV=X⊕PN0=H0⊕PN0⊕PN0+(H1⊕PN1)⊕PN0. The frameVmay indicate a correlation between the pre-determined values132(e.g., an approximation of the pre-determined transmission sequence of the signal112) and the input signal (e.g., the frameX). The transmission sequence,PN0, of the device100and the transmission sequence,PN1, of the source180are selected to be substantially orthogonal. Thus, the second frame152,V, may approximateH0⊕PN0⊕PN0based on the correlation between the first frame170,X, and the pre-determined values132.

The second frame152(e.g., the frameV) may be provided from the first processing block150to the second processing block154where the frameVis de-convoluted byPN0⊕PN0to produce a third frame156. The second processing block154may perform de-convolution of the frameVto removePN0⊕PN0using a set of values146. The set of values146may include a concatenated matrix W, where

The third frame156(e.g., the frameC) may be provided to the third processing block158. The third processing block158may convolute the third frame156(e.g., the frameC) with the pre-determined values132(e.g., an approximation ofPN0) to generate a fourth frame160,ECHO, which may be mathematically represented asECHO=C⊕PN0≈H0⊕PN0. The frameECHOmay represent an estimate of a portion of the frameXcorresponding to the echo signal112) to be cancelled by the filter140.

The fourth processing block162may receive the fourth frame160from the third processing block158and the frame170(e.g., the frameX) as inputs and generate an output frame164. The fourth processing block162may generate the output frame164by subtracting the frameECHO(e.g., the estimate of the echo signal112) from the frameX. Thus, the output frame164may correspond to an estimate ofH1⊕PN1(i.e., the signal182convoluted by the impulse response184).

By storing the pre-determined values132associated with the locally unique transmission sequence (i.e., a PN sequence orPN0) of the device100and then using the pre-determined values132to perform echo cancellation, the device100may consume less power due to the reduced computational complexity of the echo cancellation filter140as compared to other echo cancellation filters, such as an adaptive feedback filter. For example, to perform echo cancellation operations, an adaptive feedback filter may dynamically adapt to a transmitted signal and a received signal in order to determine both a transmission sequence (PNn) and an impulse response (Hn) corresponding to an unknown echo signal. In contrast, the filter140performs echo cancellation on a received signal (e.g., the frameX) using the pre-determined values132(e.g., a pre-transmission sequence (PN0)) stored at the memory130. The computational complexity of the filter140may be reduced because the transmission sequence of the device100is pre-determined and stored at the memory130as the pre-determined values132. Thus, to perform echo cancellation, the filter140need only estimate the impulse response114(H0) using convolution as described with reference to the processing blocks150,154,158. Additionally, implementation costs may be reduced due to reduced computational resources used to perform echo cancellation using the filter140(i.e., by performing convolution operations on a received signal using the pre-determined values132) as compared to other filters, such as the adaptive feedback filter where both the transmission sequence and the impulse response are unknown.

Referring toFIG. 2, a second illustrative embodiment of a system including a device200including a filter configured to perform echo cancellation using pre-determined values is shown. In a particular embodiment, the device200may be a mobile communication device (e.g., a cell phone), a smart phone, a tablet computing device, a laptop computing device, a portable digital assistant (PDA) device, or other electronic device. The device200includes a transmitter202, one or more receiver(s)204, a memory206, and a filter208.

The transmitter202may be configured to transmit a signal272according to a pre-determined transmission sequence. In an embodiment, the transmitter202may be an ultrasound transmitter configured to transmit an ultrasound signal according to the pre-determined transmission sequence. As shown inFIG. 2, the memory206may store signal data242. The signal data242may include information descriptive of the pre-determined transmission sequence. The pre-determined transmission sequence may be a pseudorandom noise (PN) sequence that may be locally unique to the device200. In an embodiment, the signal data242may include information descriptive of a plurality of transmission sequences (e.g., a plurality of gold codes, a plurality of kasami codes, a plurality of barker codes, etc.), and the device200may select the pre-determined transmission sequence from among of the plurality of transmission sequences such that the signal272transmitted from the transmitter202is locally unique to the device200. In addition to the signal data242, the memory206may store pre-determined values240associated with the pre-determined transmission sequence. In an embodiment, pre-determined values240may include pre-calculated values based on the signal data242, such as a fast Fourier transform (FFT) of the pre-determined transmission sequence that is locally unique to the device200. One of ordinary skill in the art would easily recognize that any other generally known time-to-frequency domain transform techniques such as, without limitation, discrete Cosine transform, discrete Fourier transform, or Wavelet transform, may be used instead of the FFT. The filter208may be configured to perform echo cancellation operations on input signals received at the receiver(s)204using the pre-determined values240. In contrast to the echo cancellation operations performed by the filter140ofFIG. 1, the echo cancellation operations performed by the filter208may include operations in both a frequency domain (e.g., using FFT operations) and a time domain (e.g., using inverse fast Fourier transform (IFFT) operations).

During operation, one or more signals (e.g., one or more ultrasound signals) may be received as an input signal at the receiver(s)204. The one or more signals may include a signal282received from a source280(e.g., a transmitter of another device not shown inFIG. 2) and an echo signal272. The echo signal272may introduce noise into the signal282. As described with reference toFIG. 3, the device200may be configured to determine a position of the source280(or another operation) based on the signal282. An input signal received at the one or more receiver(s)204may be filtered to remove the echo signal272to improve accuracy of the determination of the position of the source280.

As shown inFIG. 2, the filter208may include a first processing block250, a first processing path210and a second processing path212. The first processing path210includes a plurality of processing blocks, such as a second processing block252, a third processing block254, a fourth processing block256, a fifth processing block258, and a sixth processing block260. The second processing path212includes a seventh processing block262. The terms processing path and processing block are used to describe each of the elements210,212, and250,252,254,256,258,260,262for simplicity of description. The terms processing path and processing block are not intended to require particular physical circuitry; rather, processing paths and processing blocks are used to describe particular portions of the filter208that are operable to implement particular functions, such as the functions described with reference to each of the processing paths210,212and the processing blocks250,252,254,256,258,260,262. As such, the terms processing path and processing block may, in a particular embodiment, refer to one or more circuits or portions of a circuit that perform a particular function associated with the filter208. In another embodiment, the terms processing path and processing block may refer to instructions stored in a computer-readable storage medium that, when executed by a processor, cause the processor to initiate execution of a particular function associated with the filter208.

An input signal received at the one or more receiver(s)204may be sampled by the one or more receiver(s)204. A sample of the input signal may be provided to the filter208as a frame218. The filter208may perform echo cancellation on the frame218using the pre-determined values240to reduce or eliminate the echo signal272. The frame218may be received at the filter208as a frameX, which may be represented mathematically asX=H0⊕PN0+H1⊕PN1, whereH0corresponds to an impulse response274affecting the signal272,PN0corresponds to the pre-determined transmission sequence of the signal112,H1corresponds to an impulse response284affecting the signal282,PN1corresponds to a pre-determined transmission sequence of the signal282, wherePN0is different thanPN1, and where the symbol ⊕ indicates convolution. The first processing block250may perform an FFT operation on the frameXto generate a frame220. The frame220represents the frameXin the frequency domain (i.e.,FFT_X=FFT(X)). The FFT operation herein is just for an exemplary purpose and any other generally known time-to-frequency domain transform techniques such as, without limitation, discrete Cosine transform, discrete Fourier transform, or Wavelet transform, may be performed in the first processing block250, instead of the FFT.

In the frameX,H0⊕PN0corresponds to the echo signal272received at the one or more receivers204which is to be cancelled or reduced by the filter208. Further,H1⊕PN1corresponds to the signal282received from the source280. The impulse response274may indicate how acoustics of an area surrounding the device200(e.g., a room where device200is located) affect the signal272, and the impulse response284may indicate how acoustics of an area surrounding the source280(e.g., a room where source280is located) affect the signal282. The impulse response274may be different from the impulse response284even when the device200and the source280are located in the same area (e.g., the same room).

The first processing block250may provide the frame220to the first processing path210and to the second processing path212. The first processing path210may provide the frame220to the second processing block252. The second processing block252may be configured to multiply the frame220by FFT(PN0) determined from the pre-determined values240to generate a second processed frame222. Thus, the second processing block252multiplies the FFT(X) by the FFT(PN0), which is mathematically equivalent to convolution of the frameXwithPN0in the time domain (e.g., as described with reference to the first processing block150ofFIG. 1). The second frame222, frameFFT_IN, where the frameFFT_INrepresents a correlation of thePN0with the frameXin the time domain. The second frame222may be provided to the third processing block254.

The third processing block254may perform an IFFT operation on the second frame222to produce a third frame224. The IFFT operation herein is just for an exemplary purpose and any other generally known frequency-to-time domain transform techniques such as, without limitation, inverse discrete Cosine transform, inverse discrete Fourier transform, or inverse Wavelet transform, may be performed in the third processing block254, instead of the IFFT. The third frame224, frameV, may indicate a correlation between thePN0and the input signal (e.g., the frameX) in the time domain. For example, assuming that the signal112ofFIG. 1and the signal272ofFIG. 2are transmitted according to the same pre-determined transmission sequence (i.e., the pre-determined values240=FFT(the pre-determined values132), the frameVofFIG. 2may be the same as the frameVofFIG. 1provided the signal182and282is same or substantially similar.

The third frame224(e.g., the frameV) may be provided from the third processing block254to the fourth processing block256where the frameVis de-convoluted fromPN0⊕PN0to produce a fourth frame226. The fourth processing block256may perform de-convolution of the frameVfromPN0⊕PN0using a set of values270. The set of values270may correspond to the set of values146described with reference toFIG. 1. The fourth frame226may be a frameC, where the frameCcorresponds to an estimate of the impulse response274(e.g., an estimation ofH0).

The fourth frame226(e.g., the frameC) may be provided to the fifth processing block258. The fifth processing block258may perform a FFT operation on the fourth frame226(e.g., FFT(C)) to generate a fifth frame228,FFT_C, which corresponds to the estimate of the impulse response274in the frequency domain. The FFT operation herein is just for an exemplary purpose and any other generally known time-to-frequency domain transform techniques such as, without limitation, discrete Cosine transform, discrete Fourier transform, or Wavelet transform, may be performed in the fifth processing block258, instead of the FFT.

The fifth frame228(e.g., the frameFFT_C) may be provided to the sixth processing block260. The sixth processing block260may be configured to multiply the fifth frame228by the pre-determined values240(e.g., the FFT(PN0)) to produce a sixth frame230,FFT_OUT. Multiplying the frameFFT_C(e.g., the FFT(C)) by the pre-determined values240(e.g., the FFT(PN0) in the frequency domain is mathematically equivalent to convolution of the frameCby the pre-determined values240in the time domain, as described with reference to the first processing block158ofFIG. 1. The sixth frame230(e.g., the frameFFT_OUT) may represent, in the frequency domain, a portion of the frameXcorresponding to the echo signal272to be cancelled by the filter208.

The seventh processing block262may receive the sixth frame230(e.g., the frameFFT_OUT) from the sixth processing block260and the frame220(e.g., the frameFFT_X) as inputs and generate an output frame232. The seventh processing block262may generate the output frame232by subtracting the frameFFT_OUT(e.g., the signal272) from the frameFFT_X. Thus, the output frame232may represent an estimate of the signal282in the frequency domain.

By storing the pre-determined values240(e.g., the FFT(PN0) associated with the locally unique transmission sequence (i.e., a PN sequence) of the device200and then using the pre-determined values240to perform echo cancellation, the device200may consume less power due to the reduced computational complexity of the echo cancellation filter208as compared to other echo cancellation filters, such as an adaptive feedback filter. For example, to perform echo cancellation operations, an adaptive feedback filter may dynamically adapt to a transmitted signal and a received signal in order to determine both a transmission sequence (PNn) and an impulse response (Hn) corresponding to an unknown echo signal. In contrast, the filter140performs echo cancellation on a received signal (e.g., the frameX) using the pre-determined values240(e.g., FFT(PN0)) stored at the memory206. The computational complexity of the filter208may be reduced because calculations based on the transmission sequence of the device200can be done in advance with results stored at the memory206as the pre-determined values240. Thus, to perform echo cancellation, the filter208only estimates the impulse response (H0), as described with reference to the processing block256. As demonstrated inFIG. 2, the impulse response (e.g., the frameFFT_C) may be estimated using a combination of time domain processing (e.g., de-convolution) and frequency domain processing. Additionally, implementation costs may be reduced due to computational resources used to perform echo cancellation using the filter208as compared to other filters, such as the adaptive feedback filter.

Referring toFIG. 3, an illustrative embodiment of a multi-user peer-to-peer positioning system300is shown. As shown inFIG. 3, the multi-user peer-to-peer positioning system300includes a first electronic device302and a second electronic device340. The first electronic device302includes microphones304,306,308and a transmitter310. In a particular embodiment, the microphones304,306,308may correspond to the receiver(s)120described with reference toFIG. 1or the receiver(s)204described with reference toFIG. 2and the transmitter310may correspond to the transmitter110described with reference toFIG. 1or the transmitter202described with reference toFIG. 2. As shown inFIG. 3, the first electronic device302may transmit a first signal320(e.g., a first ultrasound signal) from the transmitter310according to a first transmission sequence, and the second electronic device340may transmit a second signal350(e.g., a second ultrasound signal) from the transmitter342according to a second transmission sequence. As shown inFIG. 3, the first signal320is designated by a first pattern322and the second signal350is designated by a second pattern352.

The first electronic device302may receive the second signal350at one or more of the microphones304,306,308and may determine a location of the second electronic device340based on the second signal350using triangulation. For example, inFIG. 3, the first electronic device302receives the second signal350as a signal350aat the microphone304, a signal350bat the microphone308, and a signal350cat the microphone306. The first electronic device302may use time delays associated with each of the signals350a,350b,350cto estimate, or triangulate, the position of the second electronic device340. In an embodiment, estimating the position of the second electronic device340may include determining an angle α that indicates a direction of the location of the second electronic device340and a distance380. In a particular embodiment, the distance380corresponds to a distance between the first electronic device302and the second electronic device340. It is noted that although only three microphones are shown inFIG. 3, the first electronic device302may include more than three microphones.

As shown inFIG. 3, the first signal320may be received as an echo signal (e.g., the signals320a,320b,320c) at one or more of the microphones304,306,308. The echo signals may interfere with, or otherwise degrade the accuracy of calculations of the position of the second electronic device340. As shown inFIG. 3, the first electronic device302includes a memory330and a filter332. The memory330may store pre-determined values334associated with the first transmission sequence used by the transmitter310to transmit the first signal. In a particular embodiment, the memory330may correspond to the memory130ofFIG. 1, or the memory206ofFIG. 2. The filter332may receive a frame including samples of the signal(s) received at each of the microphones304,306,308(e.g., the first signal320and the second signal350) and may perform echo cancellation operations prior to calculating an estimate of the position of the second electronic device340. In a particular embodiment, the filter332may correspond to the filter140described with reference toFIG. 1or the filter208described with reference toFIG. 2.

In an embodiment, the device302may interact with the device340and other devices (not shown) to form a peer-to-peer positioning system. The device302may be configured to determine a location of other devices operating within the peer-to-peer positioning system based on the output of the filter332. Each of the devices operating within the peer-to-peer positioning system may transmit a signal that is received at the device302(e.g., at the microphones304,306,308) and used by the device302to determine an estimated location of each device that transmitted a signal that was received at the device302.

To distinguish the signals transmitted from each of the devices, the device302may negotiate with each of the other devices to select a particular transmission sequence from a set of pre-determined transmission sequences (e.g., gold codes). In a particular embodiment, the set of transmission sequences comprise a family of transmission sequences where each of the transmission sequences has a low cross-correlation relative to the other transmission sequences in the family. After selecting the particular transmission sequence, the device302periodically transmits a signal (e.g., the signal320) according to the selected particular transmission sequence. In a particular embodiment, each of the transmission sequences may comprise a periodic sequence. The device302may periodically transmit the signal320based on a time interval. In an embodiment, the time interval may be determined based on a length of the selected particular transmission sequence.

By storing information (e.g., the pre-determined values334) associated with the locally unique transmission sequence (e.g., PN) of the first electronic device302and then using the stored information to perform echo cancellation using the filter332, the first electronic device302may consume less power due to the reduced computational complexity of the filter332as compared to other echo cancellation filters, such as an adaptive feedback filter. The reduced computational complexity of the filter332may also enable the first electronic device302to perform faster location determinations.

Referring toFIG. 4, another illustrative embodiment of a device400configured to perform echo cancellation is shown. As shown inFIG. 4, the device400includes a processor402, a receiver(s)404, a transmitter406, and a memory408. In a particular embodiment, the device400may correspond to the device100ofFIG. 1, the device200ofFIG. 2, or the device302ofFIG. 3. The memory408may store instructions420. The instructions420may be executable by the processor402to perform the one or more of the functions described with reference to the filter140ofFIG. 1or the filter208ofFIG. 2.

In an embodiment, the instructions420may include instructions executable to perform location determinations based on signals received at the receiver(s)404, such as location instructions426. The location instructions426may be executable by the processor402to determine, or triangulate, positions of other devices based on signals received from the other devices at the receiver(s)404as described with reference toFIG. 3. The location instructions426may be executable by the processor402to determine an angle (e.g., the angle α described with reference toFIG. 3) that indicates a direction of the location of the other device and a distance (e.g., the distance380described with reference toFIG. 3).

In an embodiment, the instructions420may include instructions executable to dynamically select a particular transmission sequence from a set of transmission sequences440and to store pre-determined values430at the memory408. For example, the instructions420may include sequence selection instructions424. The sequence selection instructions424may be executable by the processor402to select a particular transmission sequence from the set of transmission sequences440. In an embodiment, the set of transmission sequences440comprise gold code sequences. Each transmission sequence in the set of transmission sequences440may have a low cross-correlation relative to other transmission sequences in the in the set of transmission sequences440. The sequence selection instructions424may include instructions that cause the processor402to communicate with other devices via a wireless communication link (e.g., a Bluetooth or Wi-Fi communication link), within a communication range of the device400, to determine a locally unique transmission sequence to be used by the transmitter406. The transmission sequence may be considered locally unique in that each device within the communication range of the device400may use a different transmission sequence while devices outside of the communication range of the device400may concurrently be using the same transmission sequence as the device400.

After selecting the transmission sequence, the sequence selection instructions424may cause the processor402to calculate or to access the pre-determined values430. In an embodiment, the pre-determined values430are stored at the memory408before the transmitter406begins transmitting a signal according to the transmission sequence. For example, after selecting the transmission sequence, the sequence selection instructions424may cause the processor402to calculate the pre-determined values430for the selected transmission sequence and to store the pre-determined values430at the memory408. In this particular embodiment, the sequences selection instructions424may include instructions executable by the processor402to indicate, during operation, the particular selected transmission sequence and a corresponding set of the pre-determined values430to use for echo cancellation. To illustrate, the set of transmission sequences may include ten (10) different transmission sequences and the pre-determined values430may include values calculated based on each transmission sequence. A particular transmission sequence may be selected for use in transmissions via the transmitter406. During echo cancellation operations, the processor402may use pre-determined values430corresponding to the particular transmission sequence used by the transmitter406. In another embodiment, only a single set of pre-determined values430may be generated and stored at the memory408using the sequence selection instructions424.

Referring toFIG. 5, another illustrative embodiment of a device500configured to perform echo cancellation is shown. As shown inFIG. 5, the device500includes a processor502, a receiver(s)504, a transmitter506, and a memory508. In a particular embodiment, the device500may correspond to the device100ofFIG. 1or the device200ofFIG. 2. The memory508may store a set of transmission sequences522and pre-determined values520. As shown inFIG. 5, the processor502includes a filter510, a sequence selector512, and a location determination unit514. In a particular embodiment, the filter510may correspond to the filter140ofFIG. 1or the filter208ofFIG. 2. For example, the filter510may include circuitry or other logic configured to perform one or more of the operations described with reference to the filter140ofFIG. 1or the filter208ofFIG. 2. The filter510may access the memory508to retrieve the pre-determined values520for use in echo cancellation operations.

In an embodiment, the sequence selector512may include circuitry or other logic configured to perform one or more of the functions described with reference to the sequence selection instructions424ofFIG. 4. In an embodiment, the location determination unit514may include circuitry or other logic configured to perform one or more of the functions described with reference to the location instructions426ofFIG. 4. As shown inFIG. 5, the filter510, the sequence selector512, and the location determination unit514may be part of the processor502. In another embodiment, one or more of the filter510, the sequence selector512, and the location determination unit514may be external to the processor502. For example, one or more of the filter510, the sequence selector512, and the location determination unit514may be implemented by a field-programmable gate array (FPGA) device, an application-specific integrated circuit (ASIC), a special purpose processing unit, a digital signal processor (DSP), a controller, another hardware device, a firmware device, or a combination thereof.

Referring toFIG. 6, a first illustrative embodiment of a method600of performing echo cancellation is shown. At602, the method600includes accessing signal data descriptive of a transmission sequence and pre-determined values associated with the transmission sequence. For example, the signal data and the pre-determined values may be stored at a memory, such as the memory130ofFIG. 1or the memory206ofFIG. 2, before a signal corresponding to a particular transmission sequence is transmitted.

The method600includes, at604, transmitting a signal from a transmitter of an electronic device according to the transmission sequence. At606, the method600includes generating a frame based on one or more signals received at a microphone of the electronic device. The one or more signals may include an echo signal associated with the transmitted signal. At608, the method600includes processing the frame using the pre-determined values to produce an output frame in which a contribution associated with the echo signal is reduced. In a particular embodiment, processing of the frame using the pre-determined values may be performed by the filter140ofFIG. 1. In another particular embodiment, processing of the frame using the pre-determined values may be performed by the filter208ofFIG. 2. In another particular embodiment, processing of the frame using the pre-determined values may be performed by the filter332ofFIG. 3. In another particular embodiment, processing of the frame using the pre-determined values may be performed by the processor402using the echo cancellation instructions422ofFIG. 4. In another particular embodiment, processing of the frame using the pre-determined values may be performed by the filter510ofFIG. 5.

Referring toFIG. 7, a second illustrative embodiment of a method700of performing echo cancellation is shown. At702, the method700includes receiving a first processed frame. In an embodiment, the first processed frame may include, be included within, or correspond to the frame220ofFIG. 2which may be received at the filter208ofFIG. 2. At704, the method700includes multiplying the first processed frame by pre-determined values to produce a second processed frame (e.g., the frame222ofFIG. 2). In a particular embodiment, the pre-determined values may be the pre-determined values240ofFIG. 2.

At706, the method700includes performing an inverse fast Fourier transform (IFFT) on the second processed frame to produce a third processed frame (e.g., the frame224ofFIG. 2). At708, the method700includes multiplying the third processed frame by a set of pre-determined values to produce a fourth processed frame (e.g., the frame226ofFIG. 2). In a particular embodiment, the set of pre-determined values may include, be included within, or correspond to the set of pre-determined values270. At710, the method700includes performing an FFT on the fourth processed frame to produce a fifth processed frame (e.g., the frame228ofFIG. 2). At712, the method700includes multiplying the fifth processed frame by the pre-determined values to produce a sixth processed frame (e.g., the frame230ofFIG. 2), and, at714, determining a difference between the first processed frame and the sixth processed frame. In a particular embodiment, the difference between the first processed frame and the sixth processed frame produces an output frame (e.g., the frame232ofFIG. 2) in which a contribution associated with an echo signal is reduced relative to an input frame (e.g., the input frame218).

Referring toFIG. 8, a block diagram of a particular illustrative embodiment of an electronic device800operable to support the various methods, systems, and computer-readable media described with respect toFIGS. 1-7is shown. The electronic device800includes a processor810, such as a digital signal processor (DSP), coupled to a memory832. In a particular embodiment, the electronic device800may correspond to the device100ofFIG. 1or the first electronic device200ofFIG. 2, the device302ofFIG. 3, the device400ofFIG. 4, or the device500ofFIG. 5.

As shown inFIG. 8, the electronic device800includes a display controller826that is coupled to the processor810and to a display828. A coder/decoder (CODEC)834may also be coupled to the processor810. A speaker(s)836and microphone(s)838may be coupled to the CODEC834. In a particular embodiment, the microphone(s)838may be internal to the electronic device800. In an embodiment, the microphone(s)838may correspond to the receiver(s)120ofFIG. 1, the receiver(s)204ofFIG. 2, the microphones304,306,308ofFIG. 3, the receiver(s)404ofFIG. 4, or the receiver(s)504ofFIG. 5. In an embodiment, the speaker(s)836may correspond to the transmitter110ofFIG. 1, the transmitter202ofFIG. 2, the transmitter310ofFIG. 3, the transmitter406ofFIG. 4, or the transmitter506ofFIG. 5.

As shown inFIG. 8, the electronic device800includes a wireless controller840that may be coupled to a transceiver850that is coupled to an antenna842. In a particular embodiment, the processor810, the display controller826, the memory832, the CODEC834, the transceiver850, and the wireless controller840are included in a system-in-package or a system-on-chip device822. In a particular embodiment, an input device830and a power supply844are coupled to the system-on-chip device822. In a particular embodiment, the display828, the input device830, the speaker(s)836, the microphone838, the wireless antenna842, and the power supply844may be external to the system-on-chip device822. However, each of the display828, the input device830, the speaker(s)836, the microphone(s)838, the wireless antenna842, and the power supply844may be coupled to a component of the system-on-chip device822, such as an interface or a controller.

The electronic device800may store pre-determined values, such as the pre-determined values882, at the memory832. In an embodiment, the pre-determined values may be stored at a memory (i.e., a cache memory) of the processor810as the pre-determined values872. The processor810may include sequence selection logic (e.g., the sequence selector512ofFIG. 5) configured to access the pre-determined values at the memory832or the pre-determined values882. The electronic device800may receive signals (e.g., ultrasound signals) at the microphone(s)838. The received signals may include an echo signal generated by the speaker(s)836. In a particular embodiment, the CODEC834may process the received signals to generate an input frame (e.g., the input frame170ofFIG. 1or the input frame218ofFIG. 2) and provide the input frame to the processor810. In another embodiment, the input frame may be generated by the processor810.

In a particular embodiment, the processor810may include echo cancellation logic880configured to process the input frame to produce an output frame (e.g., the output frame164ofFIG. 1or the output frame232ofFIG. 2). A contribution of the echo signal to the output frame may be less than a contribution of the echo signal to the input frame. In an embodiment, the echo cancellation logic880may correspond to the filter140ofFIG. 1and may be configured to perform one or more of the operations described with reference to the processing blocks150,154,158,162ofFIG. 1. In another embodiment, the echo cancellation logic880may correspond to the filter208ofFIG. 2and may be configured to perform one or more of the operations described with reference to the processing blocks250-262ofFIG. 2. In another embodiment, the echo cancellation logic880may correspond to the filter332ofFIG. 3. In yet another embodiment, the echo cancellation logic880may correspond to the filter510described with reference toFIG. 5.

In another particular embodiment, the memory832may store echo cancellation instructions870that cause the processor810to perform echo cancellation operations on the input frame to produce the output frame as described with reference toFIGS. 1-7. A contribution of the echo signal to the output frame may be less than a contribution of the echo signal to the input frame. For example, the echo cancellation instructions870may correspond to the echo cancellation instructions422ofFIG. 4. In another embodiment, the echo cancellation instructions870may be executable by the processor810to perform one or more of the operations described with reference to the processing blocks150,154,158,162ofFIG. 1or the operations described with reference to the processing blocks250-262ofFIG. 2.

The processor810may be configured to generate the pre-determined values (e.g., values that are determined before a transmission sequence related to the pre-determined values is sent, such as the pre-determined values882or the pre-determined values872) based on signal data descriptive of a pre-determined transmission sequence. In a particular embodiment, the processor810may include a sequence selector (e.g., the sequence selector512ofFIG. 5) configured to generate the pre-determined values and to store the pre-determined values at the memory (e.g., the memory832or a cache memory of the processor810) or to access the pre-determined values at the memory832. In another embodiment, the memory832may store sequence selection instructions (e.g., the sequence selection instructions424ofFIG. 4) that cause the processor810to generate the pre-determined values and to store the pre-determined values at the memory (e.g., the memory832or a cache memory of the processor810).

The processor810may be configured to determine a location of another electronic device (not shown) based on the output frame as described with reference toFIG. 3. For example, a particular portion of the received signals may correspond to a signal generated at the other electronic device. The processor810may use triangulation to determine a location (i.e., a direction and distance) of the other electronic device relative to the electronic device800based on the output frame. In a particular embodiment, the processor810may include location logic (e.g., the location determination unit514ofFIG. 5) for use in determining the location of the other electronic device. In another embodiment, the memory832may store location instructions (e.g., the location instructions426ofFIG. 4) that cause the processor810to determine the location of the other electronic device.

In conjunction with the described embodiments, a system is disclosed that may include means for transmitting a signal according to a transmission sequence. In a particular embodiment, the means for transmitting the signal may include the speaker(s)836, the transmitter110ofFIG. 1, the transmitter202ofFIG. 2, the transmitter310ofFIG. 3, the transmitter406ofFIG. 4, or the transmitter506ofFIG. 5. The system may include means for receiving one or more signals. In a particular embodiment, the means for receiving one or more signals may include the microphone(s)838, the receiver(s)120ofFIG. 1, the receiver(s)204ofFIG. 2, the microphones304-308ofFIG. 3, the receiver(s)404ofFIG. 4, or the receiver(s)504ofFIG. 5. The system may include means for storing pre-determined values associated with a transmission sequence. In an embodiment, the means for storing the pre-determined values associated with the transmission sequence may include the memory832, the memory130ofFIG. 1, the memory206ofFIG. 2, the memory330ofFIG. 3, the memory408ofFIG. 4, or the memory508ofFIG. 5. In another embodiment, the means for storing the pre-determined values associated with the transmission sequence may include a memory (e.g., a cache memory) or register of the processor810.

The system may include means for generating an input (e.g., the input frame170ofFIG. 1or the input frame218ofFIG. 2) based on the one or more received signals. In an embodiment, the means for generating the input based on the one or more received signals may include the processor810. In another embodiment, the means for generating the input based on the one or more received signals may include the receiver(s)120ofFIG. 1or the receiver(s)204ofFIG. 2. In another embodiment, the means for generating the input based on the one or more received signals may include the filter510ofFIG. 5. In an embodiment, the means for generating an input based on the one or more received signals may be implemented by a field-programmable gate array (FPGA) device, an application-specific integrated circuit (ASIC), a processing unit such as a central processing unit (CPU), a digital signal processor (DSP), a controller, another hardware device, a firmware device, or any combination thereof configured to generate an input based on one or more received signals.

The system may include means for processing the input based on the pre-determined values to produce a first output (e.g., the frame160ofFIG. 1or the frame230ofFIG. 2). The first output may be indicative of a contribution of the transmitted signal to the input. In an embodiment, the means for processing the input based on the pre-determined values may include the echo cancellation logic880, which may be incorporated within the processor810. In another embodiment, the echo cancellation logic880may be external to the processor810and may be implemented by a FPGA device, an ASIC, a processing unit such as a CPU, a DSP, a controller, another hardware device, firmware device, or any combination thereof. In an embodiment, the means for processing the input based on the pre-determined values may include the first processing path142ofFIG. 1(e.g., the processing blocks150,154,158,162ofFIG. 1) of the filter140ofFIG. 1. In another embodiment, the means for processing the input based on the pre-determined values may include the first processing path210ofFIG. 2(e.g., the processing blocks250-262ofFIG. 2) of the filter208ofFIG. 2. In another embodiment, the means for processing the input based on the pre-determined values may include the filter332ofFIG. 3. In an embodiment, the first processing path142, the first processing path210may be implemented by a FPGA device, an ASIC, a processing unit such as a CPU, a DSP, a controller, another hardware device, a firmware device, or any combination thereof configured to perform the functions described with reference to the processing blocks150,154,158ofFIG. 1or the processing blocks252-260ofFIG. 2.

The system may include means for generating a second output (e.g., the output frame164ofFIG. 1or the output frame232ofFIG. 2) based on a difference between the input and the first output. In an embodiment, the means for generating the second output may include the echo cancellation logic880. In a particular embodiment, the echo cancellation logic880may be incorporated within the processor810. In another embodiment, the echo cancellation logic880may be external to the processor810(e.g., as application specific circuitry). In an embodiment, the means for generating the second output may include the second processing path144(e.g., the processing block162ofFIG. 1) of the filter140ofFIG. 1, the second processing path212(e.g., the processing block262ofFIG. 2) of the filter208ofFIG. 2, or may include the filter332ofFIG. 3. In an embodiment, the second processing path144of the filter140ofFIG. 1or the second processing path212of the filter208ofFIG. 2may be implemented by a FPGA device, an ASIC, a processing unit such as a CPU, a DSP, a controller, another hardware device, firmware device, or any combination thereof configured to perform the functions described with reference to the processing block162ofFIG. 1or the processing block262ofFIG. 2.

In an embodiment, the means for generating the input (e.g., the frame220ofFIG. 2) may include means for receiving a frame (e.g., the frame218ofFIG. 2) generated based on the one or more received signals and means for performing a fast Fourier transform (FFT) on the frame. The input may include a result of the FFT. In an embodiment, the means for performing the FFT on the frame may include the first processing block250ofFIG. 2. In an embodiment, the first processing block250may be implemented by a FPGA device, an ASIC, a processing unit such as a CPU, a DSP, a controller, another hardware device, a firmware device, or any combination thereof configured to receive a frame and perform a FFT on the frame.

In a particular embodiment, the means for processing the input (e.g., the frame220ofFIG. 2) includes means for determining a first product (e.g., the frame222ofFIG. 2) by multiplying the input by the pre-determined values, means for performing an inverse fast Fourier transform (IFFT) on the first product, means for determining a second product (e.g., the frame226) by multiplying a result of the IFFT (e.g., the frame224ofFIG. 2) by a set of pre-determined values (e.g., the set of pre-determined values270ofFIG. 2), means for performing a second FFT on the second product, and means for multiplying a result of the second FFT (e.g., the frame228ofFIG. 2) by the pre-determined values to produce the first output (e.g., the frame230).

In an embodiment, the means for determining the first product, the means for performing the IFFT on the first product, the means for determining the second product, the means for performing the second FFT on the second product, and the means for multiplying a result of the second FFT may each be implemented by a FPGA device, an ASIC, a processing unit such as a CPU, a DSP, a controller, another hardware device, firmware device, or any combination thereof configured to perform the functions described with reference to the second processing block154ofFIG. 1. In an embodiment, the means for performing the IFFT on the first product corresponds to the third processing block254. In an embodiment, the set of pre-determined values corresponds to the set of pre-determined values132described with reference toFIG. 1.