홍익대 서울캠퍼스 2023학년도 수시 오전 자연계열 2번 해설

문제 2 (20점)

디지털 통신에서 송신기가 1비트(bit) 0 또는 1을 전송하는 상황을 생각하자. 송신기가 1을 보내었어도 다른 신호에 의한 간섭 때문에 수신기는 0을 받을 수도 있다. 또는, 송신기가 0을 보내었어도 수신기는 1을 받을 수 있다.

이러한 간섭의 효과를 줄이기 위해 현대 통신에서 송신기는 하나의 비트를 한 번 보내는 대신 동일한 비트를 연속으로 $\displaystyle n$ 번(이때 $\displaystyle n$ 은 홀수인 자연수) 반복하여 보낸다. 이러한 반복을 통해 간섭에 의한 최종 오류를 줄일 수 있는데, 이를 $\displaystyle n$ -반복 코드( $\displaystyle n$ -repetition code)라고 한다. 수신기에서 받은 $\displaystyle n$ 개의 비트들을 기준으로 송신기가 보낸 비트가 무엇인지를 결정하게 되며, 이때 수신기는 더 많이 받은 비트를 송신기가 보내었다고 결정한다.

예시: $\displaystyle n=5$ 인 5-반복 코드의 경우, 1을 보내는 대신, 송신기는 1을 5개 붙여서 11111을 송신한다. 이때, 간섭에 의해 각각의 비트는 변화할 수 있다. 수신기가 10011을 받았다면 0이 두 개이고 1이 세 개이므로 수신기는 송신기가 보낸 비트는 1이라고 최종결정한다. 혹은, 수신기가 10000을 받았다면 수신기는 송신기가 보낸 비트가 0이라고 최종결정하게 된다. 이처럼 수신기가 최종결정한 비트가 송신기가 보낸 비트와 서로 다른 경우 '최종결정오류'가 발생했다고 하자.

아래와 같은 가정을 하자, $\displaystyle n$ -반복 코드 내에서 각각의 비트는 독립적으로 간섭에 노출되어 바뀌고 그 확률은 $\displaystyle p$ 이다.

즉,· 0을 보낼 때, 간섭에 의해 수신기가 1을 받을 확률은 $\displaystyle p$ 이다.· 1을 보낼 때, 간섭에 의해 수신기가 0을 받을 확률은 $\displaystyle p$ 이다.· 간섭에 의한 영향을 받지 않아 0 또는 1이 바뀌지 않고 수신기가 그대로 받을 확률은 $\displaystyle 1-p$ 이다.

(1) 보통의 경우, 각각의 비트가 간섭에 의해 바뀔 확률 $\displaystyle p$ 를 0.1이라 하자. 이때, 3-반복 코드 수신기의 최종결정 비트와 송신기가 보낸 비트가 서로 달라 최종 결정 오류가 발생할 확률을 구하시오.

(2) 갑작스런 태양의 활동으로 각각의 비트가 바뀔 확률 $\displaystyle p$ 가 0.1에서 0.2로 늘어났다고 하자. 이때, 동일하게 구성된 3-반복 코드 수신기의 최종 결정 오류 확률을 구하시오. 그리고, 이 값이 문항 (1)에서 구한 확률의 몇 배인지 소수점 둘째 자리에서 반올림하여 구하시오.

(3) 문항 (2)와 같이 태양 활동이 활발한 경우( $\displaystyle p=0.2$ ), 수신기의 최종 결정 오류를 줄이기 위해 송신기의 비트를 $\displaystyle m$ 번 반복하는 $\displaystyle m$ -반복 코드를 설계하려고 한다. 단, $\displaystyle m$ -반복 코드 수신기의 최종 결정 오류 확률값이, 문항 (1)에서 구한 $\displaystyle p=0.1$ 일 때의 3-반복 코드의 최종 결정 오류 확률값보다 더 작도록 설계하고 싶다. 필요한 $\displaystyle m$ 의 최솟값을 아래의 표를 참고하여 구하시오.

$2^{10}=1024$	$2^{11}=2048$	$2^{12}=4096$	$2^{13}=8192$	$2^{14}=16384$
$2^{15}=32768$	$2^{16}=65536$	$2^{17}=131072$	$2^{18}=262144$	$2^{19}=524288$
$63\times2^{18}=16515072$	$21\times2^{17}=2752512$	$9\times2^{17}=1179648$	$9\times2^{15}=294912$	$35\times2^{13}=286720$

홍익대 서울캠퍼스 2023학년도 수시 오전 자연계열 2번 · mathesis.kr/archive/hongik_seoul/2023su_am/jayeon_2

제시문에서와 같이 $\displaystyle m$ 개의 비트를 송신했을 때 간섭에 의해 변화하는 비트의 개수는 이항분포 $\displaystyle \mathrm{B}(\mathrm{m},\mathrm{p})$ 를 따름을 알 수 있다. 즉, $\displaystyle X$ 를 이항분포 $\displaystyle \mathrm{B}(\mathrm{m},\mathrm{p})$ 를 따르는 이산확률변수라 하면 $\displaystyle m$ 개의 비트를 송신했을 때 간섭에 의해 $\displaystyle k$ 개의 비트가 변화할 확률은 $\displaystyle \mathrm{P}(X=k)=\binom{m}{k}p^{k}(1-p)^{m-k}$ 이다.

$\displaystyle m$ 번 반복해서 보낸 비트를 수신기가 잘못 최종결정할 경우는 $\displaystyle m$ 개의 비트 중 $\displaystyle n+1$ 개 이상의 비트가 간섭에 의해 변화한 경우이다. (단, $\displaystyle m=2n+1$ 이라 하자) 따라서 $\displaystyle m$ -반복 코드의 최종결정 오류 확률은 $\displaystyle \begin{aligned} \mathrm{P}(\mathrm{X}\ge\mathrm{n}+1) &=\mathrm{P}(X=n+1)+\mathrm{P}(X=n+2)+\cdots+\mathrm{P}(X=m) \\ &=\binom{m}{n+1}p^{n+1}(1-p)^{m-(n+1)}+\binom{m}{n+2}p^{n+2}(1-p)^{m-(n+2)}+\cdots+\binom{m}{m}p^{m}(1-p)^{0} \end{aligned}$ 이다.

5점 만점 · 최종결정오류가 발생할 확률의 식을 구함 (2점) 확률값을 계산함 (3점)

(1) $\displaystyle m=3,p=0.1$ 인 경우이다. 위와 같이 최종 결정 오류가 발생할 확률은 $\displaystyle \binom{3}{2}\times0.1^{2}\times0.9+\binom{3}{3}\times0.1^{3}=0.028$ 이다.

5점 만점 · 최종결정오류가 발생할 확률의 식을 구함 (2점) 확률값을 계산함 (2점) (1)에서 구한 값과 비를 반올림하여 소수 첫째 자리까지 구함 (1점)

(2) $\displaystyle m=3,p=0.2$ 인 경우이다. 최종 결정 오류가 발생할 확률은 $\displaystyle \binom{3}{2}\times0.2^{2}\times0.8+\binom{3}{3}\times0.2^{3}=0.104$ 이다.(1)에서 구한 확률과의 비는 $\displaystyle \frac{0.104}{0.028}=3.7142\cdots$ 이고 소수점 둘째 자리에서 반올림하면 3.7 이다.

10점 만점 ·

\displaystyle p=0.2

,

\displaystyle m=5,7,9

인 각 경우 최종결정오류가 발생할 확률의 식을 구하고, 값을 구함 (또는 일부 항의 값을 구하여 확률값을 (1)에서 구한 값과 비교) -

\displaystyle p=0.2, m=5

인 경우 (3점) -

\displaystyle p=0.2, m=7

인 경우 (3점) -

\displaystyle p=0.2, m=9

인 경우 (4점)

(3) $\displaystyle p=0.2$ , $\displaystyle m=5,7,9$ 인 각 경우 최종 결정 오류가 발생할 확률을 문제에서 주어진 표를 이용하여 대략 구하여 (1)에서 구한 값 0.028과 비교한다.

$\displaystyle m=5,p=0.2$ 일 때, 최종 결정 오류가 발생할 확률은 $\displaystyle \binom{5}{3}\times0.2^{3}\times0.8^{2}+\binom{5}{4}\times0.2^{4}\times0.8^{1}+\binom{5}{5}\times0.2^{5}\times0.8^{0}$ 이다. $\displaystyle \binom{5}{3}\times0.2^{3}\times0.8^{2}=0.0512>0.028$ 이므로 이 확률값은 0.028 보다 크다.

마찬가지로 $\displaystyle m=7,p=0.2$ 일 때, 최종 결정 오류가 발생할 확률은 $\displaystyle \binom{7}{4}\times0.2^{4}\times0.8^{3}+\binom{7}{5}\times0.2^{5}\times0.8^{2}+\binom{7}{6}\times0.2^{6}\times0.8^{1}+\binom{7}{7}\times0.2^{7}\times0.8^{0}$ 인데, $\displaystyle \binom{7}{4}\times0.2^{4}\times0.8^{3}=0.028672>0.028$ 이므로 이 확률값은 0.028 보다 크다.

$\displaystyle m=9,p=0.2$ 일 때, 최종 결정 오류가 발생할 확률은 $\displaystyle \binom{9}{5}\times0.2^{5}\times0.8^{4}+\binom{9}{6}\times0.2^{6}\times0.8^{3}+\binom{9}{7}\times0.2^{7}\times0.8^{2}+\binom{9}{8}\times0.2^{8}\times0.8^{1}+\binom{9}{9}\times0.2^{9}\times0.8^{0}$ 이다.

문제에서 주어진 표를 이용하여 계산하면 $\displaystyle \binom{9}{5}\times0.2^{5}\times0.8^{4}+\binom{9}{6}\times0.2^{6}\times0.8^{3}=0.019\cdots$ 이다. $\displaystyle \binom{9}{7}\times0.2^{7}\times0.8^{2}=2.95..\times10^{-4}$ 이고 마지막 두 항은 이 값보다도 작으므로 최종 결정 오류가 발생할 확률은 $\displaystyle 0.019\cdots+3\times(3\times10^{-4})<0.020\cdots$ 보다 작다.따라서 (1)에서 구한 값 0.028 보다 작아지는 $\displaystyle m$ 의 최솟값은 $\displaystyle m=9$ 이다.

질문과 답변 · 0개질문과 답변 · 고정 0개

아직 등록된 질문이 없습니다. 질문 작성은 멤버십 회원만 가능합니다.

자연계열 2번

문제

첨삭 사례

질문과 답변 · 0개질문과 답변 · 고정 0개