EECS16A

Acoustic Positioning System

We will start at Berkeley Time

Semester Outline

Shazam

Acoustic Positioning

Voice

Recognition 1

Voice

Recognition 2

Today’s Lab: Acoustic Positioning System

• Global Positioning System (GPS)
• Uses radio waves instead of sound waves
• Understand mathematical tools used for shifting and detecting signals
• Think about cross correlation!

​

eecs 16a final fall 2025

Babak Ayazifar

Set-up

• Known: Location of each satellite and what beacon signal each satellite is playing
• Unknown: Location of receiver ← what we want to figure out!

Set-up

• Satellite:
• Known, periodic waveforms
• Know satellite location
• Receiver:
• Will record the waveform
• Sum of all shifted beacons
• Waveform will be shifted from known satellite waveform based on how far it is from satellite (sound takes time to travel)

​

Let’s go backwards

Assume we know the distance between the receiver and every satellite

• Use lateration and the satellites’ locations to locate the receiver!
• How many satellites do we need in a 2D world?

​

How do we get those distances?

Assume we know the time-delay (in secs) of every beacon

• Use the speed of sound through air to get exactly how far our receiver is from every satellite
• d = v_s⋅ t
• v_s ≈ 343 m/s

​

How do we get those time-delays?

Assume we know how many samples it takes for each beacon signal to arrive at the receiver

• Use the sampling frequency of receiver to get the time-delay
• Sampling frequency [samples/sec] - rate at which microphone records samples

Poll Time!

Let the sampling frequency be 1000 Hz and the speed of sound be 343 m/s. If I detect a signal with a delay of 100 samples, what is the distance between the speaker and the mic?

• 3430 m
• 34.3 m
• 343 m
• 3.43 m

​

Poll Time!

Let the sampling frequency be 1000 Hz and the speed of sound be 343 m/s. If I detect a signal with a delay of 100 samples, what is the distance between the speaker and the mic?

• 3430 m
• 34.3 m →
• 343 m
• 3.43 m

​

How do we get sample delays?

• Receiver’s recorded signal is the sum of all the beacon signals
• Need to separate the recorded signal into the individual beacon signals to see how many samples each signal is delayed by

​

Overview

Recall: Inner (Dot) product

• Computes how similar two vectors are

​

Recall: Inner (Dot) product

• Given this expression, with ||x|| = ||y||, when is this expression maximized?

An alternate form of the dot product

• 𝜃 = 0
• vectors point in the SAME DIRECTION, so they are the SAME SIGNAL

​

The bigger the dot product magnitude, the more “similar” the two vectors are

Tool: Cross-correlation

• Mathematical tool for finding similarities between signals
• Idea: Computes dot product between r and signal B_A shifted by k samples

​

• From the previous slide, the peak of the cross-correlation vector tells us which shift amount makes B_A “most similar” to r

In Python:

cross_correlation(r, B_A)[k]

Poll Time!

Given ||x|| = ||y|| = 1, when is the magnitude of the inner product expression maximized?

• theta = 0
• theta = 90
• theta = 180
• theta = -90

​

​

Poll Time!

Given ||x|| = ||y|| = 1, when is the magnitude of the inner product expression maximized?

• theta = 0
• theta = 90
• theta = 180 (cos 180 = -1)
• theta = -90

​

​

Tool: Cross-correlation

• At ~ how many offset samples are the signals most similar?

Note: zero pad signals

to match length

blue = r

red = B_A

How to use?

• Cross correlating should tell us where each beacon signal arrived in our recorded signal
• Let’s cross-correlate each of the known beacon signals with what we recorded and plot the result

​

Absolute or relative sample delays?

• We can see peaks where each beacon signal arrived!
• But notice it only gives us relative sample delays
• Still can’t tell how many absolute samples each beacon is delayed, we don’t know when it was supposed to arrive
• Arbitrarily pick a beacon to be the reference point

​

Absolute or relative sample delays?

separated signals

Shift and recenter separated signals

• Let’s shift our axis so beacon 0 has a delay of 0

​

• We could pick any beacon to be the center
• 0 is arbitrary

Absolute or relative sample delays?

Now beacon 0 is at our new “origin” and all computations are relative to the new “0” – but how do we find T0?

3 Beacon Example

• To answer the T0 question, we must formally set up our system. Let beacon centers be: (x₀, y₀), (x₁, y₁) and (x₂, y₂)
• Time of arrivals: 𝜏₀, 𝜏₁, 𝜏₂
• Distance of beacon m (m = 0, 1, 2) is d_m = v𝜏_m = R_m (circle radii)

Circle equations: (x - x_m)² + (y - y_m)² = d²_m

​

​

Trilateration

Trilateration

Trilateration

​

​

​

Subtracting the zeroth equation yields:

and,

Trilateration

​

​

​

​

We want to write this in terms of TDOAs and unknowns!

Trilateration

​

​

​

What are our unknowns in this system?

Trilateration

​

​

​

What are our unknowns in this system?

​

Trilateration

​

​

​

What are our unknowns in this system?

​

​

​

​

Problem: 3 unknowns and 2 equations!

Solution: add another beacon to produce a third equation!

Trilateration

3 equations and 3 unknowns, so we have a solvable system!

Multilateration

We can produce overdetermined system with M beacons!

“Solving” an Overdetermined System

• After simplifying, we have more equations than unknowns (x,y)
• Can do least-squares regardless of number of beacons
• Best estimate of location if measurements are inconsistent
• If there is no exact point of intersection because of error or noise

​

​

Notes for Lab Computer Users

• Please use the lab computers and download the zip file from the lab website. Extract the files first. Click on Launch Notebook.bat. This should open the lab notebook.
• Might have to hit reload on the notebook tab for pictures to render.
• Read over the math carefully, we’ll be asking you about it during the checkoff!

​

Notes for DataHub Users

• This lab is a bit more computationally intensive than the previous ones. When many students work on it simultaneously, DataHub can slow down or become unresponsive due to limited computing resources.
• If this happens, please shut down all active kernels and try again at a later time.
• Read over the math carefully, we’ll be asking you about it during the checkoff!

​

Checking-off Today

• Follow the directions linked at bottom of the lab
• Fill out Google form: tinyurl.com/16a-checkoff-sp26
• Station number: Sit at a lab computer and enter the number ## on the monitor (c111-##)
• During checkoff:
• You will be asked a series of conceptual questions. Make sure you fully understand what is going on.
• If you want to add songs to our playlist: tinyurl.com/16a-playlist