Citation
Analysis of cell phone adaptive noise cancellation filters

Material Information

Title:
Analysis of cell phone adaptive noise cancellation filters
Creator:
Feist, Sam
Place of Publication:
Denver, CO
Publisher:
University of Colorado Denver
Publication Date:
Language:
English

Thesis/Dissertation Information

Degree:
Master's ( Master of science)
Degree Grantor:
University of Colorado Denver
Degree Divisions:
Department of Music and Entertainment Industry Studies, CU Denver
Degree Disciplines:
Recording arts
Committee Chair:
Grigoras, Catalin
Committee Members:
Smith, Jeff
Whitecotton, Cole

Notes

Abstract:
When background noise compromises the quality of a cell phone call, adaptive noise cancellation filters can be used to increase call clarity. These filters are utilized by most major cell phone manufacturers to reduce background noise during calls through the use of a secondary microphone usually located at the top of the device [1]. Unfortunately, these filters use proprietary algorithms [2] which are unavailable to forensic examiners and scientists. In the fall of 2018, Anthony Nelson published a thesis paper which proposed a method for recording and analyzing the adaptive noise reduction filters found in cell phones [3]. Nelson used his proposed method of recording and analyzing these noise reduction filters to categorize and document specific aspects of the filters and sort them by make and model. This thesis is a continuation of that research on cell phone models not covered in Nelson's original work including the iPhone Xr, iPhone Xs Max, Samsung Galaxy S7, Samsung Galaxy Note 9, and Google Pixel 1. In addition to running Nelson’s proposed method on these models, this thesis includes a test on an iPhone Xs Max using babble noise and a test on an iPhone 7, which was covered in Nelson’s thesis, for comparison.

Record Information

Source Institution:
University of Colorado Denver
Holding Location:
Auraria Library
Rights Management:
Copyright Sam Feist. Permission granted to University of Colorado Denver to digitize and display this item for non-profit research and educational purposes. Any reuse of this item in excess of fair use or other copyright exemptions requires permission of the copyright holder.

Downloads

This item has the following downloads:


Full Text
ANALYSIS OF CELL PHONE ADAPTIVE NOISE CANCELLATION FILTERS
by
SAM FEIST
BE. A., University of Cincinnati, 2017
A thesis submitted to the Faculty of the Graduate School of the University of Colorado in partial fulfilment of the requirements of the degree of Master of Science Recording Arts Program
2019


This thesis for the Master of Science degree by Sam Feist
has been approved for the Recording Arts Program by
Catalin Grigoras, Chair Jeff Smith Cole Whitecotton
Date: December 14, 2019


Feist, Sam (M.S., Recording Arts Program)
Analysis of Cell Phone Adaptive Noise Cancellation Filters Thesis directed by Associate Professor Catalin Grigoras
ABSTRACT
When background noise compromises the quality of a cell phone call, adaptive noise cancellation filters can be used to increase call clarity. These filters are utilized by most major cell phone manufacturers to reduce background noise during calls through the use of a secondary microphone usually located at the top of the device [1], Unfortunately, these filters use proprietary algorithms [2] which are unavailable to forensic examiners and scientists. In the fall of 2018, Anthony Nelson published a thesis paper which proposed a method for recording and analyzing the adaptive noise reduction filters found in cell phones [3], Nelson used his proposed method of recording and analyzing these noise reduction filters to categorize and document specific aspects of the filters and sort them by make and model. This thesis is a continuation of that research on cell phone models not covered in Nelson's original work including the iPhone Xr, iPhone Xs Max, Samsung Galaxy S7, Samsung Galaxy Note 9, and Google Pixel 1. In addition to running Nelson’s proposed method on these models, this thesis includes a test on an iPhone Xs Max using babble noise and a test on an iPhone 7, which was covered in Nelson’s thesis, for comparison.
The form and content of this abstract are approved. I recommend its publication.
Approved: Catalin Grigoras
m


I would like to dedicate this thesis to all the teachers I’ve had throughout my academic career and to my loving parents, the best teachers of them all.
IV


ACKNOWLEDGMENTS
Thank you to Jeff Smith, Catalin Grigoras, Cole Whitecotton, and Leah Haloin for running a tight ship with the NCMF and helping everyone get through the program; none of this would be possible without your dedication. Thanks to Marcus Rogers, Jason Lewis, and Greg Wales for teaching interesting and informative courses at the NCMF. I would also like to acknowledge my friends Andy Birkenhauer, Dylan Wallace, Drew Mannix, Alex Kallmeyer and Adam Lutz for lending their time and cell phones to my experiments, I would not have been able to finish this thesis without your help and I am forever grateful. Finally, I’d like to acknowledge and thank my father Larry Feist for also lending his cell phone and helping me stay grounded throughout the thesis process.
v


TABLE OF CONTENTS
CHAPTER
I. INTRODUCTION.....................................................1
Scope and Limitations............................................2
II. CELL PHONE LAYOUTS...............................................3
Apple iPhone Xr, Xs Max and 7....................................3
Samsung Galaxy S7 and Note 9.....................................5
Google Pixel 1...................................................7
III. TESTING..........................................................8
Test 1...........................................................8
Test 2...........................................................9
Test 3...........................................................9
IV. ANALYSIS AND RESULTS............................................10
Spectrograms....................................................10
FFT Spectrum....................................................17
Signal to Noise Ratios..........................................20
V. CONCLUSION......................................................23
VI. FURTHER RESEARCH................................................24
REFERENCES............................................................25
vi


LIST OF TABLES
TABLE
4.1 SNR Results............................................................21
Vll


LIST OF FIGURES
FIGURE
2.1 iPhone Xr layout...................................................................3
2.2 iPhone Xs Max layout................................................................4
2.3 iPhone 7 layout.....................................................................4
2.4 Samsung Galaxy S7 front view........................................................5
2.5 Samsung Galaxy S7 back view.........................................................6
2.6 Samsung Galaxy Note 9 layout.......................................................6
2.7 Google Pixel 1......................................................................7
4.1 iPhone Xr with Noise Cancellation off, white noise playback at 70db(A).............11
4.2 iPhone Xr with Noise Cancellation on, white noise playback at 70db(A)..............11
4.3 iPhone Xr with Noise Cancellation off, white noise playback at 80db(A).............11
4.4 iPhone Xr with Noise Cancellation on, white noise playback at 80db(A)..............12
4.5 iPhone Xs Max with Noise Cancellation off, white noise playback at 70db(A).........12
4.6 iPhone Xs Max with Noise Cancellation on, white noise playback at 70db(A)..........13
4.7 iPhone Xs Max with Noise Cancellation off, white noise playback at 80db(A).........13
4.8 iPhone Xs Max with Noise Cancellation on, white noise playback at 80db(A)..........14
4.9 iPhone Xs Max with Noise Cancellation off, babble noise playback at 70db(A)........15
4.10 iPhone Xs Max with Noise Cancellation on, babble noise playback at 70db(A)........15
4.11 iPhone Xs Max with Noise Cancellation off, babble noise playback at 80db(A).......15
4.12 iPhone Xs Max with Noise Cancellation on, babble noise playback at 80db(A)........16
4.13 iPhone 7 with noise cancellation off recorded in front of oven blower.............16
4.14 iPhone 7 with noise cancellation on recorded in front of oven blower..............17
viii


4.15 iPhone Xs Max white noise playback at 70db(A) FFTs.............................18
4.16 iPhone Xs Max white noise playback at 80db(A) FFTs.............................18
4.17 iPhone Xr white noise playback at 70db(A) FFTs..................................18
4.18 iPhone Xr white noise playback at 80db(A) FFTs..................................19
4.19 iPhone Xs Max babble noise playback at 70db(A) FFTs............................19
4.20 iPhone Xs Max babble noise playback at 80db(A) FFTs............................19
4.21 iPhone 7 oven blower noise FFTs................................................20
IX


CHAPTERI
INTRODUCTION
Over the last decade, noise cancellation has become effective and cheap enough to use in mobile phones [4], Most smart phone manufacturers make use of the technology today and implement it in their products under setting names such as “noise reduction” or “phone noise cancellation” (as is the case in iPhones). These noise reduction filters have been an area of cell phones without much forensic research until Anthony Nelson’s thesis “Proposed Method for Recording and Analyzing Cell Phone Adaptive Noise Reduction Filters” was published in the fall of 2018.
Nelson’s proposed method recorded and documented aspects of noise reduction filters and categorized them by phone make and model. His testing method consisted of playing a broadband noise over loudspeakers while someone spoke into the cell phone being studied (cell phone A) and recording the call using a call recording application on the phone receiving the call (cell phone B) [3], The caller using cell phone A was positioned in front of the loudspeakers so the broadband noise would trigger the threshold of the filter and activate the noise cancellation feature. The broadband noise consisted of a twenty second clip of white noise which was used because white noise evenly disperses noise across the audible sound spectrum [5], The broadband noise clip also included impulses at the one and nineteen second marks for later synchronization. The recordings were made with the broadband noise played back at two different volumes: 70db(A) and 80db(A) which were measured using an SPL meter. Three recordings were made per cell phone with the noise cancellation feature turned on and then three more were made with the cancellation turned off for comparison. The recorded calls were then imported into Adobe Audition where they were trimmed down to the twenty seconds matching
1


the broadband noise and analyzed via spectrograms, FFT frequency analysis, and Signal to Noise Ratios (SNR).
The work done in this thesis is comprised of three tests: the first uses Nelson’s proposed method on newer models of cell phones, the second test involves a similar testing method to Nelson’s but with babble noise (noise that is comprised of multiple simultaneous speech sources [6] which obscures any one source from being intelligible) instead of white noise, and the third uses a novel test on a phone covered in Nelson’s original thesis for comparison. The makes and models of cell phones used in the first two tests include the following:
Apple iPhone Xr Apple iPhone Xs Max Samsung Galaxy S7 Samsung Galaxy Note 9 Google Pixel 1
The novel test was conducted on an Apple iPhone 7 running the newest version of iOS,
13.1.2.
Scope and Limitations
The scope of this thesis is limited to the phones studied from Apple, Samsung, and Google. This thesis does not attempt to discern or interpret the proprietary algorithms or code used in the noise reduction filters of these phones but instead records and interprets their unique impact on recorded calls made with these makes and models.
2


CHAPTER II
CELL PHONE LAYOUTS
While cell phones make use of a secondary microphone (sometimes more than two) for noise reduction filters to operate [1], the location of these additional microphones varies between cell phone makes and models. The following are the microphone layouts of the cell phones studied in this thesis.
Apple iPhone Xr, Xs Max and 7
While the different models of iPhones used for this test generally place their additional microphones in the same location, layouts for each iPhone used are included here as the dimensions vary between models.
Figure 2.1 iPhone Xr layout [7]
3


1. Volume up/down buttons
2. Ring/silent switch
3. Proximity sensor
4. Ambient light sensor
5. Receiver (stereo speaker)
6. Front camera
7. TrueDepth cameras
8. Side button
9. True Tone flash
10. Microphone
11. Bottom microphones
12. Lightning connector
13. Stereo speaker
Figure 2.2 iPhone Xs Max layout [8]
Figure 2.3 iPhone 7 layout [9]
4


Samsung Galaxy S7 and Galaxy Note 9
It is important to note that the Samsung phones used in this test do not allow the user to toggle the noise reduction setting on and off, noise reduction is always turned on in these phones by default. Samsung Galaxy smartphones used to allow the user to turn noise reduction off but since the Galaxy S6 model that option has been removed [3],
SIM card / Memory card
tray
LED indicator Proximity sensor
Touchscreen Edge screen
Recents key
Headset jack Multipurpose jack
Receiver
Front camera GPS antenna
Power key
Edge screen
Home key (Fingerprint recognition sensor)
Back key
Loud speaker Microphone
Figure 2.4 Samsung Galaxy S7 front view [10]
5


Microphone
Rear camera
NFC antenna/MST antenna / Wireless charging coil
Flash
Volume key
Main antenna
Figure 2.5 Samsung Galaxy S7 back view [10]
Figure 2.6 Samsung Galaxy Note 9 layout [11]
6


Google Pixel 1
Like the Samsung Galaxy smartphone, the Google Pixel also does not allow the user the option to toggle noise reduction on or off.
e o
0(D 0
O
0
0
0
0 0 0
Figure 2.7 Google Pixel 1 where point 7 is the primary microphone and the secondary microphone is located to the right of the rear facing camera at point 11 on the diagram [12]
7


CHAPTER III
TESTING
Test 1
The first test was modeled after Nelson’s original test and involved playing a clip of white noise over loudspeakers in front of cell phone A while a call was made from cell phone A to cell phone B. Noise cancellation filters work to improve signal intelligibility during a phone call and thus calls from cell phone A to cell phone B were necessary to capture the signal for comparison between the filter being turned on and off. This call was recorded on cell phone B using the application TapeACall which recorded the phone calls at an 8kHz sampling rate (this is the default setting for TapeACall as cell phone signals only transmit at an 8kHz sampling rate [13]). The white noise clip included impulses at the one and nineteen second marks for later synchronization and was played back over the loudspeakers at 70db(A) and 80db(A) (both measured using an SPL meter). Each cell phone was recorded three times with its noise reduction filter on and three times with its noise reduction filter turned off (if applicable). The recorded phone calls were then trimmed down using Adobe Audition to the twenty seconds matching the noise playback and analyzed via spectrograms, FFT charts, and SNRs.
The Fast Fourier Transform, or FFT, is an algorithm that can be used to convert the time domain of an audio signal into the frequency domain [14], allowing a recorded signal to be viewed on a graph where the x-axis is the frequency in Hz and the y-axis is the gain in dB. This produces an FFT spectrum which displays the loudness level of each frequency present in the entire signal. In addition to the FFT spectrum, spectrograms were also produced of the recorded calls which show time in seconds along the x-axis and frequency along the y-axis. These graphs
8


display the frequencies present at each moment in time in the signal and also show loudness via a heatmap style display where the brighter colors are louder and the darker colors are quieter.
Test 2
The second test involved repeating the method of the first test but using babble noise instead of white noise as the controlled noisy signal. This test was run on an iPhone Xs Max and was conducted to simulate a more realistic noisy condition for noise cancellation than white noise.
Test 3
The third test consisted of recording an iPhone 7 running the latest version of iOS (version 13.1.2) in front of an oven blower with the “phone noise cancellation” setting turned on and then off. The spectrograms of the two recordings were captured and compared.
9


CHAPTER IV
ANALYSIS AND RESULTS
The trimmed, recorded clips were analyzed via spectrograms, FFT charts and SNRs and compared to each other. The idea behind these comparisons is that there should be a discernible difference between the results when the noise cancellation filters are turned on and off, therefore allowing for documentation of what a particular phone’s noise cancellation looks like on a recorded call. However, when listening back to these recordings very little difference, if any at all, existed between the filter being turned on or off in the settings. Furthermore, since Samsung and Google manufactured smartphones do not allow the user to toggle this setting, getting a picture of the effect that noise reduction had on these phones becomes difficult. Without the option to turn the filter on and off, comparison between the filter affecting the signal and not affecting it is not possible.
Spectrograms
When observing the spectrograms of the recorded calls, it was expected that there would be a difference in the level of background noise present in between the spoken words of the caller. However, this was not the case and the background noise appeared to be reduced whether or not the noise reduction setting was turned on. The following are the spectrograms of the iPhone models from Test 1 which allowed for the noise reduction setting to be turned off.
10


Figure 4.1 iPhone Xr with Noise Cancellation off, white noise playback at 70db(A)
Figure 4.2 iPhone Xr with Noise Cancellation on, white noise playback at 70db(A)
Figure 4.3 iPhone Xr with Noise Cancellation off, white noise playback at 80db(A)
11


Figure 4.4 iPhone Xr with Noise Cancellation on, white noise playback at 80db(A)
Figure 4.5 iPhone Xs Max with Noise Cancellation off, white noise playback at 70db(A)
12


Figure 4.6 iPhone Xs Max with Noise Cancellation on, white noise playback at 70db(A)
Figure 4.7 iPhone Xs Max with Noise Cancellation off, white noise playback at 80db(A)
13


Figure 4.8 iPhone Xs Max with Noise Cancellation on, white noise playback at 80db(A)
As can be seen from the Test 1 spectrograms of the iPhones with noise reduction turned on and off, there is no major difference between the amount of noise in between the spoken words. The dynamic range of the signal with the filter turned on is 58.34dB as calculated by Adobe Audition while the dynamic range of the signal with the filter turned off is 59.97dB. A higher dynamic range would be expected in the signal with the filter turned on as it should reduce the noise therefore lowering the signal in certain sections. This prompted Test 2 and Test 3, which used babble noise on an iPhone Xs Max and an oven blower on an iPhone 7, respectively. Here are those spectrograms:
14


Figure 4.10 iPhone Xs Max with Noise Cancellation on, babble noise playback at 70db(A)
Figure 4.11 iPhone Xs Max with Noise Cancellation off, babble noise playback at 80db(A)
15


Figure 4.12 iPhone Xs Max with Noise Cancellation on, babble noise playback at 80db(A)
16


Figure 4.14 iPhone 7 with noise cancellation on recorded in front of oven blower
Again, no discernable difference in background noise can be noted with the noise reduction filter turned off in the iPhone’s settings. In fact, the noise seemed to be reduced even when the noise cancellation setting was turned off.
FFT Spectrum
The Fast Fourier Transform, or FFT, is an algorithm that can be used to convert the time domain of an audio signal into the frequency domain [14], allowing a recorded signal to be viewed on a graph where the x-axis is the frequency in Hz and the y-axis is the gain in dB. The recorded calls were ran through Adobe Auditions’ frequency analysis window which allows for an FFT view of the signal. The FFT spectrum was captured of a recording at either the 70db(A) or 80db(A) noise level playback with the filter turned off and then the FFT for the recording at the same noise level but with the filter turned on was captured and overlaid on the first graph. A red line was used for the filter turned off and a green line was used for the filter turned on. Here are those charts:
17


Frequency Analysis =
Scale: Linear Ch Hold: 12 3 4
Display: Lines •* Top Channel Channel 1 ■*' ( Scan Selection )
v Advanced
FFTSIze: 6S536 v window: Blackman ~ 0 dB Reference: 0 dBFS
Figure 4.15 iPhone Xs Max white noise playback at 70db(A) FFTs
Frequency Analysis :
« y v ' rvTl'
y



100 200 300 400 SOO 600
lk lJk 12k 131
24k 25k 2.6k 2.7k 28k 2.91

isplay: Lines v Top Channel Channel 1 Advanced
T Size: 65536 - Window: Blackman
( Son Selection )
Figure 4.16 iPhone Xs Max white noise playback at 80db(A) FFTs
Figure 4.17 iPhone Xr white noise playback at 70db(A) FFTs
18


Figure 4.18 iPhone Xr white noise playback at 80db(A) FFTs
Figure 4.19 iPhone Xs Max babble noise playback at 70db(A) FFTs
Figure 4.20 iPhone Xs Max babble noise playback at 80db(A) FFTs
19


Figure 4.21 iPhone 7 oven blower noise FFTs A difference in frequency response for the noise cancellation filter turned off and on was expected to be noticeable in the FFT charts of each recorded call. However, it can be seen in the graphs that this is not the case and that the iPhone models responded almost the same whether or not the noise cancellation filter was turned on or off. No frequencies were significantly reduced and the FFT spectrum responses were quite similar.
Signal to Noise Ratios
Signal to noise ratios, or SNRs, were found for each iteration of the tests based on phone
model, noise type, noise playback volume and whether the filter was on or off. Since each
iteration was recorded three times, the SNR for each of those was found using a Matlab script
and then averaged. In the Matlab script the audio signal represented by “y” is the controlled
noise signal, the generated white noise signal or the babble noise recording depending on the
test. Here is the Matlab script and the results:
[namel, pathl] =uigetfile [x, fs] = audioread(namel)
[name2, pathl] = uigetfile [y, fs] = audioread(name2) r = snr(x, y)
20


Table 4.1 SNR Results
Average SNR of recorded call with noise reduction ON Average SNR of recorded call with noise reduction OFF
iPhone Xr, white noise at 70db(A) -4.343 dB -4.278 dB
iPhone Xr, white noise at 80db(A) -4.799 dB -4.278 dB
iPhone Xs Max, white noise at 70db(A) -4.812 dB -4.323 dB
iPhone Xs Max, white noise at 80db(A) -11.329 dB -14.554 dB
iPhone Xs Max, babble noise at 70db(A) 7.8159 dB 7.0566 dB
iPhone Xs Max, babble noise at 80db(A) 8.0167 dB 8.2357 dB
Samsung Galaxy S7, white noise at 70db(A) 3.246 dB N/A
Samsung Galaxy S7, white noise at 80db(A) 5.902 dB N/A
Samsung Galaxy Note 9, white noise at 70db(A) -2.448 dB N/A
Samsung Galaxy Note 9, white noise at 80db(A) -2.441 dB N/A
Google Pixel, white noise at 70db(A) -1.319 dB N/A
Google Pixel, white noise at 80db(A) 0.387 dB N/A
It was expected that the SNRs would be noticeably higher when the filter setting was turned on due to the filter reducing noise and thus increasing the ratio of signal to noise, but as with the spectrogram and FFT spectrums the expected results were not the case. There was a
21


minor difference between the SNRs of some of the filters turned on and off but the change was not consistent: some SNRs were higher when the filter was on and others were lower when the filter was on. For example, the SNR increased when the noise reduction filter was turned off on the iPhone Xs Max during the babble noise test at 80db(A) but it decreased from filter-on to filter-off during the babble noise test at 70db(A).
22


CHAPTER V
CONCLUSION
Based on the analysis of the test results, a discernible difference between the noise reduction filter turned on and off could not be found in those phone models which allow the user to toggle the noise reduction setting. Furthermore, the fact that most major phone manufacturers today such as Samsung and Google do not allow the user to toggle the noise reduction setting on and off makes documentation of the filter’s effects on the call signal very difficult. This method might be useful in a select few cases but overall the study of noise cancellation filters does not seem like a very practical way of identifying the make and model of a cell phone based on a recorded call. The very small difference between the filter turned off and on is not always consistent and certainly not enough to confidently identify a particular cell phone.
23


CHAPTER VI
FURTHER RESEARCH
While noise reduction filters are used in most modern cell phones, the study of them in a forensic setting may not be the most practical way of identifying a make and model of cell phone. The fact that most phones do not give the user the option to turn this setting off is the key sticking point in this research and renders comparison nearly impossible for those models of cell phone. Out of the phone models studied, only the Apple iPhone models actually allowed the user to turn noise reduction off and even with that setting turned off it was apparent that some level of noise reduction was still present. Cell phones are very important area of research in forensics as their use becomes more ubiquitous across the world but perhaps noise reduction filters should not be the forefront of that research.
24


REFERENCES
[1] Thom, Thomas. “Background Noise Reduction: One of Your Smartphone's Greatest Tools.” TechRadar, TechRadar, 28 Feb. 2014, www.techradar.com/news/phone-and-communications/mobile-phones/background-noise-reduction-one-of-vour-smartphone-s-greatest-tools-1229667.
[2] Williams, Martyn. “Apple Sued Over Noise Reduction Technology.” CIO, IDG News Service, 6 July 2012, www.cio.com/article/2394362/apple-sued-over-noise-reduction-technology.html.
[3] Nelson, Anthony. “PROPOSED METHOD FOR RECORDING AND ANALYZING CELL PHONE ADAPTIVE NOISE REDUCTION FILTERS.” University of Colorado, Denver, 2018.
[4] Monteith, David. “Ambient Noise Cancellation Comes to Mobile Phone.” Wolfsonmicro.com, Aug. 2010,
d3uzseaevmutzl.cloudfront.net/pubs/whitePaper/WP Ambient Noise Cancellation Comes to Mobile Phone.pdf.
[5] Castro, Joseph. “What Is White Noise?” LiveScience, Purch, 29 July 2013, www. livescience. com/3 8 3 87-what-i s-white-noi se. html.
[6] Hall, Joseph L., and James L. Flanagan. “Intelligibility and Listener Preference of Telephone Speech in the Presence of Babble Noise.” The Journal of the Acoustical Society of America, vol. 127, no. 1, 5 Jan. 2010, pp. 280-285., doi: 10.1121/1.3263603.
[7] “IPhone XR - Technical Specs.” Apple , 2018, www.apple.com/lae/iphone-xr/specs.
[8] “The IPhone Xs /Xs Max Service Technical Guide for Repairing/Reassembling.” EBay, 2019, www.ebav.com/itm/The-iPhone-Xs-Xs-Max-Service-Manual-Guide-to-Repairing-Reassembling-/! 32809360900.
[9] Chew, Tung Shen. “Position of MEMS Microphones on an IPhone 7.” Vesper, 2017, vespermems.com/wp-content/uploads/2017/10/Vesper-Microphone-Arravs-whitepaper-l.pdf.
[10] “Galaxy S7 Layout and Galaxy S7 Edge Layout.” Galaxy S7 Guides, 2016, gadgetguideonline.com/s7/galaxy-s7-online-manual/galaxy-s7-layout-and-galaxy-s7-edge-layout/.
[11] Groenheijde, Michel. “Samsung Galaxy Note 9 Handleiding Nu Beschikbaar.” Galaxy Club -De Onafhankelijke Samsung Experts, 13 Nov. 2018, www.galaxyclub.nl/nieuws/samsung-galaxy-note-9-handleiding/.
25


[12] “Pixel Phone Hardware Diagram - Pixel Phone Help.” Google, Google, 2016, support.google.com/pixelphone/answer/7157629?hl=en.
[13] “Sampling Frequency and Bit Resolution for Speech Signal Processing.” Sampling Frequency and Bit Resolution for Speech Signal Processing (Theory) : Speech Signal Processing Laboratory : Biotechnology and Biomedical Engineering : Amrita Vishwa Vidyapeetham Virtual Lab, 2011, vlab.amrita.edu/?sub=3&brch=164&sim=474&cnt=l.
[14] Heckbert, Paul. Fourier Transforms and the Fast Fourier Transform (FFT) Algorithm. Jan. 1995, www.cs.cmu.edu/afs/andrew/scs/cs/15-463/2001/pub/www/notes/fourier/fourier.pdf.
26


Full Text

PAGE 1

ANALYSIS OF CELL PHONE ADAPTIVE NOISE CANCELLATION FILTERS by SAM FEIST B.F.A., University of Cincinnati, 2017 A thesis submitted to the Faculty of the Graduate School of the University of Colorado in partial fulfilment of the requirements of the degree of Master of Science Recording Arts Program 2019

PAGE 2

ii This thesis for the Master of Science degree by Sam Feist has been approved for the Recording Arts Program by Catalin Grigoras, Chair Jeff Smith Cole Whitecotton Date: December 14, 2019

PAGE 3

iii Feist, Sam (M.S., Recording Arts Program) A nalysis of C ell P hone Ad aptive N oise C ancellation F ilters Thesis directed by Associate Professor Catalin Grigoras ABSTRACT When background noise compromises the quality of a cell phone call, adaptive noise cancellation filters can be used to increase call clarity. These filters are utilized by most major cell phone manufacturers to reduce background noise during calls through the use of a secondary microphone usually located at the top of the device [1]. Unfortunately, these filters use proprietary algorithms [2] which are unavailable to forensic examiners and scientists. In the fall of 2018, Anthony Nelson published a thesis paper which proposed a method for recording and analyzing the adaptive noise reduction filters found in cell phones [3]. Nelson used his proposed method of recording and analyzing these noise reduction filters to categori ze and document specific aspects of the filters and sort them by make and model. This thesis is a continuation of that research on cell phone models not covered in Nelson's original work including the iPhone Xr, iPhone Xs Max, Samsung Galaxy S7, Samsung Ga laxy Note 9, and Google Pixel 1. In addition to running Nelson’s proposed method on these models, this thesis includes a test on an iPhone Xs Max using babble noise and a test on an iPhone 7, which was covered in Nelson’s thesis, for comparison. The form and content of this abstract are approved. I recommend its publication. Approved: Catalin Grigoras

PAGE 4

iv I would like to dedicate this thesis to all the teachers I’ve had throughout my academic career and to my loving parents, the best teachers of them all.

PAGE 5

v ACKNOWLEDGMENTS Thank you to Jeff Smith, Catalin Grigoras, Cole Whitecotton, and Leah Haloin for running a tight ship with the NCMF and helping everyone get through the program; none of this would be possible without your dedication. Thanks to Marcus Roge rs, Jason Lewis, and Greg Wales for teaching interesting and informative courses at the NCMF. I would also like to acknowledge my friends Andy Birkenhauer, Dylan Wallace, Drew Mannix, Alex Kallmeyer and Adam Lutz for lending their time and cell phones to m y experiments, I would not have been able to finish this thesis without your help and I am forever grateful. Finally, I’d like to acknowledge and thank my father Larry Feist for also lending his cell phone and helping me stay grounded throughout the thesis process.

PAGE 6

vi TABLE OF CONTENTS CHAPTER I. INTRODUCTION ...............................................................................................................1 Scope and Limitations ..........................................................................................................2 II. CELL PHONE LAYOUTS ..................................................................................................3 Apple iPhone Xr, Xs Max and 7 ..........................................................................................3 Samsung Galaxy S7 and Note 9...........................................................................................5 Google Pixel 1 ......................................................................................................................7 III. TESTING .............................................................................................................................8 Test 1 ....................................................................................................................................8 Test 2 ....................................................................................................................................9 Test 3 ....................................................................................................................................9 IV. ANALYSIS AND RESULTS ............................................................................................10 Spectrograms ......................................................................................................................10 FFT Spectrum ....................................................................................................................17 Signal to Noise Ratios ........................................................................................................20 V. CONCLUSION ..................................................................................................................23 VI. FURTHER RESEARCH ...................................................................................................24 REFERENCES ..............................................................................................................................25

PAGE 7

vii LIST OF TABLES TABLE 4.1 SNR Results .............................................................................................................................21

PAGE 8

viii LIST OF FIGURES FIGURE 2.1 iPhone Xr layout ........................................................................................................................3 2.2 iPhone Xs Max layout ................................................................................................................4 2.3 iPhone 7 layout ..........................................................................................................................4 2.4 Samsung Galaxy S7 front view ..................................................................................................5 2.5 Samsung Galaxy S7 back view ..................................................................................................6 2.6 Samsung Galaxy Note 9 layout ..................................................................................................6 2.7 Google Pixel 1............................................................................................................................7 4.1 iPhone Xr with Noise Cancellation off, white noise playback at 70db(A) ..............................11 4.2 iPhone Xr with Noise Cancellation on, white noise playback at 70db(A) ..............................11 4.3 iPhone Xr with Noise Cancellation off, white noise playback at 80db(A) ..............................11 4.4 iPhone Xr with Noise Cancellation on, white noise playback at 80db(A) ..............................12 4.5 iPhone Xs Max with Noise Cancellation off, white noise playback at 70db(A) .....................12 4.6 iPhone Xs Ma x with Noise Cancellation on, white noise playback at 70db(A) ......................13 4.7 iPhone Xs Max with Noise Cancellation off, white noise playback at 80db(A) .....................13 4.8 iPhone Xs Max with Noise Cancellation on, white noise playback at 80db(A) ......................14 4.9 iPhone Xs Max with Noise Cancellation off, babble noise playback at 70db(A) ...................15 4.10 iPhone Xs Max with Noise Cancellation on, babble noise playback at 70db(A) ..................15 4.11 iPhone Xs Max with Noise Cancellation off, babble noise playback at 80db(A) .................15 4.12 iPhone Xs Max with Noise Cancellation on, babble noise playback at 80db(A) ..................16 4.13 iPhone 7 with noise cancellation off recorded in front of oven blower .................................16 4.14 iPhone 7 with noise cancellation on recorded in front of oven blower .................................17

PAGE 9

ix 4.15 iPhone Xs Max white noise playback at 70db( A) FFTs ........................................................18 4.16 iPhone Xs Max white noise playback at 80db(A) FFTs ........................................................18 4.17 iPhone Xr white noise playback at 70db(A) FFTs .................................................................18 4.18 iPhone Xr white noise playback at 80db(A) FFTs .................................................................19 4.19 iPhone Xs Max babble noise playback at 70db(A) FFTs ......................................................19 4.20 iPhone Xs M ax babble noise playback at 80db(A) FFTs ......................................................19 4.21 iPhone 7 oven blower noise FFTs ..........................................................................................20

PAGE 10

1 CHAPTER I INTRODUCTION Over the last decade, noise cancellation has become effective and cheap enough to use in mobile phones [4]. Most smart phone manufacturers make use of the technology today and implement it in their products under setting names such as “noise reduction” or “phone noise cancellation” (as is the case in iPhones). These noise reduction filters have been an area of cell phones without much forensic research until Anthony Nelson’s thesis “Proposed Method for Recording and Analyzing Cell Phone Adaptive Noise Reduc tion Filters” was published in the fall of 2018. Nelson’s proposed method recorded and documented aspects of noise reduction filters and categorized them by phone make and model. His testing method consisted of playing a broadband noise over loudspeakers while someone spoke into the cell phone being studied (cell phone A) and recording the call using a call recording application on the phone receiving the call (cell phone B) [3]. The caller using cell phone A was positioned in front of the loudspeakers so the broadband noise would trigger the threshold of the filter and activate the noise cancellation feature. The broadband noise consisted of a twenty second clip of white noise which was used because white noise evenly disperses noise across the audible sou nd spectrum [5]. The broadband noise clip also included impulses at the one and nineteen second marks for later synchronization. The recordings were made with the broadband noise played back at two different volumes: 70db(A) and 80db(A) which were measured using an SPL meter. Three recordings were made per cell phone with the noise cancellation feature turned on and then three more were made with the cancellation turned off for comparison. The recorded calls were then imported into Adobe Audition where they were trimmed down to the twenty seconds matching

PAGE 11

2 the broadband noise and analyzed via spectrograms, FFT frequency analysis, and Signal to Noise Ratios (SNR). The work done in this thesis is comprised of three tests: the first uses Nelson’s proposed metho d on newer models of cell phones, the second test involves a similar testing method to Nelson’s but with babble noise (noise that is comprised of multiple simultaneous speech sources [6] which obscures any one source from being intelligible) instead of whi te noise, and the third uses a novel test on a phone covered in Nelson’s original thesis for comparison. The makes and models of cell phones used in the first two tests include the following: Apple iPhone Xr Apple iPhone Xs Max Samsung Galaxy S7 Samsun g Galaxy Note 9 Google Pixel 1 The novel test was conducted on an Apple iPhone 7 running the newest version of iOS, 13.1.2. Scope and Limitations The scope of this thesis is limited to the phones studied from Apple, Samsung, and Google. This thesis doe s not attempt to discern or interpret the proprietary algorithms or code used in the noise reduction filters of these phones but instead records and interprets their unique impact on recorded calls made with these makes and models.

PAGE 12

3 CHAPTER II CELL PHO NE LAYOUTS While cell phones make use of a secondary microphone (sometimes more than two) for noise reduction filters to operate [1], the location of these additional microphones varies between cell phone makes and models. The following are the microphone layouts of the cell phones studied in this thesis. Apple iPhone Xr, Xs Max and 7 While the different models of iPhones used for this test generally place their additional microphones in the same location, layouts for each iPhone used are included here a s the dimensions vary between models. Figure 2.1 iPhone Xr layout [7]

PAGE 13

4 Figure 2.2 iPhone Xs Max layout [8] Figure 2.3 iPhone 7 layout [9]

PAGE 14

5 Samsung Galaxy S7 and Galaxy Note 9 It is important to note that the Samsung phones used in this test do not allow the user to toggle the noise reduction setting on and off, noise reduction is always turned on in these phones by default. Samsung Galaxy smartphones used to allow the user to turn noise reduction off but since the Galaxy S6 model that option has bee n removed [3]. Figure 2.4 Samsung Galaxy S7 front view [10]

PAGE 15

6 Figure 2.5 Samsung Galaxy S7 back view [10] Figure 2.6 Samsung Galaxy Note 9 layout [11]

PAGE 16

7 Google Pixel 1 Like the Samsung Galaxy smartphone, the Google Pixel also does not allow the user t he option to toggle noise reduction on or off. Figure 2.7 Google Pixel 1 where point 7 is the primary microphone and the secondary microphone is located to the right of the rear facing camera at point 11 on the diagram [12]

PAGE 17

8 CHAPTER III TESTING Test 1 The first test was modeled after Nelson’s original test and involved playing a clip of white noise over loudspeakers in front of cell phone A while a call was made from cell phone A to cell phone B. Noise cancellation filters work to improve signal intelligibility during a phone call and thus calls from cell phone A to cell phone B were necessary to capture the signal for comparison between the filter being turned on and off. This call was recorded on cell phone B using the application TapeACall which recorded the phone calls at an 8kHz sampling rate (this is the default setting for TapeACall as cell phone signals only transmit at an 8kHz sampling rate [13]). The white noise clip included impulses at the one and nineteen second marks for later synchronizati on and was played back over the loudspeakers at 70db(A) and 80db(A) (both measured using an SPL meter). Each cell phone was recorded three times with its noise reduction filter on and three times with its noise reduction filter turned off (if applicable). The recorded phone calls were then trimmed down using Adobe Audition to the twenty seconds matching the noise playback and analyzed via spectrograms, FFT charts, and SNRs. The Fast Fourier Transform, or FFT, is an algorithm that can be used to convert the time domain of an audio signal into the frequency domain [14], allowing a recorded signal to be viewed on a graph where the x axis is the frequency in Hz and the y axis is the gain in dB. This produces an FFT spectrum which displays the loudness level of each frequency present in the entire signal. In addition to the FFT spectrum, spectrograms were also produced of the recorded calls which show time in seconds along the x ax is and frequency along the y axis. These graphs

PAGE 18

9 display the frequencies present at each moment in time in the signal and also show loudness via a heatmap style display where the brighter colors are louder and the darker colors are quieter. Test 2 The second test involved repeating the method of the first test but using babble noise instead of white noise as the controlled noisy signal. This test was run on an iPhone Xs Max and was conducted to simulate a more realistic noisy condition for noise cancellation than white noise. Test 3 The third test consisted of recording an iPhone 7 running the latest version of iOS (version 13.1.2) in front of an oven blower with the “phone noise cancellation” setting turned on and then off. The spectrograms of the two recordings were captured and compared.

PAGE 19

10 CHAPTER IV ANALYSIS AND RESULTS The trimmed, recorded clips were analyzed via spectrograms, FFT charts and SNRs and compared to each other. The idea behind these comparisons is that there should be a discernible difference between the results when the noise cancellation filters are turned on and off, therefore allowing for documentation of what a particular phone’s noise cancellation looks like on a recorded call. However, when listening back to these recording s very little difference, if any at all, existed between the filter being turned on or off in the settings. Furthermore, since Samsung and Google manufactured smartphones do not allow the user to toggle this setting, getting a picture of the effect that no ise reduction had on these phones becomes difficult. Without the option to turn the filter on and off, comparison between the filter affecting the signal and not affecting it is not possible. Spectrograms When observing the spectrograms of the recorded c alls, it was expected that there would be a difference in the level of background noise present in between the spoken words of the caller. However, this was not the case and the background noise appeared to be reduced whether or not the noise reduction set ting was turned on. The following are the spectrograms of the iPhone models from Test 1 which allowed for the noise reduction setting to be turned off.

PAGE 20

11 Figure 4.1 iPhone Xr with Noise Cancellation off, white noise playback at 70db(A) Figure 4.2 iPhone Xr with Noise Cancellation on, white noise playback at 70db(A) Figure 4.3 iPhone Xr with Noise Cancellation off, white noise playback at 80db(A)

PAGE 21

12 Figure 4.4 iPhone Xr with Noise Cancellation on, white noise playback at 80db(A) Figure 4.5 iPhone Xs Ma x with Noise Cancellation off, white noise playback at 70db(A)

PAGE 22

13 Figure 4.6 iPhone Xs Max with Noise Cancellation on, white noise playback at 70db(A) Figure 4.7 iPhone Xs Max with Noise Cancellation off, white noise playback at 80db(A)

PAGE 23

14 Figure 4.8 iPhone Xs Max with Noise Cancellation on, white noise playback at 80db(A) As can be seen from the Test 1 spectrograms of the iPhones with noise reduction turned on and off, there is no major difference between the amount of noise in between the spoken wo rds. The dynamic range of the signal with the filter turned on is 58.34dB as calculated by Adobe Audition while the dynamic range of the signal with the filter turned off is 59.97dB. A higher dynamic range would be expected in the signal with the filter tu rned on as it should reduce the noise therefore lowering the signal in certain sections. This prompted Test 2 and Test 3, which used babble noise on an iPhone Xs Max and an oven blower on an iPhone 7, respectively. Here are those spectrograms:

PAGE 24

15 Figure 4.9 iPhone Xs Max with Noise Cancellation off, babble noise playback at 70db(A) Figure 4.10 iPhone Xs Max with Noise Cancellation on, babble noise playback at 70db(A) Figure 4.11 iPhone Xs Max with Noise Cancellation off, babble noise playback at 80db(A)

PAGE 25

16 Figure 4.12 iPhone Xs Max with Noise Cancellation on, babble noise playback at 80db(A) Figure 4.13 iPhone 7 with noise cancellation off recorded in front of oven blower

PAGE 26

17 Figure 4.14 iPhone 7 with noise cancellation on recorded in front of oven blower Again, no discernable difference in background noise can be noted with the noise reduction filter turned off in the iPhone’s settings. In fact, the noise seemed to be reduced even when the noise cancellation setting was turned off. FFT Spectrum The Fast Fourier Transform, or FFT, is an algorithm that can be used to convert the time domain of an audio signal into the frequency domain [14], allowing a recorded signal to be viewed on a graph where the x axis is the frequency in Hz and the y axis is the gain in dB. The recorded calls were ran through Adobe Auditions’ frequency analysis window which allows for an FFT view of the signal. The FFT spectrum was captured of a recording at either the 70db(A) or 80db(A) noise level playback with the filter turned off and then the FFT for the recording at the same noise level but with the filter turned on was captured and overlaid on the first graph. A red line was used for the filter turned off and a green line was used for the filter turned on. Here are those charts:

PAGE 27

18 Figure 4.15 iPhone Xs Max white noise playback at 70db(A) FFTs Figure 4.16 iPhone Xs Max white noise playback at 80db(A) FFTs Figure 4.17 iPhone Xr white noise playback at 70db(A) FFTs

PAGE 28

19 Figure 4.18 iPhone Xr white noise playback at 80db(A) FFTs Figure 4.19 iPhone Xs Max babble noise playback at 70db(A) FFTs Figure 4.20 iPhone Xs Max babble noise playback at 80db(A) FFTs

PAGE 29

20 Figure 4.21 iPhone 7 oven blower noise FFTs A difference in frequency response for the noise cancellation filter turned off and on was expected to be noticeable in the FFT charts of each recorded call. However, it can be seen in the graphs that this is not the case and that the iPhone models responded almost the same whether or not the noise cancellation filter was turned on o r off. No frequencies were significantly reduced and the FFT spectrum responses were quite similar. Signal to Noise Ratios Signal to noise ratios, or SNRs, were found for each iteration of the tests based on phone model, noise type, noise playback volum e and whether the filter was on or off. Since each iteration was recorded three times, the SNR for each of those was found using a Matlab script and then averaged. In the Matlab script the audio signal represented by “y” is the controlled noise signal, the generated white noise signal or the babble noise recording depending on the test. Here is the Matlab script and the results: [name1, path1] = uigetfile [x, fs] = audioread(name1) [name2, path1] = uigetfile [y, fs] = audioread(name2) r = snr(x, y)

PAGE 30

21 Table 4.1 SNR Results Average SNR of recorded call with noise reduction ON Average SNR of recorded call with noise reduction OFF iPhone Xr, white noise at 70db(A) 4.343 dB 4.278 dB iPhone Xr, white noise at 80db(A) 4.799 dB 4.278 dB iPhone Xs Max, white noise at 70db(A) 4.812 dB 4.323 dB iPhone Xs Max, white noise at 80db(A) 11.329 dB 14.554 dB iPhone Xs Max, babble noise at 70db(A) 7.8159 dB 7.0566 dB iPhone Xs Max, babble noise at 80db(A) 8.0167 dB 8.2357 dB Samsung Galaxy S7, white noise at 70db(A) 3.246 dB N/A Samsung Galaxy S7, white noise at 80db(A) 5.902 dB N/A Samsung Galaxy Note 9, white noise at 70db(A) 2.448 dB N/A Samsung Galaxy Note 9, white noise at 80db(A) 2.441 dB N/A Google Pixel, white noise at 70db(A) 1.319 dB N/A Google Pixel, white noise at 80db(A) 0.387 dB N/A It was expected that the SNRs would be noticeably higher when the filter setting was turned on due to the filter reducing noise and thus increasing the ratio of signal to noise, but as with the spectrogram and FFT spectrums the expected results were not th e case. There was a

PAGE 31

22 minor difference between the SNRs of some of the filters turned on and off but the change was not consistent: some SNRs were higher when the filter was on and others were lower when the filter was on. For example, the SNR increased when the noise reduction filter was turned off on the iPhone Xs Max during the babble noise test at 80db(A) but it decreased from filter on to filter off during the babble noise test at 70db(A).

PAGE 32

23 CHAPTER V CONCLUSION Based on the analysis of the test results , a discernible difference between the noise reduction filter turned on and off could not be found in those phone models which allow the user to toggle the noise reduction setting. Furthermore, the fact that most major phone manufacturers today such as Sam sung and Google do not allow the user to toggle the noise reduction setting on and off makes documentation of the filter’s effects on the call signal very difficult. This method might be useful in a select few cases but overall the study of noise cancellat ion filters does not seem like a very practical way of identifying the make and model of a cell phone based on a recorded call. The very small difference between the filter turned off and on is not always consistent and certainly not enough to confidently identify a particular cell phone.

PAGE 33

24 CHAPTER VI FURTHER RESEARCH While noise reduction filters are used in most modern cell phones, the study of them in a forensic setting may not be the most practical way of identifying a make and model of cell phone. The fact that most phones do not give the user the option to turn this setting off is the key sticking point in this research and renders comparison nearly impossible for those models of cell phone. Out of the phone models studied, only the Apple iPhone model s actually allowed the user to turn noise reduction off and even with that setting turned off it was apparent that some level of noise reduction was still present. Cell phones are very important area of research in forensics as their use becomes more ubiquitous across the world but perhaps noise reduction filters should not be the forefront of that research.

PAGE 34

25 REFERENCES [1] Thorn, Thomas. “Background Noise Reduction: One of Your Smartphone's Greatest Tools.” TechRadar , TechRadar, 28 Feb. 2014, www.techradar.com/news/phone and communications/mobile phones/background noise reduction one of your smartphone s greatest tools 1229667 . [2] Williams, Martyn. “Apple Sued Over Noise Reduction Technology.” CIO , IDG News Service, 6 July 2012, www.c io.com/article/2394362/apple sued over noise reductiontechnology.html . [3] Nelson, Anthony. “PROPOSED METHOD FOR RECORDING AND ANALYZING CELL PHONE ADAPTIVE NOISE REDUCTION FILTERS.” University of Colorado, Denver , 2018. [4] Monteith, David. “Ambient N oise Cancellation Comes to Mobile Phone.” Wolfsonmicro.com , Aug. 2010, d3uzseaevmutz1.cloudfront.net/pubs/whitePaper/WP_Ambient _Noise_Cancellation_Comes_ to_Mobile_Phone.pdf. [5] Castro, Joseph. “What Is White Noise?” LiveScience, Purch, 29 July 2013, www.livescience.com/38387what is white noise.html . [6] Hall, Joseph L., and James L. Flanagan. “Intelligibility and Listener Preference of Telephone Speech in the Presence of Babble Noise.” The Journal of the Acoustical Society of America , vol. 127, no. 1, 5 Jan. 2010, pp. 280–285., doi:10.1121/1.3263603. [7] “IPhone XR Technical Specs.” Apple , 2018, www.apple.com/lae/iphone xr/specs . [8] “The IPhone Xs /Xs Max Service Technical Guide for Repairing/Reassembling.” EBay , 2019, www.ebay.com/itm/The iPhone Xs Xs Max ServiceManual Guide to Repairing Reassembling /132809360900 . [9] Chew, Tung Shen. “Position of MEMS Microphones on an IPhone 7.” Vesper , 2017, vespermems.com/wp content/uploads/2017/10/Vesper Microphone Arrays whitepaper 1.pdf. [10] “Galaxy S7 Layout and Galaxy S7 Edge Layout.” Galaxy S7 Guides , 2016, gadgetguideonline.com/s7/galaxy s7 online manual/galaxy s7 layout and galaxy s7 edgelayout/. [11] Groenheijde, Michel. “Samsung Galaxy Note 9 Handleiding Nu Beschikbaar.” Galaxy Club D Onafhankelijke Samsung Experts , 13 Nov. 2018, www.galaxyclub.nl/nieuws/samsung galaxy note 9handleiding/ .

PAGE 35

26 [12] “Pixel Phone Hardware Diagram Pixel Phone Help.” Google , Google, 2016, support.google.com/pixelphone/answer/7157629?hl=en. [13] “Sampling Frequency and Bit Resoluti on for Speech Signal Processing.” Sampling Frequency and Bit Resolution for Speech Signal Processing (Theory) : Speech Signal Processing Laboratory : Biotechnology and Biomedical Engineering : Amrita Vishwa Vidyapeetham Virtual Lab, 2011, vlab.amrita.edu/?sub=3&brch=164&sim=474&cnt=1. [14] Heckbert, Paul. Fourier Transforms and the Fast Fourier Transform (FFT) Algorithm. Jan. 1995, www.cs.cmu.edu/afs/andrew/scs/cs/15 463/2001/pub/www/notes/fourier/fourier.pdf .