선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 여러 개의 출력단을 갖는 논리회로에는 동일한 회로가 반복 사용되는 경우가 종종 있다. 논리회로 최적화 방법 중의 하나가 반복 사용된 회로를 공유하도록 하여 전체 논리회로를 최적화하는 것이다. 이러한 최적화 방법을 공통식 추출 방법(extraction) 이라 한다.
- 이러한 방법들 모두 선험 방식(heuristic method)에 의한 기법으로 여전히 간략화를 하지 못하는 문제점을 갖고 있다. 따라서, 본 논문에서는 기존의 나눗셈에 의한 공통식 산출이 아니라, 각 출력단의 논리식을 변형하고, 변형된 후의 논리식에서 공통식이 있는지 찾는 방법을 제시하였다.
- 이때, 이 전 절에서 언급한 방식을 적용하기 위해 즉, 배타 논리합 식 산출 원리를 적용한 논리식을 산출하고, 보정식이 다른 출력의 논리식과 공통 부분이 있는지 전수 조사를 하는 것은 장시간의 수행시간을 요구하기 때문에 실용성이 없다. 따라서, 본 논문에서는 배타 논리합 식 산출과 보정식의 공통 부분 조사를 위해 커널 집합을 이용한 선험 방법을 제안한다.
- 제안하는 방법은 XOR 연산자를 이용한 베타 논리합식 산출 방법을 이용하였지만, XOR 연산자는 사용하지 않고 OR 연사자와 보정식을 사용하도록 하였다. 배타 논리합 식은 주어진 카르노 맵을 이용할 경우 다수 개가 산출될 수 있어, 최적의 결과를 찾는 수행 시간이 증가할 수 있기 때문에 본 논문에서는 선험 방식을 도입한 간략화 방법을 제안하였다. 마지막으로 제안한 방법은 리터럴 개수를 줄이는 것이 목표로 실험 결과에서 보였듯이타 방법들에 비해 리터럴 개수를 줄이는 효과를 보였다.
- 이전 절에서 언급한 바와 같이 배타 논리합 식의 경우 단순식에 비해 리터럴의 개수를 줄일 수 있는 장점이 있지만, XOR 게이트를 논리회로에 사용해야 점과 다수 개의 배타 논리합 식이 산출될 수 있다는 단점이 있다. 본 논문에서는 논리회로에 XOR 게이트를 사용하지 않고, 단지 AND, OR, NOT 게이트만으로 구성된 논리회로를 산출하는 것을 목표로 하며, 제안하는 방법은 다음과 같다.
- 본 논문은 여러 출력에서 존재할 수 있는 공통 논리식을 산출하기 위한 방법을 제안하였다. 즉, 최적화 전의 전체 논리식들에서 전역(global)의 공통식을 찾는 방법이다.
가설 설정
- 정의 3: 단순식을 구성하는 모든 큐브들에 대하여, 공통으로 쓰인 리터럴이 없다면 그 단순식은 큐브면제(cube-free) 되었다고 한다. 단순식이 어떤 큐브로부터 나누어졌을 때 몫이 큐브면제라면, 그 몫을 커널(kernel)이라 한다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.