108 年 國立成功大學電腦與通信工程研究所乙組《通信數學》

核心觀念

本題考查：

• 二元對稱通道（Binary Symmetric Channel, BSC）的錯誤模型。
• 重複碼（repetition code）與多數決解碼。
• 二項分布的應用。
• 重複傳送對錯誤率、傳輸效率與資源消耗的影響。

每個資訊位元重複傳送 $5$ 次。接收端採用多數決，因此至少需要 $3$ 個接收位元錯誤，才會造成最後判決錯誤。

令單一通道位元發生錯誤的機率為 $p$，正確接收的機率為 $1-p$。

---

解題方法

（a）接收端判決錯誤的機率

資訊位元為 $0$ 時，傳送碼字為 $00000$。接收端判決錯誤，表示接收到的 $1$ 至少有 $3$ 個，也就是通道錯誤數為 $3$、$4$ 或 $5$。

由於每個位元是否錯誤彼此獨立，錯誤位元數 $K$ 服從二項分布：

$$K\sim \mathrm{Binomial}(5,p)$$

因此，

$$P(\text{判決錯誤}\mid X=0) = \sum_{k=3}^{5}\binom{5}{k}p^k(1-p)^{5-k}$$

展開得

$$P(\text{判決錯誤}\mid X=0) = \binom{5}{3}p^3(1-p)^2 +\binom{5}{4}p^4(1-p) +\binom{5}{5}p^5$$ $$= 10p^3(1-p)^2+5p^4(1-p)+p^5$$

資訊位元為 $1$ 時，傳送碼字為 $11111$。要使多數決判成 $0$，同樣需要至少 $3$ 個位元發生錯誤。因此，

$$P(\text{判決錯誤}\mid X=1) = 10p^3(1-p)^2+5p^4(1-p)+p^5$$

由於 $P(X=0)=P(X=1)=1/2$，總錯誤率為

$$\begin{aligned} P_e &=P(X=0)P(\text{錯誤}\mid X=0) \\ &\quad+P(X=1)P(\text{錯誤}\mid X=1) \\ &=\frac12 P(\text{錯誤}\mid X=0) +\frac12 P(\text{錯誤}\mid X=1) \end{aligned}$$

兩個條件錯誤率相同，所以

$$\boxed{ P_e=10p^3(1-p)^2+5p^4(1-p)+p^5 }$$

進一步整理：

$$\boxed{ P_e=10p^3-15p^4+6p^5 }$$

---

（b）與不重複傳送相比的優缺點

不使用重複碼時，每個資訊位元只傳送一次，因此接收錯誤率就是

$$P_{e,\text{single}}=p$$

使用五次重複碼後，錯誤率為

$$P_{e,\text{rep}}=10p^3-15p^4+6p^5$$

優點

當通道本身較可靠，即

$$0\leq p<\frac12$$

重複碼配合多數決可降低錯誤率：

這題考驗對聯合機率密度函數的理解、邊緣機率密度函數、條件機率密度函數的計算，以及條件期望值和條件變異數的求法。題目給定一個在圓盤上的均勻分佈。

核心觀念：

1. 機率密度函數的歸一化 (Normalization)。
2. 邊緣機率密度函數 (Marginal PDF)。
3. 條件機率密度函數 (Conditional PDF)。
4. 條件期望值 (Conditional Expectation)。
5. 條件變異數 (Conditional Variance)。
6. 圓座標轉換。

解題步驟：

首先，我們需要確定常數 $c$ 的值，使聯合機率密度函數 $f_{X,Y}(x,y)$ 滿足歸一化條件，即在整個定義域上的積分為 1。
$\iint_{-\infty}^{\infty} f_{X,Y}(x,y) \,dx\,dy = 1$
題目給定的 $f_{X,Y}(x,y)$ 在圓盤 $x^2+y^2 < r^2$ 上為常數 $c$，在圓盤外為 0。圓盤的面積是 $\pi r^2$。
$\iint_{x^2+y^2 < r^2} c \,dx\,dy = c \times (\text{Area of the disk}) = c (\pi r^2)$
因此，$c (\pi r^2) = 1$，所以 $c = \frac{1}{\pi r^2}$。
聯合機率密度函數為：
$f_{X,Y}(x,y) = \begin{cases} \frac{1}{\pi r^2} & \text{if } x^2+y^2 < r^2 \\ 0 & \text{if elsewhere} \end{cases}$

** Part (a): Determine the conditional pdf $f_{Y|X}(y|x)$ for $-r \le x \le r$. Name this conditional distribution. **

條件機率密度函數 $f_{Y|X}(y|x)$ 的定義是：
$f_{Y|X}(y|x) = \frac{f_{X,Y}(x,y)}{f_X(x)}$
其中 $f_X(x)$ 是 X 的邊緣機率密度函數。我們首先需要計算 $f_X(x)$。
$f_X(x) = \int_{-\infty}^{\infty} f_{X,Y}(x,y) \,dy$
對於 $-r < x < r$，積分範圍是使得 $x^2+y^2 < r^2$ 的 $y$ 值。這意味著 $y^2 < r^2 - x^2$，即 $-\sqrt{r^2-x^2} < y < \sqrt{r^2-x^2}$。
$f_X(x) = \int_{-\sqrt{r^2-x^2}}^{\sqrt{r^2-x^2}} \frac{1}{\pi r^2} \,dy$
$f_X(x) = \frac{1}{\pi r^2} [y]_{-\sqrt{r^2-x^2}}^{\sqrt{r^2-x^2}} = \frac{1}{\pi r^2} (\sqrt{r^2-x^2} - (-\sqrt{r^2-x^2}))$
$f_X(x) = \frac{2\sqrt{r^2-x^2}}{\pi r^2} \quad \text{for } -r < x < r$
當 $x \le -r$ 或 $x \ge r$ 時，$f_X(x) = 0$。

現在我們可以計算條件機率密度函數 $f_{Y|X}(y|x)$：
$f_{Y|X}(y|x) = \frac{f_{X,Y}(x,y)}{f_X(x)} = \frac{\frac{1}{\pi r^2}}{\frac{2\sqrt{r^2-x^2}}{\pi r^2}} \quad \text{for } -\sqrt{r^2-x^2} < y < \sqrt{r^2-x^2}$
$f_{Y|X}(y|x) = \frac{1}{2\sqrt{r^2-x^2}} \quad \text{for } -\sqrt{r^2-x^2} < y < \sqrt{r^2-x^2}$
並且 $f_{Y|X}(y|x) = 0$ 其他情況。
這個條件機率密度函數定義了一個區間 $(- \sqrt{r^2-x^2}, \sqrt{r^2-x^2})$ 上的均勻分佈。

Name this conditional distribution:
The conditional distribution of $Y$ given $X=x$ is a Uniform distribution on the interval $(-\sqrt{r^2-x^2}, \sqrt{r^2-x^2})$.
The interval has length $2\sqrt{r^2-x^2}$. The density is $\frac{1}{2\sqrt{r^2-x^2}}$, which is consistent with a uniform distribution.

** Part (b): Find the conditional expectation $E(Y|X = x)$ for $-r \le x \le r$. **

條件期望值 $E(Y|X=x)$ 是在給定 $X=x$ 的條件下，隨機變數 $Y$ 的期望值。

這題考驗線性代數中關於矩陣、特徵值、秩、線性變換以及矩陣性質的基礎知識。需要判斷四個敘述的正確性。

核心觀念：

1. 特徵值 (Eigenvalues) 與矩陣的秩 (Rank)。
2. 矩陣的性質：可逆性 (Invertibility)。
3. 線性變換 (Linear Transformation)。

解題步驟：

** Part (a): If an $n \times n$ matrix $A$ has $n$ distinct non-zero eigenvalues, then the rank of $A$ is $n$. **

True.
一個 $n \times n$ 的矩陣 $A$ 如果有 $n$ 個不同的特徵值，則這個矩陣是可對角化的 (diagonalizable)。
如果這些特徵值都是非零的，那麼矩陣 $A$ 的 determinant (行列式) 是所有特徵值的乘積。
$\det(A) = \lambda_1 \lambda_2 \cdots \lambda_n$。
因為所有的 $\lambda_i \neq 0$，所以 $\det(A) \neq 0$。
一個方陣的行列式非零當且僅當該矩陣是可逆的 (invertible)。
一個 $n \times n$ 的可逆矩陣的秩 (rank) 是 $n$。
因此，這個敘述是正確的。

** Part (b): If all eigenvalues of an $n \times n$ matrix $A$ are zero, then the rank of $A$ is 0. **

False.
如果一個 $n \times n$ 矩陣 $A$ 的所有特徵值都是零，這意味著 $A$ 的 characteristic polynomial 是 $\lambda^n$。
根據 Cayley-Hamilton 定理，矩陣 $A$ 滿足其 characteristic polynomial，即 $A^n = 0$。
這樣的矩陣稱為冪零矩陣 (nilpotent matrix)。
然而，一個冪零矩陣的秩不一定是 0。
例如，考慮一個 $2 \times 2$ 的矩陣 $A = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$。
它的 characteristic polynomial 是 $\det(A - \lambda I) = \det \begin{pmatrix} -\lambda & 1 \\ 0 & -\lambda \end{pmatrix} = (-\lambda)(-\lambda) - 1 \cdot 0 = \lambda^2$。
所有特徵值都是 0。
但是，矩陣 $A$ 的秩是 1，因為第一行（或第二列）是非零的。

核心觀念

已知 $M$ 是 $4\times 5$ 矩陣，且

$$\operatorname{rank}(M)=4.$$

依秩—零度定理，

$$\dim\ker(M)=5-4=1.$$

因此存在非零向量 $x\in\mathbb{R}^5$，使得

$$Mx=0.$$

另外，對任意 $x\in\mathbb{R}^5$，

$$x^T M^T Mx=(Mx)^T(Mx)=\|Mx\|^2\ge 0.$$

所以 $M^TM$ 是半正定矩陣。其可逆性可由零空間判斷：

$$\ker(M^TM)=\ker(M).$$

證明如下：

若 $Mx=0$，則顯然 $M^TMx=0$。

反之，若 $M^TMx=0$，則

$$0=x^TM^TMx=\|Mx\|^2,$$

故 $Mx=0$。

---

(a) $M^TM$ 是否可能為可逆矩陣？

矩陣 $M^TM$ 的大小為 $5\times 5$。由上面的結果，

$$\ker(M^TM)=\ker(M).$$

而

$$\dim\ker(M)=1,$$

因此 $M^TM$ 存在非零零向量，必定不可逆。

也可直接取非零向量 $x\in\ker(M)$，則

$$Mx=0$$

且

$$M^TMx=M^T(Mx)=M^T0=0.$$

所以 $M^TM$ 有非平凡零空間。

【答案】不可能。$M^TM$ 必定不可逆。

---

(b) $I+M^TM$ 是否為可逆矩陣？