3.Data Representation

이번 단원에서 Huffman Encoding 에 관해 자세히 알아 보도록 하겠습니다.
오늘 DS시간에 수업을 듣는데 허프만 코드에 대해서 나왔는데, 정말 이해가 안되서 DS공부도 할 겸 허프만 코드에 대해 공부해 보도록 하겠습니다.

허프만 코드란 Keyword encoding, Run-Length encoding 과 함께 Text Compression 의 한 종류입니다.
호프만 부호화의 기본 개념은 각 단위 정보를 표현하는 비트 수를 단위 정보들의 출현 빈도를 기본으로 할당한 것인데요.
빈도가 높은 정보는 적은 비트 수를 사용하여 표현하고, 빈도가 낮은 정보는 비트 수를 많이 사용하여 표현해서 전체 데이터의 표현에 필요한 비트의 양을 줄이는 것입니다.
 허프만 부호는 팩스전송이나 JPEG, MPEG 등 화상 정보의 압축 부호화 표준 규격에도 널리 사용됩니다.


허프만 부호화의 동작원리를 알아 봅시다.
① 발생확률이 높은 순서대로 부호를 정렬한후, 최소 발생확률 2개 부호를 선정함
② 최소 발생확률 2개 부호를 합한 값을 구한후, 발생확률이 높은 순서대로 부호 정렬
③ ①과 ②의 과정을 부호 값이 1이 될때 까지 반복함
④ 원래 확률값과 각각의 확률값을 합산하여 나온 결과값에 각각 0과1을 순차적으로 부여함

이 원리에 따라 허프만 트리를 만들어 보면 다음과 같다.


AAAAABBCDDEEEEEF 라는 문자가 있습니다.
이것을 압축하지 않으면 8bit * 17 개 = 136 bit 가 됩니다.
따라서 허프만 부호화 방법으로 압축해 보겠습니다.



첫번째




빈도순으로 정렬을 하고 가장 빈도가 낮은 둘을 더합니다.
그리고 다시 정렬을 하는데 여기서는 2로 나왔기 때문에 제자리에 두고 다시 옆수와 더합니다.



계속해서 정렬과 더하기를 반복합니다.




그럼 마지막으로 다음과 같은 트리가 완성되게 됩니다.



이렇게 해서

A   0
B   110
C   11010
D   1110
E    10
F    11111

으로 허프만 테이블을 만들 수 있습니다.

이것으로 위의 문자를 압축하여
0000001101101101011101110101010101011111 과 같이 나타낼 수 있습니다.
136bit 보다 훨씬 압축된게 보이시죠!?



이렇게 해서 허프만 부호화에 대해 알아보았습니다.

4.Gates and Circuits

오늘은 정말 제 때에 과제를 내네요..ㅠㅠ
죄송해요 힝

오늘은 시험이 얼마 남지 않아 시험 공부도 할 겸 4단원에 adders 를 자세히 공부해 보도록 하겠습니다.


4단원은 Gate 와 Circuits 에 관해서 배우는데 전 컴맹인 관계로 Gate 와 Circuits 의 뜻부터 확실히 알아봅시다

Circuit 은  회로로 Gate로 구성되어 있습니다.
Gate는 논리 게이트라 하여 기본이 되는 논리 기능을 실현하는 전자 회로 입니다.
Gate의 종류로는 NOT, AND,OR,XOR,NAND 등이 있습니다.

이번 단원은 전자회로와 컴퓨터에 관해 배웠던 시간이었습니다.


그럼 이제부터 제가 자세히 공부하기로 한 Adder 에 대해 공부해 봅시다.

Adder 란 우리말로 가산기라는 것인데 두개 이상의 수를 입력하여 이들의 합을 출력하는 논리 회로 또는 장치 입니다.
종류로는 Full Adder 와 Half Adder 가 있습니다.

그럼 우선 Half Adder 란 무엇일까요?

반가산기란 컴퓨터 내에서 2진 숫자(비트)를 덧셈하기 위해 사용되는 논리 회로의 하나입니다. 덧셈해야 할 2개의 비트를 받아서 2개의 출력, 즉 합 (Sum) 과 자리 올림비트 (Carry) 를 생성합니다. 반가산기는 자리 올림 비트를 출력할 수는 있지만 앞의 덧셈으로부터 자리 올림 비트를 받을 수는 없습니다. 

이 회로는 반가산기 회로입니다.

A와 B 를 입력하여 S(sum)과 C(carry)를 출력해 냅니다.

그럼 반가산기의 진리표를 봅시다.

그럼 전가산기에 대해 알아봅시다.

반가산기는 2개의 값을 더하는 것이었는데 3개 이상의 값을 더야해 할 때 어떻게 해야할까요. 그 때 쓰는 것이 전가산기입니다.

전가산기는 3개의 입력, 즉 덧셈해야 할 2개의 비트와 앞의 덧셈으로부터 자리 올림 비트를 덧셈하는 것이다. 컴퓨터는 전가산기를 반가산기라고 하는 2개의 입력 회로와 조합시켜, 동시에 4개 비트 또는 그 이상의 덧셈을 할 수 있습니다.

위의 그림은 전가산기의 회로인데 두개의 반가산기와 OR 게이트로 이루어져 있습니다.
A와 B 는 입력값이고 Cin 은 입력되는 자리 올림수 이고 Cout 은 출력되는 자리올림수 입니다.

위와 같은 회로를 여러 개 붙이면 3개 이상의 수를 더할 수 있는 회로가 만들어 질 수 있겠죠



그럼 전가산기의 진리표를 보도록 합시다.

      A   B   C-in   Sum   C-out
      0    0     0       0         0
      0    0     1       1         0
      0    1     0       1         0
      0    1     1       0         1
      1    0     0       1         0
      1    0     1       0         1
      1    1     0       0         1
      1    1     1       1         1




이와 같이 가산기에 대해 알아 보았습니다.
뿌듯한 이 맘 !! 히힛
오늘은 과제를 제 때 내어서 기분이 좋습니다.

지난 과제들을 조금 늦게 올립니다. 그래도 과제한거 꼭 봐주세요 선생님 ㅜㅜ

2.Binary Values and Number Systems

이번 단원은 수요일에 공강 시간이 너무 긴 바람에 선아와 민주의 수업이 끝나기를 기다리며
국제관 2층에 앉아서 공부를 했다!!
그래서 과제를 조금은 쉽게 할 수 있을 듯 해요. 히힛
뿌듯하네요 헤헤

이번 단원에서는 2진수, 8진수, 16진수 같은 여러 진수에 관해서 배우고 각 진수들을 다른 진수들로 변환시키는 방법들에 대해 배웠습니다.

그래서 이번 단원에서는 수요일 공강 시간에 열심히 공부한 컴퓨터 수의 체계에 대해 더 자세히 공부해 보도록 하겠습니다!


컴퓨터에서는 실제로 2진수가 사용됩니다. 그러나 이번 단원에서는 2진수 뿐만 아니라 8진수, 16진수를 배우는데요.  그 이유는 8과 16이 2의 제곱수 중 하나이기 때문에 2, 8, 16 진수 끼리 서로 변환되기 편하기 때문입니다.

2진법은 컴퓨터의 ON OFF 를 사람이 인식하기 쉽게 0과 1의 형태로 표시한 방법입니다.
ON과 OFF 신호의 다양한 조합으로 각 H/W장치는 통신을 하는데 각 신호의 조합에 각 명령을 대입하여 CPU내에 약속을 저장한 것을 내부명령어라고 합니다.
이 각 신호를 BIT(데디터 표현의 최소 단위) 라고 합니다.
다양한 신호를 만들기 위해 최초로 7개의 신호를 묶어서 약속을 만들게 된 것이 ASCII코드(7bit)입니다. (ASCII코드는 3단원에서 자세히 배우네요~)
8bit 체계로 발전이 되고 언어 상징 등을 8bit 조합으로 표현이 됩니다.
8bit = 1Byte

[컴퓨터에서 사용하는 저장단위]
bit : 최소
byte : 정보 기본 단위 (8 bit = 2의 3승)
1KB = 1 kilo byte = 1024 = 2의 10승
1MB = 1024 KB = 1024 * 1024 Byte
1GB = 1024 MB
1TB = 1024 GB

출처 :  http://blog.naver.com/bluesyj00?Redirect=Log&logNo=100087591633

2진수는 0, 1 의 두 개의 수를 사용하여 나타낸 수이고
8진수는 0~7 의 8 개의 수를 사용한 수이고
16진수는 0~9 의 10개의 수와 A~F까지의 알파벳을 사용하여 나타낸 수입니다.


그럼 보수를 이용하여 2진수의 뺄셈을 하는 법을 알아보도록 합시다.

컴퓨터에는 마이너스라는 개념이 없습니다.
그래서 보수를 사용하여 뺄셈을 하게 되는데요.

그럼 예를 들어보아요

10진수 1은 2진수로 00000001 입니다.
그럼 10진수 -1은 이진수로 어떻게 표현할까요??
음수일때 사인비트는 1이고 양수일 때 사인비트 0이므로  쉽게 생각하면 10000001 이라고 생각하기 쉽습니다.
그러나 1+(-1) = 0 이므로 두이진수를 더해도 0이 나와야 하지만 계산해 보면 그렇지 않습니다.
실제로 10진수 -1의 2진수 값은 1111111 입니다.

    00000001
  +11111111
                         
  100000000

이고 맨 앞의 1은 8비트이므로 잘라버려 두 이진수의 값이 0임을 알 수 있습니다.


실제로 컴퓨터는 뺄셈을 할 수 없습니다.
위의 1 + (-1) 과 같은 방법으로 뺄셈을 하는 것 입니다.

보수는 이 때문에 만들어진 개념인데요
1을 -1로 바꾼 것처럼 수를 음수로 바꾸는 것이 보수입니다.

보수로 바꾸는 방법은 간단합니다.

첫째,  수를 2진법으로 고칩니다.
둘째,  2진법으로 표현된 수가 1010 이라면 0101로 바꾸는 것처럼 0은 1로, 1은 0으로 바꿉니다.
셋째,  바꾸어진 수에 1을 더합니다.

예를 들어 10진수 1의 보수를 알아봅시다.

첫번째! 10진수 1을 2진수로 바꾸면 00000001 입니다.
두번째! 0과 1을 변환시키면 11111110 이 됩니다.
세번째! 11111110 에 1을 더하면 111111111 이 됩니다.

참 쉽네요!! 히힛

두 수 더하니 00000001 + 11111111 = 100000000  이네요 제일 앞자리의 1은 자리수가 초과되었으므로 없어지니 00000000 이 됬네요!!