부울 회로

부울 회선의 예.

displaystyle

노드는 AND 게이트,

\vee

\

displaystyle \vee

노드는 OR 게이트,

\neg

\

displaystyle \neg

노드는

\neg

게이트가 아닙니다.

계산 복잡도 이론과 회로 복잡도에서 부울 회로는 조합 디지털 논리 회로의 수학적 모델입니다.형식언어는 가능한 입력길이마다 하나의 회로인 부울회로 패밀리에 의해 결정될 수 있다.

부울 회로는 논리 게이트에 의해 정의됩니다.예를 들어, 회로는 이진 AND 및 OR 게이트와 단항 NOT 게이트를 포함하거나 이진 NAND 게이트에 의해 완전히 기술될 수 있습니다.각 게이트는 고정 비트 수를 입력으로 사용하고 단일 비트를 출력하는 일부 부울 함수에 해당합니다.

부울 회로는 멀티플렉서, 가산기 및 산술 로직 유닛을 포함한 컴퓨터 엔지니어링에서 사용되는 많은 디지털 컴포넌트의 모델을 제공하지만 순차 로직은 제외됩니다.이들은 준안정성, 팬아웃, 글리치, 소비전력, 전파지연 변동 등 실제 디지털 논리회로의 설계에 관련된 많은 측면을 생략한 추상화입니다.

형식적 정의

부울회로의 정식 정의를 내릴 때 Vollmer는 회로모델에서 허용되는 게이트에 대응하는 부울함수의 집합 B로 베이스를 정의함으로써 시작한다.다음으로 n개의 입력과 m개의 출력을 갖는 베이스 B상의 부울회로를 유한유향 비순환그래프로 정의한다.각 정점은 기본 함수 또는 입력 중 하나에 대응하며 ^[1]^{: 8}출력으로 라벨이 지정된 정확히 m개의 노드 세트가 있습니다.또한 동일한 부울 ^[1]^{: 9}함수에 대한 서로 다른 인수를 구별하기 위해 모서리에는 순서가 있어야 합니다.

특별한 경우로서 명제식 또는 부울식은 단일 출력 노드를 가진 부울 회로로, 다른 모든 노드가 1의 팬아웃을 가집니다.따라서 부울 회선은 서브공식 공유와 복수의 출력을 가능하게 하는 일반화로 간주할 수 있습니다.

부울 회로의 공통 기반은 기능적으로 완전한 세트 {AND, OR, NOT}, 즉 다른 모든 부울 함수를 구성할 수 있는 세트입니다.

계산의 복잡성

배경

특정 회로는 고정 크기의 입력에만 작동합니다.그러나, 형식 언어(결정 문제의 문자열 기반 표현)는 다른 길이의 문자열을 포함하므로, 언어는 단일 회로에 의해 완전히 포착될 수 없다(단일 튜링 기계에 의해 언어가 완전히 기술되는 튜링 기계 모델과는 대조적으로).언어는 회선 패밀리에 의해 대신 표시됩니다.회선 패밀리는 $(C_{0},C_{1},C_{2},...)$ 회선의 무한 $(C_{0},C_{1},C_{2},...)$ $(C_{0},C_{1},C_{2},...)$ C 1, $(C_{0},C_{1},C_{2},...)$ 2 . $(C_{0},C_{1},C_{2},...)$ . $(C_{0},C_{1},C_{2},...)$ ){ $display$ ( $C$ _ 0 , $C$ _ { $1}$ , C _ {2 $}$ , ... $(C_{0},C_{1},C_{2},...)$ )입니다 $(C_{0},C_{1},C_{2},...)$ $C_{n}$ 서 C $C_{n}$ n \ $display style$ C _ { $n$ }에는 $C_{n}$ $n$ n개의 $입력변수가 있습니다.$ $C_{n}(w)=1$ 패밀리는 모든 $문자열$ w $\displaystyle$ w $\$ w\ $displaystyle$ w $\$ displaystyle $w$ L $\$ displaystyle L\displaystyle L $\$ displaystyle $C_{n}(w$ 인 $C_{n}(w)=1$ 에만 $언어$ L $\$ $displaystyle$ L을 $L$ $L$ 결정합니다. $n$ 서 n $\displaystyle$ n은 $n$ $w$ 의 $w$ n 즉, 언어는 그 길이에 대응하는 회로에 적용되었을 때 ^[2]^{: 354}1로 평가되는 문자열 세트이다.

복잡도 측정

부울 회로에는 회로 깊이, 회로 크기, AND 게이트와 OR 게이트 간의 교대 횟수 등 몇 가지 중요한 복잡도 측정을 정의할 수 있습니다.예를 들어 부울 회선의 크기 복잡도는 회선 내의 게이트 수입니다.

회로 크기의 복잡성과 시간의 ^[2]^{: 355}복잡성 사이에는 자연스러운 관계가 있습니다.직관적으로 시간 복잡도가 작은 언어(즉, 튜링 기계에서 비교적 적은 수의 순차 연산을 필요로 함)는 또한 작은 회로 복잡도를 가진다(즉, 상대적으로 적은 수의 부울 연산을 필요로 함).공식적으로는 언어가 ${\mathsf {TIME}}(t(n))$ ${\mathsf {TIME}}(t(n))$ ${\mathsf {TIME}}(t(n))$ ( ${\mathsf {TIME}}(t(n))$ ( ${\mathsf {TIME}}(t(n))$ $){$ $display$ { $mathsf$ { $TIME$ } ( t ( $n$ ) } } } } ${\mathsf {TIME}}(t(n))$ } } } 。 $t$ 서 $t$ t $t:\mathbb {N} \to \mathbb {N}$ { $displaystyle$ t $:\mathbb {N}$ \ $to \mathbb {N}$ $t:\mathbb {N} \to \mathbb {N}$ } , , 、 , $O(t^{2}(n))$ （） complex $O(t^{2}(n))$ complex complex complex complex complex complex complex complex complex complex complex complex complex complex complex complex complex $O(t^{2}(n))$ ( complex complex ( $t:\mathbb {N} \to \mathbb {N}$ ( ( ( ( ( n complex n , ( $O(t^{2}(n))$ $t:\mathbb {N} \to \mathbb {N}$ $t:\mathbb {N} \to \mathbb {N}$ N $t:\mathbb {N} \to \mathbb {N}$ complex , formally formally formally $t:\mathbb {N} \to \mathbb {N}$ formally formally

복잡도 클래스

부울 회선의 관점에서 몇 가지 중요한 복잡도 클래스가 정의되어 있습니다.이들 중 가장 일반적인 것은 다항식 크기의 회로 패밀리로 결정 가능한 언어 집합인 P/poly입니다.이는 T ${\mathsf {TIME}}(t(n))$ ${\mathsf {TIME}}(t(n))$ E ( ${\mathsf {TIME}}(t(n))$ ( ${\mathsf {TIME}}(t(n))$ $){$ $displaystyle$ { $TIME$ }} ( t ( ${\mathsf {TIME}}(t(n))$ n ) } ${\mathsf {TIME}}(t(n))$ t 、 P ${\$ \ $displaystyle$ \ $subseteq }$ /poly의 회선 $O(t^{2}(n))$ O $O(t^{2}(n))$ ( $O(t^{2}(n))$ ( $n$ ) { $displaystyle O$ ( $n$ ) ）。즉, 결정론적 튜링 기계에 의해 다항 시간에 계산될 수 있는 문제는 다항식 크기의 회로 패밀리에 의해서도 계산될 수 있다.또한 P/poly에 결정 불가능한 문제가 있기 때문에 포함이 적절한 경우(즉, P ${\$ \displaystyle \ $\subsetneq$ } P/poly)입니다.P/poly에는 복잡도 클래스 간의 관계를 연구하는 데 매우 유용한 여러 특성이 있는 것으로 나타났습니다.특히 P 대 NP와 관련된 문제를 조사하는 데 유용합니다.예를 들어 NP에 P/poly에 없는 언어가 있는 경우 P ${\$ { $displaystyle \neq }$ NP $\neq$ .^[3]^{: 286} P/poly는 다항식 계층의 속성 조사에도 도움이 됩니다.예를 들어 NP p P/poly일 경우 PH는 $\Sigma _{2}^{\mathsf {P}}$ 2 $\Sigma _{2}^{\mathsf {P}}$ { $displaystyle$ \ $Sigma$ _ { $2}^{\mathsf {P$ 로 축소됩니다.P/poly와 기타 복잡도 클래스의 관계에 대한 자세한 설명은 "Importance of P/poly"에서 확인할 수 있습니다.P/poly는 또한 다항식 경계 조언 함수를 가진 다항식 시간 튜링 기계에 의해 인식되는 언어의 클래스로 동등하게 정의될 수 있다는 흥미로운 특징을 가지고 있다.

P/poly의 서브클래스는 NC와 AC입니다.이러한 클래스는 회로 크기뿐만 아니라 깊이에서도 정의됩니다.회로의 깊이는 입력 노드에서 출력 노드까지의 가장 긴 방향 경로 길이입니다.클래스 NC는 다항식 크기뿐만 아니라 다항식 깊이까지 제한되는 회로 패밀리로 해결할 수 있는 언어 집합입니다.클래스 AC는 NC와 유사하게 정의되지만 게이트에는 무제한 팬인이 허용된다(즉, AND 및 OR 게이트는 2비트 이상에 적용할 수 있다).NC는 효율적인 병렬 알고리즘을 가진 언어 클래스를 나타내는 중요한 클래스입니다.

회로 평가

회선값 문제, 즉 특정 입력 문자열에 대한 특정 부울 회선의 출력을 계산하는 문제는 P-완전 판정의 문제입니다.^[3]^{: 119}따라서 이 문제는 문제를 해결하는 효율적이고 고도의 병렬 알고리즘이 없을 가능성이 높다는 점에서 "원리적으로 순차적"으로 간주됩니다.

완전성

논리회로는 간단한 논리연산, AND, OR 및 NOT(및 비순차 플립플롭 또는 회로망 등 이들의 조합)의 물리적인 표현으로 부울 대수라고 불리는 수학 구조를 형성합니다.이들은 어떤 결정론적 알고리즘도 실행할 수 있다는 점에서 완전합니다.하지만 이게 전부가 아닐 뿐이죠.물리 세계에서도 양자화 효과에 의해 지배되는 작은 시스템에서 나타나는 무작위성과는 양자역학 이론에서 설명됩니다.논리회로는 랜덤성을 생성할 수 없으며, 그런 의미에서 논리회로는 불완전한 논리세트를 형성합니다.이에 대한 해결책은 확률론적 튜링 기계와 같은 논리 네트워크 또는 컴퓨터에 애드혹 랜덤 비트 생성기를 추가하는 데서 찾을 수 있다.최근 연구는 랜덤 플립 플랍이라는 이름의 본질적으로 랜덤 논리 회로의 이론적 개념을 도입하여 세트를 완성했습니다.랜덤성을 편리하게 포장하고 결정론적 부울 논리 회로와 상호 운용할 수 있습니다.단, 부울 대수에 상당하는 대수구조와 확장집합에 대한 회로구축 및 감소의 관련방법은 아직 알려져 있지 않다.

「」를 참조해 주세요.

각주

^ ^a ^b Vollmer, Heribert (1999). Introduction to Circuit Complexity. Berlin: Springer. ISBN 3-540-64310-9.
^ ^a ^b Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). USA: Thomson Course Technology. ISBN 978-0-534-95097-2.
^ ^a ^b Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.
^ Stipčević, Mario; Batelić, Mateja (2022). "Entropy considerations in improved circuits for a biologically-inspired random pulse computer". Scientific Reports. 12: 115. doi:10.1038/s41598-021-04177-9.

[Vollmer-1] Vollmer, Heribert (1999). Introduction to Circuit Complexity. Berlin: Springer. ISBN 3-540-64310-9.

[Sipser-2] Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). USA: Thomson Course Technology. ISBN 978-0-534-95097-2.

[arorabarak-3] Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.

[4] Stipčević, Mario; Batelić, Mateja (2022). "Entropy considerations in improved circuits for a biologically-inspired random pulse computer". Scientific Reports. 12: 115. doi:10.1038/s41598-021-04177-9.

[1]

[2]

[3]

v t 디지털 일렉트로닉스
구성 요소들	트랜지스터 저항기 인덕터 콘덴서 프린트 일렉트로닉스 프린트 기판 전자 회로 플립 플랍 메모리 셀 조합논리 순차 논리 논리 게이트 부울 회로 집적회로(IC) 하이브리드 집적회로(HIC) 혼합 신호 집적 회로 3차원 집적회로(3D IC) 이미터 결합 논리(ECL) Erasable Programmable Logic Device(EPLD) 매크로셀 어레이 프로그래머블 로직 어레이(PLA) 프로그래머블 로직 디바이스(PLD) 프로그래머블 어레이 로직(PAL) 범용 어레이 로직(GAL) 복합 프로그래머블 로직 디바이스(CPLD) Field-Programmable Gate Array(FPGA; 필드 프로그래밍 가능 게이트 어레이) Field-Programmable Object Array(FPOA; 필드 프로그래머블오브젝트 어레이) Application-Specific Integrated Circuit(ASIC; 응용 프로그램 고유 집적회로) 텐서 처리 장치(TPU)
이론.	디지털 신호 부울 대수 논리합성 컴퓨터 공학에서의 논리학 컴퓨터 아키텍처 디지털 신호 디지털 신호 처리 회선 최소화 스위칭 회로 이론 게이트 등가물
설계.	논리합성 장소 및 경로 배치 라우팅 Register-transfer level 하드웨어 설명 언어 높은 수준의 합성 형식적 동등성 검사 동기 논리 비동기 논리 유한 상태 기계 계층형 스테이트 머신
적용들	컴퓨터 하드웨어 하드웨어 액셀러레이션 디지털 오디오 무전 디지털 사진 디지털 전화 디지털 비디오 촬영술 텔레비전 전자 문학
설계상의 문제	준안정성 런트 펄스

Search

부울 회로

네임스페이스

더

목차

형식적 정의

계산의 복잡성

배경

복잡도 측정

복잡도 클래스

회로 평가

완전성

「」를 참조해 주세요.

각주

Search

부울 회로

형식적 정의

계산의 복잡성

배경

복잡도 측정

복잡도 클래스

회로 평가

완전성

「 」를 참조해 주세요.

각주

「」를 참조해 주세요.