Transcript Masters Presentation at Griffith University

Masters Presentation at
Griffith University
Master of Computer and Information Engineering
Magnus Nilsson
2000 - 2001
Masters Presentation
• FFT, Realization and Implementation in FPGA
• Speaker Verification in JAVA
• Demonstration of FFT and JAVA application
FFT, Realization and
Implementation in FPGA
•
•
•
•
•
•
•
•
•
•
•
Technical Function
History of Fourier Transform
Discrete Fourier Transform
Fast Fourier Transform
The Radix-2 Algorithm
The Radix-4 Algorithm
FPGA
Complex FFT
Bit Length and Implementation
Results
Conclusion
Technical Function
• Background
• Ericsson Microwave System
• XILINX FPGA 1024-point FFT
• Task
• Study, Implement and evaluate FFT in FPGA
• Technical Function
• Collect data, execute a FFT and output the data.
• The implementation shall be optimized on execution
time, area and cost.
History of Fourier Transform
•
•
•
•
Jean-Baptiste-Joseph Fourier
Problem of flow of heat in solid bodies
The analytical theory of heat, 1815
Universal problem solving technique
Radar
Speaker Verification
Medical Science
Discrete Fourier Transform
 N2 complex multiplications
 (N)(N-1) complex additions
 ~ 2N2 additions and multiplications
Fast Fourier Transform
• Early 1960’s
• John W. Tukey and James W Cooley
• An algorithm for the machine calculation of
complex Fourier series
• Runge and König
• Radix - 2 algorithm
The Radix-2 Algorithm
~ 2N2 additions and multiplications for DFT, Vs. N2/2 for FFT
The Radix-4 Algorithm
•
•
•
•
•
Base 4 i.e. N = 4x
More complex but less computation power utilized
The Radix-4 algorithm consists of v steps (log(N)/log(4))
Each step involves N/4 number of butterflies
3*v*N/4 = (3N/8)log2N number of complex
multiplications
• (3N/2)log2N complex additions
• Radix-2 Vs. Radix-4:
• 25% reduction of complex multiplications
• Complex additions will increase by 50%
Radix-4 Dragonfly
FPGA
• Field Programmable Gate Array
• For fast time to market hardware
implementation
• Xilinx Virtex-E
• PCB with a Xilinx Virtex-E 1000
Complex FFT
• Specification
• Minimum: 16 complex samples
• Maximum: 1024 complex samples
• Typical: 16 or 64
• Number of bits for the input signal
• Minimum: 10 bits
• Maximum: 16 bits
• Typical: 12
Construction configuration
Bit Length
•
•
•
•
•
•
Implementing in hardware
Multiplications
Nbits x Nbits = 2 Nbits
Minimize the phase and amplitude error
Realizable
Different types of bit lengths
Implementation
• Ease, Eale, Modelsim and Symplify
• Virtex-E 2000 @ Fc = 55 MHz,
Computation phase = 640 ns my FFT
• Xilinx Virtex LogiCore block @ 110 MHz,
Computation phase = 1.92 ms
• LogiCore = Serial
• My FFT = Parallel
Result
• Tested using a Logical Analyser, Hewlett
Pacard HP16555D (2.0 M Samples, 110/500
MHz) and a Pattern Generator
Result
Conclusion
• As the Radix-4 FFT algorithm utilizes less
complex multipliers than the Radix-2 FFT
algorithm, the Radix-4 algorithm is preferable for
hardware implementation.
• A parallel programming approach seems to be the
model when a real time system with high sampling
rate is desired.
• To reach an acceptable level of phase error, it is
desirable to use 16 bits precision on the input
signal and the phase factor
Speaker Verification in JAVA
•
•
•
•
•
•
•
Technical Function
JAVA
Speaker Verification and Speaker Recognition
VQ Speaker Verification
Hardware Parallel Port Extension and access
Results
Conclusion
Technical Function
• Background
• It would be interesting to develop a Speaker Verification
system/software in JAVA, since the JAVA language is
said to be platform independent and would be
interesting as a research language.
• Task
• To study, implement and evaluate a VQ (Vector
Quantization) Speaker Verification system in JAVA,
using MFCC’s (Mel Frequency Cepstral Coefficients).
• Technical Function
• A graphical software implementation which shall record
speech from a person through a microphone, verify the
person as true speaker or false speaker.
JAVA
• 1991 @ Sun Microsystems by James Gosling &
•
•
•
•
•
•
•
•
Co
Address the problem of building software for
network consumer devices
Survive transport across networks
Operate on any client
Safe to run
Capability to work on a wide range of platforms
and CPU's
Virtual Machine
Applet and Application
Platform portability
Speaker Verification and Speaker
Recognition
Speaker Verification and Speaker
Recognition
•
•
•
•
•
•
•
•
•
Accessing confidential information areas
Access to remote computers
Voice dialing
Banking by telephone
Telephone shopping
Database access services
Information services
Voice mail
PIN code for your ATM
VQ Speaker Verification
Speech Feature Extraction
Mel Frequency Cepstral
Coefficients
Mel Frequency Wrapping
Cepstral Coefficients
• Power of the triangular filter = summarized
• Log calculated
• Convert them to time domain using the Discrete Cosine
Transform (DCT)
• Result is called the mel frequency cepstral coefficients
(MFCC).
Feature Matching
•
•
•
•
Dynamic Time Warping (DTW)
Hidden Markov Modeling (HMM)
Gaussian Mixture Model (GMM)
Vector Quantization (VQ)
• High Accuracy
• Interesting to implement
LBG algorithm
MFCC’s and Codebook
Verification
• Threshold
• Cohort Speakers
• Ratio
Graphical Implementation of
application in JAVA
Results
Conclusion
• Since Java is said to be platform independent, some
experiments has been conducted that has showed this is not
always the case. As soon as you would like to access the
hardware through Java you will face problems that will
make your software to become platform dependent.
• It is interesting to note that all the algorithm developed for
the speaker verification system is platform independent,
except for those parts accessing the sound card of the users
computer, and can easily be executed under both Microsoft
Windows and Linux.
• Testing, simulation and verification of the speaker
verification program show a total error rate of four percent.