4. Bits and Boolean Algebra

Bit

• Binary + Digit 로부터 만들어진 용어.

  • Binary란 둘 중 하나의 값을 가지는 것. : Bit is binary
  • Digit은 10진수를 표현하는 10가지 기호 0~9(엄밀히는 10개 중에 하나의 값을 가지는 것)

• Information을 표현하는 기본단위
• Bit는 흔히 0과 1 중에 하나의 값을 가지지만, 0과 1의 의미는 다를 수 있음.

1. Information을 표현하는 기본단위이기 때문.
   보다 큰 비트에 해당하는 information이 정보량이 많다고 해석 가능.
2. 처리가능한 bit가 큰 컴퓨터일 수록 처리가능한 정보량이 큼.
3. 처리가능하다는 얘기는 표현할(represent) 수 있다는 의미이기도 함.

MSB and LSB

• MSB : Most Significant Bit
• LSB : Least Significant Bit
• 2진수 표기 시 가장 왼쪽에 있는 bit가 MSB, 가장 오른쪽에 있는 bit가 LSB.
• positive integer만 표시하는 unsigned 경우, MSB는 가장 큰 자리수가 됨.
• negative integer를 고려하는 경우, MSB는 positive인지 negative인지 나타내는 sign임. 0은 positive, 1은 negative.

Bit 관련 단위

정량적인 단위

bit

• information의 최소 단위

nibble

• 4bit에 해당하는 단위. 16진수와 묶여서 사용.

byte

• 8bit에 해당. 주로 사용되는 단위 중에서는 가장 작은 단위.

half word

• 16bit에 해당. 초기 컴퓨터가 16bit machine일 때 word 였지만 컴퓨터가 발전함에 따라 half라는 용어를 붙여 구분함.

long word(full word)

• 32bit에 해당. 컴퓨터가 32bit machine일 때의 word. 컴퓨터가 발전함에 따라 long이라는 prefix가 붙어 구분.
• 일반적으로 word라 하면 long word를 얘기하기도 함.

double word

• 64bit에 해당. 현재 컴퓨터는 64bit machine으로 원래 word 정의에 따르면 현재는 double word가 word임.
• 하지만 하위호환성 등에 대한 고려로 word라고 하지 않고 double word라고 지칭하는 게 일반적임.

논리적인 단위

field

• 파일 구성의 최소 단위
• 주로 DB의 column을 의미.

record

• 하나 이상의 관련 field가 모여 구성
• 주로 DB의 row를 의미.

block

• 하나 이상의 관련 record가 모여 구성
• 최소 I/O 단위로 많이 사용(block 단위로 입출력이 이루어지는 device가 보편화되었기 때문)
• 물리적 record라고 불림.

file

• 프로그램 구성 기본 단위
• storage에서 사람이 인식하는 기본 저장 단위

DB(DataBase)

• 여러 개의 관련된 파일의 집합
• 일반적으로 RDBMS 같은 database 시스템을 지칭하는데 사용
• 정보량을 의미하는데에는 잘 사용되지 않음.

Boolean Algebra

• Logic을 다루는 algebra
• True, False를 수학적인 영역으로 포함시켜 참과 거짓을 1,0에 대입하고 AND , OR , NOT 등의 logical operation을 사용하여 논리적 동장을 대수적으로 처리
• bit들을 이용한 logic operation에 대한 규칙 정의

Pre-requirements

1. Operation

• empty set이 아닌 set에서 2개의 element를 이용하여 제 3의 element를 만드는 것.

2. logical operation

• True, False 두가지 element만 존재하는 set(엄밀하게는 ring으로 불림)에서의 operation.

3. algebra

• set of rules for operating on numbers
• 어떤 set과 해당 set에 속한 element들을 이용하도록 정의된 operation들에 대한 규칙을 연구하는 학문

Rules

• Associative Rule : ($a$ $AND$ $b$) $AND$ $c$ = $a$ $AND$ ($b$ $AND$ $c$)
• Commutative Rule : $a$ $AND$ $b$ = $b$ $AND$ $a$
• Distributive Rule : $a$ $AND$ ($b$ $AND$ $c$) = ($a$ $AND$ $b$) $AND$ ($a$ $AND$ $c$)

Basis Operations and Composite Operations

• NOT

• AND

• OR

  ---

• composite operation은 basic operation들의 조합으로 만들어짐.

• NAND

• NOR

• XOR : eXclusive OR, print 1 if inputs are not same.
  

De Morgan's Law

• logic operation에서 'OR'과 'NOT'으로 표현된 expression을 'AND', 'NOT'으로 표현된 expression으로 바꿀 수 있음을 보여줌.

1. 명제(논리학)를 이용한 표현
   $$
   ￢(p ∨ q) = ￢p ∧ ￢q$$
2. Set(집합)을 이용한 표현
   $$
   (A∪B)^C = A^C ∩ B^C$$
3. 디지털 회로 등에서의 표현
   $$
   \overline{(A+B)} = \overline{A} \cdot \overline{B}$$
   $$
   \overline{(A\cdot B)} = \overline{A} + \overline{B}$$

• De Morgan's Law를 통해 negative logic을 사용할 수 있음.

Prefixs for SI Units and for bits(IEC)

Prefixs for SI Units

• 인간을 위한 것으로 base를 10으로 사용

  Prefix for bit(IEC standard prefix)

  

• bit의 경우 base-2 system이기 때문에 실제로는 2의 제곱으로 표현

• KiB 는 kibi-bytes를 의미하고, Mib는 Mebi-bits를 의미

---

Reference:

1) https://dsaint31.me/mkdocs_site/CE
2) https://www.researchgate.net/figure/Summary-of-the-common-Boolean-logic-gates-with-symbols-and-truth-tables_fig3_291418819
3) https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=cni1577&logNo=221622302364
4) https://www.amountofsubstance.com/si-unit-symbol-prefixes
5) https://www.podfeet.com/blog/2019/04/8-bits-to-byte/