바라보지는 않지만 푸른 하늘을 좋아합니다.

닫힌 블로그 입니다.

2010-06-26T17:10:00.001+09:00

아무 것도 없어용!

영화 <파라노말 액티비티> (2010)

2010-01-19T18:03:00.000+09:00

우리는 보이지 않는 것에 더 두려움을 느낀다

과거 <주온> (2003) 시리즈는 보이는 두려움의 새로운 장을 연 영화라고 할 수 있었다. <주온> 시리즈의 첫 작품은 특유의 하얀 피부 분장을 통해서 나름 영상적인 섬뜩함을 주는데 성공했다. 하지만 계속되는 시리즈에 익숙해져 버리자 유령의 모습은 더 이상 그 존재의 두려움을 어필하기에는 우스꽝스러워 보이기 시작했고 때로는 애처롭기까지 했다. 작년에 개봉한 <주온 - 원혼의 부활> (2009)은 기존 <주온> (2003)의 구성을 따라서 예전의 영광을 부활시키고자 했지만 이제는 별다른 감흥이 없는 그냥 일본 공포 영화에 지나지 않게 되어 버렸다.

반면 같은 시기에 개봉한 영화 <다크니스> (2003)는 어떤 존재를 내세우기 보다는 어둠으로 그를 대신했다. 우리는 발자국 소리와 아이들 목소리, 빛과 그림자, 언뜻 스쳐 지나가는 형체들로 그들의 존재를 알 수 있을 뿐이다. 그래서 우리는 오히려 존재가 무엇인지 파악하기 어렵고 어디서 나타날지 예상하기 힘들다. 또한 어둠과 더불어 영화의 적절한 음향 효과는 존재에 대한 상상을 부추기기에 충분했다.

가짜 다큐멘터리 영화, 사실성?

<파라노말 액티비티>는 다큐멘터리의 형식을 지닌 영화여서 보이지 않는 존재와 주인공 커플이 벌이는 사투를 마치 실제 영상을 편집한 것처럼 보여준다. 때문에 여타 영화와는 달리 배경 음악도 없고 오직 주인공 커플의 일상과 사건들에서 발생되는 소리들 만이 주를 이룬다. 영상은 종종 초점이 맞지 않고 흐리기 까지 하고 카메라 시점의 이동도 미숙해서 마치 일반인이 촬영한 듯한 느낌을 준다. 때문에 일반 적인 영화를 볼 때와는 달리 몰입하기 힘든 거북함은 있지만 그래도 정말 아마추어 비디오 같은 사실감은 느낄 수 있었다.

어쩌면 이런 점 때문에도 관객은 보이지 않는 존재가 내는 소리를 더욱 사실적으로 받아들일 수 있는지도 모르겠다. 단순히 발 구르는 소리, 문 닫는 소리, 주인공 들의 비명 소리뿐 이지만 그것 만으로도 존재가 확실하게 관객에게 각인되는 것이다. 여기에 관객의 상상이 덧붙여 진다면 존재는 더욱 무서운 모습으로 공포를 자극할 것이다.

마지막 10분의 공포

영화 앞의 대부분 시간은 주인공 커플의 일상 및 대화로 이루어져 있어 다소 지루한 감이 없지 않다. 하지만 이는 현장감을 주기 위해 의도적으로 구성된 것이라고 생각한다. 이후에도 자잘한 사건들이 일어나지만 역시 큰 놀라움은 주지 않는다. 하지만 일련의 사건들이 깔아놓은 분위기는 후반의 전개로 자연스럽게 이어져 마지막 사건들의 두려움을 극대화 시키는데 큰 역할을 한다. 이 영화는 마지막을 보기 위해서 있다고 해도 과언이 아니라고 생각한다.

...

1. 잘 봤다고 생각하기는 했지만 아무래도 몰입이 조금 힘든 점은 있었다.

2. 스티븐 스필버그가 작업했다고 들었는데 알고봤더니 감독은 원래 오렌 펠리이고 이미 2007년에 미국에서 개봉, 이후 스필버그씨가 판권을 사서 결말을 바꾼것이라고 한다. 인터넷을 찾아서 다른 결말 내용도 보기는 했지만 개인적으로는 이 결말이 가장 마음에 든다.

3. 아무래도 사운드가 대부분의 비중을 차지하는 만큼, 영화관에서 보지 않는다면 시시할 수도 있겠다는 생각이 든다.

영화 <셜록 홈즈> (2009)

2009-12-27T18:02:00.000+09:00

셜록 홈즈 포스터. 출처: http://www.warnerbros.com/

처음엔 셜록 홈즈가 영화로 만들어 진다고 했을 때는 고전적인 소설 내용이 영화화 되지 않을까 하고 단순히 생각했다. 하지만 소설에서 보통 냉철하게 묘사되었던 모습은 온데간데 없고 열혈에 머리보다는 몸을 사용(?)하는 홈즈를 볼 수 있었다. 물론 홈즈의 추리력은 여전한 듯 하지만 다소 과장된 액션 씬에 묻혀버린 것 같다.

그래도 활달하고 유쾌한(때로는 방탕한) 홈즈의 모습이 정말로 어색한 것은 아니다. 홈즈가 냉철한 추리력의 소유자기도 하지만 한 편으로는 열정적인 실험 정신 및 탐구심의 소유자이기도 하기 때문이다. 또한 소설에서도 묘사된 홈즈는 그렇게 완벽한 사람은 아니어서 때로는 마약 같은 방탕한 생활에도 빠져있는 일도 종종 있다. 영화는 이런 점을 상당히 잘 살린 것 같다. 오히려 '완벽하지 않은 홈즈'는 친근하게 다가오는 듯 하다.

전체적 스토리는 액션을 잘 살리는데 맞추어져 있어서 사실 내용면에서는 매우 만족할만한 정도는 아니다. 이 영화 역시 헐리우드 블록버스터 액션 영화라는 전형적인 틀에서 벗어나지는 못할 것 같다. 하지만 <2012>와 마찬가지로 풍성한 볼거리가 있다는 점에서 즐겁게 볼 수 있는 영화라고 생각한다.

...

영화 후반의 모리어티 교수에 대한 언급은 속편 제작을 의식한 것이라고 생각되기도 하지만 한편으로는 '셜록 홈즈'라는 장르에 맞추기 위한 요소가 아니었을까 하는 생각도 해본다.

[글] 한 사람

2009-10-28T01:43:00.000+09:00

그저 바라보는 바다가 넓어서

그저 바라보는 하늘이 한 없이 푸르러서,

그저 바라보는 달이 너무나도 밝게 빛나서

나는 떠올려 버렸다, 그리운 모습을.

그저 조용히 나무에 기대어 바라보는 해안선은

달처럼 무언가 떠오를 듯 하면서도 잠기는 수심 같아

바람은 불어와 긴 머릿결 같은 생각을 쓸어 넘기고

아무도 곁에 없다는 걸 시린 목소리로 속삭여.

그저 혼자 있을 때는 몰랐었지.

밝은 해가 내리쬐는 해변가를 홀로 걸어도

그저 넓은 바다에 마음을 빼앗겼지

그저 푸르른 하늘에 걱정을 빼앗겼지

그저 하늘을 가로지르는 갈매기의 날개 짓에

한 없이 한 없이 바라보았지.

그저 흘러가는 자연을 느끼는 것이었다고.

그리움이라는 걸 더욱더 잘 알고 있었으면서.

속으로 수 없이 되뇌었던 이름, 어쩌면 그 자신.

새삼스레 누군가 같이 있는다는 것은

오히려 혼자 있을 때 더 잘 아는게 아닐까.

아니, 폭풍을 만나 헤어진 한 쌍의 새처럼

함께 있는 시간 뒤에 남겨진

건널 수 없는 바다와 같은 곳에 놓여진

작은 섬과 같은 공간이 아닐까.

함께하는 체온은 온기 이상으로 여기지 못하면서

떨어져서 전해온 그리움에 묻어난 환상만을 보는게 아닐까.

그저 익숙하기에

그저 의식할 수 없을 정도의 따뜻함이기에

그저 영원히 바라보고 만질 수 있다고 믿기에,

수 없이 닳아버린 그 이름.

하지만 잡고 있던 손을 놓쳐버렸을 때

한 없이 한 없이 열망하던 촉감, 그 온기.

그건

너.

[글] 가을, 낙엽

2009-10-17T22:00:00.000+09:00

세상도 이젠 다 지친걸까.
곳곳에서 나무들은 벌써
시간의 무게를 털어 버리고
이 대지와 같은 색 옷을 입고
먼 곳에서부터 불어오는 바람도
차가움은 멀다 않고 오는데
저 먼 하늘을 나는 흰 새는
아무렴, 나는 것은 적어도
이 땅에 발 붙이고 사는 나보담은
조금은 가볍지 않을까 생각해도
어쩜 낙엽은 가벼워도 떨어질까
궁금하기도 한 것 같아.
하늘은 그리도 높고 높아서
새는 저 멀고 먼 하늘은 날아가도 될텐데
낙엽아, 넌 그냥 떨어지기만 하누나.
그저 외로울 것이면
빗자루로 쓸어 모여서 그렇게
낙엽은 모여 쌓아두고
드문 드문 걷는 이 거리를
한번 걸어 보자.
걷다가 언듯 시려운 바람 불며는
낙엽아 바람따라 한번 날아보자꾸나.
울긋 불긋 단풍져가는 이 숲 위로
빙그르르 솟아올라서는
회오리 치듯 휘휘 떨어져 보자.
저들처럼 날지는 못해도 그냥
잠깐 동안의 비행을 하여보자.

이제 여기 커다란 나무 아래 앉아서
먼 하늘 저 구름너머로 언젠가 노오란 노을지며는
하늘도 이젠 다 지친 걸까.
바람도 어느새날카로운 질주를 멈추고,
긴 비행을 마치고 돌아오는
새들의 무리도 그저 정다웁고
노을 지는 이 하늘과 땅도
낙엽 지는 이 아름다움을-
언젠가부터 나는 아무래도
이 땅에 발 붙이고 사는 것이 좋았던 모양이다.
나무의 가칠한 피부를 느끼며 미소 짓는
따뜻한 누군가의 품속에 안긴 듯 그렇게 눈을 감았다.

[메모] [Java] MP3 Bit rate, duration 계산하기

2009-06-25T16:32:00.000+09:00

0. 주어진(기본 API로 얻을 수 있는) 값들
(1) File length in byte: javax.sound.sampled.AudioFileFormat.getByteLength()
(2) File length in frame: javax.sound.sampled.AudioFileFormat.getFrameLength()
(3) Sample rate: javax.sound.sampled.AudioFormat.getSampleRate()
(4) Frame rate: javax.sound.sampled.AudioFormat.getFrameRate()

1. Frame size
"javax.sound.sampled.AudioFormat.getFrameSize()"로 얻어져야 하지만 -1을 리턴합니다.
(이유는 잘 모르겠네요...)
그래서...

Frame size in byte = (File length in byte) / (File length in frame)

로 얻습니다.

2. Bit rate (bps)
http://oreilly.com/catalog/mp3/chapter/ch02.html - "Frames per Second"에 나와있는 식

"FrameSize = 144 * BitRate / (SampleRate + Padding)"

을 변형해서,

Bit rate = (Frame size in byte) * (Sample rate + Padding) / 144

로 구할 수 있습니다.

다만 144라는 값이 원래는...

Bit rate = (Frame size in byte) * 8 * (Sample rate + Padding) / 1152

여기서 나온 값이고 1152란 값은 MPEG-1의 (Sample rate) / (Frame rate) 값에 해당됩니다
(Samples per Frame).
MPEG-1이 아닐 때도 적용할 수 있도록 이 값 대신에 (Sample rate) / (Frame rate * 8)을 사용합니다.
그렇다면...

Bit rate = (Frame size in byte) * (Sample rate + Padding) / ((Sample rate) / (Frame rate)) * 8
= (Frame size in byte) * (Frame rate) * 8 (단 padding이 0이라고 가정)

로 구합니다.

3. Duration
위에서 구한 Bit rate (bps)를 이용하여

Duration in second = (File length in byte) * 8 / (Bit rate)

로 구합니다.

4. 실제 계산 예
<파일 정보(주어진 값)>
Sample rate: 44100 (Hz) / Frame rate: 38.28125 (Hz)
File size: 9526420 (byte) / # of frame: 9124 (frames)

<계산 시 기대 되는 값(MP3 정보에 나와있는 값)>
Duration: 3:58 (분:초) / Bit rate: 320 (kbps)

<Frame size 계산>
Frame size in byte = (File length in byte) / (File length in frame) = 9526420 / 9124
= 1044.1057 (bytes)

<Bit rate 계산>
Bit rate = (Frame size in byte) * (Frame rate) * 8 = 1044.1057 * 38.28125 * 8
= 319757 (bps) ≒ 320 (kbps)

<Duration 계산>
Duration = (File length in byte) * 8 / (Bit rate) = 9526420 * 8 / 319757 ≒ 238 (초) = 3:58 (분:초)

[글] 깊은 암흑, 늪지, 한숨

2009-05-30T23:35:00.000+09:00

생각할 수도 없는 고요.
깊고 깊은 어둠. 하늘에 희미한
달. 한 줌의 별빛.
연잎에서 한 방울 떨어지는 물방울.
고요 속의 파동. 조금 흔들리는 연잎.
한 방울, 한 방울, 여러 방울.

툭
툭
투둑, 툭
투둑
투두두둑
툭

깊은 늪.
바닥부터 울리는 물방울의 파동.
그리고 불어오는,
바람.

춤을 춘다.물방울이 춤을 춘다.
연잎은 옷소매인양 푸른 잎을
높이 들어 들고 내리고 휘이젓고
수 없이 흔들리는 검은 천
물방울은 바닥부터 수 없이 울려온다.
무한의 구.
모든 것이 가라앉는 늪 바닥을 때리우고
추잡한 감정은
흙처럼 일어나 뜨고 앉고 뜨고 앉고.

바람이 멎는다. 연잎의 흔들림도 멎는다.
늪. 마음 속 앙금처럼 흙은 차츰 갈앉고
새로운 퇴적물을 기다린다.

생각할 수도 없는 고요.
깊고 깊은 바닥. 늪. 영원히
퇴적될 흙. 한 줌의 숨.
구름에서 한 방울 떨어지는 물방울.
흐려오는 하늘. 조금 슬퍼오는 늪지.
한 방울, 한 방울, 여러 방울.

[노트][DSP] X+1. Multi-rate signal processing

2009-05-29T23:22:00.000+09:00

1. Decimator와 Interpolater에서 filter 위치 바꾸기
(1) Decimator
원래 decimator는
x[n] RARROW box{DARROW M} RARROW x_a [n] RARROW box{H(z)} RARROW y[n] ~ ~ ~ ... a)
이지만 필터의 위치를 앞으로 바꾸면
x[n] RARROW box{H(z^M)} RARROW x_b [n] RARROW box{DARROW M} RARROW y[n] ~ ~ ... b)
가 된다. 두 결과가 같다는 것은 다음 두 개의 식으로 증명할 수 있다.
alignl a) x_a [n] = x[n M] DRARROW X_a(e^{j omega}) = 1 over M sum from {i = 0} to {M - 1} X(e ^ {j {omega - 2 pi i} over M}) newline DRARROW Y(e^{j omega}) = X_a(e^{j omega}) H(e^{j omega}) = 1 over M sum from {i = 0} to {M - 1} X(e ^ {j {omega - 2 pi i} over M}) H(e^{j omega})
alignl b) H(z^M) = sum from {n = - infinity} to {infinity} h[n] z^{-n M}, ~ X_b(e^{j omega}) = H(e^{j omega M}) X(e^{j omega}) newline Y(e^{j omega}) = 1 over M sum from {i = 0} to {M - 1} X_b(e^{j {omega - 2 pi i} over M}) = 1 over M sum from {i = 0} to {M - 1} X(e ^ {j {omega - 2 pi i} over M}) H(e^{j omega})

-a)와 b)의 성능 비교
a)는 down sampling 후에 filter를 하므로 filter에서 계산량이 감소한다.
반면 b)는 filter 후에 down sampling하므로 filter에서 a)에 비해 많은 계산을 필요로 한다.
따라서 성능상으로는 본래의 모양인 a)가 좋다.

(2) Interpolater
decimator와 비슷하다.
원래 interpolater는
x[n] RARROW box{H(z)} RARROW x_a [n] RARROW box{UARROW L} RARROW y[n] ~ ~ ~ ... a)
이지만 필터의 위치를 뒤로 바꾸면
x[n] RARROW box{UARROW L} RARROW x_b [n] RARROW box{H(z^L)} RARROW y[n] ~ ~ ... b)
가 된다. 두 결과가 같다는 것은 다음 식으로 증명할 수 있다.
Y(e^{j omega}) = X_a(e^{j omega L}) = H(e^{j omega L}) X(e^{j omega L}) = H(e^{j omega L}) X_b(e^{j omega})

-a)와 b)의 성능 비교
a)는 filter후에 up sampling을 하지만,
b)는 up sampling후에 filter를 하므로 늘어난 sample을 filtering해야 한다. 별로 좋지 않다.
따라서 성능상으로는 본래의 모양인 a)가 좋다.

-사실은...
a)에서 b)로 바꾸는 것이 목적이 아니다. a)를 poly-phase decomposition 하면 b)와 같은 형태가 생기는데 이것을 a)로 바꾸는 것이 목적이다.

2. Poly-phase decomposition

poly-phase decomposition은 h[n]을 M개의 sequence의 합으로 나누는 것을 말한다.
그러기 위해서 우선 e_k[n], h_k[n]을 다음과 같이 정의 한다.
alignl h_k [n] = lbraket{stack{{h[n + k] ~ n = x M, integer x}{0 ~ ~ ~ ~ ~ otherwise}}} newline e_k[n] = h_k[n M]
h_k[n]은 sequence h[n]에서 n = k부터 M간격으로 sample을 뽑아낸 것과 같다. 따라서
alignl h[n] = sum from {k = 0} to {M - 1} h_k[n - k] newline DRARROW H(z) = sum from {k = 0} to {M - 1} H_z(z) z^{-k} = sum from {k = 0} to {M - 1} E_k(z^M) z^{-k}
결과적으로 poly-phase decomposition은 하나의 시스템(H(z))을 여러 개의 작은 시스템(H_k(z))으로 나누어 병렬 처리할 수 있도록 바꾸어 주는 것이다.

3. Poly-phase decimation filter

filter + decimator의 조합을 아래와 같이 decomposition할 수 있다.

-decimator의 복잡도
만일 H(z)가 N개의 point를 가지는 FIR(Finite Impulse Response) Filter라면 1개의 output을 내기 위해서
(단, 곱셈(mult.)은 덧셈(add.)과 같은 정도의 복잡도를 가지며, 실수 곱셈이라고 가정.)

바꾸기 전) (N mult. + N - 1 add.) cdot M "times" = (2N - 1) cdot M
바꾼 후) (N over M mult. + N over M - 1 add.) cdot M parallel units = (2N - M)

를 하게 된다. 바꾼 후에 복잡도가 약 1/M정도로 감소하는 것을 알 수 있다.

4. Poly-phase interpolate filter

interpolater + filter의 조합을 아래와 같이 decomposition할 수 있다.

-interpolater의 복잡도
만일 H(z)가 N개의 point를 가지는 FIR(Finite Impulse Response) Filter라면 L개의 output을 내기 위해서
(단, 곱셈(mult.)은 덧셈(add.)과 같은 정도의 복잡도를 가지며, 실수 곱셈이라고 가정.)

바꾸기 전) (N mult. + N-1 add.) cdot L "times " = (2N - 1) cdot L
바꾼 후) (N over L mult. + N over L - 1 add.) cdot L parallel units = (2N - L)

를 하게 된다. 바꾼 후에 복잡도가 약 1/L정도로 감소하는 것을 알 수 있다.

[노트][DSP] X+0. Changing sampling rates

2009-05-28T14:08:00.000+09:00

1. Down sampling (Compressor)

down sampling은 sample sequence에서 일정 간격(M)으로 sample을 골라내는 것이다. 이것은 결과적으로 샘플 주기를 크게 하고 sample의 수를 줄인다.

alignl x[n] RARROW box {DARROW M} RARROW x_d [n] = x [n M]

새 sample 주기: T' = M T

X(e^{j omega}) = sum from {n = - infinity} to {infinity} {x [n] e ^ {-j omega n}} = 1 over T sum from {k = - infinity} to {infinity} {X_c (j (omega over T - {2 pi k} over T))}
alignl down sampled ~ X_d (e^{j omega}) = sum from {n = - infinity} to {infinity} {x_d [n] e ^ {-j omega n}} = sum from {n = - infinity} to {infinity} {x [n M] e ^ {-j omega n}} newline = 1 over MT sum from {k = - infinity} to {infinity} {X_c (j (omega over {M T} - {2 pi k} over {M T}))} newline = 1 over MT sum from {i = 0} to {M - 1} sum from {r = - infinity} to {infinity} {X_c (j (omega over {M T} - {2 pi (i + r M)} over {M T}))} (k = i + r M) newline = 1 over MT sum from {i = 0} to {M - 1} sum from {r = - infinity} to {infinity} {X_c (j ({omega - 2 pi i} over {M T} - {2 pi r} over T))} newline = 1 over MT sum from {i = 0} to {M - 1} sum from {r = - infinity} to {infinity} {X_c (j ({omega over M - {2 pi i} over M} over T - {2 pi r} over T))} newline = 1 over M sum from {i = 0} to {M - 1} {X (e ^ {j {omega - 2 pi i} over M})}

결국 down sampling은 frequency domain에서 신호를 {2 pi} over M간격으로 M개로 분산시키는 일을 한다.

따라서 크기도 1 over M배가 된다.

- aliasing of down sampling:
down sample 된 frequency domain을 살펴보면 DTFT에서의 pi가 pi over M에 해당된다.
즉 sampling할 때 omega_c T < pi 였던 것처럼 최종적으로 down sampling을 했을 때 aliasing이 없으려면
omega_c T < pi over M
이어야 된다.

2. Low Pass Filter + Down sampling = Decimator

위에서 down sampling을 했지만 aliasing을 제거한 것은 아니다. 따라서 aliasing이 일어나지 않도록 하는 조건을 만족하도록 down sampling전에 low pass filter를 통과시켜야한다.

x[n] RARROW box {stack {{LPF} {pi over M}}} RARROW box {DARROW M} RARROW tilde {x_d} [n] ` = ` tilde {x} [n M]

low pass filter의 bandwidth는 abs omega < pi over M이다.

3. Up sampling (Expander)

up sampling은 본래의 sample 값 사이에 0을 여러 개 끼워 넣어서 sample수를 늘리는 것이다. 이것은 결과적으로 sample 주기를 작게 한다. 이렇게 해도 (단지 0을 끼워넣은 것이기 때문에) 실질적인 정보량의 변화는 없지만 신호의 크기가 L배가 되기 때문에 frequency resolution(신호의 선명도)가 좋아진다.

새 sample 주기: T' = 1 over L T

alignl x [n] RARROW box {UARROW L} RARROW x_e [n] = lbraket {stack {{x [n over L] ~ n = mL, m=0, plusminus 1, plusminus 2, ...} {0 ~ ~ ~ ~ otherwise}}} = sum from {k = - infinity} to {infinity} x [k] delta [n - k cdot L] newline X_e (e^{j omega}) = sum from {n = - infinity} to {infinity} x_e [n] e^{- j omega n} = sum from {n = - infinity} to {infinity} (sum from {k = - infinity} to {infinity} x [k] delta [n - k cdot L]) e^{- j omega n} newline = sum from {k = - infinity} to {infinity} x [k] (sum from {n = - infinity} to {infinity} delta [n - k cdot L] e^{- j omega n}) newline = sum from {k = - infinity} to {infinity} x [k] e^{- j (omega L) k} = ` X(e^{j omega L})

결국 up sampling은 frequency domain상에서의 신호의 폭을 1 over L배 scale한다. 단, 크기(amplitude)는 변하지 않는다.

-aliasing of up sampling:

up sampling시에는 aliasing이 없다. frequency domain에서 보면 신호의 폭(bandwidth)이 1 over L배로 축소 되기 때문에 서로 겹칠 일이 없기 때문이다.

4. Up sampling + Low Pass Filter = Interpolater

up sampling에서는 aliasing이 없다. 하지만 신호의 폭이 1 over L로 scale되어버렸기 때문에 - pi < omega le pi 범위에 1 over L로 scale된 신호가 L개 존재한다. 이것을 하나로 모아줄 필요가 있다.

결과적으로, 흩어져있는 L개의 신호를 모아주는 것은 가운데 있는 하나의 신호만 low pass filter로 건져내서 L배 하는 것과 동일하다. 이 때, 신호의 폭은 omega T over L (le pi over L)이므로, low pass filter의 bandwidth는 pi over L이 된다. 그리고 L배를 해야하기 때문에 gain을 L로 둔다.

x[n] RARROW box{UARROW L} RARROW box{stack{{LPF}{gain = L}{pi over L}}} RARROW x_i [n]

(ex) Linear Interpolater

실제로 low pass filter를 구현하는 것은 어렵다. low pass filter는 time domain에서는 sinc function({sin ({pi n} / L)} over {{pi n} / L})과 동일하기 때문이다. 따라서 sinc function 대신에 근사적인 필터 함수를 만들어 사용하기도 한다. 그 예중 가장 단순한 것이 linear interpolater이다. time domain에서의 모양은 아래와 같다.

h_e [n] = lbraket {stack {{1 - {abs n} over L ~ abs n le L} {0 ~ ~ otherwise}}}

5. Changing sampling rate

T' = M over L T

단, 순서는 interpolator 후에 decimator를 해야한다. 왜냐하면...

(1) 이렇게 하면 아래처럼 low pass filter를 하나로 합칠 수 있다.

(2) down sampling시에 데이터의 손실이 일어나기 때문이다.

(decimator 후에 interpolator를 하면 decimator에서 일어난 데이터 손실(aliasing)을 interpolator에서 확대하는 꼴이 되어 버린다.)

x[n] RARROW box{UARROW L} RARROW box{stack{{LPF}{gain = L}{pi over L}}} RARROW box{stack{{LPF}{gain = 1}{pi over M}}} RARROW box{DARROW M} RARROW y[n]
에서 low pass filter를 합치면

x[n] RARROW box{UARROW L} RARROW box{stack{{LPF}{gain = L}{min (pi over L , pi over M)}}} RARROW box{DARROW M} RARROW y[n]

와 같이 할 수 있다.

-sampling rate를 바꿀 필요가 있을까?

보통 DSP에서는 sampling한 것을 여러가지 filter를 거쳐 결과를 내놓는다. 이 때 sample 데이터의 손실을 막기 위해서는 filter를 매우 정교하게 디자인 할 필요가 있다. 하지만 정교한 filter는 디자인과 구현도 힘들고 가격도 비싸진다. 하지만 sample 데이터를 up sampling한 뒤 처리하게 되면 filter가 엉성해서 발생하는 손실이 그렇게 크지 않은데다 나중에 down sampling할 때 그 영향이 축소 되므로 filter를 정교하게 디자인 할 필요가 없어진다. 따라서 sampling rate를 바꾸는 것이 필요하다.

[담아 두기] 다르게 사는 방법 - J.크리슈나무르티

2009-05-27T17:22:00.000+09:00

이 모든 논의에서 우리가 애쓰는 것은 우리가 마음의 근본적인 변화를 경험하는지 알아보는 것입니다.
있는 그대로 받아들이는 것이 아니라 그것을 이해하고, 그 안에 들어가, 살펴보는 것입니다.

당신이 발견한 것에 당신의 가슴과 마음과 당신이 찾아야 할 모든 것을 주는 것입니다.

다르게 사는 방법입니다.

그러나 그것은 다른사람이 아닌 당신에게 달려있습니다.

여기에는 선생도, 학생도, 지도자도, 정신적 스승도, 주인도, 구세주도 없기 때문입니다.
당신 자신이 선생이고, 학생이고, 주인이고, 정신적 스승이고, 지도자 입니다.

당신이 모든 것입니다.

그래서 이해하는 것은 현재를 바꾸는 것입니다.

- J. 크리슈나무르티

(출처: 시대정신 2 자막)

[글] 회상 3

2009-05-19T01:03:00.000+09:00

왜 지나간 일들이 슬퍼야 했는지

왜 지나간 시간이 그리워져야 했는지.

하늘은 모두 세피아 빛.

모든 것이 푸르러지는 늦은 봄 하늘에도

그 가슴을 긁히는 사포 같은 갈색 빛이 있었다.

그건 저녁 노을 질 때의 한 순간.

타오르는 붉음과 그 뒤로 이어지는 심연의 짙은 푸름의 만남이었다.

단지 따뜻함만을 간직하기에도

늦은 봄의 밤은 너무 추웠다.

세차게 불어오는 바람 보다도

모든 것이 검게 멀어져 가는 하늘에

별빛 한 점이라도 없는 것이 추웠다.

오직 기억뿐인데.

무엇이 그렇게 나를 포근히 안았다가

잠시 고개를 돌리면 흔적도 없이 사라지는지.

오직 꿈 뿐인데.

밀쳐낸 이불의 촉감보다도 생생히 만져지는 것

그것은 왜

조금 몸을 뒤척이면 잡을 수도 없이 흩어지는지.

그것은 만져질 듯 느낄 수 없는 것.

어딘가 허물어져 가는 서고에

수 많은 먼지들이 쌓인 채 잊혀져 가는

슬픈 동화책 속의 옛 이야기.

[글] 회상 2

2009-05-08T21:52:00.000+09:00

1

푸른 바닷바람은
누가 그를 그리도 부르기에 불어 오나요.
이 작고 작은 백사장에.
나만이 아는 기나긴 수평선에.
살포시 쓰다듬듯 떠가는 뭉게구름들이
숱한 바람에도 쓰러지지 않는 깊은 주름진 절벽을 감싸듯이
빛바랜 조개 껍질처럼
그 안에 숨겨진 오랜 흰 빛의 진주처럼
그리고 그 안에 숨겨진
연한 푸름의 회색은 그대와 손을 맞잡고
걸어오던 비탈길의 푸름과도 닮아 있었죠.

2

붉은 바다 노을은
누가 그를 괴롭혔기에
가슴이 아리도록 붉게 젖어가는 건가요.
비가 오는 밤에 하늘은 이상할 정도로 맑고
별이 눈물을 흘리듯 비가 오는 밤에
산에 쓸쓸한 나무 오두막 램프의 따뜻함은
좁은 침대를 비추고 함께 할 수 없는 시간
그러나 조용히 곁에 머무르는 시간
바위처럼 묵묵히 대답 없이도
그대의 얼굴은 미소지었고
조용히 바라보는 눈 앞에 다소곳이 고개를 끄덕이던 모습은
어느 따뜻한 봄 날의 햇살이 비추는 정원에
조용히 흘러들어오는 산들 바람처럼
살며시 불어와 끝내 내 마음에 깃든 깃털을 날려 보내지만
아쉽게도 떠올릴 수 없는 미소
그것은 그토록 목마음에 외쳤던
붉게 물든 백사장에 잔잔해져버린 파도처럼
내 마음을 적시다가도 금방 사라져 버리는 숱한 거품들
흔적밖에 찾을 수 없는 발자취는
노을에 젖어 가슴에 지울수도 없이 찍힌
낙인이 되어 지금도 쓰리도록 아파오고 있지요.

3

밤 하늘의 북극성은
누가 그를 멀리하기에
고독한 흰 빛을 발하고 있는 건가요.
잔잔한 밤의 바다와 좁은 백사장에는
지금도 고귀한 달의 빛이 내리고 있는데
내가 선 넓은 백사장 어디에도 그 빛은 없고
짙은 회색 빛 구름만이 밤 하늘을 채우고
오직 곱디고운 흰 모래를 한 움큼 집어
세차게 불어오는 바닷 바람에 흘려 보내고
그대와 디뎠던 좁은 해안선의
고운 백사장의 감촉이 그대와 함께한 것처럼
내 마음을 포근히 감싸오고 그저
느낄 수 밖에 없는 슬픔 속에 빛 바랜 미소의 기쁨
따뜻해지는 가슴에 좋은 시선만을 담아 밤 하늘을 올려다 보면
어느새 하늘은 구름 한 점 없이 맑은 거울처럼
그 위에 뜬 고귀한 달의 자태에 나란히 선
북극성의 희게 느껴졌던 바랜 빛에서
그대의 웃음소리를 들을 수 있었죠.

그대의 작은 속삭임 같은 자장가에
진심어린 미소와 함께 잠든 나의 얼굴을 보아요.

[메모][C] 이더넷 패킷 전송하기

2009-04-29T17:39:00.000+09:00

0. PF_PACKET(or AF_PACKET) 소켓으로 패킷을 전송할 때는 bind가 필요없습니다.

bind는 packet을 받을 때 사용한다는 군요. 어찌 되었던...

1. 패킷을 전송하려면 일단 raw 소켓을 만듭니다.

sockfd = socket(PF_PACKET, SOCK_RAW, 0);

raw 소켓을 생성할 때는 루트 권한이 필요합니다.

2. 패킷을 만듭시다.

이더넷 헤더는 목적지 MAC 주소(6 byte), 발신 MAC 주소(6 byte), 프로토콜 타입(2byte)로 이루어 집니다.

그리고 그 뒤에 데이터가 따라 붙습니다. 예를 들어 ARP 패킷같은 경우에는...

typedef struct arp_packet
{

//이더넷 헤더
BYTE dest[6];    //mac destination.
BYTE source[6];    //mac source.
WORD type;    //protocol type.

//ARP 패킷 내용

WORD hw_type;    //hardware type.
WORD p_type;    //protocol type.
BYTE hw_len;    //hardware address length.
BYTE p_len;    //protocol address length.
WORD opcode;    //operation.
BYTE s_hw_addr[6];    //sender hardware address.
BYTE s_p_addr[4];    //sender protocol address.
BYTE t_hw_addr[6];    //target hardware address.
BYTE t_p_addr[4];    //target protocol address.
} __attribute__ ((__packed__))
ARPPacket;

과 같이 구성할 수 있겠습니다.

3. sendto를 하기 전에, sockaddr 설정.

sendto에서 쓸 sockaddr를 만듭니다.

여기서는 struct sockaddr이 아니고 struct sockaddr_ll을 만들어 줍니다.

struct sockaddr_ll send_address;

sockaddr_ll에서 ll은 이더넷 패킷 전송이 link layer level에서 이루어 져서 붙은 거라고 추측이 되네요.

이제 값을 줘야 하는데 일단 다른 건 전부 0으로 초기화 해야 합니다(memset 같은 걸로요).

그리고 다음에 3가지만 설정합니다.

send_addr.sll_family = PF_PACKET;
send_addr.sll_ifindex = if_nametoindex("네트웍 장치 이름");
send_addr.sll_halen = 6;

sll_family는 socket의 것과 같은 것으로 해주고...

sll_ifindex는 전송에 사용할 네트웍 장치의 index입니다. 제 경우에는 eth0가 index 2에 해당되더군요.

만일 장치의 이름을 알고 있다면 위처럼 if_nametoindex를 이용해서 index를 얻는 방법도 있습니다

if_nametoindex(char *) :

interface이름을 character로 바꾸어 줍니다. <net/if.h>에 정의되어 있습니다.

4. 이렇게 sockaddr_ll을 설정해 준 다음 이것을 이용해서 sendto를 합니다.

만일 sendto에서 오류가 난다면 strerror로 errno를 찍어봐야 겠죠...

printf("error message:%s", strerror(errno));

대부분 경우에는 해당 네트웍 장치가 사용 불가 상태/부적합인 경우에 에러가 나더군요.

그리고 listen할 때는 모르겠지만 전송 할 때는 psudo network device(any)는 사용 불가인가 봅니다.

제 경우는 index 0번이 any더군요.

[노트][DSP] 5. Frequency Domain Representation

2009-04-19T16:53:00.000+09:00

1. Exponential sequence response

alignl x[n] = e^{j omega n} RARROW gauss stack {{~}{h[n]}{~}} RARROW y[n] = x[n] * h[n] = h[n] * x[n] = sum from {k = - infinity} to infinity h[k] cdot e^{j omega (n - k)} newline = e ^ {j omega n} sum from {k = - infinity} to infinity h[k] cdot e^{- j omega k} = e ^ {j omega n} cdot H(e^{j omega})

즉, exponential sequence에 대한 응답은
입력에서 주파수는 변하지 않고 크기(abs {H(e^{j omega})})와 위상(angle H(e^{j omega}))만 변하는 것을 알 수 있다.

- H(e^{j omega}) : frequency response(주파수 응답). 이 값은 complex number이다.
이것은 h[n](impulse response)을 Discrete-TimeFourierTransform한 결과이다.

1.1. exponential response의 의미?

LTI는 x[n]을 δ[n]의 합으로 표현 했다면(in Time domain)
DTFT는 x[n]을 exponential sequence(e ^ {j omega n})의 합으로 표현한다(in Frequency domain).
즉, LTI와 비슷하게 DTFT에서는 exponential sequence(e ^ {j omega n})에 대한 response(H(e^{j omega}))만 알면 system의 특성을 알 수 있다.

(ex) ~ cos omega_0 n = {e^{j omega_0 {n}} + e^{j omega_0 {n}}} over 2 DRARROW y[n] = 1 over 2 H(e^{j omega_0}) cdot e^{j omega_0 n} + 1 over 2 H(e^{- j omega_0}) cdot e^{- j omega_0 n}

1.2. Filters

Filter에는 대표적으로 다음과 같은 것이 있다.

alignl low-pass filter H_LPF(e^{j omega}) = lbraket {stack {{1 ~~ abs omega lesseq omega_c} {0 ~~ omega_c < abs omega < pi}}}

alignl high-pass filter H_HPF(e^{j omega}) = lbraket {stack {{1 ~~ omega_c lesseq abs omega lesseq pi} {0 ~~ absomega < omega_c}}}

alignl band-pass filter H_BPF(e^{j omega}) = lbraket {stack {{1 ~~ omega_a lesseq absomega lesseq omega_b} {0 ~~ otherwise}}}

alignl band-stop(reject) filter H_BSF(e^{j omega}) = lbraket {stack {{0 ~~ omega_a < absomega < omega_b} {1 ~~ otherwise}}}

DSP에서의 filter 설계는(대략적으로...)

(1) 원하는 filter의 특성을 frequency domain에서 그려본다(abs {H(e^{j omega})}).

(2) abs {H(e^{j omega}})으로 부터 h[n]을 얻는다. 그리고 이것으로 구현을 설계한다.

2. Discrete-Time Fourier Transform

DTFT Pair lbraket stack {{X(e^{j omega}) = sum from {n = - infinity} to infinity x[n] e^{- j omega n} ~ ~ (X(e^{j omega})는 x[n]의 fourier series 표현)} {x[n] = 1 over {2 pi} int from {- pi} to pi X(e^{j omega}) cdot e^{j omega n} d omega ~ ~ (x[n]은 fourier series의 계수)}}

- principal value of angle H(e^{j omega})
- pi < angle H(e^{j omega}) lesseq pi

- existence of DTFT
당연히 X(e^{j omega})의 값이 finite해야 할 것이다. 따라서,
abs {X(e^{j omega})} = abs {sum from {k = - infinity} to infinity x[k] cdot e^{- j omega k}} lesseq sum from {k = - infinity} to infinity abs{x[k]} cdot abs{e^{- j omega k}} = sum from {k = - infinity} to infinity abs{x[k]} < infinity

2.1. Properties of DTFT

({~}^*는 conjugation을 의미)

(1) Even, Odd

even function : n에 대해 대칭

odd function : 원점 대칭

alignl x_even[n] = 1 over 2 "{" x[n] + x^*[- n] "}" = {x_even}^*[-n] newline x_odd[n] = 1 over 2 "{" x[n] - x^*[- n] "}" = - {x_odd}^*[-n]

abs {X(e^{j omega})} = abs {X(e^{- j omega})} (크기는 omega 에 대해 even)

angle {X(e^{j omega})} = - angle {X(e^{- j omega})}(각은 omega 에 대해 odd)

실제로는 x[n]이 real이므로 (complex number은 계산의 편의를 위한 것임.)

x[n]이 real이면...

alignl X(e^{j omega}) = sum from {k = - infinity} to infinity x[k] cdot e^{- j omega k} newline X^*(e^{- j omega}) = sum from {k = - infinity} to infinity x^*[k] cdot {(e^{j omega n})}^* = sum from {k = - infinity} to infinity x[k] cdot e^{- j omega k} = X(e^{j omega})

(2) Linearity

a x_1[n] + b x_2[n] lrarrow a X_1(e^{j omega}) + b X_2(e^{j omega})

(3) Time shift

x[n - n_d] lrarrow e^{- j omega n_d} cdot X(e^{j omega})

(4) Frequency shift (for modulation)

e^{j omega_0 n} cdot x[n] lrarrow X(e^{j (omega - omega_0)})

(5) Time reversal

x[- n] lrarrow X(e^{- j omega})

(6) Differentiation

n cdot x[n] lrarrow j cdot d over {d omega} (X(e^{j omega}))

(7) Parseval's theorem

E = sum from {n = - infinity} to infinity abs{x[n]}^2 = 1 over {2 pi} int from {- pi} to pi abs{X(e^{j omega})}^2 d omega

즉, sample의 에너지의 합은 frequency domain의 에너지의 합과 같다.

(8) Convolution theorem

y[n] = x[n] * h[n] lrarrow Y(e^{j omega}) = X(e^{j omega}) cdot H(e^{j omega})

time domain에서의 convolution은 DTFT에서의 곱

(9) Windowing theorem

y[n] = x[n] cdot w[n] lrarrow Y(e^{j omega}) = int from {- pi} to pi X(e^{j omega}) cdot W(e^{j (omega - theta)}) d theta

time domain에서의 곱은 DTFT에서의 convolution.

2.2. Gibbs Phenomenon

아래와 같은 LowPassFilter가 있다.

alignl H_LP(e^{j omega}) = lbraket stack{{1 ~~ abs omega < omega_c} {0 ~~ otherwise}}

alignl h_LP[n] = 1 over {2 pi} int from {- pi} to pi H_LP(e^{j omega}) cdot e^{j omega n} d omega = 1 over {2 pi} int from {- omega_c} to {omega_c} e^{j omega n} d omega newline = 1 over {2 pi} {e^{j omega_c n} - e^{- j omega_c n}}over{j n} = {sin(omega_c n)}over{pi n}

h_LP[n]은 absolutely summable하지 않다. 따라서 전체 중 일부분만 잘라서 사용하기로 한다.

alignl {tilde h}_LP[n] = lbraket {stack {{{sin(omega_c n)} over {pi n} ~~ |n| lesseq M} {0 ~~ otherwise}}}

{tilde H}_LP(e^{j omega}) = sum from {m = - M} to M {sin(omega_c n)} over {pi n} cdot e^{- j omega n}

이 때 M이 finite하면 절대로 peak가 일정 수준 아래로 줄지 않는다. 즉 이대로는 ideal filter(또는 windowing할 때 쓰는 ideal function 같은 것)를 만들 수 없다

(eof)

[글] 밤, 거리, 방

2009-04-18T01:45:00.000+09:00

지금까지 하늘만 바라보고 있었는지도 모른다.
부둣가에 서서 먼 수평선 너머를 바라보고 있었는지도
작은 창문 너머로 저무는 해와 그 아래의 거리를
바쁘게 오가는 사람들만 바라보고 있었는지도, 모른다.
무언가가 변하고 지나가고, 사라졌다.
그렇게 움직일줄 모르던 구름도 멀리 가버렸다.
그래서 나는 언제나 움직여야 했다.
매일이 새로워야 한다고, 특별해야 한다고 생각하고
그러니까 무언가 빨리 해 내야만 한다고 생각하고
항상 바쁜 생각을 하고 쉴새 없이 움직여야 했다.
그런데 모든 잡음이 사라진 새벽의 방에서
보았다.
자신이라는 것.
너무 많은 의미를 가져야 한다고 생각했던게 아닐까.
모든 것이 중심을 가지고 있다고 생각하는게 아닐까.
하지만 나를 완전히 빗겨나가며 도는 세계를 보면서
내가 왜 남들 처럼 밤 거리를 정처 없이 돌아다녀야 하는지를 생각했다.

거의 비어가는 기억이 나를 다시 슬프게 한다.

어쩌면 나는 다시 나를 찾으러 되돌아 가야 할지 모르겠다.

[기타] 윈도우 가젯 - sitmo 수식 입력기

2009-04-17T17:33:00.000+09:00

sitmo.gadget

sitmo 수식 입력기 윈도우 가젯입니다.

구글 데스크탑 가젯은 만들기 뷁 같아서

단순한 윈도우용 가젯으로 만들었습니다.

크기가 크기 때문에 Vista에서는 어떨지 모르겠네요.

위의 스샷은 윈도우 7 입니다.

[Javascript] 수식 변환기 스크립트

2009-04-16T15:12:00.000+09:00

- 미니 수식 변환기

minieqn.js

<span code="minieqn">~</span>

의 내용을 수식으로 변환해주는 스크립트입니다.

아래의 예시에서 보이듯이 모양은 별로 깔끔하지 않습니다......

역시 그냥 sitmo를 쓸걸 그랬...

아직은 실험적으로만 사용중입니다. 버그가 남아있을 수 있습니다.

테스트:

정상 작동(아마도...) - IE 8, FF 3.08, Opera9.64

symbol이 왼쪽으로 밀림 - Safari 3.2.2

일부 symbol 보이지 않음 - (IE Tester로) IE 5.5, IE 6.0
아랫 부분 잘림 - IE 7.0 (LINE_HEIGHT값 설정으로 해결)

- 적용하는 법(쓰실 분이 혹시나 있다면...)

홈페이지나 블로그의 적당한 부분(예를 들면 <head>~</head>)에 js를 삽입해 주세요.

그리고 본문 로딩이 끝난 뒤 RunMiniEqn()을 불러주도록 하면 됩니다.

예를 들면 다음과 같습니다.

<body>
...
<script>

</script>
</body>

저의 경우에는 텍큐에 있는 HTML 위젯에 소스코드를 전부 붙여 넣었습니다.

- 문법

설명	코드	결과
하한(심볼의 아래쪽)	sum from {a = 1}	sum from {a = 1}
상한(심볼의 윗쪽)	sum to {infinity}	sum to {infinity}
상한 & 하한	sum from {k = - infinity} to {0}	sum from {k = - infinity} to {0}
지수	S^{x+1}	S^{x+1}
분수	{x} over {x + 1}	{x} over {x + 1}
줄 바꿈	x = 2009 newline y = 2010	x = 2009 newline y = 2010
공백	x ` = ` y newline x = y	x ` = ` y newline x = y
공백 * 2	x ~ = ~ y	x ~ = ~ y
문자열	"this is text!"	"this is text!"
정렬	AAAAAAAAAAAAAAAAA newline alignl "left text" newline alignr "right text" newline alignc "center text"	AAAAAAAAAAAAAAAAA newline alignl "left text" newline alignr "right text" newline alignc "center text"
행렬	matrix {{12 3 45} {6 78 9}}	matrix {{12 3 45} {6 78 9}}
세로로 나열하기	stack {a b c d}	stack {a b c d}
색상	color:red {x = y + z}	color:red {x = y + z}

다음은 예시 입니다.

minieqn 코드	결과
sum from {k = 1} to {N} S_i	sum from {k = 1} to {N} S_i
lim from {n rarrow infinity} {gauss {n^2}} over {n^2 + n^2 + 1}	lim from {n rarrow infinity} {gauss {n^2}} over {n^2 + n^2 + 1}
h(t) = 1 over {2 pi} int from {- pi} to pi H(j OMEGA) e^{j OMEGA t} d OMEGA	h(t) = 1 over {2 pi} int from {- pi} to pi H(j OMEGA) e^{j OMEGA t} d OMEGA
alignl u[n] = lbraket stack {{1 ~ n ge 0} {0 ~ otherwise}}	alignl u[n] = lbraket stack {{1 ~ n ge 0} {0 ~ otherwise}}

[글] 아침, 어느 마을의 정원

2009-04-14T00:40:00.000+09:00

어느 아침에ㅡ
긴 잠에 날개 짓하며 날아오르는 새처럼
어린 팔로 기지개를 펴면,
창문 너머로 구름 뭉실 떠가는
푸른 하늘을 보았지.

우린 참 아름다운 정원을 가지고 있어요.

조용히 솟아있는 산들과
그 푸르고 보드라운 살결 한 언저리
오래된 고성의 풀담 아래서
햇빛의 구를 소리 없이 굴리는 풀들과
묵묵히 서 있는 초록 나무들이
언제나 함께 있어주었지.

잔잔히 햇살이 드리우는 어느 아침
살갑게 바람이 흘러오는 창가에서
짧고도 길었던 거리들을 바라보았지.
지금은 볼 수 없는 푸른 하늘과
먼 거리 저 편으로 날아오르는 새들과
즐겁게 웃으며 달려가는 아이들.
낡아도 정 때 묻은 건물 사이
오래 닳아서 푸근한 돌길 위로
어딘가로 향하네. 다시 볼 수 있을까.

입안에 퍼지는 향그러운 차
그의 향 만큼이나
사뿐히 부서지는 비스킷
그 감촉만큼이나,
자꾸만 마음속에 음미하듯 다가오는 곳.
그 생각에 눈을 스르르 감으면…….

어느 아침에
긴 잠에서 깨어나는 새처럼
날개 짓 하는
어린 아이가
있다.

[노트][DSP] 4. LTI(Linear Time Invariant) System

2009-04-10T15:50:00.000+09:00

1. Linear Time Invariant System

_∞

- input : ∑ x[k] δ[n-k]

^k=-∞

_{∞ ∞ ∞}

- output: y[n] = T{ ∑ x[k] δ[n-k] } = ∑ x[k] T{δ[n-k]} = ∑ x[k] h[n-k]

^{k=-∞ k=-∞ k=-∞}

(Linearity) (Time-Invariant : T{δ[n-k]} = h[n-k])

where h[n] = T{δ[n]} (impulse response : δ[n]에 대한 응답)

즉, impulse response h[n]만 알면 그 LTI System의 성질을 알 수 있다.

x[n] * δ[n] = x[n] !!!

2. Convolution

_∞

y[n] = x[n] * h[n] = ∑ x[k] h[n-k]

^k=-∞

- Commutative : x[n] * h[n] = h[n] * x[n]

- Distribute : (x₁[n] + x₂[n]) * (h₁[n] + h₂[n]) =

x₁[n] * h₁[n] + x₁[n] * h₂[n] + x₂[n] * h₁[n] + x₂[n] * h₂[n]

- 병렬화 : h[n] = h₁[n] + h₂[n] (시스템의 속도 향상에 도움이 되는 디자인)

x[n] -> [h[n]] -> y[n] == 병렬화 ==> x[n]-> Divide -> [h₁[n]] -> Add -> y[n]

Input -> [h₂[n]] -> Outputs

3. Convolution 계산하기 (예제와 함께...)

- h[n]을 움직이면서 더하기

{x[n]}중에 하나를 택한다. 그것을 k라고 하면 x[k] × h[n-k] (convolution 아님)를 그린다.

(eg)

- Flip-and-drag

h[k]을 뒤집는다(h[-k]). 그리고 x[k]의 시작과 h[-k]의 끝을 맞춘 뒤에

오른쪽으로 끌어가면서(h[-(k-n)]) 겹치는 것 끼리 곱해서 더한 값을 해당 지점(n)의 값으로 한다.

(eg)

- 수학적으로...(δ[n]의 성질 이용)

∑ z[n, k] δ[k-c] = z[n, c] (δ[k-c]가 의미를 갖는 것은 k = c일 때 뿐이다) 임을 이용한다.

(eg) 위와 같은 예를 풀어보자.

∑ (2δ[k] - δ[k-1])(-δ[n-k] + 2δ[n-1-k]) + δ[n-2-k])

(k = 0) (k = 1) 일 때 의미를 갖는다.

= 2 (-δ[n] + 2 δ[n-1]) + δ[n-2]) - (-δ[n-1] + 2δ[n-1-1]) + δ[n-2-1])

k = 0 k = 1

= - 2 δ[n] + 5 δ[n-1] - δ[n-3]

4. Inverse System

x[n] -> [ h₁ ] -> [ h₂ ] -> x[n] = x[n] -> [ δ[n] ] -> x[n]

h₁ * h₂ = δ[n] : identical system

이 때, h₂는 h₁의 inverse system(또는 h₁는 h₂의 inverse system).

* h₁을 모를 때 h₂를 바꾸어 가면서 y[n] = x[n]이 되는 h₂를 찾으면 h₁을 알 수 있다.

(eg) accumulator와 backward difference는 inverse 관계이다.

u[n] * (δ[n] - δ[n-1]) = u[n] - u[n-1] = δ[n]

5. Finite Impulse Response(FIR), Infinite Impulse Response(IIR)

- FIR : impulse 에 대한 response가 finite한 sequence인 것.

- IIR : impulse 에 대한 response가 infinite한 sequence인 것.

(eg) accumulator는 IIR이다. ∴ h[n] = u[n] = δ[n] + δ[n-1] + δ[n-2] + …

backward difference는 FIR이다. ∴ h[n] = δ[n] - δ[n-1]

6. Difference Equation

_N _N

- General form : ∑ a_k y[n-k] + ∑ b_m x[n-m]

^k=0 ^m=0

- Method1: 수학적으로...는 어렵다. ㅠ.ㅠ

y = y_p + y_h......

- Method2: 컴퓨터에게 시키는 방법.

_N _N

a₀ y[n] = - ∑ a_k y[n-k] + ∑ b_m x[n-m]

^k=1 ^m=0

일단 y[-1], y[-2], ..., y[-N]값(초기 값)은 주어진 상태여야 한다.

그 다음에는 컴퓨터가 차례대로 y[0], y[1], y[2], ...를 계산해 나가면 된다.

- Method3: DTFT를 이용하는 방법.(가장 좋음)

Difference Equation을 Discrete Time Fourier Transform으로 변환해서 푸는 방법으로 가장 무난함. Frequency Domain Representation에서 다룸.

[글] 부둣가에서의 밤 인사 - 그리움은 밤의 어둠에 묻고

2009-04-05T21:39:00.000+09:00

해가 저문 후의 부둣가는

어둠이 조용히 내리 우고,

새하얀 벽돌이

어둠 속에서 진주처럼

희미하게 빛나네.

차갑게 식은 대지의 위에서

마음은 다른 마음 깊이 끌어안고

쌀쌀히 내게 불어오는 밤 바람은

나의 눈가에 맺힌 이슬 닦아주네.

해가 저문 후의 부둣가는

달빛이 조용히 내리 우고,

내 안의 조그만

공간 속에서 추억처럼

바랜 듯이 빛나네.

차갑게 식은 벤치 위에 앉아서

눈은 어딘가 다른 곳을 바라보고

잔잔히 내게 걸어오는 밤 바람은

너의 손길처럼 살며시 감싸네.

모든 밤의 시간들이 다가와

쓸쓸한 발자취를 남기지만,

너와의 추억 속에 시간은

어두운 하늘에 바랜 달빛.

해가 저문 후의 부둣가는

바람이 조용히 내리 우고,

파도가 잔잔히 부둣가를

아쉬운 손길로 쓰다듬네.

지나간 시간들 속에 갇힌 채

내일의 하늘은 푸르지 않다고,

상처 입은 눈을 감싸 쥐고

혼자서 하염없이 그저 앉아 있네.

해가 저문 후의 부둣가는

가로등이 조용히 빛나고,

새하얀 벽돌은 어둠 속에

희미한 불빛을 머금고 있네.

마음 속에 담아둔 풍경들을

그리워 자꾸 잡으려는 것이지만,

내일의 힘찬 걸음을 걷는 나를

너는 보고 싶은 것이 아닐까.

고통에 사로잡혀 주저 앉는 건

과거를 놓지 않기 때문이야.

바쁘게 걸어가야 할 현재 속에

언젠가 조용히 생각 할 수 있기를.

해가 저문 후의 부둣가는

달빛이 조용히 내리 우고,

잔잔히 내게 걸어오는 밤 바람은

너의 손길처럼 살며시 감싸네.

[리눅스] 프로세스 죽이는 쉘 스크립트

2009-04-01T21:39:00.000+09:00

죽지 않는 bochs들... 때문에 고민하다가 만든 쉘 스크립트입니다.

프로세스 이름으로 pid를 찾아서 죽이는 방식입니다.

그런데 찾아보니 아주 짧고 간단한 것도 많더군요(괜한 삽질 -_-;;).

#!/bin/bash

#killua : process kill helper



imm_flag=1

exact_flag=1

user_flag=1



process_name=""



_kill_pids()

{

  #check process name

  if [ "$process_name" = "" ]

  then

    echo "error! process name is empty."

    exit 1

  fi



  #get process list

  if [ $user_flag -eq 1 ]

  then

    if [ $exact_flag -eq 1 ]

    then

    grep_result=$(ps | grep -w $process_name)

    else

    grep_result=$(ps | grep $process_name)

    fi

  else

    if [ $exact_flag -eq 1 ]

    then

    grep_result=$(ps -A | grep -w $process_name)

    else

    grep_result=$(ps -A | grep $process_name)

    fi

  fi

  pid_list=""



  #extract pids

  for segment in $grep_result

  do

    if [ "${segment##[0-9][0-9][0-9][0-9]*}" = "" ]

    then

      pid_list="$pid_list $segment"

    fi

  done



  failed_list=""

  #kill each pid

  for pid in $pid_list

  do

    echo "kill pid: $pid"

    if [ $imm_flag -eq 1 ]

    then

      kill -9 $pid

    else

      kill $pid

    fi



    #check that pid is killed.

    grep_result=$(ps -A | grep $pid | grep $process_name)

    if [ "$grep_result" != "" ]

    then

      echo "failed."

      failed_list="$failed_list $pid"

    else

      echo "killed."

    fi

  done



  #print failed pids

  echo "Failed pids: $failed_list"

}



_usage_message()

{

  echo "killua : process kill helper."

  echo "./killua  "

  echo ""

  echo "<>"

  echo "--user-only, -u       kill user process only.(default)"

  echo "--all, -a              kill all process(needs root permission.)"

  echo "--immediately, -i     kill immediately(sigkill)(default)"

  echo "--send-signal, -s     send sigterm."

  echo "--exactly, -e           find process of which name is exact same as (default)"

  echo "--contains, -c         find process of which name contains "

}



_main()

{

  if [ $# -lt 1 ]

  then

    _usage_message ""

    exit 1

  fi



  #parse argument

  while [ $# -ge 1 ]

    do

      if [ "$1" = "--immediately" -o "$1" = "-i" ]

      then

        imm_flag=1

      elif [ "$1" = "--send-signal" -o "$1" = "-s" ]

      then

        imm_flag=0

      elif [ "$1" = "--user-only" -o "$1" = "-u" ]

      then

        user_flag=1

      elif [ "$1" = "--all" -o "$1" = "-a" ]

      then

        user_flag=0

      elif [ "$1" = "--exactly" -o "$1" = "-e" ]

      then

        exact_flag=1

      elif [ "$1" = "--contains" -o "$1" = "-c" ]

      then

        exact_flag=0

      elif [ "$1" = "--help" ]

      then

        _usage_message ""

      else

        process_name="$1"

      fi

      shift

  done



  #do kill pids

  _kill_pids ""

}



_main $*

[글] 산홋빛 밤 바다

2009-03-25T22:26:00.000+09:00

바닷가의 밤은 그렇게
파도 소리 하나 없이 찾아온다.
언젠가 이 절벽에 앉아서
먼 바다를 내려다보면
예전의, 더 오래전의 바다가
달빛 아래서 잔물결에 빛나고
언제인가 함께했던 너의 모습도
달빛 받아 바랜지 오래-
그렇게 절벽은 고독한 표정인듯 싶다가도
바다 먼 곳에서 바람은 불어온다.
밤에 부는 바람은 차고도 잔잔하다.
먼 예전의 촉감이었으리라.

바닷가의 밤은 그렇게
밝은 등불하나 들고 오지 않는다.
해변의 모래사장은 순백의 피부에
벌써 밤의 어둠을 머금어 빛나고 있었다.
먼 예전의 모습이었으리라.

언젠가 저 멀고먼 수평선의 곡선 너머로
배 한척이 흔들거리며 올 듯한
바다를 바라보며 생각에 잠기면
수면은 달빛에 더욱 하얗게 빛나는 것이었다.
언젠가 만날 너의 바다를
더욱더 더욱더 밝게 비추어 주기를.

바닷가의 밤은 그렇게
먹구름 한 점도 몰고 오지 않는다.
고개를 들어 하늘을 바라보면,
거울에 비추어진 바다가 보인다.
바다처럼 파도는 치지 않지만,
바다 보담은 별은 많이 떠 있다.
파도도 잔물결도 없는 검은 바다엔
수많은 별들이 배처럼 유유히 떠간다.
너의 배는 지금 어디쯤에 있을까.
그곳에서 별과 지구는
그렇게 먼 곳에 떨어져 있는건데.
너를 아무리 불러도 바다 바람소리만 들려오는
이 해안가에서 여전히 나는 걷고 있다.
매일 하늘에 검은 바다가 몰려오면,
언젠가 네가 있을 그 바다로
나도 별처럼 떠 갈 것을 생각한다.

그러기 전엔 매일 하루를
물결도 일지 않는 검은 바다 아래에서
홀로 추억에 이슬 짓고
바닷가 백사장을 걸으며
옛일을 더듬어 찾을 뿐이다.

바다 바람은 그치지 않고 계속 불어오나 보다.

[메모][리눅스] 쉘 스크립트 작성시 주의사항

2009-03-22T14:34:00.000+09:00

매번 까먹고 삽질하는 부분 ㅠ.ㅠ

1. 변수에 대입할 때 varid=value에서 '=' 양쪽에 절대로 공백이 있어서는 안됨!

(예) msg="this is a message"

(잘못된 예)

msg = "this is a message"

와 같이 하면 쉘이 'msg'를 명령어로 인식해서 못찾겠다고 함.

에러 메시지는 대략 이런 모양...

./test: line 1: msg: command not found

2. if [ condition ] 에서 condition 앞, 뒤에는 꼭 space가 하나 있어야 함!!

(예) if [ $# -ge 1 ]

^ ^

(잘못된 예)

id=0

if ["$id" -eq "0"]

then

echo "$id"

와 같이 space가 없으면 쉘이 [0을 모른다느니 이상한 소리를 함. 아마도

["$id" -> ["0" -> [0

이라고 생각해서 '[0' 이 명령어 인줄 아는듯...

에러 메시지는 대략 이런 모양...

./test: line 2: [0: command not found

./test: line 2: [0: not found

만일에 위의 1, 2의 두 실수를 같이 하면 이런 메시지를 보게 될지도...

[: 38: missing ]

[노트][DSP] 3. Discrete-time Systems

2009-03-18T11:44:00.000+09:00

0. Discrete-time System에는 5가지의 특성이 있다.

(1) Memoryless (2)Linear (3)Time-invariant (4)Causal (5)Stable

1. Memoryless System

출력이 현재의 입력으로만 결정되는 것으로 T{δ[n]} = 0 (n ≠ 0) 인 시스템.

다시 말해 과거나 미래의 입력에 의존하지 않는 시스템이다.

(eg) memoryless system

y[n] = x[n] (identical)

y[n] = c x[n], (c is constant) (scaling)

(eg) memory system

y[n] = x[n - n_d] (n_d ≠ 0) (ideal delay)

2. Linear System

- Additive

T{x₁[n] + x₂[n]} = T{x₁[n]} + T{x₂[n]}

- Scaling

T{a x₁[n]} = a T{x₁[n]}

- x[n] = Σ a_k x_k[n] -> [T( · )] -> y[n] = Σ a_k y_k[n]

3. Time-invariant System

입력에 delay가 있으면 출력에도 delay가 생기는 system.

즉, T{x[n - n_d]} = y[n - n_d].

(eg) not time-invariant한 것들

_n _{n_d-1}

y[n] = Σ x[k] (n ≥ N) => T{x[n]} * δ[n-n_d] = Σ x[k] (n ≥ N + n_d)

^{k = N} ^{k = N}

0 (n < N) 0 (n < N + n_d)

T{x[n] * δ[n-n_d]} = Σ x[k-n_d] (n ≥ N)

^{k = N}

0 (n < N)

∴T{x[n - n_d]} ≠ y[n - n_d]

y[n] = x[M n] => 전체 sample에서 일정 간격 M으로 sample을 고른것.

n_d ≠ M k (k is integer)이면 전혀 다른 sample을 고르게 된다.

따라서 T{x[n - n_d]} ≠ y[n - n_d] (아래 그림 참고)

4. Causal System

현재의 출력은 미래에 영향을 받지 않는다. (y[n] depends on only {x[k]}, k ≤ n)

If x₁[n] = x₂[n] for n ≤ n₀ then y₁[n] = y₂[n] for n ≤ n₀.

(eg) Backward difference : y[n] = x[n] - x[n-1] (causal)

Forward difference : y[n] = x[n+1] - x[n] (not causal!)

non-causal system은 ideal delay를 이용해서 causal system으로 만들 수 있다.

예를 들어 위의 Forward difference에 δ[n-1]를 붙여주면

h[n] * δ[n-1] = (δ[n+1] - δ[n]) * δ[n-1] = δ[n+1 - (-1)] - δ[n - 1] = δ[n] - δ[n-1]

즉, Backward difference가 된다.

또, non-causal system은 input 받는 부분에 queue를 달아서 causal system으로 만들 수 있다.

예를 들어 Forward difference의 경우 크기가 2인 큐 Q로 input {x[n]}을 받아서

k ← 2

insert(Q, x[1])

while (k < N)

{

insert(Q, x[k])

y[k-1] ← Q.First() - Q.Last()

poll(Q)

k ← k + 1

}

와 같이 구현 할 수 있겠다.

5. Stable System(Bounded Input Bounded Output)

|x[n]| ≤ B_x < ∞ => |y[n]| ≤ B_y < ∞

또는 output이라는 것은 본래 impulse(δ[n]) response로 결정되므로(LTI System) 간단하게

Σ|h[n]| < ∞ (absolutely summable)

하면 stable system이다.

후자에 대해서 덧붙이자면, 만일 system의 impulse response h[n]이

finite sequence 이면 stable하고 infinite sequence이면 not stable이다.

[글] 의미 없는 것

2009-03-15T23:59:00.000+09:00

아직 해가 뜨지 않아 어두운 거리를

버스 정류장에서 서서 바라보며

즐겨보는 영화의 한 장면을

스크린처럼 비추어 보는것

달리는 버스안에서

이제막 밝아오는 하늘을 바라보며

즐겨듣던 노래의 한 구절을

혼자서 들리지 않게 흥얼거리는 것

만원인 지하철 문가에 서서

언제나 창 밖을 지나가는 건물들을 바라보다

처음 보는 간판을 바라보며

신기하게 생각하는 것

비어있는 시간에

쥐 죽은듯 조용한 곳에 앉아서

멍하니 공상에 잠겨있다

시계를 보고 깜짝 놀라는 것

돌아오는 버스안에서

열심히 수업내용을 외워보려고 해도

지는 석양을 바라보다

최면에 걸린 것처럼 어느새 잠이 드는 것

정류장에서 집으로 걸어오며

예전에 자주 지났었던

놀이터의 작은 샛길을 보며

교복을 입은 나의 뒷 모습을 상상하는 것

늦은 저녁의 휴식시간

이제 막 재미있어진 애니메이션을 보며

주인공의 위기에 나도 모르게 긴장해버린

자신이 우습게 느껴지는 것

잠이 들기 전에

자꾸만 쓸데없는 말들이 떠올라

잠을 못 이루고 컴퓨터 앞에 앉아

이 글을 쓰는 것...은

당신에게는 의미 없는 것

[글] 밤의 산들바람

2009-03-12T22:58:00.000+09:00

초원의 작은 언덕에 올라
스스럼 없이 드러낸 달을 바라보는 것은
그것이 바람 추운 계절이라도 따뜻한 것이라.
세계는 온갖 슬픔의 빛으로 뒤덮여서
마을은 환한 가운데 어두우나
달빛 은은한 초원에는
밝음도 어둠도 없어라, 따뜻함만이.

보름달 아래 초원을 거닐며
미소짓는 얼굴을 마음속에 그리는 것은
그것이 홀로 외로이 있음에도 가득차는 것이라.
환한 보름달처럼 가득한 밤하늘의 빛깔은
그야말로 순수한 미소로다, 온기로다,
끝없이 떠오르는 그리운 얼굴이로다.
그곳엔 슬픔은 없어라, 오래된 기쁨만이.

초원 한 가운데 서서
조용히 밤바람을 맞는 것은
그것이 무심한 가운데에도 의미가 있는 것이라.
숱하게 흩어져가는 풀잎이며 작은 흙먼지처럼
응어리져 박혀버린 생각들을 흘려보내고
오직 마음만이 있어라,
달빛 깊은 초원에.

[노트][DSP] 2. Discrete-time Signals

2009-03-11T13:40:00.000+09:00

0. 몇 가지 표현들

f(t) 와 같이 "()"로 변수를 둘러싼 것은 Analog Signal을 의미.

f[n]와 같이 "[]"로 변수를 둘러싼 것은 Discrete Signal을 의미.

1. Discrete-time signal is sequence.

- x = {x[n]}, where -∞ < n < ∞ n integer.

or x[n] = x_a(nT), x_a is analog signal, T is sampling period.

- delayed sequence

y[n] = x[n - n₀]

- unit sample sequence (or discrete-time impulse)

δ[n] = 0 elsewhere

1 (n = 0)

그리고` x[n] = sum from {k = - infinity} to {infinity} x[k] cdot delta [n - k]

(결국 모든 discrete signal은 unit sample sequence의 합!)

- unit step sequence

u[n] = 1 (n ≥ 0)

0 (n < 0)

"그리고"` u[n] = sum from {k = 0} to {infinity} 1 cdot delta [n - k] = sum from {t = - infinity} to n delta [t] newline "또" delta [n] = u[n] - u[n - 1]

- exponential sequence

x[n] = A alpha^n

* If α, A is complex, α = |α|e^jw₀, A = |A| e^jΦ.

then Aαⁿ = |A| |α|ⁿ e^{j w₀ n} e^{jΦ =}|A| |α|ⁿ( cos(w₀ n + Φ) + j sin(w₀ n + Φ) )

[참고] Rectangular Coordinate & Polar Coordinate

Rect. Coordinate : z = a + j b

Polar Coordinate : z = |z| e^jθ, where |z| = sqrt(a² + b²), θ = tan^-1 (b / a)

- sinusoidal sequence

x[n] = A cos(w₀ n + Φ) = Re{ A e^{j(w₀ n + Φ)} }

w₀ : frequency

Φ : phase

* Re{ A e^{j(w₀ n + Φ)} } = Re{ A ( cos(w₀ n + Φ) + j sin(w₀ n + Φ) ) }

= A cos(w₀ n + Φ)

2. Sampling periodic signal

- periodic signal에서 임의의 구간을 sampling 하면

그 결과가 반드시 주기적인 discrete signal인 것은 아니다.

- 주파수에 대해서 주기적이다 (period of period : 2 π).

w₀ 보다 더 빠른 w₀ + 2 π r (r is integer)을 sampling 해도 w₀와 같은 결과를 얻는다.

(즉, 다시 말해서 sampling한 결과만 놓고서 어떤 주파수의 파형인지는 알 수 없다.)

* w₀와 w₀ + 2 π r 을 구분 못하는 이유는...

x[n] = A e^{j(w₀ + 2 π r)n} = A e^{j w₀ n} e^{j 2 π r n} = A e^{j w₀ n} (cos(2πrn) + j sin(2πrn))

= A e^{j w₀ n} ( 1 + j · 0 ) = A e^{j w₀ n}

즉, A e^{j(w₀ + 2 π r)n} = A e^{j w₀ n} 이기 때문이다.

- complex exponential에서 w₀의 범위는

-π ≤ w₀ ≤ π 또는 0 ≤ w₀ ≤ 2π

그리고 π에 가까울 수록 high frequency,

0이나 2π에 가까울 수록 low frequency이다.

- Discrete signal의 주기

x[n + N] = A e^{j w₀ (n + N)} = A e^{j w₀ n} e^{j w₀ N}

if w₀ N = 2 π k (k is integer), e^{j w₀ N} = 1 => x[n + N] = x[n] (period = N).

(*k의 의미: analog signal을 k 주기 만큼 sampling하면 주기 N을 갖는 sample을 얻는다.

만일 k가 존재하지 않는다면, 주기가 있는 sample을 얻을 수 없다.)

(eg 1) x[n] = cos((3 / 8) π n) => (3 / 8) π N = 2 π k => N = 16, k = 3

(eg 2) x[n] = cos n => 1 · N = 2 π k => 만족하는 최소 정수 k가 존재하지 않는다. 따라서 주기 없음.

- 변동이 심한 sample = high frequency

변동이 적은 sample = low frequency

[노트][DSP] 1. Digital Signal Processing

2009-03-10T23:01:00.000+09:00

1. Digital System

analog input → [A/D] → [Digital System] → [D/A] → analog output

Digital system은 analog 적인 데이터를 처리하여 내보내는 역할을 한다.

대개 학부 수준에서는 LTI System (Linear Time-Invarient System = Filter) 정도를 다룬다.

2. LTI System f(x)

- LTI System은 시간에 상관 없이 동일한 input에 대하여 동일한 output을 낸다.

- Linear이기 때문에 f(a) + f(b) = f(a + b)이다.

3. DSP라는 것이 왜 필요한가?

예를 들면 sin파형을 sampling한다고 하자.

sampling하는데 만일 일정한 간격으로 sampling 한다면?

정확하게 하기 위해 많은 sample이 필요하다.

하지만 DSP에서의 이론들을 이용한다면 2 + ε개의 sample로 가능하다.

(2개면 두 sample 모두 값이 의미 없는 sample(값 0)을 찍는 경우에 문제가 됨.)

...

(그외의 이야기들도 있었지만 현재로서는 이해 불가 -_-;;)

[노트][Automata] 3. Finite Automata - Regular Expression

2009-03-10T17:50:00.000+09:00

0. Regular Language를 표현하는 방법 3가지

- Finite Automata

- Regular Expression

- Regular Grammar

1. Regular expression (Syntax)

- Ø (Syntax 상 아무 것도 없음을 의미), λ (Semantic 상 아무 것도 없음을 의미)

and a ∈ Σ are all regular expression.

* (λ) ≠ () : 의미상으로는 같은듯 보이지만 완전히 다름. 여기서는 λ도 symbol이다.

더구나 ()는 regular expression이 아니다.

- if r₁, r₂ are regular expression, so are (r₁ + r₂), (r₁ · r₂), (r₁)^* and (r₁).

(위의 네가지에서 괄호는 의미상 혼동이 없을 경우에 생략 가능하다.)

- 위의 두 가지에 의해 재귀적으로 구성되는 모든 string은 regular expression이다.

2. Regular Language denoted by Regular Expression

L(r) : A language denoted by any regular expression r is defined by the following rules.

(꼭 기억! regular expression은 a set of string을 denote한다!)

(1) Ø is regular expression denoting the empty set {}.

(2) λ is regular expression denoting {λ}

(3) For All a ∈ Σ, a is regular expression denoting {a}

(4) L(r₁ + r₂) = L(r₁) ∪ L(r₂)

(5) L(r₁ · r₂) = L(r₁) · L(r₂)

(6) L(r₁^*) = ( L(r₁) )^*

(7) 당연한 이야기인데도 헷갈리는 empty set과의 concatenation,

Ø r = r Ø = Ø

3. Regular Expression은 NFA / DFA dual을 가진다.

Let r be a regular expression.

There exists NFA which accepts L(r).

3-1. Regular Expression → NFA / DFA (Regular Language)

(증명)

(편의상 [q_k]는 일반적인 state, [[q_f]]는 final state로 표시한다.)

(1) Automata that accepts L(Ø), L(λ), L(a).

λ a

→[q_i] [[q_f]] →[q_i] --→ [[q_f]] →[q_i] --→ [[q_f]]

L(M₁) = Ø L(M₂) = {λ} L(M₃) = {a}

(2) Assume M₁(r₁), M₂(r₂) accept r₁, r₂

(r₁ + r₂) M₁

[ ]~~~~[::]

λ↗ ↘λ

→[q_i] [[q_f]]

λ↘ ↗λ

[ ]~~~~[::]

M₂

(r₁ · r₂)

λ M₁ λ M₂ λ

→[q_i] --→ [ ]~~~~[::] --→ [ ]~~~~[::] --→ [[q_f]]

(r₁^*)

________λ_______

↙ ↖

↙λ M₁ λ ↖

→[q_i] --→ [ ]~~~~[::] --→ [[q_f]]

↘ ↗

↘_______λ________↗

3-2. NFA / DFA (Regular Language) → Regular Expression

L is a regular language(즉, NFA / DFA를 가짐),

then there exists a regular expression r such that L = L(r).

(a) By reducing the number of states.

본래의 state diagram의 state들을 가장 간단한 형태인 2개의 state(initial, final)로 줄인다. 이 때 transition들은 regular expression으로 표현한다.

(공식은 다음에 찾아야 할 듯.)

이 방법은 어렵기 때문(state 줄인 뒤 공식에 대입. 공식도 복잡 -__-;;)에 아래 방법이 더 권장됨.

(b) By End set equations.

- End set : 그 state에서 시작해서 final state에 도달하는 string들의 모임.

E(q_k) = E_k (편의상 이렇게 표시) = {w ∈ Σ^* | δ^*(q_k, w) ∩ F ≠ Ø}

(initial state의 end set은 그 자체가 language!)

- Right-linear end set equation

q_k ∈ Q, E_k = ∪ (v_ik E_i ∪ w_k)

^{q_i ∈ Q}

- X = P X ∪ Q 의 해 X

X = P^*Q 이다.

(이 해는 not λ ∈ P 일 경우만 unique하다.

~~만일 λ ∈ P이면 Σ^*도 해가 될 수 있다.~~

Σ^* = PΣ^* ∪ Q = ( (Σ ∪ {λ})Σ^* ) ∪ Q = Σ^* ∪ Q = Σ^*)

* not λ ∈ P 일 경우 unique함에 대해서.

일단, 해가 하나가 아니라고 가정한다.

Let X₁, X₂ is solutions of X = P X ∪ Q,

X₀ = X₁∪ X₂

and X₁or X₂ could be proper-subset of X₀,

because (X₁- X₂) ∪ (X₂- X₁) ≠ Ø (same as X₁ ≠ X₂).

Let X₁ is proper-subset of X₀ (X₁ ⊂ X₀).

Then we can define A = X₀ - X₁ ≠ Ø, X₀ = A∪ X₁.

From X₁ = P X₁ ∪ Q, X₂ = P X₂ ∪ Q,

X₀ = X₁∪ X₂ = (P X₁ ∪ Q) ∪ (P X₂ ∪ Q) = P (X₁∪ X₂) ∪ Q = P X₀ ∪ Q.

And X₀ = A∪ X₁ = P (A∪ X₁) ∪ Q.

Take intersection A on both side of above formula,

LHS = (A∪ X₁) ∩ A = (A ∩ A)∪ (X₁ ∩ A) = A ∪ {} = A

RHS = (P (A∪ X₁) ∪ Q) ∩ A = ((P X₁∪ Q) ∪ P A) ∩ A = (X₁ ∪ P A) ∩ A

= (X₁ ∩ A) ∪ (P A ∩ A) = {} ∪ (P A ∩ A) = P A ∩ A

= P A ∩ {λ} A = (P ∩ {λ}) A

= Ø A (because of not λ ∈ P)

= Ø

That is, A = Ø.

But we defined A as X₀ - X₁ ≠ Ø,

so X₁ ≠ X₂(solution is not unique) is false. □

[노트][Automata] 2. Finite Automata - Accepter

2009-03-09T11:48:00.000+09:00

0. Finite Accepter

주로 언어에 관하여 다룰 때에는 Automata를 Acceptor(받아 들일지 말지)로 본다.

1. Deteministic Finite Accepter
M_D = <Q, Σ, δ, q₀, F>

- Q : A finite set of internal states.

- Σ : (input) alphabet.

- δ : transition functions. Q × Σ → Q

(1) λ에 대해서 정의하지 않음.

하지만 디자인을 편하게 하기 위해 λ transition을 사용하는 경우도 있다.

λ transition으로 디자인 한 M은 어차피 λ transition이 없는 M으로 바꿀 수 있다.
(ex) δ(q₀, s) = q₂

(2) δ^* : Q × Σ^* → Q, δ^*(q, λ) = q and δ^*(q, wa) = δ(δ^*(q, w), a)

- q₀ : A set of initial state(s)

(1) q₀ ∈ Q (여러 개일 경우 q₀ ⊆ Q)

(2) Machine은 이 state에서 시작한다.

(3) initial state가 여러 개일 수도 있다.

F : a set of final states.

(1) final state로 가면 = accepted!

1-1. L(M) = {w ∈ Σ^* : δ^*(q₀, w) ∈ F}

- Accept된 것은 반드시 Final state들 중 하나!

- λ가 accept 되는 경우는 ? initial state = final state

1-2. L이 regular하다.

There exists some DFA, M, such that L = L(M).

2. Non-deterministic Finite Accepter

M_N = <Q, Σ, δ, q₀, F>

- δ : transition functions. Q × (Σ ∪ {λ}) → P(Q) (power set of Q)

어떤 state에서 하나의 input에 대해서 갈 수 있는 state의 수가 여러 개(집합).

(ex) δ(q₀, s) = {q₁, q₂}

또는 δ를 transition relation이라고도 함. δ : ( Q × (Σ ∪ {λ}) ) × Q

* δ가 transition relation이기 때문에, 특정 Q × (Σ ∪ {λ})에 대해 정의되지 않는 것도 있다.

그런 것을 transition function으로 표현한다면... δ(q_i, s) = {} (next state가 없다)

- 다른 것은 DFA와 비슷하다.

- non-deterministic을 사용하는 이유?

deterministic은 잘못 되면 이전 state를 거슬러 올라가야(backtracking)하지만 non-deterministic은 그런 것이 필요 없다(이유는 찾아봐야 겠다). 실제로 non-deterministic을 구현하기는 힘들지만 이것을 deterministic으로 바꾸는 것은 가능하다(즉, 구현 가능!).

2-1. L(M) = {w ∈ Σ^* : δ^*(q₀, w) ∩ F ≠ {}}

- Accept된 것(δ^*의 결과 값은 set)은 반드시 Final state에 포함되어야 한다!

그리고 적어도 하나의 Final state가 있어야 한다!

- trap state는 상관 하지 않음.

3. M_N = <Q_N, Σ, δ_N, {q₀}, F_N> → M_D = <Q_D, Σ, δ_D, q₀, F_D>

3-1. NFA로부터 DFA를 구성.
(a) identify initial state.
(b) Md에서 한 state {qi, qj, qk, ...}를 선택한다.
(c) qi, qj, qk에 대해서 d(qi, a), d(qj, a), d(qk, a), ...를 계산한다.
그 결과가 {ql, qm, qn, ...}이라면 Md에 state {ql, qm, qn, ...}와,
{qi, qj, qk, ...}에서 {ql, qm, qn, ...}로의 edge를 추가한다.
(d) identify final states.

* 3-1은 항상 끝나는가?
우선 P(Q)는 유한한 집합이다.
어떤 state s는 s ∈ P(Q)이고
s1 -> s2 ⊆ P(Q) × P(Q) (upper bound)이다.
따라서 이런 s1 -> s2를 만드는 과정은 유한하다.

3-2. L(M_N) = L(M_D)

(a) L(M_N) ⊆ L(M_D)

Let w ∈ L(M_N) where w = s₁s₂…s_k, s_i ∈Σ, i = 1, ..., k

by definition of L(M_N), there ∃ state sequence such that

s₁ s₂ s₃ s_k

q₀ ==> q_i1 ==> q_i2 ==> … ==> q_f ∈ F_N (Seq 1)

by construction process from M_N to M_D

s₁ s₂ s₃ s_k

{q₀} ==> {…, q_i1, …} ==> {…, q_i2, …} ==> … ==> {…, q_f, …} ∈ F_D (Seq 2)

by definition of L(M_D), w ∈ L(M_D).

so, L(M_N) ⊆ L(M_D) □

(b) L(M_D) ⊆ L(M_N)

단지 (a)를 거꾸로 하면 된다.

[글] 달오름

2009-03-07T00:00:00.000+09:00

달은 이제
검은색 파랑이 일는
어느 바다위에서
소리도 없이 떠 갈뿐이다.
밤의 바다는
도시의 불빛에 잠기어
사람들의 마음속에는
달이란 것은 없어졌다.

오늘 밤도,
달은 조용한 조각배처럼
밤하늘을 유유히 저어 가는데
월광은 빛을 잃어가는 전구처럼
천천히 도시의 가로등에 녹아든다.

가끔은
가로등 하나 없는 시골에서
달오름을 보는것이 좋다.
기나긴 하루의 일부분을
달은 유유히
밤의 바다를 가로지른다.

달빛은 내리고 내려
내 손도 옷도 월광에 젖었나보다.
월광은 살갗에 따스히 스미는
저 달의 눈물 방울인건가.

[글] 회상

2009-03-02T23:17:00.000+09:00

지나간 일은
필름에 투영되는
회색빛 한장의 사진이 되겠지만,
어느 햇빛 잔잔히 내리우는 시간에
바닷가 어느집 창가의 탁자 앞에 앉아서
내려다보이는 이 백색 벽돌의 도시 이 거리에서
밝게 타오르는 하이얀 벽돌만큼이나 생생하게 빛나고
그러다가도 지나가던 구름이 가리우면 그렇게도
점점 어두워가서 회색빛깔이 도는 것이다.
먼곳의 바다에서 불어오는 바람은
해안가 등대를 넘어 이곳으로
소금 냄새에 젖어 부는데
내 마음 한곳에 자리잡은 해안선에
새하얀 모래 사장에 발 내딛는 나의 발과
저 멀고 먼 지평선 너머 갈매기들 날아오면
언젠가, 언젠가 소리쳐 부를 저 바다로
자꾸 자꾸 불어오는 바람에 회답하듯
휘파람이라도 불어보는 것이다.

햇빛은 밝고 밝게 내려서
창가에 앉아 있는 날 비추는데
나 혼자 앉은 이 자리에는 나 말고는
오직 하이얀 햇빛만이 옆자리를 채우고는
저 멀고 먼곳 이 마을 해안가도 비추고 왔을까.
푸르른 따스함이 나를 비추고 그렇게 얼마가 지나
해가 스러져가는 저 하늘, 저 노을지는 노오란 해를 바라보며
바닷가 부두에 정박한 배에서 들려오는 정다운 소리와
내 마음에 고이 간직해둘 사진 한장도 그렇게
노오랗게 물들여 가는 것이다.

내가 앉은 이 창가에
반짝 번지듯 별이 떠오르는 때면
은은하고 밝은 달빛 아래서 마을은 잠을 자는데
저 멀리 해안가의 잠자는 숨소리 잔잔히 바람에 실려
내 안에 열어둔 창문으로 들어오며는
어느새 자장가를 듣는 아기처럼
바다의 소리에 스르르
눈을 감는다.
아, 무슨 꿈을 꾸고 있을까?

[노트][Automata] 1. 도입부

2009-03-02T23:10:00.000+09:00

1. Automata - Formal Lang - Grammar는 서로 뗄 수 없는 관계이다.

왜냐하면 Automata의 Class는 다음과 같은 요소로 정의 되기 때문이다.

- Automata의 model

- 그 model이 accept 할 수 있는 (또는 process 할 수 있는) Language를 specify 한다.

- 그런 language는 grammar를 통해 generate 된다.

2. Automata Classes

(1) Finite Automata Generate 가능한 언어의 범위

(2) Pushdown Automata (1) ⊆ (2) ⊆ (3)

(3) Turing Machine 높은 수준의 것은 낮은 수준의 것을 "포함" 그 이상 가능

- Turing Machine은 가장 Powerful한 것으로 이것으로 풀 수 있다면 컴퓨터가 계산 가능!

- 그래서 프로그래밍 언어들은 주로 (3)인가?

분명 (3)일 수록 표현의 유연성(flexibility)가 높지만 (lang.의 scope가 크다는 것)

parsing 시간(문법, 에러 체크)은 길어진다.

따라서 주로 (2)임.

3. 이산수학에서...

- Relation : R ⊆ A × B

- Function: 특수한 관계(Relation). ∀x, x -> y

- Graph에서 walk : seq. of edges

...

4. Alphabet Σ?

Σ is a finite non-empty set of symbols.

5. string on Σ?

a finite seq. of symbols from Σ.

(ex) Σ = {1, 2}, string on Σ = {1, 2, 11, 12, 21, 22, …}

- |<string>| = Length of string

- string concatenation : w₁w₂

- string set concatenation : (ex) {aa, ba} {12} = {aa12, ba12}

* Empty set concatenation Ø S = S Ø = Ø

- Reverse of string : w^R

- Empty string λ :

|λ| = 0

w λ = λ w = w

w⁰ = λ (w의 0승)

- Σ⁺ = Σ^* - {λ}

- Σ^* = Σ⁰ ∪ Σ¹ ∪ Σ² ∪ Σ³ ∪ … ∪ Σ^∞

6. language on Σ

subset of Σ^*

L ⊆ Σ^*

{λ}도 language!

7. Grammar

G = <V, T, S, P>

- V = Variables (or non-terminal symbols) (set)

- T = Terminal symbols (set)

- S = Start variable (one)

- P = Productions (set) : x -> y where x ∈ (V ∪ T)⁺, y ∈ (V ∪ T)^*

Automata Class간의 주요한 차이:

Production의 형태에 제약이 없을수록 생성가능한 언어의 범위는 늘어난다.

8. Language generated by G = L(G)

L(G) = {w ∈ T^* : S =>^* w}

- 그래서, Grammar가 같다는 건...

L(G) = L(G') <==> L(G) ⊆ L(G') and L(G) ⊇ L(G')

10. Automata : abstract model of digital computer.

[input file]

↓

[control unit] <--> [storage]

↓

[output file]

- Configuration = state of control unit

- Move = transition of one configuration to next configuration.

(* 이 글은 개인적인 정리 용도로 작성된 것입니다.)

[글] The Tales

2009-01-12T01:50:00.000+09:00

종은 울리고 하루는 그렇게 기쁨의 푸름으로 시작되어
언젠가 끝없이 이어졌던 이야기는 여기서 한 도막 끊기고
이제는 낡은 서랍에서 새 종이를 꺼내자.

도시를 시계바늘처럼 해가 가로지르기 시작하는 하루
많은 손짓과 많은 이야기들과 많은 의문들과 많은 웃음들
많고도 많은 눈물들과 많은 고민들과 많은 눈길들과 많은 걸음들

그렇게 종이는 한 자씩 한 단어씩 한 문장씩 채워져 가는 기쁨을
시간은 한 줄에서 다른 줄로 자꾸만 달음질 치고
생각은 출발점에서 꼬리에 꼬리를 물고 늘어지는 발자국.

도시를 시계바늘처럼 해가 하늘을 가로지르는 하루
얼마나 많고 많은 일들이 눈앞에서 피어나는
화원의 꽃들을 바라보고 있는 마음은 설레기만 해.

시간의 광장 한복판에서 나는 무얼 향하고 있을까
이제 막 여정의 시작은 막을 올렸을 뿐인 걸
갈래길 거미줄 같이 얽힌 세계를 나아가겠네.

도시를 시계바늘처럼 해가 땅을 향해 곡선을 그리는 하루
가냘픈 몸을 받아 나아가는 세상은 온갖 불꽃의 향연
언젠가 힘들어져도 화려하게 빛나는 불꽃은 참 아름다워.

한 아이의 걸음은 땅을 딛고 조금씩 나아가 나아가
언젠가 닿을 지평선을 향해 나아가는 기나긴 여행길을
친근한 사람들과 함께해도 좋고 홀로 힘차게 걸어가도 좋아.

그렇게 종이는 한 문장씩 한 단어씩 한 자씩 마무리 되는 서운함을
어느 이야기책이나 끝은 존재하는 것이라지만
생각은 슬픈 이야기 꼬리에 꼬리를 물고 사라지는 발자국.

도시를 시계바늘처럼 해가 땅속으로 저물어가는 하루
노을의 절정과 그 아래 모두가 얼굴 주홍빛으로 물들어가는
종이도 빛바래져가는 시간아래 펜은 마지막으로 달음질친다.

종은 울리고 하루는 그렇게 그리워지는 주황으로 끝나가
언젠가 끝이 없을 것 같았던 이야기는 여기서 한 도막 끊기고
이제는 낡은 서랍에 빛바랜 이야기를 넣어두자.

시간은 계속 흘러간다.
언젠가 빛바랜 종이의 이야기들을 추억할 때까지.

[글] 흐름

2008-12-06T02:08:00.000+09:00

시간은 다르게 지나가지만

시냇가에 소용돌이치는 물결 일 뿐이라고

존재는 말없이 그곳에 서 있지만

사라져 버릴 풍경일 뿐이라고

내가 바라보는 것에

어떤 느낌도 없을 뿐이라고

결국 있지 않은 것일 뿐이라고

말하고 싶다가도

지나감은 초겨울 추운 바람 같이 매섭게 불어오고

데워진 음료의 따뜻한 온기를 느끼며

흐린 겨울 하늘 아래서 버스를 기다리는 시간 속에서

나는 흘러가고 있었다.

[글] 부둣가에서의 저녁 인사

2008-11-30T23:31:00.000+09:00

해가 저물어 가는 부둣가는

새하얀 벽돌도 노오랗게

물들어가고,

너와 그리고 나.

이 부두에 걸터앉아서

지난 이야기 함께 해.

멀리 노을지는 하늘을 나는

저 자유로운 갈매기에게

지금도 먼 곳에 있을 그에게

소식 전해달라고 했지.

해가 저물어 가는 부둣가는

너와 나의 추억도 노오랗게 물들어,

한없이 먼 저 수평선 너머에서

멀리 떨어지는 해를 바라보았네.

노오란 캔버스를 배경으로

범선 한척이 돌아올때 쯤이면

해도 어느새 수평선 너머로 사라지고는 해.

밤의 별빛만이 우리를 비추지만

너와 나의 마음은 달과 함께라고.

쓸쓸하고 외로웠던 마음도

은은한 달빛, 그 아래

서로를 감싸 안는

이곳의 바람을 느끼네.

바람을 느끼네.

쉬고 싶다...

2008-11-29T02:10:00.000+09:00

때가 때인지라 어느정도 예상은 했지만,

작년 이맘 때보다 마음에 여유가 없는것 같네요.

데드라인은 몰려오고, 잠은 오고...

정말 사는게 정확히 짜여진 일정표처럼 갑갑하게 돌아가는 것 같습니다.

그래도 보름 후의 휴식을 위해서 달려야 겠지요.

......

어둠이 있어야 빛이 있고

일이 있어야 휴식이 있다(?)

[글] 어느 잠 안오는 밤에 - 한 밤중

2008-11-26T01:00:00.000+09:00

오롯이 빛나는 별들 사이로

밤, 그는 앉아있습니다.

매일 모든 것이 개벽하는 천공에

지금은 쓸쓸히 혼잔가 봅니다.

아름다운 보석들로

아무리 빛나는 치장을 해도

그는 기쁘지 않은가 봅니다.

무언가 공허한 미소가

스산한 곡선을 띄우고, 그는

다소곳이 앉아만 있습니다.

그는 자꾸만 머언 곳 머언 밤

하늘 어딘가를 바라봅니다.

과거의 시간 속에

유성이 하늘을 가로지르고,

어린아이의 호기심 가득한 눈망울과

먼 하늘 별 찾아 떠도는

순진한 사람들 모습을

더듬어 찾는 모양입니다.

더 없이 깊어지는 시간

그의 눈망울은 암흑보다 깊습니다.

그 깊고 깊은 어딘가에

언젠가 쓸쓸히 이별한 사람이

깨진 전구의 파편처럼 박혔나 봅니다.

하나 둘 씩 모두

영원한 백야를 찾아 떠나고

그는 외로이

무섭도록 슬퍼지는

시간 속에 앉아있습니다.

한, 밤 중에

알 수없이 슬퍼질 때가 있습니다.

남 모를 그의 시린 이슬이

어둠 속에 소리 없이 내리나 봅니다.

창가에 앉아서 그의 얼굴을 바라봅니다.

나의 눈에 솟아오는 그것을 보았는지,

먹구름 거두고는 희미하게 미소짓나봅니다.

한, 밤 중에

눈물 빛 점점이 번진

보름달이 떠 있습니다.