다수결 함수
1. 개요
다수결 함수는 입력의 50% 이상이 참일 때 참을 반환하는 논리 게이트이다. 부울 회로 및 회로 복잡도 분야에서 사용되며, 전가산기, 3중 모듈 중복성 시스템의 오류 수정 등에 활용된다. 회로 복잡도 이론에 따르면 AC0 회로에서 서브 지수 크기로 계산할 수 없으며, 3진 다수결 함수는 특정 성질을 만족한다. 다수결 함수는 일반화될 수 있으며, 동률 발생 시 0으로 편향되거나 무작위로 해소될 수 있다.
-
회로 복잡도 -
스위칭 회로 이론
-
회로 복잡도 -
NC (복잡도)
NC 복잡도는 함수 문제와 탐색 문제를 분류하는 복잡도 종류로, 정수 연산, 행렬 연산 등 병렬 연산에 적합한 다양한 문제가 속하며, NC<sup>i</sup>로 표현되는 계층 구조를 가지고, NC 계층의 적절성은 중요한 미해결 문제이고, 배링턴 정리는 NC 복잡도를 이해하는 데 중요한 역할을 한다. -
불 대수 -
드 모르간의 법칙
드 모르간의 법칙은 명제 논리, 술어 논리, 집합론, 부울 대수 등에서 결합 또는 분리의 부정을 각 요소의 부정의 분리 또는 결합으로 표현하는 논리적 원리이다. -
불 대수 -
불 논리
불 논리는 0과 1, 참과 거짓의 두 값만으로 논리곱, 논리합, 부정 연산을 통해 명제의 참, 거짓을 판단하고 조작하는 논리 체계로, 라이프니츠의 개념 대수에서 기원하여 조지 불에 의해 체계화되었으며, 섀넌의 스위칭 회로 연구를 통해 디지털 논리 회로 설계의 기초를 다지는 데 기여하며 다양한 분야에서 핵심적인 역할을 수행한다.
2. 부울 회로
다수결 게이트는 부울 회로에서 입력의 과반수가 참일 때 참을 출력하는 논리 게이트이다. 전가산기에서 자리올림수(캐리) 출력은 세 개의 입력에 다수결 함수를 적용하여 구할 수 있지만, 종종 가산기의 이 부분은 여러 개의 더 간단한 논리 게이트로 분해된다.
2.1. 회로 복잡도
회로 복잡도 이론에서 다수결 함수는 AC0 회로에서 으로 계산할 수 없다는 것이 증명되었다. 이는 다수결 함수가 특정 복잡도 클래스에 속하지 않음을 의미한다.
2.2. 응용
다수결 게이트는 전가산기에서 자리올림수 출력을 계산하거나, 오류 정정을 위한 다수결 논리 디코딩에 사용된다. 많은 시스템에서 3중 모듈 중복성을 사용하며, 오류 수정을 위해 다수결 함수를 활용한다. 예를 들어, 전가산기에서 자리올림수 출력은 3개의 입력에 다수결 함수를 적용하여 구할 수 있다.
3. 성질
3진 다수결 함수 <x, y, z>는 다음 성질을 만족한다.
* <x, y, y> = y
* <x, y, z> = <z, x, y>
* <x, y, z> = <x, z, y>
* <<x, w, y>, w, z> = <x, w, <y, w, z>>
이러한 대수 구조를 중앙값 대수라 한다. 임의의 x, y, z에 대해 삼항 중앙값 연산자 ⟨x, y, z⟩는 다음 방정식을 만족한다.
* ⟨x, y, y⟩ = y
* ⟨x, y, z⟩ = ⟨z, x, y⟩
* ⟨x, y, z⟩ = ⟨x, z, y⟩
* ⟨⟨x, w, y⟩, w, z⟩ = ⟨x, w, ⟨y, w, z⟩⟩
이러한 공리를 만족하는 추상적인 시스템은 중앙값 대수이다.
4. 다수결 함수의 일반화
n = 1일 때에는 항등 함수 x가 되고, n = 3일 때에는 xy + yz + zx가 된다. 이때 +는 논리합이나 배타적 논리합이나 같은 결과를 도출한다. 임의의 n에 대해 크기가 O(n5.3)인 다수결 함수에 대한 단조 공식이 존재하지만 이는 확률적 방법에 의한 비구성적 증명이다.
다항식 크기의 명시적 다수결 공식을 위한 접근 방식은 다음과 같다.
* 각 비교-교환 "와이어"가 단순히 OR 게이트와 AND 게이트인 정렬 네트워크에서 중앙값을 취한다. 아지-콤로스-세메레디 (AKS) 구조가 그 예이다.
* 더 작은 다수결 회로의 출력을 결합한다.