8. 조합논리함수(2: 디코더, 엔코더, 코드 변환기, 멀티플렉서, 디멀티플렉서, 패리티 발생/점검기, 에러수정코드)

8. 조합논리함수(2: 디코더, 엔코더, 코드 변환기, 멀티플렉서, 디멀티플렉서, 패리티 발생/점검기, 에러수정코드)

디코더

디코더(decoder)는 \(n\)개의 입력변수에 대해 \(2^{n}\)개의 곱항을 생성하는 논리회로이다.

3 입력 8 출력 디코더의 논리회로와 진리표

4입력 16출력 디코더의 진리표와 디코더 기호

위의 그림은 Enable 입력(IC의 동작을 제어하기 위한 입력)을 갖는 2입력 4출력 디코더의 논리회로와 진리표이고 \(E=1\)이면, 입력에 관계없이 모든 출력이 1이 되고(디코더 기능을 하지 않음), \(E=0\)이면 디코더로 동작하고 반전출력을 발생시킨다.

(BCD 디코딩 함수)

(BCD-7 세그먼트 디코더 기호)

엔코더

엔코더(encorder)는 디코더의 역연산으로 \(2^{n}\)개(또는 그 이하)의 입력에 대해 \(n\)개의 출력을 생성하고, 출력은 인가된 입력값에 해당하는 2진 코드를 생성한다. 

다음은 10진수를 BCD코드로 변환하는 디코더의 진리표, 논리회로, 기호이다.

이 엔코더는 10개의 입력에서 오직 하나의 1만이 인가되도록 제한해서 출력에서 해당 입력에 대한 2진수를 생성한다. 여기서$$\begin{align*}A_{3}&=I_{8}+I_{9}\\A_{2}&=I_{4}+I_{5}+I_{6}+I_{7}\\A_{1}&=I_{2}+I_{3}+I_{6}+I_{7}\\A_{0}&=I_{1}+I_{3}+I_{5}+I_{7}+I_{9}\end{align*}$$이다. 

코드 변환기

다음의 논리회로는 4비트 2진수-그레이 코드 변환기이다.

(왼쪽: 4비트 2진수에서 그레이 코드로 변환, 오른쪽: 4비트 그레이 코드에서 2진수로 변환)

위의 그림에서 왼쪽은 2진수 1010을 그레이 코드로, 오른쪽은 그레이 코드 1101을 2진수로 변환하는 것을 나타낸 것이다.

멀티플렉서

멀티플렉서(multiplexer, MUX)는 여러개의 입력중 하나를 선택해서 출력으로 전송하는 조합논리회로(데이터 선택기, data selector)이다.

다음은 4입력 멀티플렉서의 진리표, 기호, 논리회로, 파형이다.

선택입력 \(S_{1}S_{0}\)에 의해 입력이 선택되어 출력 \(Y\)에 전달된다.

다음은 멀티플렉서를 이용하여 조합 논리함수를 SOP형태로 나타낸 3입력 74HC151 논리함수 발생기이다.

왼쪽은 진리표, 오른쪽은 기호이다.

(74HC151 4입력 논리함수 발생기)

디멀티플렉서

디멀티플렉서(demultiplex, DMUX)는 멀티플렉서의 역연산으로 입력 정보를 하나의 입력선에서 받아서 가능한 \(2^{n}\)개의 출력선 중 하나를 택해서 전송한다. 출력하는 출력선은 입력으로부터 선택한다.

다음은 1선-4선 디멀티플렉서의 논리회로이다.

패리티 발생/점검기

패리티 논리는 짝수 패리티를 사용하는 경우, 1의 총 개수가 짝수가 되도록 패리티 값을 조정하고, 홀수 패리티를 사용하는 경우, 1의 총 개수가 홀수가 되도록 패리티 값을 조정한다.

예를 들어 2비트의 합은 2비트 XOR로, 4비트의 합은 4비트 XOR로 점검한다.(아래 그림 참고)

(왼쪽: 2비트 덧셈, 오른쪽: 4비트 덧셈)

(74LS280 9비트 패리티 발생기/검사기)

에러 수정 코드

에러 수정 코드(error correction code, ECC)는 메모리 장치의 신뢰도를 향상시키며 에러의 검출을 위해 패리티 비트를 사용한다. 이때 에러 수정 코드는 여러 비트의 검출비트를 포함해야 한다.

메모리에서 가장 많이 사용되는 에러 수정 코드는 해밍 코드(Hamming code)이다.

n비트 데이터와 k비트 패리티 비트의 합은 n+k비트이다. 2의 거듭제곱수에 해당하는 위치에 패리티를 위해 할당하고 나머지는 데이터 비트이다.

P1

P2

1

P4

1

0

0

P8

0

1

0

0

위의 8비트 데이터 워드에서 4개의 패리티 비트 P1, P2, P4, P8이 각각 1, 2, 4, 8자리에 위치해 있고,

P1 비트는 3, 5, 7, 9, 11의 XOR로 \(1\oplus1\oplus0\oplus0\oplus0=0\)

P2 비트는 3, 6, 7, 10, 11의 XOR로 \(1\oplus0\oplus0\oplus1\oplus0=0\)

P4 비트는 5, 6, 7, 12의 XOR로 \(1\oplus0\oplus0\oplus0=1\)

P8 비트는 9, 10, 11, 12의 XOR로 \(0\oplus1\oplus0\oplus0=1\)

XOR함수는 홀수 함수로 변수의 1의 개수가 홀수이면 1, 짝수이면 0이다. 따라서 각 패리티 비트는 점검하려는 위치의 1의 개수에 의해 세트 또는 리셋된다. 또한 패리티 비트를 포함해서 1의 개수는 항상 짝수이다.

(점검하려는 위치의 1의 개수_패리티 비트의 1의 개수=짝수)

 

0

0

1

1

1

0

0

1

0

1

0

0

위의 8비트 데이터와 4비트 패리티 비트의 합 12비트가 메모리로부터 읽혀지면 에러가 발생했는지를 점검한다(패리티 비트를 포함시켜서 위와 같은 조합을 점검한다).

다음은 위의 12비트에 대한 4개의 점검비트이다.

\(C_{1}\)은 1, 3, 5, 7, 9, 11의 XOR로 \(0\oplus1\oplus1\oplus0\oplus0\oplus0\oplus0=0\)

\(C_{2}\)은 2, 3, 6, 7, 10, 11의 XOR로 \(0\oplus1\oplus0\oplus0\oplus1\oplus0=0\)

\(C_{4}\)은 4, 5, 6, 7, 12의 XOR로 \(1\oplus1\oplus0\oplus0\oplus0=0\)

\(C_{8}\)은 8, 9, 10, 11, 12의 XOR로 \(1\oplus0\oplus1\oplus0\oplus0=0\)

여기서 점검 비트가 0이면 짝수 패리티, 1이면 홀수 패리티이다. 

짝수 패리티를 사용하는 경우, \(C=C_{8}C_{4}C_{2}C_{1}=0000\)이고 에러(오류)가 없으나 그렇지 않은 경우(\(C\neq0000\))는 에러가 발생한다.

해밍 코드는 임의의 길이를 갖는 데이터에 적용할 수 있다. 일반적으로 해밍 코드는 n비트 데이터와 k비트 점검 비트로 구성되어 있다(n+k비트). 신드롬 값(syndrome value)(에러 검사에 대한 검사 결과) \(C\)는 k비트로 \(0\,\sim\,2^{k}-1\)범위의 값을 가지며 \(C=0\)이면 에러가 없고, \(C\neq0\)이면 n+k비트 중 하나에 에러가 있다. \(2^{k}-1\)개의 각각의 값에 의해 에러 비트가 판정되므로 \(2^{k}-1\)은 비트 수보다 큰 값이어야 한다. 즉 \(2^{k}-1\geq n+k\)이고 \((2^{k}-1)-k\geq n\)이다.

해밍 코드는 단일 에러의 검출과 수정이 가능하나 복수개의 에러를 검출할 수 없다. 따라서 부가의 패리티 비트를 첨가해서 단일 에러 뿐만 아니라 2개의 에러를 검출이 가능하게 한다. 

부가된 패리티 P13은 1부터 12까지의 모든 비트들의 XOR이고, P를 12개의 비트와 P13의 XOR이라고 하면 P=0일 때 짝수 패리티(true), 

P=1일 때 홀수 패리티(false)이다.

*참고

\(C=0000,\,P=0\)이면 에러가 없다.

\(C\neq0000,\,P=1\)이면 단일 에러가 있고 수정이 가능하다.  

\(C\neq0000,\,P=0\)이면 복수(2개)의 에러가 있고, 검출만 가능하고 수정이 불가능하다.   

\(C=0000,\,P=1\)이면 P13비트에 에러가 있다.  

참고자료:

Digital Fundamentals 11th edition, Floyd, Pearson

Digital Design 5th edition, Mano, Ciletti, Pearson

http://www.ktword.co.kr/abbr_view.php?m_temp1=1212

http://www.ktword.co.kr/abbr_view.php?nav=&m_temp1=3690&id=483