[논리회로] 3. 게이트 레벨 최소화

 

 

 

3.1 게이트 레벨 최소화

게이트 레벨 최소화는 불 함수의 최적(게이트 개수에 대한 optimal 측면)의 게이트 레벨 구현을 위한 설계작업이다. 동일한 작업을 기준으로 복잡도, 게이트 개수를 줄여 각격을 낮추기 위한 목적으로 실행된다.

 

 

불 함수를 표기하는 방법 

1. 정준 형식(어느 변수 하나 빠지지 않고 모든 변수가 포함되어 있어야 함.)

• -최소항
• -최대항

2.표준형식(정준형식을 제외한 모든 형식)

• 곱의 합
• 합의 곱

 

3.2 카르노 맵

카르노 맵(Karnaugh map, K map) 은 불 함수의 간략화를 위한 간단하고 직접적인 방법이다.

구성된 네모 칸들 중 하나의 네모 칸은 하나의 최소항(minterm)을 나타낸다.

간략화된 표현에서 맵은 곱의 합 또는 합의 곱으로 표현된다.

 

카르노맵의 가로 세로 변수 조합은 1비트씩 변화시키는 gray코드를 따르기 때문에 순서가 뒤바뀌어 있다.

2변수 카르노맵

3변수 카르노맵

4변수 카르노맵

 

 

 

3.3 카르노맵의 간략화

카르노맵으로 표현 후 함수 간소화

주항(prime implicant)은 맵 안의 인접 네모 칸을 최대로 결합했을 때 얻어지는 곱의 합이다.

이 때 네모 칸의 개수는 1,2,4,8,......의 2^n 개 여야 한다. 

필수 주항(essential prime implicant)은 어떤 최소항을 단 하나의 주항으로 커버할 수 있는 항을 말한다.(가능한 주항들 중 다른 묶음들과 2회 이상 겹치지 않고 한번만 포함되는 항)

가장 간략화 된 표현식을 얻기 위해서는 모든 필수 주항(essential prime implicant)을 찾아야 한다.

 

정답이 될 수 있는 불 함수

주어진 카르노맵에서 최대로 묶일 수 있는 항들을 나타내었을 때 한번만 겹치는 것이 필수주항이다. 

필수주항을 포함하는 최소항들은 결과식에 반드시 포함되어야 한다.

 

 

진리표에서 1은 곱의 합, 최소합을 나타내고 0은 합의 곱, 최대항을 나타낸다. 

 

카르노맵에서 F를 구하는 방법

1.카르노맵의 1인 항을 묶어 F의 곱의 합 구하기

2.카르노맵의 0인 항을 묶어 F프라임의 곱의 합을 구한 후, 드모르간 법칙을 이용해 F의 합의 곱을 구하기

(F와 F프라임은 보수관계)

 

표준형식은 논리게이트로 나타내었을 때 2-level로 구현될 수 있다.

곱의 합 형식 : AND 게이트가 OR 게이트에 연결

합의 곱 형식 : OR 게이트가 AND 게이트에 연결

 

 

 

 

3.4 don't care 조건

don't care 조건은 입력조합에 대해 불완전하게 규정되는 함수로, 0이나 1로 표현한다.

 

 

 

 

3.5 NAND와 NOR의 구현

 AND,OR,NOT게이트항으로 구성된 불함수를 등가의 NAND,NOR논리도록 바꿀 수 있다.

디지털 회로에서 AND,OR게이트 보다 NAND(곱의 합) NOR(합의 곱)로 표현하는 이유는 더 경제적이고 시간지연이 작기 때문이다.

 

 

 

 

3.6 기타 2-level 구현

AND,OR,NAND,NOR 게이트로 만들 수 있는 2-level조합은 16개이다. 이 중 8개는 단일 레벨로 표현 가능하여 degenerate형식이며 나머지 8개는 nondegenerate형식이다.

NAND와 NOR은 결합법칙이 성립하지 않는다.

AND-OR-INVERT

카르노맵에서 0끼리 결합 > 곱의 합 형식으로 F프라임 구함 > 드모르간으로 F출력

OR-AND-INVERT

카르노맵에서 1끼리 결합해 F구함 > 드모르간으로 F프라임 구함

 

 

 

 

 

3.7 XOR구현

XOR은 배타적 논리합으로 산술연산과 에러검출(통신에서 고속전송 시 에러가 발생) 및 수정(수정 가능)회로에 사용한다.

XOR은 1이 홀수개면(=x와 y가 다르면) 1인 odd function이다.

XNOR은 배타적 논리부정합으로 XOR의 보수이다.

XNOR은 1이 짝수개면(=x와 y가 같으면) 1인 even function이다.

 

 

 

 

3.8 패리티 생성과 검사

패리티 비트는 2진 정보의 전송 중에 에러 검출 목적으로 사용된다.

송신기에서 일정 비트의 신호를 보내고 수신기에서 일정 비트의 신호를 받는 상황이다.

(통신규약(protocol) : 만약 odd를 통신규약으로 할 경우, 1의 개수가 홀수개가 되도록 송신하여, 패리티 생성기가 프로토콜에 맞추어 1의 갯수를 세고 1 or 0을 추가)

1의 개수가 (송신기 - 짝수, 수신기 - 홀수) or (송신기 - 홀수, 수신기 - 짝수) 이면 통신오류가 발생하는데, 

이를 방지하기 위해 패리티 생성기는 1의 개수가 짝수인지 홀수인지 확인하고  이를 맞춰주기 위해 0 또는 1의 비트를 추가해주는 역할을 한다. 이후 패리티 검사기를 통해 홀짝을 검사한다.

 

*패리티 비트의 한계

1.에러가 1개가 아닌 짝수개가 날 경우, 에러검출이나 수정을 할 수 없다.

ex)송신 : 5개 > 수신 : 3개

2.패리티비트 자체가 잘못 수신된 경우 에러를 검출할 수 없다.

송신 : 0 > 수신 : 1

송신 : 1 > 수신 : 0