[TIL] 2019.04.03 - Computer Science

NAND 연산자와 NOR 연산자

NAND 는 AND 연산에 NOT을 붙인 것과 같고, NOR 는 OR 연산에 NOT을 붙인 것과 같다.

일단 자주 사용할 or, and 를 함수로 만들어 놓겠다.

const boolToInt = (b) => b ? 1 : 0
function and (a, b) {
    return boolToInt(a && b)
}

function or (a, b) {
    return boolToInt(a || b)
}

• NAND

function nand (a, b) {
    return boolToInt(!and(a, b))
}

• NOR

function nor(a, b) {
    return boolToInt(!or(a, b))
}

XOR 연산자와 XNOR 연산자

XOR(기호: ⊕, 논리식: A`B + AB`) 는 두 입력이 반대 논리여야만 참을 반환하고, XNOR(기호: ⊙, 논리식: AB + A`B`)은 XOR에 NOT을 붙인것과 같다.

XOR 진리표

A	B	F
0	0	0
0	1	1
1	0	1
1	1	0

XOR, XNOR 구현

function xor(a, b) {
    return  or(and(!a, b),and(a,!b))
}

function xnor(a, b) {
    return boolToInt(!xor(a,b))
}

불대수

컴공 시간에 배웠지만 전부 잊어버리것 같아 다시 정리해 보겠다.

불대수 기본 공식

1. 일반 법칙

A + A = A
AA = A
A + A` = 1
AA` = 0
1 + A = 1
1A = A
0A = 0
(A`)` = A

2. 교환 법칙

A + B = B + A

3. 분배 법칙

A + A`B  = (A + A`)(A + B)
         = 1(A + B)
         = A + B

4. 드모르간의 법칙

(A + B)` = A`B`
(AB)` = A`+ B`

카르노맵

단순화를 하기 위한 방법으로 최소항으로 공식을 표현할 수 있게 해준다.

카르노맵의 간소화 규칙은

1. 이웃을 2의 지수 승으로 묶는다. (2개, 4개, 8개)
2. 바로 이웃한 항끼리 묶는다.
3. 최대한 크게 사각형 형태로 묶는다.
4. 3변수 이상 카르노 맵을 그릴때는 00, 01, 11, 10 순서로 기입한다.
   이런 진리표가 주어 졌을때

A	B	F
0	0	1
0	1	1
1	0	0
1	1	0

카르노 맵을 이용하면 다음과 같다.

이제 인접한 이웃의 값을 사각형으로 묶어주면

따라서 1로 되어 있고 묶인 항의 A와 B를 이용해서 식을 사용하면

A`B` + A`B
= A`(B`+ B)
= A`1
= A`

따라서 A` 의 식을 얻을 수 있다.

이진 덧셈

• 반가산기(Half Adder) : 1bit짜리 2진수 두 개를 덧셈한 값으로 합과 자리올림수를 구하는 논리회로
• 전가산기(Full Adder) : 1bit짜리 2진수 두 개와 뒷자리에서 올라온 자리올림수를 포함한 1bit 짜리 2진수 1개를 더하여 합과 자리올림수를 구하는 논리회로

반가산기 진리표

A 와 B를 입력했을때 합(S) 와 자리올림수(C)

A	B	S	C
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

전가산기 진리표

X 와 Y, 전단계 자리올림수 CI 입력했을때 합(S) 와 자리올림수(CO)

X	Y	CI	S	CO
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

반가산기, 전가산기 구현

반가산기의 합은 XOR 이고 자리올림수는 AND 이다.

• 반가산기

function halfAdder(a, b) {
    return [and(a, b), xor(a,b)]
}

전가산기는 복잡하므로 카르노맵을 이용하여 간소화 시켜보자.
우선 합( S )을 카르노 맵으로 그리면

A \B CI	00	01	11	10
0	0	1	0	1
1	1	0	1	0

이웃한 항이 없으므로 식은

AB`C` + A`B`C + ABC + A`BC`
= A(B`C` + BC) + A`(B`C + BC`)
= A(B ⊙ C) + A`(B ⊕ C)
= A(B ⊕ C)` + A`(B ⊕ C)
= A ⊕ B ⊕ C

A ⊕ B ⊕ C 이다.

다음으로 CO 를 카르노맵으로 간소화 해보자

A \B CI	00	01	11	10
0	0	0	1	0
1	0	1	1	1

겹치는 부분을 이용해서 식을 구하면

AC + BC + AB

AC + BC + AB라는 식이 완성된다.
최종 식은 S : A ⊕ B ⊕ C, C : AC + BC + AB 이다.

코드로 작성해보겠다.

function fullAdder(a, b, carry) {
    let s = xor(a, xor(b, carry))
    let c = or(
            and(a, carry), 
            or(
                and(b, carry),
                and(a, b)
            )
        )
    return [c, s]
}

바이트 계산기

조건

바이트 덧셈(byteadder) : 8비트를 BOOL타입 배열로 2개를 입력 받는다.
자리올림(carry) + 전체 합(sum)을 순서대로 배열로 담아서 리턴하는 함수를 구현한다.
입력으로 들어오는 byteA, byteB 배열의 길이는 같다고 가정한다.
입력으로 들어오는 byteA 비트 순서는 낮은 자리가 배열의 앞쪽에 오도록 표현한다. 배열의 순서대로 보면 이진수가 뒤집혀 있는 것처럼 보인다고 가정한다.

function *twoEach(iterA, iterB) {
    let leng = iterA.length
    for(let i = 0; i < leng; i++) {
        yield [iterA[i], iterB[i]]
    }
}

function byteadder(byteA, byteB) {
    let answer = [],
        leng = byteA.leng,
        carry = 0
    for(const val of twoEach(byteA, byteB)) {
        let [a, b] = val
        let [c, s] = fullAdder(a, b, carry)
        answer.push(s)
        carry = c
    }
    answer.push(carry)
    return answer;
}

두 배열을 순회하면서 해당 배열의 value를 출력하는 제네레이터를 구현하고 전가산한 answer 에 넣고, 자리올림 수를 다시 carry에 넣어 구현한다.

진법 변환

• 10 진수를 2진수로 변환

function dec2bin(decimal) {
    let answer = [],
        q = decimal
    while (q > 1) {
        answer.push(q % 2)
        q = Math.floor(q / 2)
    }
    answer.push(q)
    return answer;
}

• 2 진수를 10진수로 변환

function bin2dec(bin) {
    var answer = 0;
    bin.forEach((el, i) => {
        if(el) answer += Math.pow(2, i)

    })
    return answer;
}