스니스니 닷넷

우리가 어떤 사이인지,
평소 어떻게 노는지.
한 눈에 알 수 있다. ( '')




(방명록이 그러하듯, 밑에서 부터 읽어야 한다.)

예전에, 아베다에서 받아온 작은 대나무.
아베다 초록색 화장품 병에 꽂혀있었다.
어느 날 보니, 대나무가 조금 자라, 굵어져서 병목에 꽉 끼어있었다.
나중에 더 자라면 문제가 될 것 같아, 그제서야 꺼내주려니,
뿌리쪽이 약간 더 굵어서 안빠지는 거다.
그래도, 지금 빼는게 나을 것 같아서,

조금만 참아. 조금만 참아. 하면서 삐죽빼죽 빼 주었다.
그리곤 지금 큰 화병에 물 가득 넣어서 자리를 마련해줬다.

어제는, 더 마음 아픈 일.
지난 학기에, 할머니께서, 아토피에 좋다면서
아주 작은 알로애를 가져와서 집 화분에 심어주셨다.

그 때는 별 애착이 없었다.
방학 중에 2주 부산에 내려가 있다 올라왔을 때,
난 말라죽었을 줄 알았는데, 잘 살아있었다.

미안한 마음에 그 때 부터 꼬박꼬박 물을 잘 주니,
아주 싱싱해졌다.

주말에 잠시 부산 내려갔다 올라오면,
걔네들 물 부터 줬는데...

어제는 내가 아토피가 심해져서,
걔네들을 잘랐다.

왜그렇게 작은지, 하나가지곤 안될 것 같아서,
4 잎이나 잘랐다.
어찌나 미안하던지...

어제 내가 편한 쪽만 잘랐더니, 나를 보고 있는 쪽 잎이 거의 없다.
쟤네들 다시 언제 자라지...

내가 섭취하는 야채는 참 만만치 않은데...
내가 기른 알로애는 잘라서 바를려니... 이상했다..

아토피를 심하게 앓고 난 뒤에,
눈물이 더 많아진 것 같다. 쳇.

1. Logic Functions and Switches
⊙ Axioms of Boolean Algebra
1. B contains at least two elements, a, b, such that a≠b
2. Closure a,b in B,
(i) a + b in B
(ii) a •b in B
3. Commutative Laws: a,b in B,
(i) a + b = b + a
(ii) a •b = b •a
4. Associative Laws: a,b in B,
(i) (a + b) + c = a + (b + c) = a + b + c
(ii) (a • b) • c = a • (b • c) = a • b • c
5. Identities: 0, 1 in B
(i) a + 0 = a
(ii) a •1 = a
6. Distributive Laws:
(i) a + (b •c) = (a + b) •(a + c)
(ii) a •(b + c) = a • b + a •c
7. Complement:
(i) a + a' = 1
(ii) a •a' = 0

⊙ Thm : truth tabel로 표현되는 Boolean function은 Boolean Algebra로 표현될 수 있다.
⊙ NAND, NOR gate는 AND, OR 보다 더 효과적이라, 많이 사용되고, 어떤 Boolean expression도 NAND, NOR, NOT 만으로 구현될 수 있다. 사실, NOT 역시, NAND나 NOR의 input을 묶어 같이 넣어주면 구현가능하다.
⊙ Literal : Boolean expression 에서 한 문자는 하나의 literal 이며, 이는 나중에 wire 개수에 해당한다. literal이 적을 수록 wire가 적게 필요해서 좋다.
(예) Z = AB'C + A'B + A'BC' + B'C : 3 variables, 10 literals

⊙ XOR, XNOR. (내가 초반에 젤 헷갈렸던 것.)
XOR : X or Y but not both ("inequality", "difference")
XNOR : X and Y are the same ("equality", "coincidence")



2. Gate Logic
⊙ Duality : AND ↔ OR, 0s ↔ 1s, literal은 그대로.
► 참이 expression은, 그 dual도 참이다.
(앞의 Boolean Algebra의 Axiom에서 빠진 내용만 보자.)
Simplification Theorems:
9. X •Y + X •Y' = X 9D. (X + Y) • (X + Y') = X
10. X + X •Y = X 10D. X •(X + Y) = X
11. (X + Y') •Y = X •Y 11D. (X •Y') + Y = X + Y
DeMorgan's Law: AND ≡ NOR, OR ≡ NAND, AND/OR ≡ OR/AND
12. (X + Y + Z + ...)' = X' •Y' •Z' •... 12D. (X •Y •Z •...) ' = X' + Y' + Z' + ...
13. {F(X1,X2,...,Xn,0,1,+, •}' = {F(X1',X2',...,Xn',1,0, •,+)}
Duality:
14. (X + Y + Z + ...) = X •Y •Z •... 14D. (X •Y •Z •...) = X + Y + Z + ...
15. {F(X1,X2,...,Xn,0,1,+, •} = {F(X1,X2,...,Xn,1,0, •,+)}
Theorems for Multiplying and Factoring:
16. (X + Y) •(X' + Z) = X •Z + X' •Y
16D. X •Y + X' •Z = (X + Z) •(X' + Y)
Consensus Theorem:
17. (X •Y) + (Y •Z) + (X' •Z) = X •Y + X' •Z
17D. (X + Y) •(Y + Z) •(X' + Z) = (X + Y) •(X' + Z)


⊙ Truth table은 Boolean function의 unique signature이다. 따라서, expression은 여러가지일지라도, truth table은 하나이다.
► Canonical form : Boolean expression의 표준 형식.
(truth table을 그대로 boolean function으로 나타내면 된다.)
► Sum of Product form = minterm (1:A, 0:A')
F = [F 값이 1인 것들의 product를 sum]
F' = [F 값이 0인 것들의 product를 sum]
► Product of Sum = maxterm (1:A', 0:A)
F = [F 값이 0인 것들의 sum을 product]
F' = [F 값이 1인 것들의 sum을 product]




3. Two-Level Simplification
⊙ 여기에서의 핵심은, The Uniting Theorem 이다.
A(B'+B) = A
① Boolean Cubes : 4 demensions 이상은 그리기 힘들다.
② Karnaugh Map Method : ~6 demensions
③ CAD Tools : 6 demensions 이상.
(Quine-McCluskey Method)
④ Esspresso Method ( skip )

몇 가지 1장에 있던 내용을 정리해 본다.

◎ Combinational logic : no feedback among inputs and outputs
Sequential logic : inputs and outputs overlap

◎ Synchronous systems : clock에 의해서 signal이 변한다.
Asysnchronous systems : 아무 때나 입력이 주어지면 state 변한다.

◎ Multiple representation of a digital desing
① Switches

② Truth tables
③ Boolean Algebra
④ Gates

⑤ Waveforms
⑥ Blocks

⑦ Behaviors : 이건 안배운거고, 나머진 다 알지? ( '')

제일 심했던 오른 쪽 뺨.

요즘 계속 조짐이 보이더니,
진짜.... 안좋아졌다.

겁난다.

[시작 전에]
더 적은 components와 wires로 Boolean functions를 구현할 수 있는 좀 더 customizable 하고 복잡한 building block들을 배운다.
▪ Design with structured circuit implementation styles based on programmable array logic and memories.
PALs/PLAs, ROMs : general-purpose digital building blocks 만드는 데 유용하다.
(특정 함수를 구현하는데 customized되고, 더 적은 공간을 차지한다.)
PAL : programmable array logic
PLA : programmable logic array

▪ Design with logic building blocks that are different from traditional logic gates.
Switch Logic
Multiplexers/Selecters and Decoders : 종종 switch 처럼 truth table이나 logic gate보다 Boolean function을 보여주기 더 쉽다.
Tri-State Gates/Open Collector Gates : output이 항상 0이나 1이 아닌 logic들.

▪ Combinational Logic Design Problems
Seven Segment Display Decoder
Process Line Controller
Logical Function Unit
Barrel Shifter


1. Programmable Arrays of Logic Gates
(1) PALs and PLAs
Pre-fabricated building block of many AND/OR gates (or NOR, NAND) "Personalized" by making or breaking connectins among the gates
(*) Product term 을 공유하는 것이라 보면 된다.
F0 = A + B' C'
F1 = A C' + A B
F2 = B' C' + A B
F3 = B' C + A
⇒ A, B'C', AC', AB, B'C' 이렇게 5개의 term만 있으면 된다.




(2) PAL PLA 차이점
⊙ PLA : generalized topologies in AND and OR planes.
즉, AND, OR subarray가 디자이너가 원하는대로 personalized 될 수 있다.
((장점)) product term들 공유

⊙ PAL : implemented by Monolithic Memories.
AND array는 programmable 하지만, product term들간의 연결과 OR gate는 고정되어있다. OR gate로 들어가는 product term input은 2,4,8,16개로 제한되어있다.
((장점)) pre-defined hardwired connection을 사용하기 때문에 빠르다.

(3) Design Examples
◎ BCD-to-Gray-Code Converter
Gray-code : 1 bit 씩만 다른 코드들.
shared product term 없으므로, PAL이 적당하다!


◎ Two-bit Magnitude Comparator
shzred product term 2개 -> PLA 사용.

[시작 전에 ]
In general, multi-level implementations are more gate efficient than two-level implementations but have worse propagation delay.
Factored form 으로 바꾸면, 훨씬 적은 수의 gate와 wire로 회로를 구성할 수 있다. 그러나, level 이 증가하므로, 그에 따른 delay가 증가한다. (어디에나 있는, trade-off!)


1. Multi-level logic을 NAND/NAND 와 NOR/NOR로 바꿔보자.
DeMorgan's Law와 Pushing Bubbles 이용.
(1) DeMortan's Law
(A + B)' = A'B' -> A + B = (A'B')'
(AB)' = A'+B' -> AB = (A'+B')'



여기에서도 알 수 있듯이,
AND/OR 즉, Sum of Product 는 NAND/NAND 로,
OR/AND, Product of Sum 은 NOR/NOR 로 바꾸는 것이 쉽다.
왜냐하면, 이런 변환에서는 두 gate 사이에 buuble이 쑝쑝 들어가기만 하기 때문이다. 그러나, SOP를 NOR/NOR로, POS를 NAND/NAND로 바꾸려면, input 단자와 output 단자에도 bubble을 달아줘야하기 때문이다.

(*) 위의 그림은 two-level 이다. multi-level 에서는 다음을 주의한다.
1. Any internal signal wires that undergo an odd number of inversions must have an additional inverter inserted in the path.
2. NAND-only network로 변환하려면, odd levels에 AND gate를, even levels에 OR gate를 둔다.
3. NOR-only netwrok로 변환하려면, odd levels에 OR gate를, even levels에 AND gate를 둔다.

2. AND-OR-Invert Blok (AOI)
AOI function : AND, OR, Invert의 세 stage. 하나의 circuit block 으로 "packaged"된 multiple gate 이다. (OAI : OR-AND-Invert)

여기에서 stack은 AND의 개수.
AOI 의 장점은, 이 것을 하나의 gate로 count한다는 것!
Even if the use of the AOI blocks represents no savings in circuit area, the transition away from discrete logic offers a considerable advantage in reducing wiring complexity.


3. Multi-level Optimization (called synthesis)
(1) Factor out common sublogic (reduce fan-in, increase gate levels), subject to timing constraints
(2) Map factored form onto library of gates
(3) Minimize number of literals (correlates with number of wires)

(*) factored form : SOP의 연속이다. 즉, AND/OR/AND/OR/....
two-level expression들의 연속이라고도 할 수 있다.


① Decomposition
F = ABC + ABD + A'C'D' + B'C'D' (12 literals)
⇒ F = XY + X'Y' (4 literals)
X = AB
Y = C + D

② Extraction
F = (A+B)CD + E
G = (A+B)E'
H = CDE
⇒ F = XY + E
G = XE'
H = YE
X = A+B
Y = CD (A+B, CD 는 primary divisor 이다.- kernel, cube)

③ Factoring
F = AC + AC + BC + BD + E
⇒F = (A+B)(C+D) +E

④ Substitution
F = A + BC
G = A + B
⇒F = G(A+C)

⑤ Collapsing
F = G(A+C)
= (A+B)(A+C)
= AA + AC + AB + BC
= A + BC


4. Time Response in Combinational Networks
: 좋게 사용될 수도 있고, glitch처럼 부정확한 회로 오작동 유발도 한다.

Gate delay : input -> output 딜레이 시간
Rise time : output 이 low->high voltage로 변화는 시간
Fall time : output 이 high->low voltage로 변하는 시간

glitch : transient(일시적인) output changes.
-> A logic circuit is said to have a hazard if it has the potential for these glitches.

(1) Hazards/Glitches and How to Avoid Them
방법 : 신호가 stable할 때 까지 기다리기. 절~~~대 asynchronous input 사용은 안됨. hazard-free 회로 만들기

(2) Hazard의 종류
Static hazard : 2-level 회로에서. 한 번 glitch
Dynamic hazard : multi-level 회로에서. 두 번 이상 glitch

(3) Hazard free network 만들기 (two-level 에서)
When the initial and final inputs are covered by the sameprime implicant, no glitch is possible. But when the input change spans prime implicants, a glitch can happen.
A strategy for eliminating the hazard is to add redundant prime implicants to guarantee that all single-bit input changes are covered by one such implicant.
① static 1-hazard 제거
F의 SOP (1's 묶기. 1을 A로) 만들어서 여분의 implicant 추가.

② static 0-hazard 제거
F의 POS (0's 묶기. 0을 A로) 만들어서 여분의 implicant 추가.
⇒ ② 를 SOP로 바꾸면 ①과 같은 식이 나온다. 따라서, shorcut으로 다음과 같은 방법을 사용할 수 있다.
static 1-hazard free expression의 complement를 만들어서, 그것이 K-map에서 0's 를 다 cover 하는지 확인한다. (필요하면 add)

(4) Multilevel Networks에서 Static Hazard free 만들기
: transient output function (multi -> 2-level)으로 mapping 한다. 여기에서는 X와 X'는 독립적 변수이다. (XX'=0, X+X'=1 사용 못한다.) XX'는 static 0-hazards를, X+X'는 static 1-hazards를 일으킨다. 따라서, static 1-hazards를 제거할 때는, XX'를 고려할 필요가 없고, static 0-hazards를 제거할 때는 X+X'를 고려할 필요가 없다.
(예) F = ABC + (A+D)(A'+C')
F1 = ABC + AA' + AC' + A'C + C'D (transient output function)
F2 = AC' + A'D + C'D + AB + BD ( AA'는 1-hazards랑 무관, AB가 ABC cover)
F' = (ABC + (A+C)(A'+C'))'
= A'D' + AB'C
F3 = (A+D)(A'+B+C')(B+C'+D) // F'에 B'CD'추가.

F3을 SOP로 바꾸면 F2가 나온다. 따라서, 둘 다 static 0-과 1-hazards에 free 하다.

(5) 결론, static-hazard-free circuits 디자인 방법!
: transient output function이 K-map 에서 인접한 모든 1을 커버하는 term을 가지게 하고, term이 A와 A'를 모두 가질 수는 없게 한다. 즉, AA' 이런 term 은 안된다.

요즘은 계속 고민과 갈등의 연속.

컴퓨터를 계속 해야하는가?

알고리즘? 수업시간엔 다 몰라도, 책 읽으면서 어려워도, 재미는 있다.
DB? 아직은 쉽다. ERD 그리는 것도 쏠쏠..
디논.. 음... 처음 해보는 전공 재수강... 열라 쉽다. -.-
(사실 3년 전에 들은거라. 다 알지는 못하겠는데, 다 너무 당연한 이야기 같다. 요즘 디논과 교양 C++을 들으면서 지식인을 이해하게 된다.)

지금까지 들었던 전공들도 다, 공부할 때는 괜찮았다.

요즘 청강중인 시스템 프로그래밍도,
숙제의 압박 없이 차교수님만 바라보고 있자니,
얼마나 재밌는지 모른다. 흐흐흐...

그런데!
모르겠다.
아무 생각 없이, 지금처럼 그래왔던 것 처럼,
아무 생각 없이 공부만 하면 할 수 있을 것도 같다.

그런데, 나한테 맞지 않는 것 같다는 생각이 든다.
가끔, 내 주위에 너무너무 잘하는 사람들이 많아서
그렇게 느끼는 것 같기도 하다-는 생각도 해본다.
다른 과사람들하고 같이 있으면,
적어도 내가 못한다- 는 생각은 들지 않으므로.

그런 생각을 하다가도.....
그~~그렇게 잘하지도 않는데, 왜 계속 해야하냐는 생각.
요즘 부쩍 관심이 생긴 음식-에 대한 흥미.
(음식 조절 안하면 아토피가 바로바로... -.- )

유전자 쪽도 재미있는 것 같고.
컴터 베이스로 걍 바이오 인포매틱스 쪽을 해볼까 싶기도 하고.

아~~~주 여러가지 생각... 을 하면서
공부를 너무 소홀히 했다.

금요일이 알고리즘 시험인데,
오늘 범위 체크를 하면서,
앗! 이런 것도 배웠네! 하는 부분까지 나왔다. -.-

이런 적은 없었는데.... -.-

오늘은 낮잠도 잘~ 주무시고... ( '')

아아아아... 답 없는 인간... -.-

Disjoint set 에서 중요한 operation 은,
1. union : O(1)
2. find : (n)
이다.

union 은 주어진 두 집합의 모든 원소가 동일한 멤버쉽을 갖게 만드는 연산

find 는 집합의 구성가능 원소가 모두 알려져 있는 상태에서, 특정한 원소가 특정한 집합의 멤버쉽을 갖고 있느냐를 알아내는 연산

(출처 : 엠에센을 통한 1:1 지식 검색 서비스 =33 )

어제 오늘 몸이 안좋았다.

추석 당일 오전에, 딱히 많이 먹은 거 같지는 않은데,
(딱히.. -.- )
산소 가는 길에 머리가 아프더니.
갔다 와서는 계속 속도 안좋고 머리가 깨질 듯이 아팠다.
오후에 계속 자고,
고등학교 친구들의 약속 시간까지 자다가
독촉을 받고 머리 아픈 채로 나가서
이야기 하고 놀다가
집에 들어가니,

어지럽고, 숨도 못 쉴 것 같고. -ㅇ-

열 손가락을 다 따고, (이거 참 신기.)
세라젬 한 판 하고 겨우 잠이 들었는데

오늘도 계속 머리가 아프고,
소화도 잘 안되고.

서울 집에 도착해서,
배가 고프지만, 저녁을 안먹기로 결심!

과일만 (신이나서) 세척기에 씻어서 먹다가...
부산에서 들고 온 김치가 생각나서
꺼내어 한 쪽 먹었더니 -ㅇ-

배 깎아서, 배 한 입, 김치 한 조각.... 으흐흐...
어찌나 맛나던지.
바로 이맛이야~~ -ㅇ-
(속도 좀 편해지는 것 같다.
외국 사람들은 먹고 쓰러질 만큼 김치를 먹고,
나는 속이 편해지다니. 나는 역시 한국인. 크흐..)

나는 엄마처럼 맛난 김치를 담글 수 있을까?