데이터구조 : Array & List (음성신호처리)

소개글

음성 신호처리를 하면서 데이터 구조에 대한 개념을 알 수 있도록 한 과제에 대한 보고서이다. Array와 List에 관련된 데이터 구조를 자세히 알 수 있도록 설명이 되어 있으며 또한 소스코드도 첨부되어 있다. Array와 List를 코딩해야 하는 사람들에게 큰 도움이 될 것이다. Yonsei 대학교 데이터 구조를 수강하면서 만들어진 보고서 이다.

목차

1. Definition of Problem.
2. Consideration for this Project.
3. Consideration for ADT.
1. Array
2. Linked list
◑ Single side linked list
◑ Double side linked list
◑ Single side circularly linked list
◑ Double side circularly linked list
4. The step of project.
5. Timing analysis
6. Anything for this project.
7. Reference.

본문내용

1. Definition of Problem.

이번 프로젝트는 수업시간에 잠시 언급하셨던 신호 처리에 대한 프로젝트로 Array와 Linked list 라는 ADT에 대하여 생각해보고 구현해 볼 수 있었다. 신호는 16bit sampled 16KHz의 binary `short` type의 데이터로 주어졌다. 이 신호를 FIR filter 에 통과 시켜 그 결과를 확인하는 것이 이 프로젝트의 기본적인 목표이다.

2. Consideration for this Project.

그림 . GoldWave 프로그램으로 확인한 16bit/sample 16KHz의 입력 신호

위에서 잠시 언급한 입력신호의 파형은 위와 같다. ‘대단히 피곤해 있는 것 같습니다. 과자랑 과일이랑 배불리 먹었습니다.’ 라는 음성 신호임을 간단히 알 수 있었다. 이 음성신호는 8초의 길이를 갖고 있었는데 이는 16bit/sample, 16KHz의 binary `short` type signal 이기 때문에 를 가지게 된다. 이는 ‘Short’ Type 신호이기 때문에 128,000 개의 `Short` Type 변수에 저장된다.
이러한 신호를 다음과 같은 FIR filter에 통과 시킨다.
그림 . FIR filter coefficient

간단히 보아도 Sinc function의 형태를 갖는 것을 알 수 있다. 이는 주파수 상에서 아래 그림과 같은 특성을 지니게 된다. 시켰을 때의 결과 값을 얻어내는 것이 이번 프로젝트의 주요한 내용이다. 어떤 System에서 입력 신호가 주어지면 그 System의 Impulse response와 입력신호를 Convolution 한 결과가 Output이 된다.
Convolution

위의 수식과 같이 Convolution은 주파수 축에서 보면 단순한 곱하기가 된다. 그래서 다음과 같이 h[n]을 DFT를 통해 주파수에서 분석을 해보았다.
그림 . FIR filter in frequency axi

참고 자료

1. Data structures and algorithm analysis in c, M.A. Weiss
2. Print material, 강홍구
3. Digital signal processing, Mitra, McGraw Hill
4. Digital signal processing : principles, algorithms, and applications,
john G. Proakis and Ditiris, Prentice Hall
5. Web site
http://en.wikipedia.org/wiki/Linked_list
http://www.nist.gov/dads/HTML/linkedList.html
http://lcm.csa.iisc.ernet.in/dsa/node25.html
http://academics.tjhsst.edu/compsci/CS2C/U7/circlink.html
http://occs.cs.oberlin.edu/classes/fall2004spring2005/Old%20cs160/lab03.html
http://www.cs.fiu.edu/%7Eweiss/dsaa_c2e/files.html

압축파일 내 파일목록

Project2.c
h_n.txt
Project#2 - 신호 처리.hwp
linked_list.zip