![]()
디지털 시스템의 논리 설계를 학습하기 위해 필요한 기본 수학은 부울 대수이다. 우리가 사용할 모든 스위칭 장치들은 기본적으로 2상태 장치이며 따라서 우리는 모든 변수가 두 값 중 하나만을 가지는 부울 대수의 특별한 경우를 강조할 것이다. 이렇게 두 값을 갖는 부울 대수는 종종 스위칭 대수라고 불린다. 부울 대수에서 사용되는 0과 1은 수치적인 값을 가지지 않는다. 대신 논리회로에서 두 개의 다른 상태를 표현하고, 스위칭 변수의 두 값을 나타낸다. 논리 게이트 회로에서, 0을 일반적으로 낮은 전압대를 표현하고, 1은 높은 전압대를 표현한다. 스위칭 회로에서 0은 일반적으로 열린 회로(normally open, NO)를 의미하고, 1은 닫힌 회로(normally close, NC)를 의미한다. 🧐 기본 연산..
![]()
이번 글에서는 필요한 회로의 기능에 대한 설명 문장을 통한 조합논리회로의 설계를 다뤄보겠습니다. 첫 단계에서는 보통 회로에 기능에 대한 설명을 진리표 혹은 대수 표현식으로 변환하게 됩니다. 부울함수에 대한 진리표가 주어지면, 표준 논리곱의 합(최소항 전개)과 표준 논리합의 곱(최대항 전개)의 두 가지 함수의 표준 대수식을 얻을 수 있습니다. 이들을 간략화하여 AND와 OR 게이트로 이루어진 회로를 구성할 수 있게 됩니다. 🧐 문제 서술부의 부울식 변환 논리설계 문제는 종종 한 문장 혹은 여러 문장을 사용하여 서술되기도 합니다. 논리회로 설계의 첫 단계는 이들 문장을 부울식으로 변환하는 것입니다. 이렇게 하기 위해서는 각 문장을 구로 나누고 각 구를 부울변수와 연관시켜야 합니다. 어떤 한 구가 "참(tru..
![]()
비결정성은 왜 쓰는가 비결정적 유한 인식기(nfa)는 결정적 유한 인식기(dfa)에 비해 모델링하기 쉬우며, 복잡한 문제를 간략하게 기술하는 데 효과적입니다. 또한 최적해를 찾기 위해 백트래킹(backtraking)등의 기법을 사용하여 모든 경우를 탐색했던 것을 최적의 선택을 할 수 있는 비결정적 알고리즘을 사용한다면 백트래킹 없이 문제를 해결할 수 있으며 결정적 알고리즘은 추가적인 작업을 통해서 비결정성을 시뮬레이트 할 수 있습니다. 이러한 이유로 비결정적 기계는 탐색 - 백트랙 알고리즘에 대한 모델로 사용될 수 있습니다. 또한 비결정성은 몇몇 복잡한 언어들을 간단하게 정의하는 데 효과적입니다. 예를 들어 다음과 같은 생성규칙 $$ S \to aSb | \lambda$$ 은 모든 경우 두 생성규칙들 중..
지난번 글에 이어서 정규 언어에 대한 판별에 사용될 수 있는 펌핑 보조정리에 대해 알아보도록 하겠습니다. 펌핑 보조정리 (Pumping lemma) 펌핑 보조정리는 비둘기집 원리를 다른 형태로 이용한 것입니다. 이에 대한 증명은 다음 관찰에 기반을 두고 있습니다. n개의 정점을 갖는 전이 그래프에서, 길이가 n 이상인 모든 보행은 어떤 정점이 반복, 즉 사이클을 가져야 한다 펌핑 보조정리는 다음과 같습니다. L을 무한 정규 언어(infinite regular lanuage)라 하면, 다음 성질을 만족하는 양의 정수 m이 존재합니다. 다음을 만족하는 모든 문자열 w에 대하여 $$|w| \geq m, \;\;\;\;\;\; w \in L$$ 문자열 w는 아래의 조건을 만족하도록 분할될 수 있습니다. $$w ..
스위칭 함수는 일반적으로 대수학적인 방법으로 간략화될 수 있으나 대수학적 방법은 두 가지 문제가 있습니다. 1. 체계적인 방법으로 적용하기 어렵다. 2. 최소 해답(minimum solution)을 얻었는지 확인하기 어렵다. 이 장에서 학습할 카노맵(Karnaugh map) 방법과 이후 다룰 퀸-맥클러스키(Quine-McCluskey) 방법은 스위칭 함수를 체계적인 방법으로 간략화시킬 수 있으므로 위의 문제점을 해결할 수 있습니다. 카노맵은 3변수 혹은 4변수로 이루어진 스위칭 함수를 간략화하고 조작하는 데 특별히 유용한 방법입니다. 🧐 스위칭 함수의 최소 형식 어떤 함수를 AND와 OR 게이트를 사용하여 구현할 때, 이에 들어가는 비용은 게이트의 개수, 게이트 입력의 개수와 연관이 있습니다. 카노맵은 ..
