第十四次作业

6.1.

[!QUESTION]
若码长为 100 的 0, 1 符号串, 信道是二元对称, 差错的概率为 0.001, 求满足下列条件的概率:
(1) 无差错;
(2) 恰好一个错;
(3) 恰好两个错;
(4) 多于两个错.

每个比特的传输是独立的, 因此错误比特数 $X$ 服从二项分布 $\mathrm{bin}(n,p)$, 其中 $n=100$, $p=0.001$, 成功概率 (无差错) 为 $q=1-p=0.999$. 二项分布的概率质量函数为:

$$P(X=k)=(\genfrac{}{}{0ex}{}{n}{k})p^k{q}^{n-k},k=0,1,2,\dots ,n$$

(1) 无差错: $P(X=0)$

$$P(X=0)=(\genfrac{}{}{0ex}{}{100}{0})\cdot (0.001{)}^0\cdot (0.999{)}^{100}=1\cdot 1\cdot (0.999{)}^{100}=0.904 792 147 1$$

(2) 恰好一个错: $P(X=1)$

$$P(X=1)=(\genfrac{}{}{0ex}{}{100}{1})\cdot (0.001{)}^1\cdot (0.999{)}^{99}=100\cdot 0.001\cdot (0.999{)}^{99}=0.090 569 784 50$$

(3) 恰好两个错: $P(X=2)$

$$P(X=2)=(\genfrac{}{}{0ex}{}{100}{2})\cdot (0.001{)}^2\cdot (0.999{)}^{98}=0.004 487 692 025$$

(4) 多于两个错: $P(X>2)$

$$P(X>2)=1-P(X=0)-P(X=1)-P(X=2)=0.000 150 376 365 9$$

6.6.

[!QUESTION]
设 $C$ 是长为 n 的线性码, 在 $C$ 中权为偶数的码字未端加 0, 在权为奇数的码字未端加 1, 从而形成一新的码 $C^{\prime }$,
(1) 若 $\mathbf{H}$ 是 $C$ 的校验矩阵, 则 $C^{\prime }$ 的校验矩阵为

$$\left[\begin{array}{cccc}1& 1& \cdots & 1\\ & & & 0\\ & \mathbf{H}& & ⋮\\ & & & 0\end{array}\right]$$

(2) 证明 $C^{\prime }$ 的任意两个码间的距离为偶数.
(3) 证明若 $C$ 的两个码间的最小距离 $d$ 是奇数, 则 $C^{\prime }$ 对应码间最小距离为 $d+1$.

(1)

设 $C$ 是长为 $n$ 的线性码, 其校验矩阵为 $\mathbf{H}$, 大小为 $ (n-k) \times n$, 其中 $k$ 是 $C$ 的维数. 新码 $C^{\prime }$ 是通过在每个码字 $\mathbf{c}\in C$ 的末端添加一个比特形成的: 若 $\mathbf{c}$ 的权重 (即 1 的个数) 为偶数, 则加 0；若权重为奇数, 则加 1. 因此, $C^{\prime }$ 的码字形式为 ${\mathbf{c}}^{\prime }=(c_1,c_2,\dots ,c_n,p)$, 其中 $p=\sum _{i=1}^n{c}_i\mathrm{mod}2$, 且 $\mathbf{c}=(c_1,c_2,\dots ,c_n)\in C$.

$C^{\prime }$ 的校验矩阵 ${\mathbf{H}}^{\prime }$ 应满足 ${\mathbf{H}}^{\prime }({\mathbf{c}}^{\prime }{)}^T=\mathbf{0}$ 当且仅当 ${\mathbf{c}}^{\prime }\in C^{\prime }$. 这等价于以下两个条件:

• 前 $n$ 位 $\mathbf{c}=(c_1,\dots ,c_n)$ 属于 $C$, 即 $\mathbf{H}{\mathbf{c}}^T=\mathbf{0}$.
• 总和 $\sum _{i=1}^{n+1}{c}_i=0\mathrm{mod}2$, 即 $c_1+c_2+\cdots +c_n+c_{n+1}=0$.

给定矩阵为:

$${\mathbf{H}}^{\prime }=\left[\begin{array}{cccc}1& 1& \cdots & 1\\ & & & 0\\ & \mathbf{H}& & ⋮\\ & & & 0\end{array}\right]$$

该矩阵大小为 $ (n-k+1) \times (n+1)$. 其结构为:

• 第一行是全 1 的行向量 ${\mathbf{1}}_{n+1}=(1,1,\dots ,1)$, 长度为 $n+1$.
• 剩余部分为 $\mathbf{H}$ 右侧添加一列全 0 向量, 即 $\left[\begin{array}{cc}\mathbf{H}& \mathbf{0}\end{array}\right]$, 其中 $\mathbf{0}$ 是 $ (n-k) \times 1$ 零列向量.

因此, ${\mathbf{H}}^{\prime }$ 可明确写为:

$${\mathbf{H}}^{\prime }=\left[\begin{array}{c}{\mathbf{1}}_{n+1}\\ \mathbf{H}& \mathbf{0}\end{array}\right]$$

现在验证 ${\mathbf{H}}^{\prime }$ 是 $C^{\prime }$ 的校验矩阵:

• 若 ${\mathbf{c}}^{\prime }\in C^{\prime }$, 则 $\mathbf{c}\in C$, 故 $\mathbf{H}{\mathbf{c}}^T=\mathbf{0}$, 且 $\sum _{i=1}^{n+1}{c}_i=0$. 因此:$${\mathbf{H}}^{\prime }({\mathbf{c}}^{\prime }{)}^T=\left[\begin{array}{c}{\mathbf{1}}_{n+1}({\mathbf{c}}^{\prime }{)}^T\\ \left[\begin{array}{cc}\mathbf{H}& \mathbf{0}\end{array}\right]({\mathbf{c}}^{\prime }{)}^T\end{array}\right]=\left[\begin{array}{c}\sum _{i=1}^{n+1}{c}_i\\ \mathbf{H}{\mathbf{c}}^T\end{array}\right]=\left[\begin{array}{c}0\\ \mathbf{0}\end{array}\right]=\mathbf{0}$$

$$- 若 $\mathbf{H}' (\mathbf{c}') ^T = \mathbf{0}$, 则: - $\begin{bmatrix} \mathbf{H} & \mathbf{0} \end{bmatrix} (\mathbf{c}') ^T = \mathbf{H} \mathbf{c}^T = \mathbf{0}$, 故 $\mathbf{c} \in C$. - $\mathbf{1}_{n+1} (\mathbf{c}') ^T = \sum_{i=1}^{n+1} c_i = 0$. 由 $\mathbf{c} \in C$ 和 $\sum_{i=1}^{n+1} c_i = 0$, 得 $c_{n+1} = \sum_{i=1}^n c_i$, 故 $\mathbf{c}' \in C'$. 此外, $\mathbf{H}'$ 的行线性无关: $\mathbf{H}$ 的行线性无关, $\begin{bmatrix} \mathbf{H} & \mathbf{0} \end{bmatrix}$ 的行也线性无关 (添加零列不改变线性无关性) , 且 $\mathbf{1}_{n+1}$ 与 $\begin{bmatrix} \mathbf{H} & \mathbf{0} \end{bmatrix}$ 的行线性无关 (因为 $\mathbf{1}_{n+1}$ 的最后一个分量为 1, 而 $\begin{bmatrix} \mathbf{H} & \mathbf{0} \end{bmatrix}$ 的最后一列为 0). 因此, $\mathbf{H}'$ 是 $C'$ 的校验矩阵. ### (2) $C'$ 是线性码 (因为 $C$ 线性, 且添加位 $p = \sum_{i=1}^n c_i$ 是线性操作). 对于线性码, 任意两个码字 $\mathbf{c}_1', \mathbf{c}_2' \in C'$ 间的汉明距离 $d (\mathbf{c}_1', \mathbf{c}_2')$ 等于其差向量的权重, 即 $d (\mathbf{c}_1', \mathbf{c}_2') = \operatorname{wt} (\mathbf{c}_1' - \mathbf{c}_2')$. 由于 $C'$ 线性, $\mathbf{c}_1' - \mathbf{c}_2' \in C'$, 故只需证明 $C'$ 中所有非零码字的权重均为偶数. 由 $C'$ 的构造, 对任意 $\mathbf{c}' = (c_1, \ldots, c_n, p) \in C'$, $p = \sum_{i=1}^n c_i \mod 2$ 使得总权重 $\sum_{i=1}^{n+1} c_i = 0 \mod 2$, 即 $\operatorname{wt} (\mathbf{c}')$ 为偶数. 因此: - 若 $\mathbf{c}' = \mathbf{0}$, 则 $\operatorname{wt} (\mathbf{c}') = 0$ (偶数). - 若 $\mathbf{c}' \neq \mathbf{0}$, 则 $\operatorname{wt} (\mathbf{c}')$ 为偶数. 故 $C'$ 中所有码字的权重均为偶数. 进而, 对任意 $\mathbf{c}_1', \mathbf{c}_2' \in C'$, 有 $d (\mathbf{c}_1', \mathbf{c}_2') = \operatorname{wt} (\mathbf{c}_1' - \mathbf{c}_2')$ 为偶数. ### (3) 设 $C$ 的最小距离为 $d$ (奇数) , 即 $d = \min_{\mathbf{c} \in C, \mathbf{c} \neq \mathbf{0}} \operatorname{wt} (\mathbf{c})$. 由于 $C$ 线性, $d$ 也是 $C$ 的最小权重. $C'$ 的最小距离 $d'$ 等于其最小权重, 即 $d' = \min_{\mathbf{c}' \in C', \mathbf{c}' \neq \mathbf{0}} \operatorname{wt} (\mathbf{c}')$. 对任意非零 $\mathbf{c}' \in C'$, 对应 $\mathbf{c} \in C$ 非零, 且 $\mathbf{c}' = (\mathbf{c}, p)$ 其中 $p = \sum_{i=1}^n c_i \mod 2$. $\operatorname{wt} (\mathbf{c}')$ 的计算如下: - 若 $\operatorname{wt} (\mathbf{c})$ 为偶数, 则 $p = 0$, 故 $\operatorname{wt} (\mathbf{c}') = \operatorname{wt} (\mathbf{c})$. - 若 $\operatorname{wt} (\mathbf{c})$ 为奇数, 则 $p = 1$, 故 $\operatorname{wt} (\mathbf{c}') = \operatorname{wt} (\mathbf{c}) + 1$. 由于 $d$ 是奇数, 且 $\operatorname{wt} (\mathbf{c}) \geqslant d$ 对所有非零 $\mathbf{c} \in C$ 成立. - 若 $\operatorname{wt} (\mathbf{c})$ 为偶数, 则 $\operatorname{wt} (\mathbf{c}) \geqslant d + 1$ (因为 $d$ 奇数, $\operatorname{wt} (\mathbf{c}) \geqslant d$ 且为偶数, 故 $\operatorname{wt} (\mathbf{c}) \geqslant d + 1$) , 所以 $\operatorname{wt} (\mathbf{c}') = \operatorname{wt} (\mathbf{c}) \geqslant d + 1$. - 若 $\operatorname{wt} (\mathbf{c})$ 为奇数, 则 $\operatorname{wt} (\mathbf{c}) \geqslant d$, 所以 $\operatorname{wt} (\mathbf{c}') = \operatorname{wt} (\mathbf{c}) + 1 \geqslant d + 1$. 此外, 存在 $\mathbf{c} \in C$ 非零使得 $\operatorname{wt} (\mathbf{c}) = d$ (由最小权重的定义). 由于 $d$ 奇数, $\operatorname{wt} (\mathbf{c})$ 为奇数, 故对应 $\mathbf{c}' \in C'$ 满足 $\operatorname{wt} (\mathbf{c}') = d + 1$. 综上, $C'$ 中所有非零码字的权重至少为 $d + 1$, 且存在权重为 $d + 1$ 的码字, 故 $d' = d + 1$. 因此, $C'$ 的最小距离为 $d + 1$. ## 6.10. > [!QUESTION] > 证明 $2 t + 1$ 重复码可以纠正 $t$ 个错. ### 编码 - 如果原始信息位是 0, 那么编码后的码字是 $C_0 = \underbrace{00...0}_{2t+1 \text{ 次}}$. - 如果原始信息位是 1, 那么编码后的码字是 $C_1 = \underbrace{11...1}_{2t+1 \text{ 次}}$. ### 译码 (纠错) 假设发送的码字是 $C$. 由于信道中可能存在噪声, 接收到的码字可能是 $R$. 我们使用 **多数译码** (majority decoding) 规则来进行译码. 具体来说, 我们检查接收到的码字 $R$ 中 0 和 1 的数量. - 如果 0 的数量大于 1 的数量, 则译码为 0. - 如果 1 的数量大于 0 的数量, 则译码为 1. ### 证明纠错能力 假设我们发送了一个码字 (例如, 对应信息位 0 的 $C_0 = 00...0$). 设接收到的码字为 $R$. 如果在传输过程中发生了 $k$ 个错误, 那么 $R$ 中将有 $k$ 个位与原始码字中的对应位不同. #### 情况 1: 发送的是 $C_0 = 00...0$ 如果发生了 $k$ 个错误, 那么接收到的码字 $R$ 将包含 $k$ 个 1 和 $ (2t+1-k)$ 个 0. 为了能正确译码回 0, 接收到的码字中 0 的数量必须大于 1 的数量. 即: $ (2t+1-k) > k$. 化简得: $2t+1 > 2k$. 或者: $k < t + 1/2$. 由于 $k$ 必须是整数, 所以 $k \le t$. 这意味着如果错误的数量 $k$ 不超过 $t$ (即 $k \le t$) , 那么 $2t+1-k \ge t+1$, 而 $k \le t$. 因此, $0$ 的数量 $ (2t+1-k)$ 仍然会大于 $1$ 的数量 $k$. 译码器将正确地译码为 0. #### 情况 2: 发送的是 $C_1 = 11...1$ 如果发生了 $k$ 个错误, 那么接收到的码字 $R$ 将包含 $k$ 个 0 和 $ (2t+1-k)$ 个 1. 为了能正确译码回 1, 接收到的码字中 1 的数量必须大于 0 的数量. 即: $ (2t+1-k) > k$. 化简得: $2t+1 > 2k$. 或者: $k < t + 1/2$. 由于 $k$ 必须是整数, 所以 $k \le t$. 这意味着如果错误的数量 $k$ 不超过 $t$ (即 $k \le t$) , 那么 $2t+1-k \ge t+1$, 而 $k \le t$. 因此, $1$ 的数量 $ (2t+1-k)$ 仍然会大于 $0$ 的数量 $k$. 译码器将正确地译码为 1. 在这两种情况下, 只要发生的错误数量 $k$ 满足 $k \le t$, 多数译码规则都能将接收到的码字 $R$ 正确地译码回原始的信息位. 如果发生了 $t+1$ 个错误: - 假设发送 $C_0 = 00...0$. 发生 $t+1$ 个错误后, $R$ 中有 $t+1$ 个 1 和 $ (2t+1) - (t+1) = t$ 个 0. 此时, $1$ 的数量 ($t+1$) 大于 $0$ 的数量 ($t$) , 译码器会错误地译码为 1. - 假设发送 $C_1 = 11...1$. 发生 $t+1$ 个错误后, $R$ 中有 $t+1$ 个 0 和 $ (2t+1) - (t+1) = t$ 个 1. 此时, $0$ 的数量 ($t+1$) 大于 $1$ 的数量 ($t$) , 译码器会错误地译码为 0. 因此, $2t+1$ 重复码可以纠正最多 $t$ 个错误, 但不能纠正 $t+1$ 个或更多错误. $$